數(shù)據(jù)結(jié)構(gòu)課后習(xí)題與解析第二章

1、第二章習(xí)題1 .描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)2 .填空：(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動元素，具體移動的元素個(gè)數(shù)與有關(guān)。(2) 在順序表中，邏輯上相鄰的元素，其物理位置相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲位置指示，首元素結(jié)點(diǎn)的(3) 由存指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲位儲位置由置由指示。3.已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是：。b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是：。c.在表首

2、插入S結(jié)點(diǎn)的語句序列是：。d.在表尾插入S結(jié)點(diǎn)的語句序列是：。供選擇的語句有：(1) P->next=S;(2) P->next=P->next->next;(3) P->next=S->next;(4) S->next=P->next;(5) S->next=L;(6) S->next=NULL;(7) Q=P;(8) while(P->next!=Q)P=P->next;(9) while(P->next!=NULL)P=P->next;(10) P=Q;(11) P=L;(12) L=S;(13) L=P

3、;設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中且遞增有序。試寫一算X插入4. 法，將到線性表的適當(dāng)位置上，以保持線性表的有序性。一5. 寫一算法，從順序表中刪除自第的八口k個(gè)元素。6. 已知線性表中的元素(整數(shù))以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素(若表中存在這樣的元素),分析你的算法的時(shí)間復(fù)雜度(注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù))。7. 試分別以不同的存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表(a1,a2.,an)逆置為(an,an-1,.,a1)。11) 以一維

4、數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中。12) 以單鏈表作存儲結(jié)構(gòu)。8. 假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B,均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序排列的線性表C,并要求利用原表(即A表和B表的）結(jié)點(diǎn)空間存放表C已知s為指向鏈9. 假設(shè)有一個(gè)循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點(diǎn)也無頭指針。表s所指結(jié)點(diǎn)的前趨結(jié)某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針點(diǎn)。已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元(如字母字符、數(shù)字字符和其10. 素它字符)，試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字

5、符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。11.設(shè)線性表A=(a1,a2,am),B=(b1,b2,bn),試寫一個(gè)按下列規(guī)則合并AB為線性表C二(a1,b1,C=(a1,或者b1,線性表A、B、C意：單鏈表的長度值C的算法，使得:,am,bm,bm+1,bn)當(dāng)m<n時(shí)；,an,bn,an+1,am)當(dāng)m>n時(shí)。C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成均以單鏈表作為存儲結(jié)構(gòu)，且注m和n均未顯式存儲。12 .將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來構(gòu)成這兩個(gè)鏈表。data13 .建立

6、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的域存放一個(gè)二進(jìn)制位。并在此鏈表上實(shí)現(xiàn)對二進(jìn)制數(shù)加1的運(yùn)算。設(shè)多項(xiàng)式P(x)采用課本中所述鏈接方法存儲。寫一算法，對給定x值，求P(x)的14 .的值。實(shí)習(xí)題1 .將若干城市的信息存入一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)中的城市信息包括城市名、城市的位置坐標(biāo)。要求：(1)給定一個(gè)城市名，返回其位置坐標(biāo)；(2)給定一個(gè)位置坐標(biāo)P和一個(gè)距離D,返回所有與P的距離小于等于D的城市。2 .約瑟夫環(huán)問題。1,2,n的n個(gè)人按順時(shí)針方向圍坐一圈，約瑟夫問題的一種描述是：編號為每人持有一個(gè)密碼(正整數(shù))。一開始任選一個(gè)整數(shù)作為報(bào)數(shù)上限m,從第一個(gè)人開始順時(shí)

7、針值自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人由列，將他的密碼作為新的m值，從他在順1報(bào)數(shù)，如此下去，直至所有的人全部由列為時(shí)針方向上的下一個(gè)人開始重新從止。試設(shè)計(jì)一個(gè)程序，求由由列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照由列順序打印由各人的編例如m的初值為20;n=7,7個(gè)人的密碼依次是：3,1,7,2,4,8,4,由列的順序?yàn)?,1,4,7,2,3,5。第二章答案約瑟夫環(huán)問題約瑟夫問題的一種描述為：編號1,2,n一圈，密碼(正整數(shù))。一開始任選一個(gè)報(bào)數(shù)上限的n個(gè)人按順時(shí)針方向圍坐每個(gè)人持有一個(gè)m,從第一個(gè)人開始順時(shí)針自1開始順序報(bào)數(shù),報(bào)到m時(shí)停止報(bào)數(shù)報(bào)m的人由列，將他的密碼作為

