【数据结构】线性表 顺序表（动态、静态分配，插入删除查找基本操作）解析+完整代码

1.线性表的基本概念

  • 定义

    线性表（Linear List）是具有相同数据类型的n个数据元素的有限序列。

    • n为表长，n=0时线性表是个空表

  • 前驱、后继

    • 前驱：其中一个数据元素的前一个元素。第一个元素没有前驱。
    • 后继：其中一个数据元素的后一个元素。最后一个元素没有后继。

  • 存储/物理结构

    • 顺序表（顺序存储）
    • 链表（链式存储）

2.顺序表

2.1 顺序表的定义

  • 顺序表定义

    用顺序存储方式实现线性表的储存。

    是用一组地址连续的存储单元依次存储线性表中的数据元素。

    • 特点：

      1.表中元素的逻辑顺序与物理顺序相同。

      2.可以随机存取——知道顺序表起始位置LOC(A)和每个元素所占内存的大小sizeof(ElemType)后，可知道任意一个元素的位置。

  • 优点

    1.可随机访问，O(1)时间内找到指定元素；

    2.存储密度高，每个结点只存储数据元素。

  • 缺点

    1.元素的插入和删除要移动大量数据元素。

    2.需要连续存储空间，不够灵活。

2.1.1 静态分配
//静态分配结构存储
#define MaxSize 10 //最大长度
typedef struct{
    int data[MaxSize]; //静态数组存放数据元素
    int length; //顺序表当前长度
}SqList; //顺序表类型定义

//静态分配初始化
void InitList(SqList &L){
    L.Length=0;
}

  • 如果数组存满怎么办？

    没办法了，因为顺序表表长刚开始确定后就无法改变，∴有了动态分配

2.1.2 动态分配
//动态分配结构存储
#define InitSize 100 //表长度的初始定义
typedef struct{
    ElemType *data; //指示动态分配数组的指针
    int MaxSize; //最大容量
    int length; //当前个数
}SeqList;

//动态分配初始化
void InitList(SeqList &L){
    L.data=(ElemType*)malloc(MaxSize*sizeof(ElemType));
    L.length=0;
    L.MaxSize=InitSize;
}

C动态分配语句

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
free(L.data);

C++动态分配语句

