《数据结构A》实验指导书2012版 - 马春江

数据结构实验指导书

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY

数据结构A 实验指导书

马春江 撰写 付勇智 审核

电气与信息工程学院计算机工程系

2013年12月

第 1 页 共 30 页

数据结构实验指导书

前言

数据结构课程开设8个必做的实验：

1、线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

2、堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

3、串基本操作的编程实现（2学时，验证型），掌握串的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、合并、剪裁等操作，存储结构可以在顺序结构或链接结构、索引结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

4、二维数组基本操作的编程实现（2学时，验证型），掌握数组的建立、读取数据、压缩存储等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

5、二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用链接结构，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

6、图基本操作的编程实现（2学时，验证型），掌握图的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构可以在顺序结构或链接结构中任选，也可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

7、查找技术的编程实现（2学时，综合型），掌握查找技术的编程实现，可以实现一种，也可以实现多种，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

8、排序技术的编程实现（2学时，综合型），掌握排序技术的编程实现，可以实现一种，也可以实现多种，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。

9、实验要求把每次实验的程序文本和运行结果存入到本人的用户目录下供实验老师检查。 10、对实验室要求是必须保证学生上机时人手一机;必须保证满足课程要求的上机时数;必须配备专职的《数据结构》课程的实验指导老师。

第 2 页 共 30 页

数据结构实验指导书

目录

实验一 线性表基本操作的编程实现??????????????????????? 4 实验二 堆栈和队列基本操作的编程实现????????????????????? 9 实验三 串基本操作的编程实现????????????????????????? 12 实验四 二维数组基本操作的编程实现?????????????????????? 16 实验五 二叉树基本操作的编程实现??????????????????????? 19 实验六 图基本操作的编程实现????????????????????????? 24 实验七 查找技术的编程实现?????????????????????????? 27 实验八 排序技术的编程实现?????????????????????????? 29

第 3 页 共 30 页

数据结构实验指导书

湖北汽车工业学院实验报告

班 号 学 号 姓 名 选课班中的序号 完成日期 年 月 日 至 节

实验一 线性表基本操作的编程实现

一、 实验目的

1.了解线性表的逻辑结构和存储结构的工作原理； 2.理解顺序表和链表的工作原理； 3.掌握顺序表和链表的程序设计；

二、实验要求

编程实现通用的线性表常用功能程序，其中插入数据和删除数据是必须实现的。存储结构由学生自己选择。 实验题目采用班级目标总体一致，细节由学生按照自己的能力随意拓展和提高，程序源码实现原创设计。 存储结构最简模式为：顺序存储，使用一维数组实现。鼓励使用链表结构，一般可以采用单链表结构，更加复杂的可以采用循环链表或双向链表结构。时间足够的情况下，希望把这些在课外全部自行编程实现。 界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程流畅。如果启用文件，则可以采用全程无界面设计模式。

原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件读入。

数据类型最简模式为：整数。其他依次鼓励使用的为：实数、字符、英语字符串、汉字字符串。

三、 实验内容

功能设计最简模式为：原始数据构建、全部数据遍历、插入数据、删除数据。其他的任何相关功能见参考教材，鼓励实现。

开发语言最简模式为：C语言。以下依次为更加鼓励的设计环境：C++（不带对象），C++（带对象），C++带图形包（带对象），C++ windows mfc（带对象）。

知识分布原始数据构建、全部数据遍历属于C语言。插入数据、删除数据涉及的循环程序设计属于C语言。但是插入数据、删除数据涉及的数据移动的必要性、移动的所有位置和数量控制、具体移动的过程、移动对于程序的时间效率产生的影响属于数据结构原理范畴。

重点实验内容图示

第 4 页 共 30 页

数据结构实验指导书

教材图 3-2 顺序表插入操作的示意图

教材图 3-3 顺序表删除操作的示意图

顺序表的操作关键是要把相关的坐标控制好，如合法的插入和删除位置的范围，移动数据两边的坐标值。完成任务最后要注意数据量的变化。

教材图 3-6 单链表中进行插入操作的示意图

教材图 3-7 单链表存储删除操作的示意图

链表编程主要是注意关键语句的次序相关性，注意不要出现“内存垃圾”，把握好修改链的节奏和语句。注意空间的结点的申请和释放。

重点实验内容参考源码 顺序表

returninfo seqlist::insert(int position,const int &item) //插入一个元素 {

