一、问题描述

    问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。

    测试数据：由读者指定,可自行指定一个马的初始位置。

    实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

二、实验目的

  熟练使用栈和队列解决实际问题；

（1）  了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

（2）  初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

（3）  提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

三、设计过程

算法设计思想：

根据分析先建了2个结构体

struct PosType     //马的坐标位置类型

{

    int m_row;     //行值

    int m_col;      //列值

};

struct DataType     //栈的元素类型

{

    PosType seat;    //马在棋盘中的“坐标位置”

    int di;         //换方向的次数

};

chess::chess()

bool chess::chessPath(PosType start) //在棋盘中进行试探寻找下一步位置并同时记录位置，以及涉及到的入栈出栈

void chess::Print() //打印马走的路径

PosType chess::NextPos(PosType a,int di)//根据当前点的位置a和移动方向di，试探下一位置

（1）、位置的存储表示方式

typedef struct

    {

        int x;

        int y;

        int from;

}Point;

（2）、栈的存储方式

#define STACKSIZE 70

#define STACKINCREASE 10

typedef struct Stack

{

       Point *top;

       Point *base;

       int stacksize;

};

（3）设定栈的抽象数据类型定义：

 ADT Stack {

     数据对象：D=｛a_i | a_i∈ElemSet,i=1,2,…,n,n≥0｝

     数据关系：R1={<a_i-1 , a_i>|a_i-1, a_i∈D,i=2,…,n}

               约定a_n端为栈顶，a_i端为栈顶。

     基本操作：

             InitStack(&s)

         操作结果：构造一个空栈s，

             DestroyStack(&s)

         初始条件：栈s已存在。

         操作结果：栈s被销毁。

             ClearStack(&s)

         初始条件：栈s已存在。

         操作结果：栈s清为空栈。

             StackEmpty(&s)

         初始条件：栈s已存在。

         操作结果：若栈s为空栈，则返回TRUE，否则返回FALSE。

             StackLength(s);

         初始条件：栈s存在。

         操作结果：返回s的元素个数，即栈的长度。

             GetTop (s,&e);

         初始条件：栈s已存在且非空。

         操作结果：用e返回s的栈顶元素。

             Push(&s,e)

         初始条件：栈s已存在。

        操作结果：插入元素e为新的栈顶元素。

            Pop(&s,&e)

        初始条件：栈s存在且非空。

        操作结果：删除栈顶元素，并用e返回。

            stackTraverse(s,visit())

       初始条件：栈s存在且非空。

       操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败，则操作失败。

}ADT Stack

四、功能测试

    如下图：输入1   5进行数据测试，

测试成功！

五、实验总结与体会

          

根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：

1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。

2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。

3、认真上好专业实验课，多在实践中锻炼自己。

4、写程序的过程中尽量在正确的基础上追求简洁。

5、在做设计的时候要有信心，有耐心，切勿浮躁。

6、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，不过也不能完全依赖课本。

7、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。            

六、参考文献

万健主编，数据结构实用教程（C++版），电子工业出版社，2011

课本《数据结构》

七、源代码

#include <iostream>

using namespace std;

#include "SqStack.h"

struct PosType     //马的坐标位置类型

{

    int m_row;     //行值

    int m_col;      //列值

};

struct DataType     //栈的元素类型

{

    PosType seat;    //马在棋盘中的“坐标位置”

    int di;         //换方向的次数

};

class chess

{

    public:

            chess();

            bool chessPath(PosType);

            void Print();

    private:

            PosType NextPos(PosType c , int d );

            int m_chess[8][8];    // 棋盘数组

   

};

chess::chess()

{

    int i,j;

    for(i=0;i<=7;i++)

    for(j=0;j<=7;j++)

    m_chess[i][j]=0;

}

bool chess::chessPath(PosType start)

