ln18.c

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

#define maxsize 128
#define NULL 0
#define n 8
#define e 9
#include "stdio.h"
typedef char vextype;
typedef int datatype;

typedef struct node
{ int adjvex;
  struct node *next;
} edgenode;

typedef struct
{ vextype vertex;
  edgenode *link;
} vexnode;
vexnode gl[n];

typedef struct
{ datatype data[maxsize];
  int front,rear;
} sequeue;
sequeue *Q;
int i=0,m,l,visited[n];

CREAT(ha)
vexnode ha[];
{ int i,j,k;
  char p;
  edgenode *s,*q;
  printf("\n链接表:\n");
  for(i=0;i<n;i++)
  { scanf("%c",&p);
    ha[i].vertex=p;
    ha[i].link=NULL;
    printf("%c\t",ha[i].vertex);
  }
  printf("\n");
  for(k=0;k<e;k++)
  { printf("输入(vi%d,vj%d)\n",k+1,k+1);
	scanf("%d%d",&i,&j);
	s=(struct node *)malloc(sizeof(edgenode));
	s->adjvex=j;
	s->next=ha[i].link;
	ha[i].link=s;
	s=(struct node *)malloc(sizeof(edgenode));
	s->adjvex=i;
	s->next=ha[j].link;
	ha[j].link=s;
  }
  printf("链接表为:\n");
  for(i=0;i<n;i++)
   { printf("%d",i);
     q=ha[i].link;
     while(q!=NULL)
     { printf("-->");
       printf("%d",q->adjvex);
       q=q->next;
     }
     if(q==NULL)
       printf("\n");
   }
}

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

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]);
  }
}

DFSL(i)
{
  edgenode *p;
  visited[i]=0;
  printf("node:%c\n",gl[i].vertex);
  visited[i]=1;
  p=gl[i].link;
  while(p!=NULL)
  { if(visited[p->adjvex]!=1)
      DFSL(p->adjvex);
      p=p->next;
  }
}

BFSL(i)
{ int a,k;
  edgenode *p;
  SETNULL(Q);
  for(k=0;k<n;k++)
  visited[k]=0;
  printf("node:%c\n",gl[i].vertex);
  visited[i]=1;
  ENQUEUE(Q,i);
  while(!EMPTY(Q))
  { a=DEQUEUE(Q);
	p=gl[a].link;
	while(p!=NULL)
	{ if(!visited[p->adjvex])
	   { printf("node:%c\n",gl[p->adjvex].vertex);
	     visited[p->adjvex]=1;
	     ENQUEUE(Q,p->adjvex);
	   }
	   p=p->next;
	}
  }
}

main()
{
  CREAT(gl);
  getchar();
  printf("深度遍历:\n");
  DFSL(m);
  getchar();
  printf("广度遍历:\n");
  BFSL(l);
  getchar();
}