新课程设计

中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-1-《数据结构》课程设计报告专业：计算机科学与技术（软件工程方向）班级：软件801班学号：200880114120学生姓名：霍锦超2010年1月14日星期四中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-2-目录一、设计目的………………………………………………………….3二、设计要求………………………………………………………….3三、设计题目………………………………………………………….3四、设计思路……………………………………………………..3题目一迷宫求解………………………………………………….3题目二拓扑排序…………………………………………………16五、心得体会…………………………………………………….......24中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-3-《数据结构》课程设计报告一、设计目的《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计题目１．迷宫求解２．拓扑排序四．设计思路题目一迷宫求解一、设计题目：迷宫求解问题二、需要分析：任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出输入数据：输入开始界面的选项1-4，选择1初始化建立迷宫图，输入（0、1）建立正方形迷宫图；选择2输入迷宫入口坐标和出口坐标；选择3判断是否为通路并显示可通路径。选择4退出出程序。输出形式：输出迷宫图以及走出迷宫的路径；程序所能达到的功能输出迷宫图以及走出迷宫的路径“1”代表障碍物“0”代表路径，“#”代表外围迷宫墙，“*”显示迷宫可通时的路径；如果主函数选项错误显示“选项错误，请从新输入要选择项目”，选择迷宫尺寸超出范围显示“输入错误”；如果输入迷宫有路径时显示“找到通路”，如果迷宫有路径显示迷宫图以及走出路径和“找不到通路”。中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-4-三．概要设计1.定义栈的抽象数据类型定义：ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：typedefstructSqStack//构造一个栈的结构体StatusInitStack(Stack&S)//建立一个空栈StatusStackEmpty(StackS)//若s为空返回TRUE,否则返回FALSEStatusPush(Stack&S,SElemTypee)//插入元素e为新的栈顶元素StatusPop(Stack&S,SElemType&e)//若栈不空删除栈顶元素用e返回并返回OK，2.定义迷宫的抽象数据类型ADTMaze{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：voidInitmaze(intmaze[22][22],intsize)//初始化迷宫voidPrintmaze(intmaze[22][22],intsize)//显示初始化迷宫图形voidPrintmaze(intmaze[22][22],intsize)//将标记路径信息的迷宫输出到终端(包括外墙)StatusPass(intmaze[22][22],PosTypeCurPos)//当前位置可通则返回TURE,否则返回FALSEvoidMarkfoot(intmaze[22][22],PosTypeCurPos)//标记当前位置可通StatusMazePath(MazeType&maze,PostTypestart,PostTypeend)//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中;并返回TRUE,否则返回FALSEPosTypeNextPos(PosTypeCurPos,intDir)//进入下一位置寻找可通路径StatusMazePath(intmaze[22][22],SqStack&S,PosTypestart,PosTypeend)//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中3.主程序包含三个模块：1）voidmain(){//主函数输出开始界面；由switch()语句调用各函数；输出测试结果；}2）栈模块---实现栈抽象数据类型3）迷宫模块---实现迷宫抽象数据类型各模块调用关系如下：主程序模块迷宫模块栈模块四．详细设计中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-5-1.主程序中的需要全程量#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量2.迷宫类型：typedefstructPosType//定义通道块通道坐标结构体{introw;//迷宫行号intline;//迷宫列号}PosType;typedefstructdf{intord;//通道快路径上的序号PosTypeseat;//通道块在迷宫中的坐标位置intdi;//从此通道块走向下一通道块的方向}SElemType;3.栈类型typedefstructSqStack//初始化一个栈的结构{SElemType*base;SElemType*top;intstacksize;}SqStack;4.求解迷宫迷宫的部分伪代码：voidInitmaze(intmaze[22][22],intsize){inti;Printf(----------输入一个迷宫布局（0和1）-------------\n);for(i=0;isize+2;i++)maze[0][i]=1;for(i=1;isize+1;i++){……for(j=1;jsize+1;j++)scanf(%d,&maze[i][j]);…………}for(i=0;isize+2;i++)maze[size+1][i]=1;}voidPrintmaze(intmaze[22][22],intsize)//显示初始化后的迷宫{inti,j;Printf(\n\n);Printf(显示所建的迷宫(#表示外面的墙):\n);for(i=0;isize+2;i++)Printf(%c,'#');Printf(\n);for(i=1;isize+1;i++){Printf(%c,'#');…...Printf(%d,maze[i][j]);…….Printf(%c,'#');Printf(\n);中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-6-}//forfor(i=0;isize+2;i++)Printf(%c,'#');Printf(\n);}StatusPass(intmaze[22][22],PosTypeCurPos)//当前位置可通则返回OK,否则返回ERROR{if(maze[CurPos.row][CurPos.line]==0)returnOK;//如果当前位置是可以通过，回1elseif(maze[CurPos.row][CurPos.line]==1)returnERROR;//其它情况返回0}PosTypeNextPos(PosTypeCurPos,intDir)//进入下一位置{PosTypeReturnPos;switch(Dir){．．．．．．}returnReturnPos;}//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中StatusMazePath(intmaze[22][22],SqStack&S,PosTypestart,PosTypeend){PosTypecurpos;intcurstep;SElemTypee;InitStack(S);curpos=start;//设定当前位置为入口位置curstep=1;//探索第一步do{if(Pass(maze,curpos))//当前位置可通过，即是未曾走到过的通道块{Markfoot(maze,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);中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-7-while(e.di==4&&!StackEmpty(S)){Markfoot(maze,e.seat);//留下不能通过的标记，并退回一步Pop(S,e);}if(e.di4){e.di++;//换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);//当前位置设为新方向的相邻块}}}}while(!StackEmpty(S));returnERROR;}voidPrintpath(intmaze[22][22],SqStackS,intsize)//输出路径{．．．．．．while(p!=S.top){maze[p-seat.row][p-seat.line]=2;//标记为路径中的点p++;}for(i=0;isize+2;i++)Printf(%c,'#');Printf(\n);for(i=1;isize+1;i++){Printf(%c,'#');for(j=1;jsize+1;j++){if(maze[i][j]==2)Printf(%c,'*');……}//forPrintf(%c,'#');Printf(\n);}for(i=0;isize+2;i++)Printf(%c,'#');Printf(\n\n);}5.函数调用关系图反映了演示程序的层次结构：中原工学院信息商务学院《数据结构》课程设计报告5/25/2020-8-五．调试分析1.即迷宫的路径，所以总的调试比较顺利，只是在调试，发现好多地方都遗漏去地址符&，导致所建立的IintStack()不能运行；一开始有些函数函数都是已声明后使用，调换主函数位置以及其他调用别的函数的先后书写位置；标志通路路径和原来以0标记的路径混淆，导致显示迷宫图式失败，修改通路标记路径maze[p-seat.row][p-seat.line]=2;//标记为路径中的点。2.本实验有三主要算法：InitMaze；MazePath和PrintMaze时间复杂度均为：O（size*size）空间复杂度为O（size*size）（栈所占空间最大）;六．测试结果；1、创建并显示一个迷宫退出程序输入出口坐标Main()Prin