C++数据结构上机作业DS作业和实验参考答案总汇

2013级DS作业和实验参考答案总汇目录20141217第一次作业：复习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第十二次实验：模拟考试！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！第一次作业：复习C++9000，90029000:矩形面积

ProblemDescription声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。

Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。

Output若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“dataerror”。

SampleInput222441234

SampleOutput44//9000ANSWERCODE1#include<iostream>usingnamespacestd;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;cin>>n;while(n--){cin>>a>>b>>c>>d;if(a<0||b<0||c<0||d<0||a>=c||b>=d)cout<<"dataerror"<<endl;else{rectr(a,b,c,d); cout<<r.area()<<endl;}}return0;}9002:数组的循环移位

ProblemDescription对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。

Input输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。

Output循环左移后的字符型数组内容。

SampleInput1abcdefgh3

SampleOutputdefghabc//9002ANSWERCODE1#include<iostream>usingnamespacestd;#defineN20voidReverse(chara[],intfrom,intto){ inti,j;chart;i=from;j=to; while(i<j) {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;cin>>m; while(m--){ cin>>a>>i; n=strlen(a);i=i%n; Converse(a,n,i); cout<<a<<endl; }return0;}第二次作业：顺序表插入和删除操作9003，90049003:合并顺序表

ProblemDescription假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，则输出“notenough”。

Input第一行为一个数字n,表示下面有n组数据，每组数据包括4行；每组数据中的第一行表示表A的表长，第二行表示表A的数据元素，第三行表示表B的表长，第四行表示表B的数据元素。

Output若合并成功，输出两行信息，第一行表示合并后A表的表长，第二行表示合并后A表的数据元素，元素之间用一个空格分隔；若合并后的顺序表表长超过总容量20，则输出“notenough”。

SampleInput1413817361015

SampleOutput71368101517//9003ANSWERCODE1#include<iostream>usingnamespacestd;constintMaxSize=20;//有两个由小到大有序的有序顺序表A和Bvoidcombine(intA[],intA_len,intB[],intB_len){ if((A_len+B_len)>MaxSize) cout<<"notenough\n"; else { inti=0,j=0,k=0; for(i=0;i<B_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表中的位置j A_len++;//A表长度加1 } cout<<A_len<<endl; for(i=0;i<(A_len-1);i++) cout<<A[i]<<""; cout<<A[i]<<endl; }}voidmain(){ intA[MaxSize],B[MaxSize],A_len,B_len,n,i; cin>>n; while(n--){ cin>>A_len; for(i=0;i<A_len;i++){cin>>A[i];} cin>>B_len; for(i=0;i<B_len;i++){cin>>B[i];} combine(A,A_len,B,B_len); } }9004:连续删除

ProblemDescription从由小到大有序的顺序表中删除其值在[s,t]之间（含s和t）的所有元素，且不改变顺序表的有序性。如果s>=t则显示“dataerror”；否则输出顺序表的表长和顺序表中的元素，若处理后的顺序表为空，则不输出任何信息。

Input输入的第一行为一个数字n，表示下面有n组数据，每组数据包括3行；每组数据中的第一行包含两个数字s和t，第二行为顺序表的表长len（0<len<=20），第三行为顺序表的数据元素。

Output对于每组数据，如果s>=t，则直接输出“dataerror”，否则输出两行信息：第一行为处理后顺序表的表长，第二行为处理后顺序表中的元素，元素之间用一个空格分隔，如果处理后的顺序表为空，则不输出任何信息。

SampleInput1818713510171925

SampleOutput51351925//9004ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,s,t,len,A[21],i,s_i,t_i,j,span; cin>>n; while(n--){ cin>>s>>t>>len; for(i=0;i<len;i++)cin>>A[i]; if(s>=t||len<=0||len>20) {cout<<"dataerror"<<endl;continue;} s_i=0;t_i=len-1; while(A[s_i]<s&&s_i<len)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;j<len;j++)A[j]=A[j+span]; len-=span; } if(len!=0) { cout<<len<<endl; for(i=0;i<len-1;i++)cout<<A[i]<<""; cout<<A[i]<<endl; } } return0;}第三次作业：顺序表查找操作和单链表建立9012，90069012:找唯一数

ProblemDescription在一个表长为n的顺序表中，除一个元素之外，其余的元素都出现了两次。请找出这个仅出现一次的元素。

Input有多组数据，每组第一行表示表长n（1<=n<=11111）；第二行表示顺序表的各元素。

Output输出这个唯一数。

SampleInput52213172113-123

