DS第二章_課后習(xí)題答案

1、第二章 線性表2.1 填空題 (1)一半 插入或刪除的位置 (2)靜態(tài) 動(dòng)態(tài) (3)一定 不一定 (4)頭指針 頭結(jié)點(diǎn)的next 前一個(gè)元素的next2.2 選擇題 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D2.3 頭指針：在帶頭結(jié)點(diǎn)的鏈表中，頭指針存儲(chǔ)頭結(jié)點(diǎn)的地址；在不帶頭結(jié)點(diǎn)的鏈表中，頭指針存放第一個(gè)元素結(jié)點(diǎn)的地址； 頭結(jié)點(diǎn)：為了操作方便，在第一個(gè)元素結(jié)點(diǎn)前申請(qǐng)一個(gè)結(jié)點(diǎn)，其指針域存放第一個(gè)元素結(jié)點(diǎn)的地址，數(shù)據(jù)域可以什么都不放； 首元素結(jié)點(diǎn)：第一個(gè)元素的結(jié)點(diǎn)。2.4已知順序表L遞增有序，寫一算法，將X插入到線性表的適當(dāng)位置上，以保持線性

2、表的有序性。void InserList(SeqList *L,ElemType x) int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; /順序表已滿 while(i>=0 && L->elemi>x) L->elemi+1=L->elemi; i-; L->elemi+1=x; L->last+;2.5 刪除順序表中從i開(kāi)始的k個(gè)元素int DelList(SeqList *L,int i,int k) int j,l; if(i<=0|i>L->

3、;last) printf("The Initial Position is Error!"); return 0; if(k<=0) return 1; /*No Need to Delete*/ if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/ for(j=i-1,l=i+k-1;l<L->last;j+,l+) L->elemj=L->eleml; L->last=L->last-k; return 1;2.6 已知長(zhǎng)度為n的線性表A

4、采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，刪除線性表中所有值為item的數(shù)據(jù)元素。算法1void DeleteItem(SeqList *L,ElemType item) int i=0,j=L->last; while(i<j) while(i<j && L->elemi!=item) i+; while(i<j && L->elemi=item) j-; if(i<j) L->elemi=L->elemj; i+; j-; L->last=i-1;算法2void De

5、leteItem (SeqList *L,ElemType e)int i,j;i=j=0;while(L->elemi!=e && i<=L->last)i+;j=i+1;while(j<=L->last)while(L->elemj=e && j<=L->last)j+;if(j<=L->last)L->elemi=L->elemj;i+; j+;L->last=i-1;2.7 編寫算法，在一非遞減的順序表L中，刪除所有值相等的多余元素。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1

6、)。void DeleteRepeatItem(SeqList *L) int i=0,j=1; while(j<=L->last) if(L->elemi=L->elemj) j+; else L->elemi+1=L->elemj; i+; j+; L->last=i; 2.8已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度。void DelData(LinkList L,ElemType mink,ElemType ma

7、xk)Node *p=L->next,*pre=L;while(!p && p->data <= mink) /尋找開(kāi)始刪除的位置pre=p; p=p->next;while(p) if(p->data > maxk) break; else pre->next=p->next; free(p); p=pre->next; T(n)=O(n);2.9試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1, a2., an）逆置為（an, an-1,., a1）。（1） 以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)。（2）

8、以單鏈表作存儲(chǔ)結(jié)構(gòu)。(略)(1)void ReverseArray(ElemType a,int n)int i=0,j=n-1;ElemType t;while(i<j) t=ai; ai=aj; aj=t;(2)void ReverseList(LinkList L) p=L->next; L->next=NULL; while(p!=NULL) q=p->next; p->next=L->next; L->next=p; p=q; 2.10已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表,假設(shè)鏈表只給出了頭指針L。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查

