數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 線(xiàn)性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)

/*數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 線(xiàn)性表地動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)P-6 編譯環(huán)境：Dev-C+ 4.9.9.日期：0年月9日 */#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef int ElemType;/ 定義數(shù)據(jù)結(jié)構(gòu)元素地?cái)?shù)據(jù)類(lèi)型#define LIST_INIT_SIZE 0/ 線(xiàn)性表存儲(chǔ)空間地初始分配量#define LISTINCREMENT 5/ 線(xiàn)性表存儲(chǔ)空間地分配增量/ 線(xiàn)性表地動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)typedef structElemType *elem;/ 存儲(chǔ)空間基址int length;/ 當(dāng)前長(zhǎng)度int listsize;/ 當(dāng)前分配地存儲(chǔ)容量(以sizeof(ElemType)為單位)SqList;/ 算法.3，P3 / 構(gòu)造個(gè)空地順序線(xiàn)性表即對(duì)順序表結(jié)構(gòu)體中地所有元素/ 進(jìn)行初始化。int InitList(SqList *L)/ 分配指定大小地存儲(chǔ)空間給順序表(*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType);if( !(*L).elem ) / 存儲(chǔ)分配失敗exit(0);(*L).length = 0; / 當(dāng)前長(zhǎng)度初始化為0/ 指定分配地存儲(chǔ)容量(*L).listsize = LIST_INIT_SIZE;return ;/ 銷(xiāo)毀順序線(xiàn)性表L即將順序表結(jié)構(gòu)體中地所有成員銷(xiāo)毀（空間釋放，/ 數(shù)值置0）。int DestroyList(SqList *L)/ 先釋放空間，然后置空f(shuō)ree( (*L).elem );(*L).elem = NULL;(*L).length = 0;(*L).listsize = 0;return ;/ 將L重置為空表（當(dāng)前長(zhǎng)度為0即是空表）。int ClearList(SqList *L) (*L).length = 0;return ;/*若L為空表，則返回，否則返回0。如何判斷是否為空表呢？結(jié)構(gòu)體中已經(jīng)包含個(gè)可以說(shuō)明地元素，那就是length，表示當(dāng)前順序表地長(zhǎng)度，根據(jù)當(dāng)前地長(zhǎng)度就可以判斷了，為0就是空表，不為0就不是空表了。*/int ListEmpty(SqList L) if(0 = L.length)return ;elsereturn 0;/ 返回L中數(shù)據(jù)元素個(gè)數(shù)。int ListLength(SqList L)/ L.length剛好記錄了當(dāng)前順序表地長(zhǎng)度，直接返回return L.length;/ 用e返回L中第i個(gè)數(shù)據(jù)元素地值，第i個(gè)數(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】 表示第個(gè)數(shù)，而第i個(gè)數(shù)則是用基址L.elem + i - 來(lái)表示,也可以用L.elem【i-】表示。為什么可以那樣表示呢？因?yàn)閘.elem是基地址，相當(dāng)于數(shù)組頭樣，指示了個(gè)首地址，然后對(duì)地址進(jìn)行加減，形成不同元素地地址。*是取地址所指地內(nèi)容，所以*(L.elem+i-)就是第i個(gè)數(shù)據(jù)地值了。*/*e = *(L.elem + i - );/ *e = L.elem【i-】;return ;/*算法.6，P6返回L中第個(gè)與e滿(mǎn)足關(guān)系compare()地?cái)?shù)據(jù)元素地位序。若這樣地?cái)?shù)據(jù)元素不存在，則返回值為0。*/int LocateElem(SqList L,ElemType e, int(* compare)( ElemType, ElemType)ElemType *p;int i = ;/ i地初值為第個(gè)元素地位序p = L.elem;/ p地初值為第個(gè)元素地存儲(chǔ)位置即地址/ 循環(huán)比較，直到找到符合關(guān)系地元素while(i <= L.length && !compare(*p+, e) )+i;if(i <= L.length)return i;elsereturn 0;#if 0/*算法.7 與算法.區(qū)別已知順序線(xiàn)性表La和Lb地元素按值非遞減排列。歸并La和Lb得到新地順序線(xiàn)性表Lc,Lc地元素也按值非遞減排列。算法地時(shí)間復(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指向線(xiàn)性表La地頭結(jié)點(diǎn)pb = Lb.elem;/pb指向線(xiàn)性表Lb地頭結(jié)點(diǎn)/* 不用InitList()創(chuàng)建空表Lc */(*Lc).listsize = (*Lc).length = La.length + Lb.length;/ pc指向線(xiàn)性表Lc地頭結(jié)點(diǎn)pc = (*Lc).elem = (ElemType *)malloc(*Lc).listsize*sizeof(ElemType);if( !(*Lc).elem )/* 存儲(chǔ)分配失敗 */exit(0);pa_last = La.elem + La.length - ;/pa_last指向線(xiàn)性表La地尾結(jié)點(diǎn)pb_last = Lb.elem + Lb.length - ;/pb_last指向線(xiàn)性表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+ = *pa+;/* 插入La地剩余元素 */while(pb <= pb_last)/* 表Lb非空且表La空 */*pc+ = *pb+;/* 插入Lb地剩余元素 */#endif/ 若cur_e是L地?cái)?shù)據(jù)元素，且不是第個(gè)，則用pre_e返回它地前驅(qū)，否/ 則返回0。int PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)int i = ;/ 因?yàn)榈趥€(gè)數(shù)據(jù)元素?zé)o前繼，從第二個(gè)數(shù)據(jù)元素開(kāi)始ElemType *p = L.elem + ;/ 找到該cur_e對(duì)應(yīng)地元素并賦給pwhile(i <= L.length && *p != cur_e)p+;i+;if(i > L.length)return 0;else/*將該cur_e地前驅(qū)賦給*pre_e.對(duì)等式說(shuō)明下：* 和 -是同優(yōu)先級(jí)地，且它們地結(jié)合性是自右向左地，所以先p自減，p指向其前驅(qū)，然后將p所指向地地址地內(nèi)容賦給*pre_e。從這里要明白為什么用指針進(jìn)行傳值，我給你個(gè)地址，你把內(nèi)容放進(jìn)去，然后我就知道其中地值了。這就是使用指針地用處。*/*pre_e = *-p;return ;/*若cur_e是L地?cái)?shù)據(jù)元素，且不是最后個(gè)，則用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)return0;else/*對(duì)這個(gè)等式說(shuō)明下：* 和 -是同優(yōu)先級(jí)地，且它們地結(jié)合性是自右向左地，所以先p自加，然后將p所指向地地址地內(nèi)容賦給*next_e*/*next_e = *+p;return ;/ 算法.4 P4/ 在L中第i個(gè)位置之前插入新地?cái)?shù)據(jù)元素e，L地長(zhǎng)度加.int ListInsert(SqList *L,int i,ElemType e)ElemType *newbase, *q, *p;/ 輸入地i不合法if(i < | i > (*L).length + )return 0;/ 當(dāng)前存儲(chǔ)空間已滿(mǎn),增加分配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 = newbase; / 新基址(*L).listsize += LISTINCREMENT; / 增加存儲(chǔ)容量/ 指定插入地位置q = (*L).elem + i - ;/ q之后地元素右移步，以騰出位置for(p = (*L).elem + (*L).length - ; p >= q; -p)*(p+) = *p;*q = e;/ 插入e+(*L).length;/ 表長(zhǎng)增return ;/*算法.5 P5刪除L地第i個(gè)數(shù)據(jù)元素，并用e返回其值，L地長(zhǎng)度減.*/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;/ 被刪除元素地值賦給eq = (*L).elem + (*L).length-;/ 表尾元素地位置for(+p; p <= q; +p)/ 被刪除元素之后地元素左移*(p-) = *p;(*L).length-;/ 表長(zhǎng)減return ;/ 依次對(duì)L地每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()。int ListTraverse(SqList L, void( *vi )(ElemType* )ElemType *p;int i;p = L.elem;/ 對(duì)順序表中地每元素調(diào)用函數(shù)vi()for(i = ; i <= L.length; i+)vi(p+);printf("n");return ;/ 判斷兩元素地值是否相等地函數(shù)，Union()用到，相等返回，不相等返回0int equal(ElemType c,ElemType c)if(c = c)return ;elsereturn 0;/*算法. P0將所有在線(xiàn)性表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);/ 依次對(duì)Lb中地元素與La地所有元素進(jìn)行比較for(i = ; i <= Lb_len; i+)/ 取Lb中第i個(gè)數(shù)據(jù)元素賦給eGetElem(Lb, i, &e);/ La中不存在和e相同地元素,則插入之if( !LocateElem(*La, e, equal) )ListInsert(La, +La_len, e);/*算法.。P已知線(xiàn)性表La和Lb中地?cái)?shù)據(jù)元素按值非遞減排列。歸并La和Lb得到新地線(xiàn)性表Lc,Lc地?cái)?shù)據(jù)元素也按值非遞減排列。*/void MergeList(SqList La, SqList Lb, SqList *Lc)int i = , j = , k = 0;int La_len, Lb_len;ElemType ai, bj;InitList(Lc);/ 創(chuàng)建空表LcLa_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(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中while(j <= Lb_len)GetElem(Lb, j+, &bj);ListInsert(Lc, +k, bj);/ 在L中按非降序插入新地?cái)?shù)據(jù)元素e，L地長(zhǎng)度加.void InsertAscend(SqList *L, ElemType e)ElemType *newbase, *p;int k;/ k為e要插入地位置if( (*L).length >= (*L).listsize )/ 當(dāng)前存儲(chǔ)空間已滿(mǎn),增加分配newbase = (ElemType *)realloc(*L).elem,(*L).listsize + LISTINCREMENT) * sizeof(ElemType);if( !newbase )exit(0);(*L).elem = newbase;(*L).listsize += LISTINCREMENT;p = (*L).elem;/ 中介，做對(duì)比用地。for(k = ; k <= (*L).length; k+)if(e > *p)p+;elsebreak;ListInsert(L, k, e);/ 在L中按非升序插入新地?cái)?shù)據(jù)元素e，L地長(zhǎng)度加。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);(*L).elem = newbase;(*L).listsize += LISTINCREMENT;p = (*L).elem;for(k = ; k <= (*L).length; k+)if(e < *p)p+;elsebreak;ListInsert(L, k, e);/ 在L地頭部插入新地?cái)?shù)據(jù)元素e，L地長(zhǎng)度加 。int HeadInsert(SqList *L, ElemType e)ElemType *p, *q, *newbase;if( (*L).length >= (*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;/ 從表頭至表尾地元素依次向后移動(dòng)位for(p = (*L).elem + (*L).length-; p >= q; -p)*(p+) = *p;*q = e;(*L).length+;/長(zhǎng)度加return ;/ 在L地尾部插入新地?cái)?shù)據(jù)元素e，L地長(zhǎng)度加。int EndInsert(SqList *L, ElemType e)ElemType *q, *newbase;if( (*L).length >= (*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+(*L).length;/ q為插入位置*q = e;(*L).length+;return ;/ 刪除L地第個(gè)數(shù)據(jù)元素，并由e返回其值，L地長(zhǎng)度減。int DeleteFirst(SqList *L,ElemType *e)ElemType *p, *q;if( ListEmpty(*L) ) / 空表無(wú)法刪除return 0;p = (*L).elem;/ p指向第個(gè)元素*e = *p;q = (*L).elem + (*L).length - ;/ q指向最后個(gè)元素for(+p; p <= q; +p)*(p-) = *p;/ 從第個(gè)元素起，所有元素向前移動(dòng)個(gè)位置(*L).length-;/ 當(dāng)前長(zhǎng)度減return ;/ 刪除L地最后個(gè)數(shù)據(jù)元素，并用e返回其值，L地長(zhǎng)度減 。int DeleteTail(SqList *L,ElemType *e) ElemType *p;if( !(*L).length )/ 空表return 0;p = (*L).elem + (*L).length - ;/ 最后個(gè)數(shù)據(jù)元素地位置*e = *p;/ 被刪除元素地值賦給e(*L).length-;/ 表長(zhǎng)減return ;/ 刪除表中值為e地元素，并返回；如無(wú)此元素，則返回0int DeleteElem(SqList *L, ElemType e)int i = 0,/ 記錄與e值相同地元素地位置j;/ 先判斷i地位置是否越界，然后將e與順序表地每個(gè)元素相比較，/ 直到找到while(i < (*L).length && e != *(*L).elem + i)i+;if(i = (*L).length)/ 沒(méi)找到return 0;else/ 后面地元素依次前移for(j = i; j < (*L).length; j+)*(*L).elem + j) = *(*L).elem + j + );(*L).length-;return ;/ 用e取代表L中第i個(gè)元素地值。int ReplaceElem(SqList L, int i, ElemType e)if(i < | i > L.length)/ i值不合法exit(0);*(L.elem + i - ) = e;/替換為ereturn ;/按非降序建立n個(gè)元素地線(xiàn)性表。int CreatAscend(SqList *L, int n) int i,j;/記錄數(shù)據(jù)要插入地位置ElemType e;InitList(L);printf("請(qǐng)輸入%d個(gè)元素:（空格）n",n);scanf("%d", &e);ListInsert(L, , e); / 在空表中插入第個(gè)元素for(i = ; i < n; i+)scanf("%d",&e);/將待插入地?cái)?shù)據(jù)與順序表地每個(gè)元素比較/比期中個(gè)小地話(huà)則退出循環(huán)for(j = 0; j <(*L).length; j+)if(e <= *(*L).elem+j)break;/ 將e插表中地第j+個(gè)位置ListInsert(L, j+, e);return ;/按非升序建立n個(gè)元素地線(xiàn)性表。int CreatDescend(SqList *L, int n)int i,j;/記錄數(shù)據(jù)要插入地位置ElemType e;InitList(L);printf("請(qǐng)輸入%d個(gè)元素:n", n);scanf("%d", &e);ListInsert(L, , e);/ 在空表中插入第個(gè)元素for(i = ; i < n; i+)scanf("%d", &e);for(j = 0;j < (*L).length; j+)if(e >= *(*L).elem + j)break;ListInsert(L, j + , e);return ;/ 進(jìn)行測(cè)試/ 數(shù)據(jù)元素判定函數(shù)(平方關(guān)系)int comp(ElemType c, ElemType c)if(c = c*c)return ;elsereturn 0;/ ListTraverse()調(diào)用地函數(shù)(類(lèi)型要致)void visit(ElemType *c)printf("%d ",*c);/ 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 L.length=%d L.listsize=%dnn",L.elem, L.length, L.listsize);/ 通過(guò)插入操作創(chuàng)建個(gè)順序表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=%dnn",L.elem, L.length, L.listsize);/ 判斷順序表是否為空表i = ListEmpty(L);printf("L是否空：i=%d(:是 0:否)nn",i);/ 清空順序表i = ClearList(&L);printf("清空L后：L.elem=%u L.length=%d L.listsize=%dnn",L.elem,L.length,L.listsize);i = ListEmpty(L);printf("L是否空：i=%d(:是 0:否)nn",i);/ 再次通過(guò)插入操作創(chuàng)建個(gè)新地順序表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=%dnn",L.elem, L.length, L.listsize);/ 插入個(gè)數(shù)地操作ListInsert(&L, , 0);printf("在L地表頭插入0后：*L.elem=");/ 求當(dāng)前順序表地長(zhǎng)度,并打印順序表, ListLength(L)返回元素個(gè)數(shù)for(j = ; j <= ListLength(L); j+)printf("%d ",*(L.elem+j-);printf("n");printf("L.elem = %u(有可能改變) L.length = %d(改變)""L.listsize = %d(改變)nn",L.elem, L.length, L.listsize);/ 取得順序表地第5個(gè)數(shù)并用e返回GetElem(L, 5, &e);printf("第5個(gè)元素地值為：%dnn",e);/ 返回第個(gè)與j滿(mǎn)足關(guān)系compare地?cái)?shù)據(jù)元素地位序/ 在這里舉了兩個(gè)例子，個(gè)符合，個(gè)不符合地for(j = 3; j <= 4; j+)k = LocateElem(L, j, comp);if(k)printf("第%d個(gè)元素地值為%d地平方nn", k, j);elseprintf("沒(méi)有值為%d地平方地元素nn", j);/ 求前驅(qū)地操作,在這里舉了兩個(gè)例子，個(gè)符合，個(gè)不符合地（即頭）for(j = ; j <= ; j+)GetElem(L, j, &e0);/ 把第j個(gè)數(shù)據(jù)賦給e0i = PriorElem(L,e0,&e);/ 求e0地前驅(qū)if(i = 0)printf("元素%d無(wú)前驅(qū)nn",e0);elseprintf("元素%d地前驅(qū)為：%dnn",e0,e);/ 求后繼操作，在這里同樣舉了兩個(gè)例子，個(gè)符合，個(gè)不符合地（即尾）for(j = ListLength(L)-; j <= ListLength(L); j+)GetElem(L,j,&e0);/ 把第j個(gè)數(shù)據(jù)賦給e0i = NextElem(L,e0,&e);/ 求e0地后繼if(i = 0)printf("元素%d無(wú)后繼nn",e0);elseprintf("元素%d地后繼為：%dnn",e0,e);/ 刪除操作k = ListLength(L);for(j = k+; j >= k; j-)/ 刪除第j個(gè)數(shù)據(jù)i = ListDelete(&L, j, &e);if(i = 0)printf("刪除第%d個(gè)數(shù)據(jù)失敗nn",j);elseprintf("刪除地元素值為：%dnn",e);/ 對(duì)順序表地所有元素調(diào)用函數(shù)visitprintf("依次輸出L地元素：");ListTraverse(L,visit);/對(duì)順序表地所有元素調(diào)用函數(shù)dblprintf("nL地元素值加倍后：");/ 依次對(duì)元素調(diào)用dbl()，元素值乘ListTraverse(L,dbl);/ 顯示鏈表ListTraverse(L,visit);printf("n");/ 銷(xiāo)毀順序表DestroyList(&L);printf("銷(xiāo)毀L后：L.elem=%u L.length=%d L.listsize=%dnnn",L.elem,L.length,L.listsize);/ 創(chuàng)建兩個(gè)表并進(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 <= 5; j+)i = ListInsert(&Lb, j, * j);printf("Lb= ");ListTraverse(Lb, visit);/ 將兩個(gè)表進(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= ");ListTraverse(La, visit);InitList( &Lb );for(j = ; j <= 7; j+)ListInsert(&Lb, j, b【j-】);printf("Lb= ");ListTraverse(Lb, visit);/ 合并La和Lb 為 LcMergeList(La, Lb, &Lc);printf("合并La與Lb后得到地Lc= ");ListTraverse(Lc, visit);printf("n");/ 按非降序建立n個(gè)元素地線(xiàn)性表Lprintf("按非降序建立n個(gè)元素地線(xiàn)性表L,請(qǐng)輸入元素個(gè)數(shù)n: ");scanf("%d",&n);CreatAscend(&L,n);printf("依次輸出L地元素：");ListTraverse(L, visit);printf("n");/ 按非降序插入元素0InsertAscend(&L,0);printf("按非降序插入元素0后，線(xiàn)性表L為：");ListTraverse(L,visit);printf("n");/ 在L地頭部插入HeadInsert(&L,);/ 在L地尾部插入9EndInsert(&L,9);printf("在L地頭部插入，尾部插入9后，線(xiàn)性表L為：");ListTraverse(L,visit);printf("n");printf("請(qǐng)輸入要?jiǎng)h除地元素地值: ");scanf("%d",&e);i = DeleteElem(&L,e);if(i)printf("成功刪除%dn",e);elseprintf("不存在元素%d!n",e);printf("線(xiàn)性表L為：");ListTraverse(L,visit);printf("n");printf("請(qǐng)輸入要取代地元素地序號(hào) 元素地新值:（空格） ");scanf("%d%d", &n, &e);ReplaceElem(L, n, e);printf("線(xiàn)性表L為：");ListTraverse(L,visit);printf("n");DestroyList(&L);printf("銷(xiāo)毀L后,按非升序重新建立n個(gè)元素地線(xiàn)性表L,請(qǐng)輸入""元素個(gè)數(shù)n(>): ");scanf("%d",&n);CreatDescend(&L,n);printf("依次輸出L地元素：");ListTraverse(L,visit);printf("n");/ 按非升序插入元素0InsertDescend(&L,0);printf("按非升序插入元素0后，線(xiàn)性表L為：");ListTraverse(L,visit);printf("n");printf("請(qǐng)輸入要?jiǎng)h除地元素地值: ");scanf("%d",&e);i = DeleteElem(&L,e);if(i)printf("成功刪除%dn",e);elseprintf("不存在元素%d!n",e);printf("線(xiàn)性表L為：");ListTraverse(L,visit);printf("n");/ 刪除頭節(jié)點(diǎn)DeleteFirst(&L,&e);/ 刪除尾節(jié)點(diǎn)DeleteTail(&L,&d);printf("刪除表頭元素%d和表尾元素%d后,線(xiàn)性表L為：n",e,d);ListTraverse(L,visit);printf("n");system("pause"); return 0;/*輸出效果：初始化L后：L.elem=3484 L.length=0 L.listsize=0在L地表頭依次插入5后：*L.elem=5 4 3 L.elem=3484 L.length=5 L.listsize=0L是否空：i=0(:是 0:否)清空L后：L.elem=3484 L.length=0 L.listsize=0L是否空：i=(:是 0:否)在L地表尾依次插入0后：*L.elem= 3 4 5 6 7 8 9 0L.elem=3484 L.length=0 L.listsize=0在L地表頭插入0后：*L.elem=0 3 4 5 6 7 8 9 0L.elem = 3484(有可能改變) L.length = (改變)L.listsize = 5(改變)第5個(gè)元素地值為：4第0個(gè)元素地值為3地平方?jīng)]有值為4地平方地元素元素0無(wú)前驅(qū)元素地前驅(qū)為：0元素9地后繼為：0元素0無(wú)后繼刪除第個(gè)數(shù)據(jù)失敗刪除地元素值為：0依次輸出L地元素：0 3 4 5 6 7 8 9L地元素值加倍后：0 4 6 8 0 4 6 8銷(xiāo)毀L后：L.elem=0 L.length=0 L.listsize=0La= 3 4 5Lb= 4 6 8 0La與Lb合并后新地La= 3 4 5 6 8 0La= 3 5 8 Lb= 6 8 9 5 0合并La與Lb后得到地Lc= 3 5 6 8 8 9 5 0按非降序建立n個(gè)元素地線(xiàn)性表L,請(qǐng)輸入元素個(gè)數(shù)n: 3請(qǐng)輸入3個(gè)元素:（空格） 3依次輸出L地元素： 3按非降序插入元素0后，線(xiàn)性表L為： 3 0在L地頭部插入，尾部插入9后，線(xiàn)性表L為： 3 0 9請(qǐng)輸入要?jiǎng)h除地元素地值: 3成功刪除3線(xiàn)性表L為： 0 9請(qǐng)輸入要取代地元素地序號(hào) 元素地新值:（空格） 5 4線(xiàn)性表L為： 0 4銷(xiāo)毀L后,按非升序重新建立n個(gè)元素地線(xiàn)性表L,請(qǐng)輸入元素個(gè)數(shù)n(>): 3請(qǐng)輸入3個(gè)元素: 3依次輸出L地元素：3 按非升序插入元素0后，線(xiàn)性表L為：0 3 請(qǐng)輸入要?jiǎng)h除地元素地值: 0成功刪除0線(xiàn)性表L為：3 刪除表頭元素3和表尾元素后,線(xiàn)性表L為：請(qǐng)按任意鍵繼續(xù). . .*/ /*數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 線(xiàn)性表地動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)P-6 編譯環(huán)境：Dev-C+ 4.9.9.日期：0年月9日 */#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef int ElemType;/ 定義數(shù)據(jù)結(jié)構(gòu)元素地?cái)?shù)據(jù)類(lèi)型#define LIST_INIT_SIZE 0/ 線(xiàn)性表存儲(chǔ)空間地初始分配量#define LISTINCREMENT 5/ 線(xiàn)性表存儲(chǔ)空間地分配增量/ 線(xiàn)性表地動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)typedef structElemType *elem;/ 存儲(chǔ)空間基址int length;/ 當(dāng)前長(zhǎng)度int listsize;/ 當(dāng)前分配地存儲(chǔ)容量(以sizeof(ElemType)為單位)SqList;/ 算法.3，P3 / 構(gòu)造個(gè)空地順序線(xiàn)性表即對(duì)順序表結(jié)構(gòu)體中地所有元素/ 進(jìn)行初始化。int InitList(SqList *L)/ 分配指定大小地存儲(chǔ)空間給順序表(*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType);if( !(*L).elem ) / 存儲(chǔ)分配失敗exit(0);(*L).length = 0; / 當(dāng)前長(zhǎng)度初始化為0/ 指定分配地存儲(chǔ)容量(*L).listsize = LIST_INIT_SIZE;return ;/ 銷(xiāo)毀順序線(xiàn)性表L即將順序表結(jié)構(gòu)體中地所有成員銷(xiāo)毀（空間釋放，/ 數(shù)值置0）。int DestroyList(SqList *L)/ 先釋放空間，然后置空f(shuō)ree( (*L).elem );(*L).elem = NULL;(*L).length = 0;(*L).listsize = 0;return ;/ 將L重置為空表（當(dāng)前長(zhǎng)度為0即是空表）。int ClearList(SqList *L) (*L).length = 0;return ;/*若L為空表，則返回，否則返回0。如何判斷是否為空表呢？結(jié)構(gòu)體中已經(jīng)包含個(gè)可以說(shuō)明地元素，那就是length，表示當(dāng)前順序表地長(zhǎng)度，根據(jù)當(dāng)前地長(zhǎng)度就可以判斷了，為0就是空表，不為0就不是空表了。*/int ListEmpty(SqList L) if(0 = L.length)return ;elsereturn 0;/ 返回L中數(shù)據(jù)元素個(gè)數(shù)。int ListLength(SqList L)/ L.length剛好記錄了當(dāng)前順序表地長(zhǎng)度，直接返回return L.length;/ 用e返回L中第i個(gè)數(shù)據(jù)元素地值，第i個(gè)數(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】 表示第個(gè)數(shù)，而第i個(gè)數(shù)則是用基址L.elem + i - 來(lái)表示,也可以用L.elem【i-】表示。為什么可以那樣表示呢？因?yàn)閘.elem是基地址，相當(dāng)于數(shù)組頭樣，指示了個(gè)首地址，然后對(duì)地址進(jìn)行加減，形成不同元素地地址。*是取地址所指地內(nèi)容，所以*(L.elem+i-)就是第i個(gè)數(shù)據(jù)地值了。*/*e = *(L.elem + i - );/ *e = L.elem【i-】;return ;/*算法.6，P6返回L中第個(gè)與e滿(mǎn)足關(guān)系compare()地?cái)?shù)據(jù)元素地位序。若這樣地?cái)?shù)據(jù)元素不存在，則返回值為0。*/int LocateElem(SqList L,ElemType e, int(* compare)( ElemType, ElemType)ElemType *p;int i = ;/ i地初值為第個(gè)元素地位序p = L.elem;/ p地初值為第個(gè)元素地存儲(chǔ)位置即地址/ 循環(huán)比較，直到找到符合關(guān)系地元素while(i <= L.length && !compare(*p+, e) )+i;if(i <= L.length)return i;elsereturn 0;#if 0/*算法.7 與算法.區(qū)別已知順序線(xiàn)性表La和Lb地元素按值非遞減排列。歸并La和Lb得到新地順序線(xiàn)性表Lc,Lc地元素也按值非遞減排列。算法地時(shí)間復(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指向線(xiàn)性表La地頭結(jié)點(diǎn)pb = Lb.elem;/pb指向線(xiàn)性表Lb地頭結(jié)點(diǎn)/* 不用InitList()創(chuàng)建空表Lc */(*Lc).listsize = (*Lc).length = La.length + Lb.length;/ pc指向線(xiàn)性表Lc地頭結(jié)點(diǎn)pc = (*Lc).elem = (ElemType *)malloc(*Lc).listsize*sizeof(ElemType);if( !(*Lc).elem )/* 存儲(chǔ)分配失敗 */exit(0);pa_last = La.elem + La.length - ;/pa_last指向線(xiàn)性表La地尾結(jié)點(diǎn)pb_last = Lb.elem + Lb.length - ;/pb_last指向線(xiàn)性表Lb地尾結(jié)點(diǎn)while(pa <= pa_last && pb <= pb_last)/* 表La和表Lb均非空 */* 歸并 */if(*pa <= *pb)/*pa更小接到pc后*pc+ = *pa+;else/*pb更小接到pc后*pc+