ST数据结构作业与实验参考答案(一)

9000:矩形面积ProblemDescription声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。Output若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。SampleInput222441234SampleOutput44//9000ANSWER#includeiostreamusingnamespacestd;classrect{public:rect(inta,intb,intc,intd);~rect(){}intarea();private:intx1,y1,x2,y2;};rect::rect(inta,intb,intc,intd){x1=a;y1=b;x2=c;y2=d;}intrect::area(){return(x2-x1)*(y2-y1);}intmain(){inta,b,c,d,n;cinn;while(n--){cinabcd;if(a0||b0||c0||d0||a=c||b=d)coutdataerrorendl;else{rectr(a,b,c,d);coutr.area()endl;}}return0;}9002:数组的循环移位ProblemDescription对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。Input输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。Output循环左移后的字符型数组内容。SampleInput1abcdefgh3SampleOutputdefghabc//9002ANSWER#includeiostreamusingnamespacestd;#defineN20voidReverse(chara[],intfrom,intto){inti,j;chart;i=from;j=to;while(ij){t=a[i];a[i]=a[j];a[j]=t;i++;j--;}}voidConverse(chara[],intn,inti){Reverse(a,0,i-1);Reverse(a,i,n-1);Reverse(a,0,n-1);}intmain(){chara[N];intm,n,i;cinm;while(m--){cinai;n=strlen(a);i=i%n;Converse(a,n,i);coutaendl;}return0;}9003:合并顺序表ProblemDescription假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，则输出“notenough”。Input第一行为一个数字n,表示下面有n组数据，每组数据包括4行；每组数据中的第一行表示表A的表长，第二行表示表A的数据元素，第三行表示表B的表长，第四行表示表B的数据元素。Output若合并成功，输出两行信息，第一行表示合并后A表的表长，第二行表示合并后A表的数据元素，元素之间用一个空格分隔；若合并后的顺序表表长超过总容量20，则输出“notenough”。SampleInput1413817361015SampleOutput71368101517//9003ANSWER#includeiostreamusingnamespacestd;constintMaxSize=20;//有两个由小到大有序的有序顺序表A和Bvoidcombine(intA[],intA_len,intB[],intB_len){if((A_len+B_len)MaxSize)coutnotenough\n;else{inti=0,j=0,k=0;for(i=0;iB_len;i++){while(B[i]A[j])//找到B[i]在A表中的插入位置j{j++;}for(k=A_len-1;k=j;k--)//把j(包括j)以后的元素往后挪一个位置，空出j来。{A[k+1]=A[k];}A[j]=B[i];//把B[i]插入A表中的位置jA_len++;//A表长度加1}coutA_lenendl;for(i=0;i(A_len-1);i++)coutA[i];coutA[i]endl;}}voidmain(){intA[MaxSize],B[MaxSize],A_len,B_len,n,i;cinn;while(n--){cinA_len;for(i=0;iA_len;i++){cinA[i];}cinB_len;for(i=0;iB_len;i++){cinB[i];}combine(A,A_len,B,B_len);}}9004:连续删除ProblemDescription从由小到大有序的顺序表中删除其值在[s,t]之间（含s和t）的所有元素，且不改变顺序表的有序性。如果s=t则显示“dataerror”；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任何信息。Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括3行；每组数据中的第一行包含两个数字s和t，第二行为顺序表的表长len（0len=20），第三行为顺序表的数据元素。Output对于每组数据，如果s=t，则直接输出“dataerror”，否则输出两行信息：第一行为处理后顺序表的表长，第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信息。SampleInput1818713510171925SampleOutput51351925//9004ANSWER#includeiostreamusingnamespacestd;intmain(){intn,s,t,len,A[21],i,s_i,t_i,j,span;cinn;while(n--){cinstlen;for(i=0;ilen;i++)cinA[i];if(s=t||len=0||len20){coutdataerrorendl;continue;}s_i=0;t_i=len-1;while(A[s_i]s&&s_ilen)s_i++;while(A[t_i]t&&t_i=0)t_i--;if(s_i=t_i){span=t_i-s_i+1;for(j=s_i;jlen;j++)A[j]=A[j+span];len-=span;}if(len!=0){coutlenendl;for(i=0;ilen-1;i++)coutA[i];coutA[i]endl;}}return0;}9005:最长相等子序列长度ProblemDescription给定一个有n个元素的整数数组b，b中连续的相等元素构成的子序列称为平台。设计一个算法求b中最长平台的长度。Input第一行为一个数字m，表示下面有m组数据，每组数据包括2行；每组数据中的第一行表示数组的长度n（不会超过20，但可为空表），第二行表示数组的所有元素。Output输出最长平台的长度。SampleInput2811388888710113325888887SampleOutput55//9005ANSWER#includeiostreamusingnamespacestd;intmain(){intm,n,i,b[21],c,max;cinm;while(m--){cinn;if(n=0||n20){cout0\n;continue;}for(i=0;in;i++)cinb[i];i=0;c=max=1;do{while((b[i]==b[i+1])&&(in)){c++;i++;}i++;if(cmax)max=c;c=1;}while(in);coutmaxendl;}return0;}9006:单链表的建立和遍历ProblemDescription输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。Input输入数据有多组，每组数据占两行；每组第一行为一个数字N（N=50）；第二行有N个整数。Output输出这组整数，数字之间用一个空格分隔。SampleInput51232457854SampleOutput1232457854//9006ANSWER#includeiostreamusingnamespacestd;structNode{intdata;Node*next;};intmain(){intN,i,A[51];Node*head=newNode,*p,*tail;while(cinN){if(N0){for(i=0;iN;i++)cinA[i];tail=head;for(i=0;iN;i++){p=newNode;p-data=A[i];tail-next=p;tail=p;}tail-next=NULL;p=head-next;for(i=0;iN-1;i++){coutp-data;p=p-next;}coutp-dataendl;}}return0;}9007:单链表按值操作ProblemDescription对值递增有序的单链表进行以下操作：若表中存在值为x的结点，则将它从表中删除；否则，就往表中插入一个值为x的结点，并保持表值递增有序的性质不变（假设表中没有值相同的元素）。处理后若为空表则不输出。Input每组数据包括3行，第一行表示单链表的长度n（不会超过50）；第二行表示单链表的所有元素；第三行表示x值。Output输出执行操作后的单链表，元素之间用一个空格分隔。SampleInput51357935135794SampleOutput1579134579//9007ANSWER#includeiostreamusingnamespacestd;structNode{intdata;Node*next;};intmain(){inti,n,x,A[51];Node*p,*first,*q,*r,*s;while(cinn){if(n==0){cinx;coutxendl;continue;first=newNode;first-next=NULL;s=newNode;s-data=x;s-next=first-next;first-next=s;}elseif(n=1&&n=50){for(i=0;in;i++){cinA[i];}cinx;//尾插法creaLinkListfirst=newNode;first-next=NULL;r=first;for(i=0;in;i++){s=newNode;s-data=A[i];s-next=r-next;r-next=s;r=s;}//按值查找p=first-next;q=first;while(p){if(p-data==x){q-next=p-next;deletep;break;}elseif(p-datax){q=p;p=p-next;}elseif(p-datax){s=newNode;s-data=x;s-next=p;q-next=s;break;}}if(p==