北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)編程練習(xí)答案

《北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)編程練習(xí)答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)編程練習(xí)答案（95頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1.一元多項(xiàng)式相加(10分) 成績(jī): 10 / 折扣: 0.8 題目說(shuō)明： 編寫(xiě)一元多項(xiàng)式加法運(yùn)算程序。要求用線性鏈表存儲(chǔ)一元多項(xiàng)式（參照課本）。該程序有以下幾個(gè)功能： 1. 多項(xiàng)式求和 輸入：輸入三個(gè)多項(xiàng)式，建立三個(gè)多項(xiàng)式鏈表Pa、Pb、Pc （提示：調(diào)用CreatePolyn(polynomial &P,int m)。 輸出：顯示三個(gè)輸入多項(xiàng)式Pa、Pb、Pc、和多項(xiàng)式Pa+Pb、多項(xiàng)式Pa+Pb+Pc （提示：調(diào)用AddPolyn(polynomial &Pa, polynomial Pb), 調(diào)用PrintPolyn(polynomial P))。 0. 退出 輸入： 根據(jù)所選功能的不同，輸入格式要求如下所示（第一個(gè)數(shù)據(jù)是功能選擇編號(hào)，參見(jiàn)測(cè)試用例）： 1 多項(xiàng)式A包含的項(xiàng)數(shù)，以指數(shù)遞增的順序輸入多項(xiàng)式A各項(xiàng)的系數(shù)（整數(shù)）、指數(shù)（整數(shù)） 多項(xiàng)式B包含的項(xiàng)數(shù)，以指數(shù)遞增的順序輸入多項(xiàng)式B各項(xiàng)的系數(shù)（整數(shù)）、指數(shù)（整數(shù)） 多項(xiàng)式C包含的項(xiàng)數(shù)，以指數(shù)遞增的順序輸入多項(xiàng)式C各項(xiàng)的系數(shù)（整數(shù)）、指數(shù)（整數(shù)） 0 －－－操作終止，退出。 輸出： 對(duì)應(yīng)一組輸入，輸出一次操作的結(jié)果（參見(jiàn)測(cè)試用例）。 1 多項(xiàng)式輸出格式：以指數(shù)遞增的順序輸出: <系數(shù),指數(shù)>,<系數(shù),指數(shù)>,<系數(shù),指數(shù)>,參見(jiàn)測(cè)試用例。零多項(xiàng)式的輸出格式為<0,0> 0 無(wú)輸出 1. #include #include using std::cin; using std::cout; using std::endl; struct date { int a; int b; struct date* pnext; }; typedef struct date DATE; typedef struct date* PDATE; void output(PDATE p) { int f=0; p=p->pnext; while(p!=NULL) { if(p->a!=0) { f=1; cout<<"<"<a<<","<b<<">"; if(p->pnext==NULL) cout<pnext; } if(f==0) cout<<"<0,0>"<pnext; //skip head if(p2!=NULL) p2=p2->pnext; while((p1!=NULL)&&(p2!=NULL)) { if(p1->b>p2->b) { p3->pnext=(PDATE)malloc(sizeof(DATE)); p3=p3->pnext; p3->a=p2->a; p3->b=p2->b; p3->pnext=NULL; p2=p2->pnext; } else if(p1->bb) { p3->pnext=(PDATE)malloc(sizeof(DATE)); p3=p3->pnext; p3->a=p1->a; p3->b=p1->b; p3->pnext=NULL; p1=p1->pnext; } else { p3->pnext=(PDATE)malloc(sizeof(DATE)); p3=p3->pnext; p3->a=p1->a+p2->a; p3->b=p1->b; p3->pnext=NULL; p1=p1->pnext; p2=p2->pnext; } }//end while if(p1==NULL) p3->pnext=p2; if(p2==NULL) p3->pnext=p1; } int main() { int flag; int n; PDATE P[6]={NULL}; PDATE p=NULL; for(int i=0;i<6;i++) { P[i]=(PDATE)malloc(sizeof(DATE)); P[i]->a=0; P[i]->b=0; P[i]->pnext=NULL; } cin>>flag; if(flag==1) { for(int i=1;i<4;i++) { p=P[i]; cin>>n; while(n--!=0) { p->pnext=(PDATE)malloc(sizeof(DATE)); p=p->pnext; cin>>p->a>>p->b; p->pnext=NULL; } output(P[i]); } } add(P[1],P[2],P[4]); output(P[4]); add(P[4],P[3],P[5]); output(P[5]); }  0 約瑟夫問(wèn)題(10分) 成績(jī): 10 / 折扣: 0.8 0 約瑟夫問(wèn)題 成績(jī)10分 折扣0.8 (本題要求用循環(huán)鏈表實(shí)現(xiàn)) 0 ,1, 2, 3題,只能選做三題. 約瑟夫問(wèn)題是一個(gè)經(jīng)典的問(wèn)題。已知n個(gè)人（不妨分別以編號(hào)1，2，3，…，n 代表）圍坐在一張圓桌周?chē)?，從編?hào)為 k 的人開(kāi)始，從1開(kāi)始順時(shí)針報(bào)數(shù)1, 2, 3, ...，順時(shí)針數(shù)到m 的那個(gè)人，出列并輸出。然后從出列的下一個(gè)人開(kāi)始，從1開(kāi)始繼續(xù)順時(shí)針報(bào)數(shù)，數(shù)到m的那個(gè)人，出列并輸出，…依此重復(fù)下去，直到圓桌周?chē)娜巳砍隽小? 輸入：n,k,m 輸出：按照出列的順序依次輸出出列人的編號(hào)，編號(hào)中間相隔一個(gè)空格,每10個(gè)編號(hào)為一行。 非法輸入的對(duì)應(yīng)輸出如下 a) 輸入：：n、k、m任一個(gè)小于1 輸出：n,m,k must bigger than 0. b) 輸入：k>n 輸出：k should not bigger than n. 例 輸入 9,3,2 輸出 4 6 8 1 3 7 2 9 5 #include #include #include struct date { int a; struct date* next; }; typedef struct date DATE; typedef struct date* PDATE; PDATE setnew(PDATE p,int a) { PDATE pt; pt=(PDATE) malloc (sizeof(DATE)); pt->a=a; pt->next=p->next; p->next=pt; return pt; } int count; PDATE del(PDATE p0) { if(!count) { printf("\n"); count=10; } printf("%d ",p0->a); PDATE p=p0->next; p0->a=p->a; p0->next=p->next; free(p); count--; return p0; } int main() { count=10; int n=0,k=0,m=0; scanf("%d,%d,%d",&n,&m,&k); if(!(n>0&&m>0&&k>0)) printf("n,m,k must bigger than 0.\n"); else if(m>n) printf("k should not bigger than n.\n"); else { PDATE p=NULL; PDATE head=(DATE *)malloc(sizeof(DATE)); head->next=head; head->a=1; p=head; for(int i=2;i<=n;i++) p=setnew(p,i); while(p->a!=m) p=p->next; while(n) { // int temp=k; int temp=k%n+n; while(--temp) p=p->next; del(p); n--; } printf("\n"); } }  2. 綜教樓后的那個(gè)坑 成績(jī): 10 / 折扣: 0.8 描述 　　在 LIT 綜教樓后有一個(gè)深坑，關(guān)于這個(gè)坑的來(lái)歷，有很多種不同的說(shuō)法。其中一種說(shuō)法是，在很多年以前，這個(gè)坑就已經(jīng)在那里了。這種說(shuō)法也被大多數(shù)人認(rèn)可，這是因?yàn)樵摽佑幸环N特別的結(jié)構(gòu)，想要人工建造是有相當(dāng)困難的。 　　從橫截面圖來(lái)看，坑底成階梯狀，由從左至右的 1..N 個(gè)的平面構(gòu)成（其中 1 ≤ N ≤ 100,000），如圖： 　　?。　　　　　　　　　　　。?: 　　?。　　　　　　　　　　　。?: 　　?。　　　　　　　　　　　。?8 　　?。　　　。　　　　　。?7 　　?。　　　。　　　　　。?6 　　?。　　　。　　　　　。?5 　　　＊　　　?。?4 <- 高度 　　?。　　　。?3 　　?。?2 　　?。?1 平面?。?1　 ｜2｜　　　3　　　 ｜ 每個(gè)平面 i 可以用兩個(gè)數(shù)字來(lái)描述，即它的寬度 Wi 和高度 Hi，其中 1 ≤ Wi ≤ 1,000、1 ≤ Hi ≤ 1,000,000，而這個(gè)坑最特別的地方在于坑底每個(gè)平面的高度都是不同的。每到夏天，雨水會(huì)把坑填滿(mǎn)，而在其它的季節(jié)，則需要通過(guò)人工灌水的方式把坑填滿(mǎn)。灌水點(diǎn)設(shè)在坑底位置最低的那個(gè)平面，每分鐘灌水量為一個(gè)單位（即高度和寬度均為 1）。隨著水位的增長(zhǎng)，水自然會(huì)向其它平面擴(kuò)散，當(dāng)水將某平面覆蓋且水高達(dá)到一個(gè)單位時(shí)，就認(rèn)為該平面被水覆蓋了。 　　請(qǐng)你計(jì)算每個(gè)平面被水覆蓋的時(shí)間。 　　 灌水 水滿(mǎn)后自動(dòng)擴(kuò)散 | | * | * * | * * * * V * * V * * * * * * .... * *~~~~~~~~~~~~* * ** * *~~~~** : * *~~~~**~~~~~~* * ** * *~~~~** : * *~~~~**~~~~~~* * ** * *~~~~**~~~~~~* *~~~~**~~~~~~* * ********* *~~~~********* *~~~~********* *~~~~********* *~~~~********* *~~~~********* ************** ************** ************** ************** ************** ************** 　　　4 分鐘后 　　　26 分鐘后 　　　　　　　50 分鐘后 　　　平面 1 被水覆蓋 　　　　平面 3 被水覆蓋　　　　平面 2 被水覆蓋輸入 　　輸入的第一行是一個(gè)整數(shù) N，表示平面的數(shù)量。從第二行開(kāi)始的 N 行上分別有兩個(gè)整數(shù)，分別表示平面的寬度和高度。 輸出 　　輸出每個(gè)平面被水覆蓋的時(shí)間。 #include #include struct date { long long * timedate; long h; int w; struct date* pl; struct date* pr; }; typedef struct date DATE; typedef struct date* PDATE; PDATE setnew(PDATE p0,int w,long h,long long * num)//p0為左鄰 { PDATE p=(PDATE) malloc(sizeof(DATE)); p->timedate=num; p->pl=p0; p->pr=NULL; p0->pr=p; p->h=h; p->w=w; return p; } void output(long long* p,long n) { while(n--) printf("%lld\n",*(++p)); } int main() { long long myclock; long n; int w; long h; PDATE p=NULL,pt=NULL; //set leftp PDATE left=(PDATE) malloc(sizeof(DATE)); left->timedate=NULL; left->pl=NULL; left->pr=NULL; left->h=1000000; left->w=0; p=left; pt=left; scanf("%d",&n); long long* timedate=new long long[n+1]; for(long i=0;i>w>>h; scanf("%d%d",&w,&h); p=setnew(p,w,h,timedate+i+1); if(pt->h>h) pt=p; } PDATE right=setnew(p,0,1000000,NULL); p=pt; myclock=0; while(p->pl->h!=p->pr->h) { *(p->timedate)=myclock+p->w; //計(jì)算時(shí)間并刪除合并 if(p->pl->h>p->pr->h) { myclock+=(p->pr->h-p->h)*p->w; p->pr->w+=p->w; p->pl->pr=p->pr; p->pr->pl=p->pl; pt=p; p=p->pr; delete pt; } else if(p->pl->hpr->h) { myclock+=(p->pl->h-p->h)*p->w; p->pl->w+=p->w; p->pl->pr=p->pr; p->pr->pl=p->pl; pt=p; p=p->pl; delete pt; } //移至下一進(jìn)水點(diǎn) if(p->pl->h>p->h&&p->pr->h>p->h) continue; else if(p->pl->hpr->h)//左移 { while(p->h>p->pl->h) p=p->pl; } else //右移 { while(p->h>p->pr->h) p=p->pr; } } myclock+=p->w; *(p->timedate)=myclock; output(timedate,n); }  3. 單詞壓縮存儲(chǔ)(10分) 成績(jī): 10 / 折扣: 0.8 如果采用單鏈表保存單詞，可采用如下辦法壓縮存儲(chǔ)空間。如果兩個(gè)單詞的后綴相同，則可以用同一個(gè)存儲(chǔ)空間保存相同的后綴。例如，原來(lái)分別采用單鏈表保存的單詞Str1“abcdef”和單詞Str2“dbdef”，經(jīng)過(guò)壓縮后的存儲(chǔ)形式如下。 請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效的算法完成兩個(gè)單鏈表的壓縮存儲(chǔ)，并估計(jì)你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。 要求：閱讀預(yù)設(shè)代碼，編寫(xiě)函數(shù)SNODE * ziplist( SNODE * head1, SNODE * head2 ) ziplist的功能是：在兩個(gè)串鏈表中，查找公共后綴，若有公共后綴，則壓縮 并返回指向公共后綴的指針；否則返回NULL 預(yù)設(shè)代碼 前置代碼 view plaincopy to clipboardprint? 1. /*PRESETCODEBEGIN-NEVERTOUCHCODEBELOW*/ 2. 3. #include 4. #include 5. 6. typedefstructsdata 7. {chardata; 8. structsdata*next; 9. }SNODE; 10. 11. voidsetlink(SNODE*,char*),outlink(SNODE*); 12. intlistlen(SNODE*); 13. SNODE*ziplist(SNODE*,SNODE*); 14. SNODE*findlist(SNODE*,SNODE*); 15. 16. intmain() 17. { 18. SNODE*head1,*head2,*head; 19. charstr1[100],str2[100]; 20. 21. gets(str1); 22. gets(str2); 23. 24. head1=(SNODE*)malloc(sizeof(SNODE)); 25. head2=(SNODE*)malloc(sizeof(SNODE)); 26. head=(SNODE*)malloc(sizeof(SNODE)); 27. head->next=head1->next=head2->next=NULL; 28. 29. setlink(head1,str1); 30. setlink(head2,str2); 31. 32. head->next=ziplist(head1,head2); 33. 34. head->next=findlist(head1,head2); 35. outlink(head); 36. return0; 37. } 38. 39. voidsetlink(SNODE*head,char*str) 40. { 41. SNODE*p; 42. 43. while(*str!=\0) 44. {p=(SNODE*)malloc(sizeof(SNODE)); 45. p->data=*str; 46. p->next=NULL; 47. str++; 48. head->next=p; 49. head=p; 50. } 51. return; 52. } 53. 54. voidoutlink(SNODE*head) 55. { 56. while(head->next!=NULL) 57. { 58. printf("%c",head->next->data); 59. head=head->next; 60. } 61. printf("\n"); 62. return; 63. } 64. 65. intlistlen(SNODE*head) 66. { 67. intlen=0; 68. while(head->next!=NULL) 69. { 70. len++; 71. head=head->next; 72. } 73. returnlen; 74. } 75. 76. SNODE*findlist(SNODE*head1,SNODE*head2) 77. { 78. intm,n; 79. SNODE*p1=head1,*p2=head2; 80. 81. m=listlen(head1); 82. n=listlen(head2); 83. 84. while(m>n) 85. {p1=p1->next; 86. m--; 87. } 88. while(mnext; 90. n--; 91. } 92. 93. while(p1->next!=NULL&&p1->next!=p2->next) 94. { 95. p1=p1->next; 96. p2=p2->next; 97. } 98. returnp1->next; 99. } 100. 101. /*Hereiswaitingforyou!*/ 102. /* 103. SNODE*ziplist(SNODE*head1,SNODE*head2) 104. { 105. } 106. */ 107. 108. /*PRESETCODEEND-NEVERTOUCHCODEABOVE*/ SNODE * ziplist( SNODE * head1, SNODE * head2 ) { int m, n; SNODE *p1=head1, *p2=head2,*p11=NULL,*p22=NULL; m = listlen( head1 ); n = listlen( head2 ); while ( m > n ) { p1 = p1->next; m--; } while ( m < n ) { p2 = p2->next; n--; } p11=p1; p22=p2; while(p1->next->next!=NULL) { if(p1->next->data!=p2->next->data) { p11=p1->next; p22=p2->next; } p1=p1->next; p2=p2->next; } if(p1->next->data!=p2->next->data) return NULL; else { p22->next=p11->next; return p11->next; } }  4. 括號(hào)匹配（10分） 成績(jī): 10 / 折扣: 0.8 4 括號(hào)匹配 （10分） 成績(jī): 10 / 折扣: 0.8 假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)兩種類(lèi)型的括號(hào)，試編寫(xiě)一個(gè)判斷表達(dá)式中括號(hào)是否匹配的程序，匹配返回Match succeed!，否則返回Match false!。 例 [1+2*(3+4*(5+6))]括號(hào)匹配 (1+2)*(1+2*[(1+2)+3) 括號(hào)不匹配 輸入 包含圓括號(hào)、方括號(hào)兩種類(lèi)型括號(hào)的算術(shù)表達(dá)式 輸出 匹配輸出 Match succeed! 不匹配輸出 Match false! 例 輸入 [1+2* (3+4*(5+6))] 輸出Match succeed! #include int main() { int flag=0; char a[1000]={0}; char* p; p=&a[0]; char temp; temp=getchar(); *p=temp; while(temp!=\n) { switch (temp) { case (: { p++; *p=temp; break; } case ): { if(*p!=() { printf("Match false!\n"); return 0; } *p=0; p--; break; } case [: { p++; *p=temp; break; } case]: { if(*p!=[) { printf("Match false!\n"); return 0; } *p=0; p--; break; } }//endswiych temp=getchar(); }//end whilw printf("Match succeed!\n"); return 0; }  5. 迷宮問(wèn)題（15分） 成績(jī): 15 / 折扣: 0.8 5 迷宮問(wèn)題（15分） 成績(jī): 15 / 折扣: 0.8 迷宮有一個(gè)入口，一個(gè)出口。一個(gè)人從入口走進(jìn)迷宮，目標(biāo)是找到出口。陰影部分和迷宮的外框?yàn)閴?，每一步走一格，每格有四個(gè)可走的方向，探索順序?yàn)椋耗稀|、北、西。 輸入：輸入迷宮數(shù)組 輸出：若有解，輸出從入口到出口的一條路徑，否則輸出 there is no solution! 例（上圖所示的迷宮數(shù)組） 輸入 4 4 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 輸出 <1,1> <2,1> <3,1> <3,2> <3,3> <4,3> <4,4> #include using std::cin; using std::cout; using std::endl; int main() { int a,b; cin>>a>>b; bool date[102][102]; for(int i=0;i<102;i++) for (int j=0;j<102;j++) date[i][j]=1; int stack[500][4]={0}; int p=1; stack[0][2]=5; stack[1][0]=1; stack[1][1]=1; stack[1][3]=5; for(int x=1;x<=a;x++)//input start { for(int y=1;y<=b;y++) { bool temp; cin>>temp; date[x][y]=temp; } }//input finish int p1,p2; while(!(stack[p][0]==a&&stack[p][1]==b))//find start { switch (stack[p][2]) { case 0://down { if(stack[p][2]==stack[p][3]) { stack[p][2]++; break; } p1=stack[p][0]+1; p2=stack[p][1]; if(date[p1][p2])//wall { stack[p][2]++; goto x1; } else//road { stack[p][2]++; p++; stack[p][0]=p1; stack[p][1]=p2; stack[p][3]=2; break; } } case 1://right { x1: if(stack[p][2]==stack[p][3]) { stack[p][2]++; break; } p1=stack[p][0]; p2=stack[p][1]+1; if(date[p1][p2])//wall { stack[p][2]++; goto x2; } else//road { stack[p][2]++; p++; stack[p][0]=p1; stack[p][1]=p2; stack[p][3]=3; break; } } case 2://up { x2: if(stack[p][2]==stack[p][3]) { stack[p][2]++; break; } p1=stack[p][0]-1; p2=stack[p][1]; if(date[p1][p2])//wall { stack[p][2]++; goto x3; } else//road { stack[p][2]++; p++; stack[p][0]=p1; stack[p][1]=p2; stack[p][3]=0; break; } } case 3://left { x3: if(stack[p][2]==stack[p][3]) { stack[p][2]++; break; } p1=stack[p][0]; p2=stack[p][1]-1; if(date[p1][p2])//wall { stack[p][2]++; goto x4; } else//road { stack[p][2]++; p++; stack[p][0]=p1; stack[p][1]=p2; stack[p][3]=1; break; } } case 4://back { x4: stack[p][2]=0; p--; break; } case 5: { cout<<"there is no solution!\n"; return 0; } } }//find finish p=1; while(stack[p][2]) { cout<<"<"< "; p++; } cout<<"<"< "< #include int time,wayn,downtime,uptime,up,down,upwaiting,downwaiting,upcount,downcount,use; int* way; float* waytime; int manage() { for(int i=1;i<=wayn;i++) { if(*(way+i)==0) { use--; if(downwaiting>0) { *(way+i)=downtime; (*(waytime+i))+=downtime; printf("airplane %04d is ready to land on runway %02d\n",downcount++,i); downwaiting--; use++; } else if(upwaiting>0) { *(way+i)=uptime; (*(waytime+i))+=uptime; printf("airplane %04d is ready to takeoff on runway %02d\n",upcount++,i); upwaiting--; use++; } else *(way+i)=-1; } else if(*(way+i)<0) { if(downwaiting>0) { *(way+i)=downtime; (*(waytime+i))+=downtime; printf("airplane %04d is ready to land on runway %02d\n",downcount++,i); downwaiting--; use++; } else if(upwaiting>0) { *(way+i)=uptime; (*(waytime+i))+=uptime; printf("airplane %04d is ready to takeoff on runway %02d\n",upcount++,i); upwaiting--; use++; } } }//end of for return 0; } int main() { float avewaitingup=0; float avewaitingdown=0; scanf("%d%d%d",&wayn,&downtime,&uptime); way=(int*) malloc (sizeof(int)*(wayn+1)); waytime=(float*) malloc (sizeof(float)*(wayn+1)); for(int i=0;i<=wayn;i++) { *(way+i)=-1; *(waytime+i)=0; } downcount=5001; upcount=1; use=0; printf("Current Time: 0\n"); scanf("%d%d",&down,&up); for(time=1;up>=0&&down>=0;) { upwaiting+=up; downwaiting+=down; manage(); avewaitingup+=upwaiting; avewaitingdown+=downwaiting; for(int i=0;i<=wayn;i++) (*(way+i))--; printf("Current Time: %4d\n",time++); for(int i=1;i<=wayn;i++) { if(*(way+i)==0) { printf("runway %02d is free\n",i); } } scanf("%d%d",&down,&up); } manage(); avewaitingup+=upwaiting; avewaitingdown+=downwaiting; while(use) { for(int i=0;i<=wayn;i++) (*(way+i))--; printf("Current Time: %4d\n",time++); for(int i=1;i<=wayn;i++) { if(*(way+i)==0) { printf("runway %02d is free\n",i); } } manage(); avewaitingup+=upwaiting; avewaitingdown+=downwaiting; } time--; //finish printf("simulation finished\nsimulation time: %4d\n",time); float aa=avewaitingdown/(downcount-5000-1),bb=avewaitingup/(upcount-1),cc=0; if(avewaitingdown==0||downcount==5001) aa=0; if(avewaitingup==0||upcount==1) bb=0; printf("average waiting time of landing: %4.1f\naverage waiting time of takeoff: %4.1f\n",aa,bb); float all=0; int i=1; for(;i<=wayn;i++) { printf("runway %02d busy time: %4.0f\n",i,*(waytime+i)); all+=*(waytime+i); } if(all==0||time==0||wayn==0) cc=0; else cc=all/wayn/time*100;