算法与数据结构课程设计报告系（院）：计算机科学学院专业班级：教技1001班*名：***学号：*********指导教师：***设计时间：2012.6.16 - 2012.6.24设计地点：4号楼2号机房目录一、设计方案及实现过程******************第3页二、实现代码***********************************第4页三、测试******************************************第19页四、难点与收获********************************第21页一、设计方案及实现过程这次课程设计要求实现无向图、有向图、无向网以及有向网的一些基本操作以及应用，大体的方案是先进入界面后，选择无向图、有向图、无向网、无向网中的一个，然后创建相应的图或者网，创建好后，在此基础上选择进行相关的操作，具体的函数放在main函数前面，通过多次函数调用已达到具体操作的实现。
流程图如下：进入选择界面1 无向图创建无向图1 创建无向图的邻接矩阵函数调用2 创建无向图的邻接表函数调用3无向图的深度优先遍历函数调用4 无向图的广度优先遍历函数调用5 返回选择主界面2 有向图3 无向网4 有向网5 退出有向图、无向网、有向网的操作和无向图类似，在这里不一一列举。
二、实现代码#include<stdio.h># include <stdlib.h># 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 <ctype.h>#include <string.h>#include <queue>#include <stack>#include <process.h>using namespace std;#define MAX_VERTEX_NUM 20#define MAX 1000typedef struct{int a[maxlen],b[maxlen],h[maxlen];char vexs[maxlen];int vexnum,arcnum;int kind;int arcs[maxlen][maxlen];}graph;typedef struct node{int adjvex;int info;struct node *next;}edgenode;typedef struct{int id;char data;edgenode *link;}vexnode;typedef struct{vexnode adjs[maxlen];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 stack[maxlen];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("vertex\t");for (i=0;i<g.vexnum;i++) printf("%4c",g.vexs[i]);printf("\n");for(i=0;i<g.vexnum;i++){printf("% 4c \t",g.vexs[i]);for(j=0;j<g.vexnum;j++) printf("%4d",g.arcs[i][j]);printf("\n");}return g;}void create_2(graph g){ //构造有向图int i,j,k,c=0;for (i=0;i<g.vexnum;i++)for(j=0;j<g.vexnum;j++)g.arcs[i][j]=c;for(k=0;k<g.arcnum;k++)g.arcs[g.a[k]-1][g.b[k]-1]=1;printf_adjmatrix(g);}void create_1(graph g){ //构造无向图int i,j,k,c=0;for (i=0;i<g.vexnum;i++)for(j=0;j<g.vexnum;j++)g.arcs[i][j]=c;for(k=0;k<g.arcnum;k++){g.arcs[g.a[k]-1][g.b[k]-1]=1;g.arcs[g.b[k]-1][g.a[k]-1]=1;}printf_adjmatrix(g);}graph create_4(graph g){ //构造有向网int i,j,k,c=999;for (i=0;i<g.vexnum;i++)for(j=0;j<g.vexnum;j++)g.arcs[i][j]=c;for(k=0;k<g.arcnum;k++)g.arcs[g.a[k]-1][g.b[k]-1]=g.h[k];printf_adjmatrix(g);return g;}graph create_3(graph g){ //构造无向网int i,j,k,c=999;for (i=0;i<g.vexnum;i++)for(j=0;j<g.vexnum;j++)g.arcs[i][j]=c;for (k=0;k<g.arcnum;k++){g.arcs[g.a[k]-1][g.b[k]-1]=g.h[k];g.arcs[g.b[k]-1][g.a[k]-1]=g.h[k];}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("Error\n");}}adjlist createlist (graph g ,adjlist adjl){ //创建邻接表int i;edgenode *p;if(g.kind==1||g.kind==3){//创建有向邻接表for(i=0;i<adjl.arcnum;i++){p=(edgenode*)malloc(sizeof(edgenode));p->adjvex=g.b[i];p->info=g.h[i];p->next=adjl.adjs[g.a[i]-1].link;adjl.adjs[g.a[i]-1].link=p;}}if(g.kind==2||g.kind==4){//创建无向邻接表for(i=0;i<adjl.arcnum;i++){p=(edgenode*)malloc(sizeof(edgenode));p->info=g.h[i];p->adjvex=g.b[i];p->next=adjl.adjs[g.a[i]-1].link;adjl.adjs[g.a[i]-1].link=p;p=(edgenode*)malloc(sizeof(edgenode));p->info=g.h[i];p->adjvex=g.a[i];p->next=adjl.adjs[g.b[i]-1].link;adjl.adjs[g.b[i]-1].link=p;}}printf("邻接表为:\n");for(i=0;i<g.vexnum;i++){printf("[%d,%c]=>",i+1,adjl.adjs[i].data);p=adjl.adjs[i].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 visit[maxlen]; //深度优先搜索void DFS(adjlist adjl,int i){edgenode *p;visit[i]=1;printf("%c ",adjl.adjs[i].data);for(p=adjl.adjs[i].link;p;p=p->next){if(!visit[p->adjvex]) DFS(adjl,p->adjvex);}}void DFSTraverse(adjlist adjl){int i;printf("\t\t深度优先搜索:");for( i=0;i<maxlen;i++)visit[i]=false;for( i=0;i<=adjl.vexnum;i++)if(!visit[i]) DFS(adjl,i);}queue <int> Q;void BFSTraverse(adjlist adjl) { //广度优先搜索edgenode *w;int i,j;printf("\n\t\t广度优先搜索:");for( i=0;i<maxlen;i++)visit[i]=0;for(i=0;i<=adjl.vexnum;i++){if(!visit[i]){visit[i]=1;printf("%c ",adjl.adjs[i].data);Q.push(i);while(!Q.empty()){j=Q.front();Q.pop();for( w=adjl.adjs[i].link;w;w=w->next)if(!visit[w->adjvex]){visit[w->adjvex]=1;printf("%c ",adjl.adjs[w->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->stack[s->top]=x;}return 1;}status pop(stackstru *s) //出栈{int y;if(s->top==0)printf("the stack is empty!\n");else{y=s->stack[s->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 <int> S;edgenode *p;int i,j,count=0;printf("\n拓扑排序：");for(i=0;i<=adjl.vexnum;i++)if(adjl.adjs[i].id==0)S.push(i);count=0;while(!S.empty()){j=S.top(); S.pop();count++;printf("(%d %c) ",j,adjl.adjs[j].data);for(p=adjl.adjs[i].link;p;p=p->next){int k=p->adjvex;int d=--(adjl.adjs[k].id);if(!d)S.push(k);}}if(count<adjl.vexnum){ printf("\n网中有环!\n");return error;}else return ok;}void prim(graph g){int i,j,k,min;int lowcost[maxlen];int closet[maxlen];printf("最小生成树的边为:\n");for(i=1;i<g.vexnum;i++){lowcost[i]=g.arcs[0][i];closet[i]=1;}closet[1]=0;j=1;for(i=1;i<g.vexnum;i++){min=lowcost[j];k=i;for(j=1;j<g.vexnum;j++)if(lowcost[j]<min&&closet[j]!=0){min=lowcost[j];k=j;}printf("(%c,%c),",g.vexs[k-1],g.vexs[closet[k-1]]);closet[k]=0;for(j=1;j<g.vexnum;j++)if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0){lowcost[j]=g.arcs[k][j];closet[j]=k;}}}int ve[maxlen];int vl[maxlen];status toporder(adjlist adjl,stackstru *t){ //关键路径int i,j,count,k;edgenode *p;initstack(s);initstack(t);for(i=0;i<adjl.vexnum;i++)if(adjl.adjs[i].id==0) push(s,i);count=0;for(i=0;i<adjl.vexnum;i++) ve[i]=0;while(!stackempty(s)){j=pop(s);push(t,j);++count;for(p=adjl.adjs[j].link;p;p=p->next){k=p->adjvex;if(--adjl.adjs[k-1].id==0) push(s,k-1);if(ve[j]+(p->info)>ve[k-1]) ve[k-1]=ve[j]+(p->info);}}if(count<adjl.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;i<adjl.vexnum;i++) vl[i]=ve[i-1];printf("关键路径为:\n");while(!stackempty(t))for(j=pop(t), p=adjl.adjs[j].link;p;p=p->next){k=p->adjvex; dut=(p->info);if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;}for(j=0;j<adjl.vexnum;++j)for(p=adjl.adjs[j].link;p;p=p->next){k=p->adjvex;dut=p->info;ee=ve[j];el=vl[k-1]-dut;if(ee==el) printf("(%c,%c)->",adjl.adjs[j].data,adjl.adjs[k-1].data);}return ok;}void shortpath_dijkstra(graph g) //有向网的最短路径{int cost[maxlen][maxlen];int dist[maxlen];int path[maxlen];int s[maxlen];int i,j,v0,min,u;printf("\n请输入起点的编号:");scanf("%d",&v0);v0--;for(i=0;i<g.vexnum;i++){for(j=0;j<g.vexnum;j++)cost[i][j]=g.arcs[i][j];}for(i=0;i<g.vexnum;i++){dist[i]=cost[v0][i];if(dist[i]<large&&dist[i]>0) path[i]=v0;s[i]=0;}s[v0]=1;for(i=0;i<g.vexnum;i++){min=large;u=v0;for(j=0;j<g.vexnum;j++)if(s[j]==0&&dist[j]<min){min=dist[j];u=j;}s[u]=1;for(j=0;j<g.vexnum;j++)if(s[j]==0&&dist[u]+cost[u][j]<dist[j]){dist[j]=dist[u]+cost[u][j];path[j]=u;}}printf("\n顶点%d到各顶点的最短路径长度为:\n",v0);for(i=0;i<g.vexnum;i++)if(s[i]==1){u=i;while(u!=v0){ printf("%4c<-",g.vexs[u]);u=path[u];}printf("%4c",g.vexs[u]);printf(":%d\n",path[i]);}else printf("%4c<-%4c:无路径\n",g.vexs[i],g.vexs[v0]);}void ShowMainMenu(){printf("\n");printf("**************图的基本操作及应用***************\n");printf("* 1 无向图的基本操作及应用*\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("请选择：");scanf("%d",&n);switch(n){case 1:printf("----------wait-------");creategraph(g);break; //邻接矩阵case 2:printf("----------wait-------");createlist (g,adjl);break; //邻接表case 3:printf("----------wait-------");DFSTraverse(adjl);break; //深度优先搜索case 4:printf("----------wait-------");BFSTraverse(adjl);break; //广度优先搜索case 5:break;default:printf("ERROR!");}}while(n!=5);}void DG(){int n;do{printf("\n");printf("**************有向图的基本操作及应用***************\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-------");creategraph(g);break; //邻接矩阵case 2:printf("--------wait-------");createlist (g,adjl);break; //邻接表case 3:printf("--------wait-------");createlist(g,adjl);TopologicalSort(adjl);break; //拓扑排序case 4:break; //退出default:printf("ERROR!");}}while(n!=4);}void UDN(){int n;do{printf("\n");printf("**************无向网的基本操作及应用***************\n");printf("* 1 创建无向网的邻接矩阵*\n");printf("* 2 创建无向网的邻接表*\n");printf("* 3 Prim算法求最小生成树*\n");printf("* 4 kraskal算法求最小生成树*\n");printf("* 5 退出\n");printf("***************************************************\n");printf("请选择：");scanf("%d",&n);switch(n){case 1:printf("---------wait-------");creategraph(g);break; // 创建无向网的邻接矩阵case 2:printf("--- ----wait-------");createlist (g,adjl);break; // 创建无向网的邻接表case 3:printf("---------wait-------");prim(g);break; //Prim算法求最小生成树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");printf("请选择：");scanf("%d",&n);switch(n){case 1:printf("---------wait-------");creategraph(g);break; //创建有向网的邻接矩阵case 2:printf("---------wait-------");createlist (g,adjl);break; //创建有向网的邻接表case 3:printf("---------wait-------");criticalpath(adjl);break; //关键路径case 4:printf("---------wait-------");criticalpath(adjl);break; //单源顶点最短路径问题case 5:break; //退出default:printf("ERROR!");}while(n!=5);}void main(){int i,j,k,h,n;do{ShowMainMenu();printf("请选择：");scanf("%d",&n);if(n>5) error;else{g.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;i<g.vexnum;i++){printf("第%d个顶点的信息:",i+1);scanf("%s",&g.vexs[i]);adjl.adjs[i].data=g.vexs[i];adjl.adjs[i].link=null;adjl.adjs[i].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.a[k-1]=i;g.b[k-1]=j;while (i<1||i>g.vexnum||j<1||j>g.vexnum){printf(" 编号超出范围,重新输入");//goto label;}if (g.kind==3||g.kind==4){printf("\t该边的权值:");scanf("%d",&h);g.h[k-1]=h;}else g.h[k-1]=null;adjl.adjs[i].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语言的编程环境都花了一段时间。
