1. 首页
  2. 文章中心
  3. C/C++

数据结构-线性表-顺序表

87 阅读 0 评论
我是靠谱客的博主 标致小虾米，这篇文章主要介绍数据结构-线性表-顺序表，现在分享给大家，希望可以做个参考。

线性表-顺序表//附有详细注释
完整代码在最后。

常量，用于表示函数返回的状态等

复制代码
1
2
3
4
#define OVERFLOW -2
#define OK 1
#define ERROR 0

数据类型说明

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//数据类型说明
typedef int ElemType;
//为int类型创建两个新的名字：元素类型和状态
typedef int Status;
#define List_init_size 100
//储存空间最大值
#define Listincrement 10
//线性表存储空间初始分配量
typedef struct {
ElemType *elem;
//存储空间基址
int length;
//当前长度
int listsize;
//当前分配的存储容量
// (以sizeof(ElemType)为单位)
}sqlist;

初始化 线性表

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始化线性表：
Status lnitList(sqlist &L)
//Status即int类型，用以表示函数返回一种状态：OK 或者 ERROR 或者OVERFLOW
{
//构造一个空线性表L
L.elem=(ElemType *) malloc (List_init_size* sizeof (ElemType)); //ElemType，int的别名
// malloc 函数的功能是为一个对象在堆中分配一个sizeof (ElemType)大小的内存空间,并且返回一个指向这块内存的指针
if (!L.elem) exit (OVERFLOW);
L.length=0;
L.listsize= List_init_size;
//储存容量为100
return OK;
}

构建线性表的基本操作

