马踏棋盘——一个数据结构综合实验案例新解

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

马踏棋盘实验报告

西安郵電學院 数据结构 课内实验报告书 院系名称：计算机学院 实验题目：马踏棋盘 学生姓名： 专业名称：计算机科学与技术班级： 学号： 时间： 2011年10月10日指导教师：曾艳

一、实验题目：马踏棋盘 二、实验目的： 通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。 三、实验要求： 设计一个国际象棋的马踏遍棋盘的演示程序。 要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之 四、设计与实现过程 （1）栈或队列的定义及其主要操作的实现 struct Chess { int x; int y; int h;/*h记录下一次需要试探的马字格式的下标值*/ }Chess1[65]; （2）主要算法的描述 void Handlechess(int m,int n) { int flag=1,i; double j=0.0;/*增加了j用于统计while循环的执行次数，很好奇循环到底执行了多少次*/ int chessx[8]={-2,-2,-1,-1,1,1,2,2};/*马字的格式的8个位置，按下标序依次试探*/ int chessy[8]={-1,1,-2,2,-2,2,-1,1}; for(i=1;i<=64;i++) Chess1[i].h=0;/*赋初值*/ chess[m][n]=flag; Chess1[flag].x=m; Chess1[flag].y=n; while(flag<64) { j+=1.0; for(i=Chess1[flag].h;i<8;i++)/*i的初值由Chess1[flag].h确定*/ { m=Chess1[flag].x+chessx[i]; n=Chess1[flag].y+chessy[i]; if((m>=0&&m<=7&&n>=0&&n<=7)&&(chess[m][n]==0))/*去掉了函数，改为直接用关系表达式判断，提高运行速度*/ { Chess1[flag].h=i+1;/*h记录下一次需试探马字格式位置的下标*/ flag++;

实验报告 马踏棋盘

2.4题马踏棋盘 题目：设计一个国际象棋的马踏棋盘的演示程序 班级：姓名：学号：完成日期： 一．需求分析 （1）输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y， X和Y的范围都是[1,8]。 （2）输出形式： 以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的 棋盘。 （4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结 果。数据可以任定，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。 二．概要设计 （1）、位置的存储表示方式 （2） 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; }; （1）、设定栈的抽象数据类型定义： ADT Stack { 数据对象：D=｛ai | ai∈ElemSet,i=1,2,…,n,n≥0｝ 数据关系：R1={|ai-1, ai∈D,i=2,…,n} 约定an端为栈顶，ai端为栈顶。 基本操作： InitStack(&s) 操作结果：构造一个空栈s， DestroyStack(&s) 初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&s) 初始条件：栈s已存在。

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

马踏棋盘数据结构实践报告

马踏棋盘问题 摘要： 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。理解栈的“后进先出”的特性以及学会使用回溯。 关键字：马踏棋盘、递归、栈、回溯 1．引言 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。 编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2….64依次填入一个8X8的方阵，并输出它的行走路线。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 2．需求分析 （1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。 （2）输入马的起始位置，必须保证输入的数字在规定范围内，即0<=X<=7,0<=Y<=7。 （3）保证马能走遍整个棋盘，并且不重复。

（4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。 3．数据结构设计 采用栈数组为存储结构。 #define maxsize 100 struct { int i; int j; int director; }stack[maxsize]; 4．算法设计 4.1 马的起始坐标 void location(int x,int y) //马的位置坐标的初始化 { top++; stack[top].i=x; //起始位置的横坐标进栈 stack[top].j=y; //起始位置的竖坐标进栈 stack[top].director=-1;

a[x][y]=top+1; //标记棋盘Try(x,y); //探寻的马的行走路线 } 4.2 路径探寻函数 void Try(int i,int j) { int count,find,min,director; int i1,j1,h,k,s; int b[8]={-2,-2,-1,1,2,2,1,-1},c[8]={1,-1,-2,-2,-1,1,2,2} ; //存储马各个出口相对当前位置行、列坐标的增量数组 int b2[8],b1[8]; for(h=0;h<=7;h++) //用数组b1[8]记录当前位置的下一个位置的可行路径的条数 { count=0; i=stack[top].i+c[h]; j=stack[top].j+b[h]; if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0) //如果找到下一个位置 { for(k=0;k<=7;k++) { i1=i+c[k]; j1=j+b[k]; if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1]

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

马踏棋盘分析文档

数据结构课程设计 题目：马踏棋盘 院系： 班级： 学号： 姓名： 2014-2015年度第1学期

马踏棋盘 一．题目：马踏棋盘 (3) 二. 设计目标 (3) 三. 问题描述 (3) 四. 需求分析 (4) 五. 概要设计 (4) 第一步：定义四个常量和一个数据类型 (4) 第二步：构造函数 (4) 六. 详细设计（给出算法的伪码描述和流程图） (5) 流程图设计 (5) 代码分析 (9) 第一步：定义常量与变量 (9) 第二步：构造函数 (9) ●定义一个结构体类型 (9) ●创建一个初始化函数 (10) ●创建提示输入函数 (10) ●创建产生新节点函数 (11) ●创建计算路径函数 (12) ●创建入栈函数 (13) ●创建出栈函数 (13) ●创建输出函数 (13)

第三步：在主函数中调用其它函数 (15) 七. 测试分析 (16) 八. 使用说明 (16) 九. 测试数据 (16) 十．课程设计总结 (17) 一．题目：马踏棋盘 二. 设计目标 帮助学生熟练掌握顺序栈的基本操作，让学生深入了解栈的使 用，使得更深层次的灵活运用栈。 三. 问题描述 ○所谓的马踏棋盘是：将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1、2、…、64依次填入一个8X8的方阵并输出。 从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过。如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个路点的可扩展路数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构 马踏棋盘 设计报告

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目： 姓名： 院系： 专业： 年级： 学号： 指导教师： 2011年月日

目录 1、程序设计的目的 2、设计题目 3、分析 4、设计思想 5、算法 6、测试结果 7、调试分析 8、小结 1、课程设计的目的 1、熟练使用C++语言编写程序，解决实际问题； 2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、学习并熟悉栈的有关操作； 6、利用栈实现实际问题； 2、设计题目 【马踏棋盘】 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳

策略”，以减少回溯的次数。 3、分析 确定输入值的范围，输入马的初始行坐标X和Y，X和Y的范围都是1到8之间。程序的功能是输出马走的步骤，要使马从任一起点出发，通过程序能找到下一个地点，然后遍历整个棋盘。每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。输出时可以用二维数组。 4、设计思想 输入马初始位置的坐标。将初始位置进栈，经过一个while循环，取出符合条件的栈顶元素。利用函数，找出栈顶元素周围未被占用的新位置，如果有，新位置入栈；否则弹出栈顶元素。再进行判断，最后输出。 位置的存储方式，栈的存储方式和一些操作函数为： #include #ifndef STACK_H #define STACK_H struct Point { int x; int y; int from; }; #define STACKSIZE 70 #define STACKINCREASE 10 struct Stack { Point *top; Point *base; int length;

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨

实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构课程设计报告_马踏棋盘

. 杭州师范大学钱江学院课程设计 题目马踏棋盘算法研究 教学院信息与机电工程分院 专业计算机科学与技术 班级计算机1201 姓名吴秋浩 指导教师王李冬 2013 年12 月21 日

目录 一．概述 (3) 二．总体方案设计 (3) 三．详细设计 (4) 四．最终输出 (7) 五．课程设计总结 (11) 参考文献 (15)

一概述 1.课程设计的目的 （1）课题描述 设计一个国际象棋的马踏遍棋盘的演示程序。 （2）课题意义 通过“马踏棋盘”算法的研究，强化了个人对“栈”数据结构的定义和运用，同时也锻炼了自身的C语言编程能力。另一方面，通过对“马踏棋 盘”算法的研究，个人对“迷宫”、“棋盘遍历”一类的问题，有了深刻 的认识，为今后解决以此问题为基础的相关的问题，打下了坚实的基础。 （3）解决问题的关键点说明 解决问题的关键首先要熟练掌握C语言编程技术，同时能够熟练运用“栈”数据结构。另外，态度也是非常重要的。在课程设计过程中，难免 会遇到困难，但是不能轻易放弃，要肯花时间，能静得下心，积极查阅相 关资料，积极与指导老师沟通。 2.课程设计的要求 （1）课题设计要求 将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方 格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1， 2，…，64依次填入一个8×8的方阵，输出之。 程序由回溯法和贪心法实现，比较两种算法的时间复杂度。 （2）课题设计的思路 首先，搞清楚马每次在棋盘上有8个方向可走，定义两个一位数组，来存储马下一着点的水平和纵向偏移量。程序再定义一个8*8二维数组，初始 所有元素置0，起始点元素置1。若为回溯法，初始方向数据（一维数组下 标）入栈。随后，马从起始点开始，每次首先寻找下一可行的着点，然后记 下方向，方向数据入栈，把该位置元素置为合适的序列号，若无下一可行着 点，则回溯，寻找下一方向位置着点，以此类推，直到64填入数组中，则 输出二维数组，即为马可走的方案。若为贪婪法，选择下一出口的贪婪标准 是在那些允许走的位置中，选择出口最少的那个位置。直到没有下一着点位 置，若此时已标记到64，则找到可行方案，输出之。反之，改变初始寻找方 向继续寻找，直到8种方向顺序都试过，若还是没有合适的方案，则说明以 该起始 点开始马无法踏遍棋盘。

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;

马踏棋盘c报告 数据结构课程设计

实现顺序栈或循环队列的存储 一、实验目的 （1）、理解栈的特性“后进先出”和队列的特性“先进先出”。 （2）、仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。 （3）、在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。 二、实验环境 （1）Windows XP系统下 （2）编程环境：VC6.0++ 三、实验内容 （1）、要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（棋盘如图所示）。 （2）、输入：任意一个起始位置； 输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 （3）、数据结构要求：采用顺序栈或者链栈实现。

四、实验步骤 为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。 （一）、概要设计 （1）、顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={a i| a i∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={< a i-1, a i >| a i-1, a i∈D,i=1,2，…，n} } ADT Stack （2）本程序包含三个模块： 1、主程序模块： void main(){ 定义变量； 接受命令； 处理命令； 退出； } 2、起始坐标函数模块——马儿在棋盘上的起始位置； 3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； 4、输出路径函数模块——输出马儿行走的路径； 各模块之间的调用关系： 主程序模块 输入的初始位置是否正确 否 是 起始坐标函数模 探寻路径函数模 输出路径函数模 结束 （二）、详细设计

数据结构实验报告 - 答案汇总

数据结构(C语言版) 实验报告

专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存

马踏棋盘课程设计实验报告

《数据结构》 课 程 设 计 实 验 报 告 课程名称：《数据结构》课程设计 课程设计题目：马踏棋盘 姓名：邱可昉 院系：计算机学院 专业：计算机科学与技术 班级：10052313 学号：10051319 指导老师：王立波 2012年5月18日

目录 1.课程设计的目的 (3) 2.问题分析 (3) 3.课程设计报告内容 (3) （1）概要设计 (3) （2）详细设计 (3) （3）测试结果 (5) （4）程序清单 (6) 4.个人小结 (10)

1.课程设计的目的 《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。 2.问题分析 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。 3.课程设计报告内容 （1）概要设计 定义一张棋盘，定义一个栈保存马走的路径的点坐标和来自方向，用函数计算周围可走坐标，并检查正确性，当周围没有可走格子时退栈到最优位置，继续进行，然后将路径输出。 （2）详细设计 定义结构体，方向数组和Qioan类 struct Point { int x; //记录横坐标 int y; //记录纵坐标 int from; //前一个位置的方向 }; Point side[8]={0,0,0}; //记录可能的方向坐标 class Qipan{ public: Qipan(); ~Qipan(); void Setside(Point); //设置方向坐标 bool Getside(int,Point &); //将指定方向的坐标给特定指针 bool HorseVisit(Point); //输入开始点运行棋盘 bool Pass(Point); //输出路径 private: int **gezi; //棋盘格子 };

数据结构实验报告(图)

附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的,）。 邻接矩阵——表示顶点间相联关系的矩阵 设G=(V,E) 是有n 1 个顶点的图，G 的邻接矩阵A 是具有以下性质的n 阶方阵特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 9

无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图；

数据结构实验报告马踏棋盘

目录 1 课程设计的目的 (x) 2 需求分析 (x) 3 课程设计报告内容 (x) 1、概要设计 (x) 2、详细设计 (x) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (x) 6、程序清单 (x) 4 小结 (x) 5 参考文献 (x) 2011年5月23日 1、课程设计的目的 （1）熟练使用栈和队列解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。 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，试探下一位置 4、总结 一、这次课程设计的心得体会通过实践我的收获如下： 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。 二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中尽量在正确的基础上追求简洁。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用，不过也不能完全依赖课本。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 6、参考文献 （1）万健主编，数据结构实用教程（C++版），电子工业出版社，2011 （2）网上搜索相关程序作为参考 7、程序运行结果：

马踏棋盘

马踏棋盘 学院 专业 学号 学生姓名 指导教师 年月日

摘要： 国际象棋想必大家都玩过，但你有没有想过，让一个“马”遍历国际象棋8*8的棋盘，有没有可能？如果有可能，在给定起点的情况下，有多少种可能？下面，我们将用计算机来模拟“马”对棋盘的遍历. 关键字： 回溯算法贪心算法遍历 正文： 已知国际象棋为8×8棋盘，共64个格，规则中，马按 照如图所示规则移动。将马放在任意方格中，令马遍历每个方 格一次且仅一次，编制非递归程序，将数字1，2， (64) 照马的行走路线依次填入一个8×8的方阵，并输出结果。 通过结合图示，我们不难发现，当马的起始位置（i,j） 确定的时候，可以走到下列8个位置之一： (i-2,j+1)、(i-1,j+2)、(i+1,j+2)、(i+2,j+1)、(i+2,j-1)、 (i+1,j-2)、(i-1,j-2)、(i-2,j-1) 但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不可达的位置。8个可能位置可以用一维数组Htry1[0…7]和HTry2[0..7]来表示： Htry1： 0 1 2 3 4 5 6 7 -2 -1 1 2 2 1 -1 -2 Htry2： 0 1 2 3 4 5 6 7 1 2 2 1 -1 -2 -2 -1 所以位于（i,j）的马可以走到新位置是在棋盘范围内的（i+ Htry1[h],j+Htry2[h]）,其中h的取值是0~7. 整个问题，我们可以用两种算法来解决，既“回溯算法”与“贪心算法”我们先来看回溯算法： 搜索空间是整个棋盘上的8*8个点.约束条件是不出边界且每个点只能经过

数据结构课程设计 马踏棋盘求全部解及演示程序

安徽工程大学信息10 课程设计 马踏棋盘的求解及演示设计 摘要 数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。 马踏棋盘问题，实际上是图论中的哈密顿通路问题，是典型的NP问题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍历采用算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对所有路径的搜索。在调试过程发现，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个点都也只有168步，所以求出所有路径在不到一秒的时间内完成。 关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法；

目录 马踏棋盘的求解及演示设计......................... 错误！未定义书签。目录........................................... 错误！未定义书签。第一章引言................................. 错误！未定义书签。第二章需求分析................................. 错误！未定义书签。 2.1问题描述....................................... 错误！未定义书签。 2.2基本要求....................................... 错误！未定义书签。 2.3具体需求....................................... 错误！未定义书签。 2.4开发环境....................................... 错误！未定义书签。第三章概要设计................................. 错误！未定义书签。 3.1 系统概述....................................... 错误！未定义书签。 3.2 系统描述....................................... 错误！未定义书签。 3.3逻辑设计....................................... 错误！未定义书签。第四章详细设计................................. 错误！未定义书签。 4.1 功能模块设计.................................. 错误！未定义书签。 4.2 数据结构设计.................................. 错误！未定义书签。 4.3算法设计....................................... 错误！未定义书签。第五章调试与分析............................... 错误！未定义书签。 5.1 调试分析....................................... 错误！未定义书签。第六章系统试用说明............................. 错误！未定义书签。 6.1 系统试用说明................................... 错误！未定义书签。第七章总结与体会............................... 错误！未定义书签。参考文献......................................... 错误！未定义书签。