第 5 页 共 30 页

数据结构实验指导书

if(count+1>=Maxsize) return overflow; //溢出处理 if(position<=0 || position>count+1) return range_error;

count++; //计数器加一 for(int i=count;i>=position;i--) //循环移动数据 { dataarray[i]=dataarray[i-1]; }

dataarray[position-1]=item; return success; }

returninfo seqlist::remove(int position) //删除一个元素 {

if(empty()) return underflow;

if(position<=0||position>count) return range_error;

for(int i=position-1;i

count--; //计数器减一 return success; }

链表

returninfo linklist::insert(int position,const int &item) //插入一个结点 { if(position<=0 || position>=count+2) return range_error;

node *newnodep=new node, *searchp=headp->next, *followp=headp; for(int i=1; inext; } newnodep->data=item; //给数据赋值 newnodep->next=followp->next; //注意此处的次序相关性 followp->next=newnodep; count++; //计数器加一 return success; }

returninfo linklist::remove(int position) //删除一个结点 { if(empty()) return underflow;

第 6 页 共 30 页

数据结构实验指导书

if(position<=0||position>=count+1) return range_error; node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后 for(int i=1; inext; } followp->next=searchp->next; //删除结点的实际语句 delete searchp; //释放该结点 count--; //计数器减一 return success; }

实验测试数据设计通过对各种数据的输入和输出的结果对比分析，证实所有的功能的正确性，特别是需要测试非法数据的响应情况。实验报告中需要提交这些数据以及结果和自己的分析。鼓励提出一些错误（Bug）报告和改进建议。

以下为一个小的测试数据范例：逻辑结构：线性表，存储结构：顺序，操作：插入。数据申请空间的下标范围：0-10，实际数据最后的位置6，0号单元可以启用，也可以不用或者使用其他的功能。测试地址必须包括：-5、-1、0、1、5、6、7、9、10、11、18等至少11个数据。也就是说插入或删除必须考虑意外的两种情况：1.顺序表在分配的地址空间中，但是范围超界，2.完全是不存在的地址。其他的正常的都需要测试：如正常的边界。如顺序表插入时，最后数据地址为5.则在6插入也是容许的。

数据构成的多态性

学生可以根据自己的实力实现下面的某一个要求或同时实现多种数据类型的实现。 1. 数据构成为字符。由单个大写字母构成结点名称。（小写字母自动换成大写字母） 2. 数据构成为字符串。由美国人的姓名组成。（可以为两个或三个单词，首字母大写） 3. 数据构成为中文字符串。由中文人名组成。

4. 数据构成为多个数据。如一个人的多种信息。如：学号、姓名、性别、课程名、分数等。（也可以自己设

计）

实验报告提示

实验报告主要按照以下的框架完成：

本次实验的实验方式、目标和其他背景信息。实验的逻辑结构和存储结构的基本概念和原理（最好附图）。实验的总体设计（功能和界面等，算法思路）。实验的程序设计细节或测试细节。实验的总收获清单：（包含弄懂的原理和一些结论、学会了新的一些语句或功能段源码、学会了新的测试方法和过程、学会了内部结构控制和一些软件设计规范的细节等等），实验的遗憾和下一步努力的方向（总结自己未能达成的目标和原因分析，提出可行的改进方案）。

报告中应该涉及界面截图、开发过程综述（花费时间、总语句数、调试过程）、开发总结、重点源码清单（本次实验仅仅为插入和删除）、致谢等。

第 7 页 共 30 页

数据结构实验指导书

在实验中受到其他同学的帮助时在报告最后的致谢中鼓励实名感谢。 实验提交文件约定

程序名一律类似为：

T1123-02-17-某某某-链表实验程序.cpp

所有信息之间为中横线。如果有文本文件，也是类似的结构： T1123-2-17-某某某-链表实验程序输入数据.txt T1123-2-17-某某某-链表实验程序输出数据.txt 报告电子版为T1123-2-17-某某某-实验报告01.doc

（必须涉及工程的时候请打包管理，但是最后的文件名和内部的文件名也需要如此管理。） 思考题

1. 线性表的顺序存储和链表存储的差异？优缺点分析？ 2. 那些操作引发了数据的移动？ 3. 算法的时间效率是如何体现的？

4. 链表的指针是如何后移的？如何加强程序的健壮性？ 实验使用参考书

本实验指导书主要参考书为：

《数据结构与程序构建》马春江 付勇智 孟繁军编著 ISBN 978-7-302-29404-7 清华大学出版社 2012年8月第1版

四、实验总结和体会

第 8 页 共 30 页

数据结构实验指导书

湖北汽车工业学院实验报告

班 号 学 号 姓 名 选课班中的序号 完成日期 年 月 日 至 节

实验二 栈和队列基本操作的编程实现

一 、 实验目的

1.了解栈和队列的逻辑结构和存储结构的工作原理； 2.理解栈和队列的用途； 3.掌握栈和队列的程序设计；

二、实验要求

由于本次实验涉及到栈和队列两种数据结构的原理，实验题目将按照分级和分类的方式提供，任何学生都可以选择其中之一或多个综合来达成对原理的理解。细节由学生按照自己的能力随意拓展和提高，程序源码实现原创设计。

存储结构最简模式为：顺序存储，使用一维数组实现。鼓励使用链表结构，一般可以采用单链表结构。时间足够的情况下，希望把这些在课外全部自行编程实现。特别是希望和第一次实验采取相反的策略进行选择，以此来提高自己对于不同的存储结构的熟练运用。

界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程流畅。如果启用文件，则可以采用全程无界面设计模式。

原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件读入。

数据类型最简模式为：整数。其他依次鼓励使用的为：实数、字符、英语字符串、汉字字符串。

三、 实验内容

功能设计难度系数分为五级制：1：很容易，2：较容易，3：有一定难度，4：难度较大，5：难度很大。 1.栈功能演示系统。难度系数：2

2.汉字回文字符串的判断程序。难度系数：3 3.十进制正整数转换为八进制的程序。难度系数：4 4.环状队列功能演示系统。难度系数：2

5.十进制正小数转换为八进制的程序。难度系数：3

6.用计算机自动产生作业名、申请时间和打印时间的随机数据，然后用队列管理，随时显示队列中的数据和已

第 9 页 共 30 页

数据结构实验指导书

经打印完毕的作业名。难度系数：4

开发语言最简模式为：C语言。以下依次为更加鼓励的设计环境：C++（不带对象），C++（带对象），C++带图形包（带对象），C++ windows mfc（带对象）。

知识分布界面的显示和控制、原始数据构建、全部数据遍历属于C语言。进栈和出栈、进队和出队等原理属于数据结构原理范畴。

重点实验内容图示

教材图 5-5 链栈的出栈操作示意图

教材图 5-4 链栈的进栈操作示意图

讨论的初始状态

相对初始状态进栈444的效果 相对初始状态出栈333的效果 教材图 5-2 顺序栈的进栈、出栈示意图

空环队

入队9次，出队4次 再入队3次，出队3次

图 6-4 环状队列的操作示意图

第 10 页 共 30 页

再入队4次

数据结构实验指导书

重点实验内容参考源码

本次实验无参考代码，请参考教材。

实验测试数据设计通过对各种数据的输入和输出的结果对比分析，证实所有的功能的正确性，特别是需要测试非法数据的响应情况。实验报告中需要提交这些数据以及结果和自己的分析。鼓励提出一些错误（Bug）报告和改进建议。

以下为一个小的测试数据范例：逻辑结构：栈，存储结构：顺序，操作：进栈。数据申请空间的下标范围：0-10，实际数据最后的位置6，0号单元可以启用，也可以不用或者使用其他的功能。测试必须包括：上溢、下溢。

数据构成的多态性

学生可以根据自己的实力实现下面的某一个要求或同时实现多种数据类型的实现。 5. 数据构成为字符。由单个大写字母构成结点名称。（小写字母自动换成大写字母） 6. 数据构成为字符串。由美国人的姓名组成。（可以为两个或三个单词，首字母大写） 7. 数据构成为中文字符串。由中文人名组成。

8. 数据构成为多个数据。如一个人的多种信息。如：学号、姓名、性别、课程名、分数等。（也可以自己设

计） 9. 进栈数据可以为象棋盘的位置坐标。

思考题

栈和队列的性质？使用顺序存储和链表存储的差异？优缺点分析？ 栈和队列引发了数据移动吗？为什么？ 算法的时间效率是如何体现的？ 栈和队列各自的主要作用？ 实验使用参考书

本实验指导书主要参考书为：

《数据结构与程序构建》马春江 付勇智 孟繁军编著 ISBN 978-7-302-29404-7 清华大学出版社 2012年8月第1版

四、实验总结和体会

第 11 页 共 30 页

数据结构实验指导书

湖北汽车工业学院实验报告

班 号 学 号 姓 名 选课班中的序号 完成日期 年 月 日 至 节

实验三 串基本操作的编程实现

一、 实验目的

1.了解串的逻辑结构和存储结构的工作原理； 2.理解串的特殊性；

3.掌握顺序串、链串、索引结构的程序设计；

二、实验要求

本次实验涉及到字符串工作原理，实验题目将按照基本功能展示和应用级别的方式提供，任何学生都可以选择其中之一或多个综合来达成对原理的理解。细节由学生按照自己的能力随意拓展和提高，程序源码实现原创设计。

存储结构字符串使用顺序存储，使用一维数组实现会引发大量的数据移动。而单独使用链表结构，又会引发程序设计相当困难。最终的解决方案是联合使用数组和链表的思想，推出更复杂的索引结构，用最小的数据移动量解决上面的两个致命问题。但是在实验中，可以使用单独的存储结构进行训练，以便对这种特殊的线性表结构和第一次实验中涉及到的线性表结构做一个较为全面的对比。

界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程流畅。如果启用文件，则可以采用全程无界面设计模式。

原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件读入。

数据类型英语字符串、汉字字符串。

三、 实验内容

功能设计难度系数分为五级制：1：很容易，2：较容易，3：有一定难度，4：难度较大，5：难度很大。 1. 字符串的查找和其他基本功能的实现。难度系数：2 2. 统计文件中各种信息，如字符个数，行数等。难度系数：2 3. 中英语次序互换系统的设计。难度系数：3

4. 多个文本文件敏感水印信息的抄袭判别系统。（可以把多个文件拷贝到一个文件中）难度系数：4 5. 索引系统的部分功能实现。（将来可以拓展为课程设计）难度系数：5

第 12 页 共 30 页

数据结构实验指导书

开发语言最简模式为：C语言。以下依次为更加鼓励的设计环境：C++（不带对象），C++（带对象），C++带图形包（带对象），C++ windows mfc（带对象）。

知识分布界面的显示和控制、数据输入、全部数据遍历属于C语言。字符串的重要操作在存储结构中的具体实现等原理属于数据结构原理范畴。

主要操作名称表

表7-2 字符串的主要操作 操作 名称 求串长 串赋值 建议算法名称 返回串string的长度 string1是一个串变量，string2是一个串常量或串变量（通常string2 是一个串常量时称为串赋值，是一个串变量称为串复制）。将string2的串值赋值给string1， string1原来的值被覆盖掉 两个串的联接就是将一个串的串值放在另一个串的后面，连接成一个串。前者是产生新串string，string1和string2不改变; 后者是在string1的后面联接string2的串值，string1改变， string2不改变。例如： string1=＂bei＂，string2=＂ jing＂，前者操作结果是string=＂bei jing＂，后者操作结果是string1=＂bei jing＂ 串string存在，1≤i≤strlength(string)，0≤len≤strlength(string)-i+1。返回从串string的第i个字符开始的长度为 len 的子串。len=0得到的是空串。例如：strsub(＂abcdefghi＂,3,4)= ＂cdef＂ 若string1==string2，操作返回值为0；若string1string2, 返回值>0 寻找子串substring在主串string中首次出现的位置。若substring在string中，则操作返回substring在string中首次出现的位置，否则返回值为-1。如：strindex(＂abcdebda＂,＂bc＂)=2, strindex(＂abcdebda＂,＂ba＂)=-1 串string、substring存在，1≤i≤strlength(string)+1。将串substring插入到串string 的第i个字符位置上 串string存在，1≤i≤strlength(string)，0≤len≤strlength(string)-i+1。删除串string 中从第i个字符开始的长度为len的子串 串string、 substring01、 substring02存在，substring01不为空。用串substring02 替换串编程细节约定 串初始化 create (string) strlength(string) strassign(string1,string2) 串连接 strconcat (string1,string2,string) 或strconcat (string1,string2) 求子串 strsub(string,i,len) 串比较 strcomp(string1,string2) 子串定位 strindex(string,substring) 串插入 strinsert(string,i, substring) strdelete(string,i,len) strreplace(string, substring01, substring02) 串删除 串替换 第 13 页 共 30 页

数据结构实验指导书

string中出现的所有与串substring01相等的不重叠的子串 串遍历 strtraverse(string) 把字符串中所有字符从头至尾依次输出 重点实验内容参考源码

returninfo string::strmodify(int beginposition,int endposition,char newstr[]) {

int i,j,k,str_length,count,newlength,returnvalue; char *newdata;

count=endposition-beginposition+1; str_length=strlen(newstr); if(length==0) return empty;

if(beginposition>length||endposition>length||beginposition<=0||endposition<=0||beginposition>endposition)

return range_error;//如果位置错误则返回错误标志

for(i=0,j=beginposition-1;i

if(str_length>count)//当输入串的长度大于需要修改串的长度时，处理后面多的一部分 {

newlength=str_length-count; newdata=new char[newlength];

for(i=count,k=0;i

returnvalue=strinsert(endposition+1,newdata,newlength); if(returnvalue==overflow) return overflow; }

if(str_length

对字符串的修改功能，将有三种情况，新串长分别小于、等于、大于原串长。这个细节和一般线性表有着很大的不同。

数据构成的多态性

学生可以根据自己的实力实现下面的某一个要求或同时实现多种数据类型的实现。

字符串可以体现在人名、地名、物品名，可以体现在英语文章，一般性口语造句。可以体现在各种文字中，如英语或中文。

第 14 页 共 30 页

数据结构实验指导书

思考题

1. 字符串的顺序存储和链表存储的差异？C语言中是如何实现字符串的？ 2. 在字符串处理方面主要有什么操作？ 3. 字符串的操作的主要特点是什么？

4. 索引结构的最大优点是什么？在哪些实际系统中有应用？ 5. 举出几个字符串的应用范例？

实验使用参考书

本实验指导书主要参考书为：

《数据结构与程序构建》马春江 付勇智 孟繁军编著 ISBN 978-7-302-29404-7 清华大学出版社 2012年8月第1版

四、实验总结和体会

第 15 页 共 30 页

数据结构实验指导书

湖北汽车工业学院实验报告

班 号 学 号 姓 名 选课班中的序号 完成日期 年 月 日 至 节

实验四 二维数组基本操作的编程实现

一、 实验目的

1.了解线性表的逻辑结构和存储结构的工作原理； 2.理解顺序表和链表的工作原理； 3.掌握顺序表和链表的程序设计；

二、实验要求

掌握二维数组的建立、读取数据、压缩存储等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。

三、 实验内容

1. 修改程序：补充推箱子游戏的遗缺的部分，使之能正常运行，逻辑结果正确。之后增加至少一关自己的关数，墙体，箱子的最初位置，人的最初位置由自己设定，要求必须有解，而且有一定的破解难度。主要的问题是部分移动方向的代码没有给出，另外计数器的整体工作不正常，更完善的修改包括启用栈结构实现后悔的机制。

2.运行程序了解二维结构：稀疏矩阵的压缩和解压缩、生命繁衍模型、迷宫问题等，通过这些程序的运行过程或结果体会二维结构在程序设计中的重要性和实用性。

原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件读入。 思考问题

1. 数组的下标从什么地址开始？好处是什么？

2. 二维数组的表达能力仅仅限于横向和纵向的数据关系吗？ 3. 压缩数据主要的思路是什么？

4. 为什么用数组可以存储超出计算机数据要求的范围的数字？ 5. 举出几个数组的应用范例？ 实验使用参考书

本实验指导书主要参考书为：

《数据结构与程序构建》马春江 付勇智 孟繁军编著 ISBN 978-7-302-29404-7 清华大学出版社 2012年8月第1版 参考代码

第 16 页 共 30 页

数据结构实验指导书

void box::right() { if(map[positionh][positionl+1]==0) { map[positionh][positionl+1]=4; if(flag==1) { map[positionh][positionl]=2; flag=0; } else map[positionh][positionl]=0; positionl++; } else if(map[positionh][positionl+1]==2)//人要到目标位置上 { map[positionh][positionl+1]=4; if(flag==1) map[positionh][positionl]=2;//恢复目标位置 else { map[positionh][positionl]=0;//恢复原来的状态 flag=1;//标志位，记录人在目标位置上 } positionl++; } else if(map[positionh][positionl+1]==3&&map[positionh][positionl+2]==0)//将箱子推到空白位置上 { map[positionh][positionl+2]=3; map[positionh][positionl+1]=4; if(flag==1) { map[positionh][positionl]=2; flag=0; } else map[positionh][positionl]=0; positionl++; } else if(map[positionh][positionl+1]==5&&map[positionh][positionl+2]!=1)//要将箱子从目标位置上推出 { if(map[positionh][positionl+2]==2)//下一个位置还是目标位置 { map[positionh][positionl+2]=5; map[positionh][positionl+1]=4; if(flag==1) map[positionh][positionl]=2; else

第 17 页 共 30 页

数据结构实验指导书

{ map[positionh][positionl]=0; flag=1; } } else if(map[positionh][positionl+2]==0)//下一个位置是空白 { map[positionh][positionl+2]=3; map[positionh][positionl+1]=4; if(flag==1) map[positionh][positionl]=2; else { map[positionh][positionl]=0; flag=1; } } positionl++; } else if(map[positionh][positionl+1]==3&&map[positionh][positionl+2]==2)//要将箱子推到目标位置上 { map[positionh][positionl+2]=5;//箱子在目标位置上 map[positionh][positionl+1]=4; if(flag==1)//人在目标位置上 { map[positionh][positionl]=2; flag=0; } else //人不在目标位置上 map[positionh][positionl]=0; positionl++; } else count--;//抵消人不动的情况 test_flag(); }

四、实验总结和体会

第 18 页 共 30 页

数据结构实验指导书

湖北汽车工业学院实验报告

班 号 学 号 姓 名 选课班中的序号 完成日期 年 月 日 至 节

实验五 二叉树基本操作的编程实现

一、 实验目的

1.了解二叉树的逻辑结构和存储结构的工作原理； 2.理解二叉树的功能； 3.掌握二叉树的程序设计；

二、实验要求

二叉树基本操作的编程实现

二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，存储结构主要采用链接结构。

实验性质

验证性实验（学时数：2H）

三、 实验内容

本次实验分为三种模式：

第一种：全部自行编程，完成二叉树构建和遍历的操作。

第二种：使用教材中的程序构建基本框架，将三种根序遍历的递归实现和层次遍历回填并且调试成功。 注意如果仅仅显示成多个数据，三种根序遍历相对是比较简单的。 如 a b c d 可以先行尝试去完成。

如果要把结果显示成线性表的逻辑结构，即带有括号和逗号分隔的形式，就有一定的技巧性。 如 （a,b,c.d）比较难，可以在上面的程序设计结束后再改进。

注意报告中的二叉树应该是自己设计的，每个学生的都是不同的，结果首先自己分析出来，然后再通过程序的运行结果进行对比，从而理解一些设计原理。

第三种：用c进行程序的改进和提高，把下面的程序源码进行输入和改写，调试，直到成功。 1. 建立二叉树，并以前序遍历的方式将结点内容输出。 2. 将一个表示二叉树的数组结构转换成链表结构。

3. 将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序及后

序遍历结果，并计算出表达式之结果。

有兴趣和精力的学生可以自行学习线索二叉树的程序构建，对比某些功能的设计上的差异。

思考问题

1. 二叉树是树吗？它的定义为什么是递归的？

第 19 页 共 30 页

数据结构实验指导书

2. 三种根序遍历主要思路是什么？

3. 如果不用遍历算法一般启用什么数据结构实现后序遍历？ 4. 举出二叉树的应用范例？

参考代码

#include #include #include #include using namespace std;

enum returninfo {success,fail,overflow,underflow,nolchild,norchild,nofather,havesonl,havesonr, haveason,havetwosons,range_error,quit }; //定义返回信息清单 #define Maxsize 100 //定义广义表数组的长度 char defaultbtree1[]=\ //默认广义表数据表示的二叉树范例1 char defaultbtree2[]=\//默认广义表数据表示的二叉树范例2 class node {

friend class btree;//二叉树类的友元类 public:

node(char initdata='0',int initdeep=0,node *initl=NULL,node *initr=NULL, node *initf=NULL,node *initn=NULL); ~node() {}; protected: char data; //二叉树结点中的数据，此处定义为字符 int deep; //设置二叉树结点的深度 node *lchild; //左儿子 node *rchild; //右儿子 node *father; //父亲结点 node *next; //用单链表处理所有结点时指向下一个结点 };

node::node(char initdata,int initdeep,node *initl,node *initr,node *initf,node *initn) {

data=initdata; deep=initdeep; lchild=initl; rchild=initr; father=initf; next=initn; }

class stackdata //创建一个stackdata类，在非递归遍历算法中需要 {

friend class btree; private:

第 20 页 共 30 页

数据结构实验指导书

node *link; int flag; public:

stackdata() {}; ~stackdata() {}; };

class btree //创建一个二叉树类 {

private:

char btreedata[Maxsize]; //广义表字符数组 char answer; //用于回答菜单选项 node *root; //指向根结点位置的指针 node *workinp,*linkrear; //定义一个工作指针，尾部指针 int btreecount; //结点个数计数器 bool firstbracket; //显示广义表时处理第一个括号，为1是，变成0就不是了 int countnow; //每一次需要使用计数器时临时保存该值 int leafcount; int countall; int sondeep; //创建儿子结点时保存当前深度 public:

btree(node *initrootp); btree() {

root=NULL; firstbracket=1; countall=0; //递归函数内部统计结点个数 btreecount=0; //二叉树统计后的结点个数 };

~btree() {};

void initfirstbracket(); //把第一个括号标志位恢复成1

returninfo createbtree(int choice); //根据广义表字符串生成二叉树，choice=1为默认数据，2为键盘输入 returninfo createroot(); //建立树根函数

void visit(node *searchp); //访问当前结点数据域 void showbtreedata(); //在主界面中显示当前工作数组 int rgetcount(node *searchp); //递归统计二叉树中的结点个数 int getcount(); //记录二叉树中的结点个数

returninfo changeworkinpp(); //将工作指针指向左儿子、右儿子或者父亲 returninfo findnode(); //查找结点

returninfo addchild(); //增加左儿子或者右儿子 returninfo deletenode(); //删除结点

returninfo getinformation(); //获取二叉树结点和叶子信息

returninfo gliststravel(node *searchp);//以广义表glists表示法输出二叉树 returninfo indenttravel(node *searchp);//以凹入indent表示法输出二叉树 returninfo preorder (node *searchp);//递归先根遍历

第 21 页 共 30 页

数据结构实验指导书

returninfo inorder (node *searchp);//递归中根遍历 returninfo postorder (node *searchp);//递归后根遍历 returninfo nrpreorder (node *searchp);//非递归先根遍历 returninfo nrinorder (node *searchp);//非递归中根遍历 returninfo nrpostorder (node *searchp);//非递归后根遍历 returninfo levelorder (node *searchp);//层次遍历 };

returninfo btree::preorder(node *searchp) //先根递归遍历 { if(firstbracket==1) //处理显示第一个括号 {

searchp=root;

if(searchp==NULL) return underflow; firstbracket=0; //此后都不是第一个括号了 countnow=getcount(); //本函数中使用结点个数 cout<<\递归先根遍历结果： (\ }

if(searchp!=NULL) { visit(searchp); countnow--;

if(countnow!=0) cout<<\ else

cout<<\ preorder(searchp->lchild); preorder(searchp->rchild); }

return success; }

returninfo btree::nrpreorder(node *searchp)//非递归先根遍历 {

node *stack[Maxsize],*pnow; //启用栈，pnow指向二叉树某个结点的地址 int top;

searchp=root;

if(searchp==NULL) return underflow; top=0; //0号地址启用存入第一个数据 pnow=searchp;

cout<<\非递归先根遍历结果：(\

第 22 页 共 30 页

数据结构实验指导书

countnow=getcount(); while(!(pnow==NULL&&top==0)) {

while(pnow!=NULL) {

visit(pnow); countnow--; if(countnow!=0) cout<<\ else

cout<<\

if(top

stack[top]=pnow; top++; } else {

return overflow; }

pnow=pnow->lchild; }

if(top<=0) return success; else {

top--;

pnow=stack[top]; pnow=pnow->rchild; } }

cout<

四、实验总结和体会

第 23 页 共 30 页

数据结构实验指导书

湖北汽车工业学院实验报告

班 号 学 号 姓 名 选课班中的序号 完成日期 年 月 日 至 节

实验六 图基本操作的编程实现

一、 实验目的

1.了解图的逻辑结构和存储结构的工作原理； 2.理解图的用途； 3.掌握图的程序设计；

二、实验要求

阅读程序功能方面要求掌握图的建立、遍历、插入、删除等基本操作的编程实现，程序设计方面要求掌握图的遍历。

存储结构可以在顺序结构、链接结构等中选择，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。

实验性质

验证性实验（学时数：2H）

三、 实验内容

一、在给出的程序代码基础上，首先排除遇到的语法问题，然后通过填空完成遍历的任务，通过自己绘制的

图形进行验证。本部分资料直接通过.cpp文件直接给出。请注意下载。为了保证在实验时间内完成，最好提前预习。涉及的主要问题包括：常用语句出错了。基础部分的结点存储结构的一维数组设计需要自己写。图的数据结构定义部分。显示图的结构。主要遍历的功能设计。存储结构主要是邻接矩阵，最后可以通过提供参考答案来对比。邻接表的程序代码删除了更多的部分，且不提供参考答案，供有能力的学生自己研究。

二、如果希望自行独立编程，可以实现对图进行存储（邻接矩阵或邻接表都可以，学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。以下的题目都可以作为独立编程的题目

设计一个将图形转成邻接链表的程序。

设计一个深度优先搜索法来查找图形的程序。

设计一个广度优先搜索法来查找一个图形的程序。 鼓励开发出难度更高的程序。

思考问题

1. 图的定义和特性？

2. 图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？

第 24 页 共 30 页

数据结构实验指导书

3. 图的主要遍历思路是哪些？ 4. 举出图的应用范例？

参考代码

//图类

const int maxvertices=26;//定义结点个数最大值为26

const int maxweight=10000;//当两个结点之间不存在边时距离无穷大用10000来模拟 class graph {

private:

int i,j; //循环变量 int flag; //标志位

int inputnodenum,inputedgenum; //输入的结点个数、边数 int numofedges; //记录边的条数

char *nodearray; //输入结点时使用的一维数组 SeqList Vertices; //图的结点信息，启用了线性表

int Edge[maxvertices][maxvertices]; //图的边信息,使用了二维数组，是一个方阵 public:

graph(const int size=maxvertices); //图的构造函数 ~graph(){}; //图的析构函数

void initializationofEdge(int size); //边的邻接矩阵初始化 void inputdata(); //手工输入数据 void defaultdata(); //启用默认数据 void showgraph(); //显示图的邻接矩阵 void showVertex(); //显示图的结点 int graphempty()const{return Vertices.ListEmpty();}//判断图是否为空 int numofVertices(){return Vertices.ListSize();} //求图的结点个数 int numofEdges(void){return numofedges;} //求图的边数

char getvalue(const int i); //求取图某个结点的值

int getweight(const int nodestart,const int nodeend);//求两个结点之间的边的权值 void insertVertices(const char& vertices); //向图中添加一个结点 int deleteVertex(const int v); //删除一个结点

int insertEdge(const int nodestart,const int nodeend,int weight);//添加一条边 int deleteEdge(const int nodestart,const int nodeend);//删除一条边

int getfirstneighbor(const int v);//为实现图的遍历而必须定义的求取其第一个相邻结点的函数 int getnextneighbor(const int nodestart,const int nodeend);//求取其下一个相邻结点的函数 void depthfirstsearch(const int v,int visited[],void visit(char item));//深的优先遍历 void breadthfirstsearch(const int v,int visited[],void visit(char item));//广度优先遍历 };

void graph::depthfirstsearch(const int startpoint,int visited[],void visit(char item))//深度优先遍历 {

int neighborpoint;

visit(getvalue(startpoint));//访问结点startpoint

visited[startpoint]=1;//标记结点startpoint已经被访问

neighborpoint=getfirstneighbor(startpoint);//求结点startpoint的第一个邻接结点 while(neighborpoint!=-1)//当邻接结点存在时循环 {

if(!visited[neighborpoint])

depthfirstsearch(neighborpoint,visited,visit);//对结点startpoint递归 neighborpoint=getnextneighbor(startpoint,neighborpoint);

//结点neighborpoint为邻接边的下一个邻接结点 } }

void graph::breadthfirstsearch(const int startpoint,int visited[],void visit(char item))//广度优先遍历 {

char getqueuehead,neighborpoint; SeqQueue queue;

visit(getvalue(startpoint));//访问初始结点startpoint visited[startpoint]=1;//标记startpoint已经访问

第 25 页 共 30 页

本文来源：https://www.bwwdw.com/article/7g68.html