12数据结构课程设计报告

算法与数据结构课程设计报告

系（院）： 计算机科学学院

专业班级： 教育技术学1001班

姓名：宋佳

学号： 201003901

指导教师： 詹泽梅

设计时间： 2012.6.16 - 2012.6.24

设计地点： 4号楼2号机房

《算法与数据结构》课程设计任务书

班级：教育技术11001

课程设计题目：图的基本操作及应用

数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。

一．设计目的

1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。

2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。

二．设计任务

设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：

1．无向图的基本操作及应用

① 创建无向图的邻接矩阵

② 创建无向图的邻接表

③ 无向图的深度优先遍历

④ 无向图的广度优先遍历

2．有向图的基本操作及应用

① 创建有向图的邻接矩阵

② 创建有向图的邻接表

③ 拓扑排序

3．无向网的基本操作及应用

① 创建无向网的邻接矩阵

② 创建无向网的邻接表

③ 求最小生成树

4．有向网的基本操作及应用

① 创建有向网的邻接矩阵

② 创建有向网的邻接表

③ 关键路径

④ 单源最短路径

三．设计指导

第一步：根据设计任务，设计DOS菜单。

第二步：设计菜单（c语言）

#include<stdio.h>

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-------");break;

case 2:

printf("----------wait-------");break;

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("**************有向图的基本操作及应用***************\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{

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-------");break;

case 2:

printf("--- ----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");

printf("请选择：");

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:

printf("ERROR!");

}

}while(n!=5);

}

void main(){

int n;

do{

ShowMainMenu();

printf("请选择：");

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);

}

第三步：添加功能函数。在主程序的合适位置添加相应的函数实现各功能（提示：语句printf(“-------wait---------”)所在位置）。

四．成绩评定

l 实习报告（文字不得少于4000字）

一、设计方案；

二、实现过程；

三、实现代码；

四、测试；

五、结论；

六、难点与收获。

l 程序实现

1. 程序运行正确，无编译错误，无逻辑错误；

2. 在第一条的基础上，任务完成的越多，成绩等级越高。

l 成绩由三部分组成：平时考核(20%)、程序实现(50%)、实习报告(30%)

一、 设计方案

由课程设计任务书，按照要求，需要设计有向图3、有向网、无向图、无向网四种图，邻接矩阵、邻接表两种数据存储结构，共十六种基本操作及应用，三层以上的显示菜单。图的操作中又包含有有关线性表、栈和队列的基本操作。由于显示菜单已给出，剩下的只是把函数写入其中，而线性表、栈和队列的基本操作并不复杂，很容易实现，我们只有完成图的相关操作即可。

图的操作都是以两种存储结构为基础的，邻接矩阵存储结构和邻接表存储

结构，如四种图（有向图，有向网，无向图，无向网）的创建，其他的操作都是在四种图创建后才开始进行的。所以，首先必须理解两种存储结构的定义。

图的邻接矩阵存储结构即图的数组表示法。用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。用邻接矩阵存储结构的图具有以下几点特征：

（一）：顶点数：vexnum，边（弧）数：arcnum，图的种类：kind；

（二）：邻接矩阵：arcs(1顶点关系类型:adj 2相关信息:*info)；

（三）：顶点向量（顶点名）：vexs[]；

其优点是以二维数组表示有n个顶点的图时，需存放n顶点的信息和n*n个弧的信息存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求各个顶点的度。缺点其时间复杂度是O（n*n）,例如，构造一个具有n个顶点和e条边的无向网的时间复杂度为O（n*n+e*n）。

图的邻接表存储结构是图的一种链式存储结构。对图中的每个顶点建立一个单链表，每个结点有三个域组成，邻接点域adjvex（弧尾在邻接表链表中的位序），链域nextarc（下一条弧），数据域info(权值)。还要建立一个邻接表链表，用以存放顶点名data和后继指针firstarc,表头结点以顺序结构的形式存储，便于随机访问任一顶点的单链表。邻接表存储结构的优点在于其时间复杂度小。

除此之外，还有十字链表存储结构和多重链表存储结构。由于，没有用到他们，故不再详细描述。

树的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。从图中的某个顶点出发，访问此顶点，然后依次从该顶点出发深度优先搜索遍历图，直至图中所有与该顶点有关的路径都被访问到；此时图中若还有顶点未被访问到，则另选图中的一个未被访问的顶点作为起始点，重述上述过程，直至所有顶点都被访问到。

广度优先搜索遍历类似于树的按层次遍历的过程。以某个顶点为起始顶点，由近至远，依次访问和该顶点有路径相通的且路径长度为1， 2， 3，······的顶点。当图中所有顶点都被访问到后，就完成了图的广度优先搜索遍历。

求无向网的最小生成树问题有两种算法：Prima算法和Kruskal算法。Prima算法是从网中的某个顶点出发，选择与该顶点有路径的所有顶点中路径最小的一条路径，从该最小路径的另一顶点出发，重复上述过程，直至图中所有顶点都被访问完成。Kruskal算法是从网中找出所有路径最小的一条路径，记下已访问该路径的两个顶点，再次从图中找出剩下路径中的最小路径，重复上述过程，直至所有顶点都被访问完成，按访问的顺序依次输出各顶点，即构造了一棵最小生成树。