SampleOutput3-1//9012ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,j,A[11112],B[11112]; while(cin>>n) { if(n>=1&&n<=11111) { for(i=0;i<n;i++)cin>>A[i]; for(i=0;i<n;i++)B[i]=1; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) {if(A[i]==A[j]){B[i]=0;B[j]=0;break;}} } for(i=0;i<n;i++) {if(B[i]==1)cout<<A[i]<<endl;} } } return0;}9006:单链表的建立和遍历

ProblemDescription输入N个整数，按照输入的顺序建立单链表存储，并遍历所建立的单链表，输出这些数据。

Input输入数据有多组，每组数据占两行；每组第一行为一个数字N（N<=50）；第二行有N个整数。

Output输出这组整数，数字之间用一个空格分隔。

SampleInput51232457854

SampleOutput1232457854//9006ANSWERCODE1#include<iostream>usingnamespacestd;structNode{intdata;Node*next;};intmain(){ intN,i,A[51]; Node*head=newNode,*p,*tail; while(cin>>N) { if(N>0) { for(i=0;i<N;i++)cin>>A[i]; tail=head; for(i=0;i<N;i++) { p=newNode; p->data=A[i]; tail->next=p; tail=p; } tail->next=NULL;p=head->next; for(i=0;i<N-1;i++) { cout<<p->data<<"";p=p->next;} cout<<p->data<<endl; } } return0;}第四次作业：单链表操作9014，9016，90179014:删最小值

ProblemDescription设有一单链表，现要求删除其最小值（假设最小值唯一）。若删除成功，则输出被删的最小值；若删除失败，则输出“notexist”。

Input有多组数据，每组第一行为单链表的元素个数n（0<=n<100）；第二行为单链表的各个元素。

Output若删除成功，则输出被删的最小值；若删除失败，则输出“notexist”。

SampleInput8426-319145524167

SampleOutput-31//9014ANSWERCODE1#include<iostream>usingnamespacestd;structNode{intdata;Node*next;};intmain(){ inti,n,data[100],min; Node*first,*p,*q,*s,*tail; while(cin>>n) { if(n==0){cout<<"notexist\n";continue;} for(i=0;i<n;i++)cin>>data[i]; first=newNode; first->next=NULL;tail=first; for(i=0;i<n;i++) {s=newNode;s->data=data[i];tail->next=s;tail=s;} tail->next=NULL; p=first;min=first->next->data; while(p->next) { q=p;p=p->next; if(p->data<min)min=p->data; } p=first->next;q=first; while(p) {if(p->data==min)break; else{q=p;p=p->next;}} if(p&&q){q->next=p->next;deletep;cout<<min<<endl;} else{cout<<"notexist\n";} } return0;}9016:查找倒数第k个结点

ProblemDescription有一单链L，请输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“notfind”。

Input有多组数据，每组第一行为单链表元素个数n和k值（0<n<100，k>0）；第二行为单链表的各元素。

Output输出该单链表中倒数第k个结点的值。若该结点不存在，则输出“notfind”。

SampleInput51123455512345

SampleOutput51//9016ANSWERCODE1#include<iostream>usingnamespacestd;structNode{intdate; Node*next;};intmain(){ intn,k,i,c,data[100];Node*first,*r,*p,*s; while(cin>>n>>k) { for(i=0;i<n;i++)cin>>data[i]; first=newNode; r=first; for(i=0;i<n;i++) { s=newNode;s->date=data[i]; r->next=s;r=s; } r->next=NULL; //倒数第k个就是正数第n-k+1个。 if(k<=n&&k>=1) { p=first->next;c=1; while(p&&c<(n-k+1)){p=p->next;c++;} if(p&&c==(n-k+1)){cout<<p->date<<endl;} } elsecout<<"notfind"<<endl; } return0;}9017:统计选票

ProblemDescription设有m个候选人n张选票，每张选票选且只选一人，候选人编号依次为1，2，3，...，m。现将这n张选票存于一单链表中，要求统计并输出每个候选人的得票结果。

Input有多组数据，每组第一行为候选人总数m和选票总数n（m>0，0<n<100）；第二行为n张选票的内容。

Output输出每个候选人的得票结果，数字之间用一个空格隔开。

SampleInput361312215833433211

SampleOutput32121410//9017ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intvotes[100],n,i,m,c; while(cin>>m>>n) { for(i=1;i<=m;i++)votes[i]=0; for(i=0;i<n;i++) { cin>>c; votes[c]++; } for(i=1;i<m;i++)cout<<votes[i]<<""; cout<<votes[m]<<endl; } return0;}第五次作业：特殊线性表栈操作9045，9042，90419045:判栈输出序列的有效性

ProblemDescription设一个栈的输入序列为1,2,3,...,n-1,n。请编写一个算法，判断一个序列p1,p2,p3,...,pn是否是一个有效的栈输出序列。若有效输出1，无效输出0。

