数 据 结 构 实 验 报 告 目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int QElemType; typedef struct QNode{ //队的操作 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; void InitQueue(LinkQueue &Q){ //初始化队列 Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 Q.front ->next =NULL; } int EnQueue(LinkQueue &Q,QElemType e) //插入元素 e 为 Q 的新的队尾元素 { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear =p; return OK; } int DeQueue(LinkQueue &Q,QElemType &e) //删除Q 的队头元素，用e 返回其值 { if(Q.front ==Q.rear ) return ERROR; QueuePtr p; p=Q.front ->next; e=p->data; Q.front->next=p->next ; if(Q.rear==p) Q.rear =Q.front ; free(p); return OK; } 主程序： #include #include #include"duilie.h" #define TRUE 1 #define FALSE 0 #define Status int #define MAX_VERTEX_NUM 8 /*顶点最大个数*/ #define VertexType char /*顶点元素类型*/ enum BOOlean {False,True}; BOOlean visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组 typedef struct ArcNode {int adjvex; struct ArcNode *nextarc; int weight; /*边的权*/ }ArcNode; /*表结点*/ typedef struct VNode { int degr...
