線性表是最常用且最簡單的一種數據結構，一個線性表是 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