数据结构迷宫-学校超市选址、停车场管理算法

1、精选课程设计课程：数据结构课程设计名称： 1.迷宫求解路径问题2. 停车场管理问题3. 学校超市选址问题专业班级：学生姓名：可编辑精选利用栈实现迷宫的求解一、 要解决的问题 ：以一个 m*n 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和障碍，设计一个 程序，对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。 二：算法基本思想描述 :用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0 ”（表示通路）或“ 1”（表示墙壁）。二维数组的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“ 1 ”， 表示迷宫 的边界；第 1 行第 1 列元素和第 m

2、 行第 n 列元素置成“ 0 ”， 表示迷宫的入口和出口走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北 4 个方向 顺序试探下一个位置；用二维数组 move 记录 4 个方向上行下标增量和列下标增量，则沿第 i 个方向前进一步， 可能到达的新位置坐标可利用 move 数组确定：Px=x+movei0Py=y+movei1如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索； 如果 4 个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。三：设计：1）定义三元数组元素的结构1：数据结构的设计：可编辑精选typedef struct Ma

3、zeDirectint Dx; / 行标int Dy; / 列标int direct; / 走到下一个坐标点的方向 MazeDirect;（2）定义链表节点的结构组成typedef struct LinkNodeelemtype data; / 数据域struct LinkNode *next;/ 指针域LinkNode;（3）定义链栈的头指针typedef structLinkNode *top;/ 栈的头指针LinkStack;（4）移动数组结构的定义typedef structint x,y;/x 为行标， y 为列标Direction_increm;【1】迷宫图的设计设迷宫为 m行n列

