迷宫求解数据结构课程设计及通讯设备分配问题-数学规划课程设计

《数据结构》课程设计题目：迷宫求解班级：学号：作者姓名：指导教师：目录1．需求分析…………….…….…..……12．概要设计…………….….……..……12.1．数据结构………….……..……12.1.1．逻辑结构…………..………..…..…….12.1.1．存储结构…………………..…….…22.2.基本操作…………..…...…….…32.2.1.迷宫中栈的基本操作………….…….32.2.2.迷宫的抽象数据类型…………..………32.2.3.本程序包含三个模块……….….….43．详细设计……………..……….……54．调试与分析………..……….………95．用户手册……………96.测试结果…………….107.附录………………….128.参考文献…………….129、心得体会……………1210、小组成员工作分配………………..13PAGE -PAGE33-共9页第1页需求分析以二维数组maze[n+2][m+2]表示迷宫，其中：maze[0][j]和maze[n+1][j](0<=j<=m+1)及maze[i][0]和maze[i][m+1](0<=i<=j+1)为添加的一圈障碍。数组中以元素值为0的表示通路，1表示障碍，限定迷宫的大小，m，n<=0。迷宫的入口位置和出口位置可由用户自行设定。如设定的迷宫处在通路，则值输出迷宫中的通路，即0，现实的0连起来就是一个迷宫通路路径；如设定的迷宫中不出在通路，则输出“该迷宫找不到通路!”；测试样例：输入迷宫的长宽为5和6，输入迷宫为：100111001111100011010111110000当入口位置为（1,2），出口位置为（5,6）时，则输出数据为：#########0##0##00##0##0000#########程序执行的命令为：输入迷宫的尺寸；2、创建迷宫；3、输入迷宫的的出入口位置；4、求解迷宫；输出迷宫的解。概要设计2.1.数据结构2.1.1、逻辑结构1）栈的定义：限定仅在表尾进行插入或删除操作的线性表；2）操作特性：后进先出;3)ADT定义：ADTStack{数据对象：D={ai|ai∈CharSet,i=1,2,…,n,n>=0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack（&S）初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(&S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(&S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit())初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。}ADTStack2.1.2、存储结构1）顺序存储结构：顺序栈：是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指针top来指示栈顶元素的位置。注：在本迷宫求解程序设计中用到的就是栈的顺序存储结构。//栈的顺序存储表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;2）链式存储结构链式栈：链栈是指采用链式存储结构存储的栈。链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。2.2、基本操作2.2.1、迷宫中栈的基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈S。StackEmpty(&S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。2.2.2、迷宫的抽象数据类型ADTMazeType{数据对象:D={ai,j|ai,j∈{‘’,‘#’、‘@’、‘*’}，0<=i<=n+1,0<=j<=m+1,m,n<=20} 数据关系:R={ROW,LINE}ROW={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1}LINE={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1} 基本操作:StatusPass(MazeType&maze,PosTypecurpos) 初始条件:maze存在迷宫,curpos保存了当前位置的坐标 操作结果:如果可通,返回真,否则为假voidFootPrint(MazeType&maze,PosTypecurpos) 初始条件:maze存在迷宫,curpos保存了当前位置的坐标 操作结果:将当前坐标curpos处的maze[][]值记为足迹PosTypeNextPos(PosTypeCurPos,intdi) 初始条件:各参数值已经定义操作结果:求得以当前位置为栈顶的下一个方向的元素的坐标StatusMazePath(SqStack&S,PosTypestart,PosTypeend) 初始条件:maze存在迷宫地图操作结果:为建立的迷宫找到一条路径}ADTmaze;2.2.3、本程序包含三个模块1）主函数模块：intmain（）{初始化迷宫；求解迷宫；输出迷宫的解；return0；}2）栈实现模块—实现栈的抽象殊绝类型3）迷宫实现模块—实现迷宫的抽象数据类型各模块的调用关系如下：主函数模块——>迷宫模块——>栈模块4）求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do{ 若当前位置可通， 则{将当前位置插入栈顶；//纳入路径 若该位置是出口位置，则结束；//求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置；}否则{若栈不空且栈位置尚有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；//后退一步，从路径中删去该通道块；若栈不空，则重新测试新的栈顶位置；直到找到一个可通的相邻块或出栈至栈空；}}}while(栈不空)；{栈空说明没有路径存在}详细设计坐标位置类型typedefstruct{ introw; intline;}PosType;迷宫类型StatusPass(PosTypeCurPos)//判定当前位置是否可以通过，即是未曾走到过的通道块voidFootPrint(PosTypeCurPos)//给当前可通过的位置标记PosTypeNextPos(PosTypeCurPos,intdi)//探寻下一个位置，并标记方向StatusMazePath(SqStack&S,PosTypestart,PosTypeend)//求解迷宫maze中，从入口start到出口end的一条路径，//如存在，返回OK，否则返回ERROR栈类型typedefstruct{ intord;//通道块在路径上的“序号” intdi;//通道块在迷宫中的“坐标位置” PosTypeseat;//从此通道块走向下一通道块的“方向”}SElemType;//栈的元素类型typedefstruct{ SElemType*base;//在构造栈之前和销毁之后，base的值为NULL SElemType*top;//栈顶指针 intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//栈定义栈的基本操作如下：voidInitStack(SqStack&S)//初始化栈，设栈S为空栈（S.top=NULL）voidPush(SqStack&S,SElemTypee)//若分配空间成功，则在S的栈顶插入新的栈顶元素e//否则增加栈栈的存储空间，再插入新的元素intGetTop(SqStack&S,SElemTypee)//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSEintPop(SqStack&S,SElemType&e)//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE//否则返回FALSEintStackEmpty(SqStackS)//若S为空栈（S.top==NULL），则返回TRUE；否则返回FALSE具体部分操作的算法如下：voidInitStack(SqStack&S){//初始化栈S为空栈（S.top=NULL） S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;}//InitstackvoidPush(SqStack&S,SElemTypee){//若分配空间成功，则在S的栈顶插入新的栈顶元素e//否则增加栈栈的存储空间，再插入新的元素 if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;}//Push求解迷宫的伪码算法：StatusMazePath(SqStack&S,PosTypestart,PosTypeend){//若迷宫maze中存在从入口start到出口end的通道，则//一条存放在栈中(从栈底到栈顶为从入口到出口的路径)，并返//回OK，否则返回ERROR PosTypecurpos; intcurstep; SElemTypee; InitStack(S); curpos=start;//设定“当前位置”为“初始位置” curstep=1;//探索第一步 do{ if(Pass(curpos)) {//当前位置可以通过，即是未曾走到过的的通道块//留下足迹 FootPrint(curpos); e.di=1; e.ord=curstep; e.seat=curpos; Push(S,e);//加入路径 if(curpos.row==end.row&&curpos.line==end.line)returnOK;//到达出口位置 curpos=NextPos(curpos,1); curstep++;//探索下一步 } else//当前位置不能通过 { if(!StackEmpty(S)) { Pop(S,e); while(e.di==4&&!StackEmpty(S)) { FootPrint(e.seat); Pop(S,e);curstep--； } if(e.di<4) { e.di++; Push(S,e); curpos=NextPos(e.seat,e.di); }//if }//if } }while(!StackEmpty(S)); returnERROR;}//MazePath主函数和其它函数的伪码算法voidprintpath(SqStackS,intn,intm){//打印路径 printf("\n\n通路路径为:\n"); //PosTypestart,end;SElemType*p=S.base;//定义一个指针p指向栈中的元素，设//定初值为p=S.base while(p!=S.top) { maze[p->seat.row][p->seat.line]=2; p++;//将有效路径的通道块全部标记为2或其他不为1或0的//值 } inti,flag=0;//打印出路径，周围用“#”围成一圈作围墙 for(i=0;i<m+2;i++)printf("%c",'#');printf("\n"); for(i=1;i<n+1;i++) { printf("%c",'#'); for(intj=1;j<m+1;j++) { if(maze[i][j]==2)printf("%c",'0'); elseprintf(""); } printf("%c",'#'); printf("\n"); } for(i=0;i<m+2;i++)printf("%c",'#');printf("\n\n");}//printpathintmain(){//主函数 SqStackS; intr,l; while(true) { printf("创建一个迷宫，请输入迷宫长和宽(不得大于20):\n"); scanf("%d%d",&r,&l);if(r<1||r>20||l<1||l>20){printf("输入错误!");} inti; printf("按行输入%d*%d数据(0代表可通,1代表不可通):\n",r,l); for(i=0;i<l+2;i++)maze[0][i]=1; for(i=1;i<r+1;i++) { maze[i][0]=1; for(intj=1;j<l+1;j++) scanf("%d",&maze[i][j]); maze[i][l+1]=1; } for(i=0;i<l+2;i++)maze[r+1][i]=1; PosTypestart,end; printf("输入入口行坐标和列坐标:");scanf("%d",&start.row);scanf("%d",&start.line); printf("输入出口行坐标和列坐标:");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(S,start,end)) printpath(S,r,l); elseprintf("该迷宫找不到通路!\n\n"); } return0;}//main调试分析1、在本次的程序设计中，最核心的算法就是MazePath()函数，其他的算法并没有出现什么问题。不过在最后输出的时候本来想输出路径的先后顺序，即maze[1][2]>maze[2][2]>maze[3][2]>maze[3][3]>maze[4][3]>maze[5][3]>maze[5][4]>maze[5][5]>maze[5][6]，但是最后发现这样只有在入口在左上角，出口在右下角时，才可以正确输出。但是入口和出口是随机的，若是入口在右下角，出口在左上角，则也同样输出maze[1][2]>maze[2][2]>maze[3][2]>maze[3][3]>maze[4][3]>maze[5][3]>maze[5][4]>maze[5][5]>maze[5][6]，虽然这两个路径是一样的，但是有先后顺序，故最后没有输出这种形式，将这段代码注释了（源程序中有注释的代码）；2、本来是想设计成既可以手动输入迷宫又可以自动生成迷宫，但是感觉没有太大的用处，所以最后省略了，只保留了手动输入。3、在整个编写的过程中，出现过很多错误，包括一些标点符号的小错误，但是借助DEBUG调试器和数据观察窗口，很快找出来问题的所在。用户手册本程序的运行环境为DOS操作系统,执行文件为：迷宫求解.exe.进入演示程序后,即显示文本方式的用户界面:根据提示输入迷宫大小及迷宫后,输入迷宫的行和列,回车后即可得到所输入迷宫的解或者是显示“该迷宫找不到通路!”字样。测试结果输入长宽为5，6，入口为（1,2），出口为（5,6）的迷宫100111001111100011010111110000求解结果：输入长宽为4，5，入口为（1,1），出口为（4,5）的迷宫01011001101011110000输出结果为：输入长宽为4，5，入口为（1,1），出口为（4,5）的迷宫110111010101100011010111110000输出结果为：附录源程序文件名清单：主函数.cpp迷宫的实现.h栈的实现.h参考文献1、严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社，2012.2、严蔚敏，吴伟民，米宁.数据结构题集(C语言版)[M].北京：清华大学出版社，2012.3、苏仕华，魏韦巍，王敬生，刘燕君.数据结构课程设计[M].北京：机械工业出版社，2010.心得体会做了这次程序设计，我们发现利用数据结构进行程序设计并不像想像中的那么高深，像我们现在所做的，只是一些最基本的程序。经过一个学期的学习，对数据结构有了一个初步的认识，但没有进行实际应用。这次程序设计，就相当于对一个学期的所学做一个总结，再进行一次综合运用，更是学到了很多新的东西，无意中也提升了自己的程序设计水平；在程序设计过程中碰到了很多问题，通过上网查资料等各种手段，我们的解决实际问题的能力也得到了提高。这次的程序设计，让我们对程序设计有了一个更全面的认识，如果我们以后能在编程领域深入发展，这一次也算是我们迈出的重要一步吧。小组成员工作分配程序、文档的编写；程序校对及查找资料；文档的勘误及字体的调整。数学规划课程设计

