数据结构作业——地图设计.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+ ;（三）讨论有关复杂度人大地图简化如下：27631541东门：（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 stackprivate: 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 maze1010, stack p)/显示地图路径cout地图路径为n;int a,b;DataType data;while(!p.IsEmpty()data=p.Pop();a=data.x;b=data.y;switch(data.d)case 0: mazeab=5; break;case 1: mazeab=6; break;case 2: mazeab=7; break;case 3: mazeab=8; break;default:coutendl;for(int i=0;i10;i+)for(int j=0;j10;j+)switch(mazeij)case -1: coutO ; break;case 0: coutO ; break;case 1: cout* ; break;case 5: cout ; break;case 6: cout ; break;case 7: cout ; break;case 8: cout ; break;default:coutendl;coutendl;bool Mazepath(int maze1010,DataType a,DataType b)/寻找maze中从a到b的路径int n=0;Move move4=0,1,1,0,0,-1,-1,0;stack p; /定义栈p,存探索路径过程 DataType Temp; int x,y,d,i,j;Temp.x=a.x;Temp.y=a.y;Temp.d=-1;p.Push(Temp);n+;while(!p.IsEmpty()Temp=p.Pop();n+;x=Temp.x; y=Temp.y; d=Temp.d+1;while(d=1&j=1&i=8) if(mazeij=0) Temp.x=x; Temp.y=y; Temp.d=d; p.Push(Temp); n+; x=i ; y=j ; mazexy= -1 ; if(x=b.x)&(y=b.y) PrintPath(maze,p);coutnendl; return 1; else d=0;else d+;else d+;void main()int maze1010=1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,1,1,0,1, 1,0,1,1,0,0,0,0,0,1, 1,0,1,1,0,0,0,0,0,1, 0,0,0,0,0,1,1,0,0,1, 1,0,0,1,0,0,0,0,0,0, 1,0,0,1,0,0,0,0,0,1, 1,0,0,0,0,0,1,0,0,1, 1,0,0,0,0,0,1,0,0,1, 1,1,1,1,1,1,1,1,1,1;/0表示通，“1”表示不同for(int i=0;i10;i+)for(int j=0;j10;j+)if(mazeij=0)coutO ;else cout* ;coutendl;int s,d;/s=起点，d=终点cout请输入您现在所在的位置（1.东门 2.信息楼 3.逸夫会议中心 4.东区食堂 5.世纪馆 6.明德楼 7.西门）：s;cout请输入您想去的位置（1.东门 2.信息楼 3.逸夫会议中心 4.东区食堂 5.世纪馆 6.明德楼 7.西门）：d;DataType Start,Des,Temp;switch(s)case 1: Start.x=5; Start.y=8; break;case 2: Start.x=2; Start.y=7; break;case 3: Start.x=5; Start.y=6; break;case 4: Start.x=6; Start.y=6; break;case 5: Start.x=6; Start.y=4; break;case 6: Start.x=4; Start.y=3; break;case 7: Start.x=4; Start.y=1; break;default:coutendl;switch(d)case 1: Des.x=5; Des.y=8; break;case 2: Des.x=2; Des.y=7; break;case 3: Des.x=5; Des.y=6;