数据结构课程设计超市选址.docx
- 文档编号:15274994
- 上传时间:2023-07-03
- 格式:DOCX
- 页数:18
- 大小:91.46KB
数据结构课程设计超市选址.docx
《数据结构课程设计超市选址.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计超市选址.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构课程设计超市选址
课程设计任务书
专业
计算机科学与技术
班级
姓名
设计起止日期
2015年5月1日-205年5月7日
设计题目:
超市选址
设计任务(主要技术参数):
硬件环境:
CPU:
P42.8GHz以上;内存:
256MB以上;硬盘大小:
80G以上。
软件环境:
(1)操作系统:
WINDOWSXP。
(2)开发软件:
VC++6.0或TC。
实现功能:
熟练掌握权值的计算和弗洛伊德算法,通过带权又向图和弗洛伊德算法求出最短路径,让我们更加了解、熟悉数据结构中各种算法的运用与计算,并且学会如何去实现它,对我们的生活也增加了一些常识。
指导教师评语:
成绩:
签字:
年月日
超市选址
1.课程设计目的
通过对数据结构中权值的计算和弗洛伊德算法的学习,将其在课程设计中实现、表达出来,数据结构是计算机软件和计算机应用专业的核心课程之一,在众多的计算机系统软件和应用软件中都要用到各种数据结构。
在数据结构中,在设计中可以处理数值计算问题、选取合适数据结构、写出更有效的算法。
计算机核心课程,程序=算法+数据结构,数据结构的重要性可见一斑。
事实上,想要写出优美高效的代码,数据结构的知识一定要有的,学习的过程中更重要的是去理解它的思想。
2.设计方案论证
2.1设计思路
核心问题:
求最短路径(选址的要求就是超市到各单位权值之和最少)
数据模型(逻辑结构):
带权有向图(权值计算:
距离*频度)
存储结构:
typedefstruct
{
stringvexs[MAX_VERTEX_SIZE];
intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
intvexnum;//,arcnum;
}MGraph;
核心算法:
Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)
输入数据:
各单位名称,距离,频度,单位个数.
输出数据:
所选单位名称.
总体思路:
如果超市是要选在某个单位,那么先用floyd算法得出各顶点间的最短距离/最小权值。
假设顶点个数有n个,那么就得到n*n的一张表格,arcs(i,j)表示i单位到j单位的最短距离/最小权值,这张表格中和最小的那一行(假设为第t行),那么超市选在t单位处就是最优解。
2.2设计方法
Floyd算法利用动态规划思想,通过把问题分解为子问题来解决任意两点见的最短路径问题。
设G=(V,E,w)是一个带权有向图,其边V={v1,v2,…,vn}。
对于k≤n,考虑其结点V的一个子集。
对于V中任何两个结点vi、vj,考虑从vi到vj的中间结点都在vk中的所有路径,设该路径是其中最短的,并设它的路径长度为最短路径长度。
如果结点vk不在从vi到vj的最短路径上,则;反之则可以把分为两段,其中一段从vi到vk,另一段从vk到vj,这样便得到表达式。
上述讨论可以归纳为如下递归式:
算法结构图,如图1
N
Y
图1算法结构图
2.3详细设计
让所有路径加上中间顶点1,取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值,完成后得到A
(1),如此进行下去,当第k步完成后,A(k)[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。
当第n-1步完成后,得到A(n-1),A(n-1)即所求结果。
A(n-1)[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度,即A(n-1)[i][j]表示从i到j的最短路径长度。
2.3.1结构体的定义
typedefstruct
{
Vextypevexs[MAXVEX][MAXVEX];//单位名称(顶点信息);
intadj[MAXVEX][MAXVEX];//单位之间的相通情况(是否有边);
intdis[MAXVEX][MAXVEX];//单位间距离(边的长度);
intf[MAXVEX];//各单位去超市的频率;
intn;//顶点数和边数;
inte;
}Mgraph;
2.3.2带权有向图求最短路径floyd算法
voidFloyed(Mgraph*G)//带权有向图求最短路径floyd算法
{
intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
inti,j,k,pre;
intcount[MAXVEX];
for(i=0;i
for(j=0;j
{
A[i][j]=G->dis[i][j];
path[i][j]=-1;
count[i]=0;
}
for(k=0;k
{
for(i=0;i
for(j=0;j
if(A[i][j]>(A[i][k]+A[k][j]))//从i经j到k的一条路径更短
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 超市 选址