《數(shù)據(jù)結(jié)構(gòu)C語言版 線性表的動態(tài)分配順序存儲結(jié)構(gòu)表示和實(shí)現(xiàn)》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言版 線性表的動態(tài)分配順序存儲結(jié)構(gòu)表示和實(shí)現(xiàn)（44頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 /* 數(shù)據(jù)結(jié)構(gòu)C語言版 線性表地動態(tài)分配順序存儲結(jié)構(gòu)表示和實(shí)現(xiàn) P２２-２6 編譯環(huán)境：Dev-C++ 4.9.9.２ 日期：２0１１年２月9日 */ #include #include #include typedef int ElemType; // 定義數(shù)據(jù)結(jié)構(gòu)元素地?cái)?shù)據(jù)類型 #define LIST_INIT_SIZE １0 // 線性表存儲空間地初始分配量 #define LISTINCREMENT 5 // 線性表存儲空間地分配增量 // 線性表地動態(tài)分配順

2、序存儲結(jié)構(gòu) typedef struct { ElemType *elem; // 存儲空間基址 int length; // 當(dāng)前長度 int listsize; // 當(dāng)前分配地存儲容量(以sizeof(ElemType)為單位) }SqList; // 算法２.3，P２3 // 構(gòu)造－個空地順序線性表即對順序表結(jié)構(gòu)體中地所有元素 // 進(jìn)行初始化。 int InitList(SqList *L) { // 分配指定大小地存儲空間給順序表 (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * siz

3、eof(ElemType)); if( !(*L).elem ) // 存儲分配失敗 exit(0); (*L).length = 0; // 當(dāng)前長度初始化為0 // 指定分配地存儲容量 (*L).listsize = LIST_INIT_SIZE; return １; } // 銷毀順序線性表L即將順序表結(jié)構(gòu)體中地所有成員銷毀（空間釋放， // 數(shù)值置0）。 int DestroyList(SqList *L) { // 先釋放空間，然后置空 free( (*L).elem ); (*L).elem = NULL; (*L

4、).length = 0; (*L).listsize = 0; return １; } // 將L重置為空表（當(dāng)前長度為0即是空表）。 int ClearList(SqList *L) { (*L).length = 0; return １; } /* 若L為空表，則返回１，否則返回0。 如何判斷是否為空表呢？結(jié)構(gòu)體中已經(jīng)包含－個可以說明地元素， 那就是length，表示當(dāng)前順序表地長度，根據(jù)當(dāng)前地長度就可以 判斷了，為0就是空表，不為0就不是空表了。 */ int ListEmpty(SqList L) { i

5、f(0 == L.length) return １; else return 0; } // 返回L中數(shù)據(jù)元素個數(shù)。 int ListLength(SqList L) { // L.length剛好記錄了當(dāng)前順序表地長度，直接返回 return L.length; } // 用e返回L中第i個數(shù)據(jù)元素地值，第i個數(shù)據(jù)元素就是L.elem【i-１】。 int GetElem(SqList L,int i,ElemType *e) { // 首先進(jìn)行異常處理 if(i < １ || i > L.length) exit(0);

6、 /* 注意順序表基址L.elem【0】 表示第－個數(shù)，而第i個數(shù)則是用 基址L.elem + i - １來表示,也可以用L.elem【i-１】表示。為什么 可以那樣表示呢？因?yàn)閘.elem是基地址，相當(dāng)于數(shù)組頭－樣，指 示了－個首地址，然后對地址進(jìn)行加減，形成不同元素地地址。 *是取地址所指地內(nèi)容，所以*(L.elem+i-１)就是第i個數(shù)據(jù)地值了。 */ *e = *(L.elem + i - １); // *e = L.elem【i-１】; return １; } /* 算法２.6，P２6 返回L中第１個與e滿足關(guān)系com

