动态顺序表

发表于

标题：动态顺序表的功能实现

顺序表实现下面功能

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
//初始化 
void InitSeqList(PSeqList pSeq); 
//尾部插入 
void PushBack(PSeqList pSeq, DataType data); 
//尾部删除 
void PopBack(PSeqList pSeq); 
//头部插入 
void PushFront(PSeqList pSeq, DataType data); 
//头部删除 
void PopFront(PSeqList pSeq); 
//查找指定元素 
int Find(PSeqList pSeq, DataType data); 
//指定位置插入 
void Insert(PSeqList pSeq, int pos, DataType data); 
//删除指定位置元素 
void Erase(PSeqList pSeq, int pos); 
//删除指定元素 
void Remove(PSeqList pSeq, DataType data); 
//删除所有的指定元素 
void RemoveAll(PSeqList pSeq, DataType data); 
//返回顺序表的大小 
int Size(PSeqList pSeq); 
//判断顺序表是否为空 
int Empty(PSeqList pSeq); 
//冒泡排序 
void BubbleSort(PSeqList pSeq); 
//选择排序 
void SelectSort(PSeqList pSeq); 
//选择排序的优化 
void SelectSortOP(PSeqList pSeq); 
//二分查找 
int BinarySearch(PSeqList pSeq, DataType data); 
//二分查找递归写法 
int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d); 
//打印 
void PrintSeqList(PSeqList pSeq);

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 #ifndef __SEQLIST_H__
 #define __SEQLIST_H__
 #include <stdio.h>
 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>
 typedef int DataType;//定义元素的类型
 #define DEFAULT_SZ 3
//顺序表的定义
typedef struct{
	DataType *data;  //存放数据
	int sz;          //定义一个变量，用来记录顺序表元素的大小
	int capacity;    //定义一个变量，用来记录顺序表的容量
}SeqList,*PSeqList;
//内存开辟
void DynamicOpening(PSeqList pSeq);
//销毁
void Destory(PSeqList pSeq);
//打印
void PrintSeqList(PSeqList pSeq);
//初始化 
void InitSeqList(PSeqList pSeq); 
//尾部插入 
void PushBack(PSeqList pSeq, DataType data); 
//尾部删除 
void PopBack(PSeqList pSeq); 
//头部插入 
void PushFront(PSeqList pSeq, DataType data); 
//头部删除 
void PopFront(PSeqList pSeq); 
//查找指定元素 
int Find(PSeqList pSeq, DataType data); 
//指定位置插入 
void Insert(PSeqList pSeq, int pos, DataType data); 
//删除指定位置元素 
void Erase(PSeqList pSeq, int pos); 
//删除指定元素 
void Remove(PSeqList pSeq, DataType data); 
//删除所有的指定元素 
void RemoveAll(PSeqList pSeq, DataType data); 
//返回顺序表的大小 
int Size(PSeqList pSeq); 
//判断顺序表是否为空 
int Empty(PSeqList pSeq); 
//冒泡排序 
void BubbleSort(PSeqList pSeq); 
//选择排序 
void SelectSort(PSeqList pSeq); 
//选择排序的优化 
void SelectSortOP(PSeqList pSeq); 
//二分查找 
int BinarySearch(PSeqList pSeq, DataType data); 
//二分查找递归写法 
int BinarySearch_R(PSeqList pSeq, int left, int right, DataType d); 
 #endif //__SEQLIST_H__

SeqList.c 主函数文件

  • 注意：在实现插入操作的时候都必须判断顺序表是否表满，在删除操作的时候必须判断是否表空
  • 在每次在实现函数功能之前使用assert()断言，用于检查“不应该”出现的情况
  • 在开辟空间后, 必须在退出时free, 然后将指针赋NULL, 避免出现野指针的情况
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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
 #define _CRT_SECURE_NO_WARNINGS 1
 #include "SeqList.h"
