2013级DS作业和实验参考答案总汇(1)(5)

## Sample Output 2 3 3

//9067ANSWER CODE1

#include using namespace std;

struct BiNode{char data;BiNode *lchild,*rchild,*parent;int level;BiNode(){parent=NULL;level=1;}}; class BiTree{ public:

BiTree(){root=Creat(); } ~BiTree(){Release(root);} void PreOrder(){PreOrder(root);} private: BiNode *root; BiNode *Creat(); void PreOrder(BiNode *root); void Release(BiNode *root); };

int W[51]; int main(){ int n,i,max;cin>>n; while(n--){ max=0; for(i=0;i<51;i++) W[i]=0; BiTree bt; bt.PreOrder(); for(i=0;i<51;i++){if(W[i]>max) max=W[i];} cout<

BiNode *BiTree::Creat(){ char ch;BiNode *p; cin>>ch; if(ch=='#') p=NULL; else{ p=new BiNode;p->data=ch; p->lchild=Creat();if(p->lchild){p->lchild->parent=p;} p->rchild=Creat();if(p->rchild){p->rchild->parent=p;} } return p; }

void BiTree::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); } }

void BiTree::Release(BiNode *root){ if(root!=NULL) { Release(root->lchild); Release(root->rchild); delete root; } }

//9067ANSWER CODE2 #include using namespace std; int sum[100];

struct BiNode{char data;BiNode *lchild,*rchild;}; BiNode* Creat(int i) { BiNode *p;char ch; cin>>ch; if(ch=='#') return NULL; else { p=new BiNode; p->data=ch; sum[i]++; p->lchild=Creat(i+1); p->rchild=Creat(i+1); } return p; }

int main() { int n,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

第十次作业：图的邻接矩阵及遍历9070，9072，9087

9070:求度最大的顶点编号 Problem Description

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

有多组测试数据，每组数据的第一行表示图的顶点数n和图的边数e（0

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

ABCD 0 1 0 3 1 2 1 3

Sample Output

1

//9070ANSWER CODE1 #include using namespace std; int main() { int n,e,i,j,degree[20],max,maxi;char V[20]; while(cin>>n>>e>>V) { for(i=0;i>i>>j;degree[i]++;degree[j]++;} max=degree[0];maxi=0; for(i=0;i=max) {max=degree[i];maxi=i;} } for(i=0;i

}

//9070ANSWER CODE2 #include using namespace std; int main() { int n,e,i,j,k,Max,f,degree[20],arc[20][20]; char Vex[20]; while(cin>>n>>e>>Vex) { for(i=0;i>i>>j;arc[i][j]=1;arc[j][i]=1;} Max=0; for(i=0;iMax)Max=degree[i]; } f=0;

for(i=0;i

return 0;

9072:存储网图

Problem Description

}

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

有多组测试数据，每组数据的第一行为两个整数n和e，表示n个顶点和e条边（0

输出该网图的邻接矩阵，每组输出占n行，每行有n个数据，每两个数据之间用一个空格隔开，若无边用'#'表示。 Sample Input 4 4 ABCD 0 1 4 0 3 3 1 2 6 1 3 8

Sample Output

0 4 # 3 4 0 6 8 # 6 0 # 3 8 # 0

//9072ANSWER CODE1

#include using namespace std; int main() { int n,e,i,j,k,w,arc[20][20];char Vex[20]; while(cin>>n>>e>>Vex) { for (i=0; i