Input有多组数据，每组第一行为序列长度n（n<=50），第二行为一个由1~n值组成的长度为n且值无重复的序列。

Output栈输出序列有效输出1，无效输出0。

SampleInput31233312

SampleOutput10//9045ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,j,in,out;//in输入序列指针，out输出序列指针 intoutput[51],stack[51],top=-1; while(cin>>n) { for(i=0;i<n;i++)cin>>output[i]; top=-1;in=0; for(i=0;i<n;i++){ out=output[i]; if(out>in){ for(j=in+1;j<=out;j++)stack[++top]=j; in=out; } if(stack[top]==output[i])top--; else{cout<<"0\n";break;} } if(i==n&&top==-1)cout<<"1\n"; } return0;}9042:判操作序列有效性

ProblemDescription假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则成为非法序列。请编写一个对该操作序列的有效性进行判断，若有效输出1，无效输出0。

Input有多组数据，每组为由I和O组成的序列，序列长度不超过50。

Output操作序列有效输出1，无效输出0。

SampleInputIOIIOIOOIOOIOIIO

SampleOutput10//9042ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,flag; charstr[51],stack[51],top=-1; while(cin>>str) { n=strlen(str);top=-1;flag=0; for(i=0;i<n;i++) { if(str[i]=='I'){stack[++top]=str[i];} elseif(str[i]=='O') { if(top>-1)top--; else{cout<<"0\n";flag=1;break;} } else{cout<<"0\n";flag=1;break;} } if(top==-1&&i==n&&flag==0){cout<<"1\n";} else{if(flag==0)cout<<"0\n";} } return0;}9041:判括号匹配

ProblemDescription任意输入一个由若干个圆括号、方括号和花括号组成的字符串，设计一个算法判断该串中的括号是否配对。

Input有多组数据，每组为一个包含3类括号的字符串，串长不超过100。

Output若该串中的括号匹配输出1，否则输出0。

SampleInput([{}])([{}})([{)]}

SampleOutput100//9041ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ inti,len,flag; charstr[100],stack[100],top=-1; while(cin>>str) { len=strlen(str);flag=0;top=-1; for(i=0;i<len;i++) { if(str[i]=='('||str[i]=='['||str[i]=='{'){stack[++top]=str[i];} elseif((str[i]==')')&&(stack[top]=='(')||(str[i]==']')&&(stack[top]=='[')||(str[i]=='}')&&(stack[top]=='{')){top--;} else{cout<<"0\n";flag=1;break;} } if(top==-1&&i==len&&flag==0){cout<<"1\n";} else{if(flag==0)cout<<"0\n";} } return0;}第六次作业：特殊线性表队列操作9038，90409038:循环队列的操作

ProblemDescription现有一长度为n的整数序列和一最大容量为m的循环队列（用长为m+1的一维数组实现），要求将该序列中的偶数存入循环队列中；当循环队列满时，将循环队列中的所有元素全部出队，并按存入的先后顺序在同一行内依次输出，即每行输出m个元素，每个元素后输出一个空格。

Input有多组数据，每组第一行为整数序列的个数n和循环队列的最大容量m（m<=n<=100，0<m<10）；第二行为整数序列的各个元素。

Output有多行数据，先输出对应行号，每行输出m个元素，均为偶数，每个元素后输出一个空格。

SampleInput10491027168124311039102716812134

SampleOutput1:1021681:102162:8124//9038ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ inti,j,c,l,n,m,A[101],Queue[101],front,rear; while(cin>>n>>m) { for(i=0;i<n;i++)cin>>A[i]; front=rear=0;c=0;l=0; for(i=0;i<n;i++) { if(c<m&&A[i]%2==0) { c++; rear=(rear+1)%(m+1); Queue[rear]=A[i]; } if(c==m) { cout<<++l<<":"; for(j=front+1;j<=rear;j++)cout<<Queue[j]<<""; cout<<endl; c=0;front=rear=0; } } } return0;}9040:火车车厢重排

ProblemDescription一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同。这样，在每个车站只需卸掉最后一节车厢。因此，对于给定的任意次序车厢，必须进行重新排列，使其符合要求。车厢重排工作可通过转轨站完成，在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式工作，现要求设计算法解决火车车厢重排问题。

Input有多组数据，每组第一行为车厢节数n和缓冲轨数目k（2<=k<=5，k<=n<=10），第二行为初始给定的车厢编号次序序列。

Output若给定的车厢编号次序序列可重排，则输出1；否则输出0。

SampleInput9336924718593369247581

