C语言数据结构-algo7-1.c

blake

1. /* algo7-1.c 调用算法7.7、7.8 */
   
2. #include"c1.h"
   
3. #define MAX_NAME 2 /* 顶点字符串的最大长度+1 */
   
4. typedef char ElemType[MAX_NAME];
   
5. typedef ElemType TElemType;
   
6. #include"c6-5.h"
   
7. typedef int InfoType;
   
8. typedef char VertexType[MAX_NAME];
   
9. #include"c7-2.h"
   
10. #include"bo7-2.c"
    
11. 
    
12. void DFSTree(ALGraph G,int v,CSTree *T)
    
13. { /* 从第v个顶点出发深度优先遍历图G,建立以T为根的生成树。算法7.8 */
    
14.    Boolean first=TRUE;
    
15.    int w;
    
16.    CSTree p,q;
    
17.    VertexType v1,w1;
    
18.    visited[v]=TRUE;
    
19.    strcpy(v1,*GetVex(G,v));
    
20.    for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)))) /* w依次为v的邻接顶点 */
    
21.      if(!visited[w]) /* w顶点不曾被访问 */
    
22.      {
    
23.        p=(CSTree)malloc(sizeof(CSNode)); /* 分配孩子结点 */
    
24.        strcpy(p->data,*GetVex(G,w));
    
25.        p->firstchild=NULL;
    
26.        p->nextsibling=NULL;
    
27.        if(first)
    
28.        { /* w是v的第一个未被访问的邻接顶点 */
    
29.          (*T)->firstchild=p;
    
30.          first=FALSE; /* 是根的第一个孩子结点 */
    
31.        }
    
32.        else /* w是v的其它未被访问的邻接顶点 */
    
33.          q->nextsibling=p; /* 是上一邻接顶点的兄弟姐妹结点 */
    
34.        q=p;
    
35.        DFSTree(G,w,&q); /* 从第w个顶点出发深度优先遍历图G,建立子生成树q */
    
36.      }
    
37. }
    
38. 
    
39. void DFSForest(ALGraph G,CSTree *T)
    
40. { /* 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T。算法7.7 */
    
41.    CSTree p,q;
    
42.    int v;
    
43.    *T=NULL;
    
44.    for(v=0;v<G.vexnum;++v)
    
45.      visited[v]=FALSE; /* 赋初值 */
    
46.    for(v=0;v<G.vexnum;++v) /* 从第0个顶点找起 */
    
47.      if(!visited[v])
    
48.      { /* 第v顶点为新的生成树的根结点 */
    
49.        p=(CSTree)malloc(sizeof(CSNode)); /* 分配根结点 */
    
50.        strcpy(p->data,*GetVex(G,v));
    
51.        p->firstchild=NULL;
    
52.        p->nextsibling=NULL;
    
53.        if(!*T) /* 是第一棵生成树的根(T的根) */
    
54.          *T=p;
    
55.        else /* 是其它生成树的根(前一棵的根的＂兄弟＂) */
    
56.          q->nextsibling=p;
    
57.        q=p; /* q指示当前生成树的根 */
    
58.        DFSTree(G,v,&p); /* 建立以p为根的生成树 */
    
59.      }
    
60. }
    
61. 
    
62. void PreOrderTraverse(CSTree T,void(*Visit)(TElemType))
    
63. { /* 先根遍历孩子－兄弟二叉链表结构的树T(bo6-5.c改) */
    
64.    if(T)
    
65.    {
    
66.      Visit(T->data); /* 先访问根结点 */
    
67.      PreOrderTraverse(T->firstchild,Visit); /* 再先根遍历长子子树 */
    
68.      PreOrderTraverse(T->nextsibling,Visit); /* 最后先根遍历下一个兄弟子树 */
    
69.    }
    
70. }
    
71. 
    
72. void print(char *i)
    
73. {
    
74.    printf("%s ",i);
    
75. }
    
76. 
    
77. void main()
    
78. {
    
79.    ALGraph g;
    
80.    CSTree t;
    
81.    printf("请选择无向图\n");
    
82.    CreateGraph(&g);
    
83.    Display(g);
    
84.    DFSForest(g,&t);
    
85.    printf("先根遍历生成森林：\n");
    
86.    PreOrderTraverse(t,print);
    
87.    printf("\n");
    
88. }

复制代码