算法与数据结构课程设计

1、算法与数据结构课程设计 目录一、设计方案*第2页 二、实现过程*第4页 三、测试*第4页 四、使用说明*第11页 五、难点与收获*第12页 六、实现代码*第13页 七、可改进的地方*第 37页1、 设计方案 根据课程设计任务书，按照要求，需要设计有向图、无向图 、有向网、无向网四种图，邻接矩阵、邻接表两种数据存储结构，共十四种基本操作及应用，三层以上的显示菜单。图有关线性表、栈和队列的基本操作。由于显示菜的操作中又包含单已给出，剩下的只是把函数写入其中 1、以两种存储结构为基础 主要有邻接矩阵存储结构和邻接表存储结构。 邻接矩阵:(1).存储表示：定义顶点、弧、图的各类标志 (2)连接矩阵类型

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并标

3、记结点v已访问； (2).查找结点v的第一个邻接节点; (3).若结点v的邻接节点存在，则继续执行，否则算法结束； (4).查找结点v的邻接结点的下一个邻接结点w,转到步骤3。 4.图的广度优先遍历：采用邻接表结构，指定任意顶点x为初始顶点，利用顺序循环对列以保持访问过的结点的顺序 (1).首先访问初始结点v并标记结点v为已访问； (2).结点v入队列；2 (3).当队列非空时则继续执行，否则算法结束； (4).出队列取得队头结点u; (5).查找u的第一个邻接结点w； (6).若u的邻接结点w不存在则转到步骤3，否则循环执行下列步骤； (7).若结点w尚未被访问，则访问结点w并标记结点w为已

4、访问5. 有向图的拓扑排序：采用邻接表结构 （1）调用计算顶点入度的函数，创建栈 (2).在有向图中选择一个没有入度的顶点并入栈； (3).图中删除该顶点和所有以它为尾的弧。 (4)重复上述两步，直至全部顶点均已输出，就得到了一个拓扑有序序列。 6. 无向网的最小生成树有两种算法：Prima算法和Kruskal算法,此次采用Prima算法 (1).从网中的某个顶点出发，选择与该顶点有路径的所有顶点中权值最小的一条 (2)从最小的这条的另一顶点出发，重复上述过程，直至图中所有顶点都被访问7.关键路径：(1) 输入e条弧，建立AOE网的存储结构； (2) 从源点v0出发,令ve0=0，按拓扑有序求

5、其余各顶点的最早发生时间。如 果得到拓扑有序序列中的顶点个数小于网中的顶点数，则说明网中存在环，不 能求关键路径，算法终止；否则执行第三步。 (3) 从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发 生时间vli； (4) 根据各顶点的和值，求每条弧的最早开始时间e(s)和最迟开始时间e(s)，某 条弧满足条件e(s)=l(s)，则为关键活动。8. 最短路径：利用Dijkstra算法 (1)若从v到vi有弧，则Di为弧上的权值，否则Di为无穷大。 (2)长度为Dj=MinDi|vi属于V的路径就是从v出发的长度最短的一条路径。3二、实现过程Main():主函数模块。在

6、主函数模块中调用以下函数：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)C

7、reatAList(G2); (3)DFSTraverse(G2); (4)BFSTraverse(G2);4、 无向网UDN_(MGraph G1,ALGraph G2) (1)CreatGraph(G1); (2)CreatAList(G2); (3)MinSpanTree_PRIM(G1,u);3、 测试按照设计任务的要求，我先完成了存储结点、边、邻接矩阵、邻接表、队列、栈等存储结构体的设计，其次是栈和队列的基本操作和实现，四种图的创建和显示，基于两种存储结构的各种算法的实现测试图样：有向图45无向图67有向网89无向网104、 使用说明 根据运行出的内容提示操作即可 输入顶点数，边数，

8、弧数，权值可以是正整数，也能是字母，但不能是标点符号。 115、 难点与收获 此次课程设计虽然为已经学过的内容，但设计起来仍然有很大难度，曾经学过的也只是明白作法，对算法却很不明白，虽然教科书上有部分代码，但做起来会很困难，通过从网上搜索资料和向老师同学请教才能编写出代码，初次编写出的有很多错误，需要自己不断调试，由于在初学时基础并没有打结实，有很多名词也没有记住。 遇到的最大的困难还是不能将算法更好的理解，进而不可以跟好的运用，如不能把邻接表存储结构定义好，这就意味着无法创建以邻接表存储结构为基础的四种图，就无法实现拓扑排序和关键路径的算法。为此我只好自己定义，自己编写代码，书上的代码只剩下

