第二章線性表例題

1、1第二章 線性表2線性表順序存儲typedef struct ElemType *elem;/存儲空間基址存儲空間基址 int length; /當(dāng)前長度當(dāng)前長度 int listsize; /當(dāng)前分配的存儲容量當(dāng)前分配的存儲容量 SqList;3例例1：已知長度為：已知長度為n的線性表的線性表A采用順序存儲采用順序存儲結(jié)構(gòu)，請寫一算法，刪除該線性表中所有值結(jié)構(gòu)，請寫一算法，刪除該線性表中所有值為為item的數(shù)據(jù)元素。的數(shù)據(jù)元素。 n算法思路一：算法思路一： 從線性表的第一個數(shù)據(jù)元素開始到最后那個數(shù)據(jù)元意，依次判斷線性表中的數(shù)據(jù)元素是否滿足刪除條件。若某個數(shù)據(jù)元素滿足條件，則從線性表中刪除該數(shù)

2、據(jù)元素，然后修改線性表的長度。4算法一：算法一：Status DELItem(SqList &a, ElemType item) /刪除線性表A中所有值為item的數(shù)據(jù)元素 i=0; while(ia.length) if(a.elemi= item) /若滿足條件 for( j=i+1; j a.length; j+) a.elemj-1=a.elemj; a.length= a.length-1; else i=i+1;時間復(fù)雜度為O(n2)5n算法思路二：算法思路二： 對于數(shù)據(jù)元素Ai，如果它滿足條件，將其從線性表中刪除。由于從第i1個位置移到第i個位置的元素也可能滿足條件，因此

3、，此時的i值不能增加1，還需要原地等待以判斷從后面移來的那個元素是否也滿足刪除條件(如果也滿足刪除條件，接著刪除該元素)，只有當(dāng)Ai不滿足刪除條件時，i才向后移一個位置。 對算法一改進(jìn)后的算法思路是：當(dāng)判斷某個數(shù)據(jù)元素Ai并得知其滿足刪除條件時，先不馬上對其做刪除操作，只記錄這樣的數(shù)據(jù)元素的個數(shù)m，只是在當(dāng)某個數(shù)據(jù)元素不是要刪除的數(shù)據(jù)元素時，這時將該數(shù)據(jù)元素移到線性表的第i-m個位置。6算法二：算法二： Status DELItem(SqList &a, ElemType item) /刪除線性表A中所有值為item的數(shù)據(jù)元素 m=0 for( i=0; ia.length; i+)

4、if(a.elemi = =item ) m=m+1; else a.elemi-m=a.elemi; a.length=a.length-m; /修改線性表的長度時間復(fù)雜度為O(n)7例例2：設(shè)順序表：設(shè)順序表va中的數(shù)據(jù)元素遞增有序，試中的數(shù)據(jù)元素遞增有序，試寫一算法，將寫一算法，將x插入到順序表的適當(dāng)位置上，插入到順序表的適當(dāng)位置上，以保持該表的有序性。以保持該表的有序性。 n算法思路：算法思路： （1）查找x在順序表a.elema.length中的插入位置，即滿足條件：a.elemi=xa.elemi+1的i值（i的初值為a.length-1）; （2）將順序表中的a.length-i

5、-1個元素a.elemi+1a.length-1后移一個位置； （3）將x插入到a.elemi+1中且將表長a.length加1。上述算法正確執(zhí)行的參數(shù)條件為：0=a.lengtha.listsize。 8算法： Status InsertOrderList(SqList &a, ElemType x) /順序表a中的元素依值遞增有序，本算法將x插入其中適當(dāng)位置，以保持有序性。0=a.length=0 & xa.elemi ) i-; /查找x的插入位置 / i=a.elemi for( j=a.length-1; j=i+1; j-) a.elemj+1=a.elemj; a