L.data=new ElemType[InitSize];
delete[]指针变量名;
或
delete 指针变量名;

  • 增加动态数组长度

    void IncreaseSize(SeqList &L,int len){
    int *p=L.data; //将表中数据存储到p中
    L.data=(int*)malloc((L.MaxSize+len)*sizeof(int)); //开辟新空间
    for(int i=0;i<L.length;i++)
    {
        L.data[i]=p[i]; //数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;
    free(p);
}

  • 注：动态分配不是链式存储，同样顺序存储，只是空间大小可变。

2.2 顺序表的插入

  • 原理

    在线性表L的第i个位置插入元素e：

    将第i个元素及其后面的所有元素向后移一位，腾出空位插e。

    > 

//在L的位序i处插入元素e
bool ListInsert(SqList &L,int i,int e){
    //判i范围是否有效
    if(i<1||i>L.length+1)return false;
    //判存储空间是否已满
    if(L.length>=MaxSize)return false;
    
    //将第i个元素及之后元素后移
    for(int j=L.length;j>=i;j--) 
    {
        L.data[j]=L.data[j-1]; //注意：位序和数组下标的关系，并从后面元素依次移动
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

  • 时间复杂度

    • 最好情况：在表尾插入，元素后移不用执行，O(1)。
    • 最坏情况：在表头插入，元素后移执行n次，O(n)。
    • 平均情况：O(n/2)，即O(n)。

2.3 顺序表的删除

  • 原理

    删除顺序表L中的第i个元素：

    将被删元素赋给引用变量e，将第i+1个元素及其后的所有元素往前移一位。

//删除L中的第i个元素，并用返回
bool ListDelete(SqList &L,int i,ElemType &e){
    if(i<1||i>L.length)return false;
    
    e=L.data[i-1]; //被删元素给引用变量
    //被删元素后的元素依次后移
    for(int j=i;j<L.length;j++){
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}

  • 时间复杂度

    • 最坏情况：删除表尾元素，无需移动元素，O(1)。
    • 最好情况：删除表头元素，需移动除表尾外的所有元素，O(n)。
    • 平均情况：O(n/2)，即O(n)。

2.4 顺序表的查找

2.4.1 按位查找
ElemType GetElem(SqList L,int i){
    return L.data[i-1];
}
  • 时间复杂度：O(1)
2.4.2 按序查找
int LocateElem(SqList L,ElemType e){
    int i;
    for(i=0;i<L.length;i++)
    {
        if(L.data[i]==e)return i+1; //找到了返回位序
    }
    return 0; //没找到返回0
}
  • 时间复杂度：O(n)

*完整代码 顺序表静态存储

//顺序表 静态分配 线性表下标从0开始
#include<stdio.h>

#define ElemType int

//静态结构体
#define MaxSize 99
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//初始化
void InitList(SqList &L)
{
	L.length = 0;
}

//求表长
int Length(SqList &L) 
{
	return L.length;
}

//按值查找
int LocateElem(SqList &L,ElemType e) 
{
	for (int i = 0; i < L.length; i++) 
	{
		if (L.data[i] == e) 
		{
			return i + 1;
		}
	}
	return 0;
}

//按位查找
int GetItem(SqList& L, int i) 
{
	return L.data[i-1]; //i是位序，而顺序表从0开始存的，所以i要-1
}

//插入操作
bool ListInsert(SqList& L, int i, ElemType e) 
{
	if (i<1 || i>L.length)return false;
	if (L.length >= MaxSize)return false;

	for (int j = L.length; j >= i; j--) 
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i-1] = e; 
	L.length++;
	return true;
}

//删除操作
bool ListDelete(SqList& L, int i, ElemType& e) 
{
	if (i<1 || i>L.length)return false;

	e = L.data[i-1];
	for (int j = i; j <L.length; j++) 
	{
		L.data[j-1] = L.data[j];
	}
	L.length--;
	return true;
}

//判空操作
bool Empty(SqList& L)
{
	if (L.length == 0)
		return true;
	else
		return false;
}

//销毁操作
void DestroyList(SqList &L)
{
	L.length = 0;
}

//输出
void PrintList(SqList& L) 
{
	for (int i = 0; i < L.length; i++)
	{
		printf("%d ", L.data[i]);
	}
	printf("\n");
}

int main()
{
	SqList L;
	InitList(L);
	//赋值
	for (int i = 0; i < 10; i++)
	{
		L.data[i] = i;
		L.length++;
	}
	PrintList(L);

	printf("插入:\n");
	int e = -1, pos = 4;
	ListInsert(L, pos , e);
	PrintList(L);

	printf("删除:\n");
	int a;
	ListDelete(L, pos, a);
	PrintList(L);
	printf("%d\n", a);

	printf("按值查找:\n");
	pos = LocateElem(L, 5);
	printf("%d\n", pos);

	printf("按位查找:\n");
	printf("%d", GetItem(L, 3));
}

请添加图片描述

*完整代码 顺序表动态存储

//顺序表 动态分配 
#include<stdio.h>
#include <stdlib.h>

#define ElemType int

//静态结构体
#define InitSize 2
typedef struct {
	ElemType *data;
	int length;
	int MaxSize;
}SeqList;

//初始化
void InitList(SeqList& L)
{
	L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
	L.length = 0;
	L.MaxSize = InitSize;
}

//增加动态数组长度
void IncreaseSize(SeqList& L, int len) {
	int* p = L.data; //将表中数据存储到p中
	L.data = (int*)malloc((L.MaxSize + len) * sizeof(int)); //开辟新空间
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = p[i]; //数据复制到新区域
	}
	L.MaxSize = L.MaxSize + len;
	free(p);
}

//求表长
int Length(SeqList& L)
{
	return L.length;
}

//按值查找
int LocateElem(SeqList& L, ElemType e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == e)
		{
			return i + 1;
		}
	}
	return 0;
}

