算法与数据结构课程设计

算法与数据结构课程设计目录一、设计方案*****************************************第2页二、实现过程*****************************************第4页三、测试*****************************************第4页四、使用说明*************************************第11页五、难点与收获**************************************第12页六、实现代码***************************************第13页七、可改进的地方**********************************第37页一、设计方案根据课程设计任务书，按照要求，需要设计有向图、无向图、有向网、无向网四种图，邻接矩阵、邻接表两种数据存储结构，共十四种基本操作及应用，三层以上的显示菜单。

图有关线性表、栈和队列的基本操作。

由于显示菜的操作中又包含单已给出，剩下的只是把函数写入其中1、以两种存储结构为基础主要有邻接矩阵存储结构和邻接表存储结构。

邻接矩阵:(1).存储表示：定义顶点、弧、图的各类标志(2)连接矩阵类型设置：switch语句设置DG、UDG、DN、UDN(3)定点定位：将顶点v带入、查询、返回数组下标(4)创建邻接矩阵：输入顶点、弧，通过if语句实现，将其初始化邻接表：(1)存储表示：定义顶点、弧、权值类型、首结点、顶点数、弧数(2)邻接表类型设置:switch语句设置DG、UDG、DN、UDN(3)定点定位：将顶点v带入、查询、返回数组下标(4)邻接表插入结点(5)创建邻接表：通过if语句实现2.队列与栈：(1)队列的创建、入队、出队、判断是否为空(2)栈的创建、入栈、出栈、判断是否为空3图的深度优先遍历：采用邻接表结构，指定任意顶点x为初始顶点(1).访问结点v并标记结点v已访问；(2).查找结点v的第一个邻接节点;(3).若结点v的邻接节点存在，则继续执行，否则算法结束；(4).查找结点v的邻接结点的下一个邻接结点w,转到步骤3。

4.图的广度优先遍历：采用邻接表结构，指定任意顶点x为初始顶点，利用顺序循环对列以保持访问过的结点的顺序(1).首先访问初始结点v并标记结点v为已访问；(2).结点v入队列；(3).当队列非空时则继续执行，否则算法结束；(4).出队列取得队头结点u;(5).查找u的第一个邻接结点w；(6).若u的邻接结点w不存在则转到步骤3，否则循环执行下列步骤；(7).若结点w尚未被访问，则访问结点w并标记结点w为已访问5.有向图的拓扑排序：采用邻接表结构（1）调用计算顶点入度的函数，创建栈(2).在有向图中选择一个没有入度的顶点并入栈；(3).图中删除该顶点和所有以它为尾的弧。

(4)重复上述两步，直至全部顶点均已输出，就得到了一个拓扑有序序列。

6.无向网的最小生成树有两种算法：Prima算法和Kruskal算法,此次采用Prima算法(1).从网中的某个顶点出发，选择与该顶点有路径的所有顶点中权值最小的一条(2)从最小的这条的另一顶点出发，重复上述过程，直至图中所有顶点都被访问7.关键路径：(1) 输入e条弧，建立AOE网的存储结构；(2) 从源点v0出发,令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间。

如果得到拓扑有序序列中的顶点个数小于网中的顶点数，则说明网中存在环，不能求关键路径，算法终止；否则执行第三步。

(3) 从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]；(4) 根据各顶点的和值，求每条弧的最早开始时间e(s)和最迟开始时间e(s)，某条弧满足条件e(s)=l(s)，则为关键活动。

8.最短路径：利用Dijkstra算法(1)若从v到vi有弧，则D[i]为弧上的权值，否则D[i]为无穷大。

(2)长度为D[j]=Min{D[i]|vi属于V}的路径就是从v出发的长度最短的一条路径。

二、实现过程Main():主函数模块。

