1 线性表定义
线性表(list)是零个或多个数据元素的集合,线性表中的数据元素之间是有顺序的,线性表中的数据元素个数是有限的,线性表中数据元素的类型必须相同。
2 线性表数学定义
线性表(linear list)也称为有序表(
order list
)。每一个实例都是元素的一个有序集合。每一个实例的形式为(e
1
,e
2
,e
3
,...,e
n-1
),其中n为又穷自然数,e
i
是线性表的元素,i是元素e
i
的索引,n是线性表的大小。元素可以被看做原子,它们本身的结构与线性表的结构无关。当n = 0时,线性表为空;当n>0时,e
0
是线性表的第0个元素,e
n-1
是线性表的最后一个元素。
3 线性表的性质
e0为线性表的第一个元素,只有一个后继, en为线性表的最后一个元素,只有一个前驱。除e0和en外的其它元素ei,既有前驱,又有后继线性表能够逐项访问和顺序存取。
代码实现以及测试案例
复制代码
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//SeqList.h #ifndef _SEQLIST_H__ #define _SEQLIST_H__ typedef void SeqList; typedef void SeqListNode; //创建并且返回一个空的线性表 SeqList* SeqList_Create(int capacity); //销毁一个线性表list void SeqList_Destroy(SeqList* list); //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态 void SeqList_Clear(SeqList* list); //返回一个线性表list中的所有元素个数 int SeqList_Length(SeqList* list); int SeqList_Capacity(SeqList* list); //向一个线性表list的pos位置处插入新元素node int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //获取一个线性表list的pos位置处的元素 SeqListNode* SeqList_Get(SeqList* list, int pos); //删除一个线性表list的pos位置处的元素 返回值为被删除的元素,NULL表示删除失败 SeqListNode* SeqList_Delete(SeqList* list, int pos); #endif //_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
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//SeqList.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include "SeqList.h" //在结构体中套1级指针 typedef struct _tag_SeqList { int length; int capacity; unsigned int *node; //链表需要有内存空间装元素- 根据容量来分配内存空间-需要动态内存空间-则需要在结构体中定义一个指针 }TSeqList; //创建并且返回一个空的线性表 SeqList* SeqList_Create(int capacity) { int ret = 0; //1 链表申请动态内存空间 TSeqList *tmp = NULL; tmp = (TSeqList *)malloc(sizeof(TSeqList)); if (NULL == tmp) { ret = -1; printf("func malloc() err:%dn"); return NULL; } memset(tmp,0,sizeof(TSeqList));//让开辟的内存 完成链表初始化 //2 根据容量分配内存大小 tmp->node = (unsigned int *)malloc(sizeof(unsigned int *)*capacity); if (NULL == tmp->node) { ret = -2; printf("func malloc() err:%dn"); return NULL; } tmp->capacity = capacity; tmp->length = 0; return tmp; } //销毁一个线性表list void SeqList_Destroy(SeqList* list) { int ret = 0; //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp) { ret = -1; printf("func SeqList_Destroy() err:%dn",ret); } // 先申请 后释放 if (tmp->node!=NULL) { free(tmp->node); } free(tmp); } //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态 void SeqList_Clear(SeqList* list) { int ret = 0; //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp) { ret = -1; printf("func SeqList_Clear() err:%dn", ret); } tmp->length = 0; memset(tmp->node, 0, (tmp->capacity * sizeof(void *))); } //返回一个线性表list中的所有元素个数 int SeqList_Length(SeqList* list) { int ret = 0; //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp) { ret = -1; printf("func SeqList_Length() err:%dn", ret); } return tmp->length; } int SeqList_Capacity(SeqList* list) { int ret = 0; //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp) { ret = -1; printf("func SeqList_Capacity() err:%dn", ret); } return tmp->capacity; } //向一个线性表list的pos位置处插入新元素node int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) { int ret = 0; int i = 0; //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp) { ret = -1; printf("func SeqList_Insert() err:%dn", ret); } //如果满了 if (tmp->length >= tmp->capacity) { ret = -2; printf("func SeqList_Insert() err:%dn", ret); } //pos 位置容错处理 if (pos > tmp->length) { pos = tmp->length; } //元素后移 for (i = tmp->length; i > pos; i--) { tmp->node[i] = tmp->node[i-1]; } //空出位置插入结点 tmp->node[i] = (int *)node; tmp->length++; return 0; } //获取一个线性表list的pos位置处的元素 SeqListNode* SeqList_Get(SeqList* list, int pos) { int ret = 0; int i = 0; //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp||pos < 0|| pos >= tmp->length) { ret = -1; printf("func SeqList_Get() err:%dn", ret); } tmp = tmp->node[pos]; return tmp; } //删除一个线性表list的pos位置处的元素 返回值为被删除的元素,NULL表示删除失败 SeqListNode* SeqList_Delete(SeqList* list, int pos) { int ret = 0; int i = 0; SeqListNode *temp = NULL;//缓存删除的结点 //1 缓存下来 进行操作 TSeqList *tmp = NULL; tmp = (TSeqList *)list; if (NULL == tmp || pos < 0 || pos >= tmp->length) { ret = -1; printf("func SeqList_Delete() err:%dn", ret); } temp = tmp->node[pos]; //元素前移 for (int i = pos+1; i <tmp->length ; i++) { tmp->node[i - 1] = tmp->node[i]; //t[0]=t[1]; } tmp->length--; return temp; }
复制代码
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//text.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include "SeqList.h" //业务结点 typedef struct _Teacher { char name[32]; int age; }Teacher; int main() { int ret = 0; Teacher t1, t2, t3; t1.age = 31; t2.age = 32; t3.age = 33; //1 创建空的链表的顺序结构 SeqList *list = NULL; list = SeqList_Create(10); if (NULL == list) { ret = -1; printf("func err SeqList_Create():%dn"); return ret; } //思考1: 如何实现 链表的api(链表的算法) 和 具体的数据分离 //思考2: 链表库(业务逻辑) 测试程序的业务逻辑 结点的生命周期 归谁管? //2 插入元素 链表的插入 采用头插法 ret = SeqList_Insert(list,(SeqListNode *)&t1,0); if (ret!=0) { ret = -2; printf("func err SeqList_Insert()n"); return ret; } ret = SeqList_Insert(list, (SeqListNode *)&t2, 0); if (ret != 0) { ret = -3; printf("func err SeqList_Insert()n"); return ret; } ret = SeqList_Insert(list, (SeqListNode *)&t3, 0); if (ret != 0) { ret = -4; printf("func err SeqList_Insert()n"); return ret; } //3 遍历链表 for (int i = 0; i < SeqList_Length(list); i++) { Teacher *tmp = (Teacher *)SeqList_Get(list, i); //获取链表结点 if (NULL == tmp) { ret = -5; printf("func SeqList_Get() errn ", ret); return ret; } printf("age:%d n", tmp->age); } // 4 删除链表结点 while (SeqList_Length(list) > 0) { Teacher *tmp = (Teacher *)SeqList_Delete(list,0); if (NULL == tmp) { ret = -6; printf("func SeqList_Delete() errn "); return ret; } printf("age:%d n", tmp->age); } //5 销毁链表 SeqList_Destroy(list); system("pause"); return ret; }
最后
以上就是外向羊最近收集整理的关于数据结构之线性表——链表的顺序存储(数组描述)的全部内容,更多相关数据结构之线性表——链表内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复