基于C语言的数据结构之顺序表——带你熟练掌握顺序表基本操作！！超级详细！！-Toy模板网

这篇具有很好参考价值的文章主要介绍了基于C语言的数据结构之顺序表——带你熟练掌握顺序表基本操作！！超级详细！！。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

1.源代码如下

2.数据结构——顺序表

2.1.顺序表的特点

2.2顺序表的分类

2.2.1.动态分配内存的顺序表

2.2.2.静态分配内存的顺序表

2.3.定义一个顺序表

3.顺序表的基本操作

3.1初始化顺序表

不用将顺序表中可能存在的原有元素初始化吗？

原因

3.2求元素个数

3.3插入元素*

基本步骤与思路

各步骤目的

3.4删除元素*

基本步骤与思路

各步骤目的

3.5获取元素

结束语

前言：

顺序表是数据结构中最为基础，也是最为简单的结构。后面的栈，队列，串等结构和顺序表有密切关系，要学好数据结构，顺序表必定要掌握！！👍

1.源代码如下

#代码很长，展示了顺序表全部基本操作，不用细看，由我接下来细细分开讲解。

#define MaxSize 100  //静态内存
#include<stdio.h>
typedef int score;//将datatype设置为了成绩score（便于简单理解）
typedef struct 
{
	score list[MaxSize];
	int size;
}SeqList;//顺序表定义（此处为成绩列表）

//顺序表的操作：
//一、初始化
void ListInitiate(SeqList* L)//传入顺序表地址
{	
	L->size = 0;//初始长度为0，无元素
}//有地址有长度---》》》创建顺序表完成

//二、求当前元素个数（将长度返回）
int ListLength1(SeqList* L)//传入地址找size
{
	return L->size;
}
int ListLength2(SeqList L)//传入整个表找size
{
	return L.size;
}

//三、插入元素
//#默认i的合法范围为i∈[0,size)#
/*接受int返回值1或0，判断插入成败(后面同理)*/
int ListInsert(SeqList* L, int i, score x)//i为插入位置，x为插入的元素
{
	//1.先判断能否插入：
	if (L->size == MaxSize)
	{
		printf("无法插入，内存不足！");
		return 0;//直接退出（下同）
	}
	//2.再判断传入的i是否合法（即未超出范围）：
	else if (i < 0 || i > L->size)
	{
		printf("i的输入不合法，无法插入！");
		return 0;//直接退出
	}
	//3.开始插入:
	else
	{
		for (int j = L->size; j > i; j--) L->list[j] = L->list[j - 1];//将插入位置后面的元素整体后移
		L->list[i] = x;//覆盖i处原元素
		L->size++;//长度加1
		return 1;
	}
}

//四、删除元素
int ListDelete(SeqList* L, int i, score* x)//i为删除元素的位置，x保存删除的元素等待另外处置
{
	//先判断i是否合法（同上）
	if (i < 0 || i > L->size)
	{
		printf("i的输入不合法，无法删除");
		return 0;
	}
	//再判断能否再删
	else if (L->size == 0)
	{
		printf("已无元素可删！");
		return 0;
	}
	//开始删除
	else
	{
		*x = L->list[i];//先保存
		for (int j = i; j < L->size; j++)//再往前覆盖
		{
			L->list[j] = L->list[j+1];
		}
		L->size--;//长度减1
		return 1;
	}
}

//五、获取元素
int ListGet(SeqList* L, int i, score* x)//x接受获取到的元素
{
	//判断i输入合法性（下同）
	if (i < 0 || i > L->size)
	{
		printf("i的输入不合法，无法获取！");
		return 0;
	}
	else
	{
		*x = L->list[i];
		return 1;
	}
}

//尝试建立顺序表并使用基本操作
int main()
{
	SeqList L;
	//初始化
	ListInitiate(&L);
	//插入若干元素
	for (int i = 0; i < 10; i++)
	{
		score z=i+1;
		ListInsert(&L, i, z);
	}
	//删除一个元素
	score x;//（接受删除元素）
	ListDelete(&L, 6, &x);
	//求顺序表长度
	int length1 = ListLength1(&L);
	int length2 = ListLength2(L);
	printf("%d,%d\n", length1, length2);
	//获取元素并输出
	for (int i = 0; i < length1; i++)
	{
		score y;
		ListGet(&L, i, &y);
		printf("%d	", y);
	}
	return 0;
}

这段代码的基本情境是用顺序表存储学生成绩score。