在主函数模块中调用以下函数：1、有向图void DG_(MGraph G1,ALGraph G2)(1)CreatGraph(G1);(2)CreatAList(G2);(3)TopologicalSort(G2);2、有向网DN_(MGraph G1,ALGraph G2)(1)CreatGraph(G1);(2)CreatAList(G2);(3)CriticalPath(G2);(4)Dijkstra(&G1,path,dist,v,G1.vexnum);3、无向图UDG_(MGraph G1,ALGraph G2)(1)CreatGraph(G1);(2)CreatAList(G2);(3)DFSTraverse(G2);(4)BFSTraverse(G2);4、无向网UDN_(MGraph G1,ALGraph G2)(1)CreatGraph(G1);(2)CreatAList(G2);(3)MinSpanTree_PRIM(G1,u);三、测试按照设计任务的要求，我先完成了存储结点、边、邻接矩阵、邻接表、队列、栈等存储结构体的设计，其次是栈和队列的基本操作和实现，四种图的创建和显示，基于两种存储结构的各种算法的实现测试图样：有向图45无向图67有向网89无向网10四、使用说明根据运行出的内容提示操作即可输入顶点数，边数，弧数，权值可以是正整数，也能是字母，但不能是标点符号。

11五、难点与收获此次课程设计虽然为已经学过的内容，但设计起来仍然有很大难度，曾经学过的也只是明白作法，对算法却很不明白，虽然教科书上有部分代码，但做起来会很困难，通过从网上搜索资料和向老师同学请教才能编写出代码，初次编写出的有很多错误，需要自己不断调试，由于在初学时基础并没有打结实，有很多名词也没有记住。

遇到的最大的困难还是不能将算法更好的理解，进而不可以跟好的运用，如不能把邻接表存储结构定义好，这就意味着无法创建以邻接表存储结构为基础的四种图，就无法实现拓扑排序和关键路径的算法。

为此我只好自己定义，自己编写代码，书上的代码只剩下参考的作用，一步步慢慢调试。

在单链表中，其结点只有两个域，指针域*next 和数据域data，而在邻接表中其结点有三个域，指针域*next，顶点位置域adjvex和相关信息域*info。

顶点位置域可以表示两个顶点之间的连接关系或相邻关系，相关信息域可以表示弧或边的信息或权值，我一直无法理解的无法描述清楚的东西现在豁然开朗，L->next=0 （NULL）跟G.vertices[i].firstarc->next=0（NULL）是一样的，都是存在的，其值都为0。

尽管单链表有两个域，邻接表有三个域，但这两个域和三个域都没有分配内存空间，所以L->next->data,L->next- >next,G.vertices[i].firstarc->next->next,G.vertices[i].firstarc->next-> adjvex,G.vertices[i].firstarc->next->info都没有值，在编译器中会出现错误无法计算它们的值。

总之，难点可概括为以下几点：1、涉及知识范围广，由于数据结构学得并不好，所以很多算法只是知其所以然而不知其所以然，能够理解，但要是自己独立去实现，不去查找和参考相关资料，那几乎是不可能完成的任务；2、代码太长，没有好的设计理念和层次，完成时警告非常多，而且都是些没办法解决的问题。

因为一点点警告都会让程序出现未知错误；3、部分算法只是理解，没有掌握，如无向图的广度优先搜索、最短路径等。

在解决这些问题中，我也收获了很多。

1、调试。

调试是最考验耐心的，调试过程中会遇到很多问题，找不到出错的原因，但通过自己的不懈努力，解决了这些问题122在算法的应用上更加清楚明朗3、一些编程规则。

这也是编程重要收获的一部分。

