【数据结构算法】实验8 图的最短路径问题(附源代码)
浙江大学城市学院实验报告
课程名称数据结构与算法
实验项目名称实验八图的最短路径问题
实验成绩指导老师（签名）日期
一.实验目的和要求
1.掌握图的最短路径概念。
2.理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。
二. 实验内容
1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括：
①初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrix G);
②建立邻接矩阵表示的有向带权图void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）;
③输出邻接矩阵表示的有向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。
把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。2、编写求最短路径的DijKstra算法函数void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组path 和dist 中。编写打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist[], edgenode *path[], int n)。
3、编写测试程序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点v0到其余各顶点的最短路径。
要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件
test9_2.cpp中。
测试数据如下：
4、填写实验报告，实验报告文件取名为report8.doc。
5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。
三. 函数的功能说明及算法思路
包括每个函数的功能说明，及一些重要函数的算法实现思路
【结构说明】
const int MaxVertexNum=10; //图的最大顶点数
const int MaxEdgeNum=100; //边数的最大值
const int MaxValue=32767; //权值的无穷大表示
typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵
typedef struct Node {
int adjvex;
struct Node *next;
} edgenode; //路径结点
【函数说明】
①void InitMatrix(adjmatrix &G)
功能：初始化邻接矩阵表示的有向带权图
思路：将邻接矩阵中的所有权值设置为无穷大（MaxValue）
②void CreateMatrix(adjmatrix &G, int n)
功能：建立邻接矩阵表示的有向带权图（即通过输入图的每条边建立图的邻接矩阵）
思路：按照输入的顶点信息和权值信息，更新邻接矩阵内对应的值
③void PrintMatrix(adjmatrix G, int n)
功能：输出邻接矩阵表示的有向带权图（即输出图的每条边）
思路：按照一定的格式输出邻接矩阵
④void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n)
功能：求最短路径的DijKstra算法函数
思路：按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度。设立一个集合S，用以保存已求得最短路径的终点，其初值为只有一个元素，即源点；一个数组dist[n]，其每个分量dist[j] 保存从源点经过S集合中顶点最后到达顶点j 的路径中最短路径的长度，其初值为从源点到每个终点的弧的权值（没弧则置为∞）；一个指针数组path[n]，path[j]
指向一个单链表，保存相应于dist[j]的从源点到顶点j 的最短路径（即顶点序列），初值为空。
⑤void PATH(edgenode *path[], int i, int j)
功能：将path[i]的路径改为path[j]的路径+i
思路：分为三个步骤：一，删除path[i]中原来保存的链表；二，将path[j]的路径复制给path[i]；三，将j结点加入path[i]的路径中
⑥void PrintPath(int dist[], edgenode *path[], int n){
功能：打印输出从源点到每个顶点的最短路径及长度的函数
思路：按照一定的格式遍历输出从源点到每个顶点的最短路径及长度
四. 实验结果与分析
包括运行结果截图等
【测试数据】
顶点数：7
输入弧的信息：
正确的邻接矩阵应为：
下面以测试数据为基准，给出DijKstra 算法生成最短路径的状态变化图： （※注：顶点旁边的
【状态①】
【状态②】
【状态③】 【状态④】
【状态⑤】 【状态⑥】
【状态⑦(最短路径)】
五. 心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
【附录----源程序】
[Test9_2.cpp]
#include
#include
#include
#include
#include"Graph2.h"
typedef struct Node {
int adjvex;
struct Node *next;
} edgenode;
void main(){
int n;
adjmatrix G;
edgenode *path[MaxVertexNum];
int dist[MaxVertexNum];
void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n);
void PrintPath(int dist[], edgenode *path[], int n);
InitMatrix(G);
printf("输入要构造的图顶点数\n");
scanf("%d",&n);
CreateMatrix(G,n);
PrintMatrix(G,n); //打印图的邻接矩阵
cout< **************"< Dijkstra(G, dist, path, 0, n); PrintPath(dist,path,n); } //求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n){ int j,k; int v = 1,minIndex; void PATH(edgenode *path[], int i, int j); bool *isStepped; //初始化部分 //isStepped：申请n个空间，除i以外均为false //dist：邻接矩阵中i顶点到各顶点的距离 //path：邻接矩阵中i顶点到各顶点若有路径，则保存；无路径置为NULL isStepped = new bool[n]; for (j = 0; j < n; j++){ dist[j] = GA[i][j]; if (dist[j] != MaxValue && j!=i){ path[j] = new edgenode; path[j]->adjvex = i; path[j]->next = new edgenode; path[j]->next->adjvex = j; path[j]->next->next = NULL; } else path[j] = NULL; isStepped[j] = false; } isStepped[i] = true; while(v <= n){ //尝试查找当前最小路径结点，用minIndex保存顶点 minIndex = i; for (k = 0; k < n; k++){ if (dist[k] < dist[minIndex] && (!isStepped[k])) minIndex = k; } //有查找到最小路径顶点，则将其并入集合 if (minIndex != i) isStepped[minIndex] = true; //未查找到，则说明路径都为∞，退出 else break; //通过while中确定的最小路径顶点（minIndex）到达当前顶点 //若路径长度小于dist中保存的路径长度，则修改 for (k = 0; k < n; k++){ if (GA[minIndex][k] + dist[minIndex] < dist[k]){ dist[k] = GA[minIndex][k] + dist[minIndex]; PATH(path, k, minIndex); } } v++; } } //将path[i]的路径改为path[j]的路径+i void PATH(edgenode *path[], int i, int j){ edgenode *p, *q, *t; //删除path[i]中原来保存的链表 while(path[i] != NULL){ p = path[i]->next; delete path[i]; path[i] = p; } //将path[j]的路径复制给path[i] p = new edgenode; p->adjvex = path[j]->adjvex; path[i] = p; t = path[j]->next; while (t != NULL){ q = p; p = new edgenode; p->adjvex = t->adjvex; q->next = p; t = t->next; } //将j结点加入path[i]的路径中 q = p; p = new edgenode; p->adjvex = i; p->next = NULL; q->next = p; } //打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist[], edgenode *path[], int n){ int i; edgenode *p; for (i = 1; i < n; i++){ cout<<"[ v0 -> v"< cout<<"最短路径："; p = path[i]; if (p == NULL){ cout<<"无路径！"< continue; } while( p != NULL){ cout<<"v"< p = p->next; } cout< } } [Graph2.h] const int MaxVertexNum=10; //图的最大顶点数 const int MaxEdgeNum=100; //边数的最大值 const int MaxValue=32767; //权值的无穷大表示 typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵 //①初始化邻接矩阵表示的有向带权图 void InitMatrix(adjmatrix &G) { int i,j; for (i=0; i for (j=0; j G[i][j]=MaxValue; } //②建立邻接矩阵表示的有向带权图（即通过输入图的每条边建立图的邻接矩阵） void CreateMatrix(adjmatrix &G, int n) { int v, w, q; printf("按照：尾顶点名->头顶点名，权值输入数据，以0->0,0结尾:如A->B,23 \n"); while(true){ //构造邻接矩阵 scanf("%d->%d,%d",&v,&w,&q); //输入弧的两个定点及该弧的权重 getchar(); if (v == 0 && w == 0 ) break; if( v < 0 || v >= n || w < 0 || w >= n) {cerr<<"vertex ERROR!";exit(1);} G[v][w]=q; } } //③输出邻接矩阵表示的有向带权图（即输出图的每条边）void PrintMatrix(adjmatrix G, int n) { int i,j; cout< cout<<"Your Graph is:"< for (i=0; i for (j=0; j if(G[i][j]!=MaxValue) printf(" %2d | ",G[i][j]); else printf(" ∞| "); } printf("\n"); } } 二叉树 1 题目 编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（b 为如图示的一棵二叉树）： 输出二叉树b; 输出‘H’节点的左、 右孩子结点值; 输出二叉树b的深度; 输出二叉树b的结点个数; 输出二叉树b的叶子结点个数。 2 目标 熟悉二叉树的定义及其基本操作的实现 3 设计思想 二叉树的每个结点都有指向其左右孩子的指针，对二叉树的表示可以有很多方法，这里采用中序的带括号表示法，以字符串形式读入输出。建立存储结构的时候，从根结点开始，赋值定义其左右指针，由于二叉树的每个结点操作类似，因此可以采用递归的方法。 4 算法描述 （1）输入建立二叉树：读入字符串，根据括号表示法的规则，a（b,c）的括号中左右元素表示结点的左右子树结点，若结点是树（括号中还有括号），则再调用改操作，直至结点全部读入。 （2）输出二叉树：从根结点开始，打印根结点数据，如果结点的左右孩子指针不为空，就打印左括号，并按先左后右的次序调用此操作，最后输出右括号完成括号表示。 （3）输出二叉树的深度：从根结点开始，如果左或右孩子不是树的话返回深度加一，否则继续调用此操作，直到完全返回(返回深度是左、右深度中的最大值)。 （4）输出二叉树叶子结点数：从根结点开始，用ln和r n分别表示结点左右叶子结点数，函数返回叶子结点数之和，递归调用该函数，直到左右指针指空。 （5）输出二叉树结点数：结点数即是叶子数加一。 5 程序结构图 6 源程序 typedef struct node{ char data; struct node *lchild; struct node *rchild; }*Bitree; Bitree bt; void CreateBitree(Bitree &bt,char *str){ Bitree St[100],p=NULL;//100个结点的二叉树 int top=-1,k,j=0; char ch; bt=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break; case')':top--;break; case',':k=2;break; default:p = (struct node*)malloc(sizeof(struct node)); p->data=ch;p->lchild=p->rchild=NULL; if (bt==NULL)//是根结点 bt=p; else//是叶子结点 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 山东建筑大学测绘地理信息学院 实验报告 （2016—2017学年第一学期） 课程：计算机图形学 专业：地理信息科学 班级：地信141 学生姓名：王俊凝 学号：20140113010 指 实验一直线生成算法设计 一、实验目的 掌握基本图形元素直线的生成算法，利用编程语言C分别实现直线和圆的绘制算法。 二、实验任务 在TurboC环境下开发出绘制直线和圆的程序。 三、实验仪器设备 计算机。 四、实验方法与步骤 1 运行TurboC编程环境。 2 编写Bresenham直线绘制算法的函数并进行测试。 3 编写中点圆绘制算法的函数并进行测试。 4 增加函数参数，实现直线颜色的设置。 提示： 1. 编程时可分别针对直线和圆的绘制算法，设计相应的函数，例如void drawline(…)和void drawcircle(…)，直线的两个端点可作为drawline的参数，圆的圆心和半径可作为drawcircle的参数。 2. 使用C语言编写一个结构体类型用来表示一个点，结构体由两个成员构成，x和y。这样，在向函数传入参数时，可使用两个点类型来传参。定义方法为： typedef struct{ int x; int y; }pt2; 此处，pt2就是定义的一个新的结构体数据类型，之后就可用pt2来定义其他变量，具体用法见程序模板。 3. 在main函数中，分别调用以上函数，并传入不同的参数，实现对直线的绘制。 4. 线的颜色也可作为参数传入，参数可采用TurboC语言中的预设颜色值，具体参见TurboC图形函数。 五、注意事项 1 代码要求正确运行，直线和圆的位置应当为参数，实现可配置。 2 程序提交.c源文件，函数前和关键代码中增加注释。 程序模板 #include 中南大学 《数据结构》课程设计 题目第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 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（） 和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若 为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关 系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。 程序实现的流程图如下： 线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) { 《建筑结构试验》实验报告 班级： 学号： 姓名： 南昌航空大学土木工程试验中心 二○一○年四月 目录 试验一电阻应变片的粘贴及防潮技术试验二静态电阻应变仪的使用及接桥试验三电阻应变片灵敏系数的测定 试验四简支钢筋混凝土梁的破坏试验 试验一电阻应变片的粘贴及防潮技术 姓名：学号：星期第讲第组 实验日期：年月日同组者： 一、实验目的： 1.掌握电阻应变片的选用原则和方法； 2.学习常温用电阻应变片的粘贴方法及过程； 3.学会防潮层的制作； 4.认识并理解粘贴过程中涉及到的各种技术及要求对应变测试工作的影响。 二、实验仪表和器材： 1.模拟试件（小钢板）； 2.常温用电阻应变片； 3.数字万用表； 4.兆欧表； 5.粘合剂：T-1型502胶，CH31双管胶（环氧树脂）或硅橡胶； 6.丙酮浸泡的棉球； 7.镊子、划针、砂纸、锉刀、刮刀、塑料薄膜、胶带纸、电烙铁、焊锡、焊锡膏等小工具； 8.接线柱、短引线 三、简述整个操作过程及注意事项： 1.分选应变片。在应变片灵敏数K相同的一批应变片中，剔除电阻丝栅有形状缺陷，片内有气泡、霉斑、锈点等缺陷的应变片，将电阻值在120±2Ω范围内的应变片选出待用。 2.试件表面处理。去除贴片位置的油污、漆层、锈迹、电镀层，用丙酮棉球将贴片处擦洗干净，至棉球洁白为止，以保证应变片能够牢固的粘贴在试件表面。 3.测点定位。应变片必须准确地粘贴在结构或试件的应变测点上，而且粘贴方向必须是要测量的应变方向。 4.应变片粘贴。注意分清应变片的正、反面，保证电阻栅的中心与十字交叉点对准。应变片贴好后，先检查有无气泡、翘曲、脱胶等现象，再用数字万用表的电阻档检查应变片有无短路、断路和阻值发生突变(因应变片粘贴不平整导致)的现象。 5.导线固定。接线柱粘帖不要离应变片太远，接线柱挂锡不可太多，导线挂锡一端的裸露线芯不能过长，以31mm为宜。引出线不要拉得太紧，以免试件受到拉力作用后，接线柱与应变片之间距离增加，使引出线先被拉断，造成断路；也不能过松，以避免两引出线互碰 题目描述 一个图的存储矩阵如下所示（顶点分别是0、1、2、3、4、5）： 0，12，18，∞，17，∞ 12, 0，10，3，∞，5 18，10，0，∞，21，11 ∞，3，∞，0，∞，8 17，∞，21，∞，0，16 ∞，5，11，8，16，0 试用邻接矩阵存储法和Floyd算法求解任意两个顶点的最短路径。 输入： 输入数据第一行为1个正整：顶点个数n(顶点将分别按0，1，…，n-1进行编号)。后面有n+1行，前n行都有n个整数（第i行第j个数表示顶点i-1和顶点j-1之间的边长，用10000来表示两个顶点之间无边）；第n+1行输入一对顶点x和y 输出： x和y顶点的最短路径长度和最短路径(路径换行输出，只输出顶点编号序列)。 问题分析 题目要求图的存储类型为邻接矩阵，这种存储结构简单易懂，但存储占用较大；求最短路径的算法有Dijkstra算法和SPFA算法，三者相比，在代码的实现上，Floyd编写简单且容易理解，缺点是时间复杂度较高，不适合计算大量的数据。 数据结构及程序 #include for(int i=0;i 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 #include return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码：\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); } 数据结构 设计说明书 单源点最短路径算法的实现 学生姓名王文刚 学号1418064056 班级网络1402 成绩 指导教师 数学与计算机科学学院 年月日 课程设计任务书 20 —20 学年第学期 课程设计名称：数据结构课程设计 课程设计题目：单源点最短路径算法的实现 完成期限：自年月日至年月日共 2 周设计内容： 1.任务说明 2.要求 3.参考资料 指导教师：教研室负责人： 课程设计评阅 摘要 设计了一求解最短路径的方法，该方法具有在输入的途中查找两个顶点之间的最短路径的功能。本方法采用VC++作为软件开发环境，采用Dijkstar函数来求取顶点之间的最短路径。，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。 关键词：最短路径；Dijkstar；无向图; 目录 目录 1课题描述 (2) 2 需求分析 (3) 3概要设计 (4) 3.1 存储结构 (4) 3.2 算法描述 (5) 4详细设计 (6) 4.1 功能模块图 (6) 4.2 主函数 (6) 4.3 pd函数 (7) 4.4 CreateMGraph函数 (8) 4.5Dijkstar函数 (9) 5程序编码 (11) 6程序的调试与测试 (15) 8总结 (16) 参考文献 (17) 1.目录中可以只有一级标题 2.页码右侧对齐页边距 3.本页不需要页码 4.以上内容仅作参考，具体章节由课程设计类型确定 1课题描述 随着交通的发展，人民生活水平的提高。出门旅行变的越来越频繁，而且供暖也成为冬天不可或缺的内容。为了节约时间和金钱，所以人们都希望找到旅行目的地的最短路径和架设暖气的最短路径。那么如何找到最短路径呢？由于路径较多，手工计算比较麻烦，而且容易出错，因此人们用计算机语言代替手工计算求最短路径。而在计算机语言中迪杰斯特拉算法比较常见，简洁，故人们常借助计算机程序迪杰斯特拉算法求最短路径。这样可以广泛提高效率，容易理解。 顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.sodocs.net/doc/1216934951.html,st) { cout<<"所查找值不存在！"< 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：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 Data Structures and Algorithm 习题答案 Preface ii 1 Data Structures and Algorithms 1 2 Mathematical Preliminaries 5 3 Algorithm Analysis 17 4 Lists, Stacks, and Queues 23 5 Binary Trees 32 6 General Trees 40 7 Internal Sorting 46 8 File Processing and External Sorting 54 9Searching 58 10 Indexing 64 11 Graphs 69 12 Lists and Arrays Revisited 76 13 Advanced Tree Structures 82 i ii Contents 14 Analysis Techniques 88 15 Limits to Computation 94 Preface Contained herein are the solutions to all exercises from the textbook A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition. For most of the problems requiring an algorithm I have given actual code. In a few cases I have presented pseudocode. Please be aware that the code presented in this manual has not actually been compiled and tested. While I believe the algorithms to be essentially correct, there may be errors in syntax as well as semantics. Most importantly, these solutions provide a guide to the instructor as to the intended answer, rather than usable programs.数据结构与算法问题分析及源代码之二叉树
数据结构课程实验指导书
图形学实验报告
数据结构课程设计报告Dijkstra算法求最短路径
数据结构(C 版)王红梅_版课后答案
大数据结构与算法课程设计程序及报告材料
数据结构实验报告代码
《建筑结构试验》实验报告
数据结构最短路径
天津科技大学数据结构与算法课程设计
数据结构实验一的源代码
数据结构最短路径
数据结构实验程序
数据结构实验报告图实验
实验四-图的最短路径(弗洛伊德算法实现)
数据结构与算法分析 C++版答案
相关文档
- 源代码--数据结构与算法(Python版)chap1 数据结构与算法
- 数据结构与算法实习课件共77页PPT资料
- 数据结构与算法问题分析与源代码之单链表
- 算法与数据结构设计题与源代码
- 天津科技大学数据结构与算法课程设计报告-源程序的相似性
- 天津科技大学数据结构与算法课程设计报告源程序的相似性.doc
- 数据结构与算法课程设计程序与报告
- 数据结构课本算法源代码
- 源代码--数据结构与算法(Python版)第9章 查找
- 数据结构与算法问题分析与源代码之单链表
- 天津科技大学数据结构与算法课程设计
- 数据结构课程设计报告---几种排序算法的演示(附源代码)
- 源代码--数据结构与算法(Python版)chap6 线性表
- (完整版)数据结构算法大全有代码
- 天津科技大学数据结构与算法课程设计报告源程序的相似性
- 源代码--数据结构与算法(Python版)chap5 函数
- 源代码--数据结构与算法(Python版)chap9 查找
- 【数据结构算法】实验8 图的最短路径问题(附源代码)
- 源代码--数据结构与算法(Python版)chap8 图
- 大数据结构与算法课程设计程序及报告材料