2.数据结构——顺序表

#我们先来了解顺序表的基本知识

2.1.顺序表的特点

顾名思义，顺序表的存储结构是有顺序的，每一个元素的存储在逻辑上和物理上都是连续的。它实质上就是一个数组。（“逻辑”是对于代码逻辑而言的；“物理”是对于实际存储的地址而言的）

arr

元素1

元素2

元素3

元素4

……

元素n

……

空（可能）

arr的索引

……

n+m

arr元素的地址

（假设）

0x1000

0x1004

0x1008

0x100c

……

逻辑上：在对任一元素访问和存储时，都能依靠索引来进行。索引从0开始依次增加1，元素也按照次序存放在数组里。

物理上：当我们在VS2022上调试代码时，我们能够发现，数组中存放的每一个元素的地址也是按顺序排列的，随着索引值大小的递增而递增，差值为元素类型的字节数。

这个连续的特点和链表对比就很好理解。链表在逻辑上是连续的，因为每一个元素结点都有指针相连接，形成一个有序的数据结构。但是在物理上不是连续的，因为每个结点的地址是随机创建的的，之间没有关联。（我的主页里有关于链表的博客哦！Elnaij-CSDN博客）

2.2顺序表的分类

#本文中的顺序表默认使用静态分配内存的顺序表，关于动态分配，动态数组的创建，我会在有关串的数据结构文章中讲到！敬请期待~🖖

2.2.1.动态分配内存的顺序表

它的大小长度可以按需要创建。

2.2.2.静态分配内存的顺序表

他的大小长度由一个常量确定。

2.3.定义一个顺序表

#define Maxsize 100
typedef struct 
{
	score list[MaxSize];
	int size;
}SeqList;//顺序表定义（此处为成绩列表）

用结构体来定义，里面包含要存储score成绩数据的list数组，数组大小为宏常量Maxsize（100），还有表示元素个数的size。

#既然顺序表本质上是一个数组，可为什么还要用结构体来定义呢？就为了多存一个size元素个数的信息？有必要吗？（往下看就知道啦！）

3.顺序表的基本操作

我在源代码中使用了

typedef int score;

score是元素的数据名称，这样写目的是为了便于理解数据的实际内容，表示顺序表存储的是学生的成绩score，也就是很多教科书里面写到的DataType，这里把教材的概念具体化了。

3.1初始化顺序表

void ListInitiate(SeqList* L)//传入顺序表地址
{	
	L->size = 0;//初始长度为0，无元素
}//有地址有长度---》》》创建顺序表完成

十分简单的操作。将顺序表里的元素个数size赋值为0即可。

Q：不用将顺序表中可能存在的原有元素初始化吗？

A：初始化一个已有数据的顺序表，不必要对原有元素进行改变。

原因

i.顺序表的内存空间已经创建好，所以不管对里面的元素怎么修改，甚至空置为NULL，都不会影响其内存大小。

ii.size的值可以作为能否进行其他操作的判断标准。当size=0时，就不让删除操作进行。或者让插入操作不可以将新元素插入超过数组索引为size+1的位置。这样即使在插入时有原有元素的存在，原有元素也会被新元素覆盖掉。（不懂的话，让下看删除和插入操作就能有所体会了）

3.2求元素个数


//二、求当前元素个数（将长度返回）
int ListLength1(SeqList* L)//传入地址找size
{
	return L->size;
}
int ListLength2(SeqList L)//传入整个表找size
{
	return L.size;
}

这里有两种求元素个数的操作，实际上是一样的。

传入的是指针就用"->"访问到顺序表的size并返回；

传入的是整个顺序表就用"."访问到顺序表的size并返回。

因为这个操作不会也不需要对顺序表进行修改，所以可以不传入顺序表的指针，而是直接传入整个顺序表。

3.3插入元素*

！！重要！！


//三、插入元素
//#默认pos的合法范围为pos∈[0,size)#
/*接受int返回值1或0，判断插入成败(后面同理)*/
int ListInsert(SeqList* L, int pos, score x)//i为插入位置，x为插入的元素
{
	//1.先判断能否插入：
	if (L->size == MaxSize)
	{
		printf("无法插入，内存不足！");
		return 0;//直接退出（下同）
	}
	//2.再判断传入的i是否合法（即未超出范围）：
	else if (pos < 0 || pos > L->size)
	{
		printf("pos的输入不合法，无法插入！");
		return 0;//直接退出
	}
	//3.开始插入:
	else
	{
		for (int j = L->size; j > pos; j--) L->list[j] = L->list[j - 1];//将插入位置后面的元素整体后移
		L->list[pos] = x;//覆盖i处原元素
		L->size++;//长度加1
		return 1;
	}
}

