2022年数据结构课程设计报告 2.pdf

《2022年数据结构课程设计报告 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计报告 2.pdf（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 / 32 算法与数据结构课程设计报告系 院）：计算机科学学院专业班级：教育技术学1001 班姓名：宋佳学 号： 201803901 指导教师： 詹泽梅设计时间： 2018.6.16 - 2018.6.24设计地点： 4 号楼 2 号机房精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 32 页2 / 32 算法与数据结构课程设计任务书班级：教育技术 11001 课程设计题目：图的基本操作及应用数据结构课程设计是在学完数据结构课程之后的实践教案环节。本实践教案是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择

2、合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。一设计目的1提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。2提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二设计任务设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：1无向图的基本操作及应用 创建无向图的邻接矩阵创建无向图的邻接表无向图的深度优先遍

3、历无向图的广度优先遍历2有向图的基本操作及应用创建有向图的邻接矩阵创建有向图的邻接表拓扑排序3无向网的基本操作及应用 创建无向网的邻接矩阵 创建无向网的邻接表 求最小生成树4有向网的基本操作及应用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 32 页3 / 32 创建有向网的邻接矩阵创建有向网的邻接表关键路径单源最短路径三设计指导第一步：根据设计任务，设计DOS菜单。第二步：设计菜单 c语言）#include void ShowMainMenu( printf(n 。printf(*图的基本操作及应用 *n。printf(* 1 无向

