线性表是最常用且最简单的一种数据结构，一个线性表是 N 个数据元素的有限序列。
顺序表存储结构能够容易的实现随机存取线性表中的第 i 个数据元素，但是插入和删除表中的数据元素时，需要移动大量的数据元素。
因此，顺序表存储结构适用于数据相对稳定的线性表。
环境：eclipse，MinGW 5.1.4
File : list.h
1 /**
2 * =================================
3 * @描述: List 头文件
4 * @作者: fancy
5 * @日期: 2012-11-02
6 * @联系: fancydeepin@yeah.net
7 * =================================
8 */
9
10 #include <stdio.h>
11 #include <malloc.h>
12
13 typedef int Data;
14 typedef int Status;
15 #define OK 1
16 #define NO 0
17 #define YES 1
18 #define ERROR 0
19 #define OVERFLOW -1
20 #define OutOfBound -1
21 #define LIST_INIT_SIZE 25
22 #define LIST_INCREMENT_COUNT 15
23
24 //线性表结构
25 struct List {
26 int size; //线性表长度大小
27 int count; //线性表元素计数
28 Data *data; //数据元素
29 };
30
31 /**
32 * 描述: 初始化线性表
33 * 参数: &L 线性表
34 * 参数: length 长度
35 * 返回: ERROR/OK
36 */
37 Status initList(List &L, int length){
38
39 L.data = (Data*)malloc(length * sizeof(Data));
40 if(!L.data){
41 return ERROR;
42 }
43 L.count = 0;
44 L.size = length;
45 return OK;
46 }
47
48 /**
49 * 描述: 初始化线性表
50 * 参数: &L 线性表
51 * 返回: ERROR/OK
52 */
53 Status initList(List &L){
54
55 return initList(L, LIST_INIT_SIZE);
56 }
57
58 /**
59 * 描述: 创建指定长度大小的线性表
60 * 参数: size 长度
61 * 返回: List
62 */
63 List newList(int size){
64
65 List L;
66 if(initList(L, size) == OK){
67 return L;
68 }
69 exit(ERROR);
70 }
71
72 /**
73 * 描述: 创建线性表
74 * 返回: List
75 */
76 List newList(){
77
78 return newList(LIST_INIT_SIZE);
79 }
80
81 /**
82 * 描述: 判断线性表是否为空
83 * 参数: &L 线性表
84 * 返回: YES/NO
85 */
86 Status isEmptyList(List &L){
87
88 if(!L.data){
89 return YES;
90 }
91 return NO;
92 }
93
94 /**
95 * 描述: 将数据存储到线性表中的index位置
96 * 参数: &L 线性表
97 * 参数: data 数据
98 * 返回: ERROR/OK
99 */
100 Status putValue(List &L, int index, Data data){
101
102 if(!isEmptyList(L) && index >= 0 && index < L.size){
103 Data *p = L.data + index * sizeof(Data);
104 if(index >= L.count){
105 L.count++;
106 }
107 *p = data;
108 return OK;
109 }
110 return ERROR;
111 }
112
113 /**
114 * 描述: 将数据存储到线性表
115 * 参数: &L 线性表
116 * 参数: data 数据
117 * 返回: ERROR/OK
118 */
119 Status putValue(List &L, Data data){
120
121 if(!isEmptyList(L)){
122 if(L.count >= L.size){
123 Data *p = (Data*)realloc(L.data, (L.size + LIST_INCREMENT_COUNT) * sizeof(Data));
124 if(!p){
125 return ERROR;
126 }else{
127 L.data = p;
128 L.size += LIST_INCREMENT_COUNT;
129 }
130 }
131 *(L.data + L.count * sizeof(Data)) = data;
132 L.count++;
133 return OK;
134 }
135 return ERROR;
136 }
137
138 /**
139 * 描述: 将数据存储到线性表
140 * 参数: &L 线性表
141 * 参数: data 数据元素基址
142 * 参数: count 数据总计数
143 * 返回: ERROR/OK
144 */
145 Status putAll(List &L, Data *data, int count){
146
147 for(int i = 0; i < count; i++){
148 putValue(L, data[i]);
149 }
150 return OK;
151 }
152
153 /**
154 * 描述: 获取线性表中下标为index的值
155 * 参数: &L 线性表
156 * 参数: index 数据元素下标索引值
157 * 返回: Data
158 */
159 Data getValue(List &L, int index){
160
161 if(index < 0 || index > L.count){
162 return OutOfBound;
163 }else{
164 return *(L.data + index * sizeof(Data));
165 }
166 }
167
168 /**
169 * 描述: 获取线性表中下标为index的值，并存储到value中
170 * 参数: &L 线性表
171 * 参数: index 数据元素下标索引值
172 * 参数: &value 存储索引对应的值
173 * 返回: void
174 */
175 void getValue(List &L, int index, int &value){
176
177 value = getValue(L, index);
178 }
179
180 /**
181 * 描述: 在线性表中，在下标为index的位置插入一个数据元素，值为data，原先下标为index以及后面的数据元素往后移
182 * 参数: &L 线性表
183 * 参数: index 数据元素下标索引值
184 * 参数: data 插入的值
185 * 返回: ERROR/OK/OutOfBound
186 */
187 Status insertNode(List &L, int index, Data data){
188
189 if(index < 0 || index > L.count){
190 return OutOfBound;
191 }
192 if(L.count >= L.size){
193 Data *p = (Data*)realloc(L.data, (L.size + LIST_INCREMENT_COUNT) * sizeof(Data));
194 if(!p){
195 return ERROR;
196 }else{
197 L.data = p;
198 L.size += LIST_INCREMENT_COUNT;
199 }
200 }
201 Data *dp, *dq;
202 dq = L.data + index * sizeof(Data); //插入节点位置
203 dp = L.data + (L.count - 1) * sizeof(Data); //表尾结点位置
204 while(dp >= dq){ //右移
205 *(dp + 1 * sizeof(Data)) = *dp;
206 dp -= 1 * sizeof(Data);
207 }
208 *dq = data;
209 L.count++;
210 return OK;
211 }
212
213 /**
214 * 描述: 删除索引值为index的数据元素节点
215 * 参数: &L 线性表
216 * 参数: index 数据元素下标索引值
217 * 返回: OutOfBound/OK
218 */
219 Status removeNode(List &L, int index){
220
221 if(index < 0 || index > L.count){
222 return OutOfBound;
223 }
224 Data *dp, *dq;
225 dp = L.data + index * sizeof(Data); //删除节点位置
226 dq = L.data + (L.count - 1) * sizeof(Data); //表尾结点位置
227 while(dp < dq){ //左移
228 *dp = *(dp + 1 * sizeof(Data));
229 dp += 1 * sizeof(Data);
230 }
231 L.count--;
232 return OK;
233 }
234
235 /**
236 * 描述: 获取数据元素个数
237 * 参数: data 数据元素基址
238 * 参数: size 所有数据元素总大小
239 * 返回: 数据元素个数
240 */
241 int arrayLength(Data *data, int size){
242
243 int count = 0;
244 size /= sizeof(Data);
245 for(int i = 0; i < size; i++){
246 if(data[i] != '\0')
247 count++;
248 }
249 return count;
250 }
251
252 /**
253 * 描述: 自然排序(插入排序法)线性表
254 * 参数: &L 线性表
255 */
256 Status sortList(List &L){
257
258 if(isEmptyList(L)){
259 return OK;
260 }
261 int size = L.count;
262 Data data, *data_i, *data_j;
263 for(int i = 1; i < size; i++){
264 data_i = L.data + i * sizeof(Data);
265 for(int j = 0; j < i; j++){
266 data_j = L.data + j * sizeof(Data);
267 if(*data_j > *data_i){
268 data = *data_j;
269 *data_j = *data_i;
270 *data_i = data;
271 }
272 }
273 }
274 return OK;
275 }
File : linearList.c
1 /**
2 * =================================
3 * @描述: 测试
4 * @作者: fancy
5 * @日期: 2012-11-02
6 * @联系: fancydeepin@yeah.net
7 * =================================
8 */
9
10 #include "list.h"
11
12 int main() {
13
14 /*************************************************/
15 /* 存取、插入、删除 */
16 /*************************************************/
17 List list = newList();
18 Data data[] = {3, 1, 1, 0, 0, 0, 5, 9, 8, 1};
19 printf("存取数据: ");
20 putAll(list, data, 10);
21 for(int i = 0; i < list.count; i++){
22 printf("%d", getValue(list, i));
23 }
24 printf("\n插入数据: ");
25 insertNode(list, 9, 9);
26 for(int i = 0; i < list.count; i++){
27 printf("%d", getValue(list, i));
28 }
29 printf("\n删除数据: ");
30 removeNode(list, 9);
31 for(int i = 0; i < list.count; i++){
32 printf("%d", getValue(list, i));
33 }
34 printf("\n=======================================\n");
35
36 /*************************************************/
37 /* 排序数据元素 */
38 /*************************************************/
39 List linearList = newList();
40 Data dataSet[] = {20, 6, 18, 9, 11};
41 int count = arrayLength(dataSet, sizeof(dataSet));
42 putAll(linearList, dataSet, count);
43 printf("排序之前: ");
44 for(int i = 0; i < count; i++){
45 printf("%d\t", getValue(linearList, i));
46 }
47 printf("\n排序之后: ");
48 sortList(linearList);
49 for(int i = 0; i < count; i++){
50 printf("%d\t", getValue(linearList, i));
51 }
52 printf("\n=======================================\n");
53
54 /*
55 * 已知线性表LA和LB中的数据元素按值非递减有序排列，
56 * 现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。
57 * 设:
58 * LA = (3, 5, 8, 11)
59 * LB = (2, 6, 8, 9, 11, 15, 20)
60 * 则
61 * LC = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20)
62 */
63 /*************************************************/
64 /* 合并两个线性表 */
65 /*************************************************/
66 List LA = newList();
67 List LB = newList();
68 List LC = newList();
69 Data DA[] = {3, 5, 8, 11};
70 Data DB[] = {2, 6, 8, 9, 11, 15, 20};
71 putAll(LA, DA, 4);
72 putAll(LB, DB, 7);
73 printf("LA表数据元素: ");
74 for(int i = 0; i < LA.count; i++){
75 printf("%d\t", getValue(LA,i));
76 }
77 printf("\nLB表数据元素: ");
78 for(int i = 0; i < LB.count; i++){
79 printf("%d\t", getValue(LB,i));
80 }
81 int LA_index = 0, LA_size = LA.count, LA_value;
82 int LB_index = 0, LB_size = LB.count, LB_value;
83 while(LA_index < LA_size && LB_index < LB_size){
84 getValue(LA, LA_index, LA_value);
85 getValue(LB, LB_index, LB_value);
86 if(LA_value < LB_value){
87 putValue(LC, LA_value);
88 LA_index++;
89 }else{
90 putValue(LC, LB_value);
91 LB_index++;
92 }
93 }
94 while(LA_index < LA_size){
95 getValue(LA, LA_index++, LA_value);
96 putValue(LC, LA_value);
97 }
98 while(LB_index < LB_size){
99 getValue(LB, LB_index++, LB_value);
100 putValue(LC, LB_value);
101 }
102 printf("\nLC表数据元素: ");
103 for(int i = 0; i < LC.count; i++){
104 printf("%d\t", getValue(LC,i));
105 }
106 return 0;
107 }
测试结果：
存取数据: 3110005981
插入数据: 31100059891
删除数据: 3110005981
=======================================
排序之前: 20 6 18 9 11
排序之后: 6 9 11 18 20
=======================================
LA表数据元素: 3 5 8 11
LB表数据元素: 2 6 8 9 11 15 20
LC表数据元素: 2 3 5 6 8 8 9 11 11 15 20