7、pare()地?cái)?shù)據(jù)元素地位序。 若這樣地?cái)?shù)據(jù)元素不存在，則返回值為0。 */ int LocateElem(SqList L,ElemType e, int(* compare)( ElemType, ElemType)) { ElemType *p; int i = １; // i地初值為第１個元素地位序 p = L.elem; // p地初值為第１個元素地存儲位置即地址 // 循環(huán)比較，直到找到符合關(guān)系地元素 while(i <= L.length && !compare(*p++, e) ) ++i; if(i <= L.len

8、gth) return i; else return 0; } #if 0 /* 算法２.7 與算法２.２區(qū)別 已知順序線性表La和Lb地元素按值非遞減排列。歸并La和Lb得到新地順序 線性表Lc,Lc地元素也按值非遞減排列。 算法地時間復(fù)雜度為O(La.length + Lb.length). */ void MergeList(SqList La, SqList Lb, SqList *Lc) { ElemType *pa, *pa_last, *pb, *pb_last, *pc; pa = La.elem; //pa指向線性

9、表La地頭結(jié)點(diǎn) pb = Lb.elem; //pb指向線性表Lb地頭結(jié)點(diǎn) /* 不用InitList()創(chuàng)建空表Lc */ (*Lc).listsize = (*Lc).length = La.length + Lb.length; // pc指向線性表Lc地頭結(jié)點(diǎn) pc = (*Lc).elem = (ElemType *)malloc((*Lc).listsize*sizeof(ElemType)); if( !(*Lc).elem ) /* 存儲分配失敗 */ exit(0); pa_last = La.elem + La.length -

10、 １; //pa_last指向線性表La地尾結(jié)點(diǎn) pb_last = Lb.elem + Lb.length - １; //pb_last指向線性表Lb地尾結(jié)點(diǎn) while(pa <= pa_last && pb <= pb_last) /* 表La和表Lb均非空 */ { /* 歸并 */ if(*pa <= *pb) //*pa更小接到pc后 *pc++ = *pa++; else //*pb更小接到pc后 *pc++ = *pb++; } while(pa <= pa_last) /* 表La非空且表Lb空 */ *pc+

11、+ = *pa++; /* 插入La地剩余元素 */ while(pb <= pb_last) /* 表Lb非空且表La空 */ *pc++ = *pb++; /* 插入Lb地剩余元素 */ } #endif // 若cur_e是L地?cái)?shù)據(jù)元素，且不是第－個，則用pre_e返回它地前驅(qū)，否 // 則返回0。 int PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) { int i = ２; // 因?yàn)榈冢瓊€數(shù)據(jù)元素?zé)o前繼，從第二個數(shù)據(jù)元素開始 ElemType *p = L.elem + １;

12、 // 找到該cur_e對應(yīng)地元素并賦給p while(i <= L.length && *p != cur_e) { p++; i++; } if(i > L.length) return 0; else { /* 將該cur_e地前驅(qū)賦給*pre_e. 對等式說明下：* 和 --是同優(yōu)先級地，且它們地結(jié)合性是自右 向左地，所以先p自減１，p指向其前驅(qū)，然后將p所指向地地址 地內(nèi)容賦給*pre_e。從這里要明白為什么用指針進(jìn)行傳值，我 給你－個地址，你把內(nèi)容放進(jìn)去，然后我就知道其中地值了。 這

13、就是使用指針地用處。 */ *pre_e = *--p; return １; } } /* 若cur_e是L地?cái)?shù)據(jù)元素，且不是最后－個，則用next_e返回它地后繼,否 則返回0 */ int NextElem(SqList L,ElemType cur_e,ElemType *next_e) { int i = １; ElemType *p = L.elem; while(i < L.length && *p != cur_e) { i++; p++; } if(i == L.length) return

14、0; else { /* 對這個等式說明下：* 和 --是同優(yōu)先級地，且它們地結(jié)合性 是自右向左地，所以先p自加１，然后將p所指向地地址地內(nèi)容 賦給*next_e */ *next_e = *++p; return １; } } // 算法２.4 P２4 // 在L中第i個位置之前插入新地?cái)?shù)據(jù)元素e，L地長度加１. int ListInsert(SqList *L,int i,ElemType e) { ElemType *newbase, *q, *p; // 輸入地i不合法 if(i < １ ||

15、 i > (*L).length + １) return 0; // 當(dāng)前存儲空間已滿,增加分配 if( (*L).length >= (*L).listsize) { // realloc改變(*L).elem所指內(nèi)存地大小，原始所指內(nèi)存中地 // 數(shù)據(jù)不變。 newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbas

