C语言实现动态顺序表的实现代码
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
静态实现：结构体内部只需两个成员，其中一个为固定大小(MAX)的数组，用来存放我们的数据。数组大小我们可以通过在头文件中改变MAX的值来改变。
动态实现：在内存中开辟一块空间，可以随我们数据数量的增多来扩容。
来看看动态的顺序表实现：
1.seqlist.h
|
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
|
#define _CRT_SECURE_NO_WARNINGS 1 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef int DataType; #define DEFAULT_SZ 3 #define INC_SZ 2 typedef struct SeqList { DataType *data; int sz; int capacity; }SeqList,*pSeqList; void InitSeqList(pSeqList pList); void PushBack(pSeqList pList,DataType d); void PopBack(pSeqList pList); void PushFront(pSeqList pList, DataType d); void PopFront(pSeqList pList); int Find(pSeqList pList, DataType d); void Remove(pSeqList pList, DataType d); void RemoveAll(pSeqList pList, DataType d); void BubbleSort(pSeqList pList); int BinarySearch(pSeqList pList, DataType d); void PrintfSeqList(pSeqList pList); void Insert(pSeqList pList, int pos, DataType d); void ReverseList(pSeqList pList); void DestroySeqList(pSeqList pList); #endif//__SEQLIST_H__ |
2.seqlist.c
|
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
194
195
196
197
198
199
200
201
|
#define _CRT_SECURE_NO_WARNINGS 1 #include "seqlist.h" void InitSeqList(pSeqList pList) { pList->sz = 0; pList->data = (DataType*)malloc(sizeof(DataType)*DEFAULT_SZ); if (pList->data == NULL) { perror("malloc"); return; } memset(pList->data, 0, sizeof(DataType)*DEFAULT_SZ); } void CheckCapacity(pSeqList pList) { assert(pList); if (pList->sz == pList->capacity) { DataType*ret = (DataType*)realloc(pList->data, sizeof(DataType)*(pList->capacity + INC_SZ)); if (ret == NULL) { perror("realloc"); } pList->data = ret; pList->capacity += INC_SZ; } } void PushBack(pSeqList pList, DataType d) { assert(pList); if (pList->sz == pList->capacity) { CheckCapacity(pList); } pList->data[pList->sz] = d; pList->sz++; } void PopBack(pSeqList pList) { int i = 0; assert(pList); if (pList->sz == 0) { printf("顺序表为空:<"); return; } pList->sz--; } void PushFront(pSeqList pList, DataType d) { int i = 0; assert(pList); if (pList->sz == pList->capacity) { CheckCapacity(pList); } for (i = pList->sz; i >= 1; i--) { pList->data[i] = pList->data[i - 1]; } pList->data[0] = d; pList->sz++; } void PopFront(pSeqList pList) { int i = 0; assert(pList); for (i = 0; i < pList->sz; i++) { pList->data[i] = pList->data[i + 1]; } pList->sz--; } int Find(pSeqList pList, DataType d) { int i = 0; assert(pList); while (i < pList->sz) { if (pList->data[i] == d) { return i; } else { i++; } } return -1; } void Remove(pSeqList pList, DataType d) { int i = 0; int pos = 0; assert(pList); while (pList->data[pos=Find(pList,d)]==d) { for (i = pos; i < pList->sz-1; i++) { pList->data[i] = pList->data[i + 1]; } pList->sz--; } } void RemoveAll(pSeqList pList, DataType d) { int i = 0; int pos = 0; assert(pList); while ((pos = Find(pList, d)) != -1) { for (i = pos; i < pList->sz - 1; i++) { pList->data[i] = pList->data[i + 1]; } pList->sz--; } } void BubbleSort(pSeqList pList) { int i = 0; assert(pList); for (i = 0; i < pList->sz - 1; i++) { int j = 0; for (j = 0; j < pList->sz - i - 1; j++) { if (pList->data[j]>pList->data[j + 1]) { DataType tmp = pList->data[j]; pList->data[j] = pList->data[j + 1]; pList->data[j + 1] = tmp; } } } } int BinarySearch(pSeqList pList, DataType d) { int left = 0; int right = pList->sz - 1; assert(pList); while (left <= right) { int mid = left - ((left - right) >> 1); if (d > pList->data[mid]) { left = mid + 1; } else if (d < pList->data[mid]) { right = mid - 1; } else return mid; } return -1; } void PrintfSeqList(pSeqList pList) { int i = 0; for (i = 0; i < pList->sz; i++) { printf("%d ", pList->data[i]); } } void Insert(pSeqList pList, int pos, DataType d) { int i = 0; if (pList->sz == pList->capacity) { CheckCapacity(pList); } for (i = pList->sz - 1; i >= pos; i--) { pList->data[i + 1] = pList->data[i]; } pList->data[pos] = d; pList->sz++; } void ReverseList(pSeqList pList) { int left = 0; int right = pList->sz - 1; assert(pList); while (left < right) { DataType tmp = pList->data[left]; pList->data[left] = pList->data[right]; pList->data[right] = tmp; left++; right--; } } void DestroySeqList(pSeqList pList) { free(pList->data); pList->data = NULL; } |
3.test.c
|
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
|
#define _CRT_SECURE_NO_WARNINGS 1 #include "seqlist.h" //void Test() //{ // SeqList *List; // InitSeqList(&List); // PushBack(&List, 1); // PushBack(&List, 2); // PushBack(&List, 3); // PushBack(&List, 4); // PushBack(&List, 5); // PopBack(&List); // printf("%d ", Find(&List, 2)); // PrintfSeqList(&List); //} void Test2() { SeqList List; InitSeqList(&List); PushBack(&List, 1); PushBack(&List, 2); PushBack(&List, 3); PushBack(&List, 4); PushBack(&List, 5); PushFront(&List, 5); PushFront(&List, 2); PushFront(&List, 3); //PopFront(&List); RemoveAll(&List, 5); //BubbleSort(&List); //BinarySearch(&List, 3); PrintfSeqList(&List); } int main() { Test2(); system("pause\n"); return 0; } |
静态顺序表的实现：http://www.zzvips.com/article/166551.html
以上就是动态实现顺序表的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/qq_34021920/article/details/76222788
