算法与数据结构课程设计.docx

算法与数据结构课程设计报告系 （院）： 计算机科学学院 专业班级： 教技1001班 姓 名： 戴征淼 学 号： 201003886 指导教师： 詹泽梅 设计时间： 2012.6.16 - 2012.6.24 设计地点： 4号楼2号机房 目录1、 设计方案及实现过程*第3页2、 实现代码*第4页3、 测试*第19页4、 难点与收获*第21页一、 设计方案及实现过程这次课程设计要求实现无向图、有向图、无向网以及有向网的一些基本操作以及应用，大体的方案是先进入界面后，选择无向图、有向图、无向网、无向网中的一个，然后创建相应的图或者网，创建好后，在此基础上选择进行相关的操作，具体的函数放在main函数前面，通过多次函数调用已达到具体操作的实现。有向图、无向网、有向网的操作和无向图类似，在这里不一一列举。流程图如下：二、 实现代码#include# include # define maxlen 10# define large 999# define true 1# define false 0# define ok 1# define error 0# define overflow -2# define null 0typedef int status;#include #include #include #include #include using namespace std;#define MAX_VERTEX_NUM 20#define MAX 1000typedef structint amaxlen,bmaxlen,hmaxlen;char vexsmaxlen;int vexnum,arcnum;int kind;int arcsmaxlenmaxlen;graph;typedef struct nodeint adjvex;int info;struct node *next;edgenode;typedef struct int id; char data; edgenode *link;vexnode; typedef struct vexnode adjsmaxlen; int vexnum,arcnum; int kind;adjlist;typedef struct qnode int data; struct qnode *next;linkqlist; typedef struct linkqlist *front; linkqlist *rear; linkqueue;typedef struct int stackmaxlen; int top;stackstru;int cnull=-1;graph g;adjlist adjl;stackstru *t;stackstru *s;linkqueue *q;graph printf_adjmatrix(graph g)int i,j;printf(邻接矩阵:n);printf(vertext);for (i=0;ig.vexnum;i+) printf(%4c,g.vexsi);printf(n);for(i=0;ig.vexnum;i+)printf(% 4c t,g.vexsi);for(j=0;jg.vexnum;j+) printf(%4d,g.arcsij);printf(n);return g;void create_2(graph g) /构造有向图int i,j,k,c=0;for (i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)g.arcsij=c;for(k=0;kg.arcnum;k+)g.arcsg.ak-1g.bk-1=1;printf_adjmatrix(g);void create_1(graph g) /构造无向图int i,j,k,c=0;for (i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)g.arcsij=c;for(k=0;kg.arcnum;k+)g.arcsg.ak-1g.bk-1=1;g.arcsg.bk-1g.ak-1=1;printf_adjmatrix(g);graph create_4(graph g) /构造有向网int i,j,k,c=999;for (i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)g.arcsij=c;for(k=0;kg.arcnum;k+)g.arcsg.ak-1g.bk-1=g.hk;printf_adjmatrix(g);return g;graph create_3(graph g) /构造无向网int i,j,k,c=999;for (i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)g.arcsij=c;for (k=0;kg.arcnum;k+)g.arcsg.ak-1g.bk-1=g.hk;g.arcsg.bk-1g.ak-1=g.hk;printf_adjmatrix(g);return g;void creategraph(graph g)switch(g.kind)case 1:create_1(g);break;case 2:create_2(g);break;case 3:create_3(g);break;case 4:create_4(g);break;default:printf(Errorn);adjlist createlist (graph g ,adjlist adjl) /创建邻接表 int i; edgenode *p; if(g.kind=1|g.kind=3)/创建有向邻接表 for(i=0;iadjvex=g.bi; p-info=g.hi; p-next=adjl.adjsg.ai-1.link; adjl.adjsg.ai-1.link=p; if(g.kind=2|g.kind=4)/创建无向邻接表for(i=0;iinfo=g.hi;p-adjvex=g.bi;p-next=adjl.adjsg.ai-1.link;adjl.adjsg.ai-1.link=p;p=(edgenode*)malloc(sizeof(edgenode);p-info=g.hi;p-adjvex=g.ai;p-next=adjl.adjsg.bi-1.link;adjl.adjsg.bi-1.link=p;printf(邻接表为:n);for(i=0;i,i+1,adjl.adjsi.data);p=adjl.adjsi.link;while(p!=null)printf(%c,%d-,adjl.adjs(p-adjvex)-1.data,p-info);p=p-next;printf(n);return adjl;void initqueue(linkqueue *p) /构造空队列p-front=(linkqlist *)malloc(sizeof(linkqlist);p-rear=p-front;(p-front)-next=null;status empty(linkqueue *q) /判断是否为空int v;if(q-front=q-rear) v=true;else v=false;return v;int addqueue(linkqueue *q,int e)q-rear-next=(linkqlist *)malloc(sizeof(linkqlist);q-rear=q-rear-next;if(!q-rear) return -1;q-rear-data=e;q-rear-next=null;return ok;status delqueue(linkqueue *q) /linkqlist *p;int e;if (q-front=q-rear)printf(the linklist is overflow);else p=(q-front)-next;(q-front)-next=p-next;e=p-data;if(q-rear=p)q-rear=q-front;free(p);return(e);bool visitmaxlen; /深度优先搜索void DFS(adjlist adjl,int i)edgenode *p;visiti=1; printf(%c ,adjl.adjsi.data);for(p=adjl.adjsi.link;p;p=p-next)if(!visitp-adjvex) DFS(adjl,p-adjvex); void DFSTraverse(adjlist adjl) int i;printf(tt深度优先搜索 :);for( i=0;imaxlen;i+)visiti=false;for( i=0;i=adjl.vexnum;i+)if(!visiti) DFS(adjl,i); queue Q;void BFSTraverse(adjlist adjl) /广度优先搜索edgenode *w;int i,j;printf(ntt广度优先搜索 :);for( i=0;imaxlen;i+)visiti=0;for(i=0;inext)if(!visitw-adjvex)visitw-adjvex=1; printf(%c ,adjl.adjsw-adjvex-1.data);Q.push(w-adjvex);status initstack(stackstru *s) /构造空栈s-top=0; return ok;status push(stackstru *s,int x) /进栈if (s-top=maxlen) printf(the stack is overflow!n); else s-top=s-top+1; s-stacks-top=x;return 1;status pop(stackstru *s) /出栈 int y; if(s-top=0)printf(the stack is empty!n); elsey=s-stacks-top; s-top=s-top-1; return y;status stackempty(stackstru *s) /判断栈是否为空 if (s-top=maxlen) return (true);else return (false);int TopologicalSort(adjlist adjl) /拓扑排序stack S; edgenode *p;int i,j,count=0;printf(n拓扑排序：);for(i=0;inext) int k=p-adjvex; int d=-(adjl.adjsk.id); if(!d)S.push(k); if(countadjl.vexnum) printf(n网中有环!n);return error;else return ok; void prim(graph g)int i,j,k,min;int lowcostmaxlen;int closetmaxlen;printf(最小生成树的边为:n);for(i=1;ig.vexnum;i+)lowcosti=g.arcs0i;closeti=1;closet1=0;j=1;for(i=1;ig.vexnum;i+)min=lowcostj;k=i;for(j=1;jg.vexnum;j+)if(lowcostjmin&closetj!=0)min=lowcostj;k=j;printf(%c,%c),g.vexsk-1,g.vexsclosetk-1);closetk=0;for(j=1;jg.vexnum;j+)if(g.arcskjlowcostj&closetj!=0)lowcostj=g.arcskj;closetj=k;int vemaxlen;int vlmaxlen;status toporder(adjlist adjl,stackstru *t) /关键路径int i,j,count,k;edgenode *p;initstack(s);initstack(t);for(i=0;iadjl.vexnum;i+)if(adjl.adjsi.id=0) push(s,i);count=0;for(i=0;inext) k=p-adjvex;if(-adjl.adjsk-1.id=0) push(s,k-1);if(vej+(p-info)vek-1) vek-1=vej+(p-info);if(countadjl.vexnum) return error;else return ok;int criticalpath(adjlist adjl) int i,j,k,dut,ee,el;edgenode *p;if(!toporder(adjl,t) return error;for(i=0;inext) k=p-adjvex; dut=(p-info);if(vlk-dutvlj) vlj=vlk-dut;for(j=0;jnext)k=p-adjvex;dut=p-info;ee=vej;el=vlk-1-dut;if(ee=el) printf(%c,%c)-,adjl.adjsj.data,adjl.adjsk-1.data);return ok;void shortpath_dijkstra(graph g) /有向网的最短路径 int costmaxlenmaxlen;int distmaxlen;int pathmaxlen;int smaxlen;int i,j,v0,min,u;printf(n请输入起点的编号:);scanf(%d,&v0);v0-;for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)costij=g.arcsij;for(i=0;ig.vexnum;i+) disti=costv0i;if(disti0) pathi=v0;si=0;sv0=1;for(i=0;ig.vexnum;i+) min=large;u=v0;for(j=0;jg.vexnum;j+)if(sj=0&distjmin)min=distj;u=j;su=1; for(j=0;jg.vexnum;j+)if(sj=0&distu+costujdistj) distj=distu+costuj;pathj=u;printf(n顶点%d到各顶点的最短路径长度为:n,v0);for(i=0;ig.vexnum;i+)if(si=1) u=i;while(u!=v0) printf(%4c-,g.vexsu);u=pathu;printf(%4c,g.vexsu);printf(:%dn,pathi);else printf(%4c5) error;elseg.kind=n;h=n;printf(请输入顶点数,边数:);scanf(%d,%d,&i,&j);g.vexnum=i;adjl.vexnum=i;g.arcnum=j;adjl.arcnum=j;for (i=0;ig.vexnum;i+)printf(第%d个顶点的信息:,i+1);scanf(%s,&g.vexsi);adjl.adjsi.data=g.vexsi;adjl.adjsi.link=null;adjl.adjsi.id=0;for (k=1;k=g.arcnum;k+)/label:if (g.kind=2|g.kind=4)printf(第%d条边的起点编号,终点编号:,k);else printf(第%d条边的两个顶点的编号:,k);scanf(%d,%d,&i,&j);g.ak-1=i;g.bk-1=j;while (ig.vexnum|jg.vexnum)printf( 编号超出范围,重新输入);/goto label;if (g.kind=3|g.kind=4)printf(t该边的权值:);scanf(%d,&h);g.hk-1=h;else g.hk-1=null;adjl.adjsi.id+;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);三、 测试a) 程序开始运行，进入选择界面b） 选择无向图，并创建无向图C）基于已创建的的无向图选择各项具体的操作四、 难点与收获这次的实习报告相对我而言算是比较难的，因为在学这门课程的时候就没怎么专心听讲，所以在拿到计划书的时候，对很多地方感觉很陌生，甚至有一种没办法动手的感觉，加之开始学JAVA以后就很少用C语言编写程序，导致对很多很简单的东西都很陌生，所以熟悉整个C语言的编程环境都花了一段时间。在开始编写代码的时候呢，最开始我是打算仿照书上的算法敲代码，但是结果很多地方都不能实现，那时才明白，书上的算法仅仅是给我们讲解一些原理，要学会弄懂一个算法还需要私底下花很多功夫。自己编写代码的时候，格式一定要简洁明了，特别是当代码量大了的时候，简洁明了的格式可以使得程序的可读性提高很多，也有助于在调试程序时查找错误更改错误，简洁明了的代码有些时候也有助于避免一些不必要的书写错误。在用VC+6.0的环境编写代码的时候，很多人不注意C和C+的区别，最后编写出来的代码产生了很多错误，这一点也是要注意的。编程是一项很细致的工作，不能粗心大意，也许一点小小的错误都会导致整个程序都崩溃。最后一点感受，没有付出是没有收获的，付出了终究会有回报的时候。指导老师意见：成绩: 教师签名： 2012年 6 月 24 日The general staff (1 employees i