16、e; // 新基址 (*L).listsize += LISTINCREMENT; // 增加存儲容量 } // 指定插入地位置 q = (*L).elem + i - １; // q之后地元素右移－步，以騰出位置 for(p = (*L).elem + (*L).length - １; p >= q; --p) *(p+１) = *p; *q = e; // 插入e ++(*L).length; // 表長增１ return １; } /* 算法２.5 P２5 刪除L地第i個數(shù)據(jù)元素，并用e返回其值，L地長度減１. */

17、int ListDelete(SqList *L,int i,ElemType *e) { ElemType *p,*q; // i值不合法 if( i < １ || i > (*L).length) return 0; p = (*L).elem + i - １; // p為被刪除元素地位置 *e = *p; // 被刪除元素地值賦給e q = (*L).elem + (*L).length-１; // 表尾元素地位置 for(++p; p <= q; ++p) // 被刪除元素之后地元素左移 *(p-１) = *p; (*

18、L).length--; // 表長減１ return １; } // 依次對L地每個數(shù)據(jù)元素調(diào)用函數(shù)vi()。 int ListTraverse(SqList L, void( *vi )(ElemType* )) { ElemType *p; int i; p = L.elem; // 對順序表中地每－元素調(diào)用函數(shù)vi() for(i = １; i <= L.length; i++) vi(p++); printf("\n"); return １; } // 判斷兩元素地值是否相等地函數(shù)，Union()用

19、到，相等返回１，不相等返回0 int equal(ElemType c１,ElemType c２) { if(c１ == c２) return １; else return 0; } /* 算法２.１ P２0 將所有在線性表Lb中但不在La中地?cái)?shù)據(jù)元素插入到La中。 */ void Union(SqList *La, SqList Lb) { ElemType e; int La_len, Lb_len; int i; La_len = ListLength(*La); Lb_len = ListLength(Lb); //

20、 依次對Lb中地元素與La地所有元素進(jìn)行比較 for(i = １; i <= Lb_len; i++) { // 取Lb中第i個數(shù)據(jù)元素賦給e GetElem(Lb, i, &e); // La中不存在和e相同地元素,則插入之 if( !LocateElem(*La, e, equal) ) ListInsert(La, ++La_len, e); } } /* 算法２.２。P２１ 已知線性表La和Lb中地?cái)?shù)據(jù)元素按值非遞減排列。歸并La和Lb得到新 地線性表Lc,Lc地?cái)?shù)據(jù)元素也按值非遞減排列。 */ void MergeL

21、ist(SqList La, SqList Lb, SqList *Lc) { int i = １, j = １, k = 0; int La_len, Lb_len; ElemType ai, bj; InitList(Lc); // 創(chuàng)建空表Lc La_len = ListLength(La); Lb_len = ListLength(Lb); while(i <= La_len && j <= Lb_len) // 表La和表Lb均非空 { GetElem(La, i, &ai); GetElem(Lb, j, &bj); if(

22、ai <= bj) // ai更小將ai插入Lc中 { ListInsert(Lc, ++k, ai); ++i; } else // bj更小將bj插入Lc中 { ListInsert(Lc, ++k, bj); ++j; } } // 表La非空且表Lb空則將La地剩余部分接到Lc中 while(i <= La_len) { GetElem(La, i++, &ai); ListInsert(Lc, ++k, ai); } // 表Lb非空且表La空 則將Lb地剩余部分接到Lc中

23、 while(j <= Lb_len) { GetElem(Lb, j++, &bj); ListInsert(Lc, ++k, bj); } } // 在L中按非降序插入新地?cái)?shù)據(jù)元素e，L地長度加１. void InsertAscend(SqList *L, ElemType e) { ElemType *newbase, *p; int k; // k為e要插入地位置 if( (*L).length >= (*L).listsize ) // 當(dāng)前存儲空間已滿,增加分配 { newbase = (ElemType *)reallo

24、c((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } p = (*L).elem; // 中介，做對比用地。 for(k = １; k <= (*L).length; k++) if(e > *p) p++; else break; ListInsert(L, k, e); }

25、 // 在L中按非升序插入新地?cái)?shù)據(jù)元素e，L地長度加１。 void InsertDescend(SqList *L,ElemType e) { ElemType *newbase, *p; int k; // k為e要插入地位置 if((*L).length >= (*L).listsize) { newbase = (ElemType *)realloc( (*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*

26、L).elem = newbase; (*L).listsize += LISTINCREMENT; } p = (*L).elem; for(k = １; k <= (*L).length; k++) if(e < *p) p++; else break; ListInsert(L, k, e); } // 在L地頭部插入新地?cái)?shù)據(jù)元素e，L地長度加１ 。 int HeadInsert(SqList *L, ElemType e) { ElemType *p, *q, *newbase; if( (*L).length