由某个集合上的一个偏序得到该集合的一个全序的操作就叫做拓扑排序。拓扑排序主要有两个方面的操作：

（1）在有向图中选择一个没有前驱的顶点并输出；

（2）在图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，就得到了一个拓扑有序序列。

求关键路径的算法如下：

输入e条弧，建立AOE网的存储结构；

从源点v0出发,令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间。如果得到的拓扑有序序列中的顶点个数小于网中的顶点数，则说明网中存在环，不能求关键路径，算法终止；否则执行第三步。

从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]；

根据各顶点的和值，求每条弧的最早开始时间e(s)和最迟开始时间e(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。

从某个源点到其余各顶点的最短路径问题：若从v到vi有弧，则D[i]为弧上的权值，否则D[i]为无穷大。显然，长度为D[j]=Min{D[i]|vi属于V}的路径就是从v出发的长度最短的一条路径。

二、 实现及测试过程

按照设计任务的要求，我先完成了存储结点、边、邻接矩阵、邻接表、队列、栈等储存结构体的设计。其次是栈和队列的基本操作和实现，四种图的创建和显示，然后是基于两种存储结构的各种算法的现，最后是三层显示输出菜单。

测试样图：

三、实现代码

#include <stdio.h>

#include<stdlib.h>

#include<limits.h>

#define ERROR 0

#define OK 1

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 21

#define STACK_INIT_SIZE 100

#define STACKINCREAMENT 10

typedef enum{DG,DN,UDG,UDN}GraphKind;

typedef struct ArcCell {

int adj;

//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; //队列

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=DN;break;

case 3: G.kind=UDG;break;

case 4: G.kind=UDN;break;

default: return ERROR;

}

return OK;

} //邻接矩阵类型设置

int SetGraphKind(ALGraph &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;

} //邻接表类型设置

int LocateVex(MGraph G,char v){

int m;

for(m=1;m<=G.vexnum;m++){

if(G.vexs[m]==v) return m;

}

return ERROR;

} //邻接矩阵顶点定位

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;

} //邻接表顶点定位

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;

return 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;

} //元素出栈

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;

}

printf("请输入%d个顶点\n",G.vexnum);

for(i=1;i<=G.vexnum;++i) {fflush(stdin); scanf("%c",&G.vexs[i]);}

if(G.kind==DG||G.kind==UDG){

for(i=1;i<=G.vexnum;i++)

for(j=1;j<=G.vexnum;j++)

G.arcs[i][j].adj=0;

if(G.kind==DG){

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;

}

else{

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;

}

else{

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){

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;

}

else{

printf("请输入无向网的两个相邻的顶点（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;

}

return OK;

} //创建邻接矩阵

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);

G.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;

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,其中AB与BA是不同的弧）：\n");

for(j=1;j<=2*G.arcnum;j++){

fflush(stdin);

scanf("%c%c",&x,&y);

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->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==DN){

printf("请输入依次输入弧以及这条弧的权值（如AB 8,其中AB与BA是不同的弧）：\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 ;

}

if(G.kind==UDN){

printf("请输入依次输入弧以及这条弧的权值（如AB 8,其中AB与BA是不同的弧）：\n");

for(j=1;j<=2*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 ;

}

return OK;

} //创建邻接表

int FirstAdjVex(ALGraph G,int v){

if(G.vertices[v].firstarc)

return G.vertices[v].firstarc->adjvex;

return 0;

}

int NextAdjVex(ALGraph G,int v,int w){

AList s;

s=G.vertices[v].firstarc;

while(s->adjvex!=w)

s=s->nextarc;

if(s->nextarc)

return s->nextarc->adjvex;

return 0;

}

void DFS(ALGraph G,int v){

int w;

visited[v]=1; printf("%c ",G.vertices[v]);

for(w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w)){

if(!visited[w]) DFS(G,w);

}

void DFSTraverse(ALGraph G){

int v;

visited[0]=1;

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;

InitQueue(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);

for(w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w)){

if(!visited[w]){

visited[w]=1;

printf("%c ",G.vertices[w]);

EnQueue(Q,w);

}

else break;

}

} //图的广度遍历

void FindInDegree(ALGraph G,int in[]){

int i,j,k;AList p;

for(k=1;k<=G.vexnum;k++) in[k]=0;

for(i=1;i<=G.vexnum;i++){

p=G.vertices[i].firstarc;

while(p){

j=p->adjvex;

in[j]++;

p=p->nextarc;

}

} //计算各顶点入度

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);

count=0;

if(StackEmpty(S)) printf("此有向图不符合条件！");

while(!StackEmpty(S)){

Pop(S,i);

printf("%d ",i);

++count;

for(p=G.vertices[i].firstarc;p;p=p->nextarc){

k=p->adjvex;

if(!(--indegree[k])) Push(S,k);

}

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){

if(m[i].lowcost<min){

min=m[i].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<=G.vexnum;j++)

if(j!=k) {

closedge[j].adjvex=u;

closedge[j].lowcost=G.arcs[k][j].adj;

}

closedge[k].lowcost=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++)

