數(shù)據(jù)結(jié)構(gòu)第二版習(xí)題答案第3章

1、3.1 選擇題第 3 章線性表的鏈式存儲（1）兩個有序線性表分別具有 n 個元素與 m 個元素且 nm，現(xiàn)將其歸并成一個有序表，其最少的比較次數(shù)是（a ）。anbmcn 1dm + n（2）非空的循環(huán)單鏈表 head 的尾結(jié)點（由 p 所指向）滿足（c）。ap-next=null bp=null cp-next=head dp=head（3）在帶頭結(jié)點的單鏈表中查找 x 應(yīng)選擇的程序體是（c ）。anode *p=head-next; while (p & p-info!=x) p=p-next; if (p-info=x) return p else return null;bnode *p

2、=head; while (p& p-info!=x) p=p-next; return p;cnode *p=head-next; while (p&p-info!=x) p=p-next; return p;dnode *p=head; while (p-info!=x) p=p-next ; return p; （4）線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（d ）。a必須是連續(xù)的c一定是不連續(xù)的b部分地址必須是連續(xù)的d連續(xù)不連續(xù)都可以（5）在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持單鏈表仍然有序的時間復(fù)雜度是（b ）。ao(1) bo(n)co(n2)do

3、(nlog2n)（6）用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時（d ）。a僅修改隊頭指針c隊頭、隊尾指針都要修改b僅修改隊尾指針d隊頭,隊尾指針都可能要修改（7）若從鍵盤輸入 n 個元素，則建立一個有序單向鏈表的時間復(fù)雜度為（b ）。ao(n)bo(n2)co(n3)do(n log2n)（8）下面哪個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)（d ）。a順序表b鏈表c散列表d隊列（9）在一個單鏈表中，若刪除 p 所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（a ）。ap-next=p-next-next; bp=p-next; p-next=p-next-next; c

4、p-next=p-next; dp =p-next-next;（10）在一個單鏈表中，若 p 所指結(jié)點不是最后結(jié)點，在 p 之后插入 s 所指結(jié)點，則執(zhí)行（ b ）。as-next=p;p-next=s; bs-next=p-next;p-next=s;cs-next=p-next;p=s; dp-next=s;s-next=p;3.2 設(shè)計一個算法，求一個單鏈表中的結(jié)點個數(shù)?！敬稹浚簡捂湵泶鎯Y(jié)構(gòu)定義如下（相關(guān)文件：linklist.h）#include 11 #include typedef struct node int data; struct node *next;linknode;