//按位查找
int GetItem(SeqList& L, int i)
{
	return L.data[i - 1]; //i是位序，而顺序表从0开始存的，所以i要-1
}

//插入操作
bool ListInsert(SeqList& L, int i, ElemType e)
{
	if (i<1 || i>L.length)return false;
	if (L.length >= L.MaxSize)return false;

	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e; 
	L.length++;
	return true;
}

//删除操作
bool ListDelete(SeqList& L, int i, ElemType& e)
{
	if (i<1|| i>L.length)return false;

	e = L.data[i - 1];
	for (int j = i; j < L.length; j++)
	{
		L.data[j - 1] = L.data[j];
	}
	L.length--;
	return true;
}

//判空操作
bool Empty(SeqList& L)
{
	if (L.length == 0)
		return true;
	else
		return false;
}

//销毁操作
void DestroyList(SeqList& L)
{
	free(L.data);
	L.data = NULL; // 避免悬挂指针
	L.length = 0;
}

//输出
void PrintList(SeqList& L)
{
	for (int i = 0; i < L.length; i++)
	{
		printf("%d ", L.data[i]);
	}
	printf("\n");
}

int main()
{
	SeqList L;
	InitList(L);
	IncreaseSize(L, 9);

	//赋值
	for (int i = 0; i < 10; i++)
	{
		L.data[i] = i;
		L.length++;
	}
	PrintList(L);

	printf("插入:\n");
	int e = -1, pos = 5;
	ListInsert(L, pos, e);
	PrintList(L);

	printf("删除:\n");
	int a;
	ListDelete(L, pos, a);
	PrintList(L);
	printf("%d\n", a);

	printf("按值查找:\n");
	pos = LocateElem(L, 5);
	printf("%d\n", pos);

	printf("按位查找:\n");
	printf("%d", GetItem(L, 3));

	DestroyList(L);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/422021.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

chalk库的使用

chalk库的使用

这篇文章主要是对chalk库官方文档的中文翻译以及我自己的一些理解。chalk的官方文档可以看这里。 首先说下chalk库的作用&#xff1a;美化终端输出的文本&#xff0c;例如添加不同的字体颜色、不同颜色的背景、粗体以及添加下划线等等&#xff0c;看下图&#xff1a; 优点 富…
阅读更多...
新一代湖仓集存储，多模型统一架构，高效挖掘数据价值

新一代湖仓集存储，多模型统一架构，高效挖掘数据价值

星环科技TDH一直致力于给用户带来高性能、高可靠的一站式大数据基础平台&#xff0c;满足对海量数据的存储和复杂业务的处理需求。 同时在易用性方面持续深耕&#xff0c;降低用户开发和运维成本&#xff0c;让数据处理平民化&#xff0c;助力用户以更便捷、高效的方式去挖掘数…
阅读更多...
Node.js+vue校内二手物品交易系统tdv06-vscode前后端分离

Node.js+vue校内二手物品交易系统tdv06-vscode前后端分离

二手物品交易系统采用B/S架构&#xff0c;数据库是MySQL。网站的搭建与开发采用了先进的nodejs进行编写&#xff0c;使用了vue框架。该系统从三个对象&#xff1a;由管理员和用户、店铺来对系统进行设计构建。主要功能包括&#xff1a;个人信息修改&#xff0c;对用户、店铺、二…
阅读更多...
美剧推荐|2024值得期待的二十部美剧，你心里的TOP1是哪一部

美剧推荐|2024值得期待的二十部美剧，你心里的TOP1是哪一部

关注公众号&#xff1a;萌番bilfun&#xff0c;发送影片名称&#xff0c;即可获取资源链接 2023必看十部美剧推荐&#xff1a; 面目全非&#xff0c;堡垒&#xff0c;暗夜情报员&#xff0c;猎魔人第三季&#xff0c;阿索卡&#xff0c;洲际酒店&#xff0c;怒呛人生&#xf…
阅读更多...
Linux 学习笔记(8)

Linux 学习笔记(8)

八、 启动引导 1 、 Linux 的启动流程 1) BIOS 自检 2) 启动 GRUB/LILO 3) 运行 Linux kernel 并检测硬件 4) 挂载根文件系统 5) 运行 Linux 系统的第一个进程 init( 其 PID 永远为 1 &#xff0c;是所有其它进程的父进程 ) 6) init 读取系统引导配置文件…
阅读更多...
2D割草/吸血鬼游戏 性能优化——GPU Spine动画

2D割草/吸血鬼游戏 性能优化——GPU Spine动画

视频中万人同屏方案(gpu动画、渲染、索敌、避障等功能)&#xff0c;可某宝搜店铺&#xff1a;【游戏开发资源商店】获取整套方案源码。 在过去的几年里&#xff0c;割草、类吸血鬼玩法的游戏频出爆款&#xff0c;其丰富的技能、满屏特效、刷怪清屏的解压畅快是此类游戏的核心&…
阅读更多...
uni-app部署H5到相对路径，支持file协议打开

uni-app部署H5到相对路径，支持file协议打开

uni-app支持部署H5到相对路径&#xff0c;部署到服务端或在本地使用file协议打开均可 配置 在manifest.json文件中配置&#xff0c;Web配置->运行的基础路径配置为./即可 例:/5/&#xff0c;代表在域名的/5目录下部署运行。如设为./&#xff0c;则代表相对路径&#xff0c…
阅读更多...
TCP为什么要三次握手？

TCP为什么要三次握手？

TCP三次握手协议是为了在不可靠的互联网环境中可靠地建立起一个连接&#xff0c;三次握手可以确保两端的发送和接收能力都是正常的。 那么&#xff0c;为什么是三次而不是二次或四次握手呢&#xff1f; 为什么不是二次握手&#xff1f; 如果是二次握手&#xff0c;即客户端发…
阅读更多...
QT TCP传输文件+ui

QT TCP传输文件+ui

TCPFile tcp协议传输文件 TCPFile.pro QT core gui networkclientwidget.h #include <QWidget> #include <QTcpSocket> // 通信套接字 #include <QFile>private slots:void on_pushButton_clicked();private:QTcpSocket *tcpSocket;QFile file; /…
阅读更多...
openGauss学习笔记-232 openGauss性能调优-系统调优-资源负载管理-资源管理准备-资源规划

openGauss学习笔记-232 openGauss性能调优-系统调优-资源负载管理-资源管理准备-资源规划

文章目录 openGauss学习笔记-232 openGauss性能调优-系统调优-资源负载管理-资源管理准备-资源规划 openGauss学习笔记-232 openGauss性能调优-系统调优-资源负载管理-资源管理准备-资源规划 完成资源负载管理功能配置前&#xff0c;需要先根据业务模型完成租户资源的规划。业…
阅读更多...
2024年10个超炫酷的前端 3D 开源项目，那几个你用？

2024年10个超炫酷的前端 3D 开源项目，那几个你用？

本文将分享 10 个超炫酷的前端 3D 开源项目。从令人惊叹的视觉效果到富有创新概念的交互体验&#xff0c;这些项目展示了前端技术的无限可能。无论你是新手还是经验丰富的开发者&#xff0c;都值得一探究竟&#xff01; 蛋仔派对&#xff08;three.js版&#xff09; 利用 Rea…
阅读更多...
安卓使用ExoPlayer出现膨胀类异常

安卓使用ExoPlayer出现膨胀类异常

1.导包 implementation com.google.android.exoplayer:exoplayer-core:2.15.1implementation com.google.android.exoplayer:exoplayer-ui:2.15.1 2.在Androidifest.xml加入权限&#xff0c;我这里加了忘了与读写权限 <uses-permission android:name"android.permissio…
阅读更多...
Crime Scene Report 犯罪现场报告 Python字符串处理

Crime Scene Report 犯罪现场报告 Python字符串处理

Crime Scene Report 犯罪现场报告 Victim and Suspect were hiking along a remote trail in the Mojave Desert. By the time Victim and Suspect were able to hike back to the trailhead and receive medical attention, Victim was in critical condition. Suspect repor…
阅读更多...
用HTML5的＜canvas＞元素实现刮刮乐游戏

用HTML5的＜canvas＞元素实现刮刮乐游戏

用HTML5的&#xff1c;canvas&#xff1e;元素实现刮刮乐游戏 用HTML5的<canvas>元素实现刮刮乐&#xff0c;要求&#xff1a;将上面的“图层”的图像可用鼠标刮去&#xff0c;露出下面的“图层”的图像。 示例从简单到复杂。 简单示例 准备两张图像&#xff0c;我这…
阅读更多...
鸿蒙学习day1基础语法 基础变量类型

鸿蒙学习day1基础语法 基础变量类型

在这里插入图片描述 什么是变量&#xff1a;变量就是一些数据 如125&#xff0c;‘字符串数据’ 通过一个符号来表示 变量的定义 方法 let 变量名&#xff1a;变量类型 ’ 各种数据’ ,let是关键字&#xff0c;系统给的用来定义变量的 let name: string 张亚洲; let age: …
阅读更多...
《求生之路2》服务器如何选择合适的内存和CPU核心数，以避免丢包和延迟高？

《求生之路2》服务器如何选择合适的内存和CPU核心数，以避免丢包和延迟高？

根据求生之路2服务器的实际案例分析选择合适的内存和CPU核心数以避免丢包和延迟高的问题&#xff0c;首先需要考虑游戏的类型和对服务器配置的具体要求。《求生之路2》作为一款多人在线射击游戏&#xff0c;其服务器和网络优化对于玩家体验至关重要。 首先&#xff0c;考虑到游…
阅读更多...
Flutter中Widget的生命周期

Flutter中Widget的生命周期

Widget生命周期&#xff1a; createState-initState-didChangeDependency-build-deactive-dispose 可通过WidgetsBinding类对widget生命周期的回调进行监控。 createState&#xff1a;StatefulWidget 中用于创建 State&#xff1b; initState&#xff1a;State 的初始化操作&am…
阅读更多...
Ubuntu22.04下在Spark2.4.0中采用Local模式配置并启动pyspark

Ubuntu22.04下在Spark2.4.0中采用Local模式配置并启动pyspark

目录 一、前言 二、版本信息 三、配置相关文件 1.修改spark-env.sh文件 2.修改.bashrc文件 四、安装Python3.5.2并更改默认Python版本 1.查看当前默认Python版本 2.安装Python3.5.2 2.1 下载Python源码 2.2 解压源码 2.3 配置安装路径 2.4 编译和安装 2.5 验证安装…
阅读更多...
【计算机网络_应用层】协议定制序列化反序列化

【计算机网络_应用层】协议定制序列化反序列化

文章目录 1. TCP协议的通信流程2. 应用层协议定制3. 通过“网络计算器”的实现来实现应用层协议定制和序列化3.1 protocol3.2 序列化和反序列化3.2.1 手写序列化和反序列化3.2.2 使用Json库 3.3 数据包读取3.4 服务端设计3.5 最后的源代码和运行结果 1. TCP协议的通信流程 在之…
阅读更多...
c++/c图的邻近矩阵表示

c++/c图的邻近矩阵表示

#include<iostream> using namespace std;#define MaxVerterNum 100 typedef char VerterType; typedef int EdgeType; typedef struct {VerterType vexs[MaxVerterNum]; // 存储顶点EdgeType edges[MaxVerterNum][MaxVerterNum]; // 存储邻接矩阵int n, e; // 顶点数和边…
阅读更多...
最新文章

Copyright @ 2022~2023