北京理工大学数据结构编程练习答案

《北京理工大学数据结构编程练习答案》由会员分享，可在线阅读，更多相关《北京理工大学数据结构编程练习答案（95页珍藏版）》请在装配图网上搜索。

1.一元多项式相加(10分) 成绩: 10 / 折扣: 0.8 题目说明： 编写一元多项式加法运算程序。要求用线性链表存储一元多项式（参照课本）。该程序有以下几个功能： 1. 多项式求和 输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc （提示：调用CreatePolyn(polynomial &P,int m)。 输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc （提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用PrintPolyn(polynomial P))。 0. 退出 输入： 根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试用例）： 1 多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数） 多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数） 多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数） 0 －－－操作终止，退出。 输出： 对应一组输入，输出一次操作的结果（参见测试用例）。 1 多项式输出格式：以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。零多项式的输出格式为<0,0> 0 无输出 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 约瑟夫问题(10分) 成绩: 10 / 折扣: 0.8 0 约瑟夫问题 成绩10分 折扣0.8 (本题要求用循环链表实现) 0 ,1, 2, 3题,只能选做三题. 约瑟夫问题是一个经典的问题。已知n个人（不妨分别以编号1，2，3，…，n 代表）围坐在一张圆桌周围，从编号为 k 的人开始，从1开始顺时针报数1, 2, 3, ...，顺时针数到m 的那个人，出列并输出。然后从出列的下一个人开始，从1开始继续顺时针报数，数到m的那个人，出列并输出，…依此重复下去，直到圆桌周围的人全部出列。 输入：n,k,m 输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。 非法输入的对应输出如下 a) 输入：：n、k、m任一个小于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. 综教楼后的那个坑 成绩: 10 / 折扣: 0.8 描述 　　在 LIT 综教楼后有一个深坑，关于这个坑的来历，有很多种不同的说法。其中一种说法是，在很多年以前，这个坑就已经在那里了。这种说法也被大多数人认可，这是因为该坑有一种特别的结构，想要人工建造是有相当困难的。 　　从横截面图来看，坑底成阶梯状，由从左至右的 1..N 个的平面构成（其中 1 ≤ N ≤ 100,000），如图： 　　　＊　　　　　　　　　　　　＊ : 　　　＊　　　　　　　　　　　　＊ : 　　　＊　　　　　　　　　　　　＊ 8 　　　＊　　　　＊＊　　　　　　＊ 7 　　　＊　　　　＊＊　　　　　　＊ 6 　　　＊　　　　＊＊　　　　　　＊ 5 　　　＊　　　　＊＊＊＊＊＊＊＊＊ 4 <- 高度 　　　＊　　　　＊＊＊＊＊＊＊＊＊ 3 　　　＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 2 　　　＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 1 平面　｜　 1　 ｜2｜　　　3　　　 ｜ 每个平面 i 可以用两个数字来描述，即它的宽度 Wi 和高度 Hi，其中 1 ≤ Wi ≤ 1,000、1 ≤ Hi ≤ 1,000,000，而这个坑最特别的地方在于坑底每个平面的高度都是不同的。每到夏天，雨水会把坑填满，而在其它的季节，则需要通过人工灌水的方式把坑填满。灌水点设在坑底位置最低的那个平面，每分钟灌水量为一个单位（即高度和宽度均为 1）。随着水位的增长，水自然会向其它平面扩散，当水将某平面覆盖且水高达到一个单位时，就认为该平面被水覆盖了。 　　请你计算每个平面被水覆盖的时间。 　　 灌水 水满后自动扩散 | | * | * * | * * * * V * * V * * * * * * .... * *~~~~~~~~~~~~* * ** * *~~~~** : * *~~~~**~~~~~~* * ** * *~~~~** : * *~~~~**~~~~~~* * ** * *~~~~**~~~~~~* *~~~~**~~~~~~* * ********* *~~~~********* *~~~~********* *~~~~********* *~~~~********* *~~~~********* ************** ************** ************** ************** ************** ************** 　　　4 分钟后 　　　26 分钟后 　　　　　　　50 分钟后 　　　平面 1 被水覆盖 　　　　平面 3 被水覆盖　　　　平面 2 被水覆盖输入 　　输入的第一行是一个整数 N，表示平面的数量。从第二行开始的 N 行上分别有两个整数，分别表示平面的宽度和高度。 输出 　　输出每个平面被水覆盖的时间。 #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; //计算时间并删除合并 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; } //移至下一进水点 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. 单词压缩存储(10分) 成绩: 10 / 折扣: 0.8 如果采用单链表保存单词，可采用如下办法压缩存储空间。如果两个单词的后缀相同，则可以用同一个存储空间保存相同的后缀。例如，原来分别采用单链表保存的单词Str1“abcdef”和单词Str2“dbdef”，经过压缩后的存储形式如下。 请设计一个高效的算法完成两个单链表的压缩存储，并估计你所设计算法的时间复杂度。 要求：阅读预设代码，编写函数SNODE * ziplist( SNODE * head1, SNODE * head2 ) ziplist的功能是：在两个串链表中，查找公共后缀，若有公共后缀，则压缩 并返回指向公共后缀的指针；否则返回NULL 预设代码 前置代码 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. 括号匹配（10分） 成绩: 10 / 折扣: 0.8 4 括号匹配 （10分） 成绩: 10 / 折扣: 0.8 假设一个算术表达式中包含圆括号、方括号两种类型的括号，试编写一个判断表达式中括号是否匹配的程序，匹配返回Match succeed!，否则返回Match false!。 例 [1+2*(3+4*(5+6))]括号匹配 (1+2)*(1+2*[(1+2)+3) 括号不匹配 输入 包含圆括号、方括号两种类型括号的算术表达式 输出 匹配输出 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. 迷宫问题（15分） 成绩: 15 / 折扣: 0.8 5 迷宫问题（15分） 成绩: 15 / 折扣: 0.8 迷宫有一个入口，一个出口。一个人从入口走进迷宫，目标是找到出口。阴影部分和迷宫的外框为墙，每一步走一格，每格有四个可走的方向，探索顺序为：南、东、北、西。 输入：输入迷宫数组 输出：若有解，输出从入口到出口的一条路径，否则输出 there is no solution! 例（上图所示的迷宫数组） 输入 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;