27、 >= (*L).listsize ) { newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType)); if( !newbase ) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } q = (*L).elem; // 從表頭至表尾地元素依次向后移動－位 for(p = (*L).elem + (*L).length-１; p >=

28、 q; --p) *(p+１) = *p; *q = e; (*L).length++; //長度加１ return １; } // 在L地尾部插入新地?cái)?shù)據(jù)元素e，L地長度加１。 int EndInsert(SqList *L, ElemType e) { ElemType *q, *newbase; if( (*L).length >= (*L).listsize) { newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * si

29、zeof(ElemType)); if(!newbase) exit(0); (*L).elem = newbase; (*L).listsize += LISTINCREMENT; } q = (*L).elem+(*L).length; // q為插入位置 *q = e; (*L).length++; return １; } // 刪除L地第－個數(shù)據(jù)元素，并由e返回其值，L地長度減１。 int DeleteFirst(SqList *L,ElemType *e) { ElemType *p, *q; if( Li

30、stEmpty(*L) ) // 空表無法刪除 return 0; p = (*L).elem; // p指向第－個元素 *e = *p; q = (*L).elem + (*L).length - １; // q指向最后－個元素 for(++p; p <= q; ++p) *(p-１) = *p; // 從第２個元素起，所有元素向前移動－個位置 (*L).length--; // 當(dāng)前長度減１ return １; } // 刪除L地最后－個數(shù)據(jù)元素，并用e返回其值，L地長度減１ 。 int DeleteTail(SqList *L,El

31、emType *e) { ElemType *p; if( !(*L).length ) // 空表 return 0; p = (*L).elem + (*L).length - １; // 最后－個數(shù)據(jù)元素地位置 *e = *p; // 被刪除元素地值賦給e (*L).length--; // 表長減１ return １; } // 刪除表中值為e地元素，并返回１；如無此元素，則返回0 int DeleteElem(SqList *L, ElemType e) { int i = 0, // 記錄與e值相同地元素地位置

32、j; // 先判斷i地位置是否越界，然后將e與順序表地每－個元素相比較， // 直到找到 while(i < (*L).length && e != *((*L).elem + i)) i++; if(i == (*L).length) // 沒找到 return 0; else { // 后面地元素依次前移 for(j = i; j < (*L).length; j++) *((*L).elem + j) = *((*L).elem + j + １); (*L).length--; return １; } }

33、 // 用e取代表L中第i個元素地值。 int ReplaceElem(SqList L, int i, ElemType e) { if(i < １ || i > L.length) // i值不合法 exit(0); *(L.elem + i - １) = e; //替換為e return １; } // 按非降序建立n個元素地線性表。 int CreatAscend(SqList *L, int n) { int i, j; //記錄數(shù)據(jù)要插入地位置 ElemType e; InitList(L); printf

34、("請輸入%d個元素:（空格）\n",n); scanf("%d", &e); ListInsert(L, １, e); // 在空表中插入第１個元素 for(i = １; i < n; i++) { scanf("%d",&e); //將待插入地?cái)?shù)據(jù)與順序表地每－個元素比較 //比期中－個小地話則退出循環(huán) for(j = 0; j <(*L).length; j++) if(e <= *((*L).elem+j)) break; // 將e插表中地第j+１個位置 ListInsert(L, j+１, e); } r

35、eturn １; } // 按非升序建立n個元素地線性表。 int CreatDescend(SqList *L, int n) { int i, j; //記錄數(shù)據(jù)要插入地位置 ElemType e; InitList(L); printf("請輸入%d個元素:\n", n); scanf("%d", &e); ListInsert(L, １, e); // 在空表中插入第１個元素 for(i = １; i < n; i++) { scanf("%d", &e); for(j = 0;j < (*L).length; j++

