动态顺序表的C语言实现（详细）_c语言动态顺序表插入,删除,查找如何输出

---

前言

包含相关声明的头文件

C语言实现动态顺序表所包含的头文件，宏定义，函数声明，结构定义

将以下代码放到专门的头文件seqList.h中，这样做可以方便管理。
想要使用顺序表，只需要包含该头文件：#include “seqList.h”，再将实现函数的文件seqList.c加入项目。

#include <stdio.h>			// 包含标准输入输出头文件
#include <stdlib.h>			// 包含标准库头文件
#include <assert.h>			// 包含断言头文件
#include <stdbool.h>		// 包含标准布尔类型头文件

// 设定顺序表的元素类型，，类型可以根据需要随时改变，只需要改变这一行代码
typedef int ElemType;		

// 动态顺序表的结构声明
typedef struct {
	ElemType* data;			// 顺序表的基地址
	int length;				// 顺序表的有效数据元素个数
	int capacity;			// 顺序表分配的内存空间容量
}SeqList;					

#define LIST_INIT_SIZE 10   // 设置顺序表初始分配的内存空间
#define EXP_MUL 2			// 设置每次扩容的倍数

// 动态顺序表相关通用操作的函数声明
void InitSeqList(SeqList* L);
bool SeqListIsEmpty(const SeqList* L);
void SeqListCapacityExpansion(SeqList* L);
void SeqListInsertElem(SeqList* L, int pos, ElemType element);
ElemType SeqListDeleteElem(SeqList* L, int pos);
ElemType SeqListGetElem(const SeqList* L, int pos);
void SeqListModifyElem(SeqList* L, int pos, ElemType element);
int SeqListGetLength(const SeqList* L);
void ClearSeqList(SeqList* L);
void DestroySeqList(SeqList* L);

// 不通用操作的函数声明，假定元素类型是整型
void SeqListRemoveElem(SeqList* L, ElemType element);
int SeqListLocateElem(const SeqList* L, ElemType element);
void PrintSeqList(const SeqList* L);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

动态顺序表的定义

ElemType可以是任何类型，根据具体问题可以随时指定类型。
顺序表的内存空间动态分配，当空间不够时，会自动扩容。容量用capacity变量记录。
顺序表本质是数组，但不用定义一个数组变量，只需要定义一个表示基地址的指针。之后用malloc和realloc函数给指针动态分配空间，通过指向基地址的指针随机存取顺序表的每一个元素。

typedef int ElemType;		// 设定顺序表的元素类型
// 动态顺序表的结构声明
typedef struct {
	ElemType* data;			// 顺序表的基地址
	int length;				// 顺序表的有效数据元素个数
	int capacity;			// 顺序表分配的内存空间容量
}SeqList;
1
2
3
4
5
6
7

---

动态顺序表相关基本通用操作

包括以下基本通用操作：
1.初始化顺序表。
2.判断顺序表是否为空。
3.顺序表扩容。
4.顺序表插入元素。
5.顺序表删除元素。
6.查找顺序表指定位置的元素。
7.修改顺序表指定位置的元素。
8.得到顺序表的长度。
9.将顺序表重置为空表。
10.摧毁顺序表。
C语言实现顺序表，有2个基本操作不能满足所有类型的顺序表。
1.删除顺序表内和指定值相同的第一个元素
也就是:

void SeqListRemoveElem(SeqList* L, ElemType element);
1

2.查找顺序表内和指定值相同的第一个元素的位置
也就是：

int SeqListLocateElem(SeqList* L, ElemType element);
1

这是由于C语言的==运算符不够强大，部分数据类型的顺序表很难通过等于运算符直接比较。
比如，假设顺序表的数据类型是结构体。对于结构体变量，无法通过等号运算符判断2个结构体变量的值完全相同。


以下是所有基本操作的C语言代码实现，每个实现前都有相关注意事项的文字描述。

1.初始化顺序表

先为顺序表分配一个初始空间，空间长度为LIST_INIT_SIZE的值，之后不够再扩容。
此时顺序表没有任何元素，所有length为0。

// 构造一个空的顺序表，并分配一个初始内存空间
void InitSeqList(SeqList* L)
{
	// 给顺序表分配初始的内存空间
	L->data = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	// 如果分配空间失败，直接终止程序,并调用abort函数，显示相关提示信息
	assert(L->data != NULL);	
	L->length = 0;						// 初始化顺序表元素个数为0
	L->capacity = LIST_INIT_SIZE;		// 记录初始分配的内存空间的容量
}
1
2
3
4
5
6
7
8
9
10

2.判断顺序表是否为空

如果顺序表为空就返回true，否则返回false。

// 判断顺序表是否为空表
bool SeqListIsEmpty(const SeqList* L)
{
	return (L->length == 0) ? true : false;
}
1
2
3
4
5

3.顺序表的扩容

将顺序表的容量扩充为指定的倍数
动态顺序表相比静态顺序表的优点就是根据需要扩容。
只要一直添加顺序表的元素，顺序表的空间就可能存满。
可以利用realloc函数，扩充顺序表的容量为指定倍数。
但是realloc函数并不是简单的在已分配空间的后面增加可用内存空间。
还有可能将整个顺序表复制一份，存到全新的内存空间，这个开销是非常大的，这也是动态顺序表不可避免的缺点。