SampleOutput10//9040ANSWERCODE1#include<iostream>#include<queue>usingnamespacestd;intmain(){ intn,k,carNum[11],i,j,rearrange; while(cin>>n>>k) { for(i=0;i<n;i++)cin>>carNum[i]; queue<int>Q[5];rearrange=1; for(i=0;i<n;i++) { for(j=0;j<k;j++) { if(Q[j].empty()||carNum[i]>Q[j].back()) {Q[j].push(carNum[i]);break;} } if(j==k) {rearrange=0;break;} } cout<<rearrange<<endl; } return0;}第七次作业：二叉树的顺序存储90509050:顺序存储的前序遍历

ProblemDescription给你一个采用顺序存储结构的二叉树，请你设计一个算法求出它的前序遍历。

Input输入数据有多组，每组的第一行为一个正数n,表示该二叉树的节点个数。

接下来有n个字符，表示各个位置上的元素，当字符为'#'时表示当前节点为空。

Output输出该二叉树的前序遍历

SampleInput6ABCDEF6ABC#DE

SampleOutputABDECFABDCE//9050ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,i,top,S[100];charch[100]; while(cin>>n) { cin>>ch; if(ch[0]=='#')continue; top=-1;i=0; while(top!=-1||i<n) { while(i<n){if(ch[i]!='#')cout<<ch[i];S[++top]=i;i=2*i+1;} if(top!=-1){i=S[top--];i=2*i+2;} } cout<<endl; } return0;}//9050ANSWERCODE2#include<iostream>usingnamespacestd;charchLeverData[101];voidpreorder(inti,intn){ if(chLeverData[i]=='#'||i>=n)return; cout<<chLeverData[i]; preorder(2*i+1,n); preorder(2*i+2,n);}voidmain(){ intn; while(cin>>n) { cin>>chLeverData; preorder(0,n); cout<<endl; }}第八次作业：复制二叉树90639063:复制二叉树

ProblemDescription设有一棵二叉树，其节点值为字符型并假设各值互不相等，采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列，要求复制该二叉树，并对复制得来的二叉树进行中序遍历。

Input第一行为一个整数n，表示以下有n组测试数据，每组测试数据占一行，为扩展二叉树的前序遍历序列。

Output输出复制完的新二叉树的中序遍历序列，空二叉树则不输出任何信息。

SampleInput2AB#D##C##ABD##E##C#F##

SampleOutputBDACDBEACF//9063ANSWERCODE1#include<iostream>usingnamespacestd;structBinode{ chardata;Binode*lchild,*rchild;};Binode*Great(){ Binode*bt;charch; cin>>ch; if(ch=='#')bt=NULL; else { bt=newBinode; bt->data=ch; bt->lchild=Great(); bt->rchild=Great(); } returnbt;}Binode*copy(Binode*bt){ Binode*bt1; if(bt==NULL) returnNULL; else { bt1=newBinode; bt1->data=bt->data; bt1->lchild=copy(bt->lchild); bt1->rchild=copy(bt->rchild); } returnbt1;}voidInorder(Binode*bt1){ if(bt1==NULL) return; else { Inorder(bt1->lchild); cout<<bt1->data; Inorder(bt1->rchild); } };intmain(){ intn; cin>>n; while(n--) { Binode*bt=Great(); Binode*bt1=copy(bt); Inorder(bt1); if(bt1!=NULL) cout<<endl; } return0;}//9063ANSWERCODE2#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild;};BiNode*Creat(){ BiNode*bt;charch; cin>>ch; if(ch=='#')bt=NULL; else { bt=newBiNode; bt->data=ch; bt->lchild=Creat(); bt->rchild=Creat(); } returnbt;}voidInOrder(BiNode*root){if(root==NULL)return;//递归调用的结束条件 else{ InOrder(root->lchild);//中序递归遍历root的左子树 cout<<root->data;InOrder(root->rchild);//中序递归遍历root的右子树 }}//层序遍历复制二叉树BiNode*copy_bitree(BiNode*root){ intfront=-1,rear=-1,newfront=-1,newrear=-1; BiNode*Q[100],*newQ[100],*oldp,*newp,*newroot; if(root==NULL)returnNULL;//空二叉树 oldp=root; newp=newBiNode; newp->data=oldp->data; newroot=newp;//新二叉树的根指针 Q[++rear]=oldp;//入队 newQ[++newrear]=newp;//入队 while(rear!=front) { oldp=Q[++front];//出队 newp=newQ[++newfront];//出队 if(oldp->lchild==NULL)newp->lchild=NULL; else { newp->lchild=newBiNode; newp->lchild->data=oldp->lchild->data; Q[++rear]=oldp->lchild; newQ[++newrear]=newp->lchild; } if(oldp->rchild==NULL)newp->rchild=NULL; else { newp->rchild=newBiNode; newp->rchild->data=oldp->rchild->data; Q[++rear]=oldp->rchild; newQ[++newrear]=newp->rchild; } } returnnewroot;}voidmain(){ intn; BiNode*root,*newroot; cin>>n; while(n--) { root=Creat(); newroot=copy_bitree(root); if(newroot==NULL) continue; InOrder(newroot);//中序遍历新二叉树 cout<<endl; }}第九次作业：二叉树的高度宽度9057，90679057:Tree'sDepth