①变量必须先声明后使用，使用前最好赋初值，多属性的变量（结点）最好在使用前初始化，避免出现问题；②尽量不要定义同名变量或函数，避免出现命名冲突；③少使用全局变量或函数以及void关键词；④编程序要有框架和执行步骤；⑤输入要有出错机制，防止程序终止执行；⑥要逐步形成良好的编程习惯4、通过这次课设，让我明白扎实掌握程序语言是编写程序的基础，要认真的学会基础六、实现代码#include <stdio.h>#include<stdlib.h>#include<limits.h>#define ERROR 0//定义字符常量error#define OK 1//定义字符常量OK#define INFINITY INT_MAX//INT_MAX是系统库中定义的无穷大常量，即2个字节所能表示的最大数#define MAX_VERTEX_NUM 21//定义图、网的最大顶点数为21#define STACK_INIT_SIZE 100//定义栈的容量#define STACKINCREAMENT 10//定义栈的每次增长量#define MAX_INT 10000 //无穷大typedef int AdjType;typedef struct{int pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径int end;}PathType;typedef char VType; //设顶点为字符类型typedef enum{DG,UDG,DN,UDN}GraphKind;//定义图、网的枚举常量/*·················邻接矩阵····················*/typedef struct ArcCell {int adj; //弧的权值13//infotype *info;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{char vexs[MAX_VERTEX_NUM];//存储顶点的数组AdjMatrix arcs;//存储邻接矩阵的二维数组int vexnum,arcnum;//顶点数和弧数GraphKind kind;//链接矩阵的类型}MGraph;/*·················邻接表····················*/typedef struct ArcNode{int adjvex;//与首结点关联的顶点int quan;//该顶点的权值struct ArcNode *nextarc;//指向下一个结点的指针}ArcNode,*AList;typedef struct VNode {char data;//链表的各顶点AList firstarc;//链表的首结点}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;//存储链接表的各顶点int vexnum,arcnum;//顶点数和弧数GraphKind kind;//链接表的类型}ALGraph;/*·················队列····················*/typedef struct QNode{char data;//队列中元素数据struct QNode *next;//指向下一元素的指针}QNode,*QueuePre;typedef struct{QueuePre front;//队首指针QueuePre rear;//队尾指针}LinkQueue;14/*·················栈····················*/typedef struct {int *base;//栈底指针int *top;//栈首指针int stacksize;//栈的大小}SqStack;/*·················求最小生成树中的辅助数组··········*/ typedef struct {char adjvex;//最小生成树的结点int lowcost;//到该结点的最小权值开销}closedges[MAX_VERTEX_NUM];int option; //图的类型标识符int visited[MAX_VERTEX_NUM]; //顶点访问标记数组int indegree[MAX_VERTEX_NUM]; //顶点入度记录数组int ve[MAX_VERTEX_NUM]; //顶点权值记录数组/*·················链接矩阵类型设置··········*/int SetGraphKind(MGraph &G,int option){switch(option){case 1: G.kind=DG;break;case 2: G.kind=UDG;break;case 3: G.kind=DN;break;case 4: G.kind=UDN;break;default: return ERROR;}return OK;}/*·················邻接表类型设置··········*/int SetGraphKind(ALGraph &G,int option){15switch(option){case 1: G.kind=DG;break;case 2: G.kind=UDG;break;case 3: G.kind=DN;break;case 4: G.kind=UDN;break;default: return ERROR;}return OK;}/*·················邻接矩阵顶点定位·················将顶点V代入，查询顶点存储数组，返回其数组下标··········*/int LocateVex(MGraph G,char v){int m;for(m=1;m<=G.vexnum;m++){if(G.vexs[m]==v) return m;}printf("您输入的顶点不存在");return ERROR;}/*·················邻接表顶点定位·················将顶点V代入，查询顶点存储数组，返回其数组下标··········*/int LocateVex(ALGraph G,char v){int m;for(m=1;m<=G.vexnum;m++){if(G.vertices[m].data==v) return m;}printf("您输入的顶点不存在");return ERROR;}16/*·················队列创建··········*/int InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePre)malloc(sizeof(QNode));//申请存储空间，队首队尾指向同一位置if(!Q.front) return ERROR;Q.front->next=NULL;return OK;}/*·················元素入队··········*/int EnQueue(LinkQueue &Q,int e){QueuePre p;p=(QueuePre)malloc(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;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;17return ERROR;}/*·················栈的创建··········*/int InitStack(SqStack &S){S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base) return ERROR;S.top=S.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 &e){if(S.top==S.base) return ERROR;e=*--S.top;return OK;}18/*·················判断栈是否为空··········*/int StackEmpty(SqStack S){if(S.top==S.base) return OK;return ERROR;}/*·················创建邻接矩阵··········*/int CreatGraph(MGraph &G){int i,j,k,w;char x,y;if(!SetGraphKind(G,option)) {printf("对图类型的设置失败");return ERROR;}//设置链接矩阵类型printf("邻接矩阵：请输入顶点的个数、弧的个数：");scanf("%d %d",&G.vexnum,&G.arcnum);if(G.vexnum>20){printf("您输入的顶点个数超过最大值");return ERROR;}//ifprintf("请输入%d个顶点\n",G.vexnum);for(i=1;i<=G.vexnum;++i) {//输入矩阵的各顶点fflush(stdin); //清除缓存，略过scanf("%c",&G.vexs[i]);}//forif(G.kind==DG||G.kind==UDG){//1.有向图和无向图的矩阵创建for(i=1;i<=G.vexnum;i++)//矩阵初始化for(j=1;j<=G.vexnum;j++)G.arcs[i][j].adj=0;if(G.kind==DG){//2.有向图printf("请输入有向图的两个相邻的顶点<x,y>（如果互相邻接则<x,y>也要输入）：\n");for(k=1;k<=G.arcnum;k++){//循环输入fflush(stdin);scanf("%c%c",&x,&y);//输入矩阵中弧关联的两顶点i=LocateVex(G,x);j=LocateVex(G,y);//将两顶点转换成顶点存储数组的下标G.arcs[i][j].adj=1;}//for}//2.if19else{//2.无向图printf("请输入无向图的两个相邻的顶点（x,y）：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c",&x,&y);i=LocateVex(G,x); j=LocateVex(G,y);G.arcs[i][j].adj=1; G.arcs[j][i].adj=G.arcs[i][j].adj;//反向关联两顶点}//for}//2.else}//1.ifelse{//1.有向网和无向网for(i=1;i<=G.vexnum;i++)for(j=1;j<=G.vexnum;j++)G.arcs[i][j].adj=INT_MAX;//矩阵初始化if(G.kind==DN){ //3.有向网printf("请输入有向网的两个相邻的顶点<x,y>以及相应的权值w（如果互相邻接则<y,x>也要输入）：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);i=LocateVex(G,x); j=LocateVex(G,y);G.arcs[i][j].adj=w;}//for}//3.ifelse{//3printf("请输入无向网的两个相邻的顶点（x,y）以及相应的权值w：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);i=LocateVex(G,x); j=LocateVex(G,y);G.arcs[i][j].adj=w; G.arcs[j][i].adj=G.arcs[i][j].adj;//逆向关联}//for}//3.else}return OK;}20/*··············在邻接表中插入结点·············*/int setList(int x,int y,ALGraph &G,int key[]){int i,j,m,n; AList p,q;m=LocateVex(G,x);//获取结点x对应的数组下标n=LocateVex(G,y);p=G.vertices[m].firstarc;//获取第m个链表的首结点q=(AList)malloc(sizeof(ArcNode));//申请结点空间if(!q) return ERROR;q->nextarc=NULL;q->adjvex=n;while(key[m]&&p->nextarc){//key存储着该链表的长度，当其不为零时在首结点后插入新结点p=p->nextarc;key[m]++;//链表长度加1}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}//当链表长度为零时，新结点为首结点else p->nextarc=q;return 1;}/*·················创建邻接表··········*/int CreatAList(ALGraph &G){int i,j,m,n,key[MAX_VERTEX_NUM]; char x,y,w;AList p,q;SetGraphKind(G,option);printf("邻接表：请输入顶点的个数和弧的个数：");scanf("%d %d",&G.vexnum ,&G.arcnum);if(G.vexnum>20){printf("您输入的顶点个数超过最大值");return ERROR;}printf("请输入个顶点：\n");for(i=1;i<=G.vexnum;i++){fflush(stdin);scanf("%c",&G.vertices[i].data);21G.vertices[i].firstarc=NULL;key[i]=0;}if(G.kind==DG){//有向图printf("请输入弧（如AB,其中AB与BA是不同的弧）：\n");for(j=1;j<=G.arcnum;j++){fflush(stdin);scanf("%c%c",&x,&y);//输入弧的两顶点m=LocateVex(G,x);//将两顶点转换成数组下标n=LocateVex(G,y);p=G.vertices[m].firstarc;//获取第m个链表的首结点，及以第m个顶点为首结点的链表q=(AList)malloc(sizeof(ArcNode));//申请结点存储空间if(!q) return ERROR;q->nextarc=NULL;q->adjvex=n;while(key[m]&&p->nextarc){//链表长度不为零，且下一个结点存在时，在首结点后插入新结点p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}//链表长度为零时，新结点为首结点else p->nextarc=q;}}if(G.kind==UDG){printf("请输入弧（如AB）：\n");for(j=1;j<=G.arcnum;j++){fflush(stdin);scanf("%c%c",&x,&y);setList(x,y,G,key);setList(y,x,G,key);}}if(G.kind==DN){printf("请输入依次输入弧以及这条弧的权值（如AB 8，其中AB与BA是不同的弧）：\n");22for(j=1;j<=G.arcnum;j++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);m=LocateVex(G,x);n=LocateVex(G,y);p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q ;}}if(G.kind==UDN){printf("无向网请输入依次输入弧以及这条弧的权值（如AB 8）：\n");for(j=1;j<=G.arcnum;j++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);m=LocateVex(G,x);n=LocateVex(G,y);p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q ;23int temp;temp=m;m=n;n=temp;p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q ;}}return OK;}/*·················判断以第v个顶点为首结点的链表是否存在··········*/int FirstAdjVex(ALGraph G,int v){if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;//存在则返回首结点return 0;}/*·················获取以第v个顶点为首结点的链表中的结点w的子结点··········*/ int NextAdjVex(ALGraph G,int v,int w){AList s;s=G.vertices[v].firstarc;//获取链表的首结点vwhile(s->adjvex!=w)//当结点不是w时，指针后移直到找到结点w或到达最后一个结点s=s->nextarc;24if(s->nextarc)//跳出循环后，结点不为空，则表明找到了结点w，否则表示已至链表最后一个结点return s->nextarc->adjvex;return 0;}/*·················遍历结点v的叶子结点··········*/void DFS(ALGraph G,int v){int w;visited[v]=1; printf("%c ",G.vertices[v]);//输出第v个顶点，并标记为已访问for(w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w)){//遍历第v个顶点的子结点，并递归遍历子结点的子结点if(!visited[w]) DFS(G,w);}}/*·················图的深度优先遍历··········*/void DFSTraverse(ALGraph G){int v;visited[0]=1;//数组的存储是从1开始的，数组【0】不使用for(v=1;v<=G.vexnum;v++) visited[v]=0;//初始化各顶点的访问状态为未访问for(v=1;v<=G.vexnum;v++)if(!visited[v]) DFS(G,v);//从第一个顶点开始遍历}/*·················图的广度优先遍历··········*/void BFSTraverse(ALGraph G){int v,w,u;LinkQueue Q;for(v=1;v<=G.vexnum;v++) visited[v]=0;//初始化各顶点为未访问visited[0]=1;//数组的存储是从1开始的，数组【0】不使用25InitQueue(Q);//创建队列for(v=1;v<=G.vexnum;v++)//从第一个顶点开始遍历if(!visited[v]){visited[v]=1;printf("%c ",G.vertices[v]);EnQueue(Q,v);//将该顶点标记为已访问，输出，并加入到队列中while(!QueueEmpty(Q)){//遍历队列中顶点的所有子结点DeQueue(Q,u);//获取队首的顶点，赋值给Ufor(w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w)){//遍历顶点U所有未访问的子结点if(!visited[w]){visited[w]=1;printf("%c ",G.vertices[w]);EnQueue(Q,w);//将子结点加入队列，以便遍历子结点的子结点}//ifelse break;}//for}//while}//if}/*·················计算各顶点入度··········*/void FindInDegree(ALGraph G,int in[]){int i,j,k;AList p;for(k=1;k<=G.vexnum;k++) in[k]=0;//初始化各顶点入度为0for(i=1;i<=G.vexnum;i++){p=G.vertices[i].firstarc;//获取个链表的首结点while(p){//遍历链表的子结点j=p->adjvex;//获取子结点in[j]++;//子结点的入度加1p=p->nextarc;//指向下一子结点}26}}/*·················拓扑排序（打印输出）··········*/int TopologicalSort(ALGraph G){int i,k,count;AList p;SqStack S;FindInDegree(G,indegree);//计算各顶点入度InitStack(S);//创建栈for(i=1;i<=G.vexnum;i++)if(!indegree[i]) Push(S,i);//寻找入度为0的点，并加入到栈中count=0;//对输出的顶点计数if(StackEmpty(S)) printf("此有向图不符合条件！");while(!StackEmpty(S)){Pop(S,i);//从栈中取出顶点开始输出printf("%c ",G.vertices[i].data);++count;//输出的顶点个数加1for(p=G.vertices[i].firstarc;p;p=p->nextarc){//将顶点i的子结点的入度减1 k=p->adjvex;if(!(--indegree[k])) Push(S,k);//如子结点的入度减为0，则入栈}}if(count<=G.vexnum) return ERROR;else return OK;}/*·················求最小生成树··········*/int Minimum(MGraph G,closedges m){int i,j,min=INFINITY;for(i=1;i<=G.vexnum;i++){//从待选的可达集合中选取一条代价最小的边if(m[i].lowcost){//到顶点i可达时执行，即到顶点的权值不为0if(m[i].lowcost<min){min=m[i].lowcost;j=i;}27}}return j;}/*·················最小生成树（普里姆算法实现）··········*/void MinSpanTree_PRIM(MGraph G,char u){int i,j,k;closedges closedge;k=LocateVex(G,u);//获取初始顶点对应的数组下标for(j=1;j<=G.vexnum;j++)//初始化辅助数组，计算从初始顶点到各顶点的最小代价if(j!=k) {closedge[j].adjvex=u;//u是已连通的顶点，表示该顶点J是同那个顶点连在一起closedge[j].lowcost=G.arcs[k][j].adj;}closedge[k].lowcost=0;//顶点k到自身的最小代价设为0，即该顶点已加入最小生成树中for(i=2;i<=G.vexnum;i++){k=Minimum(G,closedge);//获取最小代价边连通的顶点printf("%c%c ",closedge[k].adjvex,G.vexs[k]);//输出最小生成树的弧closedge[k].lowcost=0;//该顶点已加入最小生成树中for(j=1;j<=G.vexnum;j++)//将顶点k代入重新计算到待连通顶点的最小代价if(G.arcs[k][j].adj<closedge[j].lowcost){//如果通过K连通该顶点的代价小于之前的，则更新closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}/*·················对链表进行拓扑排序，并存储在栈中··········*/int TopologicalOrder(ALGraph G,SqStack &T){int i,j,k,count; SqStack S; AList p;FindInDegree(G,indegree);InitStack(S);for(i=1;i<=G.vexnum;i++)28if(!indegree[i]) Push(S,i);InitStack(T);count=1;for(i=1;i<=G.vexnum;i++) ve[i]=0;//初始化到达各顶点的总权值花销为0while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;if(--indegree[k]==0) Push(S,k);if(ve[j]+p->quan>ve[k]) ve[k]=ve[j]+p->quan;//顶点J的子结点K的总权值=顶点j的权值花销+弧的权值,即该顶点的最早发生时间}}if(count<=G.vexnum) return ERROR;else return OK;}/*·················关键路径int j 指向顶点的数组下标int k 被指向顶点的数组下标标int ee 最早发生时间int el 最晚发生时间int dut 事件持续时间char tag 关键路径标识符，*表示该弧为关键路径SqStack T 堆Alist p 链表的结点int v1[MAX_VERTEX_NUM] 顶点权值记录数组，及该顶点的最早发生时间··········*/int CriticalPath(ALGraph G){int i,j,k,ee,el,dut,v1[MAX_VERTEX_NUM]; SqStack T; AList p; char tag;int str[10];int count=0;//声明一个数组来存放关键路径的各个结点，count表示当前数组使用长度，也可理解为下一结点的存放位置if(!TopologicalOrder(G,T)) return ERROR;//按拓扑排序将各顶点依次入栈for(i=1;i<=G.vexnum;i++){//初始化各顶点的权值为最后一个顶点的总权值花销，即工程的总时间花销29v1[i]=ve[G.vexnum];}while(!StackEmpty(T))//按拓扑顺序出栈，分别计算各顶点的最晚发生时间for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->quan;if(v1[k]-dut<v1[j]) v1[j]=v1[k]-dut;}for(j=1;j<=G.vexnum;j++)//循环代入所有顶点，遍历其子结点，根据弧的权值，得到最早发生时间和最晚发生时间，并判断该弧是否为关键路径for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->quan;ee=ve[j];el=v1[k]-dut;tag=(ee==el)?'*':' ';printf("%d %d %d %d %d %c\n",j,k,dut,ee,el,tag);/* 下面为非必需代码，功能为输出关键路径*/if(count==0) //存储关键路径的第一个结点（第一个链接表的首结点--str[count++]=j;if(tag=='*')//如果该弧为关键路径，则将该弧的被指向顶点存储到str中{str[count++]=k;}}for(int n=0;n<count;n++){//输出关键路径printf("%d",str[n]);printf("->");}return OK;} //求关键路径/****************最短路径*************///Dijkstra算法//求G（用邻接矩阵表示）中源点v到其他各顶点最短路径,n为G中顶点数//dist distinct 的缩写意思是在查询结果中去掉重复的记录void Dijkstra(MGraph * G,PathType path[],int dist[],int v,int n){int i,j,count,s[MAX_VERTEX_NUM],max,u;//s[n]用来标志源点到某顶点的最短路径是否求出for(i=1;i<=n;i++){//1.初始化s[i]=0;if(G->arcs[v][i].adj!=INFINITY) //INFINITY为∞30dist[i]=G->arcs[v][i].adj;else dist[i]=MAX_INT;//v到其他顶点的权为当前最短路径，送dist[i]path[i].pi[0]=v;path[i].end=0;}dist[v]=0;s[v]=1;//源点到源点本身的最短路径求出count=1;while(count<=n-1){//求n-1条最短路径max=MAX_INT;// MAX_INT为无穷大值，需要实际情况设置for(j=1;j<=n;j++){//2.找当前最短路径长度if(s[j]==0&&dist[j]<max){u=j;max=dist[j];}}if(max==MAX_INT)break;//最短路径求完（不足n-1）条，跳出while循环s[u]=1;//表示V到Vu最短路径求出path[u].end++;path[u].pi[path[u].end]=u;for(j=1;j<=n;j++){//3.u求出后，修改dist和path向量，执行完后返回2，知道跳出循环if(s[j]==0&&dist[j]>dist[u]+G->arcs[u][j].adj&&G->arcs[u][j].adj!=INFINITY){dist[j]=dist[u]+G->arcs[u][j].adj;path[j]=path[u];}}count++;}}/*·················有向图的功能操作界面··········*/void DG_(MGraph G1,ALGraph G2){int i,j,k,m,key;AList s;char x,y;for(k=0;;){31key=0;system("cls");//清空显示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<=G1.vexnum;i++){//输出邻接矩阵for(j=1;j<=G1.vexnum;j++){printf(" %d",G1.arcs[i][j].adj);}printf("\n");}break;case 2: CreatAList(G2);printf("有向图的邻接表：\n");for(i=1;i<=G2.vexnum;i++){//输出链接表printf("%c:",G2.vertices[i]);s=G2.vertices[i].firstarc;while(s){j=s->adjvex;fflush(stdin);printf("<%c ",G2.vertices[i]);printf("%c> ",G2.vertices[j]);s=s->nextarc;}printf("\n");}break;case 3:printf("有向图的拓扑排序：\n");TopologicalSort(G2);break;case 4:key=1;break;}printf("\n");if(key) break;//跳出循环，返回上一层system("pause");//暂停程序执行，直到监听到操作}printf("\n\n");} //DG/*·················有向网的功能操作界面··········*/32void DN_(MGraph G1,ALGraph G2){int i,j,k,m,key;AList s;for(k=0;;){key=0;system("cls");printf("**************************\n");printf("你选择了对有向网的基本操作及应用：\n1创建邻接矩阵\n2创建邻接表\n3关键路径\n4最短路径\n5退出\n");printf("**************************\n");printf("请选择：");scanf("%d",&m);switch(m){case 1: CreatGraph(G1); printf("有向网的邻接矩阵：\n");for(i=1;i<=G1.vexnum;i++){for(j=1;j<=G1.vexnum;j++){if(G1.arcs[i][j].adj==INT_MAX)printf(" ∞");else printf(" %d",G1.arcs[i][j].adj);}printf("\n");}break;case 2: CreatAList(G2); printf("有向网的邻接表：\n");for(i=1;i<=G2.vexnum;i++){printf("%c:",G2.vertices[i]);s=G2.vertices[i].firstarc;while(s){j=s->adjvex;fflush(stdin);printf("<%c ",G2.vertices[i]);printf("%c> ",G2.vertices[j]);printf(" %d ",s->quan);s=s->nextarc;}printf("\n");}break;case 3: printf("有向网关键路径：\n");CriticalPath(G2);break;case 4:{int i,j,v,count=0;//v为起点，n为顶点个数char c;PathType path[MAX_VERTEX_NUM];//v到各顶点的最短路径向量int dist[MAX_VERTEX_NUM];//v到各顶点最短路径长度向量printf("请输入最短路径起点：");33。