{

    SqStack<DataType> path(64);     //创建栈

    PosType curpos;

    DataType e;

   

    curpos=start ;

    int curstep=1;   //第几次走的位置

        do{

            if(curpos.m_row<=7 && curpos.m_row>=0 &&

                curpos.m_col>=0 && curpos.m_col<=7)//走在棋盘之内

            {   if(m_chess[curpos.m_row][curpos.m_col]==0){

       

                m_chess[curpos.m_row][curpos.m_col]=curstep; //留下足迹，标注当前位置是马第几次走

       

                e.seat.m_row=curpos.m_row;       

       

                e.seat.m_col=curpos.m_col;

       

                e.di=0;

                path.Push(e);    //当前位置和方向入栈

                curstep++;

                if(curstep==65)

                return true;

        curpos=NextPos(curpos,e.di); }

        else

            curpos=NextPos(curpos,e.di++); //在棋盘之外自动进行下一次试探

    }

    else{              //当前位置已走过   

        if(!path.Empty()){

            e=path.Top();

            path.Pop();

            curstep--;

            while(e.di==7 && !path.Empty()){    //该位置已无路可走

                m_chess[e.seat.m_row][e.seat.m_col]=0;

               

                e=path.Top();               //退回一步

               

                path.Pop();        

                curstep--;

            }

            if(e.di<7){         //没到可能的最后一个位置

                e.di++;          //换下一个位置

                path.Push(e);

                curstep++;

                curpos=NextPos(e.seat,e.di);

            }

        }

    }

}while(curstep<=64); //马已经走的步数

return false;

}

void chess::Print()

{

    int i,j;

    for(i=0;i<8;i++)

        {for(j=0;j<8;j++)

       

        cout<<m_chess[i][j]<<'\t';  //输出对齐，水平制表

       

        cout<<endl;}

       

    cout<<endl;

   

}

PosType chess::NextPos(PosType a,int di)//根据当前点的位置a和移动方向di，试探下一位置

{

    PosType direct[8]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

    //按照顺时针试探的8个位置

    a.m_row+=direct[di].m_row;

    a.m_col+=direct[di].m_col;

    return a;

}

void main()

{

    PosType first;

    chess chess;

    cout<<"请输入马的初始位置（第几行第几列):";

    cin>>first.m_row>>first.m_col;

    chess.chessPath(first);

    cout<<"马走过的一条路径如下："<<endl;

    chess.Print();

}

#define _SQSTACK_H_

//定义顺序栈类

template <class ElemType>//声明一个类模板

class SqStack

{

public:                     //顺序栈类的各成员函数

    SqStack(int m = 100);    

    ~SqStack();

   void Clear();

    bool Empty() const;

   int Length() const;

   ElemType & Top() const;

   void Push(const ElemType &e);

   void Pop();

private:                   //顺序栈类的数据成员

    ElemType *m_base;     //基地址指针

    int m_top;            //栈顶指针

    int m_size;           //向量空间大小

};

//构造函数，分配m个结点的顺序空间，构造一个空的顺序栈。

template <class ElemType>

SqStack <ElemType>::SqStack(int m)

{

    m_top = 0;

    m_base = new ElemType[m];

    m_size = m;

}//SqStack

//析构函数，将栈结构销毁。

template <class ElemType>

SqStack <ElemType>::~SqStack()

{

    if (m_base != NULL) delete[] m_base;

}//~SqStack

//清空栈。

template <class ElemType>

void SqStack <ElemType>::Clear()

{

    m_top = 0;

}//Clear

//判栈是否为空，若为空，则返回true，否则返回false。

template <class ElemType>

bool SqStack <ElemType>::Empty() const

{

    return m_top == 0;

}//Empty

//求栈的长度。

template <class ElemType>

int SqStack <ElemType>::Length() const

{

    return m_top;

}//Length

//取栈顶元素的值。先决条件是栈不空。

template <class ElemType>

ElemType & SqStack <ElemType>::Top() const

{

    return m_base[m_top - 1];

}//Top

//入栈，若栈满，则先扩展空间。插入e到栈顶。

template <class ElemType>

void SqStack <ElemType>::Push(const ElemType &e)

