2014级DS作业和实验参考答案(二)

2014级DS作业和实验参考答案二复习C++9000，9002顺序表插入和删除操作9003，9004顺序表查找操作和单链表建立9012，9006单链表操作9014，9016，9017特殊线性表栈操作9045，9042，9041特殊线性表队列操作9038，9040二叉树的顺序存储9050复制二叉树9063二叉树的高度宽度9057，9067图的邻接矩阵及遍历9070，9072，9087图的生成树9076，9077，9088图的最短路径9092，9091，9085！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！顺序表9010，9005顺序表29097单链表9007循环链表9008递归9039二叉树的建立及遍历9019二叉树的结点9054，9056二叉树的存储转换9049哈夫曼编码9068图的邻接表及度9071，9079图的存储转换9089，9084，9083！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！9000:矩形面积ProblemDescription声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。Output若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。SampleInput222441234SampleOutput44//9000ANSWERCODE1#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//9002ANSWERCODE1#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//9003ANSWERCODE1#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//9004ANSWERCODE1#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;}9012:找唯一数ProblemDescription在一个表长为n的顺序表中，除一个元素之外，其余的元素都出现了两次。请找出这个仅出现一次的元素。Input有多组数据，每组第一行表示表长n（1=n=11111）；第二行表示顺序表的各元素。Output输出这个唯一数。SampleInput52213172113-123SampleOutput3-1//9012ANSWERCODE1#includeiostreamusingnamespacestd;intmain(){intn,i,j,A[11112],B[11112];while(cinn){if(n=1&&n=11111){for(i=0;in;i++)cinA[i];for(i=0;in;i++)B[i]=1;for(i=0;in;i++){for(j=i+1;jn;j++){if(A[i]==A[j]){B[i]=0;B[j]=0;break;}}}for(i=0;in;i++){if(B[i]==1)coutA[i]endl;}}}return0;}9006:单链表的建立和遍历ProblemDescription输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。Input输入数据有多组，每组数据占两行；每组第一行为一个数字N（N=50）；第二行有N个整数。Output输出这组整数，数字之间用一个空格分隔。SampleInput51232457854SampleOutput1232457854//9006ANSWERCODE1#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;}9014:删最小值ProblemDescription设有一单链表，现要求删除其最小值（假设最小值唯一）。若删除成功，则输出被删的最小值；若删除失败，则输出“notexist”。Input有多组数据，每组第一行为单链表的元素个数n（0=n100）；第二行为单链表的各个元素。Output若删除成功，则输出被删的最小值；若删除失败，则输出“notexist”。SampleInput8426-319145524167SampleOutput-31//9014ANSWERCODE1#includeiostreamusingnamespacestd;structNode{intdata;Node*next;};intmain(){inti,n,data[100],min;Node*first,*p,*q,*s,