复制代码
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
//在一个线性表中输入N个数据：
Status sqlistinput(sqlist &L, int n)
{
if (n>L.listsize) return ERROR;
for (int i=0; i<n; i++)
scanf("%d", &L.elem[i]);
L.length=n;
return OK;
}
//判线性表是否为空
Status ListEmpty(sqlist L)
{
if (!L.length) return ERROR;
else return OK;
}
//求线性表的长度
Status ListLength(sqlist L)
{
return L.length;
}
//将线性表L的数据输出：
Status sqlistoutput(sqlist L)
{
for (int i=0; i<ListLength(L); i++) printf ("%d
", L.elem[i]);
printf ("n");
return OK;
}
//取线性表的第i个元素，将结果保存在e中
Status GetElem(sqlist l, int i, ElemType &e)
{
if (i<1 || i>l.length+1)
return ERROR;
e=l.elem[i-1];
//数组元素下表从0开始，第i个元素在数组中的下标为i-1
return OK;
}

顺序表实验中拓展的线性表操作

复制代码
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
//两个数据元素是否相等的比较函数
Status equal(ElemType e1, ElemType e2)
{
if (e1==e2)
return OK;
else
return ERROR;
}
//根据compare函数在线性表中定位元素e的位置
int LocateElem_sq(sqlist L, ElemType e, Status (*compare)(ElemType,ElemType))	//成功返回位序,否则返回0
{
int i=1;
ElemType *p;
//定义指针用以遍历线性表
p=L.elem;
//线性表储存空间基址
while (i<=L.length && !(*compare) (*p++, e))
++i;
//找到e或者遍历完线性表停止循环，i记录位置
if (i<=L.length)
return i;
else
return 0;
}

在线性表中求某个元素的前一个元素和后一个元素

复制代码
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
//在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息
Status PriorElem(sqlist L, ElemType cur_e, ElemType &pre_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
//pos表示某元素的位置
if (pos==0)
return ERROR;
else if (pos==1)
return OVERFLOW; //overflow 表示位于第一个
else
{
GetElem(L,pos-1,pre_e);
//pos-1表示前驱结点的位置
return OK;
}
}
//在线性表中求某元素的后继结点
Status NextElem(sqlist L, ElemType cur_e, ElemType &next_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
if (pos==0)
return ERROR;
else if (pos==L.length)
return OVERFLOW;
//overflow 表示最后一个
else
{
GetElem(L,pos+1,next_e);
return OK;
}
}

线性表的插入和删除操作

复制代码
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
//在线性表中插入一个元素
Status Listinsert_sq(sqlist &L, int i, ElemType e)
{
ElemType *p,*q,*newbase;
if (i<1 || i>L.length+1)
return ERROR;
if (L.length>=L.listsize)
{
newbase=(ElemType *) realloc (L.elem, (L.listsize+Listincrement) * sizeof (ElemType));
//realloc更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小。
if (!newbase) exit (OVERFLOW);
L.elem=newbase;
L.listsize+=Listincrement;
}
q=&(L.elem[i-1]);
//此时的&为取地址运算符，当前指针q指向线性表的第i个元素
for (p=&(L.elem[L.length-1]); p>=q; --p)
//p指向最后一个元素
{
*(p+1)=*p;
//此时*为取值运算符，元素后移一位
}
*q=e;
//将e赋值给第i个元素
++L.length;
//插入一个元素后线性表长度加一
return OK;
}
//在线性表中删除第i个元素，其结果保留在e中
Status Listdelete_sq(sqlist &l, int i, ElemType &e)
//删除和插入原理基本相同
{
ElemType *p,*q;
if (i<1 || i>l.length)
return ERROR;
p=&(l.elem[i-1]);
e=*p;
q=&(l.elem[l.length-1]);
for (++p; p<=q; ++p)
{
*(p-1)=*p;
}
--l.length;
return OK;
}

主函数用于测试线性表顺序表

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
sqlist la;
//生成对象即线性表la
int m,n,i,e,k,cur_e,pre_e,next_e;
//建立线性表，并输入线性表的数据
lnitList(la);
printf ("请输入线性表 la 的元素个数 n n");
scanf ("%d", &n);
if(n>0 && n<=List_init_size)
{
printf ("请输入线性表 la 的 n 个元素n");
sqlistinput(la,n);
sqlistoutput(la);
printf ("n");
}
else
{
printf ("建立线性表失败，线性表长度最大为%d n",List_init_size);
system("pause");
system("cls");
return 0;
}

测试插入删除操作（测试应放在主函数中，下面不在赘述）

复制代码
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
//调用插入函数，对线性表进行插入操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入插入的元素的位置和插入的值 n");
scanf ("%d%d", &i, &e);
//i代表位置，e代表数值
m=Listinsert_sq(la, i, e);
if(m!=1) printf ("插入失败n");
else sqlistoutput(la);
system("pause");
system("cls");
//调用删除函数，对线性表进除删操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要删除的元素的位置n");
scanf ("%d", &i);
m=Listdelete_sq(la, i, e);
if(m!=1) printf ("删除失败n");
else
{
printf ("删除的数据是%d n", e);
sqlistoutput(la);
}
system("pause");
system("cls");

测试元素的位置

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//调用GetElem()函数，取第i个位置的元素的值。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个位置的元素n");
scanf ("%d", &i);
m=GetElem(la, i, e);
if(m!=1) printf ("查找失败n");
else printf ("线性表中第 %d 位查找到的数据是 %d n", i, e);
system("pause");
system("cls");
//调用LocateElem_sq函数，求元素cur_e的位置。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个元素的位置n");
scanf ("%d", &cur_e);
k=LocateElem_sq(la, cur_e, equal);
if(k==0) printf ("查找失败n");
else printf (" %d 在线性表中的位置是 %d n", cur_e, k);
system("pause");
system("cls");

求元素的前驱和后继

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//调用PriorElemQ函数 求元素cur_e的前驱。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的前驱，请输入数据n");
scanf ("%d", &cur_e);
m=PriorElem(la, cur_e, pre_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的前驱是 %d n", cur_e, pre_e);
system("pause");
system("cls");
//调用NextElem()函数，求元素cur_e的后继。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的后继，请输入数据n");
scanf ("%d", &cur_e);
m=NextElem(la, cur_e, next_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的后继是 %d n",cur_e, next_e);
}

最后，如果觉得这篇博客能帮助到你，请点个小小的赞支持一下我（收藏也行呀，嘻嘻），这是我继续更新的动力呀，关注我可以得到第一时间的更新，更加快人一步哦。
如果有问题请在评论区留言，一起交流进步。
附完整代码：

复制代码
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
#include "stdio.h"
#include "stdlib.h"
#define OVERFLOW -2
#define OK 1
#define ERROR 0
//数据类型说明
typedef int ElemType;
//为int类型创建两个新的名字：元素类型和状态
typedef int Status;
#define List_init_size 100
//储存空间最大值
#define Listincrement 10
//线性表存储空间初始分配量
typedef struct {
ElemType *elem;
//存储空间基址
int length;
//当前长度
int listsize;
//当前分配的存储容量
// (以sizeof(ElemType)为单位)
}sqlist;
//直接定义结构体变量sqlist
//初始化线性表：
Status lnitList(sqlist &L)
//Status即int类型，用以表示函数返回一种状态：OK 或者 ERROR 或者OVERFLOW
{
//构造一个空线性表L
L.elem=(ElemType *) malloc (List_init_size* sizeof (ElemType)); //ElemType，int的别名
// malloc 函数的功能是为一个对象在堆中分配一个sizeof (ElemType)大小的内存空间,并且返回一个指向这块内存的指针
if (!L.elem) exit (OVERFLOW);
L.length=0;
L.listsize= List_init_size;
//储存容量为100
return OK;
}
//在一个线性表中输入N个数据：
Status sqlistinput(sqlist &L, int n)
{
if (n>L.listsize) return ERROR;
for (int i=0; i<n; i++)
scanf("%d", &L.elem[i]);
L.length=n;
return OK;
}
//判线性表是否为空
Status ListEmpty(sqlist L)
{
if (!L.length) return ERROR;
else return OK;
}
//求线性表的长度
Status ListLength(sqlist L)
{
return L.length;
}
//将线性表L的数据输出：
Status sqlistoutput(sqlist L)
{
for (int i=0; i<ListLength(L); i++) printf ("%d
", L.elem[i]);
printf ("n");
return OK;
}
//取线性表的第i个元素，将结果保存在e中
Status GetElem(sqlist l, int i, ElemType &e)
{
if (i<1 || i>l.length+1)
return ERROR;
e=l.elem[i-1];
//数组元素下表从0开始，第i个元素在数组中的下标为i-1
return OK;
}
//两个数据元素是否相等的比较函数
Status equal(ElemType e1, ElemType e2)
{
if (e1==e2)
return OK;
else
return ERROR;
}
//根据compare函数在线性表中定位元素e的位置
int LocateElem_sq(sqlist L, ElemType e, Status (*compare)(ElemType,ElemType))	//成功返回位序,否则返回0
{
int i=1;
ElemType *p;
//定义指针用以遍历线性表
p=L.elem;
//线性表储存空间基址
while (i<=L.length && !(*compare) (*p++, e))
++i;
//找到e或者遍历完线性表停止循环，i记录位置
if (i<=L.length)
return i;
else
return 0;
}
//在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息
Status PriorElem(sqlist L, ElemType cur_e, ElemType &pre_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
//pos表示某元素的位置
if (pos==0)
return ERROR;
else if (pos==1)
return OVERFLOW; //overflow 表示位于第一个
else
{
GetElem(L,pos-1,pre_e);
//pos-1表示前驱结点的位置
return OK;
}
}
//在线性表中求某元素的后继结点
Status NextElem(sqlist L, ElemType cur_e, ElemType &next_e)
{
int pos;
pos=LocateElem_sq(L, cur_e, equal);
if (pos==0)
return ERROR;
else if (pos==L.length)
return OVERFLOW;
//overflow 表示最后一个
else
{
GetElem(L,pos+1,next_e);
return OK;
}
}
//在线性表中插入一个元素
Status Listinsert_sq(sqlist &L, int i, ElemType e)
{
ElemType *p,*q,*newbase;
if (i<1 || i>L.length+1)
return ERROR;
if (L.length>=L.listsize)
{
newbase=(ElemType *) realloc (L.elem, (L.listsize+Listincrement) * sizeof (ElemType));
//realloc更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小。
if (!newbase) exit (OVERFLOW);
L.elem=newbase;
L.listsize+=Listincrement;
}
q=&(L.elem[i-1]);
//此时的&为取地址运算符，当前指针q指向线性表的第i个元素
for (p=&(L.elem[L.length-1]); p>=q; --p)
//p指向最后一个元素
{
*(p+1)=*p;
//此时*为取值运算符，元素后移一位
}
*q=e;
//将e赋值给第i个元素
++L.length;
//插入一个元素后线性表长度加一
return OK;
}
//在线性表中删除第i个元素，其结果保留在e中
Status Listdelete_sq(sqlist &l, int i, ElemType &e)
//删除和插入原理基本相同
{
ElemType *p,*q;
if (i<1 || i>l.length)
return ERROR;
p=&(l.elem[i-1]);
e=*p;
q=&(l.elem[l.length-1]);
for (++p; p<=q; ++p)
{
*(p-1)=*p;
}
--l.length;
return OK;
}
int main()
{
sqlist la;
//生成对象即线性表la
int m,n,i,e,k,cur_e,pre_e,next_e;
//建立线性表，并输入线性表的数据
lnitList(la);
printf ("请输入线性表 la 的元素个数 n n");
scanf ("%d", &n);
if(n>0 && n<=List_init_size)
{
printf ("请输入线性表 la 的 n 个元素n");
sqlistinput(la,n);
sqlistoutput(la);
printf ("n");
}
else
{
printf ("建立线性表失败，线性表长度最大为%d n",List_init_size);
return 0;
}
system("pause");
system("cls");
//调用插入函数，对线性表进行插入操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入插入的元素的位置和插入的值 n");
scanf ("%d%d", &i, &e);
//i代表位置，e代表数值
m=Listinsert_sq(la, i, e);
if(m!=1) printf ("插入失败n");
else sqlistoutput(la);
system("pause");
system("cls");
//调用删除函数，对线性表进除删操作
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要删除的元素的位置n");
scanf ("%d", &i);
m=Listdelete_sq(la, i, e);
if(m!=1) printf ("删除失败n");
else
{
printf ("删除的数据是%d n", e);
sqlistoutput(la);
}
system("pause");
system("cls");
//调用GetElem()函数，取第i个位置的元素的值。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个位置的元素n");
scanf ("%d", &i);
m=GetElem(la, i, e);
if(m!=1) printf ("查找失败n");
else printf ("线性表中第 %d 位查找到的数据是 %d n", i, e);
system("pause");
system("cls");
//调用LocateElem_sq函数，求元素cur_e的位置。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("请输入要获得哪个元素的位置n");
scanf ("%d", &cur_e);
k=LocateElem_sq(la, cur_e, equal);
if(k==0) printf ("查找失败n");
else printf (" %d 在线性表中的位置是 %d n", cur_e, k);
system("pause");
system("cls");
//调用PriorElemQ函数 求元素cur_e的前驱。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的前驱，请输入数据n");
scanf ("%d", &cur_e);
m=PriorElem(la, cur_e, pre_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的前驱是 %d n", cur_e, pre_e);
system("pause");
system("cls");
//调用NextElem()函数，求元素cur_e的后继。
printf ("当前线性表为：n");
sqlistoutput(la);
printf ("求元素的后继，请输入数据n");
scanf ("%d", &cur_e);
m=NextElem(la, cur_e, next_e);
if(m!=1) printf ("查找失败n");
else printf (" %d 元素的后继是 %d n",cur_e, next_e);
return 0;
}

最后

以上就是标致小虾米最近收集整理的关于数据结构-线性表-顺序表的全部内容，更多相关数据结构-线性表-顺序表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(58)

相关文章

对单链表的基本操作
对单链表的基本操作
双链表基本操作
双链表基本操作
双链表的基本操作
双链表的基本操作
c语言编程 ex=1,试用C语言编程1.构造一个空线性表,算法如下:StatusIni 爱问知识人...
c语言编程 ex=1,试用C语言编程1.构造一个空线性表,算法如下:StatusIni 爱问知识人...
数据结构-线性表-顺序表
数据结构-线性表-顺序表
数据结构（c语言版）顺序表的建立、初始化、插入、删除、遍历等12个基本操作及测试
数据结构（c语言版）顺序表的建立、初始化、插入、删除、遍历等12个基本操作及测试
C语言实现顺序表的基本操作
C语言实现顺序表的基本操作
链表InitList传入双重指针分析
链表InitList传入双重指针分析

评论列表共有 0 条评论

立即
投稿
返回
顶部