#先来分析插入元素的思路。

基本步骤与思路

i.传入插入的位置pos和要插入的元素。

ii.判断内存是否足够插入新元素。

iii.判断pos这一插入位置是否合法（有没有超出范围0~size）。

iiii.将在位置pos以及之后的所有元素从最后一个元素开始都依次后移一个位置。

iiiii.将新元素赋值到pos位置

iiiiii.size=size+1

各步骤目的

i步是传参，ii和iii是判断插入是否可行，iiii步是在腾出位置，这时pos位置还有一个原有元素，但是没关系，iiiii步把新元素覆盖pos处原有元素，完成插入。最后让元素个数size+1.

比如说我要在pos为2处插入元素999：

索引	0	1	2	3	4	……	n-1
arr元素	1	2	3	4	5	……	n
			↘	↘	↘	↘	↘
arr插入前	1	2	3	3	4	5	……	n
索引	0	1	2	3	4	5	……	n-1

arr插入后	1	2	999	3	4	5	……	n
索引	0	1	2	3	4	5	……	n-1

size的作用：插入操作这里就能看到size的作用了——size的值可以作为能否进行其他操作的判断标准。ii和iii步可离不开size。

3.4删除元素*

！！重要！！

//四、删除元素
int ListDelete(SeqList* L, int i, score* x)//i为删除元素的位置，x保存删除的元素等待另外处置
{
	//先判断i是否合法（同上）
	if (i < 0 || i > L->size)
	{
		printf("i的输入不合法，无法删除");
		return 0;
	}
	//再判断能否再删
	else if (L->size == 0)
	{
		printf("已无元素可删！");
		return 0;
	}
	//开始删除
	else
	{
		*x = L->list[i];//先保存
		for (int j = i; j < L->size; j++)//再往前覆盖
		{
			L->list[j] = L->list[j+1];
		}
		L->size--;//长度减1
		return 1;
	}
}

基本步骤与思路

i.传入删除的位置pos和一个类型与顺序表中元素相同的变量x。

ii.判断顺序表中是否还有元素可以删除。

iii.判断pos这一删除位置是否合法（有没有超出0~size）。

iiii.用变量x接受删除的元素。

iiiii.将在位置pos之后的所有元素从最前面的元素开始都依次前移一个位置。

iiiiii.size=size-1

各步骤目的

比如我要删除pos为2处的元素，size为n，Maxsize为n+1

							size=n
索引	0	1	2	3	4	……	n-1	n
arr元素	1	2	3	4	5	……	n	NULL
size=n			↓ 存入x	↓ ↙	↓ ↙	↓ ↙	↓ ↙
arr删除后	1	2	4	5	……	n	n	NULL
索引	0	1	2	3	……	n-2	n-1	n
						size=n-1

i~iii步骤同上（插入操作部分）。不同的是，iiii步要将删除的元素另外存起来，存起来的好处是可以后续对其进行进一步处置。最后一步，是要通过覆盖前面元素的值以达到删除的功能。最后让元素个数size -1.

size的作用：删除操作这里也能看到size的作用——size的值可以作为能否进行其他操作的判断标准。

我们可以看到，进行删除操作之后，顺序表里的数组里面最后一个元素和倒数第二个元素是一样的，但是没有关系，因为size已经-1，最后一个元素已经被size限制，保证它下次不会被进行删除操作。索引>=size的位置也只会在之后的插入操作时被覆盖。

3.5获取元素

十分简单！

//五、获取元素
int ListGet(SeqList* L, int i, score* x)//x接受获取到的元素
{
	//判断i输入合法性（下同）
	if (i < 0 || i > L->size)
	{
		printf("i的输入不合法，无法获取！");
		return 0;
	}
	else
	{
		*x = L->list[i];
		return 1;
	}
}

首先判断要获取的元素的位置是否合法，合法就存到score变量x里，完成获取。同求元素个数操作，因为这个操作不会也不需要对顺序表进行修改，所以可以不传入顺序表的指针，而是直接传入整个顺序表。

size在这又对操作合法性进行了限制！

到这里，你应该知道为什么size很重要了吧！