ADT线性表List的定义和顺序表示及实现_adt list

作者：黑客灵魂 | 2024-07-09 06:07:31

踩

adt list

目录大纲

一、线性表的类型定义
二、线性表的顺序表示和实现

文章内容引用清华大学出版社严蔚敏版《数据结构》并加以笔者注释

一、线性表的类型定义

线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数字或者一个符号，也可以是一列数字的集合(例如二维数组)，亦或是一串字符(例如字符串数组)，甚至其他更复杂的信息。例如，26个英文字母的字母表：（A，B，C，···，Z）是一个线性表，表中的数据元素是单个字母字符。又如：(6, 17, 28, 50, 92, 188)表中的数据元素是整数。

在稍微复杂的线性表中，一个数据元素可以又若干个数据项(item)组成。在这种情况下，常把数据元素称为记录(record)，含有大量记录的线性表又称文件(file)。

例如,一个学校的学生健康情况登记表如图2.1所示，表中每个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等6个数据项组成。

姓名	学号	性别	年龄	班级	健康状况
王小林	790631	男	18	计91	健康
陈红	790632	女	20	计91	一般
刘建平	790633	男	21	计91	健康
~	~	~	~	~	~

图2.1 学生健康情况登记表

同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。若将线性表记为

(a ₁，···，a _i-1，a _i，a _i+1，···，a _n)

则表中a_i-1领先于a_i，a_i领先于a_i+1，称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。当i=2，3，···，n时，a_i有且仅有一个直接前驱。

线性表中元素的个数n(n≥0)定义为线性表的长度，n=0时称为空表。

抽象数据类型线性表的定义如下：

ADT List {

        数据对象：D = {a_i | a_i ∈ ElemSet，i = 1, 2, ```, n, n ≥ 0 }

        数据关系：R1 = { < a _i-1，a_i > | a_i-1，a_i ∈ D，i = 2, ```, n }

        基本操作：

          InitList( &L )

            操作结果：构造一个空的线性表L。

          Destroy( &L)

            初始条件：线性表L已存在。

            操作结果：销毁线性表L。

          ClearList( &L )

            初始条件：线性表L已存在。

            操作结果：将L重置为空表。

          ListEmpty( L )

            初始条件：线性表L已存在。

            操作结果：若L为空表，则返回TRUE，否则FALSE。

          ListLength( L )

            初始条件：线性表L已存在。

            操作结果：返回L中数据元素个数。

          GetElem( L, i, &e )

            初始条件：线性表L已存在，1≤i≤ListLength(L)。

            操作结果：使用e返回L中的第i个数据元素的值。

          LocateElem( L, e, compare() )

            初始条件：线性表L已存在，compare()是数据元素判定函数。

            操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。

          PriorElem( L, cur_e, &pre_e )

            初始条件：线性表L已存在。

            操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。

          NextElem( L, cur_e, &next_e )

            初始条件：线性表L已存在。

            操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的后继，否则操作失败，next_e无定义。

          ListInsert( &L, i, e )

            初始条件：线性表L已存在，1≤i≤ListLength(L) + 1。

            操作结果：在L中第i个位置之前插入新的数据元素e，长的长度加1。

          ListDelete( &L, i,& e )

            初始条件：线性表L已存在，1≤i≤ListLength(L) + 1。

            操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。

          ListTraverse( L, visit() )

            初始条件：线性表L已存在。

            操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

} ADT List

二、线性表的顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(a_i+1)和第i个数据元素的存储位置LOC(a_i)之间满足下列关系：

LOC(a _i+1) = LOC(a _i) + l

一般来说，线性表的第i个数据元素a_i的存储位置为

LOC(a _i) = LOC(a ₁) + ( i - 1 ) × l

式中LOC(a₁)是线性表的第一个数据元素a₁的存储位置，通常称作线性表的起始位置或基地址。

线性表的这种机内表示乘坐线性表的顺序存储结构或顺序映像（sequential mapping），通常，称这种存储结构的线性表为顺序表。它的特点是，为表中相邻的元素a_i和a_i+1赋以相邻的存储位置LOC(a_i)和LOC(a_i+1)。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序结构是一种随机存取的存储结构。

由于高级程序设计语言中的数组类型也有随机存储的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。

具体实现如下

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h> 

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define LIST_INIT_SIZE 100	//线性表存储空间的初始分配量
#define LISTINCREMENT 10 	//线性表存储空间的分配增量 

