一.简述
栈与队列,DFS与BFS。仅以连接表为例实现。
二.头文件
BFS要用到的头文件
//3_4_part1.h
/**
author:zhaoyu
email:zhaoyu1995.com@gmail.com
date:2016-6-9
2016-6-25修改版,针对第七章
note:realize my textbook <<数据结构(C语言版)>>
*/
//Page 64
#include <cstdio>
#include "head.h"
#define QElemType int
//----循环队列:队列的顺序存储结构----
#define MAXQSIZE 10 //最大队列长度
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue;
//----循环队列的基本操作说明及实现----
Status InitQueue(SqQueue &Q)
{
//构造一个空队列 Q
Q.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if (!Q.base)
{
exit(OVERFLOW);
}
Q.front = Q.rear = ;
return OK;
}
int QueueLength(SqQueue Q)
{
//返回 Q 的元素个数,即队列的长度
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status EnQueue(SqQueue &Q, QElemType e)
{
//插入元素 e 为 Q 的新的队尾元素
if ((Q.rear+)%MAXQSIZE == Q.front)
{
return ERROR;//队列满
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear+)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &Q, QElemType &e)
{
//若队列不空,则删除 Q 的队列头元素,用 e 返回其值,
//并返回 OK,否则返回 ERROR
if (Q.front == Q.rear)
{
return ERROR;
}
e = Q.base[Q.front];
Q.front = (Q.front+)%MAXQSIZE;
return OK;
}
Status QueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear)
{
return TRUE;
}
else
{
return FALSE;
}
}
void PrintQueue(SqQueue Q)
{
int cnt = Q.front;
if (Q.front == Q.rear)
{
printf("void\n");
return;
}
while ((cnt+)%MAXQSIZE != Q.rear)
{
//printf("%d\t%d\n",Q.base[cnt++], cnt);输出好奇怪
printf("%d\t", Q.base[cnt]);
cnt++;
}
printf("%d\n", Q.base[cnt]);
}
3_4_part2.h
存储结构用到的头文件
//filename:7_2_part2.h
//date:2016-6-20
//author:zhaoyu
//note:
//----图的邻接表存储表示----
#include "head.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAX_VERTEX_NUM 20
#define VertexType int
#define InfoType char
#define Graph ALGraph
typedef struct ArcNode{
int adjvex;//该弧所指向的顶点位置
struct ArcNode *nextarc;//指向下一条弧的指针
InfoType *info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
int kind;
}ALGraph; void AddNode(ALGraph &G, int v, int w)
{
G.vertices[v].data = v;
if (NULL == G.vertices[v].firstarc)
{
G.vertices[v].firstarc = (ArcNode *)malloc(sizeof(ArcNode));
G.vertices[v].firstarc->nextarc = NULL;
G.vertices[v].firstarc->adjvex = w;
G.vertices[v].firstarc->info = NULL;
return;
}
ArcNode *temp = G.vertices[v].firstarc;
while (temp->nextarc)
{
temp = temp->nextarc;
}
ArcNode *move = (ArcNode *)malloc(sizeof(ArcNode));
move->nextarc = NULL;
move->adjvex = w;
move->info = NULL;
temp->nextarc = move;
}
void CreateALGraph(ALGraph &G)
{
for (int i = ; i < MAX_VERTEX_NUM; i++)
{
G.vertices[i].firstarc = NULL;
}
printf("input vexnum and arcnum(1~MAX):\n");
scanf("%d%d", &G.vexnum, &G.arcnum);
int v, w;
for (int i = ; i < G.arcnum; i++)
{
scanf("%d%d", &v, &w);
AddNode(G, v, w);
AddNode(G, w, v);
}
}
Status Visit(int v)
{
printf("%d->", v);
}
int FirstAdjVex(ALGraph G, int v)
{
if (NULL != G.vertices[v].firstarc)
{
return G.vertices[v].firstarc->adjvex;
}
else
{
return -;
}
}
int NextAdjVex(Graph G, int v, int w)
{
if (NULL != G.vertices[v].firstarc)
{
ArcNode *temp = G.vertices[v].firstarc;
while (temp != NULL)
{
if (temp->adjvex == w)
{
if (NULL != temp->nextarc)
{
return temp->nextarc->adjvex;
}
else
{
return -;
}
}
temp = temp->nextarc;
}
return -;
}
else
{
return -;
}
}
7_2_part2.h
其他
//filename:7_3.h
//date:2016-6-25
//author:
//note:仅以邻接表为例
#include "7_2_part2.h"
#include "3_4_part2.h"
#define Boolean int
#define MAX MAX_VERTEX_NUM
Boolean visited[MAX];//访问标志数组
Status (* VisitFunc)(int v);//函数变量
/**
algorithm 7.5
*/
void DFS(Graph G, int v)
{
visited[v] = TRUE;
VisitFunc(v);//访问第 v 个结点
for (int w = FirstAdjVex(G, v); w >= ; w = NextAdjVex(G, v, w))
{
if (!visited[w])
{
DFS(G, w);//对 v 的尚未访问的邻接顶点,递归调用 DFS
}
}
}
/**
algorithm 7.4
*/
void DFSTraverse(Graph G, Status (* Visit)(int v))
{//对图 G 做深度游优先遍历
VisitFunc = Visit;//使用全局变量VisitFunc,使DFS不必设函数指针参数
for (int v = ; v < G.vexnum; ++v)
{
visited[v] = FALSE;
}
for (int v = ; v < G.vexnum; ++v)
{
if (!visited[v])
{
DFS(G, v);
}
}
printf("\b\b \n");
} void BFSTraverse(Graph G, Status (* Visit)(int v))
{//按广度优先非递归遍历图 G,使用辅助队列 Q 和访问标志数组 visited
for (int v = ; v < G.vexnum; ++v)
{
visited[v] = FALSE;
}
SqQueue Q;
InitQueue(Q);//置空的辅助队列 Q
for (int v = ; v < G.vexnum; ++v)
{
if (!visited[v])//v 尚未访问
{
visited[v] = TRUE;
Visit(v);
EnQueue(Q, v);// v 入队列
while (!QueueEmpty(Q))
{
int u = -;
DeQueue(Q, u);//队头元素出队并置为 u
for (int w = FirstAdjVex(G, u); w >= ; w = NextAdjVex(G, u, w))
{//w 为 u 尚未访问的邻居节点
if (!visited[w])
{
visited[w] = TRUE;
Visit(w);
EnQueue(Q, w);
}
}
}
}
}
printf("\b\b \n");
}
7_3.h
三.CPP文件
#include "7_3.h"
int main(int argc, char const *argv[])
{
ALGraph G;
CreateALGraph(G);
printf("DFS Traverse\t");
DFSTraverse(G, Visit);
printf("BFS Traverse\t");
BFSTraverse(G, Visit);
return ;
}
7_3.cpp
四.测试
以书本上的图为例