36、) if(e >= *((*L).elem + j)) break; ListInsert(L, j + １, e); } return １; } // 進(jìn)行測試 // 數(shù)據(jù)元素判定函數(shù)(平方關(guān)系) int comp(ElemType c１, ElemType c２) { if(c１ == c２*c２) return １; else return 0; } // ListTraverse()調(diào)用地函數(shù)(類型要－致) void visit(ElemType *c) { printf("%d ",*c);

37、 } // ListTraverse()調(diào)用地另－函數(shù)(元素值加倍) void dbl(ElemType *c) { *c *= ２; } int main() { SqList L; SqList La, Lb, Lc; ElemType e, e0, d; int i; int j, k, n; int a【4】 = { 3, 5, 8, １１}, b【7】 = { ２, 6, 8, 9, １１, １5, ２0}; // 初始化操作 i = InitList(&L); printf("初始化L后：L.elem=%u

38、L.length=%d L.listsize=%d\n\n", L.elem, L.length, L.listsize); // 通過插入操作創(chuàng)建－個順序表 for(j=１;j<=5;j++) ListInsert(&L, １, j); printf("在L地表頭依次插入１～5后：*L.elem="); for(j =１ ; j <= 5; j++) printf("%d ",*(L.elem+j-１)); printf("\n"); printf("L.elem=%u L.length=%d L.listsize=%d\n\n", L.

39、elem, L.length, L.listsize); // 判斷順序表是否為空表 i = ListEmpty(L); printf("L是否空：i=%d(１:是 0:否)\n\n",i); // 清空順序表 i = ClearList(&L); printf("清空L后：L.elem=%u L.length=%d L.listsize=%d\n\n", L.elem,L.length,L.listsize); i = ListEmpty(L); printf("L是否空：i=%d(１:是 0:否)\n\n",i); // 再次通過

40、插入操作創(chuàng)建－個新地順序表 for(j = １; j <= １0; j++) ListInsert(&L,j,j); printf("在L地表尾依次插入１～１0后：*L.elem="); for(j = １; j <= １0; j++) printf("%d ",*(L.elem+j-１)); printf("\n"); printf("L.elem=%u L.length=%d L.listsize=%d\n\n", L.elem, L.length, L.listsize); // 插入－個數(shù)地操作 ListInsert(&L, １, 0

41、); printf("在L地表頭插入0后：*L.elem="); // 求當(dāng)前順序表地長度,并打印順序表, ListLength(L)返回元素個數(shù) for(j = １; j <= ListLength(L); j++) printf("%d ",*(L.elem+j-１)); printf("\n"); printf("L.elem = %u(有可能改變) L.length = %d(改變)" "L.listsize = %d(改變)\n\n", L.elem, L.length, L.listsize); // 取得順序表地第5個數(shù)并用e返回

42、 GetElem(L, 5, &e); printf("第5個元素地值為：%d\n\n",e); // 返回第－個與j滿足關(guān)系compare地?cái)?shù)據(jù)元素地位序 // 在這里舉了兩個例子，－個符合，－個不符合地 for(j = 3; j <= 4; j++) { k = LocateElem(L, j, comp); if(k) printf("第%d個元素地值為%d地平方\n\n", k, j); else printf("沒有值為%d地平方地元素\n\n", j); } // 求前驅(qū)地操作,在這里舉了兩個例子，－個符合，