9、参考的作用，一步步慢慢调试。在单链表中，其结点只有两个域，指针域*next和数据域data，而在邻接表中其结点有三个域，指针域*next，顶点位置域adjvex和相关信息域*info。顶点位置域可以表示两个顶点之间的连接关系或相邻关系，相关信息域可以表示弧或边的信息或权值，我一直无法理解的无法描述清楚的东西现在豁然开朗，L->next=0（NULL）跟G.verticesi.firstarc->next=0（NULL）是一样的，都是存在的，其值都为0。尽管单链表有两个域，邻接表有三个域，但这两个域和三个域都没有分配内存空间，所以L->next->data,L->n

10、ext- >next,G.verticesi.firstarc->next->next,G.verticesi.firstarc->next-> adjvex,G.verticesi.firstarc->next->info都没有值，在编译器中会出现错误无法计算它们的值。总之，难点可概括为以下几点： 1、涉及知识范围广，由于数据结构学得并不好，所以很多算法只是知其所以然而不知其所以然，能够理解，但要是自己独立去实现，不去查找和参考相关资料，那几乎是不可能完成的任务； 2、代码太长，没有好的设计理念和层次，完成时警告非常多，而且都是些没办法解决的问题。因

11、为一点点警告都会让程序出现未知错误； 3、部分算法只是理解，没有掌握，如无向图的广度优先搜索、最短路径等。在解决这些问题中，我也收获了很多。1、调试。调试是最考验耐心的，调试过程中会遇到很多问题，找不到出错的原因，但通过自己的不懈努力，解决了这些问题122在算法的应用上更加清楚明朗3、一些编程规则。这也是编程重要收获的一部分。变量必须先声明后使用，使用前最好赋初值，多属性的变量（结点）最好在使用前初始化，避免出现问题；尽量不要定义同名变量或函数，避免出现命名冲突；少使用全局变量或函数以及void关键词；编程序要有框架和执行步骤；输入要有出错机制，防止程序终止执行；要逐步形成良好的编程习惯 4、

12、通过这次课设，让我明白扎实掌握程序语言是编写程序的基础，要认真的学会基础六、实现代码#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/定义栈的容量#defi

13、ne STACKINCREAMENT 10/定义栈的每次增长量#define MAX_INT 10000 /无穷大typedef int AdjType;typedef structint piMAX_VERTEX_NUM;/存放v到vi的一条最短路径int end;PathType;typedef char VType; /设顶点为字符类型typedef enumDG,UDG,DN,UDNGraphKind;/定义图、网的枚举常量/*·············&#

14、183;··· 邻接矩阵····················*/typedef struct ArcCell int adj; /弧的权值13 /infotype *info;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM;/存储顶点的数组

15、AdjMatrix arcs;/存储邻接矩阵的二维数组 int vexnum,arcnum;/顶点数和弧数GraphKind kind;/链接矩阵的类型MGraph; /*················· 邻接表··················

16、··*/typedef struct ArcNode int adjvex;/与首结点关联的顶点 int quan;/该顶点的权值 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;

17、/链接表的类型ALGraph; /*················· 队列····················*/typedef struct QNodechar data;/队列中元素数据struct QNode *nex

18、t;/指向下一元素的指针QNode,*QueuePre;typedef structQueuePre front;/队首指针QueuePre rear;/队尾指针LinkQueue; 14/*················· 栈················

19、3;···*/typedef struct int *base;/栈底指针int *top;/栈首指针int stacksize;/栈的大小SqStack; /*················· 求最小生成树中的辅助数组··········*/typedef struct char adjvex;

20、/最小生成树的结点int lowcost;/到该结点的最小权值开销closedgesMAX_VERTEX_NUM; int option; /图的类型标识符int visitedMAX_VERTEX_NUM; /顶点访问标记数组int indegreeMAX_VERTEX_NUM; /顶点入度记录数组int veMAX_VERTEX_NUM; /顶点权值记录数组/*················· 链接矩阵类型设置·

21、;·········*/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; /*········

22、;········· 邻接表类型设置··········*/int SetGraphKind(ALGraph &G,int option) 15 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: re