/*Status 是函数的类型，其值是函数结果状态代码*/ 
typedef int Status; 
/*数据元素类型*/ 
typedef int ElemType;

typedef struct{
	ElemType *elem;		//存储空间基址
	int length;			//当前长度
	int listsize;		//当前分配的存储容量(以sizeof(ElemType)为单位) 
}SqList;

/*初始化顺序表*/ 
Status InitList(SqList &L);

/*销毁顺序表*/
Status DestroyList(SqList &L);

/*清空顺序表中的元素*/
Status ClearList(SqList &L);

/*判断顺序表是否为空*/
Status ListEmpty(SqList L);

/*返回顺序表的长度*/
int ListLength(SqList L);

/*用e获取顺序表中第i个元素的值*/
Status GetElem(SqList L, int i, ElemType &e);

/*比较两元素是否相等*/ 
Status equal(ElemType e1, ElemType e2);

/*返回顺序表中第1个与e满足关系compare()的数据元素的位序，若元素不存在，则返回值为0*/
int LocateElem(SqList L, ElemType e, Status (*compare)(ElemType, ElemType));

/*若cur_e是L的数据元素，使用pre_e返回cur_e的前驱元素*/
Status PriorElem(SqList L, ElemType e, ElemType &pre_e);

/*若cur_e是L的数据元素，且不是最后一个，则使用next_e返回cur_e的后继元素*/
Status NextElem(SqList L, ElemType e, ElemType &next_e);

/*在第i个元素位置插入新的元素e，L的长度加1*/
Status ListInsert(SqList &L, int i, ElemType e);

/*删除第i个位置的元素,L的长度减1*/ 
Status ListDelete(SqList &L, int i, ElemType &e); 
 
/*依次对L中的每个元素调用visit()函数，若visit()失败，则操作失败*/ 
Status ListTraverse(SqList L, Status (*visit)(ElemType));

/*自定义函数，用来打印list中的每个元素*/
Status print(ElemType e)
{
	printf("%d ", e);
	return OK;
}

int main()
{
	SqList L;
	/*初始化顺序表L*/ 
	if(InitList(L))
	{
		printf("顺序表L初始化成功\n");
		if(ListEmpty(L))
		{
			printf("\n顺序表L为空表!\n");
		}
		
		/*向L的第一个元素位置插入1*/
		if(ListInsert(L, 1, 1))		
		{
			printf("\n元素1成功地插入到L的第一个元素中!\n");	
		}
		else
		{
			printf("\n元素插入失败!\n");
		}
		
		/*获取L中的第一个元素值*/
		ElemType e;	
		if(GetElem(L, 1, e))		
		{
			printf("\nL中的第一个元素为%d\n", e);
		}
		
		/*寻找满足与1equal()的元素位序*/ 
		int i = LocateElem(L, 0, equal);
		if(i >= 1)
		{
			printf("\n与1满足equal()条件的元素位置为%d\n", i); 
		}
		else
		{
			printf("\n没有找到与1满足equal()条件的元素！\n");	
		} 
		
		/*插入多个数据元素*/
		ListInsert(L, 2, 2);
		ListInsert(L, 3, 3);
		ListInsert(L, 4, 4);
		
		ElemType next_e;
		if(NextElem(L, 2, next_e))
		{
			printf("\n已找到元素2的后继元素，为%d\n", next_e);	
		}		 
		else
		{
			/*此时可能是因为L中无2这个元素或者元素2无后继元素*/ 
			printf("\n未找到元素2的后继元素!\n");
		}
		
		ElemType pre_e;
		if(PriorElem(L, 2, pre_e))
		{
			printf("\n已找到元素2的前驱元素，为%d\n", pre_e);	
		}		 
		else
		{
			/*此时可能是因为L中无2这个元素或者元素2无前驱元素*/ 
			printf("\n未找到元素2的前驱元素!\n");
		}		
	
		/*删除位序为2的元素*/
		if(ListDelete(L, 2, e)) 
		{
			printf("\n已成功删除位序为2的元素,值为%d\n", e);
		}
		else
		{
			printf("\n删除失败！\n");
		}
		
		/*遍历打印L中的所有元素，将print函数指针代入visit()*/ 
		printf("\n开始遍历L中的所有元素!\n");
		ListTraverse(L, print);
				
		/*清空顺序表L*/
		if(ClearList(L)) 
		{
			printf("\n清空成功!\n"); 
		}
		else
		{
			printf("\n清空失败!\n");
		}
		
		/*判断顺序表L是否为空*/
		if(ListEmpty(L)) 
		{
			printf("\n顺序表L为空!\n"); 
		}
		/*最后销毁L，回收空间*/ 
		if(DestroyList(L))
		{
			printf("\n顺序表L销毁成功\n"); 
		}
		  
	}
	return 0;
}