ProblemDescription一个名字叫SmallGreen的同学，很喜欢研究树的问题。某一天，他随意地在纸上乱涂乱画，画出了各不相同的二叉树，他同时在想：一颗满的二叉树的深度并不难求。但如果要求出一颗二叉树（可能不是满二叉树）的深度，那么该如何求呢？

Input输入包含多个例子，每个例子的第一行为一个整数n，表示以下有n组数据，每组数据占一行，为扩展二叉树的前序遍历序列（长度小于50，若节点为NULL则用'#'表示，否则用小写字母表示）。

Output输出该二叉树的深度。

SampleInput2abcd####efg####abcd####efg#h###i##

SampleOutput45//9057ANSWERCODE1#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild;};BiNode*Creat(){ BiNode*p; charch; cin>>ch; if(ch=='#') returnNULL; else { p=newBiNode; p->data=ch; p->lchild=Creat(); p->rchild=Creat(); } returnp;}intDepth(BiNode*bt){ intl,r; if(bt==NULL)return0; else { l=Depth(bt->lchild); r=Depth(bt->rchild); return(l>=r)?(l+1):(r+1); }}main(){ intn; while(cin>>n) { while(n--) { BiNode*p=Creat(); cout<<Depth(p)<<endl; } } return0;}//9057ANSWERCODE2#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild;};intdeep;BiNode*Creat(inti){ BiNode*p; charch; cin>>ch; if(ch=='#') returnNULL; else{ p=newBiNode; p->data=ch; if(deep<i)deep=i; p->lchild=Creat(i+1); p->rchild=Creat(i+1); } returnp;}intmain(){ intn; while(cin>>n) { while(n--) { deep=0; BiNode*root=Creat(1); cout<<deep<<endl; } } return0;}9067:二叉树的宽度

ProblemDescription二叉树的宽度是指二叉树各层结点数的最大值。设有一棵二叉树，其节点值为字符型并假设各值互不相等，采用二叉链表存储表示。设计一个算法，输出该二叉树的宽度。空二叉树的宽度为0。

Input第一行为一个整数n，表示以下有n组数据，每组数据占一行，为扩展二叉树的前序遍历序列。

Output输出该二叉树的宽度。

SampleInput3AB#D##C##ABD##E##C#F##HDA##C#B##GF#E###

SampleOutput233//9067ANSWERCODE1#include<iostream>usingnamespacestd;structBiNode{chardata;BiNode*lchild,*rchild,*parent;intlevel;BiNode(){parent=NULL;level=1;}};classBiTree{public: BiTree(){root=Creat(); } ~BiTree(){Release(root);} voidPreOrder(){PreOrder(root);} private: BiNode*root; BiNode*Creat(); voidPreOrder(BiNode*root); voidRelease(BiNode*root); };intW[51];intmain(){ intn,i,max;cin>>n; while(n--){ max=0; for(i=0;i<51;i++)W[i]=0; BiTreebt; bt.PreOrder(); for(i=0;i<51;i++){if(W[i]>max)max=W[i];} cout<<max<<endl; } return0;}BiNode*BiTree::Creat(){ charch;BiNode*p; cin>>ch; if(ch=='#')p=NULL; else{ p=newBiNode;p->data=ch; p->lchild=Creat();if(p->lchild){p->lchild->parent=p;} p->rchild=Creat();if(p->rchild){p->rchild->parent=p;} } returnp;}voidBiTree::PreOrder(BiNode*root){ if(root==NULL)return; else{ if(root->parent)root->level=root->parent->level+1; W[root->level]=W[root->level]+1; PreOrder(root->lchild); PreOrder(root->rchild); }}voidBiTree::Release(BiNode*root){ if(root!=NULL) { Release(root->lchild); Release(root->rchild); deleteroot; }}//9067ANSWERCODE2#include<iostream>usingnamespacestd;intsum[100];structBiNode{chardata;BiNode*lchild,*rchild;};BiNode*Creat(inti){ BiNode*p;charch; cin>>ch; if(ch=='#') returnNULL; else { p=newBiNode; p->data=ch; sum[i]++; p->lchild=Creat(i+1); p->rchild=Creat(i+1); } returnp;}intmain(){ intn,i,width;BiNode*root; while(cin>>n) { while(n--) { memset(sum,0,sizeof(sum)); root=Creat(1); width=0; for(i=1;i<100;i++) if(width<sum[i])width=sum[i]; cout<<width<<endl; } } return0;}第十次作业：图的邻接矩阵及遍历9070，9072，90879070:求度最大的顶点编号

