线性表(linear_list)是最常用且最简单的一种数据结构，简言之，一个线性表是n个数据元素的有序序列。
例如：（a1 , ... , ai-1 , ai , ai+1 , ... , an)：ai-1 是 ai 的直接前驱，ai+1 是 ai 的直接后驱。
并且，当 i = 1，2，... ，n-1：ai 有且只有一个直接后驱。当 i = 2，3，... ，n：ai 有且只有一个直接前驱
例子：已知线性表LA，LB中的数据元素按值非递减有序排列，现将LA，LB按值非递减排列合并为LC。其伪代码为：
1 void MergeList(List La, List Lb, List &Lc) { 2 initList(Lc); //初始化Lc 3 i = j = 1; 4 k = 0; 5 La_len = ListLength(La); 6 Lb_len = ListLength(Lb); 7 while((i <= La_len) && (j <= Lb_len){ //La与Lb均非空 8 GetElem(La, i, ai); 9 GetElem(Lb, j, bj);10 if(ai <= bj) {ListInsert(Lc, ++k, ai); ++i; }11 else{ListInsert(Lc, ++k, bi); ++j;}12 }13 while(i <= La_len){ //La中剩余值插入Lc14 GetElem(La, i++, ai);15 ListInsert(Lc, ++k, ai);16 }17 while(j <= Lb_len){ //Lb中剩余值插入Lc18 GetElem(Lb, j++, bj);19 ListInsert(Lc, ++k, bj);20 }21 }分析：GetElem 和 ListInsert 这两个操作的执行时间和表长无关，所以该算法的事件复杂度为O(ListLength(LA) + ListLength(LB))。
线性表的顺序表示和实现：顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
所以可以用 LOC(ai) = LOC(a1) + (i-1) * l 来表示ai的地址（其中：l 表示每个元素所占存储单元）
优点：轻松实现随机存储。
顺序表的初始化、插入、删除、合并的伪代码如下：
1 // -------------线性表的动态分配顺序存储结构-------------- 2 #define LIST_INIT_SIZE 100 //线性表存储空间的初始化分配量 3 #define LISTINCREMENT 10 //线性表存储空间的分配增量 4 typedef struct{ 5 ElemType *elem; //存储空间基址 6 int length; //当前长度 7 int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) 8 }SqList; 9 10 //-----------初始化顺序表--------------11 Status InitList_Sq(SqList &L){12 //构造一个空的线性表13 L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));14 if(! L.elem) eixt(OVERFLOW); //存储分配失败15 L.length = 0; //空表长度为016 L.listsize = LIST_INIT_SIZE; //初始存储容量17 return OK;18 }19 20 //------------顺序表的插入算法-------------时间复杂度为O(n)21 Status ListInsert_Sq(SqList &L, int i, ElemType e) {22 //在顺序线性表L中第i个位置之前插入新的元素e23 //i的合法值为1<=i<=ListLength_Sq(L)+124 if((i<1) || (i>L.length+1)) return ERROR; //i值不合法25 if(L.length >= L.listsize){ //当前存储空间已满，增加分配26 newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemTpye));27 if(!newbase) exit(OVERFLOW); //存储分配失败28 L.elem = newbase; //新基址29 L.listsize += LISTINCREMENT; //增加存储容量30 }31 q = &(L.elem[i-1]); //q为插入位置32 for(p = &(L.elem[L.length-1]); p >= q; --p) 33 *(p+1) = *p; //插入位置及之后的元素右移34 *q = e; //插入e35 ++L.length; //表长增一36 return OK;37 }38 39 //-------------顺序表的删除操作--------------时间复杂度为O(n)40 Status ListDelete_Sq(SqList &L, int i, ElemType &e){41 //在顺序线性表L中删除第i个元素，并用e返回其值。42 if((i<1) || (i>L.length)) return ERROR; //i值不合法43 p = &(L.elem[i-1]); //p为被删除元素的位置44 e = *p; //被删除元素的值赋给e45 q = L.elem + L.length-1; //表尾元素的位置46 for(++p; p <= q; ++p){47 *(p-1) = *p; //被删除元素之后的元素左移48 }49 --L.length; //表长减150 return OK;51 }52 53 //-----------查找制定元素的位序---------------事件复杂度为O(n)54 int LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType)){55 //在顺序线性表L中查找第1个值与e满足compare()的元素的位序56 //若找到，则返回其在L中的位序，否则返回057 i = 1; //i的初值为第一个元素的位序58 p = L.elem; //p的初值为第一个元素的存储位置59 while(i <= L.length && !(* compare)(*p++, e)) ++i;60 if(i
C语言代码实现：
1 #include2 #include 3 #include 4 5 #define LIST_INIT_SIZE 100 //线性表存储空间初始分配量 6 #define LISTINCREMENT 10 //线性表存储空间的分配增量 7 8 typedef struct { 9 int *elem; //存储空间基址 10 int length; //当前长度 11 int listsize; //当前分配的存储空间容量（以sizeof(int)为单位 12 }SqList; 13 14 //初始化一个新表 15 void InitList_Sq(SqList *L){ 16 //构造一个空的线性表L 17 (*L).elem = (int *) malloc(LIST_INIT_SIZE*sizeof(int)); 18 if(!(*L).elem) exit(-1); //存储分配失败 19 (*L).length = 0; 20 (*L).listsize = LIST_INIT_SIZE; 21 } 22 23 //向表中第i个位置出插入一个数e 24 void ListInsert_Sq(SqList *L, int i, int e){ 25 if(i<1 || i>(*L).length+1) { 26 printf("插入时i值不合法...\n"); 27 exit(-1); 28 } 29 if((*L).length > (*L).listsize) { //当前存储空间已满，增加分配 30 int *newbase = (int *)realloc((*L).elem, ((*L).length+LISTINCREMENT)*sizeof(int)); 31 if(!newbase) exit(-1); 32 (*L).elem = newbase; 33 (*L).listsize += LISTINCREMENT; 34 } 35 int *q = &(*L).elem[i-1]; 36 for(int *p=&(*L).elem[(*L).length -1];p>=q;--p){ 37 *(p+1) = *p; 38 } 39 *q = e; 40 ++(*L).length; 41 } 42 43 //删除表中第i个位置的数并返回到e中 44 void ListDelete_Sq(SqList *L, int i, int *e){ 45 if(i<1 || i>(*L).length){ 46 printf("删除时i值不合法...\n"); 47 exit(-1); 48 } 49 int *p = &(*L).elem[i-1]; //要删除的元素 50 *e = *p; //被删除的元素赋值给e 51 int *q = &(*L).elem[(*L).length-1]; //表尾元素 52 for(++p;p<=q;p++){ //被删除元素之后的元素左移 53 *(p-1) = *p; 54 } 55 --(*L).length; 56 } 57 58 void MergeList_Sq(SqList La, SqList Lb, SqList *Lc){ 59 //已知顺序表La，Lb的元素按值非递减排列 60 //归并La，Lb得到新的顺序列表Lc，Lc的元素也按值非递减排列 61 int *pa = La.elem; 62 int *pb = Lb.elem; 63 (*Lc).listsize = (*Lc).length = La.length + Lb.length; 64 int *pc = (*Lc).elem = (int *)malloc((*Lc).listsize * sizeof(int)); 65 if(!(*Lc).elem){ 66 printf("内存分配失败...\n"); 67 exit(-1); 68 } 69 int *pa_last = La.elem + La.length -1; //La的表尾元素地址 70 int *pb_last = Lb.elem + Lb.length -1; //Lb的表尾元素地址 71 while(pa<=pa_last && pb<=pb_last){ 72 if(*pa <= *pb){ 73 *pc++ = *pa++; 74 }else{ 75 *pc++ = *pb++; 76 } 77 } 78 while(pa<=pa_last){ //插入La剩余的元素 79 *pc++ = *pa++; //插入Lb剩余的元素 80 } 81 while(pb <= pb_last){ 82 *pc++ = *pb++; 83 } 84 } 85 86 //查看顺序表中第一个的满足compare()的元素的位序 87 int LocateElem_Sq(SqList L, int e, int (* compare)(int x, int y)){ 88 int i = 1; 89 int *p = L.elem; 90 while(i <= L.length && !(*compare)(*p++, e)){ 91 ++i; 92 } 93 if(i <= L.length){ 94 return i; 95 }else{ 96 return 0; 97 } 98 } 99 100 int cmp(int x, int y){101 if(x == y){102 //printf("x=y\n");103 return 1;104 }else{105 //printf("x!=y\n");106 return 0;107 }108 }109 int main(){110 SqList La;111 SqList Lb;112 SqList Lc;113 int N,e;114 InitList_Sq(&La);115 printf("输入La元素的个数N：");116 scanf("%d",&N);117 printf("输入La的元素：");118 while(N--){119 scanf("%d",&e);120 int i =La.length+1;121 ListInsert_Sq(&La,i,e);122 }123 InitList_Sq(&Lb);124 printf("输入Lb元素的个数N：");125 scanf("%d",&N);126 printf("输入Lb的元素：");127 while(N--){128 scanf("%d",&e);129 int i =Lb.length+1;130 ListInsert_Sq(&Lb,i,e);131 }132 printf("此时La中的元素顺序表的值为：");133 for(int i=0;i
结果为：
