【数据结构】线性表之《顺序表》超详细实现

前言：相信大家在学完C语言后，对于指针，结构体以及动态内存管理有了一定的见解，那么数据结构像是检验真理的唯一标椎，它考察了你掌握这三种语法的程度，如果掌握的不是很理想的友友们，建议看看鄙人主页总结的文章，好啦，数据结构之旅就正式开始啦。

一.数据结构

数据结构：计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

1.逻辑结构

逻辑结构：数据对象中数据元素之间的相互关系。
逻辑结构分为：集合结构，线性结构，树形结构和图形结构。

2.物理结构

物理结构：数据的逻辑结构在计算机中的存储形式。
物理结构分为：顺序存储结构和链式存储结构。

二.顺序表的分类

顺序表实际属于线性表这个大家族，那么什么是线性表呢？

1. 线性表：是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
2. 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
3. 线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.静态顺序表

#define MAXSIZE 100     //静态顺序表的容量
typedef int SLDataType; //增强程序的可维护性

typedef struct SeqList
{
	SLDataType arr[MAXSIZE];//定长数组
	int size;               //有效的数据个数
}SeqList;
1
2
3
4
5
6
7
8

也许有人会问：这个静态顺序表说的这么神秘，本质上不就是一个数组吗？

答：没错，顺序表的低层就是数组，逻辑结构与物理结构都是连续的。不过顺序表对数组进行了封装，提供了大量常用的接口（所谓接口就是调用函数），方便完成数据进行增，删，查，改等一系列的操作。

静态顺序表的缺点：程序一但运行，数组的大小就确定了，不能被修改。数组大小给小了，空间就不够用；数组大小给大了，空间就白白的浪费掉了；

为了方便对静态顺序表进行扩容，于是，动态顺序表便应运而生。

2.动态顺序表

typedef int SLDataType;//增强程序的可维护性

typedef struct SeqList
{
	SLDataType* arr; //动态的，可以扩容
	int size;        //有效的数据个数
	int capacity;    //容量
}SL;
1
2
3
4
5
6
7
8

动态顺序表：通过堆区的动态内存管理控制顺序表空间的大小，即容量。

以下介绍的是基于动态顺序表的实现。

三.顺序表的实现

1.创建顺序表

创建一个顺序表结构，包含指向这块空间的起始地址，顺序表中存储数据的个数以及顺序表的最大容量。

typedef int SLDataType;//增强程序的可维护性，改变数据类型，只需改变int即可

typedef struct SeqList
{
	SLDataType* arr; //指向顺序表的起始位置，方便扩容
	int size;        //顺序表的有效的数据个数
	int capacity;    //顺序表的容量大小
}SL;//类型的重命名
//等价于typedef struct SeqList SL;

SL sl;//sl就代表顺序表
1
2
3
4
5
6
7
8
9
10
11

2.初始化顺序表

一般初始化我们都习惯赋值为0，指针赋值为NULL。

void SeqListInit(SL* ps)
{
	assert(ps);//断言操作，等价于assert(ps != NULL);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7

3.判断是否扩容

当我们想要增加数据的时候，会遇到容量不够用的问题。所以在此之前，应该检查容量与有效数据之间的关系，判断是否要扩容，接着插入数据。

void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)//顺序表已满，进行扩容操作
	{
		//判断顺序表容量是否为0，若为0，开辟储存4个数据大小的空间，若不为0，则容量翻倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//开辟空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)//开辟失败
		{
			perror("realloc fail!");
			exit(1);//强行退出程序（表示遇到异常情况）
		}
		ps->arr = tmp;//开辟成功，修改指针
		ps->capacity = newcapacity;//修改容量
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：若传入realloc的指针为空指针(NULL)，则realloc函数等价于malloc函数。

4.打印顺序表

循环遍历顺序表数据即可。

void SeqListPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

5.插入操作

1.头插

头插的思想：将数据整体向后挪动一位。注意：为了防止覆盖原先的数据，采用从后向前挪动。再进行头部插入，最后有效数据个数+1。

void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//检查容量

	int end = ps->size;
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end - 1];//将数据整体向后挪动一位。
		end--;
	}
	ps->arr[0] = x;//头插
	ps->size++;//有效数据个数+1

	//等价于在下标为0处插入：SeqListInsert(ps, 0, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.尾插