6、.elemi+1=a.elemi; a.length+; return OK; / InsertOrderList 9例例3.3.設(shè)有一個順序表設(shè)有一個順序表L L，其元素為整型數(shù)，其元素為整型數(shù)據(jù)，設(shè)計一個算法將據(jù)，設(shè)計一個算法將L L中所有小于中所有小于0 0的整的整數(shù)放在前半部分，大于等于數(shù)放在前半部分，大于等于0 0的整數(shù)放在的整數(shù)放在后半部分。后半部分。n算法思路 從L的兩端查找，前端找大于等于0的元素（位置為i），后端找小于0的元素（位置為j），然后將兩位置的元素交換。10Status Move(SqList &L) ElemType temp; int i=0,j=L.l

7、ength-1; while( ij ) while( ij & L.elem i 0) i+; /從前向后找大于等于0的元素 while( i=0 ) j-; / 從后向前找小于0的元素 if ( ij ) /交換L.elemi和L.elemj temp=L.elem i ; L.elem i =L.elem j ; L.elem j =temp; 11例例4. 用順序表表示集合，設(shè)計一個算法用順序表表示集合，設(shè)計一個算法實現(xiàn)集合的求交集運(yùn)算，即實現(xiàn)集合的求交集運(yùn)算，即C=AB。n算法思路： C中元素是A、B中的公共元素。掃描A中的元素A.elemi，若它與B中某個元素相同，表示是交

8、集元素，將其放到C中。12Status Intersection( SqList &C, SqList A, SqList B ) int i,j,k=0; for( i=0; iA.length; i+) j=0; while( jB.length & B.elemj !=A.elemi) j+; if( jB.length) /表示A.elemi在B中，將其放到C中 C.elemk+=A.elemi; C.length=k; /修改集合長度13例例5. 用順序表表示集合，設(shè)計一個算法用順序表表示集合，設(shè)計一個算法實現(xiàn)集合的求并集運(yùn)算，即實現(xiàn)集合的求并集運(yùn)算，即C=AB。n算