5、typedef linknode *linklist;/*尾插法創(chuàng)建帶頭結(jié)點的單鏈表*/linklist creatlinklist() linklist head,r,x,s; head=r=(linklist)malloc(sizeof(linknode); printf(n 請輸入一組以 0 結(jié)束的整數(shù)序列：n); scanf(%d,&x); while (x) s=(linklist)malloc(sizeof(linknode); s-data=x; r-next=s; r=s; scanf(%d,&x); r-next=null; return head;/*輸出帶頭結(jié)點的單鏈表*

6、/ void print(linklist head) linklist p; p=head-next; printf(list is:n); while(p) printf(%5d,p-data); p=p-next; printf(n);基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點個數(shù)的算法程序如下：int count(linklist head) int c=0; linklist p=head; while (p) c+; 12 p=p-next; return c;3.3 設(shè)計一個算法，求一個帶頭結(jié)點單鏈表中的結(jié)點個數(shù)。【答】：帶頭結(jié)點的單鏈表的存儲結(jié)構(gòu)定義同題 3.2，實現(xiàn)本題功能的算法程序

7、如下（3_3.c）#include linklist.h int count(linklist head) int c=0; linklist p=head-next; while (p) c+; p=p-next; return c;main()/*測試函數(shù)*/linklist head; head=creatlinklist(); print(head); printf(nlength of head is:%d,count(head); getch();當輸入 5 個數(shù)據(jù)時，產(chǎn)生的輸出結(jié)果如下圖所示：3.4 設(shè)計一個算法，在一個單鏈表中值為 y 的結(jié)點前面插入一個值為 x 的結(jié)點。即使值

8、為 x 的新結(jié)點成為值為 y 的結(jié)點的前驅(qū)結(jié)點。【答】：#include linklist.h void insert(linklist head,int y,int x)/*在值為 y 的結(jié)點前插入一個值為 x 的結(jié)點*/ linklist pre,p,s; pre=head; p=head-next;13 while (p & p-data!=y) pre=p; p=p-next; if (p)/*找到了值為 y 的結(jié)點*/ s=(linklist)malloc(sizeof(linknode); s-data=x; s-next=p; pre-next=s; void main()lin

9、klist head; int y,x;/*測試程序*/ head=creatlinklist(); /*創(chuàng)建單鏈表*/ print(head); /*輸出單鏈表*/ printf(n 請輸入 y 與 x 的值:n); scanf(%d %d,&y,&x); insert(head,y,x); print(head); 程序的一種運行結(jié)果如下圖所示：3.5 設(shè)計一個算法，判斷一個單鏈表中各個結(jié)點值是否有序?！敬稹浚?include linklist.h int issorted(linklist head,char c)/*當參數(shù) c=a時判斷鏈表是否為升序，當參數(shù) c=d是判斷鏈表是否為降序

10、*/ int flag=1; linklist p=head-next; switch (c) case a:/*判斷帶頭結(jié)點的單鏈表 head 是否為升序*/14 while (p &p-next & flag) if (p-datanext-data) p=p-next; else flag=0; break; case d:/*判斷帶頭結(jié)點的單鏈表 head 是否為降序*/ while (p &p-next & flag) if (p-data=p-next-data) p=p-next; else flag=0; break; return flag;int main() /*測試程序

11、*/ linklist head; head=creatlinklist(); print(head); if (issorted(head,a) printf(單鏈表 head 是升序排列的！n); else if (issorted(head,d) printf(單鏈表 head 是降序排列的！n); else printf(單鏈表 head 是無序的！n);程序運行時的三種輸出結(jié)果如下圖所示：3.6 設(shè)計一個算法，利用單鏈表原來的結(jié)點空間將一個單鏈表就地轉(zhuǎn)置?！敬稹浚?include linklist.h void verge(linklist head)/*本函數(shù)的功能是就地倒置帶頭結(jié)

12、點的單鏈表*/ 15 linklist p,q; p=head-next; head-next=null; while (p) q=p; p=p-next; /*每次從原表取一個結(jié)點插入到新表的最前面*/ q-next=head-next; head-next=q; int main()linklist head; /*測試函數(shù)*/ head=creatlinklist(); /*創(chuàng)建單鏈表*/ print(head); /*輸出原單鏈表*/ verge(head); /*就地倒置單鏈表*/ print(head); /*輸出倒置后的單鏈表*/3.7 設(shè)計一個算法，將一個結(jié)點值自然數(shù)的單鏈表拆

13、分為兩個單鏈表，原表中保留值為偶數(shù)的結(jié)點，而值為奇數(shù)的結(jié)點按它們在原表中的相對次序組成一個新的單鏈表?！敬稹浚?include linklist.h linklist sprit(linklist head)/*將帶頭結(jié)點的單鏈表 head 中的奇數(shù)值結(jié)點刪除生成新的單鏈表并返回*/linklist l,pre,p,r;l=r=(linklist)malloc(sizeof(linknode);r-next=null;pre=head;p=head-next;while (p)if (p-data%2=1)pre-next=p-next;r-next=p; r=p; p=pre-next; e

14、lse pre=p;p=p-next; /*刪除奇數(shù)值結(jié)點*/*保留偶數(shù)值結(jié)點*/16r-next=null; return l;/*置鏈表結(jié)束標記*/int main()linklist head,l;/*測試函數(shù)*/ head=creatlinklist(); /*創(chuàng)建單鏈表*/ print(head); /*輸出原單鏈表*/ l=sprit(head); /*分裂單鏈表 head*/ printf(n 原單鏈表為:n); print(head); /*輸出倒置后的單鏈表*/ printf(n 分裂所得奇數(shù)單鏈表為:n); print(l);本程序的一組測試情況如下圖所示。3.8 設(shè)計一個

15、算法，對一個有序的單鏈表，刪除所有值大于 x 而不大于 y 的結(jié)點?！敬稹浚?include linklist.h void deletedata(linklist head,datatype x,datatype y) /*刪除帶頭結(jié)點單鏈表中所有結(jié)點值大于 x 而不大于 y 的結(jié)點*/linklist pre=head,p,q;p=head-next;初始化*/ while (p & p-datanext; while (p & p-datanext;q=pre-next;pre-next=p;pre=q-next;/*刪除大于 x 而小于 y 的結(jié)點*/17while (pre!=p)f

16、ree(q);q=pre;pre=pre-next;/*釋放被刪除結(jié)點所占用的空間*/void main()linklist head,l;datatypex,y;/*測試函數(shù)*/head=creatlinklist();/*創(chuàng)建單鏈表*/print(head); /*輸出原單鏈表*/printf(n 請輸入要刪除的數(shù)據(jù)區(qū)間:n);scanf(%d%d,&x,&y);deletedata(head,x,y);print(head); /*輸出刪除后的單鏈表*/3.9 設(shè)計一個算法，在雙鏈表中值為 y 的結(jié)點前面插入一個值為 x 的新結(jié)點。即使值為 x 的新結(jié)點成為值為 y 的結(jié)點的前驅(qū)結(jié)點。【

17、答】：首先定義雙鏈表的數(shù)據(jù)結(jié)構(gòu)，相關(guān)文件 dlink.h，內(nèi)容如下：typedef int datatype; /*預(yù)定義的數(shù)據(jù)類型*/typedef struct dlink_node /*雙鏈表結(jié)點定義*/ datatype data; struct dlink_node *llink,*rlink; dnode; typedef dnode* dlinklist; /*雙鏈表結(jié)點指針類型定義*/*尾插法創(chuàng)建帶頭結(jié)點的雙鏈表*/dlinklist creatdlinklist(void) dlinklist head,r,s; datatype x; head=r=(dlinklist)

18、malloc(sizeof(dnode); /*建立雙鏈表的頭結(jié)點*/ head-llink=head-rlink=null; printf(n 請輸入雙鏈表的內(nèi)容：（整數(shù)序列，以 0 結(jié)束）n); scanf(%d,&x); while (x) /*輸入結(jié)點值信息，以 0 結(jié)束*/ s=(dlinklist ) malloc(sizeof(dnode); s-data=x; s-rlink=r-rlink; /*將新結(jié)點 s 插入到雙鏈表鏈尾*/ 18 s-llink=r; r-rlink=s; r=s; scanf(%d,&x); return head;/*輸出雙鏈表的內(nèi)容*/void

19、print(dlinklist head) dlinklist p; p=head-rlink; printf(n 雙鏈表的內(nèi)容是：n); while (p) printf(%5d,p-data); p=p-rlink; 本題的求解程序如下：#include #include dlink.h void insertxaty(dlinklist head,datatype y,datatype x) dlinklist s,p; /*首先在雙鏈表中找 y 所在的結(jié)點，然后在 y 前面插入新結(jié)點*/ p=head-rlink; while (p & p-data!=y) p=p-rlink; if

20、 (!p) printf(n 雙鏈表中不存在值為 y 的結(jié)點,無法插入新結(jié)點!n); else /*插入值為 x 的新結(jié)點*/ s=(dlinklist)malloc(sizeof(dnode); s-data=x; s-rlink=p; s-llink=p-llink; p-llink-rlink=s; p-llink=s; void main() dlinklist head; datatype x,y;/*測試函數(shù)*/19 head=creatdlinklist(); print(head); printf(n 請輸入要輸入的位置結(jié)點值 y:n); scanf(%d,&y); printf(n 請輸入要輸入的結(jié)點值 x:n); scanf(%d,&x); insertxaty(head,y,x);/*在值為 y 的結(jié)點前插入值為 x 的新結(jié)點*/ print(head);/*輸出新的雙鏈表*/ getch(); 本程序的一組測試情況如下圖所示。3.10 設(shè)計一個算法，從右向左打印一個雙鏈表中各個結(jié)點的值?！敬稹浚罕绢}的雙鏈表定義同題 3.9，實現(xiàn)從右向左打印雙鏈表的各個結(jié)點的值可以用遞歸程序?qū)崿F(xiàn)如下：#include #include dlink