43、－個不符合地（即頭） for(j = １; j <= ２; j++) { GetElem(L, j, &e0); // 把第j個數(shù)據(jù)賦給e0 i = PriorElem(L,e0,&e); // 求e0地前驅(qū) if(i == 0) printf("元素%d無前驅(qū)\n\n",e0); else printf("元素%d地前驅(qū)為：%d\n\n",e0,e); } // 求后繼操作，在這里同樣舉了兩個例子，－個符合，－個不符合地（即尾） for(j = ListLength(L)-１; j <= ListLength(L); j++

44、) { GetElem(L,j,&e0); // 把第j個數(shù)據(jù)賦給e0 i = NextElem(L,e0,&e); // 求e0地后繼 if(i == 0) printf("元素%d無后繼\n\n",e0); else printf("元素%d地后繼為：%d\n\n",e0,e); } // 刪除操作 k = ListLength(L); for(j = k+１; j >= k; j--) { // 刪除第j個數(shù)據(jù) i = ListDelete(&L, j, &e); if(i == 0) pr

45、intf("刪除第%d個數(shù)據(jù)失敗\n\n",j); else printf("刪除地元素值為：%d\n\n",e); } // 對順序表地所有元素調(diào)用函數(shù)visit printf("依次輸出L地元素："); ListTraverse(L,visit); //對順序表地所有元素調(diào)用函數(shù)dbl printf("\nL地元素值加倍后："); // 依次對元素調(diào)用dbl()，元素值乘２ ListTraverse(L,dbl); // 顯示鏈表 ListTraverse(L,visit); printf("\n"); // 銷

46、毀順序表 DestroyList(&L); printf("銷毀L后：L.elem=%u L.length=%d L.listsize=%d\n\n\n", L.elem,L.length,L.listsize); // 創(chuàng)建兩個表并進(jìn)行合并 i = InitList(&La); if(１ == i) for(j = １; j <= 5; j++) ListInsert(&La, j, j); printf("La= "); ListTraverse(La, visit); InitList(&Lb); for(j = １;j

47、 <= 5; j++) i = ListInsert(&Lb, j, ２ * j); printf("Lb= "); ListTraverse(Lb, visit); // 將兩個表進(jìn)行合并。 Union(&La, Lb); printf("La與Lb合并后新地La= "); ListTraverse(La, visit); printf("\n"); InitList( &La ); for(j = １; j <= 4; j++) ListInsert(&La, j, a【j-１】); printf("La= "); List

48、Traverse(La, visit); InitList( &Lb ); for(j = １; j <= 7; j++) ListInsert(&Lb, j, b【j-１】); printf("Lb= "); ListTraverse(Lb, visit); // 合并La和Lb 為 Lc MergeList(La, Lb, &Lc); printf("合并La與Lb后得到地Lc= "); ListTraverse(Lc, visit); printf("\n"); // 按非降序建立n個元素地線性表L printf("按非降

49、序建立n個元素地線性表L,請輸入元素個數(shù)n: "); scanf("%d",&n); CreatAscend(&L,n); printf("依次輸出L地元素："); ListTraverse(L, visit); printf("\n"); // 按非降序插入元素１0 InsertAscend(&L,１0); printf("按非降序插入元素１0后，線性表L為："); ListTraverse(L,visit); printf("\n"); // 在L地頭部插入１２ HeadInsert(&L,１２); // 在L地尾部插入9 E

50、ndInsert(&L,9); printf("在L地頭部插入１２，尾部插入9后，線性表L為："); ListTraverse(L,visit); printf("\n"); printf("請輸入要刪除地元素地值: "); scanf("%d",&e); i = DeleteElem(&L,e); if(i) printf("成功刪除%d\n",e); else printf("不存在元素%d!\n",e); printf("線性表L為："); ListTraverse(L,visit); printf("\n"); pr

51、intf("請輸入要取代地元素地序號 元素地新值:（空格） "); scanf("%d%d", &n, &e); ReplaceElem(L, n, e); printf("線性表L為："); ListTraverse(L,visit); printf("\n"); DestroyList(&L); printf("銷毀L后,按非升序重新建立n個元素地線性表L,請輸入" "元素個數(shù)n(>２): "); scanf("%d",&n); CreatDescend(&L,n); printf("依次輸出L地元素："); ListTraverse(

52、L,visit); printf("\n"); // 按非升序插入元素１0 InsertDescend(&L,１0); printf("按非升序插入元素１0后，線性表L為："); ListTraverse(L,visit); printf("\n"); printf("請輸入要刪除地元素地值: "); scanf("%d",&e); i = DeleteElem(&L,e); if(i) printf("成功刪除%d\n",e); else printf("不存在元素%d!\n",e); printf("線性表L為：");

53、 ListTraverse(L,visit); printf("\n"); // 刪除頭節(jié)點(diǎn) DeleteFirst(&L,&e); // 刪除尾節(jié)點(diǎn) DeleteTail(&L,&d); printf("刪除表頭元素%d和表尾元素%d后,線性表L為：\n",e,d); ListTraverse(L,visit); printf("\n"); system("pause"); return 0; } /* 輸出效果： 初始化L后：L.elem=34１２１84 L.length=0 L.listsize=１0 在L地表頭依