9、法思路： C中元素為A和B中非重復(fù)出現(xiàn)的所有元素。先將A復(fù)制到C中；掃描B中的元素B.elemi，若它與A中所有元素均不相同，表示是并集元素，將其放到C中。14Status Union(SqList &C, SqList A, SqList B ) int i, j, k=0; for(i=0; iA.length; i+) /將A中元素復(fù)制到C C.elemi=A.elemi； C.length=A.length; for(i=0; iB.length; i+) j=0; while( jnext; q=NULL; while（p!=NULL） r=q; /r指向前一個鏈結(jié)點(diǎn) q=p

10、; /q指向當(dāng)前鏈結(jié)點(diǎn) p=p-next; /p指向下一個鏈結(jié)點(diǎn) q-next=r; /建立逆序鏈接關(guān)系 L=q; /Invert18例例2：已知非空線性鏈表：已知非空線性鏈表L請寫一算法，刪請寫一算法，刪除該線性鏈表從第除該線性鏈表從第i個鏈結(jié)點(diǎn)開始的連續(xù)個鏈結(jié)點(diǎn)開始的連續(xù)k個個結(jié)點(diǎn)。結(jié)點(diǎn)。(設(shè)設(shè)i1) 算法思路：算法思路：根據(jù)題意，本題應(yīng)該分兩種情況加以考慮： (1)當(dāng)i1時(即從鏈表的第一個鏈結(jié)點(diǎn)就開始刪除)，只需從第一個鏈結(jié)點(diǎn)開始依次刪除鏈表的連續(xù)k個鏈結(jié)點(diǎn)，并釋放它們的存儲空間。 (2)當(dāng)i1時，先找到鏈表的第i-1個鏈結(jié)點(diǎn)，然后從第i個鏈結(jié)點(diǎn)開始刪除從第i個鏈結(jié)點(diǎn)開始的連續(xù)k個鏈結(jié)

11、點(diǎn)，并釋放它們的存儲空間。 19算法：算法： status Delete(linklist &L, int i, int k) / 刪除單鏈表從i鏈結(jié)點(diǎn)開始的k個鏈結(jié)點(diǎn) p=L-next; if(i=1) for(j=1; jnext; free(q); /for L-next=p; /重新定義頭指針 else for(j=1; jnext; /找到第i-1個鏈結(jié)點(diǎn) for(j=1; jnext; p-next=q-next; /刪除一個鏈結(jié)點(diǎn) free(q); / else / Delete 20例例3：已知非空線性鏈表：已知非空線性鏈表L的鏈結(jié)點(diǎn)按結(jié)點(diǎn)數(shù)的鏈結(jié)點(diǎn)按結(jié)點(diǎn)數(shù)據(jù)域值非遞減

12、鏈接，請寫一算法，刪除鏈表據(jù)域值非遞減鏈接，請寫一算法，刪除鏈表中數(shù)據(jù)域值相同的多余鏈結(jié)點(diǎn)。中數(shù)據(jù)域值相同的多余鏈結(jié)點(diǎn)。 n算法思路：算法思路： 算法設(shè)置一指針變量p，從鏈表的第一個鏈結(jié)點(diǎn)開始到鏈表最后那個鏈結(jié)點(diǎn)，依次判斷當(dāng)前p指的鏈結(jié)點(diǎn)與其直接后繼結(jié)點(diǎn)的值是否相同，若相同，則刪除其后繼結(jié)點(diǎn)，否則，p移到下一個鏈結(jié)點(diǎn)。 21算法：算法：status DELS(LinkList &L) /刪除單鏈表中多余的鏈結(jié)點(diǎn) p=L-next; if(!p) return ERROR; /空鏈表 while(p-next !=NULL ) q=p-next; /q指向下一個鏈結(jié)點(diǎn) if(p-data

13、=q-data) p-next=q-next; /刪除p鏈結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)； free(q); else p=p-next; /p移到下一個鏈結(jié)點(diǎn) /while/ DELS 22例例4：已知一個單向循環(huán)鏈表，其每個結(jié)點(diǎn)中：已知一個單向循環(huán)鏈表，其每個結(jié)點(diǎn)中含三個域：含三個域：prior, data 和和next，其中，其中data為為數(shù)據(jù)域，數(shù)據(jù)域，next為指向后繼結(jié)點(diǎn)的指針域，為指向后繼結(jié)點(diǎn)的指針域，prior也為指針域，但它的值為空（也為指針域，但它的值為空（NULL），），試編寫算法將此單鏈表改為雙向循環(huán)鏈表，即試編寫算法將此單鏈表改為雙向循環(huán)鏈表，即使使prior成為指向前驅(qū)結(jié)點(diǎn)的

14、指針域。成為指向前驅(qū)結(jié)點(diǎn)的指針域。 Typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode, *DuLinkList; 23Status Prior_DuL( DuLinkList &L) if(! L) return (OVERFLOW); q= L; p=L-next; if(L-next = =L) L-prior=L; /空雙向鏈表空雙向鏈表 else while( p! = L) p-prior=q; q=p; p=p-next; /while L-prior=q; /elsereturn OK;/ Prior_DuL 24例例5：試以循環(huán)鏈表作稀疏多項式的存儲結(jié)構(gòu)，：試以循環(huán)鏈表作稀疏多項式的存儲結(jié)構(gòu)，編寫求其導(dǎo)函數(shù)的算法，要求利用原多項式編寫求其導(dǎo)函數(shù)的算法，要求利用原多項式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)（多項式），同中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)（多項式），同時釋放所有無用（被刪）結(jié)點(diǎn)。時釋放所有無用（被刪）結(jié)點(diǎn)。Typedefine struct CPolyNode Float coef; Int expn; Struct CPolyNode *next; *CPolyLink; 25Status QiuD