课程设计_最短路径算法

沈阳航空航天大学

课程设计报告

课程设计名称：数据结构课程设计课程设计题目：最短路径算法

院（系）：计算机学院

专业：计算机科学与技术

班级：94010105

学号：2009040101133

姓名：

指导教师：

目录

1 课程设计介绍 (1)

1.1课程设计内容 (1)

1.2课程设计要求 (1)

2 课程设计原理 (2)

2.1课设题目粗略分析 (2)

2.2原理图介绍 (3)

2.2.1 功能模块图 (3)

2.2.2 流程图分析 (3)

3 数据结构分析 (8)

3.1存储结构 (8)

3.2算法描述 (8)

4 调试与分析 (9)

4.1调试过程 (9)

4.2程序执行过程 (9)

参考文献 (11)

附录（关键部分程序清单） (12)

1 课程设计介绍

1.1 课程设计内容

设计程序，实现最短路径的求法，系统主要功能如下：

1.编写算法能够建立带权图，并能够用Dijkstra算法求该图的最短路径。

2.能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图形方式，可顶点序列方式输出。

1.2 课程设计要求

1.带权图的顶点信息用字符串，数据可自定。

2.参考相应的资料，独立完成课程设计任务。

3.较规范课程设计报告和软件代码。

2 课程设计原理

2.1 课设题目粗略分析

根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：

1.建立有向图的存储结构.

2.应用Dijkstra算法求出该有向图的最短路径。

3.在主函数中调用上面两个子函数，完成求最短路径的程序设计。

4.

2.2 原理图介绍

2.2.1 功能模块图

图2.1 功能模块图

2.2.2 流程图分析

1. 主函数

2.2主函数流程图 2. Create 函数

2.3Create函数流程图

3.Dijkstra函数

2.4Dijkstra函数流程图

3 数据结构分析

3.1 存储结构

一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下:

#define MVNum 50

typedef struct {

VertexType vexs[MVNum];

Adjmatrix arcs[MVNum][MVNum]；

}Mgraph;

3.2 算法描述

1. Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。

迪杰斯特拉算法可用自然语言描述如下：

初始化S和D,置空最短路径终点集，置初始的最短路径值；

S[v1]=TRUE;D[v1]=0;

