ln17.c

有关数据结构的一些例子。用C语言编写的。非常有价值的程序。对初学者有指导借鉴意义。

#include "stdio.h"
#define maxsize 1024
#define NULL 0
#define n 8                /*图的顶点数*/
#define e 9                /*图的边数*/
typedef char vextype;      /*顶点数据类型*/
typedef int adjtype;       /*权值类型*/
typedef int datatype;

typedef struct
{ vextype vexs[n];
  adjtype arcs[n][n];
} graph;
graph *S,*g;
int i=1,m,l,visited[n];

typedef struct
{ datatype data[maxsize];
  int front,rear;
} sequeue;
sequeue *Q;

CREAT(ga)
graph *ga;
{ int i,j,k,w;
  char ch;
  printf("\n图的顶点信息:\n");
  for(i=0;i<n;i++)
   { scanf("%c",&ch);
     ga->vexs[i]=ch;
     printf("%c\t",ga->vexs[i]);
   }
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      ga->arcs[i][j]=0;
  for(k=0;k<e;k++)
   { printf("\nvi,vj,weight:\t");
     scanf("%d%d%d",&i,&j,&w);
     ga->arcs[i][j]=w;
     ga->arcs[j][i]=w;
   }
  printf("图的邻接矩阵:\n");
  for(k=0;k<n;k++)
   { for(j=0;j<n;j++)
       printf("%d\t",ga->arcs[k][j]);
       printf("\n\n");
   }
}

SETNULL(s)
sequeue *s;
{ s->front=3;
  s->rear=3;
}

int EMPTY(s)
sequeue *s;
{ if(s->rear==s->front)
    return(1);
  else
    return(0);
}

ENQUEUE(s,x)
sequeue *s;
datatype x;
{ if(s->front==(s->rear+1)%maxsize)
	printf("queue is full");
  else
	{ s->rear=(s->rear+1)%maxsize;
	  s->data[s->rear]=x;
	}
}

int DEQUEUE(s)
sequeue *s;
{ if(s->rear==s->front)
  {    printf("queue is empty");
       return(NULL);
  }
  else
  { s->front=(s->front+1)%maxsize;
	return(s->data[s->front]);
  }
}

DFS(i)
{ int j;
  printf("结点:%c\n",g->vexs[i]);
  visited[i]=1;
  for(j=0;j<n;j++)
     if((g->arcs[i][j]!=0) && (!visited[j]))
       DFS(j);
}

BFS(i)
{ int a,b,k;
  SETNULL(Q);
  for(k=0;k<n;k++)
  visited[k]=0;
  printf("结点:%c\n",g->vexs[i]);
  visited[i]=1;
  ENQUEUE(Q,i);
  while(!EMPTY(Q))
  { a=DEQUEUE(Q);
	for(b=0;b<n;b++)
	  if((g->arcs[a][b]!=0) && (!visited[b]))
	   {  printf("结点:%c\n",g->vexs[b]);
		 visited[b]=1;
		 ENQUEUE(Q,b);
	   }
  }
}

main()
{
  CREAT(S);
  getchar();
  g=S;
  printf("深度遍历:\n");
  DFS(m);
  printf("广度遍历:\n");
  BFS(l);
  getchar();
}