{

    if(m_top >= m_size){            //若栈满，则扩展空间。

        ElemType *newbase;

        newbase = new ElemType[m_size + 10];

        for(int j = 0; j < m_top; j++)

            newbase[j] = m_base[j];  

        delete[] m_base;

        m_base = newbase;

        m_size += 10;

    }

    m_base[m_top++] = e;

}//Push

//出栈，弹出栈顶元素。先决条件是栈非空。

template <class ElemType>

void SqStack <ElemType>::Pop()

{

    m_top--;

}//Pop 

   

 

第二篇：《数据结构课程设计》最短路径问题实验报告

目  录

  

一、概述......................................... 1

二、系统分析..................................... 1

三、概要设计..................................... 2

四、详细设计..................................... 5

4.1建立图的存储结构........................... 5

4.2单源最短路径............................... 6

4.3任意一对顶点之间的最短路径.................. 7

五、运行与测试................................... 8

参考文献........................................ 11

附录............................................ 12

交通咨询系统设计（最短路径问题）

一、概述   

    在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析

设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

三、概要设计

可以将该系统大致分为三个部分：  

①　建立交通网络图的存储结构；

②　解决单源最短路径问题；

③　实现两个城市顶点之间的最短路径问题。

 

迪杰斯特拉算法流图：

弗洛伊德算法流图：

 

四、详细设计

    4.1建立图的存储结构

定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点的信息）。

邻接矩阵的存储结构：

#define MVNum 100 //最大顶点数

typedef struct

{

     VertexType vexs[MVNum];//顶点数组，类型假定为char型

     Adjmatrix  arcs[MVNum][MVNum];//邻接矩阵，假定为int型

}MGraph;

注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。

4.2单源最短路径

单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最短路径。

迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。

算法思想：设有向图G=(V,E)，其中V={1,2，……n}，cost是表示G的邻接矩阵，

    cost[i][j]表示有向边<i,j>的权。若不存在有向边<i,j>，则cost[i][j] 的权为无穷大（这里取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点V₁为源点，集合S的初态只包含顶点V₁。数组dist记录从源点到其它各顶点当前的最短距离，其初值为dist[i]= cost[i][j]，i=2，……n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w] 的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。

    最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。    

4.3任意一对顶点之间的最短路径

    任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(V≠W)”，找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间的最短路径。

    费洛伊德算法的基本思想：假设求从V_i到V_j的最短路径。如果存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径<v_i,v₁>和<v₁,v_j>是否存在。如果存在，则比较路径<v_i.v_j>和<v_i,v₁,v_j>的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于1的最短路径。其次，考虑从v_i到v_j是否包含有顶点v₂为中间顶点的路径< v_i,…,v₂,…,v_j>，若没有，则说明从v_i到v_j的当前最短路径就是前一步求出的；若有，那么<v_i,…,v₂,…,v_j>可分解为<v_i,…,v₂>和<v₂,…,v_j>，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径<v_i,…,v₂,…v_j>的长度。将该长度与前一次中求得的从v_i到v_j的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从v_i到v_j的中间顶点序号不大于2的最短路径。依此类推……直至顶点v_n加入当前从v_i到v_j的最短路径后，选出从v_i到v_j的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以v_i到v_j的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是v_i到v_j的最短路径。

五、运行与测试

测试实例1：利用如下图所示的有向图来测试

                   

 

测试实例2：利用下图求交通网络图（无向图）的最短路径。

 

实例1运行结果：

实例2运行结果：

六、总结与心得

该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心的各种问题（当然此次试验最终主要解决的问题是：最短路径问题）。

这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为重要。

经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉算法、弗洛伊德算法等，对树的学习有了一个更深的了解。

参考文献

【1】《数据结构》严蔚敏.清华大学出版社.

【2】《数据结构课程设计》苏仕华.极械工业出版社.

附录

#include<stdio.h>

#include<stdlib.h>

#define MVNum 100

#define Maxint 32767

enum boolean{FALSE,TRUE};

typedef char VertexType;

typedef int Adjmatrix;

typedef struct{

       VertexType vexs[MVNum];

       Adjmatrix arcs[MVNum][MVNum];

}MGraph;

int D1[MVNum],p1[MVNum];

