数据结构课程设计(6)

printf(\请输入该结点的值,值为零表示删除该结点：\\n\ scanf_s(\ if(a == 0) { b = NULL ; } else { b->data = a ; Create(b->chil) ; Create(b->bro) ; } }

int Depth(Tree b) { int dep1,dep2; if(!b) return 0; else { dep1=Depth(b->chil); dep2=Depth(b->bro); if(dep1+1>dep2) return (dep1+1); else return dep2; } }

int _tmain(int argc, _TCHAR* argv[]) { Tree p = NULL ; printf(\建立树的存储结构：\\n\ Create(p) ; printf(\树的深度为：\\n\ printf(\ system(\ return 0; }

图

21、输入任意的一个网，用普里姆(Prim)算法构造最小生成树。

#include \#include \#include \

typedef struct { int v ,e ; int edges[10][10] ; }Mgraph ;

void create(Mgraph & m) { int s , t; printf(\请输入网的顶点个数：\\n\ scanf_s(\m.v)) ; printf(\请输入网的边数：\\n\ scanf_s(\m.e)) ; for(int i = 0 ; i < m.v ; i++) for(int j = 0 ; j < m.v ; j++) m.edges[i][j] = 100 ; printf(\请输入各条边的信息：\\n\ for(int i =0 ; i < m.e ; i++) { printf(\请输入第%d条边的顶点：\ scanf_s(\ printf(\请输入第%d条边的权值：\ scanf_s(\m.edges[s-1][t-1])); m.edges[t][s] = m.edges[s-1][t-1] ; } }

void MiniSpanTree(Mgraph m , int u) { int a[10] , b[10] , s , t , c = 1 ,shortest = 100 , route = 0 ; for(int i = 0 ; i < m.v ; i++) a[i] = 1 ; for(int i = m.v ; i < 10 ; i++) a[i] = 0 ; for(int i = 0 ; i < 10 ; i++) b[i] = 0 ; a[u] = 0 ; b[u] = 1 ; c = 1 ; while(c)

{ for(int i = 0 ; i < 10 ; i++) { for(int j = 0 ; j < 10 ; j++) { if(a[i] == 1 && b[j] == 1) { if(shortest > m.edges[i][j]) { shortest = m.edges[i][j] ; s = i ; t = j ; c = 0 ; } } } } if(shortest != 100) { route +=shortest ; a[s] = 0 ; b[s] = 1 ; printf(\下一条最短路线为%d到%d，长度为%d\\n\m.edges[s][t]) ; } for(int i = 0 ; i < 10 ; i++) { if(a[i] == 1) c = 1 ; } shortest = 100 ; } printf(\最小生成树的总长度为：%d\\n\ }

int _tmain(int argc, _TCHAR* argv[]) { Mgraph mg ; create(mg) ; MiniSpanTree(mg , 1) ; system(\ return 0; }

22、要求建立图的存储结构（邻接表或邻接矩阵），输入任意的一个图，显示图的深度优先

搜索遍历路径。

23、要求建立图的存储结构（邻接表或邻接矩阵），输入任意的一个图，显示图的广度优先

搜索遍历路径。 #include \#include \#include \

typedef struct Arc { int next ; int weight ; struct Arc * nextArc ; }Arc ;

typedef struct Node { int data ; Arc * firstArc ; }Node , List[10] ;

typedef struct { List ver ; int nnum , anum ; }Graph ;

typedef struct QNode { int data ; struct QNode * next ; }QNode , * Queue ;

typedef struct { Queue head ; Queue rear ; }LinkQueue ;

void InitQueue(LinkQueue &Q) { Q.head = Q.rear = (Queue)malloc(sizeof(QNode)) ; Q.head->next = NULL ; }

void EnQueue(LinkQueue &Q , int e)

{ Queue p ; p = (Queue)malloc(sizeof(QNode)) ; p->data = e ; p->next = NULL ; Q.rear->next = p ; Q.rear = p ; }

void DeQueue(LinkQueue &Q , int &e) { Queue p ; p = Q.head->next ; e = p->data ; Q.head->next = p->next ; free(p); if(Q.head->next == NULL) Q.rear = Q.head ; }

int QueueEmp(LinkQueue &Q) { if(Q.head == Q.rear) return 1 ; else return 0 ; }

int visited[10] ;

void Create(Graph &G) { int v1 , v2 , w ; Arc *p,*q ; printf(\请输入顶点数和边数：\\n\ scanf_s(\G.nnum,&G.anum) ; for(int i = 0 ; i < G.nnum ; i++) { G.ver[i].data = i ; G.ver[i].firstArc = NULL ; } printf(\请输入边的信息（顶点/顶点/权重）\\n\ for(int i = 0 ; i < G.anum ; i++) {