题目通讯设备分配问题姓名班级学号1. 课程设计评价参考标准及得分序号指标分值得分1所选题目应用价值与难度202综合应用数学专业知识解决实际问题的能力303与学分相适应的工作量和难度，有一定的创新304图标美观，参考文献，格式合适等20论文成绩指导教师签名通讯设备分配问题摘要：数学规划是运筹学的一个重要组成部分，它是近几十年里发展起来的一门新兴科学。随着电子计算机的普及与发展，它在自然科学，社会科学，工程技术和现代管理中得到了广泛的应用，日益受到人们的重视。而作为数学规划中的一个重要分支的动态规划，是一种解决复杂系统优化问题的方法，是目前解决多阶段决策过程问题的基本理论之一。由于动态规划不是一种特定的算法，因而它不像线性规划那样有自己标准的数学表达式和统一的求解方法，而必须对具体问题进行具体的分析处理。因此其更具有实用价值，解决了我们现实生活中许多实际问题。实践证明，动态规划在工程技术，经济管理，工业生产，军事以及现代控制工程等领域都有广泛的应用，并获得显著效果。在本文中，我们主要介绍的运用动态规划的思想，利用计算机软件Excel,解决资源分配问题，就是一个现实生活中动态规划的运用实例，同时，又充分利用计算机技术，使计算更为便捷有效，从而更方便的解决了实际问题。关键词：数学规划；动态规划；多阶段决策过程问题；计算机软件Excel；资源分配问题一．引言正所谓资源分配，即是将数量一定的或若干种，诸如：材料，设备，人力，资金，时间等资源，合理地分给若干个使用者，而是目标函数最大。在此处，由于分配的资源过多，且目标函数是非线性函数，可将其看成一个多阶段决策问题，利用动态规划的方法求解。在动态规划方法求解时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把规划问题中的变量取为决策变量，将累计的量或递推过程变化的量选为状态变量。二．问题阐述某邮局有4套通讯设备准备分给甲乙丙三个地区，事先调查了各地原有生产活动情况，在此基础上对各种分配方案的经济效益进行了估计，得下表1（附录）的数据，例如：甲区原有生产活动的收益为38万元，当新增加一套通讯设备时总收益为41万元，其他类推。试求4套设备的分配方案，使3地区总利益最大。三．模型的建立和求解3.1模型的建立首先我们对设备的分配规定一个顺序，即先考虑分配给甲区，其次乙区，最后丙区，但分配时必须保证邮电局德宗受益最大。将问题按分配过程分为3个阶段，根据动态规划逆序算法，可设：阶段数t=1,2,3(即甲，乙，丙3个地区的编号分别为1，2，3)；状态变量dk:表示分配给第k个地区至第3地区的设备套数（即第k阶段初尚未分配的设备套数）；决策变量Xk：表示分配给第k个地区的设备套数；状态转移方程：dk+1=dk-Xk；Rt（Xk）：表示Xk台设备分配到第k个地区所得的收益值，它由表1查得；Ft(dk):表示将dk台设备分配到第k个地区至第3地区所得的最大收益值，因而可得出递推方程：Ft(dk)=max[Rt（Xk）+Ft+1（dk-Xk）](k=1,2,3；t=1,2,3；Xk=0，1，2，3，4)F4(d4)=03.2模型的求解运用动态规划的思想，利用穷举的方法以及计算机软件Excel，进行模型求解。根据问题分析中的相关公式，此处，为方便，令Jt（dk,Xk）=Rt（Xk）+Ft+1（dk-Xk）。求解步骤：（1）根据表1数据，将Rt（Xk）输入A4：F7来构建电子表格，如图1（附录中）所示。例如：将R2（2）=50输入到单元格D6中；（2）在B11：F11中的各单元各内输入0，因为对所有的dk都有F4(dk)=0；在第18~20行，设置计算指令求出Jt（dk,Xk），此处使用Excel中的HLOOKUP命令来查找Rt（Xk）(在第5行至第7行)和Ft+1（dk-Xk）(在第11行至第14行)的值。例如，要计算J3（3,1），需要将下列公式输入单元格I18中：=HLOOKUP（I$17,$B$4：$F$7,$A18+1）+HLOOKUP(I$16-I$17,$B$10：$F$14,$A18+1)。(其中，该公式前半部分HLOOKUP（I$17,$B$4：$F$7,$A18+1）表示在B4