While(S集中的顶点数

{

开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中;

S[v]=TRUE; 更新当前最短路径及距离。

}

2Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。

4 调试与分析

4.1 调试过程

在调试程序是主要遇到一下几类问题：

1.程序完成后，调试时没有发现问题，但是当输入开始节点后，运行框却不停的

出现”<-a”,后来重新检查程序时发现for循环的括号后面多了一个”;”，去掉该分号之后，程序可以运行。

2.程序可以运行，但是输出结果不是有序的，解决方法，设立一个前驱数组，用

以记录节点的双亲节点，然后按照倒叙的方式读出该条最短路径的有向序列。

4.2程序执行过程

4.1程序执行过程

4.2程序执行过程

参考文献

[1] 《数据结构》（用面向对象方法与C++描述），殷人昆等，清华大学出版社， 2010年3月。

[2] 《算法与数据结构习题精解和实验指导》，宁正元等，清华大学出版社，

2009年6月。

[3] 《数据结构课程设计》，苏仕华等，机械工业出版社，2010年3月。

[4]《C程序设计》，谭浩强编，清华大学出版社，2006年6月。

附录（关键部分程序清单）程序代码

#include

#include

#define MVNum 100

#define Maxint 32767

typedef char VertexType;

typedef int Adjmatrix;

typedef enum {FALSE,TRUE}boolean;

typedef struct {

VertexType vexs[MVNum];

Adjmatrix arcs[MVNum][MVNum];

}MGraph;

int D1[MVNum],P1[MVNum];

int D[MVNum][MVNum],P[MVNum][MVNum];

void CreateMGraph(MGraph *G,int n,int e)

{

int i,j,k,w;

char a,b;

for(i=1;i<=n;i++)

G->vexs[i]=i;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

G->arcs[i][j]=Maxint;

printf("输入%d条边的i,j及w:\n",e);

for(k=1;k<=e;k++)

{

fflush(stdin);

scanf("%c,%c,%d",&a,&b,&w);

i=a-'a'+1;

j=b-'a'+1;

G->arcs[i][j]=w;

}

printf("有向图的存储结构建立完毕!\n");

}

void Dijkstra(MGraph G,int v1,int n)

{

int D2[MVNum],P2[MVNum];

int v,i,w,min;

boolean S[MVNum];

for(v=1;v<=n;v++)

{

S[v]=FALSE;

D2[v]=G.arcs[v1][v];

if(D2[v]

P2[v]=v1;

else

P2[v]=0;

}

D2[v1]=0;S[v1]=TRUE;

for(i=2;i<=n;i++)

{

min=Maxint;

for(w=1;w<=n;w++)

if(!S[w]&&D2[w]

{

v=w;min=D2[w];

}

S[v]=TRUE;

for(w=1;w<=n;w++)

if(!S[w]&&(D2[v]+G.arcs[v][w]

{

D2[w]=D2[v]+G.arcs[v][w];

P2[w]=v;

}

}

printf("路径长度路径\n");

for(i=1;i<=n;i++)

{

printf("%5d",D2[i]);

printf("%5c",i-1+'a');v=P2[i];

while(v!=0)

{

printf("<-%c",v-1+'a');

v=P2[v];

}

printf("\n");

}

}

void main()

{

MGraph G;

int n,e,v;

char ch;

printf("输入图中顶点个数和边数n,e:");

scanf("%d,%d",&n,&e);

CreateMGraph(&G,n,e);

while(1)

{

printf("求最短路径，输入开始点v:");

fflush(stdin);

scanf("%c",&ch);

v=ch-'a'+1;

Dijkstra(G,v,n);

}

}

沈阳航空航天大学课程设计报告

数据结构,课程设计,校园最短路径问题

一、课程设计题目：校园最短路径问题 二、课程设计目的： 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具备的科学工作方法和作风。 三、课程设计要求： 1.设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。 2.编写出课程设计报告书，内容不少于10页（代码不算）。 四、需求分析： 1、问题描述 图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。 校园最短路径问题中的数据元素有： a) 顶点数 b) 边数 c) 边的长度 2、功能需求 要求完成以下功能： a)输出顶点信息：将校园内各位置输出。 b)输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的 距离输出。 c)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输 出每两个位置（若两个位置之间有直接路径）的距离。 d)求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出 任意一点与其它各点的最短路径。 e)删除：删除任意一条边。 f)插入：插入任意一条边。 3、实现要点 a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。 为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。 b) 为了便于访问，用户可以先输出所有的地点和距离。 c) 用户可以随意修改两点之间好的距离。 d) 用户可以增加及删除边。 e) 当用户操作错误时，系统会出现出错提示。 五、概要设计:

关键路径问题报告

滁州学院 课程设计报告 课程名称：数据结构 设计题目：关键路径问题 院部：计算机与信息工程 专业：网络工程 组别：第六组 起止日期:2012年4月9日~2012年6月24日指导教师:赵玉艳 计算机与信息工程学院二○一二年制