//内存销毁
void Destory(PSeqList pSeq)
{
	DataType *p = pSeq->data;
	assert(pSeq);
	free(p);
	pSeq->data = NULL;
	pSeq->capacity = 0;
	pSeq->sz = 0;
	printf("内存销毁成功！\n");
}
//内存开辟
void DynamicOpening(PSeqList pSeq)
{
	static int flag = 1;
	//断言
	assert(pSeq);
	if (pSeq->sz == pSeq->capacity)
	{
		//创建临时变量来防止内存开辟失败
		DataType *tmp = (DataType *)realloc(pSeq->data, sizeof(DataType)*(pSeq->capacity+1));
		if (tmp == NULL)
		{
			perror("use realloc");
			exit(EXIT_FAILURE);
		}
		else
		{
			if (flag > 0)
			{
				printf("内存开辟成功！\n");
				flag--;
			}
			pSeq->data = tmp;
		}
		pSeq->capacity += 1;
	}
}
//打印
void PrintSeqList(PSeqList pSeq)
{	
	int i = 0;
	assert(pSeq);
	for(i = 0; i < pSeq->sz; i++)
	{
		printf("%d-->", pSeq->data[i]);
	}
	printf("\n");
	printf("元素个数为：%d",pSeq->sz);
	printf("\n");
}
//初始化 
void InitSeqList(PSeqList pSeq)
{
	assert(pSeq);
	pSeq->data = (DataType *)malloc(sizeof(DataType)*DEFAULT_SZ);
	if (pSeq->data == NULL)
	{
		perror("use malloc");
		exit(EXIT_FAILURE);
	}
	pSeq->sz = 0;
	pSeq->capacity = DEFAULT_SZ;
}
//尾部插入
void PushBack(PSeqList pSeq, DataType data)
{
	assert(pSeq);
	//判断表是否已满
	if (pSeq->sz == pSeq->capacity)
	{
		DynamicOpening(pSeq);
	}
	pSeq->data[pSeq->sz] = data;
	pSeq->sz++;
}
//尾部删除 
void PopBack(PSeqList pSeq)
{
	assert(pSeq);
	if(pSeq->sz == 0)
	{
		printf("表为空，无法删除\n");
	}
	pSeq->sz--;
}
//头部插入 
void PushFront(PSeqList pSeq, DataType data)
{
	int i = 0;
	assert(pSeq);
	if(pSeq->sz == pSeq->capacity)
	{
		DynamicOpening(pSeq);
	}
	for(i = pSeq->sz; i > 0; i--)
	{
		pSeq->data[i] = pSeq->data[i-1];
	}
	pSeq->data[0] = data;
	pSeq->sz++;
}
//头部删除 
void PopFront(PSeqList pSeq)
{
	int i = 0;
	assert(pSeq);
	if(pSeq->sz == 0)
	{
		printf("表空，无法删除\n");
	}
	for(i = 1; i < pSeq->sz; i++)
	{
		pSeq->data[i-1] = pSeq->data[i];
	}
	pSeq->sz--;
}
//查找指定元素 
int Find(PSeqList pSeq, DataType data)
{
	int i = 0;
	assert(pSeq);
	if (pSeq->sz == 0)
	{
		printf("表空，查找失败！\n");
	}
	for(i = 0; i < pSeq->sz; i++)
	{
		if(pSeq->data[i] == data)
		{
			return i;
		}
	}
	return -1;
}
//指定位置插入 
void Insert(PSeqList pSeq, int pos, DataType data)
{
	int i = 0;
	assert(pSeq);
	if(pSeq->sz == pSeq->capacity)
	{
		DynamicOpening(pSeq);
	}
	for(i = pSeq->sz-1; i >= pos-1; i--)
	{
		pSeq->data[i+1] = pSeq->data[i];
	}
	pSeq->data[pos-1] = data;
	pSeq->sz++;
	printf("元素插入成功！\n");
}
//删除指定位置元素 
void Erase(PSeqList pSeq, int pos)
{
	int i = 0;
	assert(pSeq);
	if(pSeq->sz == 0)
	{
		printf("表空，删除失败\n");
	}
	for(i = pos; i <= pSeq->sz; i++)
	{
		if (pSeq->data[i - 1] == pSeq->data[i])
		{
			pSeq->sz--;
			return;
		}
	}
	printf("要删除的位置不存在！\n");
}
//删除指定元素 
void Remove(PSeqList pSeq, DataType data)
{
	int i = 0;
	int ret = 0;
	assert(pSeq);
	ret = Find(pSeq, data);
	if(ret == -1)
	{
		printf("查找到元素不存在\n");
	}
	else
	{
		for(i = ret; i < pSeq->sz; i++)
		{
			pSeq->data[i] = pSeq->data[i+1];
		}
		pSeq->sz--;
	}	
}
//删除所有的指定元素 
void RemoveAll(PSeqList pSeq, DataType data)
{
	int i = 0;
	int j = 0;
	assert(pSeq);
	for(i = 0; i < pSeq->sz; i++)
	{
		if(pSeq->data[i] == data)   
		{
			for(j = i; j < pSeq->sz-1; j++)
			{
				pSeq->data[j] = pSeq->data[j+1];
			}	
			i--;
			pSeq->sz--;
		}
	}
}
//返回顺序表的大小 
int Size(PSeqList pSeq)
{
	assert(pSeq);
	return pSeq->sz;
}
//判断顺序表是否为空 
int Empty(PSeqList pSeq)
{
	assert(pSeq);
	if(pSeq->sz == 0)
	{
		return -1;
	}
	else
	{
		return pSeq->sz;
	}
}
//冒泡排序 
void BubbleSort(PSeqList pSeq)
{
	int i = 0;
	int j = 0;
	int ret = 0;
	DataType cmd = 0;
	assert(pSeq);
	ret = Empty(pSeq);
	if(ret == -1)
	{
		printf("表空，无法排序\n");
	}
	else
	{
		for(i = 0; i < pSeq->sz; i++)
		{
			for(j = 1; j < pSeq->sz-i; j++)
			{
				if(pSeq->data[j-1] > pSeq->data[j])
				{
					cmd = pSeq->data[j-1];
					pSeq->data[j-1] = pSeq->data[j];
					pSeq->data[j] = cmd;
				}
			}
		}
	}	
}
/*
选择排序的基本思想：第1趟，在待排序记录r[1]--r[n]中选出最小的记录，将它与r[1]交换；
第2趟，在待排序记录r[2]--r[n]中选出最小的记录，将它与r[2]交换；以此类推，
第i趟在待排序记录r[i]--r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
时间复杂度O(n) = n;
*/
void SelectSort(PSeqList pSeq)
{
	int min = 0;
	int i = 0;
	int j = 0;
	int count = pSeq->sz;
	DataType cmd = 0;
	int ret = 0;
	assert(pSeq);
	ret = Empty(pSeq);
	if(ret == -1)
	{
		printf("表空，无法选择排序\n");
	}
	for(i = 0; i < count-1; i++)
	{
		min = i;
		for(j = i+1; j < count; j++)
		{
			if(pSeq->data[j] < pSeq->data[min])
			{
				min = j;
			}
		}
			cmd = pSeq->data[i];
			pSeq->data[i] = pSeq->data[min];
			pSeq->data[min] = cmd;
	}
}
//选择排序的优化 
//思想：相当于遍历一遍同时记录最大值和最小值，时间复杂度 O(n) = 2/n;
void SelectSortOP(PSeqList pSeq)
{
	int start = 0;
	int ret = 0;
	int end = pSeq->sz-1;
	//记录最小值的下标
	int min = 0;            
	//记录最大值的下标
	int max = 0;			
	int i = 0,j = 0;
	int rmt = 0;
	assert(pSeq);
	ret = Empty(pSeq);
	if(rmt == -1)
	{
		printf("表空，无法选择排序\n");
	}
	//循环控制条件，每循环次取出一组最大值和最小值
	while(start < end)    
	{
		for(i = start; i < end; i++)
		{
			min = start;
			max = start;
			for(j = start+1; j < end+1; j++)
			{
				if(pSeq->data[j] > pSeq->data[max])
				{
					max = j;
				}
				if(pSeq->data[j] < pSeq->data[min])
				{
					min = j;
				}
			}
			if(min != start)
			{
				ret = pSeq->data[min];
				pSeq->data[min] = pSeq->data[start];
				pSeq->data[start] = ret;
			}
			//如果最大值下标就等于start，当最小值交换之后，start被改变，则必须更新max，否则max会被min覆盖
			if(max == start)   
			{
				max = min;
			}
			if(max != end)
			{
				ret = pSeq->data[max];
				pSeq->data[max] = pSeq->data[end];
				pSeq->data[end] = ret;
			}
		}
		start++;
		end--;
	}
}
//二分查找 
int BinarySearch(PSeqList pSeq, DataType data)
{
	int i = 0;
	int j = 0;
	int left = 0;
	int right = pSeq->sz-1;
	int mid = 0;
	int ret = 0;
	assert(pSeq);
	ret = Empty(pSeq);
	if(ret == -1)
	{
		printf("表空，无法选择排序\n");
	}
	while(left < right)
	{
		mid = (left+(right-left))>>1;
		if(pSeq->data[mid] > data)
		{
			right = mid+1;
		}
		else if(pSeq->data[mid] < data)
		{
			left = mid-1;
		}
		else if(pSeq->data[mid] == data)
		{
			return mid;
		}
		else
		{
			break;
		}
	}
	return -1;
}
//二分查找递归写法 
int BinarySearch_R(PSeqList pSeq, int left, int right, DataType d)
{
	int mid;
	assert(pSeq);
	while(left < right)
	{
		//mid = (left+(right-left))/2;
		mid = (left+(right-left))>>1;
		if(pSeq->data[mid] > d)
		{
			BinarySearch_R(pSeq, left, mid-1, d);
		}
		else if(pSeq->data[mid] < d)
		{
			BinarySearch_R(pSeq, mid+1, right, d);
		}
		else if(pSeq->data[mid] == d)
		{
			return mid;
		}
		else
		{
			break;
		}
	}
	return -1;
}

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
42
43
44
 #define _CRT_SECURE_NO_WARNINGS 1
 #include "SeqList.h"
