/* 順序表存儲結構容易實現隨機存取線性表的第i 個數據元素的操作，但在實現插入、 刪除的操作時要移動大量數據元素，所以，它適用于數據相對穩定的線性表，如職工工資 表、學生學籍表等。 c2-1.h 是動態分配的順序表存儲結構，bo2-1.cpp 是基于順序表的基本操作。由于 C++函數可重載，故去掉bo2-1.cpp 中算法2.3 等函數名中表示存儲類型的后綴_Sq。 c2-1.h 不采用固定數組作為線性表的存儲結構，而采用動態分配的存儲結構，這樣可以合 理地利用空間，使長表占用的存儲空間多， 短表占用的存儲空間少。這些可通過 bo2-1.cpp 中基本操作函數ListInsert()和圖24 清楚看出。 */
// c2-1.h 線性表的動態分配順序存儲結構(見圖2.1) #define LIST_INIT_SIZE 10 // 線性表存儲空間的初始分配量 #define LIST_INCREMENT 2 // 線性表存儲空間的分配增量 struct SqList { ElemType *elem; // 存儲空間基址 int length; // 當前長度 int listsize; // 當前分配的存儲容量(以sizeof(ElemType)為單位) };

// bo2-1.cpp 順序表示的線性表(存儲結構由c2-1.h定義)的基本操作(12個),包括算法2.3,2.4,2.5,2.6 void InitList(SqList &L) // 算法2.3 { // 操作結果：構造一個空的順序線性表L(見圖2.2) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); // 存儲分配失敗 L.length=0; // 空表長度為0 L.listsize=LIST_INIT_SIZE; // 初始存儲容量 } void DestroyList(SqList &L) { // 初始條件：順序線性表L已存在。操作結果：銷毀順序線性表L(見圖2.3) free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; } void ClearList(SqList &L) { // 初始條件：順序線性表L已存在。操作結果：將L重置為空表 L.length=0; } Status ListEmpty(SqList L) { // 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE；否則返回FALSE if(L.length==0) return TRUE; else return FALSE; } int ListLength(SqList L) { // 初始條件：順序線性表L已存在。操作結果：返回L中數據元素的個數 return L.length; } Status GetElem(SqList L,int i,ElemType &e) { // 初始條件：順序線性表L已存在,1≤i≤ListLength(L)。操作結果：用e返回L中第i個數據元素的值 if(i<1||i>L.length) return ERROR; e=*(L.elem+i-1); return OK; } int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)) { // 初始條件：順序線性表L已存在，compare()是數據元素判定函數(滿足為1，否則為0) // 操作結果：返回L中第1個與e滿足關系compare()的數據元素的位序。 // 若這樣的數據元素不存在，則返回值為0。算法2.6 ElemType *p; int i=1; // i的初值為第1個元素的位序 p=L.elem; // p的初值為第1個元素的存儲位置 while(i<=L.length&&!compare(*p++,e)) ++i; if(i<=L.length) return i; else return 0; } Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e) { // 初始條件：順序線性表L已存在 // 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅； // 否則操作失敗，pre_e無定義 int i=2; ElemType *p=L.elem+1; while(i<=L.length&&*p!=cur_e) { p++; i++; } if(i>L.length) return INFEASIBLE; // 操作失敗 else { pre_e=*--p; return OK; } } Status NextElem(SqList L,ElemType cur_e,ElemType &next_e) { // 初始條件：順序線性表L已存在 // 操作結果：若cur_e是L的數據元素，且不是最后一個，則用next_e返回它的后繼； // 否則操作失敗，next_e無定義 int i=1; ElemType *p=L.elem; while(i<L.length&&*p!=cur_e) { i++; p++; } if(i==L.length) return INFEASIBLE; // 操作失敗 else { next_e=*++p; return OK; } } Status ListInsert(SqList &L,int i,ElemType e) // 算法2.4 { // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)+1 // 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1(見圖2.4) ElemType *newbase,*q,*p; if(i<1||i>L.length+1) // i值不合法 return ERROR; if(L.length>=L.listsize) // 當前存儲空間已滿,增加分配 { if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType)))) exit(OVERFLOW); // 存儲分配失敗 L.elem=newbase; // 新基址 L.listsize+=LIST_INCREMENT; // 增加存儲容量 } q=L.elem+i-1; // q為插入位置 for(p=L.elem+L.length-1;p>=q;--p) // 插入位置及之后的元素右移 *(p+1)=*p; *q=e; // 插入e ++L.length; // 表長增1 return OK; } Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5 { // 初始條件：順序線性表L已存在，1≤i≤ListLength(L) // 操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1(見圖2.5) ElemType *p,*q; if(i<1||i>L.length) // i值不合法 return ERROR; p=L.elem+i-1; // p為被刪除元素的位置 e=*p; // 被刪除元素的值賦給e q=L.elem+L.length-1; // 表尾元素的位置 for(++p;p<=q;++p) // 被刪除元素之后的元素左移 *(p-1)=*p; L.length--; // 表長減1 return OK; } void ListTraverse(SqList L,void(*vi)(ElemType&)) { // 初始條件：順序線性表L已存在 // 操作結果：依次對L的每個數據元素調用函數vi() // vi()的形參加′&′，表明可通過調用vi()改變元素的值 ElemType *p; int i; p=L.elem; for(i=1;i<=L.length;i++) vi(*p++); printf("\n"); }