4、图的基本操作及应用 *n。printf(* 2 有向图的基本操作及应用 *n。printf(* 3 无向网的基本操作及应用 *n。printf(* 4 有向网的基本操作及应用 *n。printf(* 5 退出n。printf(*n。 void UDG( int n。do printf(n 。printf(*无向图的基本操作及应用 *n。printf(* 1 创建无向图的邻接矩阵 *n 。printf(* 2 创建无向图的邻接表 *n。printf(* 3 无向图的深度优先遍历 *n。printf(* 4 无向图的广度优先遍历 *n。printf(* 5 退出n。printf(*n。printf

5、( 请选择： 。scanf(%d,&n 。switch(n case 1: printf(-wait-。break。case 2: printf(-wait-。break。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 32 页4 / 32 case 3: printf(-wait-。break。case 4: printf(-wait-。break。case 5:break 。default: printf(ERROR! 。 while(n!=5 。 void DG( int n。do printf(n 。printf(*有向图的基本

6、操作及应用 *n。printf(* 1 创建有向图的邻接矩阵 *n。printf(* 2 创建有向图的邻接表 *n。printf(* 3 拓扑排序 *n。printf(* 4 退出 *n。printf(*n。printf( 请选择： 。scanf(%d,&n 。switch(n case 1: printf(-wait- 。break。case 2: printf(-wait- 。break。case 3: printf(-wait- 。break。case 4:break 。default: printf(ERROR! 。 while(n!=4 。 void UDN( int n。do pr

7、intf(n 。printf(*无向网的基本操作及 *n 。printf(* 1 创建无向网的邻接矩阵 *n。printf(* 2 创建无向网的邻接表 *n。printf(* 3 Prim 算法求最小生成树 *n。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 32 页5 / 32 printf(* 4 kraskal 算法求最小生成树 *n。printf(* 5 退出n。printf(*n。printf( 请选择： 。scanf(%d,&n 。switch(n case 1: printf(-wait-。break。case 2: p

8、rintf(- -wait- 。break。case 3: printf(-wait-。break。case 4: printf(-wait-。break。case 5:break 。default: printf(ERROR! 。 while(n!=5 。 void DN( int n。do printf(n 。printf(*有向网的基本操作 *n 。printf(* 1 创建有向网的邻接矩阵 *n。printf(* 2 创建有向网的邻接表 *n。printf(* 3 关键路径 *n。printf(* 4 单源顶点最短路径问题 *n。printf(* 5 退出n。printf(*n。pri

9、ntf( 请选择： 。scanf(%d,&n 。switch(n case 1: printf(-wait-。break。case 2: printf(-wait-。break。case 3: printf(-wait-。break。case 4: printf(-wait-。break。case 5:break 。default: 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 32 页6 / 32 printf(ERROR! 。 while(n!=5 。 void main( int n。do ShowMainMenu(。print

10、f( 请选择： 。scanf(%d,&n 。switch(n case 1:UDG(。break。case 2:DG(。break。case 3:UDN(。break。case 4:DN(。break。case 5:break 。default:printf(ERROR! 。break。 while(n!=5 。 第三步：添加功能函数。在主程序的合适位置添加相应的函数实现各功能所在位置）。四成绩评定实习报告 、程序实现 (50%、实习报告 (30% 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 32 页7 / 32 一、 设计方案由课

11、程设计任务书，按照要求，需要设计有向图3、有向网、无向图、无向网四种图，邻接矩阵、邻接表两种数据存储结构，共十六种基本操作及应用，三层以上的显示菜单。图的操作中又包含有有关线性表、栈和队列的基本操作。由于显示菜单已给出，剩下的只是把函数写入其中，而线性表、栈和队列的基本操作并不复杂，很容易实现，我们只有完成图的相关操作即可。图的操作都是以两种存储结构为基础的，邻接矩阵存储结构和邻接表存储结构，如四种图 有向图，有向网，无向图，无向网）的创建，其他的操作都是在四种图创建后才开始进行的。所以，首先必须理解两种存储结构的定义。图的邻接矩阵存储结构即图的数组表示法。用两个数组分别存储数据元素顶点）的信

12、息和数据元素之间的关系边或弧）的信息。用邻接矩阵存储结构的图具有以下几点特征：一）：顶点数： vexnum，边弧）数： arcnum，图的种类： kind； ；三）：顶点向量 顶点名）： vexs；其优点是以二维数组表示有n 个顶点的图时，需存放n 顶点的信息和 n*n 个弧的信息存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求各个顶点的度。缺点其时间复杂度是On*n）,例如，构造一个具有 n 个顶点和 e条边的无向网的时间复杂度为On*n+e*n）。图的邻接表存储结构是图的一种链式存储结构。对图中的每个顶点建立一个单链表，每个结点有三个域组成，邻接点域adjvex弧尾

13、在邻接表链表中的位序），链域 nextarc。还要建立一个邻接表链表，用以存放顶点名data和后继指针 firstarc,表头结点以顺序结构的形式存储，便于随机访问任一顶点的单链表。邻接表存储结构的优点在于其时间复杂度小。除此之外，还有十字链表存储结构和多重链表存储结构。由于，没有用到他们，故不再详细描述。树的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。从图中的某个顶点出发，访问此顶点，然后依次从该顶点出发深度优先搜索遍历图，直至图中所有与该顶点有关的路径都被访问到；此时图中若还有顶点未被访问到，则另选图中的一个未被访问的顶点作为起始点，重述上述过程，直至所有顶点都被访问到。广度

14、优先搜索遍历类似于树的按层次遍历的过程。以某个顶点为起始顶点，由近至远，依次访问和该顶点有路径相通的且路径长度为1， 2，3，的顶点。当图中所有顶点都被访问到后，就完成了图的广度优先搜索遍历。求无向网的最小生成树问题有两种算法：Prima算法和 Kruskal 算法。 Prima算法是从网中的某个顶点出发，选择与该顶点有路径的所有顶点中路径最小的一条路径，从该最小路径的另一顶点出发，重复上述过程，直至图中所有顶点都被访问完成。 Kruskal 算法是从网中找出所有路径最小的一条路径，记下已访问该路径的两个顶点，再次从图中找出剩下路径中的最小路径，重复上述过程，直至所有顶点都被访问完成，按访问的

15、顺序依次输出各顶点，即构造了一棵最小生成树。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 32 页8 / 32 由某个集合上的一个偏序得到该集合的一个全序的操作就叫做拓扑排序。拓扑排序主要有两个方面的操作：1）在有向图中选择一个没有前驱的顶点并输出；和最迟开始时间e(s，若某条弧满足条件 e(s=l(s，则为关键活动。从某个源点到其余各顶点的最短路径问题：若从v 到 vi 有弧，则 Di 为弧上的权值，否则 Di 为无穷大。显然，长度为Dj=MinDi|vi属于 V 的路径就是从 v 出发的长度最短的一条路径。二、 实现及测试过程按照

16、设计任务的要求，我先完成了存储结点、边、邻接矩阵、邻接表、队列、栈等储存结构体的设计。其次是栈和队列的基本操作和实现，四种图的创建和显示，然后是基于两种存储结构的各种算法的现，最后是三层显示输出菜单。测试样图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 32 页9 / 32 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 32 页10 / 32 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 32 页11 / 32

17、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 32 页12 / 32 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 32 页13 / 32 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 32 页14 / 32 三、实现代码#include #include #include #define ERROR 0 #define OK 1 #define INFINITY INT_MAX #define MAX_VER

18、TEX_NUM 21 #define STACK_INIT_SIZE 100 #define STACKINCREAMENT 10 typedef enumDG,DN,UDG,UDNGraphKind 。typedef struct ArcCell int adj。 /infotype *info 。ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM。typedef struct char vexsMAX_VERTEX_NUM 。 AdjMatrix arcs。 int vexnum,arcnum 。 GraphKind kind。MGraph。 /邻

19、接矩阵typedef struct ArcNode int adjvex。 int quan 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 32 页15 / 32 struct ArcNode *nextarc。 ArcNode,*AList 。typedef struct VNode char data 。 AList firstarc。VNode,AdjListMAX_VERTEX_NUM。typedef struct AdjList vertices。 int vexnum,arcnum 。 GraphKind kind。A

20、LGraph 。 /邻接表typedef struct QNode char data 。struct QNode *next。QNode,*QueuePre。typedef struct QueuePre front 。QueuePre rear 。LinkQueue。 / 队列typedef struct int *base。int *top。int stacksize 。SqStack。 /栈typedef struct char adjvex 。int lowcost。closedgesMAX_VERTEX_NUM 。 / 求最小生成树中的辅助数组int option。int visi

21、tedMAX_VERTEX_NUM。 /顶点访问标记数组int indegreeMAX_VERTEX_NUM 。 /顶点入度记录数组int veMAX_VERTEX_NUM。 /顶点权值记录数组int SetGraphKind(MGraph &G,int option switch(option case 1: G .kind=DG。break。 case 2: G .kind=DN 。break。 case 3: G .kind=UDG 。break。 case 4: G .kind=UDN 。break。 default: return ERROR 。 return OK。 / 邻接矩阵类

22、型设置int SetGraphKind(ALGraph &G,int option 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 32 页16 / 32 switch(option case 1: G .kind=DG。break。 case 2: G .kind=DN 。break。 case 3: G .kind=UDG 。break。 case 4: G .kind=UDN 。break。 default: return ERROR 。 return OK。 / 邻接表类型设置int LocateVex(MGraph G,ch

23、ar v int m。 for(m=1。m if(G.vexsm=v return m。 return ERROR。 / 邻接矩阵顶点定位int LocateVex(ALGraph G,char v int m。 for(m=1。m if(G.verticesm.data=v return m。 printf(您输入的顶点不存在 。 return ERROR。 / 邻接表顶点定位int InitQueue(LinkQueue &Q Q.front=Q.rear=(QueuePremalloc(sizeof(QNode 。if(!Q.front return ERROR 。Q.front-nex

24、t=NULL 。return OK。 / 队列创建int EnQueue(LinkQueue &Q,int e QueuePre p 。p=(QueuePremalloc(sizeof(QNode 。if(!p return OK 。p-data=e。p-next=NULL 。Q.rear-next=p。Q.rear=p。return OK。 / 元素入队列int DeQueue(LinkQueue &Q,int &e QueuePre p 。if(Q.front=Q.rear return ERROR。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -

25、第 16 页，共 32 页17 / 32 p=Q.front-next。e=p-data。Q.front-next=p-next。if(Q.rear=p Q.rear=Q.front。free(p。return OK。 / 元素出队列int QueueEmpty(LinkQueue Q if(Q.front=Q.rear return OK。return ERROR。 / 判断队列是否为空int InitStack(SqStack &S S.base=(int*malloc(STACK_INIT_SIZE*sizeof(int 。if(!S.base return ERROR。S.top=S.

26、base 。S.stacksize=STACK_INIT_SIZE。return OK。 /栈创建int Push(SqStack &S,int e if(S.top-S.base=S.stacksize S.base=(int*realloc(S.base,(S.stacksize+STACKINCREAMENT*sizeof(int。if(!S.base return ERROR。S.top=S.base+S.stacksize 。S.stacksize+=STACKINCREAMENT 。 *S.top+=e。return OK。 / 元素入栈int Pop(SqStack &S,int

27、 &e if(S.top=S.base return ERROR 。e=*-S.top。return OK。 /元素出栈int StackEmpty(SqStack S if(S.top=S.base return OK 。return ERROR。 /判断栈是否为空精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 32 页18 / 32 int CreatGraph(MGraph &G int i,j,k,w 。char x,y。 if(!SetGraphKind(G,option printf( 对 图 类 型 的 设 置 失 败

28、。 return ERROR。 printf(邻接矩阵：请输入定点的个数、弧的个数：。 scanf(%d %d,&G.vexnum,&G.arcnum。 if(G.vexnum20 printf(您输入的顶点个数超过最大值。 return ERROR 。 printf(请输入 %d 个顶点 n,G.vexnum。 for(i=1。i fflush(stdin 。 scanf(%c,&G.vexsi 。 if(G.kind=DG|G.kind=UDG for(i=1。i for(j=1。j G .arcsij.adj=0 。 if(G.kind=DG printf(请输入有向图的两个相邻的顶点如

29、果互相邻接则也要输入）： n。 for(k=1。kfflush(stdin 。 scanf(%c%c,&x,&y 。 i=LocateVex(G ,x。j=LocateVex(G,y。 G .arcsij.adj=1 。 else printf(请输入无向图的两个相邻的顶点。 for(k=1。kfflush(stdin 。 scanf(%c%c,&x,&y 。 i=LocateVex(G ,x。 j=LocateVex(G,y。 G .arcsij.adj=1 。 G.arcsji.adj=G.arcsij.adj 。 else for(i=1。i for(j=1。j G .arcsij.ad

30、j=INT_MAX 。 if(G.kind=DN printf(请输入有向网的两个相邻的顶点以及相应的权值w如果互相邻接则 也要输入）： n。 for(k=1。kfflush(stdin 。 scanf(%c%c %d,&x,&y,&w 。 i=LocateVex(G ,x。 j=LocateVex(G,y。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 32 页19 / 32 G .arcsij.adj=w 。 else printf(请输入无向网的两个相邻的顶点。 for(k=1。kfflush(stdin 。 scanf(%c%

31、c %d,&x,&y,&w 。 i=LocateVex(G ,x。 j=LocateVex(G,y。 G .arcsij.adj=w 。 G.arcsji.adj=G.arcsij.adj 。 return OK。 / 创建邻接矩阵int CreatAList(ALGraph &G int i,j,m,n,keyMAX_VERTEX_NUM。 char x,y,w。AList p,q。SetGraphKind(G ,option。printf( 邻接表：请输入顶点的个数和弧的个数：。scanf(%d %d,&G.vexnum ,&G.arcnum。if(G.vexnum20 printf(您输

32、入的顶点个数超过最大值。 return ERROR 。 printf( 请输入个顶点： n。for(i=1。i fflush(stdin。scanf(%c,&G.verticesi.data。G.verticesi.firstarc=NULL 。keyi=0 。 if(G.kind=DG printf( 请输入弧 。for(j=1。j fflush(stdin。scanf(%c%c,&x,&y 。m=LocateVex(G ,x。n=LocateVex(G ,y。p=G.verticesm.firstarc。q=(AListmalloc(sizeof(ArcNode 。if(!q return

33、 ERROR。q-nextarc=NULL 。q-adjvex=n。while(keym&p-nextarc 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 32 页20 / 32 p=p-nextarc。keym+。 if(!keymG .verticesm.firstarc=q。keym+。 else p-nextarc=q 。 if(G.kind=UDG printf( 请输入弧 。for(j=1。j fflush(stdin。scanf(%c%c,&x,&y 。m=LocateVex(G ,x。n=LocateVex(G ,y

34、。p=G.verticesm.firstarc。q=(AListmalloc(sizeof(ArcNode 。if(!q return ERROR。q-nextarc=NULL 。q-adjvex=n。while(keym&p-nextarc p=p-nextarc。keym+。 if(!keymG .verticesm.firstarc=q。keym+。 else p-nextarc=q 。 if(G.kind=DN printf( 请输入依次输入弧以及这条弧的权值。 for(j=1。j fflush(stdin。scanf(%c%c %d,&x,&y,&w 。m=LocateVex(G ,

35、x。n=LocateVex(G ,y。p=G.verticesm.firstarc。q=(AListmalloc(sizeof(ArcNode 。if(!q return ERROR。q-nextarc=NULL 。q-quan=w。q-adjvex=n。while(keym&p-nextarc p=p-nextarc。keym+。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 32 页21 / 32 if(!keymG .verticesm.firstarc=q。keym+。 else p-nextarc=q 。 if(G.kind

36、=UDN printf( 请输入依次输入弧以及这条弧的权值。 for(j=1。j fflush(stdin。scanf(%c%c %d,&x,&y,&w 。m=LocateVex(G ,x。n=LocateVex(G ,y。p=G.verticesm.firstarc。q=(AListmalloc(sizeof(ArcNode 。if(!q return ERROR。q-nextarc=NULL 。q-quan=w。q-adjvex=n。while(keym&p-nextarc p=p-nextarc。keym+。 if(!keymG .verticesm.firstarc=q。keym+。

37、else p-nextarc=q 。 return OK。 /创建邻接表int FirstAdjVex(ALGraph G,int v if(G.verticesv.firstarc return G .verticesv.firstarc-adjvex。return 0。 int NextAdjVex(ALGraph G,int v,int w AList s。s=G .verticesv.firstarc。while(s-adjvex!=w s=s-nextarc 。if(s-nextarc return s-nextarc-adjvex 。return 0。 精选学习资料 - - - -

38、 - - - - - 名师归纳总结 - - - - - - -第 21 页，共 32 页22 / 32 void DFS(ALGraph G,int v int w。visitedv=1 。 printf(%c ,G.verticesv。for(w=FirstAdjVex(G,v。w=1。w=NextAdjVex(G,v,w if(!visitedw DFS(G ,w。 void DFSTraverse(ALGraph G int v。visited0=1。for(v=1。v visitedv=0 。for(v=1。v if(!visitedv DFS(G ,v。 /图的深度遍历void BF

39、STraverse(ALGraph G int v,w,u。LinkQueue Q。for(v=1。v visitedv=0 。visited0=1。InitQueue(Q。for(v=1。v if(!visitedv visitedv=1。 printf(%c ,G.verticesv。 EnQueue(Q,v。 while(!QueueEmpty(Q DeQueue(Q,u 。 for(w=FirstAdjVex(G,u。w=1。w=NextAdjVex(G,u,w if(!visitedw visitedw=1 。 printf(%c ,G.verticesw。EnQueue(Q,w。

40、else break 。 /图的广度遍历void FindInDegree(ALGraph G,int in int i,j,k 。AList p。for(k=1。k ink=0 。for(i=1。i p=G.verticesi.firstarc。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 32 页23 / 32 while(p j=p-adjvex。inj+ 。p=p-nextarc。 /计算各顶点入度int TopologicalSort(ALGraph G int i,k,count。AList p 。SqStack S 。

41、FindInDegree(G ,indegree。InitStack(S。for(i=1。i if(!indegreei Push(S,i。count=0。if(StackEmpty(S printf( 此有向图不符合条件！ 。while(!StackEmpty(S Pop(S,i。printf(%d ,i 。+count。for(p=G.verticesi.firstarc 。p。p=p-nextarc k=p-adjvex。if(!(-indegreek Push(S,k。 if(count return ERROR。else return OK。 /拓扑排序int Minimum(MGr

42、aph G,closedges m int i,j,min=INFINITY 。for(i=1。i if(mi.lowcost if(mi.lowcost min=mi.lowcost 。j=i。 return j。 void MinSpanTree_PRIM(MGraph G,char u int i,j,k 。closedges closedge 。k=LocateVex(G ,u。for(j=1。j 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 32 页24 / 32 if(j!=k closedgej.adjvex=u。cl

43、osedgej.lowcost=G.arcskj.adj 。 closedgek.lowcost=0。for(i=2。i k=Minimum(G,closedge 。printf(%c%c ,closedgek.adjvex,G.vexsk。closedgek.lowcost=0。for(j=1。j if(G.arcskj.adj closedgej.adjvex=G.vexsk。closedgej.lowcost=G.arcskj.adj 。 /求最小生成树int TopologicalOrder(ALGraph G,SqStack &T int i,j,k,count。 SqStack S

44、 。 AList p。FindInDegree(G ,indegree。InitStack(S。for(i=1。i if(!indegreei Push(S,i。InitStack(T。count=1。for(i=1。i vei=0 。while(!StackEmpty(S Pop(S,j。Push(T,j。+count。for(p=G.verticesj.firstarc 。p。p=p-nextarc k=p-adjvex。if(-indegreek=0 Push(S,k。if(vej+p-quanvek vek=vej+p-quan 。 if(count return ERROR。else

45、 return OK。 int CriticalPath(ALGraph G int i,j,k,ee,el,dut,v1MAX_VERTEX_NUM。 SqStack T。 AList p 。 char tag。if(!TopologicalOrder(G,T return ERROR。for(i=1。i v1i=veG.vexnum。 while(!StackEmpty(T 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 32 页25 / 32 for(Pop(T,j,p=G.verticesj.firstarc。p。p=p-ne

46、xtarc k=p-adjvex。dut=p-quan。if(v1k-dut v1j=v1k-dut。 for(j=1。j for(p=G.verticesj.firstarc 。p。p=p-nextarc k=p-adjvex。dut=p-quan。ee=vej。el=v1k-dut。tag=(ee=el?*: 。printf(%d %d %d %d %d %cn,j,k,dut,ee,el,tag。 return OK。 /求关键路径void DG_(MGraph G1,ALGraph G2 int i,j,k,m,key 。AList s。for(k=0。 key=0。printf(*n

47、。printf( 请选择对有向图进行的操作：n1 创建邻接矩阵 n2 创建邻接表n3拓扑结构 n4 退出n。 printf(*n。printf( 请选择： 。 scanf(%d,&m。switch(m case 1: CreatGraph(G1 。printf( 有向图的邻接矩阵： n。 for(i=1。i for(j=1。j printf( %d,G1.arcsij.adj 。 printf(n。break。case 2: CreatAList(G2。printf( 有向图的邻接表： n。 for(i=1。i printf(%c:,G2.verticesi。 s=G2.verticesi.f

48、irstarc 。 while(s j=s-adjvex 。fflush(stdin。 printf(。 printf(%c ,G2.verticesj。 s=s-nextarc 。 printf(n。 break。case 3:printf( 有向图的拓扑排序：n 。TopologicalSort(G2。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 32 页26 / 32 break。 case 4:key=1 。break。printf(n 。if(key break。 printf(nn 。 /DG void DN_(MGra

49、ph G1,ALGraph G2 int i,j,k,m,key 。AList s。for(k=0。 key=0。printf(*n。printf( 请选择对有向网进行的操作：n1 创建邻接矩阵 n2 创建邻接表n3关键路径 n4 退出n。 printf(*n。printf( 请选择： 。 scanf(%d,&m。switch(m case 1: CreatGraph(G1 。printf( 有 向 网 的 邻 接 矩 阵 ：n。 for(i=1 。i for(j=1 。j if(G1.arcsij.adj=INT_MAXprintf( #。 else printf( %d,G1.arcsij

50、.adj。 printf(n。 break。 case 2: CreatAList(G2。 printf( 有向网的邻接表： n。 for(i=1 。i printf(%c:,G2.verticesi。 s=G2.verticesi.firstarc 。 while(s j=s-adjvex 。fflush(stdin。 printf(。 printf(%c ,G2.verticesj。 printf( %d ,s-quan 。 s=s-nextarc 。 printf(n。 break。 case 3: printf(有向网关键路径： n。CriticalPath(G2。break。case