線性表(linear_list)是最常用且最簡單的一種數據結構，簡言之，一個線性表是n個數據元素的有序序列。

?

例如：（a₁?, ... ,?a_i-1 , a_i , a_i+1 , ... , a_n)：a_i-1?是 a_i 的直接前驅，a_i+1 是 a_i 的直接后驅。

并且，當 i = 1，2，... ，n-1：a_i 有且只有一個直接后驅。當 i = 2，3，... ，n：a_i 有且只有一個直接前驅

　　

例子：已知線性表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中剩余值插入Lc 14 GetElem(La, i++, ai); 15 ListInsert(Lc, ++k, ai); 16 } 17 while(j <= Lb_len){ //Lb中剩余值插入Lc 18 GetElem(Lb, j++, bj); 19 ListInsert(Lc, ++k, bj); 20 } 21 }

　　分析：GetElem 和 ListInsert 這兩個操作的執(zhí)行時間和表長無關，所以該算法的事件復雜度為O(ListLength(LA) + ListLength(LB))。

?

線性表的順序表示和實現：順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數據元素。

所以可以用 LOC(a_i) = LOC(a₁) + (i-1) * l ?來表示a_i的地址（其中：l 表示每個元素所占存儲單元）

優(yōu)點：輕松實現隨機存儲。

順序表的初始化、插入、刪除、合并的偽代碼如下：

?

1 // -------------線性表的動態(tài)分配順序存儲結構-------------- 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; //空表長度為0 16 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個位置之前插入新的元素e 23 //i的合法值為1<=i<=ListLength_Sq(L)+1 24 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; //插入e 35 ++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; //被刪除元素的值賦給e 45 q = L.elem + L.length-1; //表尾元素的位置 46 for(++p; p <= q; ++p){ 47 *(p-1) = *p; //被刪除元素之后的元素左移 48 } 49 --L.length; //表長減1 50 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中的位序，否則返回0 57 i = 1; //i的初值為第一個元素的位序 58 p = L.elem; //p的初值為第一個元素的存儲位置 59 while(i <= L.length && !(* compare)(*p++, e)) ++i; 60 if(i<L.length) return i; 61 else return 0; 62 } 63 64 //------------對于順序表的合并------------------時間復雜度為O(La.length + Lb.length) 65 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { 66 pa = La.elem; 67 pb = Lb.elem; 68 Lc.listsize = Lc.length = La.length + Lb.length; 69 pc = Lc.elem = (ElemType *) malloc (Lc.listsize*sizeof(ElemType)); 70 if(!Lc.elem) exit(OVERFLOW); //存儲分配失敗 71 pa_last = La.elem + La.length -1; 72 pb_last = Lb.elem + Lb.length -1; 73 while(pa <= pa_last && pb <= pb_last){ //歸并 74 if(*pa <= *pb) *pc++ = *pa++; 75 else *pc++ = *pb++; 76 } 77 while(pa <= pa_last) *pc++ = *pa++; 78 while(pb <= pb_last) *pc++ = *pa++; 79 }?

---

?

　　C語言代碼實現：

1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 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<La.length;i++){ 134 printf("%d ",La.elem[i]); 135 } 136 printf("\nLa.length = %d\tLa.listsize = %d\n",La.length,La.listsize); 137 printf("此時Lb中的元素順序表的值為："); 138 for(int i=0;i<Lb.length;i++){ 139 printf("%d ",Lb.elem[i]); 140 } 141 printf("\nLb.length = %d\tLb.listsize = %d\n",Lb.length,Lb.listsize); 142 ListDelete_Sq(&La,4,&e); 143 printf("刪除第四個元素后La的元素順序表的值為："); 144 for(int i=0;i<La.length;i++){ 145 printf("%d ",La.elem[i]); 146 } 147 printf("\nLa.length = %d\tLa.listsize = %d\te = %d\n",La.length,La.listsize,e); 148 MergeList_Sq(La, Lb, &Lc); 149 printf("La和Lb合并后得到Lc，其Lc的信息為：\n"); 150 printf("Lc的元素順序表為："); 151 for(int i=0;i<Lc.length;i++){ 152 printf("%d ",Lc.elem[i]); 153 } 154 printf("\nLc.length = %d\tLc.listsize = %d\n",Lc.length,Lc.listsize); 155 printf("輸入你要在Lc中查找的元素e："); 156 scanf("%d",&e); 157 printf("該元素e在Lc的位序位：%d\n",LocateElem_Sq(Lc, e, cmp)); 158　　　free(La.elem);free(Lb.elem);free(Lc.elem);return 0;
159 }

---

　　結果為：

　　

?

轉載于:https://www.cnblogs.com/TsnTse/p/9070013.html

總結

以上是生活随笔為你收集整理的【数据结构】线性表（一）：顺序列表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。