用数组实现线性表，就是将数据都存放到数组中，然后写函数实现线性表的基本操作。
具体数组结构表示线性表如图所示：
数组实现线性表基本操作代码：
- 定义结构,用于存取线性表中的元素。
|
1 2 3 4 5 6 7 8 |
#define MaXSize 9999999 typedef struct LNode* List; struct LNode{ ElementType Data[MaXSize]; int Last; //最后一个元素 }; struct LNode L; List PtrL; |
- 初始化线性表：
|
1 2 3 4 5 6 7 |
List InitializeEmpty() { List PtrL; PtrL = new LNode(); PtrL->Last = -1; return PtrL; } |
- 查找元素
12345678int Find(ElementType X, List PtrL){int i=0;while(i< ptrl->Last && PtrL->Data[i] != X)i++;if (i >PtrL->Last) return -1; //没有找到元素else return i; //找到元素}
平均查找次数为(n+1)/2。最好情况，第一个找到，最坏情况最后一个找到。 - 返回K位序元素
12345ElementType Find(int k, List PtrL){if (k>=0 && K<=PtrL->Last)return PtrL->Data[k];} - 插入元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void Insert(ElementType X,int i, List PtrL) { int j; if (PtrL->Last == MAXSIZE-1){ //检查表满 printf("表满，元法差入！"); return; } if (i<1 || i>PtrL->Last+2){ //检查位置 printf("位置不合法"); return; } for(j=PtrL->Last;j>=i-1;j--){//移动元素 PtrL->Data[j+1] = PtrL->Data[j]; } PtrL->Data[i-1] = x; //插入元素 PtrL->Last++; //Last加1指向最后元素 return; } |
平均移动次数为n/2。最好情况，移一个元素，最坏情况移n个元素，时间复杂性O(n);
- 删除操作
123456789101112void Delete(int i,List PtrL){int j;if (i<1 || i>PtrL->Last+1){ //检查i是否合法printf("不存在第%d个元素",i);return;}for(j=i;j<=PrtL->Last;j++) //i后面元素往前移PtrL->Data[j-1] = PtrL->Data[j];PtrL->Last--;return}
平均移动次数为（n-1）/2，时间复杂性O(n);
从以上用数组实现线性表，可以分析出其优缺点。
数组实现线性表优点：
-
-
- 表中各元素之间的逻辑关系，不用添加额外的存储空间。
- 能够高速的存取表中任一位置的元素，（数组直接用下标[]操作符）。
-
数组实现线性表缺点：
-
-
- 插入和删除操作须要移动大量的元素，比如要删除第1个元素，就要将后面所有元素全部向前移动一次
- 动态性不好，线性表长度一直变化时，用数组实现效率会降低。（比如线性表长度从10万变成20万，就先要申请20万元素的内存，再将10万元素全部拷贝过来)
-