// func2-3.cpp 幾個常用的函數 Status equal(ElemType c1,ElemType c2) { // 判斷是否相等的函數 if(c1==c2) return TRUE; else return FALSE; } int comp(ElemType a,ElemType b) { // 根據a<、=或>b，分別返回-1、0或1 if(a==b) return 0; else return (a-b)/abs(a-b); } void print(ElemType c) { printf("%d ",c); } void print2(ElemType c) { printf("%c ",c); } void print1(ElemType &c) { printf("%d ",c); }
// main2-1.cpp 檢驗bo2-1.cpp的主程序 #include"c1.h" typedef int ElemType; #include"c2-1.h" #include"bo2-1.cpp" #include"func2-3.cpp" // 包括equal()、comp()、print()、print2()和print1()函數 Status sq(ElemType c1,ElemType c2) { // 數據元素判定函數(平方關系)，LocateElem()調用的函數 if(c1==c2*c2) return TRUE; else return FALSE; } void dbl(ElemType &c) { // ListTraverse()調用的另一函數(元素值加倍) c*=2; } void main() { SqList L; ElemType e,e0; Status i; int j,k; InitList(L); printf("初始化L后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize); for(j=1;j<=5;j++) i=ListInsert(L,1,j); printf("在L的表頭依次插入1～5后：*L.elem="); for(j=1;j<=5;j++) cout<<*(L.elem+j-1)<<""; cout<<endl; printf("L.elem=%u L.length=%d L.listsize=%d ",L.elem,L.length,L.listsize); i=ListEmpty(L); printf("L是否空：i=%d(1:是0:否)\n",i); ClearList(L); printf("清空L后：L.elem=%u L.length=%d L.listsize=%d ",L.elem,L.length,L.listsize); i=ListEmpty(L); printf("L是否空：i=%d(1:是0:否)\n",i); for(j=1;j<=10;j++) ListInsert(L,j,j); printf("在L的表尾依次插入1～10后：*L.elem="); for(j=1;j<=10;j++) cout<<*(L.elem+j-1)<<""; cout<<endl; printf("L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize); ListInsert(L,1,0); printf("在L的表頭插入0后：*L.elem="); for(j=1;j<=ListLength(L);j++) // ListLength(L)為元素個數 cout<<*(L.elem+j-1)<<""; cout<<endl; printf("L.elem=%u(有可能改變) L.length=%d(改變) L.listsize=%d(改變)\n",L.elem,L.length, L.listsize); GetElem(L,5,e); printf("第5個元素的值為%d\n",e); for(j=10;j<=11;j++) { k=LocateElem(L,j,equal); if(k) // k不為0，表明有符合條件的元素，且其位序為k printf("第%d個元素的值為%d\n",k,j); else printf("沒有值為%d的元素\n",j); } for(j=3;j<=4;j++) { k=LocateElem(L,j,sq); if(k) // k不為0，表明有符合條件的元素，且其位序為k printf("第%d個元素的值為%d的平方\n",k,j); else printf("沒有值為%d的平方的元素\n",j); } for(j=1;j<=2;j++) // 測試頭兩個數據 { GetElem(L,j,e0); // 把第j個數據賦給e0 i=PriorElem(L,e0,e); // 求e0的前驅 if(i==INFEASIBLE) printf("元素%d無前驅\n",e0); else printf("元素%d的前驅為%d\n",e0,e); } for(j=ListLength(L)-1;j<=ListLength(L);j++) // 最后兩個數據 { GetElem(L,j,e0); // 把第j個數據賦給e0 i=NextElem(L,e0,e); // 求e0的后繼 if(i==INFEASIBLE) printf("元素%d無后繼\n",e0); else printf("元素%d的后繼為%d\n",e0,e); } k=ListLength(L); // k為表長 for(j=k+1;j>=k;j--) { i=ListDelete(L,j,e); // 刪除第j個數據 if(i==ERROR) printf("刪除第%d個元素失敗\n",j); else printf("刪除第%d個元素成功，其值為%d\n",j,e); } printf("依次輸出L的元素："); ListTraverse(L,print1); // 依次對元素調用print1()，輸出元素的值 printf("L的元素值加倍后："); ListTraverse(L,dbl); // 依次對元素調用dbl()，元素值乘2 ListTraverse(L,print1); DestroyList(L); printf("銷毀L后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize); }
以下是運行的結果代碼：

/* 初始化L后：L.elem=3615192 L.length=0 L.listsize=10 在L的表頭依次插入1～5后：*L.elem=54321 L.elem=3615192 L.length=5 L.listsize=10 L是否空：i=0(1:是0:否) 清空L后：L.elem=3615192 L.length=0 L.listsize=10 L是否空：i=1(1:是0:否) 在L的表尾依次插入1～10后：*L.elem=12345678910 L.elem=3615192 L.length=10 L.listsize=10 在L的表頭插入0后：*L.elem=012345678910 L.elem=3606792(有可能改變) L.length=11(改變) L.listsize=12(改變) 第5個元素的值為4 第11個元素的值為10 沒有值為11的元素 第10個元素的值為3的平方 沒有值為4的平方的元素 元素0無前驅 元素1的前驅為0 元素9的后繼為10 元素10無后繼 刪除第12個元素失敗 刪除第11個元素成功，其值為10 依次輸出L的元素：0 1 2 3 4 5 6 7 8 9 L的元素值加倍后： 0 2 4 6 8 10 12 14 16 18 銷毀L后：L.elem=0 L.length=0 L.listsize=0 */

轉載于:https://www.cnblogs.com/KongkOngL/p/3923439.html

總結

以上是生活随笔為你收集整理的线性表的顺序表示和实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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