资源描述
.1.一元多项式相加成绩: 10 / 折扣: 0.8题目说明：编写一元多项式加法运算程序。要求用线性链表存储一元多项式参照课本。该程序有以下几个功能：1. 多项式求和输入：输入三个多项式,建立三个多项式链表Pa、Pb、Pc 提示：调用CreatePolyn。输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc 提示：调用AddPolyn, 调用PrintPolyn。0. 退出输入：根据所选功能的不同,输入格式要求如下所示第一个数据是功能选择编号,参见测试用例： 1 多项式A包含的项数,以指数递增的顺序输入多项式A各项的系数整数、指数整数多项式B包含的项数,以指数递增的顺序输入多项式B各项的系数整数、指数整数多项式C包含的项数,以指数递增的顺序输入多项式C各项的系数整数、指数整数 0 操作终止,退出。输出：对应一组输入,输出一次操作的结果参见测试用例。 1 多项式输出格式：以指数递增的顺序输出: ,参见测试用例。零多项式的输出格式为 0 无输出#include#includeusing 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 outputint f=0;p=p-pnext;whileifa!=0f=1;couta,b;ifpnext=NULLcoutendl;elsecoutpnext;ifcoutendl;void addPDATE p1,p2,p3;p1=a;p2=b;p3=c;if p1=p1-pnext;/skip headif p2=p2-pnext;while&ifbp2-bp3-pnext=mallocsizeof;p3=p3-pnext;p3-a=p2-a;p3-b=p2-b;p3-pnext=NULL;p2=p2-pnext;else ifbbp3-pnext=mallocsizeof;p3=p3-pnext;p3-a=p1-a;p3-b=p1-b;p3-pnext=NULL;p1=p1-pnext;elsep3-pnext=mallocsizeof;p3=p3-pnext;p3-a=p1-a+p2-a;p3-b=p1-b;p3-pnext=NULL;p1=p1-pnext;p2=p2-pnext;/end whileifp3-pnext=p2;ifp3-pnext=p1;int mainint flag;int n;PDATE P6=NULL;PDATE p=NULL;forint i=0;iPi=mallocsizeof;Pi-a=0;Pi-b=0;Pi-pnext=NULL;cinflag;ifforint i=1;ip=Pi;cinn;whilep-pnext=mallocsizeof;p=p-pnext;cinp-ap-b;p-pnext=NULL;output;add;output;add;output;0 约瑟夫问题成绩: 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 输入：kn输出：k should not bigger than n.例输入9,3,2输出4 6 8 1 3 7 2 9 5#include#include#includestruct dateint a;struct date* next;typedef struct date DATE;typedef struct date* PDATE;PDATE setnewPDATE pt;pt= malloc sizeof;pt-a=a;pt-next=p-next;p-next=pt;return pt;int count;PDATE delifprintf;count=10;printfa;PDATE p=p0-next;p0-a=p-a;p0-next=p-next;free;count-;return p0;int maincount=10;int n=0,k=0,m=0;scanf;if!0&m0&k0printf;else ifnprintf;elsePDATE p=NULL;PDATE head=mallocsizeof;head-next=head;head-a=1;p=head;forint i=2;ip=setnew;whilea!=mp=p-next;while/int temp=k;int temp=k%n+n;whilep=p-next;del;n-;printf;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#includestruct datelong long * timedate;long h;int w;struct date* pl;struct date* pr;typedef struct date DATE;typedef struct date* PDATE;PDATE setnew/p0为左邻PDATE p= mallocsizeof;p-timedate=num;p-pl=p0;p-pr=NULL;p0-pr=p;p-h=h;p-w=w;return p;void outputwhileprintf%lldn,*;int mainlong long myclock;long n;int w;long h;PDATE p=NULL,pt=NULL;/set leftpPDATE left= mallocsizeof;left-timedate=NULL;left-pl=NULL;left-pr=NULL;left-h=1000000;left-w=0;p=left;pt=left;scanf;long long* timedate=new long longn+1;forlong i=0;i/cinwh;scanf;p=setnew;ifhhpt=p;PDATE right=setnew;p=pt;myclock=0;whilepl-h!=p-pr-h*timedate=myclock+p-w;/计算时间并删除合并ifpl-hp-pr-h myclock+=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 ifpl-hpr-hmyclock+=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;/移至下一进水点ifpl-hp-h&p-pr-hp-hcontinue;else ifpl-hpr-h/左移whilehp-pl-hp=p-pl;else /右移whilehp-pr-hp=p-pr;myclock+=p-w;*timedate=myclock;output;3. 单词压缩存储成绩: 10 / 折扣: 0.8如果采用单链表保存单词,可采用如下办法压缩存储空间。如果两个单词的后缀相同,则可以用同一个存储空间保存相同的后缀。例如,原来分别采用单链表保存的单词Str1abcdef和单词Str2dbdef,经过压缩后的存储形式如下。请设计一个高效的算法完成两个单链表的压缩存储,并估计你所设计算法的时间复杂度。要求：阅读预设代码,编写函数SNODE * ziplistziplist的功能是：在两个串链表中,查找公共后缀,若有公共后缀,则压缩 并返回指向公共后缀的指针；否则返回NULL预设代码前置代码view plaincopy to clipboardprint?1. /*PRESETCODEBEGIN-NEVERTOUCHCODEBELOW*/2. #include 3. #include 4. typedefstructsdata 5. chardata; 6. structsdata*next; 7. SNODE; 8. voidsetlink,outlink; 9. intlistlen; 10. SNODE*ziplist; 11. SNODE*findlist; 12. intmain 13. 14. SNODE*head1,*head2,*head; 15. charstr1100,str2100; 16. gets; 17. gets; 18. head1=mallocsizeof; 19. head2=mallocsizeof; 20. head=mallocsizeof; 21. head-next=head1-next=head2-next=NULL; 22. setlink; 23. setlink; 24. head-next=ziplist; 25. head-next=findlist; 26. outlink; 27. return0; 28. 29. voidsetlink 30. 31. SNODE*p; 32. while 33. p=mallocsizeof; 34. p-data=*str; 35. p-next=NULL; 36. str+; 37. head-next=p; 38. head=p; 39. 40. return; 41. 42. voidoutlink 43. 44. whilenext!=NULL 45. 46. printfnext-data; 47. head=head-next; 48. 49. printf; 50. return; 51. 52. intlistlen 53. 54. intlen=0; 55. whilenext!=NULL 56. 57. len+; 58. head=head-next; 59. 60. returnlen; 61. 62. SNODE*findlist 63. 64. intm,n; 65. SNODE*p1=head1,*p2=head2; 66. m=listlen; 67. n=listlen; 68. whilen 69. p1=p1-next; 70. m-; 71. 72. whilem 73. p2=p2-next; 74. n-; 75. 76. whilenext!=NULL&p1-next!=p2-next 77. 78. p1=p1-next; 79. p2=p2-next; 80. 81. returnp1-next; 82. 83. /*Hereiswaitingforyou!*/84. /* 85. SNODE*ziplist 86. 87. 88. */89. /*PRESETCODEEND-NEVERTOUCHCODEABOVE*/SNODE * ziplist int m, n; SNODE *p1=head1, *p2=head2,*p11=NULL,*p22=NULL;m = listlen;n = listlen;while n p1 = p1-next;m-;while m p2 = p2-next;n-;p11=p1;p22=p2;whilenext-next!=NULLifnext-data!=p2-next-datap11=p1-next;p22=p2-next;p1=p1-next;p2=p2-next;ifnext-data!=p2-next-datareturn 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*括号匹配*1+2*+3 括号不匹配输入包含圆括号、方括号两种类型括号的算术表达式输出匹配输出 Match succeed!不匹配输出 Match false!例输入1+2* 3+4* 输出Match succeed!#includeint mainint flag=0;char a1000=0;char* p;p=&a0;char temp;temp=getchar;*p=temp;whileswitch case :if*p!=printf;return 0;*p=0;p-;break;case :p+;*p=temp;break;case:ifprintf;return 0;*p=0;p-;break;/endswiychtemp=getchar;/end whilwprintf;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 输出 #includeusing std:cin;using std:cout;using std:endl;int mainint a,b;cinab;bool date102102;forint i=0;ifor int j=0;jdateij=1;int stack5004=0;int p=1;stack02=5;stack10=1;stack11=1;stack13=5;forint x=1;x/input start forint y=1;ybool temp;cintemp;datexy=temp;/input finishint p1,p2;while!/find startswitch case 0:/downifstackp2+;break;p1=stackp0+1;p2=stackp1;if/wallstackp2+;goto x1;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=2;break;case 1:/rightx1:ifstackp2+;break;p1=stackp0;p2=stackp1+1;if/wallstackp2+;goto x2;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=3;break;case 2:/upx2:ifstackp2+;break;p1=stackp0-1;p2=stackp1;if/wallstackp2+;goto x3;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=0;break;case 3:/leftx3:ifstackp2+;break;p1=stackp0;p2=stackp1-1;if/wallstackp2+;goto x4;else/roadstackp2+;p+;stackp0=p1;stackp1=p2;stackp3=1;break;case 4:/backx4:stackp2=0;p-;break;case 5:coutthere is no solution!n;return 0;/find finishp=1;whilecoutstackp0,stackp1 ;p+;coutstackp0,stackp1 endl;return 0;6. 飞机场调度成绩: 15 / 折扣: 0.8在本实验中,需要同学们利用队列实现一个飞机场调度模拟,根据不同的输入参数得到不同的模拟结果。程序运行开始,首先需要输入以下参数： 机场跑道数,飞机降落占用跑道时间整数, 飞机起飞占用跑道时间整数 整个模拟的时间以分钟为单位,从 0 开始,每分钟的开始需要输入： 该分钟要求降落飞机数, 该分钟要求起飞飞机数 机场调度原则是降落优先起飞,在此原则下按来的顺序排队；每驾飞机都有一个编号,要起飞飞机从 1 开始,要降落飞机从 5001 开始；每驾飞机需要等待的时间是从其提要求开始到分配跑道为止；每个跑道都有一个编号从 1 开始,都可以用来降落和起飞,但同一时间只能被一架飞机占用,占用时间为该飞机降落起飞占用跑道时间。 当输入的要求降落飞机数和要求起飞飞机数都小于 0 时,表示机场关闭,不再接受新的请求,但余下没有降落起飞的飞机需照常进行。 模拟过程中需要随时输出以下数据： 1. 当前时间 2. 所有从占用变为空闲的跑道编号 在输入降落、起飞飞机数前输出 3. 可以降落起飞飞机编号 04d 、跑道编号 02d 在输入降落、起飞飞机数后输出 模拟结束后,程序需输出以下统计结果： 1. 模拟时间 4d 2. 降落平均等待时间 4.1f 3. 起飞平均等待时间 4.1f 4. 每条跑道被占用时间 4d 5. 跑道平均被占用的百分比 4.1f , 平均占用时间 100/ 模拟时间 例： 下面的黑斜体为输入 4 3 5 Current Time: 0 1 4 airplane 5001 is ready to land on runway 01 airplane 0001 is ready to takeoff on runway 02 airplane 0002 is ready to takeoff on runway 03 airplane 0003 is ready to takeoff on runway 04 Current Time: 1 0 0 Current Time: 2 0 2 Current Time: 3 runway 01 is free 3 0 airplane 5002 is ready to land on runway 01 Current Time: 4 0 0 Current Time: 5 runway 02 is free runway 03 is free runway 04 is free 0 0 airplane 5003 is ready to land on runway 02 airplane 5004 is ready to land on runway 03 airplane 0004 is ready to takeoff on runway 04 Current Time: 6 runway 01 is free 2 4 airplane 5005 is ready to land on runway 01 Current Time: 7 -1 -1 Current Time: 8runway 02 is freerunway 03 is freeairplane 5006 is ready to land on runway 02airplane 0005 is ready to takeoff on runway 03Current Time: 9runway 01 is freeairplane 0006 is ready to takeoff on runway 01Current Time: 10runway 04 is freeairplane 0007 is ready to takeoff on runway 04Current Time: 11runway 02 is freeairplane 0008 is ready to takeoff on runway 02Current Time: 12Current Time: 13runway 03 is freeairplane 0009 is ready to takeoff on runway 03Current Time: 14runway 01 is freeairplane 0010 is ready to takeoff on runway 01Current Time: 15runway 04 is freeCurrent Time: 16runway 02 is freeCurrent Time: 17Current Time: 18runway 03 is freeCurrent Time: 19runway 01 is freesimulation finishedsimulation time: 19average waiting time of landing: 1.0average waiting time of takeoff: 4.2runway 01 busy time: 19runway 02 busy time: 16runway 03 busy time: 18runway 04 busy time: 15runway average busy time percentage: 89.5% /#include#includeint time,wayn,downtime,uptime,up,down,upwaiting,downwaiting,upcount,downcount,use;int* way;float* waytime;int manageforint i=1;iif*=0use-;if0*=downtime;*+=downtime;printf;downwaiting-;use+;else if0*=uptime;*+=uptime;printf;upwaiting-;use+;else*=-1;else if*if0*=downtime;*+=downtime;printf;downwaiting-;use+;else if0*=uptime;*+=uptime;printf;upwaiting-;use+;/end of forreturn 0;int mainfloat avewaitingup=0;float avewaitingdown=0;scanf;way= malloc sizeof*;waytime= malloc sizeof*;forint i=0;i*=-1;*=0;downcount=5001;upcount=1;use=0;printf;scanf;for=0&down=0;upwaiting+=up;downwaiting+=down;manage;avewaitingup+=upwaiting;avewaitingdown+=downwaiting;forint i=0;i*-;printf;forint i=1;iif*=0printf;scanf;manage;avewaitingup+=upwaiting;avewaitingdown+=downwaiting;whileforint i=0;i*-;printf;forint i=1;iif*=0printf;manage;avewaitingup+=upwaiting;avewaitingdown+=downwaiting;time-;/finishprintf;float aa=avewaitingdown/,bb=avewaitingup/,cc=0;ifaa=0;ifbb=0;printf;float all=0;int i=1;for;iprintfrunway %02d busy time: %4.0fn,i,*;all+=*;ifcc=0;elsecc=all/wayn/time*100;printf;return 0;7. 股票撮合系统成绩: 15 / 折扣: 0.8在股票交易中,股民可以通过各种手段将委托送到股票交易所。每个委托主要说明了股民身份、买卖的股票、价格和数量。交易的规则是价格优先、时间优先,即出的价格最高的人先买,出的价格最低的人先卖。两个委托只有价格合适时才能成交,未成交的委托按价格顺序放在撮合队列中。每个股票有两个撮合队列：买队列和卖队列。只有当买委托的价格高于等于卖委托的价格,两个委托才可以成交,成交价取两个委托价格的平均值,成交量取两个委托数量的最小值。委托可以是完全成交或部分成交,部分成交的委托保留在撮合队列中继续交易。试利用单链表作为存放委托的数据结构撮合队列,编写一模拟股票交易的程序,该程序有以下几个功能： 1. 委托申请： 输入：每个委托包括四个数据项,股票编码
展开阅读全文