本文实例讲述了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
|
#ifndef _SEQ_LIST_H
#define _SEQ_LIST_H
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define ElemType float //以float类型测试算法通用性，而不是以惯用的int
#define INIT_SIZE 10 //顺序表默认初始化大小
#define LIST_INCREMENT 5 //顺序表容量增量，容量不够使用malloc申请
#define list_full(list) ((list)->size >= (list)->capacity ? 1 : 0) //顺序表判满
#define list_empty(list) ((list)->size == 0 ? 1 : 0) //判空
typedef ElemType value_type; //元素类型
typedef value_type* value_ptr; //元素指针类型
typedef enum {false, true}bool; //为C语言增加bool量
typedef enum {POSITION, VALUE}DELETE_MODE; //删除元素模式选择，分别为按位置删除和按值删除
typedef struct sequelize_list{
ElemType *base; //顺序表基址
int size; //顺序表元素大小
int capacity; //顺序表容量
} seq_list, *list_ptr;
void init_list(list_ptr lp) //初始化
{
assert(lp != NULL);
lp->base = (value_ptr)malloc(sizeof(value_type)*INIT_SIZE); //free
assert(lp->base != NULL);
memset(lp->base, 0, sizeof(value_type)*INIT_SIZE);
lp->size = 0;
lp->capacity = INIT_SIZE;
}
bool insert_elem(list_ptr lp, const int pos, const value_type elem) //插入元素
{
assert(lp != NULL && pos >= 1 && pos <= lp->size+1);
if(list_full(lp)){ //如果表满，追加申请空间
value_ptr new_base = (value_ptr)realloc(lp->base,
sizeof(value_type)*(lp->capacity+LIST_INCREMENT));//此处注意realloc用法，用新地址接收是为了防止realloc失败，原地址有效内容被释放
assert(new_base != NULL); //并且realloc填写的申请空间大小必须是之前的大小+增量的大小，而不是只写增量，否则如果原地址内存不够，在新地址申请增量大小的空间，将之前的内容挪至新空间，内存溢出，将发生段错误
lp->base = new_base; //再赋回给原地址
lp->base[lp->capacity] = elem;
lp->capacity += LIST_INCREMENT;
++lp->size;
}
else{ //未满，插入元素
for(int i=lp->size-1; i>=pos-1; --i){ //将元素后移，腾出位置
lp->base[i+1] = lp->base[i];
}
lp->base[pos-1] = elem; //插入元素
++lp->size;
//}
return true;
}
bool remove_elem_pos(list_ptr *lp, const int pos) //按位置删除
{
assert(pos >= 1 && pos <= (*lp)->size);
for(value_ptr ptmp=&(*lp)->base[pos-1]; ptmp<&(*lp)->base[(*lp)->size-1]; ++ptmp)
*ptmp = *(ptmp+1);
(*lp)->base[(*lp)->size-1] = 0;
--(*lp)->size;
return true;
}
bool remove_elem_val(list_ptr *lp, value_type elem) //按值删除
{
for(int i=0; i<(*lp)->size; ++i)
if((*lp)->base[i] == elem){
for(int j=i; j<(*lp)->size-1; ++j) //所有符合要求的值都被删除
(*lp)->base[j] = (*lp)->base[j+1];
(*lp)->base[(*lp)->size-1] = 0;
--(*lp)->size;
}
return true;
}
bool remove_elem(list_ptr lp, const void* clue, DELETE_MODE mode) //外部接口，第三个参数选择按位置或按值删除模式
{
assert(lp != NULL);
if(list_empty(lp)){ //表空，不能删
fprintf(stdout, "already empty, can not remove.\\n");
return false;
}
if(mode == POSITION){ //参数为POSITION，按位置删除
remove_elem_pos(&lp, *(int *)clue);
}
else{ //否则按值删除
remove_elem_val(&lp, *(value_ptr)clue);
}
return true;
}
void print_list(const seq_list sl) //打印函数
{
if(sl.size == 0)
fprintf(stdout, "nil list.");
for(int i=0; i<sl.size; ++i)
printf("%f ", sl.base[i]);
printf("\\n");
}
int compare(const void *vp1, const void* vp2) //比较函数
{
return *(value_ptr)vp1 - *(value_ptr)vp2;
}
int locate_elem(const seq_list sl, const value_type elem,
int (*compare)(const void *, const void *)) //定位函数
{
if(list_empty(&sl)){
fprintf(stdout, "list empty, con not locate.\\n");
}
else{
for(int i=0; i<sl.size; ++i)
if((*compare)(&sl.base[i], &elem) == 0) //相等则找到，返回位置
return i+1;
}
return 0;
}
void sort_list(list_ptr lp, int (*compare)(const void *, const void *)) //排序函数
{
assert(lp != NULL);
qsort(lp->base, lp->size, sizeof(value_type), compare); //调用系统快速排序
}
void merge_list(list_ptr lpa, list_ptr lpb, list_ptr combine,
int (*compare)(const void *, const void *)) //合并两个顺序表
{
assert(lpa != NULL && lpb != NULL && combine != NULL);
combine->base = (value_ptr)malloc(sizeof(value_type)
*(lpa->size+lpb->size)); //此处为新表申请空间，因此新表无需另外调用初始化函数，否则会发生内存泄漏
assert(combine->base != NULL);
combine->capacity = combine->size = lpa->size+lpb->size;
value_ptr it_pc = combine->base;
value_ptr it_pa=lpa->base;
value_ptr it_pb=lpb->base;
while(it_pa<lpa->base+lpa->size && it_pb<lpb->base+lpb->size){ //由小到大插入新表
if(compare(it_pa, it_pb) <= 0)
*it_pc++ = *it_pa++;
else
*it_pc++ = *it_pb++;
}
while(it_pa < lpa->base+lpa->size) //从上面while出循环只有两种情况，此处为pa为插完，pb已插完，pa剩余元素直接插入，天然有序
*it_pc++ = *it_pa++;
while(it_pb < lpb->base+lpb->size) //同理，若pb剩有元素，直接插入，天然有序
*it_pc++ = *it_pb++;
}
#endif /*seq_list*/
|
二：测试代码
?
|
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
|
为保证通用性，不用int，用float测试。
#include "seq_list.h"
#define ARRAY_SIZE 10
int main()
{
value_type array[] = {39.1, 32.1, 10.1, 11.1, 22.1, 5.1, 36.1, 28.1, 46.1, 32.1};
seq_list list; //顺序表1
init_list(&list);
for(int i=0; i<ARRAY_SIZE; ++i)
insert_elem(&list, 1, array[i]);
printf("list:\\n");
print_list(list);
#if 1
int clue = 1; //按顺序删除，删除第一个元素
//value_type clue = 32.1; //按值删除，删除值为32.1的元素，需修改下面参数为VALUE
printf("after remove:\\n");
remove_elem(&list, &clue, POSITION);
print_list(list);
#endif
#if 1
int found = locate_elem(list, 22.1, compare); //定位22.1元素所在位置
if(found >= 1)
fprintf(stdout, "found %f at the position %d\\n", list.base[found-1], found);
else
fprintf(stdout, "not found.\\n");
#endif
sort_list(&list, compare);
printf("list after sort:\\n");
print_list(list);
value_type array2[] = {98.1, 65.1, 4.1, 86.1, 34.1, 21.1, 86.1, 74.1, 93.1, 46.1};
seq_list list2;
init_list(&list2);
for(int i=0; i<ARRAY_SIZE; ++i)
insert_elem(&list2, 1, array2[i]);
printf("list2:\\n");
print_list(list2);
printf("list2 after sort:\\n");
sort_list(&list2, compare);
print_list(list2);
seq_list new_list; //无需调用init函数初始化，因为新表在merge_list中会初始化。如果强行调用，那么会出现内存泄漏。
merge_list(&list, &list2, &new_list, compare);
printf("new merge_list:\\n");
print_list(new_list);
free(list.base);
free(list2.base);
free(new_list.base); //三个释放，防止内存泄漏
return 0;
}
|
相关文章
猜你喜欢
- ASP.NET自助建站系统中的用户注册和登录功能定制方法 2025-06-10
- ASP.NET自助建站系统的域名绑定与解析教程 2025-06-10
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
