数据结构 课程设计 说明书
目 录
一、 题目简介
二、 功能说明
三、 程序框图
四、 程序清单
五、 运行结果
六、 设计体会
七、 参考文献
八、 教师评语
一 、题目简介
该程序综合了图的大部分算法，包含从图的四种存储方式，到每个存储方
式的相关算法。有向图的算法中包括：广度优先算法 、深度优先搜索、普利姆
算法、克鲁斯卡尔算法以及有向图到无向图的转化；无向图的算法中包括：弗
洛伊德算法、拓扑排序算法、迪杰斯特拉；在四类存储方式各自算法中，都包
括了：统计各个节点的度，打印显示图。
二、功能说明：
1、选择存储方式：此功能可创建相应存储方式的图。
1.无向邻接矩阵
2.有向邻接矩阵
3.无向邻接表
4.有向邻接表
2、.无向邻接矩阵的相关算法：此功能可进行无向邻接矩阵的相关算法操作。
1.广度优先算法
2.深度优先搜索
3.普利姆算法
4.克鲁斯卡尔算法
5.统计各个节点的度
6.打印显示图
7.返回上一层
3、有向邻接矩阵的相关算法：此功能可进行无向邻接矩阵的相关算法操作。
1.弗洛伊德算法
2.打印显示图
3.统计各个节点的度
4.转为无向矩阵
5.返回上一层
4、无向邻接表的相关算法：此功能可进行无向邻接矩阵的相关算法操作。
1.深度优先算法
2.广度优先搜索
3.普利姆
4.克鲁斯卡尔
5.统计节点的度
6.打印输出
7.返回上一层
5、有向邻接表的相关算法：此功能可进行无向邻接矩阵的相关算法操作。
1.拓扑排序算法
2.迪杰斯特拉算法
3.统计各个节点的度
4.打印输出
5.返回上一层
4、退出程序
三、程序框图
四、程序清单
（1）stack.h 文件
typedef int Status;
typedef int ElemType;
typedef struct SNode{
ElemType data;
struct SNode *next;
}SNode, *Stack;
struct _node
{
int adjvex ;
int v_num;
struct _node *next;
};
typedef struct _node node, *pnode;
Stack CreatStack(Stack S);
Status push(Stack S, ElemType e);
ElemType pop(Stack S);
Status IsEmpty(Stack S);
（2）queue.h 文件
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
} LinkQueue;
LinkQueue InitQueue() ;
Status EnQueue(LinkQueue *Q, QElemType e) ;
Status QueueEmpty(LinkQueue *Q);
QElemType DeQueue(LinkQueue *Q);
（3）Graph_B.h 文件
#define MAX_NUM 20
typedef struct Acnode{
int adjvex;//存放顶点在数组中的位置
int value;//权值，这里定义为整型
struct Acnode *next;
char *info;//存放弧的信息
}Acnode;//弧的定义
typedef struct _edata
{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
typedef struct {
int data;
Acnode *firstarc;
}VertexNode;//顶点定义
typedef struct{
VertexNode Vertex[MAX_NUM];
int Vexnum,Arcnum;//当前顶点数目、弧数目
}ALGraph;//图的定义
typedef struct Minimum{ //此结构存放当前过程中 V 中各节点到 U 中各节点的最小权值信息
int data; //保存 U 中与 V 中该结点相连接的结点值，使 V 中该结点到 U 中各节点间权值
最小
int lowcost; //保存两结点间最小的权值(代价)
int flag;
}Minimum,closedge[20];
void dijkstra(ALGraph G) ;
void kruskal(ALGraph G) ;
void prim(ALGraph G) ;
ALGraph YCreatGraph_DN_LinJieBiao() ;
ALGraph NCreatGraph_DN_LinJieBiao() ;
void TopologicalSort(ALGraph *G);
void CountVerNum_DN_LinJieBiao(ALGraph *G);
void DFSTraverse(ALGraph G) ;
void BFSTraverse(ALGraph &G) ;
int FirstAdjvex(ALGraph G, int v) ;
int NextAdjvex(ALGraph G, int v, int w) ;
void CriticalPath(ALGraph G) ;
void print_lgraph(ALGraph G);
（4）Graph_JZ.h 文件
#define DataType char
#define MAX_NUM 20
struct _graph
{
DataType vexs[MAX_NUM];
int arcs[MAX_NUM][MAX_NUM];
int vexnum, arcnum;
};
typedef struct _graph graph, *pgraph;
typedef struct gEdge { //定义一个边集结构，用来存储图的所有边信息
int begin;
int end;
int weight;
}gEdge;
void print_graph(graph G);
graph Ycreate_graph() ;
graph Ncreate_graph() ;
int locate(graph g, DataType data);
int firstvex_graph(graph g, int k) ;
