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

DS第二章_課后習(xí)題答案DS第二章_課后習(xí)題答案/NUMPAGES20DS第二章_課后習(xí)題答案DS第二章_課后習(xí)題答案第二章線性表2.1填空題(1)一半插入或刪除的位置(2)靜態(tài)動(dòng)態(tài)(3)一定不一定(4)頭指針頭結(jié)點(diǎn)的next前一個(gè)元素的next2.2選擇題(1)A(2)DAGKHDAELIAFIFA(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遞增有序，寫(xiě)一算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。voidInserList(SeqList*L,ElemTypex){inti=L->last;if(L->last>=MAXSIZE-1)returnFALSE;//順序表已滿while(i>=0&&L->elem[i]>x){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;L->last++;}2.5刪除順序表中從i開(kāi)始的k個(gè)元素intDelList(SeqList*L,inti,intk){intj,l;if(i<=0||i>L->last){printf("TheInitialPositionisError!");return0;}if(k<=0)return1;/*NoNeedtoDelete*/if(i+k-2>=L->last)L->last=L->last-k;/*modifythelength*/for(j=i-1,l=i+k-1;l<L->last;j++,l++)L->elem[j]=L->elem[l];L->last=L->last-k;return1;}2.6已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫(xiě)一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，刪除線性表中所有值為item的數(shù)據(jù)元素。[算法1]voidDeleteItem(SeqList*L,ElemTypeitem){inti=0,j=L->last;while(i<j){while(i<j&&L->elem[i]!=item)i++;while(i<j&&L->elem[i]==item)j--;if(i<j){L->elem[i]=L->elem[j];i++;j--;}}L->last=i-1;}[算法2]voidDeleteItem(SeqList*L,ElemTypee){ inti,j; i=j=0; while(L->elem[i]!=e&&i<=L->last) i++; j=i+1; while(j<=L->last) { while(L->elem[j]==e&&j<=L->last) j++; if(j<=L->last) { L->elem[i]=L->elem[j]; i++;j++; } } L->last=i-1; }2.7編寫(xiě)算法，在一非遞減的順序表L中，刪除所有值相等的多余元素。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

voidDeleteRepeatItem(SeqList*L){inti=0,j=1;while(j<=L->last){if(L->elem[i]==L->elem[j])j++;else{L->elem[i+1]==L->elem[j];i++;j++;}}L->last=i;}2.8已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫(xiě)一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度。voidDelData(LinkListL,ElemTypemink,ElemTypemaxk){ 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）。以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)。以單鏈表作存儲(chǔ)結(jié)構(gòu)。(略)(1)voidReverseArray(ElemTypea[],intn){ inti=0,j=n-1; ElemTypet; while(i<j) {t=a[i];a[i]=a[j];a[j]=t;} }(2)voidReverseList(LinkListL){ 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è)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data域的值，并返回1；否則，至返回0。（提示：設(shè)置兩個(gè)指針，步長(zhǎng)為k）intSearchNode(LinkListL,intk){ Node*p=L,*q; inti=0; while(i<k&&p) {i++;p=p->next;} if(p==NULL)return0;//不存在倒數(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",q->data); return1;}2.11把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列,使用原空間。（頭插法）LinkListReverseMerge(LinkList*A,LinkList*B){LinkListC;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=pa->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->next;C->next=pb;pb=temp;}/*將剩余pb的元素前插到pc表*/returnhc;}2.12一單鏈表，以第一個(gè)元素為基準(zhǔn)，將小于該元素的結(jié)點(diǎn)全部放到前面，大于該結(jié)點(diǎn)的元素全部放到后面。時(shí)間復(fù)雜度要求為O(n)，不能申請(qǐng)新空間。voidAdjustList(LinkListL){Node*pFlag=L->next,*q=L->next->next,*temp=NULL;pflag->next=NULL;while(q!=NULL){if(q->data<pFlag->data)//插到鏈表首端{(lán)temp=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)的指針，試編寫(xiě)算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。voidDelPreNode(Node*s){Node*p=s;while(p->next->next!=s)p=p->next;free(p->next);p->next=s;}2.14已知由單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其他字符），試編寫(xiě)算法來(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)鏈表，采用頭插法voidsplitLinkList(LinkListL,LinkListLch,LinkListLnum,LinkListLoth){ 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;} elseif(p->data>='0'&&p->data<='9') {temp=p->next;p->next=Lnum->next;Lnum->next=p;p=temp;} else {temp=p->next;p->next=Loth->next;Loth->next=p;p=temp;} }}2.15設(shè)線性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，試寫(xiě)一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得：C=(a1,b1,…,am,bm,bm+1,…,bn)當(dāng)m≤n時(shí)；或者C=(a1,b1,…,an,bn,an+1,…,am)當(dāng)m>n時(shí)。線性表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)被初始化為空單鏈表voidMergeLinkList(LinkListA,LinkListB,LinkListC){ Node*pa=A->next，*pb=B->next,*pc=C; inttag=1; while(pa&&pb) { if(tag) {pc->next=pa->next;pc=pc->next;pa=pa->next;tag=1;} else {pc->next=pb->next;pc=pc->next;pb=pb->next;tag=0;} } if(pa)pc->next=pa->next; elsepc->next=pb->next;s}2.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)的單鏈表voidSplitPolyList(PolyListA,PolyListB,PolyListC){ 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ù)加1的運(yùn)算。voidBinAdd(LinkListl)/*用帶頭結(jié)點(diǎn)的單鏈表L存儲(chǔ)二進(jìn)制數(shù)，實(shí)現(xiàn)加1運(yùn)算*/{ Node*q,*r,*s; q=l->next; r=l;