尾插的思想：直接在尾部插入，有效数据个数+1即可。

void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);//检查容量

	ps->arr[ps->size++] = x;//尾插：采用后置++

	//等价于在下标为ps->size处插入：SeqListInsert(ps, ps->size, x);
}
1
2
3
4
5
6
7
8
9

3.按照下标插入

按照下标插入的思想：与头插的思想相同，只不过是要挪动数据的起始位置不同而已。

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//判断下标的合法性
	SeqListCheckCapacity(ps);

	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6.删除操作

1.头删

头删的思想：不是真正意义上的删除数据，而是将头部之后的数据整体向前挪动一位，覆盖头部数据，达到与头删相同的效果，最后有效数据个数-1。注意：为了防止覆盖原先的数据，采用从前向后挪动，这里与头插不同。

void SeqListPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//前提：顺序表存在数据

	int start = 0;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;//有效数据个数-1

	//等价于在下标为0处删除：SeqListErase(ps, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.尾删

尾删的思想：有效数据个数-1即可。

void SeqListPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//前提：顺序表存在数据

	ps->size--;//有效数据个数-1

	//等价于在下标为ps->size - 1处删除：SeqListErase(ps, ps->size - 1);
}
1
2
3
4
5
6
7
8
9

3.按照下标删除

按照下标删除的思想：与头删的思想相同，只不过是要挪动数据的起始位置不同而已。

void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);//前提：顺序表存在数据
	assert(pos >= 0 && pos < ps->size);//判断下标的合法性

	int start = pos;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.查找数据

查找的思想：遍历数据，找到了返回下标，未找到返回-1即可。

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到该数据，返回下标
		}
	}
	return -1;//未找到，返回-1
}
1
2
3
4
5
6
7
8
9
10
11
12
13

8.修改数据

修改的思想：利用下标确定位置，直接修改就行。较为简单。

void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->arr[pos] = x;
}
1
2
3
4
5
6
7

9.清空顺序表

清空的思想：将有效数据个数与容量赋值为0。

void SeqListClear(SL* ps)
{
	assert(ps);

	ps->size = 0;
	ps->capacity = 0;
}

1
2
3
4
5
6
7
8

10.销毁顺序表

销毁的思想：由于空间是利用动态内存函数 realloc 在堆区开辟的，所以要及时释放，避免内存泄漏。

void SeqListDestory(SL* ps)
{
	assert(ps);

	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;//置为NULL，防止野指针
	SeqListClear(ps);//清空顺序表
}
1
2
3
4
5
6
7
8
9
10
11

四.模块化源代码

1.SeqList.h

//#pragma once：防止头文件被重复包含
#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int SLDataType;//增强程序的可维护性

typedef struct SeqList
{
	SLDataType* arr; //动态的，可以扩容
	int size;        //有效的数据个数
	int capacity;    //容量
}SL;

void SeqListInit(SL* ps);//顺序表初始化

void SeqListCheckCapacity(SL* ps);//检查顺序表的容量

void SeqListPrint(SL* ps);//打印顺序表

void SeqListPushBack(SL* ps, SLDataType x);//顺序表尾部插入

void SeqListPushFront(SL* ps, SLDataType x);//顺序表头部插入

void SeqListPopBack(SL* ps);//顺序表尾部删除

void SeqListPopFront(SL* ps);//顺序表头部删除

void SeqListInsert(SL* ps, int pos, SLDataType x);//顺序表按照位置（下标）插入

void SeqListErase(SL* ps, int pos);//顺序表按照位置（下标）删除

int SeqListFind(SL* ps, SLDataType x);//顺序表查找元素值，返回下标

void SeqListModify(SL* ps, int pos, SLDataType x);//顺序表按位置（下标）修改