ProblemDescription设有一无向图G，采用邻接矩阵存储，现要求设计一个函数，用于求图中度数最大的顶点，并输出其对应的存储编号（下标）。（注：度数最大的顶点可能有多个）

Input有多组测试数据，每组数据的第一行表示图的顶点数n和图的边数e（0<n<20），第二行表示各顶点的值，按输入顺序进行存储，后面有e行，每一行表示每条边所依附的顶点的存储编号（下标），两个下标之间用空格隔开。

Output度数最大的顶点对应的存储编号（下标），各下标之间用空格隔开。

SampleInput44ABCD01031213

SampleOutput1//9070ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,e,i,j,degree[20],max,maxi;charV[20]; while(cin>>n>>e>>V) { for(i=0;i<n;i++)degree[i]=0; for(intk=0;k<e;k++) {cin>>i>>j;degree[i]++;degree[j]++;} max=degree[0];maxi=0; for(i=0;i<n;i++) {if(degree[i]>=max){max=degree[i];maxi=i;} } for(i=0;i<n;i++) {if(degree[i]==max&&i!=maxi)cout<<i<<""; } cout<<maxi<<endl; } return0;}//9070ANSWERCODE2#include<iostream>usingnamespacestd;intmain(){ intn,e,i,j,k,Max,f,degree[20],arc[20][20]; charVex[20]; while(cin>>n>>e>>Vex) { for(i=0;i<n;i++) {for(j=0;j<n;j++)arc[i][j]=0;} for(k=0;k<e;k++) {cin>>i>>j;arc[i][j]=1;arc[j][i]=1;} Max=0; for(i=0;i<n;i++) { degree[i]=0; for(j=0;j<n;j++){if(arc[i][j]==1)degree[i]++;} if(degree[i]>Max)Max=degree[i]; } f=0; for(i=0;i<n;i++) { if(degree[i]==Max) {if(f==0)cout<<i;elsecout<<""<<i; f=1;} } cout<<endl; } return0;}9072:存储网图

ProblemDescription设有一无向网图，其顶点值为字符型并假设各值互不相等，采用邻接矩阵表示法存储表示。设计一个算法，存储该网图并输出其邻接矩阵。

Input有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0<n<20）；第二行为其n个顶点的值，按输入顺序进行存储；后面有e行，表示e条边的信息，每条边信息占一行，包括边所依附的顶点下标i和j，以及边上的权值w（可为负），设三者均为整型，数据之间用空格隔开。

Output输出该网图的邻接矩阵，每组输出占n行，每行有n个数据，每两个数据之间用一个空格隔开，若无边用'#'表示。

SampleInput44ABCD014033126138

SampleOutput04#34068#60#38#0//9072ANSWERCODE1#include<iostream>usingnamespacestd;intmain(){ intn,e,i,j,k,w,arc[20][20];charVex[20]; while(cin>>n>>e>>Vex) { for(i=0;i<n;i++) {for(j=0;j<n;j++){arc[i][j]=10000;}} for(i=0;i<n;i++)arc[i][i]=0; for(k=0;k<e;k++) { cin>>i>>j>>w; arc[i][j]=w; arc[j][i]=w; } for(i=0;i<n;i++) { for(j=0;j<(n-1);j++) { if(arc[i][j]==10000){cout<<'#'<<"";} elsecout<<arc[i][j]<<""; } if(arc[i][j]==10000){cout<<'#'<<endl;} elsecout<<arc[i][j]<<endl; } } return0;}9087:邻接矩阵遍历

ProblemDescription给出一个无向图的各个点之间的邻接关系，输出遍历序列。

Input有多组数据，每组数据第一行有两个整数n、m,(0<n,m<100)，n表示是有n个点（1~n）形成的图，接下来有m行数据，每一行有两个整数（表示点的序号），说明这两点之间有一条边。

Output分别输出从标号为1点开始深度和广度优先搜索的序列，每个数之后有一个空格。每个序列分别占一行。

SampleInput89121324253637454867

