北京理工大学数据结构编程练习进步标准答案.doc

,.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<iostream>#include<stdlib.h>using std:cin;using std:cout;using std:endl;struct dateint 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<<"<"<<p->a<<","<<p->b<<">"if(p->pnext=NULL)cout<<endl;elsecout<<","p=p->pnext;if(f=0)cout<<"<0,0>"<<endl;void add(PDATE a,PDATE b,PDATE c)PDATE p1,p2,p3;p1=a;p2=b;p3=c;if(p1!=NULL) p1=p1->pnext;/skip headif(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->b<p2->b)p3->pnext=(PDATE)malloc(sizeof(DATE);p3=p3->pnext;p3->a=p1->a;p3->b=p1->b;p3->pnext=NULL;p1=p1->pnext;elsep3->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 whileif(p1=NULL)p3->pnext=p2;if(p2=NULL)p3->pnext=p1;int main()int flag;int n;PDATE P6=NULL;PDATE p=NULL;for(int i=0;i<6;i+)Pi=(PDATE)malloc(sizeof(DATE);Pi->a=0;Pi->b=0;Pi->pnext=NULL;cin>>flag;if(flag=1)for(int i=1;i<4;i+)p=Pi;cin>>n;while(n-!=0)p->pnext=(PDATE)malloc(sizeof(DATE);p=p->pnext;cin>>p->a>>p->b;p->pnext=NULL;output(Pi);add(P1,P2,P4);output(P4);add(P4,P3,P5);output(P5);0 约瑟夫问题(10分)成绩: 10 / 折扣: 0.80 约瑟夫问题成绩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<stdio.h>#include<stdlib.h>#include<math.h>struct dateint 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");elsePDATE 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 23 每个平面 i 可以用两个数字来描述，即它的宽度 Wi 和高度 Hi，其中 1 Wi 1,000、1 Hi 1,000,000，而这个坑最特别的地方在于坑底每个平面的高度都是不同的。每到夏天，雨水会把坑填满，而在其它的季节，则需要通过人工灌水的方式把坑填满。灌水点设在坑底位置最低的那个平面，每分钟灌水量为一个单位（即高度和宽度均为 1）。随着水位的增长，水自然会向其它平面扩散，当水将某平面覆盖且水高达到一个单位时，就认为该平面被水覆盖了。请你计算每个平面被水覆盖的时间。 灌水 水满后自动扩散 | | * | * * | * * * * V * * V * * * * * * . * * * * * * : * * * * * * : * * * * * * * * * * * * * * * * * * * *4 分钟后 26 分钟后 50 分钟后平面 1 被水覆盖 平面 3 被水覆盖平面 2 被水覆盖输入输入的第一行是一个整数 N，表示平面的数量。从第二行开始的 N 行上分别有两个整数，分别表示平面的宽度和高度。输出输出每个平面被水覆盖的时间。#include<stdlib.h>#include<stdio.h>struct datelong 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("%lldn",*(+p);int main()long long myclock;long n;int w;long h;PDATE p=NULL,pt=NULL;/set leftpPDATE 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 longn+1;for(long i=0;i<n;i+)/cin>>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->h<p->pr->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->h<p->pr->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<stdio.h> 4. #include<stdlib.h> 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. charstr1100,str2100; 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(m<n) 89. p2=p2->next; 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;elsep22->next=p11->next;return p11->next; 4. 括号匹配（10分）成绩: 10 / 折扣: 0.84 括号匹配 （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<stdio.h>int main()int flag=0;char a1000=0;char* p;p=&a0;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;/endswiychtemp=getchar();/end whilwprintf("Match succeed!n");return 0;5. 迷宫问题（15分）成绩: 15 / 折扣: 0.85 迷宫问题（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<iostream>using std:cin;using std:cout;using std:endl;int main()int a,b;cin>>a>>b;bool date102102;for(int i=0;i<102;i+)for (int j=0;j<102;j+)dateij=1;int stack5004=0;int p=1;stack02=5;stack10=1;stack11=1;stack13=5;for(int x=1;x<=a;x+)/input start for(int y=1;y<=b;y+)bool temp;cin>>temp;datexy=temp;/input finishint p1,p2;while(!(stackp0=a&&stackp1=b)/find startswitch (stackp2)case 0:/downif(stackp2=stackp3)stackp2+;break;p1=stackp0+1;p2=stackp1;if(datep1p2)/wallstackp2+;goto x1;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=2;break;case 1:/rightx1:if(stackp2=stackp3)stackp2+;break;p1=stackp0;p2=stackp1+1;if(datep1p2)/wallstackp2+;goto x2;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=3;break;case 2:/upx2:if(stackp2=stackp3)stackp2+;break;p1=stackp0-1;p2=stackp1;if(datep1p2)/wallstackp2+;goto x3;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=0;break;case 3:/leftx3:if(stackp2=stackp3)stackp2+;break;p1=stackp0;p2=stackp1-1;if(datep1p2)/wallstackp2+;goto x4;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=1;break;case 4:/backx4:stackp2=0;p-;break;case 5:cout<<"there is no solution!n"return 0;/find finishp=1;while(stackp2)cout<<"<"<<stackp0<<","<<stackp1<<"> "p+;cout<<"<"<<stackp0<<","<<stackp1<<"> "<<endl;return 0;6. 飞机场调度(15分)成绩: 15 / 折扣: 0.8在本实验中，需要同学们利用队列实现一个飞机场调度模拟，根据不同的输入参数得到不同的模拟结果。程序运行开始，首先需要输入以下参数： 机场跑道数，飞机降落占用跑道时间（整数）， 飞机起飞占用跑道时间（整数） 整个模拟的时间以分钟为单位，从 0 开始，每分钟的开始需要输入： 该分钟要求降落飞机数， 该分钟要求起飞飞机数 机场调度原则是降落优先起飞，在此原则下按来的顺序排队；每驾飞机都有一个编号，要起飞飞机从 1 开始，要降落飞机从 5001 开始；每驾飞机需要等待的时间是从其提要求开始到分