// 当顺序表容量满了之后，将容量扩充为指定倍数
void SeqListCapacityExpansion(SeqList* L)
{
	// 用一个变量表示扩充后的新容量大小，EXP_MUL常量为扩容的倍数
	int newCapacity = EXP_MUL * L->capacity;
	ElemType* newAddress;				// 用一个指针暂时存储扩容后新空间的地址
	// 用realloc函数给顺序表扩容
	newAddress = (ElemType*)realloc(L->data,  newCapacity * sizeof(ElemType));
	// 如果realloc函数分配空间失败，打印提示信息，并终止程序
	if (newAddress == NULL)
	{
		puts("Capacity expansion failed!");
		exit(EXIT_FAILURE);
	}
	L->data = newAddress;				// 把新分配空间的地址给data变量
	L->capacity = newCapacity;			// 让capacity的值为新容量大小
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.在指定位置插入元素

检测插入位置是否超出顺序表的范围，有效范围是[1,length+1]，指定pos为length+1就是所谓的尾插法插入。
如果插入前顺序表容量已满，则先调用动态顺序表的扩容操作SeqListCapacityExpansion。
顺序表的插入复杂度比链表高很多，因为顺序表逻辑顺序相邻的元素，在内存空间的物理位置也相邻。
所以，插入前需要将之后的元素从后往前依次移位，才能给插入元素留出空位。
这个操作最坏时间复杂度为O(n)。

// 在顺序表的指定位置上插入一个元素
void SeqListInsertElem(SeqList* L, int pos, ElemType element)
{
	// 如果指定的插入位置超出范围，就打印提示信息，并终止程序
	if (pos <= 0 || pos > L->length + 1)
	{
		puts("The inserted position is out of range");
		exit(EXIT_FAILURE);
	}
	// 如果顺序表的容量已满，就扩容
	if (L->length >= L->capacity)
		SeqListCapacityExpansion(L);
	// 从后往前依次移动顺序表的元素，留出插入的空位
	for (int i = L->length; i >= pos; i--)
		L->data[i] = L->data[i - 1];
	L->data[pos - 1] = element;					// 将元素插入到指定位置
	L->length++;								// 让顺序表的数据长度加1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.删除顺序表指定位置上的元素

删除前要检查2个异常情况：
1.顺序表为空表。
2.指定删除的位置超出范围。
空表检测要在超出范围之前，否则会给错提示信息。
顺序表的删除操作和插入操作类似，也是要依次移动顺序表的元素，才能去除空缺位置。
删除操作会导致被删除元素的值丢失，有的应用场景可能会需要被删除的元素。
所以，函数将被删除的元素作为返回值返回。

// 删除顺序表指定位置上的元素，并返回该元素
ElemType SeqListDeleteElem(SeqList* L, int pos)
{
	// 如果要删除元素的顺序表为空表，就打印提示信息，并终止程序
	if (SeqListIsEmpty(L) == true)
	{
		puts("The sequence list is empty!");
		exit(EXIT_FAILURE);
	}
	// 如果指定删除的位置超出范围，就打印提示信息，并终止程序
	if (pos <= 0 || pos > L->length)
	{
		puts("The position of deleted element is out of range!");
		exit(EXIT_FAILURE);
	}
	// 先保存将要删除的元素
	ElemType deleteElement = L->data[pos - 1];	
	// 从指定位置处，从前往后依次将下一个元素前移，从而去掉被删除的空缺位置
	for (int i = pos; i < L->length; i++)
		L->data[i - 1] = L->data[i];
	L->length--;							// 将有效元素个数减一
	return deleteElement;					// 返回被删除的元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

6.查找顺序表指定位置上的元素

查找前要检查2个异常情况：
1.顺序表为空表。
2.查找的位置超出范围。
空表检测要在超出范围之前，否则会给错提示信息。
如果一切正常，返回指定位置的元素。由于数组下标从0开始，所以返回元素的下标为index - 1

// 得到顺序表指定位置上的元素
ElemType SeqListGetElem(const SeqList* L, int pos)
{
	// 如果要查找的顺序表为空表，就打印提示信息，并终止程序
	if (SeqListIsEmpty(L) == true)
	{
		puts("The sequence list is empty!");
		exit(EXIT_FAILURE);
	}
	// 如果指定的位置越界，打印出提示信息，并终止程序
	if (pos <= 0 || pos > L->length)
	{
		puts("The designated position is out of range!");
		exit(EXIT_FAILURE);
	}
	//返回指定位置上的元素，由于数组下标从0开始，所以返回元素的下标为index-1
	return L->data[pos - 1];			
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7.修改顺序表指定位置上的元素

修改前要检查2个异常情况：
1.顺序表为空表。
2.指定修改的位置超出范围。
空表检测要在超出范围之前，否则会给错提示信息。

// 修改顺序表指定位置上的元素
void SeqListModifyElem(SeqList* L, int pos, ElemType element)
{
	// 如果指定修改的位置越界，打印出提示信息，并终止程序
	// 如果要修改元素的顺序表为空表，就打印提示信息，并终止程序
	if (SeqListIsEmpty(L) == true)
	{
		puts("The sequence list is empty!");
		exit(EXIT_FAILURE);
	}
	if (pos <= 0 || pos > L->length)
	{
		puts("The position of the modified element is out of range!");
		exit(EXIT_FAILURE);
	}
	L->data[pos - 1] = element;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8.得到顺序表的长度

length变量就代表顺序表的有效数据个数，返回length的值即可

// 返回顺序表的有效数据元素个数
int SeqListGetLength(const SeqList* L)
{
	return L->length;					//返回length变量的值
}
1
2
3
4
5

9.清空顺序表

清空顺序表是清空顺序表存储的有效数据。
而有效数据的个数是用length变量表示，只要length为0，就相当于清空了顺序表。

// 把线性表的数据清零
void ClearSeqList(SeqList* L)
{
	L->length = 0;						// 重置线性表的元素个数为0
}
1
2
3
4
5

10.摧毁顺序表

用free函数释放掉所有空间。
再让L->data指向NULL，防止野指针非法访问未分配的内存空间。
再重置length和capacity变量为0

// 摧毁整个顺序表，释放所有被分配的空间
void DestroySeqList(SeqList* L)
{
	free(L->data);						// 释放顺序表已分配的所有空间
	L->data = NULL;						// 将指向顺序表基地址的指针设为NULL
	L->length = 0;						// 设置顺序表数据个数为0
	L->capacity = 0;					// 设置顺序表容量为0
}
1
2
3
4
5
6
7
8

---

非通用操作(只适用于整型顺序表)

1.删除顺序表和指定值相同的第一个元素

先保证顺序表非空。
遍历整个顺序表，寻找和指定值相同的元素。
如果遍历结束也没找到，就打印:要找的值不存在的提示信息。
如果找到了，就挪动顺序表，去掉删除后的空隙，并让顺序表数据长度减一。

/*
 * 删除顺序表内和指定值相同的第一个元素
 * 如果没找到和指定值相同的元素，则打印提示信息，并终止程序
 */
void SeqListRemoveElem(SeqList* L, ElemType element)
{
	// 如果要删除的顺序表为空表，就打印提示信息，并终止程序
	if (SeqListIsEmpty(L) == true)
	{
		puts("The sequence list is empty!");
		exit(EXIT_FAILURE);
	}
	int index;
	// 遍历整个顺序表，如果找到和指定值相同的元素，就跳出循环
	for (index = 0; index < L->length; index++)
		if (L->data[index] == element)
			break;
	// 如果没有找到和指定值相同的元素，就打印提示信息，并终止程序
	if (index == L->length)
	{
		puts("The value is not in the sequence list!");
		exit(EXIT_FAILURE);
	}
	// 从前往后依次前移每个元素，填补掉被删除的空缺
	for (int i = index + 1; i < L->length; i++)
	{
		L->data[i - 1] = L->data[i];
	}
	L->length--;			// 让顺序表的数据长度减一
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.查找顺序表内和指定值相同的第一个元素位置

先保证顺序表非空。
遍历整个顺序表，如果没找到指定值，就返回0，如果找到了和指定值相同的第一个元素，就返回该元素的位置（注意是位置，是下标+1）。

// 返回顺序表内和指定值相同的第一个元素的位置，如果没有找到就返回0
int SeqListLocateElem(const SeqList* L, ElemType element)
{
	// 如果要查询的顺序表为空表，就打印提示信息，并终止程序
	if (SeqListIsEmpty(L) == true)
	{
		puts("The sequence list is empty!");
		exit(EXIT_FAILURE);
	}
	int index;
	// 遍历整个顺序表，如果某个元素的值和指定值相同，就跳出循环
	for (index = 0; index < L->length; index++)
		if (element == L->data[index])
			break;
	// 如果顺序表内找不到指定值，就设置index为-1
	if (index == L->length)
		index = -1;
	return index + 1;		// 返回找到的位置，位置为下标+1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.依次打印整型顺序表所有元素

先保证顺序表非空。
依次打印每个元素，输出10个整数就换行。
等所有元素的值都输出后，最后再换行一次。

// 依次打印顺序表的元素
void PrintSeqList(const SeqList* L)
{
	// 如果要打印的顺序表为空表，就打印提示信息，并终止程序
	if (SeqListIsEmpty(L) == true)
	{
		puts("The sequence list is empty!");
		exit(EXIT_FAILURE);
	}
	// 依次打印顺序表中的元素，每输出10个整数就换行
	int index;
	for (index = 0; index < L->length; index++)
	{
		printf("%4d ", L->data[index]);
		// 如果输入了10个数字，就换行
		if (index % 10 == 9)
			putchar('\n');
	}
	// 如果最后一行没满，就在最后再换行（为了和最后一行满了的情况统一）
	if (index % 10 != 0)
		putchar('\n');
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22