void test()
{
	SeqList pSeq;
	int left = 0;
	int right = 0;
	int ret = 0;
	InitSeqList(&pSeq);
	PushBack(&pSeq, 1);
	PushBack(&pSeq, 7);
	PushBack(&pSeq, 4);
	PushBack(&pSeq, 3);
	PushBack(&pSeq, 5);
	PushBack(&pSeq, 6);
//	PrintSeqList(&pSeq);
//	PopBack(&pSeq);
//	PrintSeqList(&pSeq);
//	PushFront(&pSeq, 5);
//	PrintSeqList(&pSeq);
//	PopFront(&pSeq);
//	PrintSeqList(&pSeq);
//	Insert(&pSeq, 1, 8);
//	Erase(&pSeq, 4);
//	Remove(&pSeq, 3);
//	RemoveAll(&pSeq, 3);
//	RemoveAll(&pSeq, 2);
//	Size(&pSeq);
//	BubbleSort(&pSeq);
//	SelectSort(&pSeq);
//	SelectSortOP(&pSeq);
//	ret = BinarySearch(&pSeq, 3);
//	right = Size(&pSeq)-1;
//	ret = BinarySearch_R(&pSeq, left, right, 3);
//	PrintSeqList(&pSeq);
//	Destory(&pSeq);
//	printf("%d\n",ret);
}
int main()
{
	test();
	system("pause");
	return 0;
}