4、，利用 mazemn来表示一个迷宫，mazei j=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有 2个方向，其它边缘点有3个方向，为使问题简单化我们用mazem+2n+2来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。1111111111【2】试探方向的设计：可编辑精选在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y),与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在(m，

5、n)，因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的 求出新点的坐标，将从正东开始沿顺时针进行的这4个方向(用0，1，2，3表示东、南、西、北)的坐标增量放在一个结构数组move 4 中，在move 数组中，每个元素有两个域组成，x:横坐标增量，y：纵坐标增量。Move数组如图3所示。move数组定义如下：typedef struct int x ;/ 行int y ;/ 列 item ;item move4;这样对move的设计会很方便地求出从某点(x, y)按某一方向v (0 v3,4,03,3,03,2,1栈中每一组数据是所到达的每走的，对于图

6、3迷宫，走的路线为:点的坐标及从该点沿哪个方向向下2,2,02,1,1 1,1,0(1,1,0)(2,1,1)(2,2,0)(3,2,1)(3,3,0)(3,4,0)(下脚标表示方向)，当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向继续试探。栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：typedef structint x , y , d ;/*横纵坐标及方向*/datatype ;栈的定义为： SeqStack s ;【4.如何防止重复到达某点，以避免发生死循环：一种方法是另外设置一个标志数组markmn,它的所有元素都初始化为0, 旦到达了某一点(i , j )

7、之后，使mark i j 置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点(i , j)后使maze i j 置-1，以便区别未到达过的点，同样也能起到防止走重复点的目的，此处采用后一方法，算法结束前可恢复原迷宫。四：详细设计；1. 算法的设计思想及流程图(1) 主要函数的功能说明void ini_stack(LinkStack *)/* 初始化链栈 */int empty_Stack(LinkStack *)/* 判断是否为空栈 */void push_Stack(LinkStack *,elemtype)/* 入栈 */elemtype pop_Stack(LinkStack

8、 *) /* 出栈 */int size_stack(LinkStack ) /* 栈的规模大小 */(2) 算法描述【伪代码描述】迷宫求解算法思想如下：(1) 栈初始化 ;(2) 将入口点坐标及到达该点的方向(设为 -1 )入栈(3) while ( 栈不空 )栈顶元素=(x , y , d )出栈 ;求出下一个要试探的方向 d+;/ 当遇到死路的时候就出栈，寻找原来点的下一个方向 while (还有剩余试探方向时) if ( d 方向可走)则 (x , y , d )入栈 ;求新点坐标 (i, j ) ;x , y)将新点( i , j )切换为当前点(if ( (x , y )= =(

9、m ,n)结束else 重置 d=0 ;else d+ ;五：源程序清单 ；#include #include int m,n;typedef struct MazeDirectint Dx;int Dy;int direct;MazeDirect;/* 定义三元数组元素的结构 */typedef MazeDirect elemtype;typedef struct LinkNodeelemtype data;struct LinkNode *next;/* 定义链表节点的结构组成 */LinkNode;typedef structLinkNode *top;/* 定义链栈的头指针 */Lin

10、kStack;void ini_stack(LinkStack *stack)/* 初始化链栈 */stack-top=NULL;int empty_Stack(LinkStack *stack)/* 判断是否为空栈 */if (stack-top!=NULL)return 0;elsereturn 1;void push_Stack(LinkStack *stack,elemtype x)/*入栈 */LinkNode *s;s=(LinkNode *)malloc(sizeof(LinkNode);s-data=x;s-next=stack-top;stack-top=s;/* 出栈 */

11、elemtype pop_Stack(LinkStack *stack)elemtype x;LinkNode *p;elemtype tmpNull=0,0,0;if (stack-top=NULL)return tmpNull;/(NULL)elsex=stack-top-data;p=stack-top;stack-top=p-next;free(p);return (x);/* 栈的规模大小 */int size_stack(LinkStack stack)int i;LinkNode *Numb;i=0;Numb=stack.top;while(Numb!=NULL)Numb=Num

12、b-next;i+;return i;int w,t,maze100100;typedef structint x,y;/x 为行标， y 为列标Direction_increm;Direction_increm MazeMove4=0,1,1,0,0,-1,-1,0;typedef MazeDirect TmpType;int Maze_path()MazeDirect tmp,path;LinkStack s;int x,y,Px,Py,d,flag=0;ini_stack(&s);tmp.Dx=1;tmp.Dy=1;tmp.direct=-1;push_Stack(&s,tmp);whi

13、le (!empty_Stack(&s)tmp=pop_Stack(&s);遇到死路的时候，回溯（通过出栈完成）x=tmp.Dx;y=tmp.Dy;d=tmp.direct+1;/ while (d4)Px=x+MazeMoved.x;Py=y+MazeMoved.y;if (mazePxPy=0)tmp.Dx=x;tmp.Dy=y;tmp.direct=d;push_Stack(&s,tmp);x=Px;y=Py;mazexy=-1;/* 标记，防止重复点 */if(x=m&y=n)flag=1;printf(n 到达迷宫出口： %d,%d,x,y);printf(n 经过的节点有： %d

14、个 ,size_stack(s);while(!empty_Stack(&s)path=pop_Stack(&s);printf(n(%d,%d,%d),path.Dx,path.Dy,path.direct);break;else d=0;/ 结束 ifelse d+;/ 结束内部 while/ 结束外部 whilereturn flag;void main()printf( 请输入迷宫图的行数和列数 (输入格式为 i,j):n);scanf(%d,%d,&m,&n);printf( 创建迷宫图 :n);for(w=0;wm+2;w+)for(t=0;ttoptop0) 确保栈不空，然后用个

15、 while(1) 确保输入的车辆离 开位置的合法性。如果不和法，显示输入有误，要重新输入。通过 while(Enter-toproom)判断离开车辆的位置，如果是中间位置，就要再用一个栈前面临时开出来的车， 等要开出的车开出后， 再把临时栈的车看进 车场内， 并要调用 PRINT(p,room); 这个函数计算显示费用。然后还要用 if(W-head!=W-rear)&Enter-topMAX)语句判断便道上有没有车，如果有车就要显示进车场的车的车牌号，并登记进入时间。并要进行相应的出队列和进栈操作。五、源程序清单#include#include#include#define MAX 3/

16、停车场最大容量为 3 辆，便于观察#define price 0.05typedef struct time/ 定义时间结构体int hour;int min;Time;typedef struct node/ 定义车辆信息结构体char num10;Time reach;Time leave;CarNode;typedef struct NODECarNode *stackMAX+1;int top;SeqStackCar;typedef struct carCarNode *data;struct car *next;QueueNode;typedef struct NodeQueueNo

17、de *head;QueueNode *rear;LinkQueueCar;void InitStack(SeqStackCar *);int InitQueue(LinkQueueCar *);int Arrival(SeqStackCar *,LinkQueueCar *);void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *);void List(SeqStackCar,LinkQueueCar);void processloop();int prnmenu(void);main()processloop();void process

18、loop()可编辑精选int ichoice,ch;SeqStackCar Enter,T emp;LinkQueueCar Wait;InitStack(&Enter);InitStack(&Temp);InitQueue(&Wait);ichoice=prnmenu();while(ichoice);scanf(%d,&ichoice);while(ichoice4)printf(n 输入错误，请从新输入 =); scanf(%d,&ichoice);/ 自定义函数void InitStack(SeqStackCar *s)/ 地址栈的初始化s-top=0;s-stacks-top=NUL

19、L;int InitQueue(LinkQueueCar *Q)/ 队列的初始化Q-head=(QueueNode *)malloc(sizeof(QueueNode);if(Q-head!=NULL)Q-head-next=NULL;Q-rear=Q-head;return(1);else return(-1);可编辑精选void PRINT(CarNode *p,int room)/ 车辆收费int A1,A2,B1,B2;printf(n车辆离开的时间 :);scanf(%d:%d,&(p-leave.hour),&(p-leave.min);/ 此时 scanf 函数以 : 为接受数字

20、结束符printf(n离开车辆的车牌号为 :);puts(p-num);printf(n其到达时间为 : %d:%d,p-reach.hour,p-reach.min);printf(n离开时间为 : %d:%d,p-leave.hour,p-leave.min);A1=p-reach.hour;A2=p-reach.min;B1=p-leave.hour;B2=p-leave.min;printf(n应交费用为 : %2.1f 元 ,(B1-A1)*60+(B2-A2)*price);free(p);/ 车辆的到达登记int Arrival(SeqStackCar *Enter,LinkQu

21、eueCar *W)CarNode *p;QueueNode *t;p=(CarNode *)malloc(sizeof(CarNode);flushall();printf(n 请输入车牌号 (例:闽 B1234):);gets(p-num);if(Enter-toptop+;printf(n 车辆在车场第 %d 位置 .,Enter-top);printf(n 车辆到达时间 :);scanf(%d:%d,&(p-reach.hour),&(p-reach.min);Enter-stackEnter-top=p;elseprintf(n 该车须在便道等待 ! 有车位时进入车场 );getch

22、();t=(QueueNode *)malloc(sizeof(QueueNode);t-data=p;t-next=NULL;W-rear-next=t;W-rear=t;void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) / 车辆的离开 int room;CarNode *p,*t;QueueNode *q;if(Enter-top0) / 判断车场是否为空while(1)printf(n 请输入车在车场的位置 /1-%d/ ： ,Enter-top);scanf(%d,&room);if(room=1&room

23、top) break;可编辑精选while(Enter-toproom) / 把要删除的车辆的前面的车开出来，进临时栈。 即如果是 1， 2 号就要用到临时栈，如果 enter-top=room ，也就是三号的话就不必用到 临时栈Temp-top+;Temp-stackTemp-top=Enter-stackEnter-top;Enter-stackEnter-top=NULL;Enter-top-;p=Enter-stackEnter-top; / 把要删除的车辆节点赋给 p 。Enter-stackEnter-top=NULL;Enter-top-;while(Temp-top=1) /

24、再把临时栈里德车辆进停车场Enter-top+;Enter-stackEnter-top=Temp-stackTemp-top;Temp-stackTemp-top=NULL;Temp-top-;PRINT(p,room); / 调用计费函数计费。 。 if(W-head!=W-rear)&Enter-tophead-next;t=q-data;Enter-top+;printf(n便道的 %s 号车进入车场第 %d 位置 .,t-num,Enter-top);printf(n请输入 %s 号车进入车场的时间 :,t-num);scanf(%d:%d,&(t-reach.hour),&(t-r

25、each.min);W-head-next=q-next;if(q=W-rear) W-rear=W-head;Enter-stackEnter-top=t;free(q);else printf(n便道里没有车 .n);else printf(n 车场里没有车 .);void List1(SeqStackCar *S) / 显示车场里的车辆情况int i;if(S-top0)可编辑精选printf(n 车场 :);printf(n 位置 到达时间 车牌号 n);for(i=1;itop;i+)printf( %d ,i);printf( %d:%d ,S-stacki-reach.hour,

26、S-stacki-reach.min);puts(S-stacki-num);else printf(n 车场里没有车 );void List2(LinkQueueCar *W) / 显示便道上的车辆情况QueueNode *p;int i;p=W-head-next;可编辑精选if(W-head!=W-rear)printf(n 等待车辆的号码为 :);for(i=1; (p!=NULL); i+)printf(n 第 %d 车辆 .,i);puts(p-data-num);p=p-next ;else printf(n 便道里没有车 .);printf(n);int menu()int i

27、choice;system(cls);printf( 查看车辆列表显示 : );printf(n 1. 车场列表 n 2. 便道列表 n 3. 返回主菜单 n);printf(n 请选择 =);scanf(%d,&ichoice);while(ichoice3)printf(n 输入错误，请重新输入 =); scanf(%d,&ichoice);return ichoice;/ 显示 ,遍历void List(SeqStackCar S,LinkQueueCar W)int ichoice;ichoice=menu();while(ichoice2、车辆到达登记信息，为了便于观察，车场内最多可

28、停3辆车，当停车场已满时，只登记车牌号，然后进入便道上，即进入队列中。可编辑欢迎使用停车场系统1.车辆至lj达登记2,车辆离超记3,车辆列表显不*2 B ill S7p Jli_L| L请选择=1请输入车牌号C例：闽旳貂Q :Eb於车须在便追等侍亍有车位旳进入车场欢迎使用停车场系统1.三辆到达登记2车辆离己3三辆歹4g Uj 歹 Ox -JU lJ_i 5JU谙选择=1请輸入车牌号t例:B1234：F6b车须在便道等待?有车位时进入车场3 、分别显示车场内和便道上的车辆信息情况 示表列 M.H车閒主看场追回 12 3请选择=2 蓋待车辆的号码为:黒1车辆Mk 2车辆应第3车辆用查看年郵懐显示:

29、3堆回主彙单请选择=1到达时间5:366：ae7:36车牌号A1B2C34、车场内车辆离开时，输入离开时间，然后计算、显示费用，如果便道上有 车，则显示要进入车场内的车牌号码，同时登记时间。欢迎使用停军场统I1 车橢IJ达登记2.车辆离开登记3 * 车辆歹lj表显乔厂4,退岀系统 请选择=2谙输入车在车场的位置2车辆离开的时间=14:30离开车辆的车牌号为汕乂M的1;!30B-3 86:;14Sa 为:间为拘号号时间黑D4D4达时蓉的人到开交這输苴篱应便请O35* 13 B课程设计题目：学校超市选址问题、要解决的问题及其要求:对于某一学校超市，其他各单位到其距离不同，同时各单位人员去超市的频

30、度也不同，请为超市选址，要求实现总体最优。、算法基本思想描述 创建图G，利用普里姆算法得到最小生成树的路径和各边权值，然后用数组名为a的数组（初始值为无穷大）存储最小生成树的权值。其后利用数组名为a的数组创建新图R,即将数组a的元素赋给新图的存储边权值的数组R-arcs.adj，在新图的基础上利用佛洛依德算法求得任意两点之间的最短然后再求生成树路径及其相应的路径长度（将其存储在数组名为 A的数组中）上各点到其他点的距离之和 果一次存到数组名为 B 的数组中，再对 B 数组元素进行比较大小，求得最小元 素，其下标即为最优点存储在定点数组 vexs 中的序号。A01+A02+A03+.AG-vex

31、 nu mG-vex num，然后将求和结三、详细设计1. 数据结构的设计（1）邻接矩阵数据结构：typedef structVRType adj; / 相通情况AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;（2）图的数据结构：typedef structVertexType vexsMAX_VERTEX_NUM;/ / 顶点向量AdjMatrix arcs; / 邻接矩阵int fMAX_VERTEX_NUM; / 各 单 位 去超市的频率；int vexnum,/ 图的当前顶点数arcnum;/ 图的当前弧数 MGraph;（3 ）记录从顶点集 U 到 V-U

32、 的代价最小的边的辅助数组的数据结构： typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;2. 算法的设计思想及流程图（1）主要函数的功能说明1. 若G中存在顶点u,则返回该顶点在图中位置 否则返回-1。int LocateVex（MGraph ,VertexType u）52. 数组（邻接矩阵 ）表示法,构造无向网 G。int Create(MGraph *) ； 由于要输入定点名称和权值来建立无向图，所以在此处要调用 locatevex(Mgraph,VertexType u) 找到对应该点名称的存储在

33、数组中的序 号int Create(MGraph *) ；3.or(i=0;iG.vexnum;i+)for(j=0;jarc.adj, 作 为新图 R 各边的权值，然后经由佛洛依德算法得到任意两点之间的最短路 径，存到数组 A 中( 2 ) 计 算 各 点 分 别 到 所 有 其 他 点 的 路 径 值 之 和 ， 即B0,B1,B2 .BG-vexnum(3) 再显示佛洛依德算法的计算过程，即显示各点到其他点的路径(无穷大 的权值对应的边不显示)(4 )根据计算出来的B数组的数组，选择出最小值，求出其对应下标所对 应的顶点名称，即为超市的最佳地址(2) 模块结构及流程图(3) 主要模块算法

34、描述【1】用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出 T的各条边void Min iSpa nTree_PRIM(MGraph,VertexType,i nt)构造出最小生成树后，利用数组 a (初始值各个元素为无穷大)存储 最小生成树各边的权值。【2.用佛洛依德算法求带权有向图的最短路径void Floyed(MGraph *,MGraph *)首先先将数组a的各个元素赋给新图R,作为新图R各边的权值，然后经由佛洛依德算法得到任意两点之间的最短路径，然后存到数组 A 中 将最小生成树的各点到其他点的距离相加, 存到数组 B 中。在通过对数组 B 元素的比较大小, 是最小值的那一

35、点即为最优点, 因为该点到其他点的距离 最小四、课程设计过程中的关键算法(1)佛洛依德算法表述：第一步,让所有路径加上中间顶点 1 ,取 Ai j 与 Ai1+A1j 中较小的 值作Aij的新值，完成后得到A(1),如此进行下去，当第k步完成后，A( k) ij表示从i到就且路径上的中间顶点的路径的序号小于或等于 k的最短路径长 度。当第 n-1 步完成后，得到 A(n-1 )， A(n-1 )即所求结果。 A(n-1 ) ij 表示从 i 到 j 且路径上的中点顶点的序号小于或等于 n-1 的最短路径长度，即 A(n-1)ij 表示从 i 到 j 的最短路径长度。代码如下：void Floy

36、ed(MGraph *G,MGraph *R)/ 带权有向图求最短路径 floyd 算法intAMAX_VERTEX_NUMMAX_VERTEX_NUM,BMAX_VERTEX_NUM,pathMAX_VERTEX_NUMMAX_VERTEX_NUM;int i,j,k,pre,min;int countMAX_VERTEX_NUM;for(i=0;ivexnum;i+)始化 A 和 path 数组for(j=0;jvexnum;j+)值；Aij=R-arcsij.adj; pathij=-1;counti=0; for(k=0;kvexnum;k+) 骤for(i=0;ivexnum;i+)

37、/ 初/ 置初/k 代表运算步for(j=0;jvexnum;j+)if(Aij(Aik+Akj)/ 从 i 经 j 到 k 的一条路径更短Aij=Aik+Akj;pathij=k;(2 )普里姆算法 :void MiniSpanTree_PRIM(MGraphG,VertexType u,intaMAX_VERTEX_NUMMAX_VERTEX_NUM)int i,j,k,m;minside closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;+j) / 辅助数组初始化if(j!=k)strcpy(closedgej.adjvex,u);/ 所有边依附的在 U 中 的顶点为 uclosedgej.lowcost=G.arcskj.adj;/ 所有节点 j 到 节点 k 的距离closedgek.lowcost=0; /初始 ,U=uprintf( 最小代价生成树的各条边为 :n);for(i=1;iG.vexnum;+i) / 选择其余 G.vexnum-1 个顶点k=minimum(closedge,G);