/*初始化顺序表L*/ 
Status InitList(SqList &L)
{
	/*构造一个空的线性表L*/
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L.elem)
		exit(OVERFLOW);		//存储分配失败 
	L.length = 0;			//空表长度为0 
	L.listsize = LIST_INIT_SIZE;	//初始存储容量 
	return OK;
}

/*销毁顺序表L，回收空间*/ 
Status DestroyList(SqList &L)
{
	free(L.elem);
	L.elem = NULL;
	return OK; 
} 

/*将L重置成空表*/ 
Status ClearList(SqList &L)
{
	free(L.elem);		//回收内存 
	if(InitList(L))		//进行初始化L 
		return OK;
	else
		return ERROR;
}

/*若L为空表，返回TRUE，否则返回FALSE*/ 
Status ListEmpty(SqList L)
{
	return L.length > 0 ? FALSE : TRUE;
}

/*返回L的长度*/ 
int ListLength(SqList L)
{
	return L.length;
}

/*若第i个元素存在，返回L中第i个元素*/ 
Status GetElem(SqList L, int i, ElemType &e)
{
	/*判断第i个元素是否存在，不存在返回ERROR*/ 
	if(i < 1 || i > L.length)
		return ERROR;
	e = L.elem[i - 1];
	return OK;
}

/*判断两个元素是否相等*/ 
Status equal(ElemType e1, ElemType e2)
{
	return e1 == e2 ? TRUE : FALSE;
}

/*返回L中第1个满足compare()函数的元素的位序,若不存在，则返回0*/ 
int LocateElem(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) 
{
	for(int i = 0; i < L.length; i++)
	{
		if((*compare)(e, L.elem[i]))
			return i + 1;
	}
	return 0;
}

/*若cur_e不是第一个元素，则返回cur_e的前驱元素*/ 
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e)
{
	int i = LocateElem(L, cur_e, equal);	//定位cur_e的位置 
	if(i == 0 || i == 1)	//不符合要求 
	{
		return ERROR;
	}	
	else
	{
		pre_e = L.elem[i - 2];
		return OK;
	}
}

/*若cur_e不是最后一个元素，则返回cur_e的后继元素*/ 
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e)
{
	int i = LocateElem(L, cur_e, equal);
	if(i == L.length || i == 0)
	{
		return ERROR;
	}
	else
	{
		next_e = L.elem[i];
		return OK;
	}
}

/*若存在第i个元素，则将新元素e插入到L的第i个元素位置中*/ 
Status ListInsert(SqList &L, int i, ElemType e)
{
	if(i < 1 || i > L.length + 1)
		return ERROR;
		
	if(L.length >= L.listsize)
	{
		ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase)
			exit(OVERFLOW);				//存储分配失败 
		L.elem = newbase;				//新基址 
		L.listsize += LISTINCREMENT;	//增加存储容量 
	}
	
	ElemType *q = &L.elem[i - 1];				//第i个元素的地址,即元素插入的位置 
	ElemType *p = &L.elem[L.length - 1];		//最后一个元素的地址 
	for(p; p >= q; p--)
	{
		*(p + 1) = *p;
	}
	*q = e;			//插入e
	L.length++;		//增加L的长度
	
	return OK; 
}

/*若i合法，则删除L中第i个位置的元素，使用e返回其值*/ 
Status ListDelete(SqList &L, int i, ElemType &e)
{
	if(i < 1 || i > L.length + 1)
		return ERROR;
		
	e = L.elem[i - 1];
	ElemType *q = &L.elem[i - 1];		//第i个元素的位置，即元素删除的位置
	ElemType *p = &L.elem[L.length - 1];
	for(q; q < p; q++)
	{
		*q = *(q + 1);
	}
	L.length--;
	
	return OK;
}

/*依次对L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败*/ 
Status ListTraverse(SqList L, Status (*visit)(ElemType))
{
	for(int i = 0; i < L.length; i++)
	{
		if(!(*visit)(L.elem[i]))		//依次对L中的每个元素调用visit()函数 
			return ERROR;
	} 
	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
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/801671