ch6_1.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include <stdio.h>
#include <stdlib.h>
typedef struct node                    /* 声明结点为结构变量 */
{
  int vertex;                                   /* 结点的编号 */
  struct node *nextnode;              /* 指向下一结点的地址 */
}Node;
Node head[9];                             /* 声明首结点的数组 */
int visited[9];                                  /* 遍历记录 */
void Graph(int node[][2], int);  
void DFS(int);
void main( )
{
  Node *W;
                                            /* 记录所有边的数组 */
  int node[20][2]={{ 1, 2 }, { 2, 1 },
	           { 1, 3 }, { 3, 1 },
		   { 2, 4 }, { 4, 2 },
		   { 2, 5 }, { 5, 2 },
		   { 3, 6 }, { 6, 3 },
       		   { 3, 7 }, { 7, 3 },
		   { 4, 8 }, { 8, 4 },
		   { 5, 8 }, { 8, 5 },
		   { 6, 8 }, { 8, 6 },
		   { 7, 8 }, { 8, 7 }};
  int i;
  for(i=1; i<=8; i++)
  {
    head[i].vertex=i;                          /* 建立头结点 */
    head[i].nextnode=NULL;
    visited[i]=0;
  }
  Graph(node, 20);                             /* 建立图 */
  printf("图的邻接表内容如下:\n");
  for(i=1; i<=8; i++)
  {
    printf("V%d=>", head[i].vertex);
    W=head[i].nextnode;
    while(W != NULL)                       /* 遍历至链表尾 */
    {
      printf(" %d ", W->vertex);
      W=W->nextnode;
    }
    printf("\n");
  }
  printf("图的深度优先搜索顺序:\n");              /* 输出遍历过程 */ 
  DFS(1);
  printf("\n");
}

void Graph(int node[][2], int num)                   /* 建立图 */
{
  Node *newnode;                                /* 新结点指针 */
  Node *ptr;
  int from;                                            /* 起点 */
  int to;                                              /* 终点 */
  int i;
  for(i=0; i<num; i++)                               /* 读取边 */
  {
	 from=node[i][0];
	 to =node[i][1];
	 newnode=(Node *)malloc(sizeof(Node));        /* 建立新结点 */ 
	 newnode->vertex=to;
	 newnode->nextnode=NULL;
	 ptr=&(head[from]);
	 while(ptr->nextnode != NULL)          /* 遍历至链表的最后 */
	   ptr=ptr->nextnode;                 /* 将边加到链表中 */
	 ptr->nextnode=newnode;
  }
}

void DFS(int V)                                /* 深度优先搜索法 */
{
  Node *W;
  visited[V]=1;                            /* 记录已遍历过的顶点 */
  printf("V%d ", V);
  W=head[V].nextnode;
  while(W != NULL)                         /* 遍历至链表的最后 */
  {	                             /* 若未遍历过，则调用DFS子程序 */
    if(visited[W->vertex] == 0)
      DFS(W->vertex);
    W=W->nextnode;
  }
}