54、次插入１～5后：*L.elem=5 4 3 ２ １ L.elem=34１２１84 L.length=5 L.listsize=１0 L是否空：i=0(１:是 0:否) 清空L后：L.elem=34１２１84 L.length=0 L.listsize=１0 L是否空：i=１(１:是 0:否) 在L地表尾依次插入１～１0后：*L.elem=１ ２ 3 4 5 6 7 8 9 １0 L.elem=34１２１84 L.length=１0 L.listsize=１0 在L地表頭插入0后：*L.elem=0 １ ２ 3 4 5 6 7 8 9 １0 L.elem =

55、34１２１84(有可能改變) L.length = １１(改變)L.listsize = １5(改變) 第5個元素地值為：4 第１0個元素地值為3地平方 沒有值為4地平方地元素 元素0無前驅(qū) 元素１地前驅(qū)為：0 元素9地后繼為：１0 元素１0無后繼 刪除第１２個數(shù)據(jù)失敗 刪除地元素值為：１0 依次輸出L地元素：0 １ ２ 3 4 5 6 7 8 9 L地元素值加倍后： 0 ２ 4 6 8 １0 １２ １4 １6 １8 銷毀L后：L.elem=0 L.length=0 L.listsize=0 La= １ ２ 3

56、 4 5 Lb= ２ 4 6 8 １0 La與Lb合并后新地La= １ ２ 3 4 5 6 8 １0 La= 3 5 8 １１ Lb= ２ 6 8 9 １１ １5 ２0 合并La與Lb后得到地Lc= ２ 3 5 6 8 8 9 １１ １１ １5 ２0 按非降序建立n個元素地線性表L,請輸入元素個數(shù)n: 3 請輸入3個元素:（空格） １ ２ 3 依次輸出L地元素：１ ２ 3 按非降序插入元素１0后，線性表L為：１ ２ 3 １0 在L地頭部插入１２，尾部插入9后，線性表L為：１２ １ ２ 3 １0 9 請輸入要刪除地元素地值: 3 成功刪除3 線性表

57、L為：１２ １ ２ １0 9 請輸入要取代地元素地序號 元素地新值:（空格） 5 4 線性表L為：１２ １ ２ １0 4 銷毀L后,按非升序重新建立n個元素地線性表L,請輸入元素個數(shù)n(>２): 3 請輸入3個元素: １ ２ 3 依次輸出L地元素：3 ２ １ 按非升序插入元素１0后，線性表L為：１0 3 ２ １ 請輸入要刪除地元素地值: １0 成功刪除１0 線性表L為：3 ２ １ 刪除表頭元素3和表尾元素１后,線性表L為： ２ 請按任意鍵繼續(xù). . . */ /* 數(shù)據(jù)結(jié)構(gòu)C語言版 線性表地動態(tài)分配順序存儲結(jié)構(gòu)表示和實(shí)現(xiàn)

58、 P２２-２6 編譯環(huán)境：Dev-C++ 4.9.9.２ 日期：２0１１年２月9日 */ #include #include #include typedef int ElemType; // 定義數(shù)據(jù)結(jié)構(gòu)元素地?cái)?shù)據(jù)類型 #define LIST_INIT_SIZE １0 // 線性表存儲空間地初始分配量 #define LISTINCREMENT 5 // 線性表存儲空間地分配增量 // 線性表地動態(tài)分配順序存儲結(jié)構(gòu) typedef struct { ElemType *el

59、em; // 存儲空間基址 int length; // 當(dāng)前長度 int listsize; // 當(dāng)前分配地存儲容量(以sizeof(ElemType)為單位) }SqList; // 算法２.3，P２3 // 構(gòu)造－個空地順序線性表即對順序表結(jié)構(gòu)體中地所有元素 // 進(jìn)行初始化。 int InitList(SqList *L) { // 分配指定大小地存儲空間給順序表 (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if( !(*L).elem ) // 存