int D[MVNum][MVNum],p[MVNum][MVNum];

void CreateMGraph(MGraph * G,int n,int e)

{

       int i,j,k,w;

       for(i=1;i<=n;i++)

              G->vexs[i]=(char)i;

       for(i=1;i<=n;i++)

              for(j=1;j<=n;j++)

                     G->arcs[i][j]=Maxint;

              printf("输入%d条边的i.j及w:\n",e);

              for(k=1;k<=e;k++){

                     scanf("%d,%d,%d",&i,&j,&w);

                     G->arcs[i][j]=w;

              }

              printf("有向图的存储结构建立完毕！\n");

}

void Dijkstra(MGraph *G,int v1,int n)

{

       int D2[MVNum],p2[MVNum];

       int v,i,w,min;

       enum boolean S[MVNum];

       for(v=1;v<=n;v++){

              S[v]=FALSE;

            D2[v]=G->arcs[v1][v];

               if(D2[v]<Maxint)

               p2[v]=v1;

       else

               p2[v]=0;

       }

       D2[v1]=0; S[v1]=TRUE;

       for(i=2;i<n;i++){

              min=Maxint;

              for(w=1;w<=n;w++)

                     if(!S[w] && D2[w]<min)

                     {v=w;min=D2[w];}

                     S[v]=TRUE;

                     for(w=1;w<=n;w++)

                            if(!S[w] && (D2[v]+G->arcs[v][w]<D2[w])){

                                   D2[w]=D2[v]+G->arcs[v][w];

                                   p2[w]=v;

                            }

                     }

       printf("路径长度   路径\n");

       for(i=1;i<=n;i++){

              printf("%5d",D2[i]);

              printf("%5d",i);v=p2[i];

              while(v!=0){

                     printf("<-%d",v);

                     v=p2[v];

              }

              printf("\n");

       }

}

void Floyd(MGraph *G,int n)

{

       int i,j,k,v,w;

       for(i=1;i<=n;i++)

              for(j=1;j<=n;j++)

              {

                     if( G->arcs[i][j]!=Maxint)

                            p[i][j]=j;

                     else

                            p[i][j]=0;

                     D[i][j]=G->arcs[i][j];

              }

              for(k=1;k<=n;k++)

              {

                     for(i=1;i<=n;i++)

                            for(j=1;j<=n;j++)

                            {

                                   if(D[i][k]+D[k][j]<D[i][j])  {

                                          D[i][j]=D[i][k]+D[k][j];

                                          p[i][j]=p[i][k];

                                   }

                            }

              }

}

void main()

{

       MGraph *G;

       int m,n,e,v,w,k;

       int xz=1;

       G=(MGraph *)malloc(sizeof(MGraph));

       printf("输入图中顶点个数和边数n,e:");

       scanf("%d,%d",&n,&e);

       CreateMGraph(G,n,e);

              while(xz!=0){

                     printf("************求城市之间最短路径************\n");

                     printf("=========================================\n");

                     printf("1.求一个城市到所有城市的最短路径\n");

                     printf("2.求任意的两个城市之间的最短路径\n");

                     printf("=========================================\n");

                     printf("请选择 :1或2，选择0退出:\n");

                     scanf("%d",&xz);

                            if (xz==2){

                            Floyd(G,n);

                            printf("输入源点（或起点）和终点:v,w:");

                            scanf("%d,%d",&v,&w);

                            k=p[v][w];

                            if (k==0)

                                   printf("顶点%d  到  %d  无路径!\n",v,w);

                            else

                            {

                                   printf("从顶点%d  到  %d  最短路径路径是:%d",v,w,v);

                                   while (k!=w){

                                          printf("--%d",k);

                                          k=p[k][w];

                                   }

                                   printf("--%d",w);

                                   printf("径路长度:%d\n",D[v][w]);

                            }

                     }

                     else

                            if(xz==1)

                                   printf("求单源路径，输入源点v :");

                            scanf("%d",&v);

                            Dijkstra(G,v,n);

             

       }

       printf("结束求最短路径，再见!\n");

}