SampleOutput1245836712345678//9087ANSWERCODE1#include<iostream>usingnamespacestd;intn,visited[100],visited2[100],arc[100][100];voidDFS(intv){ cout<<v<<"";visited[v]=1; for(intj=1;j<=n;j++) {if(arc[v][j]==1&&visited[j]==0)DFS(j);} }voidBFS(intv){ intfront=-1,rear=-1,Q[100]; cout<<v<<"";visited2[v]=1; Q[++rear]=v; while(front!=rear) { v=Q[++front]; for(intj=1;j<=n;j++) if(arc[v][j]==1&&visited2[j]==0) {cout<<j<<"";visited2[j]=1;Q[++rear]=j;} }}voidmain(){ intm,i,j,k; while(cin>>n>>m) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++)arc[i][j]=0;} for(k=0;k<m;k++) {cin>>i>>j;arc[i][j]=arc[j][i]=1;} for(i=1;i<=n;i++) {visited[i]=0;visited2[i]=0;} DFS(1);cout<<endl; BFS(1);cout<<endl; }}第十一次作业：图的生成树9076，9077，90889076:深度优先生成树

ProblemDescription设有一连通无向图，其顶点值为字符型并假设各值互不相等，采用邻接矩阵表示法存储表示。利用DFS算法求其深度优先生成树（从下标0的顶点开始遍历），并在遍历过程中输出深度优先生成树的每一条边。

Input有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0<n<20）；第二行为其n个顶点的值，按输入顺序进行存储；后面有e行，表示e条边的信息，每条边信息占一行，包括边所依附的顶点下标i和j，数据之间用空格隔开。

Output输出深度优先生成树的每一条边，每组输出占一行，每条边信息之间有一空格，每行最后均有一空格，具体格式见样例。

SampleInput44ABCD01031213

SampleOutput(A,B)(B,C)(B,D)//9076ANSWERCODE1#include<iostream>usingnamespacestd;intn,visited[100],arc[100][100];charvertex[20];voidDFS_spanningTree(intv){ visited[v]=1; for(intj=0;j<n;j++) { if(arc[v][j]==1&&visited[j]==0) { cout<<"("<<vertex[v]<<","<<vertex[j]<<")"; DFS_spanningTree(j); } } }voidmain(){ inte,i,j,k; while(cin>>n>>e>>vertex) { for(i=0;i<n;i++) { for(j=0;j<n;j++)arc[i][j]=0;} for(k=0;k<e;k++) {cin>>i>>j;arc[i][j]=arc[j][i]=1;} for(i=0;i<n;i++){visited[i]=0;} DFS_spanningTree(0);cout<<endl; }}9077:广度优先生成树

ProblemDescription设有一连通无向图，其顶点值为字符型并假设各值互不相等，采用邻接矩阵表示法存储表示。利用BFS算法求其广度优先生成树（从下标0的顶点开始遍历），并在遍历过程中输出广度优先生成树的每一条边。

Input有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0<n<20）；第二行为其n个顶点的值，按输入顺序进行存储；后面有e行，表示e条边的信息，每条边信息占一行，包括边所依附的顶点下标i和j，数据之间用空格隔开。

Output输出广度优先生成树的每一条边，每组输出占一行，每条边信息之间有一空格，每行最后均有一空格，具体格式见样例。

SampleInput44ABCD01031213

SampleOutput(A,B)(A,D)(B,C)//9077ANSWERCODE1#include<iostream>usingnamespacestd;intn,visited[100],arc[100][100];charvertex[20];voidBFS_spanningTree(intv){ intfront=-1,rear=-1,Q[100];; visited[v]=1;Q[++rear]=v; while(front!=rear) { v=Q[++front]; for(intj=0;j<n;j++) if(arc[v][j]==1&&visited[j]==0){ cout<<"("<<vertex[v]<<","<<vertex[j]<<")"; visited[j]=1;Q[++rear]=j; } }}voidmain(){ inte,i,j,k; while(cin>>n>>e>>vertex) { for(i=0;i<n;i++) { for(j=0;j<n;j++)arc[i][j]=0;} for(k=0;k<e;k++) {cin>>i>>j;arc[i][j]=arc[j][i]=1;} for(i=0;i<n;i++){visited[i]=0;} BFS_spanningTree(0);cout<<endl; }}9088:村村相连

ProblemDescription漳州市政府调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。市政府的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(N<100)和M；随后的M行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N、M为0时，输入结束，该用例不被处理。

Output对每个测试用例，在1行里输出最小的公路总长度，如果未能找到请输出"nofound!"。

SampleInput331211322344612113414123324234500