9、找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data域的值，并返回1；否則，至返回0。（提示：設(shè)置兩個(gè)指針，步長(zhǎng)為k）int SearchNode(LinkList L,int k)Node *p=L,*q;int i=0;while(i<k && p)i+; p=p->next; if(p=NULL) return 0; /不存在倒數(shù)第k個(gè)元素q=L->next;while(p->next!=NULL) /p到終點(diǎn)時(shí)，q所指結(jié)點(diǎn)為倒數(shù)第k個(gè)q=q->next; p=p->next;printf("%d

10、",q->data);return 1;2.11把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列,使用原空間。（頭插法）LinkList ReverseMerge(LinkList *A, LinkList *B) LinkList C; Node *pa=A->next,*pb=B->next; /pa和pb分別指向A,B的當(dāng)前元素 A->next=NULL; C=A; while(pa!=NULL && pb!=NULL) if(pa->data < pb->data) /*將pa的元素前插到pc表*/ temp=p

11、a->next; pa->next=C->next; C->next=pa; pa=temp; else temp=pb->next; pb->next=C->next; C->next=pb; pb=temp; /*將pb的元素前插到pc表*/ while(pb!=NULL) temp=pa->next; pa->next=C->next; C->next=pa; pa=temp; /*將剩余pa的元素前插到pc表*/ while(pb!=NULL) temp=pb->next; pb->next=C->

12、;next; C->next=pb; pb=temp; /*將剩余pb的元素前插到pc表*/ return hc;2.12一單鏈表，以第一個(gè)元素為基準(zhǔn)，將小于該元素的結(jié)點(diǎn)全部放到前面，大于該結(jié)點(diǎn)的元素全部放到后面。時(shí)間復(fù)雜度要求為O(n)，不能申請(qǐng)新空間。void AdjustList(LinkList L) Node *pFlag=L->next,*q=L->next->next,*temp=NULL; pflag->next=NULL; while(q!=NULL) if(q->data < pFlag->data) /插到鏈表首端 temp

13、=q->next; q->next=L->next; L->next=q; q=temp; Else /插到pFlag結(jié)點(diǎn)后面 temp=q->next; q->next=pFlag->next; pFlag->next=q; q=temp; 2.13假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。void DelPreNode(Node* s) Node* p=s; while(p->next->next!=s) p=p->next;

14、free(p->next); p->next=s;2.14已知由單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其他字符），試編寫算法來(lái)構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。/L為待拆分鏈表/Lch為拆分后的字母鏈；Lnum為拆分后的數(shù)字鏈，Loth為拆分后的其他字符鏈/Lch,Lnum,Loth均已被初始化為帶頭結(jié)點(diǎn)的單循環(huán)鏈表，采用頭插法void splitLinkList(LinkList L,LinkList Lch,LinkList Lnum,LinkList Loth

15、) Node *p=L->next; while(p!=NULL) if( (p->data >='a' && p->data<='z')| (p->data >= 'A' && p->data<='Z')temp=p->next; p->next=Lch->next; Lch->next=p; p= temp; else if(p->data >='0' && p->da

16、ta<='9')temp=p->next; p->next=Lnum->next; Lnum->next=p; p= temp; elsetemp=p->next; p->next=Loth->next; Loth->next=p; p= temp; 2.15設(shè)線性表A=(a1, a2,am)，B=(b1, b2,bn)，試寫一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 當(dāng)mn時(shí)；或者 C= (a1, b1,an, bn, an+1, ,am) 當(dāng)m>n時(shí)

17、。線性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。/將A和B合并為C,C已經(jīng)被初始化為空單鏈表void MergeLinkList(LinkList A,LinkList B,LinkList C) Node *pa=A->next，*pb=B->next,*pc=C; int tag=1; while(pa && pb) if(tag)pc->next=pa->next; pc=pc->next; pa=pa->next; tag=1;else pc->next=p

18、b->next; pc=pc->next; pb=pb->next; tag=0; if(pa) pc->next=pa->next; else pc->next=pb->next; s2.16將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)成這兩個(gè)鏈表。/A為循環(huán)單鏈表，表示某多項(xiàng)式；將A拆分為B和C/其中B只含奇次項(xiàng)，C只含偶次項(xiàng)；奇偶按照冪次區(qū)分/B,C均已被初始化為帶頭結(jié)點(diǎn)的單鏈表void SplitPolyList(PolyList A,PolyList B,PolyL

19、ist C) PolyNode *pa=A->next,*rb=B,*rc=C; while(pa) if(pa->exp%2=0) /偶次項(xiàng)rc->next=pa->next; rc=rc->next; pa=pa->next; else /奇次項(xiàng)rb->next=pa->next; rb=rb->next; pa=pa->next; rb->next=NULL; rc->next=NULL;2.17建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位。并在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)