本文实例讲述了C语言实现的顺序表功能。分享给大家供大家参考，具体如下：
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
|
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include<cstdio>
#include<malloc.h>
#include<assert.h>
#define SEQLIST_INIT_SIZE 8
#define INC_SIZE 3 //空间增量的大小
typedef int ElemType;
typedef struct Seqlist {
ElemType *base;
int capacity; //顺序表容量
int size; //表的大小
}Seqlist;
bool Inc(Seqlist *list);//增加顺序表的容量
void InitSeqlist(Seqlist *list); //初始化顺序表
void push_back(Seqlist *list, ElemType x); //在顺序表的末尾插入元素
void push_front(Seqlist *list, ElemType x); //在顺序表的头部插入元素
void show_list(Seqlist *list); //显示顺序表中的元素
void pop_back(Seqlist *list); //删除顺序表最后一个元素
void pop_front(Seqlist *list); //删除顺序表第一个元素
void insert_pos(Seqlist *list, int pos, ElemType x);//在顺序表的选定位置上插入数据
int find(Seqlist *list, ElemType key); //在顺序表中查找元素key的下标
int length(Seqlist *list);//求顺序表的长度
void delete_pos(Seqlist *list, int pos); //删除顺序表中特定位置的数据元素
void delete_val(Seqlist *list, int key);//删除顺序表中值为key的数据元素
void sort(Seqlist *list);//冒泡排序
void reverse(Seqlist *list);//逆置顺序列表
void clear(Seqlist *list);//清除顺序表中的所有元素
void destroy(Seqlist *list);//摧毁顺序表
void merge(Seqlist *lt, Seqlist *la, Seqlist *lb);//合并两个顺序列表
#endif //__SEQLIST_H__
|
seqlist.cpp
|
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
|
#include"seqlist.h"
bool Inc(Seqlist *list) {
ElemType *newbase = (ElemType*)realloc(list, sizeof(ElemType)*(list->capacity + INC_SIZE)); //重新分配内存空间
if (newbase == NULL) {
printf("内存空间已满，无法再分配内存空间！\n");
return false;
}
list->base = newbase;
list->capacity += INC_SIZE;
return true;
}
void InitSeqlist(Seqlist *list) {
list->base = (ElemType*)malloc(sizeof(ElemType)*SEQLIST_INIT_SIZE);
assert(list->base != NULL);
list->capacity = SEQLIST_INIT_SIZE;
list->size = 0;
}
void push_back(Seqlist *list, ElemType x) {
if (list->size >= list->capacity && !Inc(list)) { //Inc(list)用来判断增加顺序表容量是否成功,只有在失败的情况下才会进入if语句中
printf("顺序表容量已满，无法再在表尾继续插入新元素！\n");
return;
}
list->base[list->size] = x;
list->size++;
}
void push_front(Seqlist *list, ElemType x) {
if (list->size >= list->capacity && !Inc(list)) {
printf("顺序表容量已满，无法再在表头插入新元素！\n");
return;
}
for (int i = list->size;i > 0;i--) {
list->base[i] = list->base[i - 1];
}
list->base[0] = x;
list->size++;
}
void show_list(Seqlist *list) {
for (int i = 0;i < list->size;i++) {
printf("%d ", list->base[i]);
}
printf("\n");
}
void pop_back(Seqlist *list) {
if (list->size == 0) {
printf("顺序表已空，无法再在表尾删除元素！\n");
return;
}
list->size--;
}
void pop_front(Seqlist *list) {
if (list->size == 0) {
printf("顺序表已空，无法再在表头删除元素！\n");
return;
}
for (int i = 0;i < list->size - 1;i++) {
list->base[i] = list->base[i + 1];
}
list->size--;
}
void insert_pos(Seqlist *list, int pos, ElemType x) {
if (pos<0 || pos>list->size) {
printf("插入位置不合法，无法插入元素！\n");
return;
}
if (list->size >= list->capacity && !Inc(list)) {
printf("顺序表容量已满，无法在插入新的元素！\n");
return;
}
for (int i = list->size;i > pos;i--) {
list->base[i] = list->base[i - 1];
}
list->base[pos] = x;
list->size++;
}
int find(Seqlist *list, ElemType key) {
for (int i = 0;i < list->size;i++) {
if (list->base[i] == key)
return i;
}
return -1;
}
int length(Seqlist *list) {
return list->size;
}
void delete_pos(Seqlist *list, int pos) {
if (pos < 0 || pos >= list->size) {
printf("删除位置不合法，无法删除元素！\n");
return;
}
for (int i = pos;i < list->size - 1;i++) {
list->base[i] = list->base[i + 1];
}
list->size--;
}
void delete_val(Seqlist *list, int key) {
int pos = find(list, key);
if (pos == -1) {
printf("顺序表中没有这个元素！\n");
return;
}
delete_pos(list, pos);
}
void sort(Seqlist *list) {
for (int i = 0;i < list->size - 1;i++) {//排序的趟数（例如5个数据需要比较4趟）
for (int j = 0;j < list->size - 1 - i;j++) {//每一趟比较中的比较次数（例如5个数据在第0趟需要比较4次）
if (list->base[j] > list->base[j + 1]) {
ElemType temp = list->base[j];
list->base[j] = list->base[j + 1];
list->base[j + 1] = temp;
}
}
}
}
void reverse(Seqlist *list) {
if (list->size == 0 || list->size == 1) return;
int low = 0, high = list->size - 1;
while (low < high) {
ElemType temp = list->base[low];
list->base[low] = list->base[high];
list->base[high] = temp;
low++;
high--;
}
}
void clear(Seqlist *list) {
list->size = 0;
}
void destroy(Seqlist *list) {
free(list->base);
list->base = NULL;
list->capacity = 0;
list->size = 0;
}
void merge(Seqlist *lt, Seqlist *la, Seqlist *lb) {
lt->capacity = la->size + lb->size;
lt->base = (ElemType*)malloc(sizeof(ElemType)*lt->capacity);
assert(lt->base != NULL);
int ia = 0, ib = 0, ic = 0;
while (ia < la->size&&ib < lb->size) {
if (la->base[ia] < lb->base[ib]) {
lt->base[ic++] = la->base[ia++];
}
else {
lt->base[ic++] = lb->base[ib++];
}
}
while (ia < la->size) {
lt->base[ic++] = la->base[ia++];
}
while (ib < lb->size) {
lt->base[ic++] = lb->base[ib++];
}
lt->size = la->size + lb->size;
show_list(lt);
}
|
main.cpp
|
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
|
#include"seqlist.h"
void main() {
Seqlist list;
InitSeqlist(&list);
ElemType item;
int pos;
int select = 1;
while (select) {
printf("*******************************************\n");
printf("*[1] push_back [2] push_front *\n");
printf("*[3] show_list [4] pop_back *\n");
printf("*[5] pop_front [6] insert_pos *\n");
printf("*[7] find [8] length *\n");
printf("*[9] delete_pos [10] delete_value *\n");
printf("*[11] sort [12] reverse *\n");
printf("*[13] clear [14] merge *\n");
printf("*[0] quit_system *\n");
printf("*******************************************\n");
printf("请选择：>>");
scanf("%d", &select);
if (select == 0) break;
switch (select) {
case 1:
printf("请输入要插入的数据（-1结束）:>");
while (scanf("%d", &item), item != -1) {//先输入item的值，只要item不等于-1就接着循环
push_back(&list, item);
}
break;
case 2:
printf("请输入要插入的数据（-1结束）:>");
while (scanf("%d", &item), item != -1) {
push_front(&list, item);
}
break;
case 3:
show_list(&list);
break;
case 4:
pop_back(&list);
break;
case 5:
pop_front(&list);
break;
case 6:
printf("请输入要插入的数据:>");
scanf("%d", &item);
printf("请输入要插入的位置:>");
scanf("%d", &pos);
insert_pos(&list, pos, item);
break;
case 7:
printf("请输入要查找的数据:>");
scanf("%d", &item);
pos = find(&list, item);
if (pos == -1)
printf("查找的数据元素不在顺序表中！\n");
else
printf("查找的数据元素在顺序表中的下标位置为%d\n", pos);
break;
case 8:
printf("顺序表的长度为%d\n", length(&list));
break;
case 9:
printf("请输入要删除数据在顺序表中的下标位置:>");
scanf("%d", &pos);
delete_pos(&list, pos);
break;
case 10:
printf("请输入要删除数据的值:>");
scanf("%d", &item);
delete_val(&list, item);
break;
case 11:
sort(&list);
break;
case 12:
reverse(&list);
break;
case 13:
clear(&list);
break;
case 14:
Seqlist mylist, yourlist;
ElemType item1, item2;
InitSeqlist(&mylist);
InitSeqlist(&yourlist);
printf("请输入顺序表1中的元素值（-1结束）:>");
while (scanf("%d", &item1), item1 != -1) {
push_back(&mylist, item1);
}
printf("请输入顺序表2中的元素值（-1结束）:>");
while (scanf("%d", &item2), item2 != -1) {
push_back(&yourlist, item2);
}
merge(&list, &mylist, &yourlist);
destroy(&mylist);
destroy(&yourlist);
break;
default:
printf("输入的选择错误！请重新输入！\n");
break;
}
}
destroy(&list);
}
|
希望本文所述对大家C语言程序设计有所帮助。
原文链接：http://www.cnblogs.com/duwenxing/p/7562588.html