主题:[讨论]邻接多重链表的深度优先遍历和广度优先遍历
下面是我写的数据结构上的一道关于对邻接多重表的遍历的程序,采用深度优先遍历和广度优先遍历并打印结点访问序列和相应生成树的边集。用gcc编译时提出了一大堆警告,但我检查源程序后找不出该如何匹配,请帮帮忙。下面是源代码,附件中是编译的截图.
[code=c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 30
#define CHNUM 50
#define MAX 1000
int visited[MAX_VERTEX_NUM]; //访问标志数组
typedef struct storage{
char name[CHNUM];
}storage[MAX];
typedef struct EBox{
int mark; //访问标记
int ivex, jvex; //该边依附的两个顶点的位置
struct EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
}EBox;
typedef struct VexBox{
char *name;
EBox *firstedge; //指向第一条依附该顶点的边
}VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum; //无向图的当前顶点数和边数
}AMLGraph;
typedef struct QNode{
int num;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct LinkQueue{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int LocateVex(AMLGraph Graph, char *name); //返回顶点*name在图Graph中的位置
void CreateAMLGraph(AMLGraph *Graph); //构造连通的无向图
void DFSTraverse(AMLGraph Graph, int starting); //对图Graph作深度优先遍历
void DFS(AMLGraph Graph, int v);
//从第v个顶点出发递归地深度优先遍历图Graph并打印节点访问序列和相应生成树的边集
void InitQueue(LinkQueue *Q); //初始化辅助队列
void EnQueue(LinkQueue *Q, int v); //v入队列
int DeQueue(LinkQueue *Q); //队头元素出队并置为u
int QueueEmpty(LinkQueue Q); //判断队列是否为空,若为空,返回1,否则返回0
void BFSTraverse(AMLGraph Graph, int starting);
//按广度优先非递归遍历图Graph并打印节点访问序列和相应生成树的边集
int main(){
AMLGraph Graph;
LinkQueue Q;
char *name;
int vertex;
int i, starting;
CreateAMLGraph(&Graph);
printf("Please indicate the starting vertex using DFSTraverse method:\t");
scanf(" %s", name);
starting = LocateVex(Graph, name);
DFSTraverse(Graph, starting);
printf("Please indicate the starting vertex using BFSTraverse method:\t");
scanf(" %s", name);
starting = LocateVex(Graph, name);
BFSTraverse(Graph, starting);
return 0;
}
//返回顶点*name在图Graph中的位置
int LocateVex(AMLGraph Graph, char *name){
int i;
for (i = 0; i < Graph.vexnum; i++)
if (strcmp(name, Graph.adjmulist[i].name))
return i;
return -1;
}
//构造连通的无向图
void CreateAMLGraph(AMLGraph *Graph){
int i, j, k;
char *v1, *v2;
EBox *p, *tmp;
printf("Please enter the number of vertex and edge:\t");
scanf("%d %d", &Graph->vexnum, &Graph->edgenum);
printf("Please enter the data of each vertex:\n");
for (i = 0; i < Graph->vexnum; i++){ //构造表头向量
scanf("%s", Graph->adjmulist[i].name); //输入顶点值
Graph->adjmulist[i].firstedge = NULL; //初始化指针
}
printf("Please enter the two vertexs of each edge:\n");
for (k = 0; k < Graph->edgenum; k++){ //输入各边并构造邻接多重表
scanf("%s %s", v1, v2); //输入一条边的两个端点
i = LocateVex(*Graph, v1);
j = LocateVex(*Graph, v2);
if (!(p = (EBox *) malloc(sizeof(EBox)))){
printf("No enough memory!\n");
exit (0);
}
p->mark = 0;
p->ivex = i;
p->jvex = j;
p->ilink = p->jlink = NULL;
if (Graph->adjmulist[i].firstedge == NULL)
Graph->adjmulist[i].firstedge = p;
else if (Graph->adjmulist[i].firstedge != NULL){
tmp = Graph->adjmulist[i].firstedge->ilink;
while (tmp->ilink != NULL)
tmp = tmp->ilink;
tmp = p;
}
else if (Graph->adjmulist[j].firstedge == NULL)
Graph->adjmulist[j].firstedge = p;
else if (Graph->adjmulist[j].firstedge != NULL){
tmp = Graph->adjmulist[j].firstedge->jlink;
while (tmp->jlink != NULL)
tmp = tmp->jlink;
tmp = p;
}
}
}
//对图Graph作深度优先遍历
void DFSTraverse(AMLGraph Graph, int starting){
int i;
for (i = 0; i < Graph.vexnum; i++)
visited[i] = 0;
if (!visited[starting])
DFS(Graph, starting); //对指定的顶点调用DFS
for (i = 0; i < Graph.vexnum; i++){
if (i != starting && !visited[i])
DFS(Graph, i); //对除指定的顶点外未访问的顶点调用DFS
}
}
//从第v个顶点出发递归地深度优先遍历图Graph,并打印节点访问序列和相应生成树的边集
void DFS(AMLGraph Graph, int v){
storage stor;
EBox *tmp = Graph.adjmulist[v].firstedge;
int adj,i, indicator = 0;
int flag = 0; //标志变量,0表示ivex,1表示jvex;
stor[indicator].name[CHNUM] = *Graph.adjmulist[v].name;
visited[v] = 1;
adj = tmp->jvex;
while (adj >= 0){
//对v的尚未访问的邻接顶点now递归调用DFS
indicator++;
if (!visited[adj])
DFS(Graph, adj);
stor[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
//通过对标志变量flag的判断来决定下个邻接点
if (!flag){
tmp = tmp->jlink;
adj = tmp->ivex;
flag = 1;
}
else{
tmp = tmp->ilink;
adj = tmp->jvex;
flag = 0;
}
}
stor[indicator+1].name[CHNUM] = "Empty";
//打印访问节点次序
printf("Print the sequence of calling vertex using DFSTraverse:\v");
for (i = 0; stor[i].name[CHNUM] != "Empty"; i++)
printf("%s\t", stor[i].name[CHNUM]);
//打印相应生成树的边集
printf("Print the set of called edges:\v");
for (i = 1; stor[i].name[CHNUM] != "Empty"; i++)
printf("%s----%s\t", stor[i-1].name[CHNUM], stor[i].name[CHNUM]);
}
//初始化辅助队列
void InitQueue(LinkQueue *Q){
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front){
printf("No enough memory!\n");
exit(0);
}
}
//v入队列
void EnQueue(LinkQueue *Q, int v){
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p){
printf("No enough memory!\n");
exit(0);
}
p->num = v;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
//队头元素出队
int DeQueue(LinkQueue *Q){
QueuePtr p;
int tmp;
if (Q->front == Q->rear)
exit (-1);
p = Q->front->next;
tmp = p->num;
Q->front->next = p->next;
if (Q->rear == p)
Q->rear = Q->front;
free(p);
return tmp;
}
//判断队列是否为空,若为空,返回1,否则返回0
int QueueEmpty(LinkQueue Q){
if (Q.front == Q.rear)
return 1;
else
return 0;
}
//按广度优先非递归遍历图Graph,并打印节点访问序列和相应生成树的边集
void BFSTraverse(AMLGraph Graph, int starting){
storage stor1;
EBox *tmp = Graph.adjmulist[starting].firstedge;
int adj, i, u, indicator = 1;
LinkQueue Q;
for (i = 0; i < Graph.vexnum; i++)
visited[i] = 0;
InitQueue(&Q);
stor1[indicator-1].name[CHNUM] = *Graph.adjmulist[starting].name;
adj = tmp->jvex;
stor1[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
EnQueue(&Q, adj);
while (!QueueEmpty(Q)){
u = DeQueue(&Q);
tmp = tmp->ilink;
adj = tmp->jvex;
while (adj >= 0){
indicator++;
visited[adj] = 1;
EnQueue(&Q, adj);
stor1[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
tmp = tmp->ilink;
adj = tmp->jvex;
}
}
stor1[++indicator].name[CHNUM] = "Next"; //标志从指定结点开始的广度优先搜索结束
for (i = 0; i < Graph.vexnum; i++){
if (!visited[i]){
indicator++;
visited[i] = 1;
stor1[indicator].name[CHNUM] = *Graph.adjmulist[i].name;
EnQueue(&Q, i);
while (!QueueEmpty(Q)){
u = DeQueue(&Q);
tmp = tmp->ilink;
adj = tmp->jvex;
while (adj >= 0){
indicator++;
visited[adj] = 1;
EnQueue(&Q, adj);
stor1[indicator].name[CHNUM] = Graph.adjmulist[adj].name;
tmp = tmp->ilink;
adj = tmp->jvex;
}
}
}
stor1[++indicator].name[CHNUM] = "Next"; //标志从这个顶点开始的广度优先搜索结束
}
stor1[++indicator].name[CHNUM] = "Empty"; //标志广度优先搜索结束
//打印访问结点次序
printf("Print the sequentce of calling vertex using BFSTraverse:\n");
for (i = 0; stor1[i].name[CHNUM] != "Empty"; i++ ){
if (stor1[i].name[CHNUM] != "Next")
printf("%s\t", stor1[i].name[CHNUM]);
}
//打印相应生成树的边集
printf("Print the set of called edges:\n");
int temp = 0;
for (i = 1; stor1[i].name[CHNUM] != "Empty"; i++){
if (stor1[i].name[CHNUM] != "Next")
printf("%s----%s\t", stor1[temp].name[CHNUM], stor1[i].name[CHNUM]);
else
temp = ++i;
}
}
[/code]
[code=c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 30
#define CHNUM 50
#define MAX 1000
int visited[MAX_VERTEX_NUM]; //访问标志数组
typedef struct storage{
char name[CHNUM];
}storage[MAX];
typedef struct EBox{
int mark; //访问标记
int ivex, jvex; //该边依附的两个顶点的位置
struct EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
}EBox;
typedef struct VexBox{
char *name;
EBox *firstedge; //指向第一条依附该顶点的边
}VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum; //无向图的当前顶点数和边数
}AMLGraph;
typedef struct QNode{
int num;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct LinkQueue{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int LocateVex(AMLGraph Graph, char *name); //返回顶点*name在图Graph中的位置
void CreateAMLGraph(AMLGraph *Graph); //构造连通的无向图
void DFSTraverse(AMLGraph Graph, int starting); //对图Graph作深度优先遍历
void DFS(AMLGraph Graph, int v);
//从第v个顶点出发递归地深度优先遍历图Graph并打印节点访问序列和相应生成树的边集
void InitQueue(LinkQueue *Q); //初始化辅助队列
void EnQueue(LinkQueue *Q, int v); //v入队列
int DeQueue(LinkQueue *Q); //队头元素出队并置为u
int QueueEmpty(LinkQueue Q); //判断队列是否为空,若为空,返回1,否则返回0
void BFSTraverse(AMLGraph Graph, int starting);
//按广度优先非递归遍历图Graph并打印节点访问序列和相应生成树的边集
int main(){
AMLGraph Graph;
LinkQueue Q;
char *name;
int vertex;
int i, starting;
CreateAMLGraph(&Graph);
printf("Please indicate the starting vertex using DFSTraverse method:\t");
scanf(" %s", name);
starting = LocateVex(Graph, name);
DFSTraverse(Graph, starting);
printf("Please indicate the starting vertex using BFSTraverse method:\t");
scanf(" %s", name);
starting = LocateVex(Graph, name);
BFSTraverse(Graph, starting);
return 0;
}
//返回顶点*name在图Graph中的位置
int LocateVex(AMLGraph Graph, char *name){
int i;
for (i = 0; i < Graph.vexnum; i++)
if (strcmp(name, Graph.adjmulist[i].name))
return i;
return -1;
}
//构造连通的无向图
void CreateAMLGraph(AMLGraph *Graph){
int i, j, k;
char *v1, *v2;
EBox *p, *tmp;
printf("Please enter the number of vertex and edge:\t");
scanf("%d %d", &Graph->vexnum, &Graph->edgenum);
printf("Please enter the data of each vertex:\n");
for (i = 0; i < Graph->vexnum; i++){ //构造表头向量
scanf("%s", Graph->adjmulist[i].name); //输入顶点值
Graph->adjmulist[i].firstedge = NULL; //初始化指针
}
printf("Please enter the two vertexs of each edge:\n");
for (k = 0; k < Graph->edgenum; k++){ //输入各边并构造邻接多重表
scanf("%s %s", v1, v2); //输入一条边的两个端点
i = LocateVex(*Graph, v1);
j = LocateVex(*Graph, v2);
if (!(p = (EBox *) malloc(sizeof(EBox)))){
printf("No enough memory!\n");
exit (0);
}
p->mark = 0;
p->ivex = i;
p->jvex = j;
p->ilink = p->jlink = NULL;
if (Graph->adjmulist[i].firstedge == NULL)
Graph->adjmulist[i].firstedge = p;
else if (Graph->adjmulist[i].firstedge != NULL){
tmp = Graph->adjmulist[i].firstedge->ilink;
while (tmp->ilink != NULL)
tmp = tmp->ilink;
tmp = p;
}
else if (Graph->adjmulist[j].firstedge == NULL)
Graph->adjmulist[j].firstedge = p;
else if (Graph->adjmulist[j].firstedge != NULL){
tmp = Graph->adjmulist[j].firstedge->jlink;
while (tmp->jlink != NULL)
tmp = tmp->jlink;
tmp = p;
}
}
}
//对图Graph作深度优先遍历
void DFSTraverse(AMLGraph Graph, int starting){
int i;
for (i = 0; i < Graph.vexnum; i++)
visited[i] = 0;
if (!visited[starting])
DFS(Graph, starting); //对指定的顶点调用DFS
for (i = 0; i < Graph.vexnum; i++){
if (i != starting && !visited[i])
DFS(Graph, i); //对除指定的顶点外未访问的顶点调用DFS
}
}
//从第v个顶点出发递归地深度优先遍历图Graph,并打印节点访问序列和相应生成树的边集
void DFS(AMLGraph Graph, int v){
storage stor;
EBox *tmp = Graph.adjmulist[v].firstedge;
int adj,i, indicator = 0;
int flag = 0; //标志变量,0表示ivex,1表示jvex;
stor[indicator].name[CHNUM] = *Graph.adjmulist[v].name;
visited[v] = 1;
adj = tmp->jvex;
while (adj >= 0){
//对v的尚未访问的邻接顶点now递归调用DFS
indicator++;
if (!visited[adj])
DFS(Graph, adj);
stor[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
//通过对标志变量flag的判断来决定下个邻接点
if (!flag){
tmp = tmp->jlink;
adj = tmp->ivex;
flag = 1;
}
else{
tmp = tmp->ilink;
adj = tmp->jvex;
flag = 0;
}
}
stor[indicator+1].name[CHNUM] = "Empty";
//打印访问节点次序
printf("Print the sequence of calling vertex using DFSTraverse:\v");
for (i = 0; stor[i].name[CHNUM] != "Empty"; i++)
printf("%s\t", stor[i].name[CHNUM]);
//打印相应生成树的边集
printf("Print the set of called edges:\v");
for (i = 1; stor[i].name[CHNUM] != "Empty"; i++)
printf("%s----%s\t", stor[i-1].name[CHNUM], stor[i].name[CHNUM]);
}
//初始化辅助队列
void InitQueue(LinkQueue *Q){
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front){
printf("No enough memory!\n");
exit(0);
}
}
//v入队列
void EnQueue(LinkQueue *Q, int v){
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p){
printf("No enough memory!\n");
exit(0);
}
p->num = v;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
//队头元素出队
int DeQueue(LinkQueue *Q){
QueuePtr p;
int tmp;
if (Q->front == Q->rear)
exit (-1);
p = Q->front->next;
tmp = p->num;
Q->front->next = p->next;
if (Q->rear == p)
Q->rear = Q->front;
free(p);
return tmp;
}
//判断队列是否为空,若为空,返回1,否则返回0
int QueueEmpty(LinkQueue Q){
if (Q.front == Q.rear)
return 1;
else
return 0;
}
//按广度优先非递归遍历图Graph,并打印节点访问序列和相应生成树的边集
void BFSTraverse(AMLGraph Graph, int starting){
storage stor1;
EBox *tmp = Graph.adjmulist[starting].firstedge;
int adj, i, u, indicator = 1;
LinkQueue Q;
for (i = 0; i < Graph.vexnum; i++)
visited[i] = 0;
InitQueue(&Q);
stor1[indicator-1].name[CHNUM] = *Graph.adjmulist[starting].name;
adj = tmp->jvex;
stor1[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
EnQueue(&Q, adj);
while (!QueueEmpty(Q)){
u = DeQueue(&Q);
tmp = tmp->ilink;
adj = tmp->jvex;
while (adj >= 0){
indicator++;
visited[adj] = 1;
EnQueue(&Q, adj);
stor1[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
tmp = tmp->ilink;
adj = tmp->jvex;
}
}
stor1[++indicator].name[CHNUM] = "Next"; //标志从指定结点开始的广度优先搜索结束
for (i = 0; i < Graph.vexnum; i++){
if (!visited[i]){
indicator++;
visited[i] = 1;
stor1[indicator].name[CHNUM] = *Graph.adjmulist[i].name;
EnQueue(&Q, i);
while (!QueueEmpty(Q)){
u = DeQueue(&Q);
tmp = tmp->ilink;
adj = tmp->jvex;
while (adj >= 0){
indicator++;
visited[adj] = 1;
EnQueue(&Q, adj);
stor1[indicator].name[CHNUM] = Graph.adjmulist[adj].name;
tmp = tmp->ilink;
adj = tmp->jvex;
}
}
}
stor1[++indicator].name[CHNUM] = "Next"; //标志从这个顶点开始的广度优先搜索结束
}
stor1[++indicator].name[CHNUM] = "Empty"; //标志广度优先搜索结束
//打印访问结点次序
printf("Print the sequentce of calling vertex using BFSTraverse:\n");
for (i = 0; stor1[i].name[CHNUM] != "Empty"; i++ ){
if (stor1[i].name[CHNUM] != "Next")
printf("%s\t", stor1[i].name[CHNUM]);
}
//打印相应生成树的边集
printf("Print the set of called edges:\n");
int temp = 0;
for (i = 1; stor1[i].name[CHNUM] != "Empty"; i++){
if (stor1[i].name[CHNUM] != "Next")
printf("%s----%s\t", stor1[temp].name[CHNUM], stor1[i].name[CHNUM]);
else
temp = ++i;
}
}
[/code]