8、新的m值，從他在順時(shí)針方向上的下求生6,1,4,7,2,3,5一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部由列為止。試設(shè)計(jì)一個(gè)程由列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照由列順序打印由各人的編o例如m的初值為20;n=7,7個(gè)人的密碼依次是：3,1,7,2,4,8,4,由列順序?yàn)椤窘獯稹克惴ㄈ缦拢簍ypedefstructNode(intpassword;intnum;structNode*next;Node,*Linklist;voidJosephus()LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(sizeof(Nod

9、e);if(L=NULL)printf("n/*初始化單向循環(huán)*/鏈表鏈表申請不到空間！");return;L->next=NULL;r=L;printf("請輸入數(shù)據(jù)n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j+)/*建立鏈表*/p=(Node*)malloc(sizeof(Node);if(p!=NULL)printf("請輸入第%d個(gè)人的密碼:",j);scanf("%d",&C);p->password=C;p

10、->num=j;r->next=p;r=p;r->next=L->next;printf("請輸入第一個(gè)報(bào)數(shù)上限值m(m>0):");scanf("%d",&m);printf("*n");printf("由列的順序?yàn)椋簄");q=L;p=L->next;while(n!=1)/*計(jì)算由列的順*/序j=1;while(j<m)/*計(jì)算當(dāng)前由列的人選p*/q=p；/*為當(dāng)前結(jié)p的前驅(qū)結(jié)*/q點(diǎn)點(diǎn)p=p->next;j+；m=p->password;/*獲得

11、新密*/碼/*由列*/n-；q->next=p->next;r=p;p=p->next;free(r);printf("%dn",p->num);2.7試分別以不同的存儲結(jié)構(gòu)實(shí)現(xiàn)單線表的就地逆置算法，即在原表的存儲空間將線性表(a1,a2,an)逆置為(an,an-1,a1)【解答】(1)用一維數(shù)組作為存儲結(jié)構(gòu)voidinvert(SeqList*L,int*num)intj;ElemTypetmp;for(j=0;j<=(*num-1)/2;j+)tmp=Lj;Lj=L*num-j-1;L*num-j-1=tmp;(2)用單鏈表作為存儲結(jié)構(gòu)r

12、=q->next;voidinvert(LinkListL)Node*p,*q,*r;if(L->next=NULL)p=L->next;return;/*鏈表為*/空q=p->next;p->next=NULL;while(q!=NULL)/*摘下第一個(gè)結(jié)點(diǎn)，生成初始逆置表/*從第二個(gè)結(jié)點(diǎn)起依次頭插入當(dāng)前逆置表/*/q->next=L->next;L->next=q;q=r;2.11將線性表A=(a1,a2,am),B=(b1,b2,am,bm,bm+1,.bn)當(dāng)m<=n時(shí)，或C=(a1,b1,A、B、C以單鏈表作為存儲結(jié)構(gòu)，C表利且用

13、,bn)合并成線性表C,C=(a1,b1,an,bn,an+1,am)當(dāng)m>n時(shí),線性表A表B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈和表的長度值m和n均未顯式存儲?！窘獯稹克惴ㄈ缦拢篖inkListmerge(LinkListA,LinkListB,LinkListC)Node*pa,*qa,*pb,*qb,*p;pa=A->next;/*pa表示A的當(dāng)前結(jié)點(diǎn)*/pb=B->next;A的頭結(jié)*/點(diǎn)p=A;/*利用p來指向新連接的表的表尾，初始值指向表while(pa!=NULL&&pb!=NULL)/*利用尾插法建立連接之后的*/鏈表qa=pa->next;q

14、b=qb->next;p->next=pa;/*交替選擇表A和表B中的結(jié)點(diǎn)連接到新鏈表*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;)if(pa!=NULL)p->next=pa;/*A的長度大于B的長度*/if(pb!=NULL)p->next=pb;/*B的長度大于A的長度*/C=A;Return(C);)提示：第2章線性表習(xí)題2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。2.2 填空：(1)在順序表中插入或刪除一個(gè)元素，需要平均移動半元素，具體移動的元素個(gè)數(shù)與插入或刪除的位置有關(guān)。(2)在順序表中，邏輯上相鄰的元素，其物

15、理位置相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。(3)在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲位置由指示，首元素結(jié)點(diǎn)的存儲位置由指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲位置由其直接前趨的next域指示。2.3 已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是：(4)、(1)ob.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是：(7)、(11)、(8)、(4)、c.在表首插入S結(jié)點(diǎn)的語句序列是：(5)、(12)。(11)、(9)、d.在表尾插入S結(jié)點(diǎn)的語句序列是:(1)、(6)。供選擇的語句有：1.

16、P->next=S;2. P->next=P->next->next;3. P->next=S->next;4. S->next=P->next;5. S->next=L;6. S->next=NULL;7. Q=P;8. while(P->next!=Q)P=P->next;9. while(P->next!=NULL)P=P->next;10. P=Q;11. P=L;12. L=S;13. L=P;已知線性表L遞增有序。試寫一算法，將X插入到L的適當(dāng)位置上，以保持線性表L的有序性。提示:voidinser

17、t(SeqList*L;ElemTypex)<方法1>(1)我由應(yīng)插入位置i,(2)移位，(3),<方法2>參P.229寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。提示：注意檢查i和k的合法性。(集體搬遷，“新房”、“舊房”)<方法1>以待移動元素下標(biāo)m(“舊房號”)為中心，計(jì)算應(yīng)移入位置(“新房號”)：for(m=i1+k;m<=L>last;m+)L>elemmk=L>elemm;<方法2>同時(shí)以待移動元素下標(biāo)m和應(yīng)移入位置j為中心：<方法3>以應(yīng)移入位置j為中心，計(jì)算待移動元素下標(biāo)：2.6已知線性

18、表中的元素(整數(shù))以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素(若表中存在這樣的元素),分析你的算法的時(shí)間復(fù)雜度(注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù))。提示:注意檢查mink和maxk的合法性：mink<maxk不要一個(gè)一個(gè)的刪除(多次修改next域)。(1)找到第一個(gè)應(yīng)刪結(jié)點(diǎn)的前驅(qū)prepre=L;p=L>next;while(p!=NULL&&p>data<=mink)pre=p;p=p>next;(2)找到最后一個(gè)應(yīng)刪結(jié)點(diǎn)的后繼s,邊找邊釋放應(yīng)刪結(jié)點(diǎn)s=p;

19、while(s!=NULL&&s>data<maxk)t=s;s=s>next;free(t);(3)pre>next=s;2.7試分別以不同的存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表(a1,a2，an)逆置為(an,an-1,，a1)。以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中。以單鏈表作存儲結(jié)構(gòu)。方法1:在原頭結(jié)點(diǎn)后重新頭插一遍方法2:可設(shè)三個(gè)同步移動的指針p,q,r，將q的后繼r改為p假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B,均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個(gè)按元

20、素值遞減有序的排列的線性表C,并要求利用原表(即A表和B表的)結(jié)點(diǎn)空間存放C.表提示:參P.28例2-1<方法1>voidmerge(LinkListA;LinkListB;LinkList*C)?pa=A>next;pb=B>next;*C=A;(*C)>next=NULL;while(pa!=NULL&&pb!=NULL)if(pa>data<=pb>data)smaller=pa;pa=pa>next;smaller>next=(*C)>next;/*頭插法*/(*C)>next=smaller;el

21、sesmaller=pb;pb=pb>next;smaller>next=(*C)>next;(*C)>next=smaller;while(pa!=NULL)smaller=pa;pa=pa>next;smaller>next=(*C)>next;(*C)>next=smaller;while(pb!=NULL)smaller=pb;pb=pb>next;smaller>next=(*C)>next;(*C)>next=smaller;merge(LinkListA;LinkListB)<方法2>LinkLi

22、st?LinkListCpa=A>next;pb=B>next;C=A;C>next=NULL;retuC;rn假設(shè)有一個(gè)循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點(diǎn)也無頭指針。已s為指向知鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。提示:設(shè)指p指s結(jié)點(diǎn)的前趨的前趨，ps有何關(guān)系？針向則與已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如字母字符、數(shù)字字符和其它字符)，試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。設(shè)線性表A=(a1,a2,am),B=(b1,b2,bn)，試寫一個(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)b表中的結(jié)點(diǎn)空間構(gòu)成。注當(dāng)m>n時(shí)。線性表A、B、C均以單鏈表作為