23、turn ERROR; return OK; /*················· 邻接矩阵顶点定位·················将顶点V代入，查询顶点存储数组，返回其数组下标······

24、83;···*/int LocateVex(MGraph G,char v) int m; for(m=1;m<=G.vexnum;m+) if(G.vexsm=v) return m; printf("您输入的顶点不存在"); return ERROR; /*················· 邻接表顶点定位·····&

25、#183;···········将顶点V代入，查询顶点存储数组，返回其数组下标··········*/int LocateVex(ALGraph G,char v) int m; for(m=1;m<=G.vexnum;m+) if(G.verticesm.data=v) return m; printf("您输入的顶点不存在"); return ERROR;

26、16/*················· 队列创建··········*/int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePre)malloc(sizeof(QNode);/申请存储空间，队首队尾指向同一位置if(!Q.front) return ERROR;Q.fron

27、t->next=NULL;return OK; /*················· 元素入队··········*/int EnQueue(LinkQueue &Q,int e)QueuePre p;p=(QueuePre)malloc(sizeof(QNode);if(!p) return OK;p->

28、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

29、) 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

30、 QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return OK;17 return ERROR; /*················· 栈的创建··········*/int InitStack(SqStack &S)S.base=(int*)malloc(STACK_INIT_

31、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

32、.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; /*················

33、3; 元素出栈··········*/int Pop(SqStack &S,int &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK; 18/*················· 判断栈是否为空·····&#

34、183;····*/int StackEmpty(SqStack S)if(S.top=S.base) return OK;return ERROR; /*················· 创建邻接矩阵··········*/int CreatGraph(MGraph &G) i

35、nt 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; /if printf("请输入%d个顶点n",G.v

36、exnum); for(i=1;i<=G.vexnum;+i) /输入矩阵的各顶点 fflush(stdin); /清除缓存，略过 scanf("%c",&G.vexsi); /for if(G.kind=DG|G.kind=UDG)/1.有向图和无向图的矩阵创建 for(i=1;i<=G.vexnum;i+)/矩阵初始化 for(j=1;j<=G.vexnum;j+) G.arcsij.adj=0; if(G.kind=DG)/2.有向图 printf("请输入有向图的两个相邻的顶点<x,y>（如果互相邻接则<x,y&

37、gt;也要输入）：n"); for(k=1;k<=G.arcnum;k+)/循环输入 fflush(stdin); scanf("%c%c",&x,&y);/输入矩阵中弧关联的两顶点 i=LocateVex(G,x);j=LocateVex(G,y);/将两顶点转换成顶点存储数组的下标 G.arcsij.adj=1; /for /2.if19 else/2.无向图 printf("请输入无向图的两个相邻的顶点（x,y）：n"); for(k=1;k<=G.arcnum;k+)fflush(stdin); scanf(

38、"%c%c",&x,&y); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=1; G.arcsji.adj=G.arcsij.adj;/反向关联两顶点 /for /2.else /1.if else/1.有向网和无向网 for(i=1;i<=G.vexnum;i+) for(j=1;j<=G.vexnum;j+) G.arcsij.adj=INT_MAX;/矩阵初始化 if(G.kind=DN) /3.有向网 printf("请输入有向网的两个相邻的顶点<x,y>以及相应的

39、权值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.arcsij.adj=w; /for /3.if else/3 printf("请输入无向网的两个相邻的顶点（x,y）以及相应的权值w：n"); for(k=1;k<=G.arcnum;k+)fflush(stdin); scanf(&quo

40、t;%c%c %d",&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=w; G.arcsji.adj=G.arcsij.adj;/逆向关联 /for /3.else return OK; 20/*··············在邻接表中插入结点··· ······&

41、#183;···*/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.verticesm.firstarc;/获取第m个链表的首结点q=(AList)malloc(sizeof(ArcNode);/申请结点空间if(!q) return ERROR;q->nextarc=NULL;q->adjvex=n;while(keym&&p->n

42、extarc)/key存储着该链表的长度，当其不为零时在首结点后插入新结点p=p->nextarc;keym+;/链表长度加1if(!keym)G.verticesm.firstarc=q;keym+;/当链表长度为零时，新结点为首结点else p->nextarc=q; return 1;/*················· 创建邻接表······&#

43、183;···*/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.vexnum>20) printf("您输入的顶点个数超过最大值"); return ERROR; printf(&qu

44、ot;请输入个顶点：n");for(i=1;i<=G.vexnum;i+)fflush(stdin);scanf("%c",&G.verticesi.data);21 G.verticesi.firstarc=NULL;keyi=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

45、,x);/将两顶点转换成数组下标n=LocateVex(G,y); p=G.verticesm.firstarc;/获取第m个链表的首结点，及以第m个顶点为首结点的链表q=(AList)malloc(sizeof(ArcNode);/申请结点存储空间if(!q) return ERROR;q->nextarc=NULL;q->adjvex=n;while(keym&&p->nextarc)/链表长度不为零，且下一个结点存在时，在首结点后插入新结点p=p->nextarc; keym+;if(!keym)G.verticesm.firstarc=q;key

46、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");22 for(j=1;j<=G.arcnu

47、m;j+)fflush(stdin);scanf("%c%c %d",&x,&y,&w);m=LocateVex(G,x);n=LocateVex(G,y);p=G.verticesm.firstarc;q=(AList)malloc(sizeof(ArcNode);if(!q) return ERROR;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(keym&&p->nextarc)p=p->nextarc;keym+;if(!keym)G.verticesm.

48、firstarc=q;keym+;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.verticesm.firstarc;q=(AList)malloc(sizeof(ArcNode);if(!q) return ERROR

49、;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(keym&&p->nextarc)p=p->nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p->nextarc=q ; 23 int temp;temp=m;m=n;n=temp;p=G.verticesm.firstarc;q=(AList)malloc(sizeof(ArcNode);if(!q) return ERROR;q->nextarc=NULL;q->quan=

50、w;q->adjvex=n;while(keym&&p->nextarc)p=p->nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p->nextarc=q ; return OK; /*················· 判断以第v个顶点为首结点的链表是否存在·····&

51、#183;····*/int FirstAdjVex(ALGraph G,int v)if(G.verticesv.firstarc)return G.verticesv.firstarc->adjvex;/存在则返回首结点return 0; /*················· 获取以第v个顶点为首结点的链表中的结点w的子结点····&#

52、183;·····*/int NextAdjVex(ALGraph G,int v,int w)AList s;s=G.verticesv.firstarc;/获取链表的首结点vwhile(s->adjvex!=w)/当结点不是w时，指针后移直到找到结点w或到达最后一个结点s=s->nextarc;24 if(s->nextarc)/跳出循环后，结点不为空，则表明找到了结点w，否则表示已至链表最后一个结点return s->nextarc->adjvex;return 0;/*···&

53、#183;············· 遍历结点v的叶子结点··········*/void DFS(ALGraph G,int v)int w;visitedv=1; printf("%c ",G.verticesv);/输出第v个顶点，并标记为已访问for(w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w

54、)/遍历第v个顶点的子结点，并递归遍历子结点的子结点if(!visitedw) DFS(G,w); /*················· 图的深度优先遍历··········*/void DFSTraverse(ALGraph G)int v;visited0=1;/数组的存储是从1开始的，数组【0】不使用for(v=1;v&

55、lt;=G.vexnum;v+) visitedv=0;/初始化各顶点的访问状态为未访问for(v=1;v<=G.vexnum;v+) if(!visitedv) DFS(G,v);/从第一个顶点开始遍历 /*················· 图的广度优先遍历··········*/void BFSTraverse(AL

56、Graph G)int v,w,u;LinkQueue Q;for(v=1;v<=G.vexnum;v+) visitedv=0;/初始化各顶点为未访问visited0=1;/数组的存储是从1开始的，数组【0】不使用25 InitQueue(Q);/创建队列for(v=1;v<=G.vexnum;v+)/从第一个顶点开始遍历if(!visitedv) visitedv=1; printf("%c ",G.verticesv); EnQueue(Q,v);/将该顶点标记为已访问，输出，并加入到队列中 while(!QueueEmpty(Q)/遍历队列中顶点的所有子

57、结点 DeQueue(Q,u);/获取队首的顶点，赋值给U for(w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w)/遍历顶点U所有未访问的子结点 if(!visitedw)visitedw=1; printf("%c ",G.verticesw);EnQueue(Q,w);/将子结点加入队列，以便遍历子结点的子结点/if else break; /for/while/if /*·············

58、;···· 计算各顶点入度··········*/void FindInDegree(ALGraph G,int in)int i,j,k;AList p;for(k=1;k<=G.vexnum;k+) ink=0;/初始化各顶点入度为0for(i=1;i<=G.vexnum;i+) p=G.verticesi.firstarc;/获取个链表的首结点while(p)/遍历链表的子结点 j=p->adjvex;/获取子结点inj+;/子结点的入度加1p=p->nextarc;/指向下一子结点26 /*················· 拓扑排序（打印输出）···