void SeqListClear(SL* ps);//清空顺序表

void SeqListDestory(SL* ps);//销毁顺序表

#endif
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
35
36
37
38
39
40
41
42
43
44
45

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void SeqListInit(SL* ps)
{
	assert(ps);//等价于assert(ps != NULL);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//扩容
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//强行退出程序（表示遇到异常情况）
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

void SeqListPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);

	ps->arr[ps->size++] = x;

	//SeqListInsert(ps, ps->size, x);
}

void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);

	int end = ps->size;
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;

	//SeqListInsert(ps, 0, x);
}

void SeqListPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	ps->size--;

	//SeqListErase(ps, ps->size - 1);
}

void SeqListPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	int start = 0;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;

	//SeqListErase(ps, 0);
}

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SeqListCheckCapacity(ps);

	int end = ps->size;
	while (end > pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	assert(pos >= 0 && pos < ps->size);

	int start = pos;
	while (start < ps->size - 1)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;
}

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->arr[pos] = x;
}

void SeqListClear(SL* ps)
{
	assert(ps);

	ps->size = 0;
	ps->capacity = 0;
}

void SeqListDestory(SL* ps)
{
	assert(ps);

	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	SeqListClear(ps);
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

enum//匿名枚举
{
	EXIT,
	PUSHBACK,
	PUSHFRONT,
	POPBACK,
	POPFRONT,
	INSERT,
	ERASE,
	FIND,
	MODIFY,
	PRINT,
	CLEAR
};

void Menu()
{
	printf("*************顺序表************\n");
	printf("****1.尾插           2.头插****\n");
	printf("****3.尾删           4.头删****\n");
	printf("****5.插入           6.删除****\n");
	printf("****7.查找           8.修改****\n");
	printf("****9.打印          10.清空****\n");
	printf("****0.退出               ******\n");
	printf("*******************************\n");
}

int main()
{
	SL sl;
	SeqListInit(&sl);
	int select = 0;   //菜单选项
	SLDataType value; //插入的值
	int pos = 0;      //插入或删除的下标
	do
	{
		Menu();
		printf("请选择您的操作：");
		scanf("%d", &select);
		switch (select)
		{
		case EXIT:
			printf("退出顺序表!");
			break;
		case PUSHBACK:
			printf("请输入您要尾插的值(输入-1代表结束)：");
			while ((scanf("%d", &value), value != -1)) //逗号表达式
			{
				SeqListPushBack(&sl, value);
			}
			break;
		case PUSHFRONT:
			printf("请输入您要头插的值(输入-1代表结束)：");
			do
			{
				scanf("%d", &value);
				if (value != -1)
				{
					SeqListPushFront(&sl, value);
				}
			} while (value != -1);
			break;
		case POPBACK:
			SeqListPopBack(&sl);
			break;
		case POPFRONT:
			SeqListPopFront(&sl);
			break;
		case INSERT:
			printf("请输入要插入的《下标》与《值》：");
			scanf("%d %d", &pos, &value);
			SeqListInsert(&sl, pos, value);
			break;
		case ERASE:
			printf("请输入要删除的《下标》：");
			scanf("%d", &pos);
			SeqListErase(&sl, pos);
			break;
		case FIND:
			printf("请输入要查找的《值》：");
			scanf("%d", &value);
			int ret = SeqListFind(&sl, value);
			if (ret != -1)
			{
				printf("找到了下标为：%d\n", ret);
			}
			else
			{
				printf("找不到!");
			}
			break;
		case MODIFY:
			printf("请输入要修改的《下标》以及修改后的《值》:");
			scanf("%d %d", &pos, &value);
			SeqListModify(&sl, pos, value);
			break;
		case PRINT:
			SeqListPrint(&sl);
			break;
		case CLEAR:
			SeqListClear(&sl);
			break;
		default:
			printf("您输入的值错误，请重新选择!\n");
			break;
		}
	} while (select);
	SeqListDestory(&sl);
	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

五.顺序表必做OJ题

1. 原地移除元素
2. 合并两个有序数组

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！