数据结构作业——地图设计.docx

数据结构报告（一）采用的数据结构人大交通指南程序的编写主要采用了2中数据结构。用2维数组即线性表来表示人大地图的位置，用栈进行路径的保存与调整。（二）算法伪码（尽量在20行以内）栈初始化;将起点坐标及到达该点的方向(设为-1)入栈;while (栈不空){栈顶元素==(x , y , d);出栈;求出下一个要试探的方向d++ ;while(还有试探方向){ if(d方向可走){(x , y , d)入栈;求新点坐标(i, j ) ;将新点(i , j)切换为当前点(x , y);if ( (x ,y)==终点 ) 结束;else 重置d=0 ;}else d++ ;}}（三）讨论有关复杂度人大地图简化如下门：（5，8）2信息楼：（2，7）3逸夫会议中心：（5，6）4东区食堂：（6，6）5世纪馆：（6，4）6明德楼：（4，3）7西门：（4，1）我所选定的原操作：入栈和出栈操作，随着地图上点的个数n的增加，所需时间增加，时间复杂度：T（n）=O（f（n））（四）结语经过这次的编程实验，我对栈这种数据结构有了更深入的了解，但是在实践的过程中，还遇到了一些问题，比如对于复杂度的分析还存在一些问题，不知道选择什么原操作更适合于复杂度的分析；还有就是算法的问题，有些路径很复杂，需要绕一大圈才能从起点找到终点，不知道有没有更好的算法。APPENDIX:// ruc_map.cpp : Defines the entry point for the console application.//#include stdafx.h#include iostream.hstruct DataType //定义描述地图中当前位置的结构类型{ int x; //x代表当前位置的行坐标 int y; //y代表当前位置的列坐标 int d; //d表示方向};struct Move //定义下一个位置的方向{ int x; int y;};struct LinkNode //链表结点{ DataType data; LinkNode *next;};//下面定义栈class stack{private: LinkNode *top; //指向第一个结点的栈顶指针public: stack(); //构造函数，置空栈 ~stack(); //析构函数 void Push(DataType data); //把元素data压入栈中 DataType Pop(); //使栈顶元素出栈 DataType GetPop(); //取出栈顶元素 void Clear(); //把栈清空 bool IsEmpty(); //判断栈是否为空，如果为空则返回1，否则返回0};stack::stack() //构造函数，置空栈{ top=NULL;}stack::~stack() //析构函数{}void stack::Push(DataType x) //把元素data压入栈中{ LinkNode *TempNode; TempNode=new LinkNode; TempNode-data=x; TempNode-next=top; top=TempNode;}DataType stack::Pop() //使栈顶元素出栈{ DataType Temp; LinkNode *TempNode; TempNode=top; top=top-next; Temp=TempNode-data; delete TempNode; return Temp;}DataType stack::GetPop() //取出栈顶元素{ return top-data;}void stack::Clear() //把栈清空{ top=NULL;}bool stack::IsEmpty() //判断栈是否为空，如果为空则返回1，否则返回0{ if(top==NULL) return true; else return false;}void PrintPath(int maze[10][10], stack p)//显示地图路径{cout地图路径为\n;int a,b;DataType data;while(!p.