if(G.arcs[k][j].adj<closedge[j].lowcost){

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++)

if(!indegree[i]) Push(S,i);

InitStack(T);count=1;for(i=1;i<=G.vexnum;i++) ve[i]=0;

while(!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;

}

if(count<=G.vexnum) return ERROR;

else return OK;

}

int CriticalPath(ALGraph G){

int i,j,k,ee,el,dut,v1[MAX_VERTEX_NUM]; SqStack T; AList p; char tag;

if(!TopologicalOrder(G,T)) return ERROR;

for(i=1;i<=G.vexnum;i++){

v1[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);

}

return OK;

} //求关键路径

void DG_(MGraph 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<=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;

}

printf("\n\n");

} //DG

void DN_(MGraph 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<=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: key=1;break;

}printf("\n");

if(key) break;

}

printf("\n\n");

} //DN

void UDG_(MGraph G1,ALGraph G2){

int i,j,k,m,key;AList s;

for(k=0;;){

key=0;

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++){

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");DFSTraverse(G2);printf("\n");break;

case 4: printf("无向图的广度优先遍历：\n");BFSTraverse(G2);break;

case 5: key=1;break;

}printf("\n");

if(key) break;

}

printf("\n\n");

} //UDG

void UDN_(MGraph G1,ALGraph G2){

int i,j,m,k,key;AList s;char u;

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<=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("请输入第一个顶点：");fflush(stdin);scanf("%c",&u);

printf("无向网的最小生成树：\n");

MinSpanTree_PRIM(G1,u);break;

case 4: key=1;break;

}printf("\n");

if(key) break;

}

printf("\n\n");

} //UDN

void main(){

MGraph G1;

ALGraph G2;

int i,n;

for(i=0;;){

n=0;

printf("********************************\n");

printf("请输入你要进行操作的图类型的编码\n1：有向图\n2：有向网\n3：无向图\n4：无向网\n5: 退出\n");

printf("********************************\n");

printf("请选择：");

scanf("%d",&option);

printf("\n\n");

switch(option){

case 1: DG_(G1,G2);break;

case 2: DN_(G1,G2);break;

case 3: UDG_(G1,G2);break;

case 4: UDN_(G1,G2);break;

case 5: n=1;break;

default: printf("你输入的编码有误！"); break;

}

if(n) break;

printf("\n\n");

}

四、 课设小结：

1.可改进的地方

（1）错误处理机制不完善：程序执行时，必须按照规定的方式输入，一旦未按照规定方式输入，程序就会运行出错，且没有错误提示。可以在此程序的基础之上设计错误处理机制，使程序的使用者更加便捷和可靠。

（2）程序代码冗长：由于本使用的是结构体设计，代码可重用率较低。如果使用面向对象的设计方法，可用到继承的方法，使程序更加简洁，可读性也大大增强。

（3）主程序界面不友好：主程序界面还是简单的dos界面，看上去很不美观。可尝试设计更加美观友好的界面。

2.收获和体会：

一看到课设题目，我就有一种书到用时方恨少的感觉，平时在学习过程中，仅仅只注重于方法上的掌握，对于写程序却显得力不从心。说实话，这次课设的代码大多是对着书本或是网上所查找的资料敲出来的，如果让我在独立不借助参考资料的话，我想我是完成不了这次任务的。当然，在做课设的整个过程除了让我认识到编程能力不足的短处外，还让我深刻体会到，编写程序确实是一件枯燥、艰苦的工作，但当你做出自己想要的东西时，心情却又是无比的愉快。因此，当你在编程时如果遇到无法解决的问题时，很容易灰心丧气，但此时切不可烦躁，一定要静下心来认真分析出错的地方，实在找不出来时可寻求同学或老师帮助，不要轻言放弃，当你做出成绩来时，你会发现之前的努力是值得的。

通过这次课设，我有以下几点体会：

（1）扎实掌握程序语言是编写程序的基础。我反思了这次课设，为什么一些算法我可以轻松地讲出他的工作原理，却写不出任何程序？我想这就是由于我对于编程语言的掌握还不够扎实，我想，以后要花更多的时间学习编程语言，如C++等程序设计语言，这些才是最基础的，必须牢固掌握，这才有利于更好的学习更深层次的语言，写出好程序。

（2）要注重培养实践能力。仅仅熟悉书本上的知识是不够的，软件工程是一门实践性极强的专业，有扎实的程序编写能力和优秀的程序编写思想才是我们的最高目标，才能真正将书本知识运用于实践。这恰恰也是我所缺乏的。

（3）必须培养严谨的态度。自己在编程时经常因为一些小错误而导致程序出错，不够认真细致，这给自己带来许多麻烦，也容易使自己失去信心。例如我在编写队列的操作时，将指针的内存分配类型弄错了，整整花了我两天的时间才找出错误。编程是一件十分严谨的事，容不得马虎。所以，今后自己一定要培养严谨的治学态度。我想，这不仅是对于程序设计，做任何事都应如此。

（4）

指导老师意见：

成绩: 教师签名：

年月日

相关推荐

12数据结构课程设计报告

专栏推荐