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

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.#includeiostream#includestdlib.husingstd::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;coutp-a,p-b;if(p-pnext==NULL)coutendl;elsecout,;}p=p-pnext;}if(f==0)cout0,0endl;}voidadd(PDATEa,PDATEb,PDATEc){PDATEp1,p2,p3;p1=a;p2=b;p3=c;if(p1!=NULL)p1=p1-pnext;//skipheadif(p2!=NULL)p2=p2-pnext;while((p1!=NULL)&&(p2!=NULL)){if(p1-bp2-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-bp2-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;}}//endwhileif(p1==NULL)p3-pnext=p2;if(p2==NULL)p3-pnext=p1;}intmain(){intflag;intn;PDATEP[6]={NULL};PDATEp=NULL;for(inti=0;i6;i++){P[i]=(PDATE)malloc(sizeof(DATE));P[i]-a=0;P[i]-b=0;P[i]-pnext=NULL;}cinflag;if(flag==1){for(inti=1;i4;i++){p=P[i];cinn;while(n--!=0){p-pnext=(PDATE)malloc(sizeof(DATE));p=p-pnext;cinp-ap-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.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,kmustbiggerthan0.b)输入：kn输出：kshouldnotbiggerthann.例输入9,3,2输出468137295#includestdio.h#includestdlib.h#includemath.hstructdate{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(!(n0&&m0&&k0))printf(n,m,kmustbiggerthan0.\n);elseif(mn)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行上分别有两个整数，分别表示平面的宽度和高度。输出输出每个平面被水覆盖的时间。#includestdlib.h#includestdio.hstructdate{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;//setleftpPDATEleft=(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;in;i++){//cinwh;scanf(%d%d,&w,&h);p=setnew(p,w,h,timedate+i+1);if(pt-hh)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-hp-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-hp-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;deletept;}//移至下一进水点if(p-pl-hp-h&&p-pr-