数据结构程序设计

《数据结构程序设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告题目：迷宫问题非递归求解2010年5月29日一、需求分析说明任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；二、总体设计（从总体上说明该题目的框架，用文字和图表说明三、详细设计：一、需求分析1、本程序实现迷宫的探索过程.以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。2、本演示程序中，输入形式以

2、“回车符”为结束标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径二、概要设计为实现上述程序功能，应以栈存储结点。为此，需要定义一个抽象数据类型。1.抽象数据类型定义为：ADTstack{数据对象：D={ai

3、ai∈LinkList,i=1,2,...n,n≥0}数据关系：R1={

4、ai-1,ai∈D

5、=2,……n}，即当前结点与下一个结点的关系基本操作：stack

6、();构造函数，建立一个空栈；操作结果：通过字符串a构造两个位数不限的长整数。voidPush(DataTypedata);初始条件：已存在栈操作结果：把元素data压入栈顶DataTypePop();初始条件：已存在栈，且非空操作结果：栈顶元素出栈，且删除栈顶元素DataTypeGetPop();初始条件：已存在栈，且非空操作结果：获取栈顶元素voidClear();初始条件：已存在栈操作结果：把当前的栈清空boolIsEmpty();初始条件：已存在栈操作结果：如果栈为空，则结果为“真”，否则为“假”}ADTOrderedList2.本程序包含三个模块：1)主程序模块

7、：voidmain(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}2)、栈模块——实现定义的抽象数据类型3)、路径探索模块——实现探索迷宫路径四、程序代码/////////////LinkList.h文件//////////////////////////#include#includeusingnamespacestd;structDataType//定义描述迷宫中当前位置的结构类型{intx;//x代表当前位置的行坐标inty;//y代表当前位置的列坐标intpre;//pre表示移动到下一步的方向};

8、structMove//定义下一个位置的方向{intx;inty;};structLinkNode//链表结点{DataTypedata;LinkNode*next;};//下面定义栈classstack{private:LinkNode*top;//指向第一个结点的栈顶指针public:stack();//构造函数，置空栈~stack();//析构函数voidPush(DataTypedata);//把元素data压入栈中DataTypePop();//使栈顶元素出栈DataTypeGetPop();//取出栈顶元素voidClear();//把栈清空boolIsEmp

9、ty();//判断栈是否为空，如果为空则返回1，否则返回0};/////////LinkList.cpp文件////////////#include"LinkList.h"stack::stack()//构造函数，置空栈{top=NULL;}stack::~stack()//析构函数{/*LinkNode*p=top;while(top!=NULL){p=top;top=top->next;//deletep;}*/}voidstack::Push(DataTypex)//把元素data压入栈中{LinkNode*TempNode;TempNode=newLinkNode

10、;TempNode->data=x;TempNode->next=top;top=TempNode;}DataTypestack::Pop()//使栈顶元素出栈{DataTypeTemp;LinkNode*TempNode;//if(top==NULL)returnNULL;//else//{TempNode=top;top=top->next;Temp=TempNode->data;deleteTempNode;returnTemp;//}}DataTypestack::GetPop()//取出栈顶元素{returntop-