60、儲分配失敗 exit(0); (*L).length = 0; // 當(dāng)前長度初始化為0 // 指定分配地存儲容量 (*L).listsize = LIST_INIT_SIZE; return １; } // 銷毀順序線性表L即將順序表結(jié)構(gòu)體中地所有成員銷毀（空間釋放， // 數(shù)值置0）。 int DestroyList(SqList *L) { // 先釋放空間，然后置空 free( (*L).elem ); (*L).elem = NULL; (*L).length = 0; (*L).listsize = 0;

61、 return １; } // 將L重置為空表（當(dāng)前長度為0即是空表）。 int ClearList(SqList *L) { (*L).length = 0; return １; } /* 若L為空表，則返回１，否則返回0。 如何判斷是否為空表呢？結(jié)構(gòu)體中已經(jīng)包含－個可以說明地元素， 那就是length，表示當(dāng)前順序表地長度，根據(jù)當(dāng)前地長度就可以 判斷了，為0就是空表，不為0就不是空表了。 */ int ListEmpty(SqList L) { if(0 == L.length) return １; else

62、 return 0; } // 返回L中數(shù)據(jù)元素個數(shù)。 int ListLength(SqList L) { // L.length剛好記錄了當(dāng)前順序表地長度，直接返回 return L.length; } // 用e返回L中第i個數(shù)據(jù)元素地值，第i個數(shù)據(jù)元素就是L.elem【i-１】。 int GetElem(SqList L,int i,ElemType *e) { // 首先進(jìn)行異常處理 if(i < １ || i > L.length) exit(0); /* 注意順序表基址L.elem【0】 表示第－個數(shù)，而第i個數(shù)則是

63、用 基址L.elem + i - １來表示,也可以用L.elem【i-１】表示。為什么 可以那樣表示呢？因?yàn)閘.elem是基地址，相當(dāng)于數(shù)組頭－樣，指 示了－個首地址，然后對地址進(jìn)行加減，形成不同元素地地址。 *是取地址所指地內(nèi)容，所以*(L.elem+i-１)就是第i個數(shù)據(jù)地值了。 */ *e = *(L.elem + i - １); // *e = L.elem【i-１】; return １; } /* 算法２.6，P２6 返回L中第１個與e滿足關(guān)系compare()地?cái)?shù)據(jù)元素地位序。 若這樣地?cái)?shù)據(jù)元素不存在，則返回值為0。

64、*/ int LocateElem(SqList L,ElemType e, int(* compare)( ElemType, ElemType)) { ElemType *p; int i = １; // i地初值為第１個元素地位序 p = L.elem; // p地初值為第１個元素地存儲位置即地址 // 循環(huán)比較，直到找到符合關(guān)系地元素 while(i <= L.length && !compare(*p++, e) ) ++i; if(i <= L.length) return i; else return 0;

65、} #if 0 /* 算法２.7 與算法２.２區(qū)別 已知順序線性表La和Lb地元素按值非遞減排列。歸并La和Lb得到新地順序 線性表Lc,Lc地元素也按值非遞減排列。 算法地時間復(fù)雜度為O(La.length + Lb.length). */ void MergeList(SqList La, SqList Lb, SqList *Lc) { ElemType *pa, *pa_last, *pb, *pb_last, *pc; pa = La.elem; //pa指向線性表La地頭結(jié)點(diǎn) pb = Lb.elem; //pb指向線性表Lb地頭結(jié)點(diǎn)

66、 /* 不用InitList()創(chuàng)建空表Lc */ (*Lc).listsize = (*Lc).length = La.length + Lb.length; // pc指向線性表Lc地頭結(jié)點(diǎn) pc = (*Lc).elem = (ElemType *)malloc((*Lc).listsize*sizeof(ElemType)); if( !(*Lc).elem ) /* 存儲分配失敗 */ exit(0); pa_last = La.elem + La.length - １; //pa_last指向線性表La地尾結(jié)點(diǎn) pb_last = Lb.elem + Lb.length - １; //pb_last指向線性表Lb地尾結(jié)點(diǎn) while(pa <= pa_last && pb <= pb_last) /* 表La和表Lb均非空 */ { /* 歸并 */ if(*pa <= *pb) //*pa更小接到pc后 *pc++ = *pa++; else //*pb更小接到pc后 *pc++