课程设计题目关键路径问题 组长柯焱芳学号2011211384 班级网工113班院部计算机工程系专业网络工程 组员靳梦婷李鹏飞陆勇刘宜雨 指导教师赵玉艳 课程设计目的1．巩固和加深学生对数据结构课程基本知识的理解，综合该课程中所学的理论知识，独立或联合完成一个数据结构应用课题的设计； 2．根据选题需要，通过查阅手册和文献资料，培养分析和解决实际问题的能力； 3．熟练掌握图的各种基本数据结构的定义、存储结构和相应的算法，并可熟练利用c语言进行实现； 4．具有一定的算法设计和分析能力，掌握选用合适的数据结构解决实际问题的方法； 5．学会撰写课程设计报告，能做出简单答辩； 6．培养严肃认真的工作作风和严谨求实的科学态度。 课程设计所需环境 ⑴实验设备：PC机⑵操作系统：Windows XP ⑶开发环境：Visio C++6.0 课程设计任务要求要求学生理解图的特征和性质，掌握各类图的存储结构、相关操作的程序实现以及图的应用，能够利用图的遍历、图的最小生成树、最短路径、关键路径、拓扑排序等原理解决实际问题。 课程设计工作进度计划 序号起止日期工作内容分工情况 1 4.09-4.16 选题与分析课题内容， 查找资料柯焱芳：选题与分析课题内容 陆勇靳梦婷李鹏飞刘宜雨：查找资料 2 4.17-4.25 编写创建图，求最大路 径的函数刘宜雨靳梦婷：创建图李鹏飞陆勇：求最大路径 3 4.26- 5.16 编写总代码和主函数 （求关键路径） 柯焱芳：编写总代码和主函数（求关键路径） 4 5.17-5.2 5 对程序输入改写柯焱芳靳梦婷：对程序输入改写 5 5.26-6.10 对程序进行测试柯焱芳靳梦婷刘宜雨陆勇李鹏飞 6 6.11-6.24 整理文档与总结柯焱芳陆勇 指导教师签字：年月日院（系）审核意见 院长（主任）签字：年月日

数据结构课程设计报告Dijkstra算法求最短路径

中南大学 《数据结构》课程设计 题目第9题 Dijkstra算法求最短路径 学生姓名 XXXX 指导教师 XXXX 学院信息科学与工程学院 专业班级 XXXXXXX 完成时间 XXXXXXX

目录 第一章问题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra算法实现最短路径--------------------------------------------------------------10 第四章上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章测试结果-----------------------------------------------------------------------------------12 第六章学习心得体会-----------------------------------------------------------------------------12 第七章参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12

关键路径问题设计与实现

《数据结构的课程设计》 报告 题目：关键路径问题设计与实现班级：1612401 学号：161240113 姓名：张修鸣 指导老师：孙涵 完成日期：2014.1.3

目录 一.需求分析. 二.程序主要功能. 三.程序运行平台. 四.程序类说明. 五.模块分析. 六.存在的不足与对策. 七．体验感悟 八.程序源代码.

