数组实现线性表
对于线性结构，有两种保存的方法，一种是使用C语言中内置的数组，这样的结构成为顺序表；另一种使用指针，这样的结构成为链表。
对于线性结构，有12种基本的操作，分别是：初始化、删除、清空、判断是否为空、遍历、求表的长度、求某个元素在表中的位置、返回特定序号的元素、求某个元素的前一个元素、求某个元素的后一个元素、插入一个元素、删除一个元素。
这一小节介绍如何利用数组实现线性表。
先看程序：
1#include
2#include
3
4typedef int ElemType;
5
6
7typedef struct arraylist
8{
9
10//实际存放元素的数组
11 ElemType *Array;
12//数组中已经使用了多少元素
13int length;
14//数组的容量
15int size;
16
17}arrayList;
18
19//初始化顺序表：给出初始化长度
20bool initialArray(arrayList *arrLst,int len)
21{
22 arrLst->length = 0;
23 arrLst->size = len;
24 arrLst->Array = (ElemType*)malloc(len*sizeof(ElemType));
25if(NULL == arrLst->Array)
26return false;
27else
28return true;
29
30}
31
32//删除顺序表
33void deleteArray(arrayList *arrLst)
34{
35 arrLst->length = 0;
36 arrLst->size = 0;
37 free(arrLst->Array);
38 arrLst->Array = NULL;
39}
40
41//清空顺序表
42void clearArray(arrayList *arrLst)
43{
44 arrLst->length = 0;
45}
46
47//判断是否为空
48bool is_empty(arrayList *arrLst)
49{
50
51if(0 == arrLst->length)
52 {
53 printf("the arrayList is empty!\n");
54return true;
55 }
56else
57 {
58 printf("the arrayList is not empty!\n");
59return false;
60 }
61}
62
63//求有多少个元素
64int arrayLength(arrayList *arrLst)
65{
66return arrLst->length;
67}
68
69//取出某个元素
70bool getElem(arrayList *arrLst,int index,ElemType *e) 71{
72if(index < 0 || index > arrayLength(arrLst)-1)
73return false;
74else
75 {
76 *e = arrLst->Array[index];
77return true;
78 }
79
80}
81
82//遍历顺序表，并打印
83void printArray(arrayList *arrLst)
84{
85 printf("array elements are: ");
86for(int i = 0; i < arrayLength(arrLst);++i)
87 {
88 printf("%d\t",arrLst->Array[i]);
89 }
90 printf("\n");
91}
92
93//判断某个元素的位置
94int locateElem(arrayList *arrLst,ElemType e)
95{
96for(int i = 0; i < arrayLength(arrLst);++i)
97 {
98if(e == arrLst->Array[i])
99return i;
100 }
101return -1;
102
103}
104
105//求某个元素的前驱：如果没找到返回-2；如果是第一个元素。返回-1；否则返回前驱元素的下标
106int preElement(arrayList *arrLst,ElemType e,ElemType *preElem)
107{
108for(int i = 0 ; i < arrayLength(arrLst); ++i)
109 {
110//如果找到了
111if(e == arrLst->Array[i])
112 {
113//如果是第一个元素
114if(0 == i)
115 {
116return -1;
117 }
118else
119 {
120 *preElem = arrLst->Array[i-1];
121return i-1;
122 }
123 }
124 }
125return -2;
126}
127
128
129//求某个元素的后继：如果没找到，返回-2,如果是最后一个元素，返回-1；否则返回后继元素的下标
130int nextElement(arrayList *arrLst,ElemType e,ElemType *nxtElem)
131{
132for(int i = 0; i < arrayLength(arrLst); ++i)
133 {
134if(e == arrLst->Array[i])
135 {
136if(arrayLength(arrLst) -1 == i)
137 {
138return -1;
139 }
140else
141 {
142 *nxtElem = arrLst->Array[i+1];
143return i+1;
144 }
145 }
146 }
147return -2;
148}
149
150//将元素插入到指定位置
151bool insertElem(arrayList *arrLst,int index ,ElemType e )
152{
153//先判断插入位置是否合法
154if(0 > index || arrayLength(arrLst) < index)
155return false;
156
157//如果顺序表存储空间已满，则需要重新分配内存
158if(arrLst->length == arrLst->size)
159 {
160 arrLst->Array =
(ElemType*)realloc(arrLst->Array,2*arrLst->size*sizeof(ElemType));
161if(NULL == arrLst->Array)
162//分配失败，程序退出
163return false;
164else
165//分配成功，扩容
166 arrLst->size *= 2;
167 }
168//将插入点之后的元素后移
169for(int i = arrayLength(arrLst); i > index; --i)
170 arrLst->Array[i] = arrLst->Array[i-1];
171//插入元素
172 arrLst->Array[index] = e;
173//顺序表长度自增
174 ++arrLst->length;
175return true;
176}
177
178
179bool deleteElem(arrayList *arrLst,int index ,ElemType *e)
180{
181if(index < 0 || index > arrayLength(arrLst)-1)
182return false;
183 *e = arrLst->Array[index];
184//将删除点的元素依次左移
185for(int i = index; i < arrayLength(arrLst);++i)
186 {
187 arrLst->Array[i] = arrLst->Array[i+1];
188 }
189 --arrLst->length;;
190return true;
191}
大部分程序都很简单，唯一需要说明的是，再插入元素时，如果线性表已满，需要重新分配内存空间，新分配的内存空间设定为原来的2倍。这个倍数也不是我随便给出的，我是参考C++中STL里面的vector给出的。相信那些专家，肯定考虑了倍数过小而导致多次分配内存与内存分配太大的折中，我也就照猫画虎的这样做了。
其他的复杂的操作，大多数都能通过这些基本操作来完成，这里就不在列出了。
我们可以看出，利用数组来表示线性结构，最大的优点在于由于数组是连续储存的，所以随机访问速度非常快，只需要用数组的首地址+下标*sizeof(结构体)就能计算指定元素的地址了。而它的缺点也很明显：就是插入、删除时效率很低，因为要移动大量的元素，甚至需要重新分配内存。