SampleOutput35//9088ANSWERCODE1#include<iostream>usingnamespacestd;intn,arc[100][100];voidPrim(){ inti,j,k,count_cc=1;//当count_cc=n时连通，否则不连通输出nofound! intlength=0;//最小的公路总长度（即最小生成树的代价） intlowcost[100],adjvex[100]; for(i=2;i<=n;i++)//初始化lowcost[]和adjvex[] { lowcost[i]=arc[1][i]; adjvex[i]=1; } lowcost[1]=0;//将顶点0加入集合U中 for(i=2;i<=n;i++) { intweight_min=10000;k=0; for(j=2;j<=n;j++) { if(lowcost[j]!=0&&lowcost[j]!=10000&&lowcost[j]<weight_min) {weight_min=lowcost[j];k=j;} } if(lowcost[k]==10000||k==0)break; count_cc++; length=length+lowcost[k]; lowcost[k]=0;//将顶点k加入集合U中 for(j=2;j<=n;j++)//调整lowcost和adjvex if(arc[k][j]<lowcost[j]) { lowcost[j]=arc[k][j];adjvex[j]=k; } } if(count_cc==n) cout<<length<<endl; elsecout<<"nofound!\n";}voidmain(){ intm,i,j,k,w;; while(cin>>n>>m) { if(n==0)return; for(i=1;i<=n;i++) {for(j=1;j<=n;j++){arc[i][j]=10000;}} for(i=1;i<=n;i++)arc[i][i]=0; for(k=0;k<m;k++)//依次输入每一条边，并修改邻接矩阵的相应元素 { cin>>i>>j>>w;//边依附的两个顶点的序号 arc[i][j]=w;//置有边标志 arc[j][i]=w; } Prim(); } }第十二次作业：图的最短路径9092，9091，90859092:最短路

ProblemDescription“水上之都”威尼斯水城是个美丽的地方，ax幻想着某天能够去那里旅游！

一天，ax想到一个问题：威尼斯由许多n个小岛（由0到n-1编号）以及m座桥梁连成一体！假设ax在s号小岛上，要去t号小岛游玩！那么s到t的最短距离是多少！

Input本题目包含多组数据，每组数据第一行包含两个正整数n和m(0<n<200,0<m<1000)，分别代表现有小岛的数目和已修建桥梁的数目。接下来是m行桥梁的信息，每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示小岛A和小岛B之间有一条长度为X的桥梁：再接下一行有两个整数s,t(0<=s,t<n)，分别代表起点和终点。

Output对于每组数据，请在一行里输出最短距离，如果不存在s到t的路径则输出"notfound!"。

SampleInput33011023121023101112

SampleOutput2notfound!//9092ANSWERCODE1#include<iostream>usingnamespacestd;intn,arc[200][200];voidDijk(intv,intv_end)//v源点，v_end终点{ intdist[200],S[200],i,k,num,min; for(i=0;i<n;i++){dist[i]=arc[v][i];} S[0]=v;dist[v]=0;num=1; while(num<n)//当S[]中的顶点数小于图的顶点数时循环 { min=10000;k=v;//min为dist[]最小值的下标kfor(i=0;i<n;i++) { if(dist[i]!=0&&dist[i]<min) {min=dist[i];k=i;} } for(i=0;i<n;i++)//修改dist[] { if(dist[i]>dist[k]+arc[k][i]) { dist[i]=dist[k]+arc[k][i]; } } S[num++]=k;//将k加入集合S if(k==v_end&&dist[v_end]<10000) {cout<<dist[v_end]<<endl;return;} dist[k]=0;//置k为已生成终点 } cout<<"notfound!\n";}voidmain(){ intm,s,t,i,j,k,w; while(cin>>n>>m) { for(i=0;i<n;i++){for(j=0;j<n;j++)arc[i][j]=10000;} for(i=0;i<n;i++)arc[i][i]=0; for(k=0;k<m;k++) {cin>>i>>j>>w;arc[i][j]=w;} cin>>s>>t; Dijk(s,t); } }9091:名次排序

ProblemDescription有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input输入有若干组，每组中的第一行为二个数N（1<=N<=500）和M，其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1和P2，表示P1队赢了P2队。

Output给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

SampleInput43122343

SampleOutput1243//9091ANSWERCODE1#include<iostream>usingnamespacestd;intn,arc[500][500];voidmain(){ intm,i,j,k,f,num,indg[500],visit[500]; while(cin>>n>>m) { for(i=1;i<=n;i++){for(j=1;j<=n;j++)arc[i][j]=0;} for(k=0;k<m;k++){cin>>i>>j;arc[i][j]=1;} for(i=1;i<=n;i++){indg[i]=0;visit[i]=0;} for(j=1;j<=n;j++) {for(i=1;i<=n;i++){indg[j]+=arc[i][j];}} f=0;num=0; while(num<n) { for(i=1;i<=n;i++) { if(indg[i]==0&&visit[i