代码已经放在Gitee上，需要可以小伙伴可以去看看
线性表和顺序表
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列，这是我们广泛使用的数据结构。
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
常见的线性表：顺序表、链表、栈、队列、字符串…
顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
一般可以分为：
- 静态顺序表：使用定长数组来存储元素
- 动态顺序表：使用动态开辟的数组来储存元素
静态顺序表
|
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
|
//定义静态数组的大小，方便后续修改#define MAX_SIZE 50//重命名数组的数据类型，方便后续修改typedef int SLDataType;//定义结构体//成员变量为数组和记录当前数据个数的变量//重命名结构体数据类型，方便书写typedef struct SeqList { SLDataType arr[MAX_SIZE]; int size;}SL;//-----------------------------------------------------------------------------//以下是一些常见的接口的声明//顺序表初始化//利用结构体类型创建一个静态顺序表变量后，可以对其进行初始化void SLInit(SL* psl);//打印顺序表//把顺序表的值按照先后顺序打印出来void SLPrint(SL* psl);//检查顺序表是否已满//每次进行加入数据的操作的时候需要先检查是否已经满了，如果满了就不能够插入了void SLCheck(SL* psl);//顺序表的尾插//在顺序表的尾部在插入一个元素//由于是数组加入数据很方便，直接使用数组下标就可以访问到void SLPushBack(SL* psl, SLDataType data);//顺序表的尾删//删除顺序表尾部的数据void SLPopBack(SL* psl);//顺序表的头插//在顺序表的开头加入一个数据void SLPushFront(SL* psl, SLDataType data);//顺序表的头删//把顺序表第一位数据删除void SLPopFront(SL* psl);//顺序表查找某个数据//查找顺序表中是否存在某个数据，如果有就返回对应的下标//如果找不到就返回-1int SLFind(SL* psl, SLDataType x);//顺序表在pos位置插入x//在指定下标位置插入数据x，原来x位置的数据以及后面的数据往后移动void SLInsert(SL* psl, size_t pos, SLDataType x);//顺序表删除在pos位置的数据void SLErase(SL* psl, size_t pos);//顺序表某一位置数据的修改void SLModify(SL* psl, size_t pos, SLDataType x); |
以下是这些接口的具体实现
|
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
165
166
|
//顺序表初始化void SLInit(SL* psl) { psl->arr[0] = 0;//此处只能初始化一个元素 psl->size = 0;}//打印顺序表void SLPrint(SL* psl) { int i = 0; if (psl->size) { for (i = 0; i < psl->size; i++) { //输出格式，记得根据SLDataTyped的类型来修改 printf("%d ", psl->arr[i]); } printf("\n"); } else { printf("Null\n"); }}/*//检查顺序表是否已满void SLCheck(SL* psl) { if (psl->size == MAX_SIZE) { printf("顺序表已满，无法进行后续操作"); }}*///顺序表的尾插void SLPushBack(SL* psl, SLDataType data) { //插入数据要先检查空间是否已满 //实现方法一不够好 /* if (psl->size == MAX_SIZE) { printf("空间已满\n"); return; } else { psl->arr[psl->size] = data; psl->size++; }*/ //实现方法二，简单明了 assert(psl->size != MAX_SIZE); psl->arr[psl->size] = data; psl->size++;}//顺序表的尾删void SLPopBack(SL* psl) { //判断是否还有元素可以删除 assert(psl->size); psl->size--;}//顺序表的头插void SLPushFront(SL* psl, SLDataType data) { assert(psl->size != MAX_SIZE); //src用来后移数据 int src = psl->size; while (src >= 1) { psl->arr[src] = psl->arr[src - 1]; src--; } psl->arr[src] = data; psl->size++;}//顺序表的头删void SLPopFront(SL* psl) { //判断是否还有数据可以删除 assert(psl->size); int src = 0; while (src < psl->size - 1) { psl->arr[src] = psl->arr[src + 1]; src++; } psl->size--;}//顺序表查找某个数据int SLFind(SL* psl, SLDataType x) { int i = 0; for (i = 0; i < psl->size; i++) { if (psl->arr[i] == x) { //找到了就返回该数据在顺序表中的位置 return i; } } //找不到就返回-1 return -1;}//顺序表在pos位置插入xvoid SLInsert(SL* psl, size_t pos, SLDataType x) { assert(psl->size < MAX_SIZE); assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的时候，相当于头插，尾插 int end = psl->size; while (end > pos) { psl->arr[end] = psl->arr[end - 1]; end--; } psl->arr[pos] = x; psl->size++;}//顺序表删除在pos位置的数据void SLErase(SL* psl, size_t pos) { assert(psl->size); assert(pos >= 0 && pos < psl->size); int start = pos + 1; while (start < psl->size) { psl->arr[start - 1] = psl->arr[start]; start++; } psl->size--;}//顺序表某一位置数据的修改void SLModify(SL* psl, size_t pos, SLDataType x) { assert(psl->size); assert(pos >= 0 && pos < psl->size); psl->arr[pos] = x;} |
上面代码的测试，我放在了Gitee上，需要的小伙伴可以参考一下
动态顺序表
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
|
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
|
//重命名SL的数据类型，方便后续修改typedef int SLDataType;//定义结构体//成员变量为指向动态顺序表的指针，数据的个数，顺序表的容量//capacity用来管理数组的总大小，如果size与capacity相等了，就表示数组已经满了需要扩容//重定义结构体类型名称，方便操作typedef struct SeqList { SLDataType* p; int size; int capacity;}SL;//----------------------------------------------------------------------//一下是一些常用的接口，与静态顺序表差不多//SL初始化void SLInit(SL* ps);//SL空间检查//如若size与capacity相等表示数组已经满了，需要扩容void SLCheckCapacity(SL* ps);//SL打印void SLPrint(SL* ps);//SL销毁//因为数组是动态开辟的，所以在最后不使用的数组的时候要释放空间void SLDestory(SL* ps);//SL尾插void SLPushBack(SL* ps,SLDataType x);//SL尾删void SLPopBack(SL* ps);//SL头插void SLPushFront(SL* ps, SLDataType x);//SL头删void SLPopFront(SL* ps);//SL查找某个数据//如果能找到，返回该数据在顺序表中下标int SLFind(SL* ps, SLDataType x);//SL在pos位置插入xvoid SLInsert(SL* ps, size_t pos, SLDataType x);//SL删除pos位置的值void SLErase(SL* ps, size_t pos);//SL修改某一位置的数据void SLModity(SL* ps, size_t pos, SLDataType x); |
以下是具体的实现
|
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
//动态顺序表的实现#include"DynamicSeqList.h"//SL初始化void SLInit(SL* ps) { ps->p = NULL; ps->capacity = 0; ps->size = 0;}//SL空间检查void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity; SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->p = tmp; }}//SL打印void SLPrint(SL* ps) { if (ps->size == 0) { printf("顺序表为空\n"); } else { int i = 0; for (i = 0; i < ps->size; i++) { //打印格式记得根据SLDataType的类型来修改 printf("%d ", ps->p[i]); } printf("\n"); }}//SL销毁//这里并没有完全销毁结构体s，只是把成员变量都赋值为0void SLDestory(SL* ps) { free(ps->p); ps->p = NULL; ps->size = ps->capacity = 0;}//SL尾插void SLPushBack(SL* ps, SLDataType x) { SLCheckCapacity(ps); ps->p[ps->size] = x; ps->size++;}//SL尾删void SLPopBack(SL* ps) { //删除数据需要判断一下顺序表是否为空 assert(ps->size > 0); ps->size--;}//SL头插void SLPushFront(SL* ps, SLDataType x) { SLCheckCapacity(ps); int end = ps->size; while (end > 0) { ps->p[end] = ps->p[end - 1]; end--; } ps->p[end] = x; ps->size++;}//SL头删void SLPopFront(SL* ps) { //删除数据需要判断一下顺序表是否为空 assert(ps->size > 0); int start = 0; while (start < ps->size - 1) { ps->p[start] = ps->p[start + 1]; start++; } ps->size--;}//SL查找某个数据int SLFind(SL* ps, SLDataType x) { //需要判断顺序表是否为空，可以用assert，也可以用if判断 assert(ps->size); int i = 0; for (i = 0; i < ps->size; i++) { if (x == ps->p[i]) { return i; } } return -1;}//SL在pos位置插入x//当pos为0或者pos为size时，相当于头插、尾插void SLInsert(SL* ps, size_t pos, SLDataType x) { SLCheckCapacity(ps); assert(pos >= 0 && pos <= ps->size); int end = ps->size; while (end > pos) { ps->p[end] = ps->p[end - 1]; end--; } ps->p[end] = x; ps->size++;}//SL删除pos位置的值void SLErase(SL* ps, size_t pos) { //判断要删除的位置是否在size之内 assert(pos >= 0 && pos < ps->size); int start = pos + 1; while (start < ps->size) { ps->p[start - 1] = ps->p[start]; start++; } ps->size--;}//SL修改某一位置的数据void SLModity(SL* ps, size_t pos, SLDataType x) { //判断要修改的位置是否在size之内 assert(pos >= 0 && pos < ps->size); ps->p[pos] = x;} |
同样的，我自己写的一些小测试也在Gitee上，需要的小伙伴可以去看看
到此这篇关于C语言 数据结构之数组模拟实现顺序表流程详解的文章就介绍到这了,更多相关数组模拟实现顺序表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/weixin_61021362/article/details/121411921