需求分析 设计并实现关键路径的一种应用。 程序主要功能 （1）实现拓扑排序和关键路径的发现。 （2）给出一个具体的应用环境。 程序运行平台 该程序是用VC++6.0制做的，使用Microsoft Visual C++ 6.0运行该程序，具体操作是：打开Microsoft Visual C++ 6.0，菜单栏里点文件→打开工作区→找到“图书管理系统.dsw”这个文件→打开，或者在资源管理器中双击该文件，此时，VC++6.0会自动打开，并载入该系统相关资源，点击Run命令菜单或者或用快捷键Ctrl+F5运行该程序。 程序类说明 typedef struct node{ int adjvex; //邻接点域 int time;//活动持续时间 struct node *next; }Node; Node *p; typedef struct VertexNode{ int vertex; //顶点域 int indegree; //入度域 Node *firstedge; //边表头指针 }AdjList[20]; typedef struct{ AdjList adjlist;//邻接表 int Dian;//顶点数

int Bian; //边数 }ALGraph 函数分析： void CreateALGraph(ALGraph *&G) //建立有向图 int TopoSort(ALGraph *G,int s[20],int ve[20]) //拓扑排序并求各顶点事件的最早发生时间及拓扑逆序列 int CriticalPath(ALGraph *G)//求关键路径和关键活动 模块分析 文件的信息 关键活动与关键路径 存在的不足与对策 由于自身能力有限，所以没有设计好交互界面。 在设计过程中由于设计者的编程功底欠缺，因此学习过程较为艰辛，需要解决的问题也比较多。在以后的学习中，应该循序渐进，不可急于求成，先打好基础，这样才能更好地发展。

《数据结构课程设计》最短路径问题实验报告

《数据结构课程设计》最短路径问题实验报告

目录 一、概述 0 二、系统分析 0 三、概要设计 (1) 四、详细设计 (5) 4.1建立图的存储结构 (5) 4.2单源最短路径 (6) 4.3任意一对顶点之间的最短路径 (7) 五、运行与测试 (8) 参考文献 (11) 附录 (12)

交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

三、概要设计 可以将该系统大致分为三个部分： ①建立交通网络图的存储结构； ②解决单源最短路径问题； ③实现两个城市顶点之间的最短路径问题。

迪杰斯特拉算法流图：

栈的课程设计完整版

唐山学院 数据结构课程设计 题目栈的基本操作及其应用 系 (部) 计算机科学与技术系 班级 16计本（2） 姓名周登旺 学号 4164001232 指导教师郭琳虹 2018 年 1 月8日至2018 年1 月12日共1 周

数据结构课程设计任务书

课程设计成绩评定表

1.引言 在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。首先系统或者数据结构栈中数据内容的读取与插入（压入push和弹出pop）是两回事！插入是增加数据，弹出是删除数据，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作，但读取栈中的数据是随便的没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用即cpu与内存的交流通道，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令，用一个形象的词来形容它就是pipeline（管道线、流水线）。cpu内部交互具体参见EU与BIU的概念介绍。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。栈可以用来在函数调用的时候存储断点，做递归时要用到栈！ 一、基本概念 栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。 栈是一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）,栈可以用来在函数调用的时候存储断点，做递归时要用到栈！ 本课程设计涉及的主要内容是对栈进行基本操作和实现栈的一些实际应用，在课程设计中，系统开发平台为Windows 7。程序设计语言使用Visual c++。程序的运行平台为Windows 2000/XP/7/10。 /* 2问题分析 本次课程设计主要介绍栈的概念和栈的基本操作和栈的两种存储结构及其应用。其中栈的基本操作主要包括置空栈，判断栈空，进栈，出栈，取栈顶元素。栈的两种存储

数据结构课程设计报告_最短路径C++

青岛理工大学琴岛学院 设计报告 课题名称：求解最优交通路径 学院：计算机工程系 专业班级：计算机科学与技术 学号：####### 学生：** 指导教师：** 青岛理工大学琴岛学院教务处 2011 年 7 月 7日

图1 B.具体功能实现及相应的弗洛伊德算法 首先,建立查询信息对话框，使用户能够录入需要查询的城市代号，并显示路径长度及最短路径沿途经过的城市。并相应地添加如下变量int m_v0;int m_v1;int m_lj;CString m_zd; 具体代码如下： #define MAXV 25 //最大顶点个数 #define INF 32767 //用32767表示∞ //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 char name[10]; //顶点名称 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int vexnum,arcnum; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 1.通过函数CreatUDN()存放城市路径信息，输入顶点之间的路径长度，创建带权图的邻接矩阵。 void CTDialog::CreatUDN() { MGraph *g=(MGraph*)malloc(sizeof(MGraph)); int i,j; for(i=0;iedges[i][j]=INF; if(i==j)g->edges[i][j]=0; //初始化置任意两城市之间距离为无穷大，即两城市之间没有直接通路

关键路径的查找实验报告

中国矿业大学矿业工程学院 实验报告 课程名称计算机软件设计基础 姓名 xxxx 班级采矿10-8班学号 xxxxx 日期 2012年10月 成绩教师 xxxx

3．2算法步骤：

(1)输入e条弧，建立AOE网的存储结构。 (2)从源点v1出发，令ve(1)=0,求ve(j)，2<=j<=n。 (3)从汇点vn出发，令vl(n)=ve(n),求vl(i) 1<=i<=n-1。 (4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。 总结 首先，关于程序方面，我发现即使对设计思路有了眉目，知道了所要用到的数据结构、用邻接表来存储AOE-网、建立栈来求拓扑序列、输出的拓扑序列的个数少于节点数则有回路等等，要把这些方法写成函数代码，其实还是一件非常不容易的事情。再加上要完善设计思路，构造整个程序框架在内，都是一件工作量非常大的工作。 在处理程序代码的时候，有两个问题始终解决不了。一是程序输入时只能输入整形数据，而非整形的输入则会导致程序异常停止，但是因为整形的输入方式已贯穿整个程序，若要修改只能另外重做整个程序，所以暂不考虑修改，而打算做一个判错系统，判断若非整形的输入则报错；二是第一种错误的解决方案未能成功实行，于网路上搜索到了几种判断是否为整形数据的程序代码，但将其修改融合到求关键路径的程序中，虽然没有错误可以运行，但是却不能正确的报错。 于是，在尝试多种方案却仍不成功的前提下，我只好选择加上提示语，即：printf("请输入某项目的信息，并请用整形数字表示（格式：弧头，

数据结构课程设计：拓扑排序和关键路径复习进程

数据结构课程设计：拓扑排序和关键路径

1 ABSTRACT 1.1图和栈的结构定义 struct SqStack////栈部分 { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的大小 int element_count;//栈中元素个素 }; /////////AOE网的存储结构 struct ArcNode //表结点 { int lastcompletetime;//活动最晚开始时间 int adjvex; //点结点位置 int info; //所对应的弧的权值 struct ArcNode *next;//指向下一个表结点指针 }; struct VNode //点结点 { VertexType data; //结点标志 int indegree; //该结点入度数 int ve; //记录结点的最早开始时间 int vl; //记录结点的最晚开始时间 struct ArcNode *first_out_arc; //存储下一个出度的表结点struct ArcNode *first_in_arc;//存储下一个入度的表结点 }; struct ALGraph

{ VNode *vertices; //结点数组 int vexnum; //结点数 int arcnum; //弧数 int kind; //该图的类型 }; 2系统总分析 2.1关键路径概念分析 2.1.1什么是关键路径 关键路径法(Critical Path Method, CPM)最早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（Critical Path），组成关键路径的活动称为关键活动。 2.1.2关键路径特点 关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。 关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。

数据结构课程设计题目(最终版)-2011

数据结构课程设计题目 2012-1 1、医务室模拟。（5人） 问题描述：假设只有一位医生，在一段时间内随机地来几位病人；假设病人到达的时间间隔为0~14分钟之间的某个随机值，每个病人所需处理时间为1~9分钟之间的某个随机值。试用队列结构进行模拟。 实现要求：要求输出医生的总等待时间和病人的平均等待时间。 程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有一位病人到达，则这些病人应依次排队，等候就诊。 2、招聘模拟（5人） 问题描述：某集团公司为发展生产向社会公开招聘m个工种的工作人员，每个工种各有不同的编号（0，1，2，…，m-1）和计划招聘人数，参加招聘的人数有n个（编号为0，1，2，。。。，n-1）。每位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩，从高到低的顺序排队录取。公司的录取原则是：从高分到低分依次对每位应聘者按其第一志愿录取；当不能按第一志愿录取时，便将他的成绩扣去5分后，重新排队，并按其志愿考虑录取。 程序为每个工种保留一个录取者的有序队列。录取处理循环直至招聘额满，或已对全部应聘者都做了录用处理。 实现要求：要求程序输出每个工种录用者的信息（编号、成绩），以及落选者的信息（编号、成绩）。 3、组织机构问题（5人） 问题描述：以物资学院为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求： （1）树中每个结点保存部门名称； （2）假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？ （3）软件可以查询某部门下面的具体编制？ 4、最少换车次数问题（5人） 问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0~n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。 实现要求：求得从站0出发乘公交车至站n-1的最少换车次数。 设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边，权值为1。因此，从站x至站y的最少上车次数对应于图G中从顶点x到顶点y的最短路径长度。 5、职工工作量统计（5人） 问题描述：采用随机函数产生职工的工号和他所完成产品个数的数据信息，对同一职工多次完成的产品个数进行累计，按职工完成产品数量的名次、该名次每位职工完成的产品数量、同一名次的职工人数和他们的职工号格式输出。

实验四图的最短路径弗洛伊德算法实现

数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：I09630221

实验四图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题描述 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量

AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #include #include using namespace std; #define INfinity 10000//最大值 # define MAX_VERTEX_NUM 10//最大顶点数 typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info; }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; int Locate(MGraph &G,string v) { int a=0; for (int i=0;i

数据结构课程设计关键路径

数据结构课程设计-关键路径 #define max 20 #include #include #include using namespace std; typedef struct ArcNode//定义表结点 {int adjvex;//该弧所指向顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 int info;//该弧的权值 }ArcNode; typedef struct VNode//定义头结点 {int data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[max]; typedef struct//定义ALGraph {AdjList vertices; int vexnum,arcnum;//图的当前顶点数和弧数 int kind;//图的种类标志 }ALGraph; typedef struct//定义栈 {int *base;//栈底 int *top;//栈顶

}stack; void initstack(stack &s)//建立空栈{s.base=(int*)malloc(max*sizeof(int)); s.top=s.base; } int stackempty(stack s)//判断是否为空栈{if(s.base==s.top) return 1; else return 0; } int stackfull(stack s)//判断是否为满栈{if(s.top-s.base>=max) return 1; else return 0; } int pop(stack &s)//进行出栈 {int e;//出栈先进行赋值，后移动指针if(!stackempty(s)) {e=*(s.top-1); s.top--; return e; } else return NULL; }

最短路径算法实验报告

东华大学计算机学院离散数学 实验五：最短路径 实验所属系列：离散数学课后实验 实验对象：本科 相关课程及专业：离散数学，计算机专业 实验类型：课后实验 实验时数（学分）：4学时 实验目的 学习图的最短路径算法的实现。 实验内容与要求 根据输入的图形（实验四），输入起点和终点，求出最短路径和最短路径的长度。 实验的软硬件环境 PC机一台，装有VC++6.0或其它C语言集成开发环境。 实验准备 熟悉最短路径算法。 实验步骤 1．编写一段代码，接收键盘的输入定点的数量，并以输入的整数对作为边来建立图形的邻接矩阵（无向权重图）。 例如：5，6，12 表示定点5和定点6间有边，边的权重为12。 2 打印出邻接矩阵。 3．输入起点和终点。 4、打印最短路径和最短路径的长

#include #define BIG 9999 void dijkstra(int cost[][6],int n,int st,int distance[]) { int s[6]; int mindis,dis; int i,j,u; for(i=0;i

数据结构课程设计——关键路径

《数据结构》课程设计报告 课程题目：关键路径 学院： 班级： 学号： 姓名： 指导教师： 完成日期：

目录 一、需求分析 ............................... 错误!未定义书签。 二、概要设计 ............................... 错误!未定义书签。 三、详细设计 ............................... 错误!未定义书签。 四、调试分析 .............................. 错误!未定义书签。 五、用户使用说明 ...................... 错误!未定义书签。 六、测试结果 .............................. 错误!未定义书签。 七、附录 ..................................... 错误!未定义书签。

一、需求分析 1、问题描述 AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。它可以使人们了解：（1）研究某个工程至少需要多少时间（2）哪些活动是影响工程进度的关键在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。 2、设计步骤 （1）、以某一工程为蓝本，采用图的结构表示实际的工程计划时间。 （2）、调查并分析和预测这个工程计划每个阶段的时间。 （3）、用调查的结果建立AOE网，并用图的形式表示。 （4 ）、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。 （5）、用SearchMaxPath()函数求出最大路径，并打印出关键路径。 （6）、编写代码并调试、测试通过。 3、测试数据 ○v2○v5 ○v1○v4○v6 ○v3 6 v1 v2 v3 v4 v5 v6 8 v1 v2 a1 3 v1 v3 a2 2 v2 v4 a3 2 v2 v5 a4 3 v3 v4 a5 4 v3 v6 a6 3 v4 v6 a7 2 v5 v6 a8 1

课程设计--最短路径：拯救007

《数据结构课程设计》报告 最短路径—拯救007 专业 xxxxxx 学生姓名 xxxx 班级 xxxx 学号 xxxx 指导教师 xxxxx 完成日期 xxxxxx

目录 一、简介 (3) 二、算法说明 (4) 三、测试结果 (7) 参考文献 (14)

一、简介 最短路径是，在一个图中，若从一个顶点到另一个顶点存在着一条路径（这里只讨论无回路的简单路径），则称该条路径长度为为该路径上所有经过的边的数目，它也等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在着多条路径，在每条路径上所经过的边数可能不同，把路径长度最短（经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短距离。这是对无权图而言的，若图是帯权图，则把从一个顶点vi到vj的一条路径上所有经过边的权值之和定义为该路径的带权路径长度。把带权路径长度最短的那条路径称为该有权图的最短路径，其路径长度称为最短距离。 Dijksra算法：如何求解从一个顶点到其余每个顶点的最短路径呢？狄克斯特拉于1959年提出了解决此问题的一种按路径长度的递增次序产生最短路径的算法。基本思想是，从图中给定源点到其他各个顶点之间客观上应个存在一条最短路径，在这组最短路径中，按其长度的递增次序求出到不同顶点的最短路径和路径长度。 图是一种较线性结构和树形结构更为复杂的非线性数据结构，这种复杂性主要来自数据元素之间的复杂关系。在图结构中，任何两个数据元素之间都可能存在关系，一般用顶点表示数据元素，而用顶点之间的连线表示数据元素之间的关系。图的二元组定义为：G=(V,E)。其中V是非空的顶点集合，E是V上的二元关系集合。 题目内容： 看过007系列的电影的人们一定很熟悉Jams Bond这个世界上最著名的特工了。在电影“Live And Let Die”中Jams Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时Jams Bond做出了一个最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反映过来的时候，他有跳到另一支鳄鱼的头上.。。。。。。最后他终于安全地跳到了湖岸上。 假设湖是100*100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆环小岛的圆心在（0，0），直径是15.。一些凶残的鳄鱼分布在湖中不同的位置。现已知的湖中的鳄鱼的位置和Jams Bond可以跳的最大距离，请你告诉Jams Bondyitiao 最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。

A算法的改进课程设计

沈阳大学

Floyd-Warshall算法的描述如下： for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if (Di,k + Dk,j < Di,j) then Di,j ← Di,k + Dk,j; 其中Di,j表示由点i到点j的代价，当Di,j为∞表示两点之间没有任何连接。 （2）Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。 当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。 （3）Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。 Bellman-Ford算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。而Bellman-Ford算法具有分辨这种负环路的能力。A*（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。公式表示为：f(n)=g(n)+h(n),其中f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：

数据结构课程设计汇本：拓扑排序和关键路径

1 ABSTRACT 1.1图和栈的结构定义 struct SqStack////栈部分 { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的大小 int element_count;//栈中元素个素 }; /////////AOE网的存储结构 struct ArcNode //表结点 { int lastcompletetime;//活动最晚开始时间 int adjvex; //点结点位置 int info; //所对应的弧的权值 struct ArcNode *next;//指向下一个表结点指针 }; struct VNode //点结点 { VertexType data; //结点标志 int indegree; //该结点入度数 int ve; //记录结点的最早开始时间 int vl; //记录结点的最晚开始时间 struct ArcNode *first_out_arc; //存储下一个出度的表结点 struct ArcNode *first_in_arc;//存储下一个入度的表结点}; struct ALGraph { VNode *vertices; //结点数组 int vexnum; //结点数 int arcnum; //弧数 int kind; //该图的类型 };

2系统总分析 2.1关键路径概念分析 2.1.1什么是关键路径 关键路径法(Critical Path Method, CPM)最早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（Critical Path），组成关键路径的活动称为关键活动。 2.1.2关键路径特点 关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。 关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。 关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会缩短项目工期；反之，则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间，也不至于影响工程的完工时间。 关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使关键路径发生变化。可以存在多条关键路径，它们各自的时间总量肯定相等，即可完工的总工期。 关键路径是相对的，也可以是变化的。在采取一定的技术组织措施之后，关键路径有可能变为非关键路径，而非关键路径也有可能变为关键路径。 2.2关键路径实现过程 2.2.1结构选取 首先要选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各