DS第二章課后習題答案

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

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個元素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 已知長度為n的線性表A

4、采用順序存儲結(jié)構(gòu)，請寫一時間復雜度為O(n)、空間復雜度為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中，刪除所有值相等的多余元素。要求時間復雜度為O(n)，空間復雜度為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ù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復雜度。void DelData(LinkList L,ElemType mink,ElemType ma

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

8、以單鏈表作存儲結(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已知一個帶有表頭結(jié)點的單鏈表,假設鏈表只給出了頭指針L。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查

9、找鏈表中倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點的data域的值，并返回1；否則，至返回0。（提示：設置兩個指針，步長為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個元素q=L->next;while(p->next!=NULL) /p到終點時，q所指結(jié)點為倒數(shù)第k個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的當前元素 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一單鏈表，以第一個元素為基準，將小于該元素的結(jié)點全部放到前面，大于該結(jié)點的元素全部放到后面。時間復雜度要求為O(n)，不能申請新空間。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é)點后面 temp=q->next; q->next=pFlag->next; pFlag->next=q; q=temp; 2.13假設有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前驅(qū)結(jié)點。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ù)字字符和其他字符），試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。/L為待拆分鏈表/Lch為拆分后的字母鏈；Lnum為拆分后的數(shù)字鏈，Loth為拆分后的其他字符鏈/Lch,Lnum,Loth均已被初始化為帶頭結(jié)點的單循環(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設線性表A=(a1, a2,am)，B=(b1, b2,bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 當mn時；或者 C= (a1, b1,an, bn, an+1, ,am) 當m>n時

17、。線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。/將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將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。/A為循環(huán)單鏈表，表示某多項式；將A拆分為B和C/其中B只含奇次項，C只含偶次項；奇偶按照冪次區(qū)分/B,C均已被初始化為帶頭結(jié)點的單鏈表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) /偶次項rc->next=pa->next; rc=rc->next; pa=pa->next; else /奇次項rb->next=pa->next; rb=rb->next; pa=pa->next; rb->next=NULL; rc->next=NULL;2.17建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位。并在此鏈表上實現(xiàn)對二進制數(shù)