北京理工大学数据结构编程练习答案.docx
- 文档编号:13282096
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:125
- 大小:104.09KB
北京理工大学数据结构编程练习答案.docx
《北京理工大学数据结构编程练习答案.docx》由会员分享,可在线阅读,更多相关《北京理工大学数据结构编程练习答案.docx(125页珍藏版)》请在冰点文库上搜索。
北京理工大学数据结构编程练习答案
1.一元多项式相加(10分)
成绩:
10/折扣:
0.8
题目说明:
编写一元多项式加法运算程序。
要求用线性链表存储一元多项式(参照课本)。
该程序有以下几个功能:
1.多项式求和
输入:
输入三个多项式,建立三个多项式链表Pa、Pb、Pc
(提示:
调用CreatePolyn(polynomial&P,intm)。
输出:
显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc
(提示:
调用AddPolyn(polynomial&Pa,polynomialPb),调用PrintPolyn(polynomialP))。
0.退出
输入:
根据所选功能的不同,输入格式要求如下所示(第一个数据是功能选择编号,参见测试用例):
∙1
多项式A包含的项数,以指数递增的顺序输入多项式A各项的系数(整数)、指数(整数)
多项式B包含的项数,以指数递增的顺序输入多项式B各项的系数(整数)、指数(整数)
多项式C包含的项数,以指数递增的顺序输入多项式C各项的系数(整数)、指数(整数)
∙0---操作终止,退出。
输出:
对应一组输入,输出一次操作的结果(参见测试用例)。
∙1多项式输出格式:
以指数递增的顺序输出:
<系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。
零多项式的输出格式为<0,0>
∙0无输出
1.
#include
#include
usingstd:
:
cin;
usingstd:
:
cout;
usingstd:
:
endl;
structdate
{
inta;
intb;
structdate*pnext;
};
typedefstructdateDATE;
typedefstructdate*PDATE;
voidoutput(PDATEp)
{
intf=0;
p=p->pnext;
while(p!
=NULL)
{
if(p->a!
=0)
{
f=1;
cout<<"<"<
if(p->pnext==NULL)
cout< else cout<<","; } p=p->pnext; } if(f==0) cout<<"<0,0>"< } voidadd(PDATEa,PDATEb,PDATEc) { PDATEp1,p2,p3; p1=a; p2=b; p3=c; if(p1! =NULL)p1=p1->pnext;//skiphead 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; } elseif(p1->b { 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; } }//endwhile if(p1==NULL) p3->pnext=p2; if(p2==NULL) p3->pnext=p1; } intmain() { intflag; intn; PDATEP[6]={NULL}; PDATEp=NULL; for(inti=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(inti=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,kmustbiggerthan0. b) 输入: k>n 输出: kshouldnotbiggerthann. 例 输入 9,3,2 输出 468137295 #include #include #include structdate { inta; structdate*next; }; typedefstructdateDATE; typedefstructdate*PDATE; PDATEsetnew(PDATEp,inta) { PDATEpt; pt=(PDATE)malloc(sizeof(DATE)); pt->a=a; pt->next=p->next; p->next=pt; returnpt; } intcount; PDATEdel(PDATEp0) { if(! count) { printf("\n"); count=10; } printf("%d",p0->a); PDATEp=p0->next; p0->a=p->a; p0->next=p->next; free(p); count--; returnp0; } intmain() { count=10; intn=0,k=0,m=0; scanf("%d,%d,%d",&n,&m,&k); if(! (n>0&&m>0&&k>0)) printf("n,m,kmustbiggerthan0.\n"); elseif(m>n) printf("kshouldnotbiggerthann.\n"); else { PDATEp=NULL; PDATEhead=(DATE*)malloc(sizeof(DATE)); head->next=head; head->a=1; p=head; for(inti=2;i<=n;i++) p=setnew(p,i); while(p->a! =m) p=p->next; while(n) { //inttemp=k; inttemp=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 structdate { longlong*timedate; longh; intw; structdate*pl; structdate*pr; }; typedefstructdateDATE; typedefstructdate*PDATE; PDATEsetnew(PDATEp0,intw,longh,longlong*num)//p0为左邻 { PDATEp=(PDATE)malloc(sizeof(DATE)); p->timedate=num; p->pl=p0; p->pr=NULL; p0->pr=p; p->h=h; p->w=w; returnp; } voidoutput(longlong*p,longn) { while(n--) printf("%lld\n",*(++p)); } intmain() { longlongmyclock; longn; intw; longh; PDATEp=NULL,pt=NULL; //setleftp PDATEleft=(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); longlong*timedate=newlonglong[n+1]; for(longi=0;i { //cin>>w>>h; scanf("%d%d",&w,&h); p=setnew(p,w,h,timedate+i+1); if(pt->h>h) pt=p; } PDATEright=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; deletept; } elseif(p->pl->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; deletept; } //移至下一进水点 if(p->pl->h>p->h&&p->pr->h>p->h) continue; elseif(p->pl->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 预设代码 前置代码 viewplaincopytoclipboardprint? 1./* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ 2. 3.#include 4.#include 5. 6.typedef struct sdata 7.{ char data; 8. struct sdata *next; 9.} SNODE; 10. 11.void setlink( SNODE *, char * ), outlink( SNODE * ); 12.int listlen( SNODE * ); 13.SNODE * ziplist( SNODE *, SNODE * ); 14.SNODE * findlist( SNODE *, SNODE * ); 15. 16.int main( ) 17.{ 18. SNODE * head1, * head2, *head; 19. char str1[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. return 0; 37.} 38. 39.void setlink( 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.void outlink( 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.int listlen( SNODE * head ) 66.{ 67. int len=0; 68. while ( head->next ! = NULL ) 69. { 70. len ++; 71. head = head->next; 72. } 73. return len; 74.} 75. 76.SNODE * findlist( SNODE * head1, SNODE * head2 ) 77.{ 78. int m, 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 &&
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京理工大学 数据结构 编程 练习 答案