数据结构实验报告——

迷宫求解问题实验

上机环境： DevC++

二、程序设计相关信息

（1）实验题目：迷宫求解问题

问题描述：

实验题3.5  改进3.1.4节中的求解迷宫问题程序，要求输出如图3.14所示的迷宫的所有路径，并求最短路径长度及最短路径。

 

（2）实验项目组成：

本项目由一个原程序mg.cpp及mg.exe文件组成。

（3）实验项目的程序结构：

函数调用关系图：

 

（4）实验项目包含的函数的功能描述：

mg[M+1][N+1]    //构造迷宫二维数组，1表示墙不可走方块，0表示通道

mgpath(int xi,int yi,int xe,int ye) 

//求解路径为：（xi,yi）->（xe,ye）

//采用顺序栈存储，进栈，回溯，退栈等

（5）算法描述：

求解迷宫从入口到出口的所有路径，从入口出发，顺某一个方向向前试探，对于可走的方块都进栈，并将这个可走发方位保存，且top+1，然后试探下一个方块，若下一个方块能走通则继续，否则则回溯到前一个方块，且top-1。为记录所有的路径调用Path[k]=Stack[k]记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。最后比较top值找到一条最短路径并输出。

试探路径过程的算法利用了“广度优先搜索遍历”算法。

流程图：

 

（6）实验数据：

迷宫数组如下：

int mg[M+1][N+1]={

    {1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},

    {1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};

实验结果：

三、程序代码：

#include <stdio.h>

#include <stdlib.h>

#define M 6

#define N 6

#define Maxsize 100

int mg[M+1][N+1]={

    {1,1,1,1,1,1},

    {1,0,0,0,1,1},

    {1,0,1,0,0,1},

    {1,0,0,0,1,1},

    {1,1,0,0,0,1},

    {1,1,1,1,1,1}

};

struct

{

    int i;

    int j;

    int di;

    }Stack[Maxsize],Path[Maxsize];

int top=-1;

int count=1;

int min=Maxsize;

int mgpath()

{

    int i,j,di,find,k;

    top++;

    Stack[top].i=1;

    Stack[top].j=1;

    Stack[top].di=-1;

    mg[1][1]=-1;

    printf("迷宫所有路径如下:\n");

    while(top>-1)

     {

        i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;

        if(i==M-2&&j==N-2)

        {

           printf("%4d:",count++);

           for(k=0;k<=top;k++)

              {

              printf("(%d,%d)",Stack[k].i,Stack[k].j);

              if((k+1)%5==0)

              printf("\n     ");

              }

           printf("\n");

                if(top+1<min)

                {

                for(k=0;k<=top;k++)

                Path[k]=Stack[k];

                min=top+1;

                }

            mg[Stack[top].i][Stack[top].j]=0;

              top--;

            i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;

        }

        find=0;

        while(di<4&&find==0)

            {

            di++;

            switch(di)

            {

            case 0:i=Stack[top].i-1;j=Stack[top].j;break;

            case 1:i=Stack[top].i;j=Stack[top].j+1;break;

            case 2:i=Stack[top].i+1;j=Stack[top].j;break;

            case 3:i=Stack[top].i;j=Stack[top].j-1;break;

            }

            if(mg[i][j]==0)find=1;

            }

            if(find==1)

            {

                Stack[top].di=di;

                top++;

                Stack[top].i=i;

                Stack[top].j=j;

                Stack[top].di=-1;

                mg[i][j]=-1;

            }

            else

            {

                mg[Stack[top].i][Stack[top].j]=0;

                top--;

            }

        }

        printf("\n");

        printf("最短路径如下：\n");

        printf("路径最短长度：%d\n",min);

        printf("最短路径路径：\n");

        for(k=0;k<min;k++)

        {

            printf("(%d,%d)",Path[k].i,Path[k].j);

        }

        printf("\n\n");

                   }

int main()

{

  mgpath();

  system("PAUSE");

  return 0;

}

 

第二篇：武汉大学考研数据结构

1.（5分）分析以下算法的时间复杂度（要求给出求解过程）。

void fun(int n)

{ int i,s=0;

while (s<n)

{

}

} i++; s+=i;

2.（5分）设b是二叉树（采用二叉链存储结构存储）的根结点指针，给出以下算法的递归模型并说明算法的功能：

int fun(BTNode *b)

{ if (b==NULL) return 0;

else if (b->lchild!=NULL && b->rchild!=NULL)

return fun(b->lchild)+fun(b->rchild)+1;

else

return fun(b->lchild)+fun(b->rchild);

}

3.（5分）有一个长度为12的有序表R[0..11]，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数是多少？（要求给出求解过程）

4.假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。

5.将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。

5.（4分）对于有n个顶点、e条边的图+

（1）若是无向图，采用邻接矩阵存储，其非零的元素有多少？

（2）若是有向图，采用邻接矩阵存储，其非零的元素有多少？

（3）若是无向图，采用邻接表存储，其表头结点和表结点个数是多少？

（3）若是有向图，采用邻接表存储，其表头结点和表结点个数是多少？

6．（3分）简要说明在执行快速排序算法时，若把栈换为队列会对最终排序结果有什么影响？

三. 算法设计题（共25分）

1. （10分）设有一个带头结点的单链表hc，设计一个算法：

void split(LinkList *hc, LinkList *&ha, LinkList *&hb,ElemType x,ElemType y)

将hc拆分成两个带头结点的单链表ha和hb，其中ha的所有结点值均大于等于x且小于等于y，hb为其他结点。

2．（15分）假设一棵二叉树采用二叉链存储结构进行存储，每个结点的类型如下（每个结点值均为正整数且大小均不同）：

typedef struct node

{ int data;

struct node *lchild,*rchild; /*左、右孩子结点指针*/

} BSTNode;

（1）（10分）设计一个算法int isBST(BSTNode *bt)，判断二叉树bt是否是一棵二叉排序树；

（2）（5分）说明你的算法的正确性。