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

1、僚I处他车X欢谬昵HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构A实验指导书马春江撰写付勇智审核电气与信息工程学院计算机工程系2013年12月、八,、刖言数据结构课程开设 8个必做的实验：1线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的 编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链接结构中任选，也 可以全部实现，用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。2、 堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出 队

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

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

4、可以实现多种， 用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。8、排序技术的编程实现（2学时，综合型），掌握排序技术的编程实现，可以实现一种，也可以实现多种， 用菜单进行管理。也鼓励学生利用基本操作进行一些应用的程序设计。9、实验要求把每次实验的程序文本和运行结果存入到本人的用户目录下供实验老师检查。10 、对实验室要求是必须保证学生上机时人手一机；必须保证满足课程要求的上机时数 ；必须配备专职的数据结构课程的实验指导老师。目录实验一线性表基本操作的编程实现4实验二堆栈和队列基本操作的编程实现9实验三串基本操作的编程实现 12实验四二维数组基本操作的编程实现 16实验五二叉树基

5、本操作的编程实现 19实验六图基本操作的编程实现 24实验七查找技术的编程实现 27实验八排序技术的编程实现 29湖北汽车工业学院实验报告班 号 学 号姓名选课班中的序号 完成日期年月日_至 节实验一 线性表基本操作的编程实现一、实验目的1. 了解线性表的逻辑结构和存储结构的工作原理；2. 理解顺序表和链表的工作原理；3. 掌握顺序表和链表的程序设计；二、实验要求编程实现通用的线性表常用功能程序，其中插入数据和删除数据是必须实现的。存储结构由学生自己选择。实验题目采用班级目标总体一致，细节由学生按照自己的能力随意拓展和提高，程序源码实现原创设计。存储结构最简模式为：顺序存储，使用一维数组实现。

6、鼓励使用链表结构，一般可以采用单链表结构，更 加复杂的可以采用循环链表或双向链表结构。时间足够的情况下，希望把这些在课外全部自行编程实现。界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程流畅。 如果启用文件，则可以采用全程无界面设计模式。原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件 读入。数据类型最简模式为：整数。其他依次鼓励使用的为：实数、字符、英语字符串、汉字字符串。三、实验内容功能设计最简模式为：原始数据构建、全部数据遍历、插入数据、删除数据。其他的任何相关功能见参考 教材，鼓励实现。开发语言最简模式为

7、： C语言。以下依次为更加鼓励的设计环境：C+（不带对象），C+（带对象），C+带图形包（带对象），C+ wi ndows mfc （带对象）。知识分布原始数据构建、全部数据遍历属于 C语言。插入数据、删除数据涉及的循环程序设计属于C语言。但是插入数据、删除数据涉及的数据移动的必要性、移动的所有位置和数量控制、具体移动的过程、移动对于 程序的时间效率产生的影响属于数据结构原理范畴。重点实验内容图示教材图3-2顺序表插入操作的示意图dtfct FULFIL IVV1址a47if101借科憤63ill1 . |0607y卜列冋WX01岩影0w iS 910oOKHEitWiinr扫述UlH7 |如

8、VT07.cXt6301H7 06071教材图3-3顺序表删除操作的示意图顺序表的操作关键是要把相关的坐标控制好，如合法的插入和删除位置的范围，移动数据两边的坐标值。 完成任务最后要注意数据量的变化。newnode 222|Aheadp / Z-T 4*T ill 殳4 333命 444AJchp教材图3-6单链表中进行插入操作的示意图follow? seatchp教材图3-7单链表存储删除操作的示意图链表编程主要是注意关键语句的次序相关性，注意不要出现“内存垃圾”，把握好修改链的节奏和语句。 注意空间的结点的申请和释放。重点实验内容参考源码 顺序表returninfo seqlist:i n

9、sert(i nt positi on,const int &item)/ 插入一个元素if(co un t+1=Maxsize) return overflow;if(positi oncoun t+1) retur n ran ge_error;coun t+;for(i nt i=co un t;i=positi on ;i-) dataarrayi=dataarrayi-1;dataarraypositi on-1=item;retur n success;retur ninfo seqlist:remove(i nt positi on) if(empty()retur n un d

10、erflow;if(positi oncount) retur n ran ge_error;for(i nt i=positi on-1;ico un t;i+) dataarrayi=dataarrayi+1;coun t-;retur n success;链表/溢出处理/计数器加一/循环移动数据/删除一个元素/循环移动数据/计数器减一/给数据赋值/注意此处的次序相关性/计数器加一删除一个结点returninfo lin klist:i nsert(i nt positi on,const int &item)/ 插入一个结点if(positi on=co un t+2)retur n r

11、an ge_error;node *newno dep=new no de,*searchp=headp-n ext,*followp=headpfor(i nt i=1; in ext;newno dep-data=item;newno dep-n ext=followp-n ext; followp-n ext =newno dep;coun t+;retur n success;retur ninfo lin klist:remove(i nt positi on) if(empty()retur n un derflow;/这里两个指针的初始值设计一前一后if(positi on=co

12、 un t+1) retur n ran ge_error;node *searchp=headp-n ext,*followp=headp; for(i nt i=1; in ext;删除结点的实际语句/释放该结点/计数器减一followp-n ext=searchp-n ext; delete searchp;coun t-;retur n success;实验测试数据设计通过对各种数据的输入和输出的结果对比分析，证实所有的功能的正确性，特别是需要 测试非法数据的响应情况。实验报告中需要提交这些数据以及结果和自己的分析。鼓励提出一些错误 （Bug）报告和改进建议。以下为一个小的测试数据范例

13、：逻辑结构：线性表，存储结构：顺序，操作：插入。数据申请空间的下标 范围：0-10，实际数据最后的位置 6，0号单元可以启用，也可以不用或者使用其他的功能。测试地址必须包括：-5、-1、0、1、5、6、7、9、10、11、18等至少11个数据。也就是说插入或删除必须考虑意外的两种情况： 1顺序表在分配的地址空间中，但是范围超界，2.完全是不存在的地址。其他的正常的都需要测试：如正常的边界。如顺序表插入时，最后数据地址为5.则在6插入也是容许的。数据构成的多态性学生可以根据自己的实力实现下面的某一个要求或同时实现多种数据类型的实现。1. 数据构成为字符。由单个大写字母构成结点名称。（小写字母自动

14、换成大写字母）2. 数据构成为字符串。由美国人的姓名组成。（可以为两个或三个单词，首字母大写）3. 数据构成为中文字符串。由中文人名组成。4. 数据构成为多个数据。如一个人的多种信息。如：学号、姓名、性别、课程名、分数等。（也可以自己设计）实验报告提示实验报告主要按照以下的框架完成：本次实验的实验方式、目标和其他背景信息。实验的逻辑结构和存储结构的基本概念和原理（最好附图）。实验的总体设计（功能和界面等，算法思路）。实验的程序设计细节或测试细节。实验的总收获清单：（包含 弄懂的原理和一些结论、学会了新的一些语句或功能段源码、学会了新的测试方法和过程、学会了内部结构控 制和一些软件设计规范的细节

15、等等），实验的遗憾和下一步努力的方向（总结自己未能达成的目标和原因分析，提出可行的改进方案）。报告中应该涉及界面截图、开发过程综述（花费时间、总语句数、调试过程）、开发总结、重点源码清单（本次实验仅仅为插入和删除）、致谢等。在实验中受到其他同学的帮助时在报告最后的致谢中鼓励实名感谢。实验提交文件约定程序名一律类似为：T1123-02-17-某某某-链表实验程序.cpp所有信息之间为中横线。如果有文本文件，也是类似的结构：T1123-2-17-某某某-链表实验程序输入数据.txtT1123-2-17-某某某-链表实验程序输出数据.txt报告电子版为T1123-2-17-某某某-实验报告01.do

16、c（必须涉及工程的时候请打包管理，但是最后的文件名和内部的文件名也需要如此管理。）思考题1. 线性表的顺序存储和链表存储的差异？优缺点分析?2. 那些操作引发了数据的移动？3. 算法的时间效率是如何体现的？4. 链表的指针是如何后移的？如何加强程序的健壮性?实验使用参考书本实验指导书主要参考书为：数据结构与程序构建马春江付勇智孟繁军编著ISBN 978-7-302-29404-7清华大学出版社2012年8月第1版四、实验总结和体会湖北汽车工业学院实验报告班 号 学 号姓名选课班中的序号 完成日期年月日_至 节实验二栈和队列基本操作的编程实现一、实验目的1. 了解栈和队列的逻辑结构和存储结构的工

17、作原理；2. 理解栈和队列的用途；3. 掌握栈和队列的程序设计；二、实验要求由于本次实验涉及到栈和队列两种数据结构的原理，实验题目将按照分级和分类的方式提供，任何学生都可以选择其中之一或多个综合来达成对原理的理解。细节由学生按照自己的能力随意拓展和提高，程序源码实 现原创设计。存储结构最简模式为：顺序存储，使用一维数组实现。鼓励使用链表结构，一般可以采用单链表结构。时 间足够的情况下，希望把这些在课外全部自行编程实现。特别是希望和第一次实验采取相反的策略进行选择， 以此来提高自己对于不同的存储结构的熟练运用。界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程

18、流畅。 如果启用文件，则可以采用全程无界面设计模式。原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件 读入。数据类型最简模式为：整数。其他依次鼓励使用的为：实数、字符、英语字符串、汉字字符串。三、实验内容功能设计难度系数分为五级制：1:很容易，2:较容易，3:有一定难度，4:难度较大，5:难度很大。1. 栈功能演示系统。难度系数：22. 汉字回文字符串的判断程序。难度系数：33. 十进制正整数转换为八进制的程序。难度系数：44. 环状队列功能演示系统。难度系数：25. 十进制正小数转换为八进制的程序。难度系数：36. 用计算机自动产生作业名、申请时间

19、和打印时间的随机数据，然后用队列管理，随时显示队列中的数据和已经打印完毕的作业名。难度系数：4C+开发语言最简模式为：C语言。以下依次为更加鼓励的设计环境：C+（不带对象），C+（带对象），带图形包（带对象），C+ wi ndows mfc （带对象）。C语言。进栈和出栈、进队和出队等原理知识分布界面的显示和控制、原始数据构建、全部数据遍历属于 属于数据结构原理范畴。重点实验内容图示讨论的初始状态相对初始状态进栈 444的效果相对初始状态出栈 333的效果i16665554443top 3；期:3tOp 2:滋B3 :2333233312221222top 13 滋 2 ! !01110111

20、U111教材图5-2顺序栈的进栈、出栈示意图111A1 inks lack lop空环队入队9次，出队4次再入队3次，出队3次再入队4次图6-4环状队列的操作示意图重点实验内容参考源码本次实验无参考代码，请参考教材。(Bug)报实验测试数据设计通过对各种数据的输入和输出的结果对比分析，证实所有的功能的正确性，特别是需要 测试非法数据的响应情况。 实验报告中需要提交这些数据以及结果和自己的分析。鼓励提出一些错误告和改进建议。以下为一个小的测试数据范例：逻辑结构：栈，存储结构：顺序，操作：进栈。数据申请空间的下标范围: 0-10，实际数据最后的位置 6, 0号单元可以启用，也可以不用或者使用其他的

21、功能。测试必须包括：上溢、 溢。数据构成的多态性学生可以根据自己的实力实现下面的某一个要求或同时实现多种数据类型的实现。5. 数据构成为字符。由单个大写字母构成结点名称。（小写字母自动换成大写字母）6. 数据构成为字符串。由美国人的姓名组成。（可以为两个或三个单词，首字母大写）7. 数据构成为中文字符串。由中文人名组成。8. 数据构成为多个数据。如一个人的多种信息。如：学号、姓名、性别、课程名、分数等。（也可以自己设 计）9. 进栈数据可以为象棋盘的位置坐标。思考题栈和队列的性质？使用顺序存储和链表存储的差异？优缺点分析？栈和队列引发了数据移动吗？为什么？算法的时间效率是如何体现的？栈和队列各

22、自的主要作用？实验使用参考书本实验指导书主要参考书为：数据结构与程序构建马春江付勇智孟繁军编著ISBN 978-7-302-29404-7清华大学出版社2012年8月第1版四、实验总结和体会湖北汽车工业学院实验报告班号选课班中的序号学号姓名完成日期年月日至节实验三 串基本操作的编程实现一、实验目的1. 了解串的逻辑结构和存储结构的工作原理；2. 理解串的特殊性；3. 掌握顺序串、链串、索引结构的程序设计；二、实验要求本次实验涉及到字符串工作原理，实验题目将按照基本功能展示和应用级别的方式提供，任何学生都可以 选择其中之一或多个综合来达成对原理的理解。细节由学生按照自己的能力随意拓展和提高，程序

23、源码实现原 创设计。存储结构字符串使用顺序存储，使用一维数组实现会引发大量的数据移动。而单独使用链表结构，又会引 发程序设计相当困难。最终的解决方案是联合使用数组和链表的思想，推出更复杂的索引结构，用最小的数据 移动量解决上面的两个致命问题。但是在实验中，可以使用单独的存储结构进行训练，以便对这种特殊的线性 表结构和第一次实验中涉及到的线性表结构做一个较为全面的对比。界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程流畅。 如果启用文件，则可以采用全程无界面设计模式。原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件

24、 读入。数据类型英语字符串、汉字字符串。三、实验内容功能设计难度系数分为五级制：1:很容易，2:较容易，3:有一定难度，4:难度较大，5:难度很大。1.字符串的查找和其他基本功能的实现。难度系数：22.统计文件中各种信息，如字符个数，行数等。难度系数：23.中央语次序互换系统的设计。难度系数：34.多个文本文件敏感水印信息的抄袭判别系统。（可以把多个文件拷贝到一个文件中）难度系数：45.索引系统的部分功能实现。（将来可以拓展为课程设计）难度系数：5C+开发语言最简模式为：C语言。以下依次为更加鼓励的设计环境：C+（不带对象），C+（带对象），带图形包（带对象），C+ wi ndows mfc

25、（带对象）。知识分布界面的显示和控制、数据输入、全部数据遍历属于C语言。字符串的重要操作在存储结构中的具体实现等原理属于数据结构原理范畴。主要操作名称表表7-2字符串的主要操作操作 名称建议算法名称编程细节约定串初始化create (stri ng)求串长strle ngth(stri ng)返回串string 的长度串赋值strassig n( stri ng1,stri ng2)stri ng1是一个串变量，stri ng2 是一个串常量或串变量（通常stri ng2是一个串常量时称为串赋值，是一个串变量称为串复制）。将string2 的串值赋值给string1 ， string1原来的值

26、被覆盖掉串连接strcon cat(stri ng1,stri ng2,stri ng) 或 strc on cat(stri ng1,stri ng2)两个串的联接就是将一个串的串值放在另一个串的 后面，连接成一个串。前者是产生新串stri ng ，string1和string2不改变；后者是在string1的后面联接 string2的串值，string1改变，string2不改变。例如：stri ng1= bei , stri ng2=jing ，前者操作结果是string= bei jing ，后者操作结果是 string1= bei jing 求子串strsub(stri ng,i,l

27、e n)串 string 存在，1 i strlength(string), 0 lenw strlength(string)-i+1。返回从串 string 的第 i个字符开始的长度为len的子串。len=0得到的是 空串。例如：strsub( abcdefghi ,3,4)=cdef串比较strcomp(stri ng1,stri ng2)若 stri ng仁=stri ng2,操作返 回值为 0 ;若string1string2,返回值 string2,返回值0子串定位stri ndex(stri ng,substri ng)寻找子串substring 在主串string中首次出现的位置

28、。若 substring 在 string中，则操作返回substring在string中首次出现的位置，否则返回值为-1。如：strindex（ abcdebda , bc ）=2,strindex（ abcdebda , ba ）=-1串插入stri nsert(stri ng,i, substri ng)串 string 、 substring存在， 1 w i wstrle ngth(stri ng)+1。将串 substri ng 插入到串string 的第i个字符位置上串删除strdelete(stri ng,i,le n)串 string 存在，1 w i w strlength

29、(string), 0 w lenw strle ngth(stri ng)-i+1。删除串 stri ng 中从第i个字符开始的长度为len的子串串替换strreplace(stri ng, substri ng01, substri ng02)串 string 、 substring01 、 substring02 存在， substri ng01 不为空。用串 substri ng02 替换串string中出现的所有与串substri ng01相等的不重叠的子串串遍历strtraverse(stri ng)把字符串中所有字符从头至尾依次输出重点实验内容参考源码retur ninfo st

30、ri ng:strmodify(i nt begi npositi on ,i nt en dpositi on, char n ewstr)int i,j,k,str_le ngth,co un t, newle ngth,retur nvalue;char *n ewdata;coun t=e ndpositi on-begi npositi on+1;str_le ngth=strle n(n ewstr);if(le ngth=0)return empty;if(beg in positi onlen gth|e ndpositi onlen gth|begi npositi on=0

31、|e ndpositi onen dpositi on)return ran ge_error;如果位置错误则返回错误标志for(i=0,j=begi npositio n-1;istr_le ngth &icou nt)当输入串的长度大于需要修改串的长度时，处理后面多的一部分n ewle ngth=str_le ngth-co unt;n ewdata=new char newle ngth;for(i=co un t,k=0;istr_le ngth;i+,k+)n ewdatak=n ewstri;retur nvalue=stri nsert(e ndpositi on+1, newd

32、ata ,n ewle ngth);if(retur nvalue=overflow)return overflow;if(str_le ngthvcou nt)当输入串的长度小于需要修改串的长度时，直接删除一部分strdelete(begi npositi on+str_le ngth,e ndpositi on);retur n success;实验测试数据设计通过对各种数据的输入和输出的结果对比分析，证实所有的功能的正确性，特别是需要测试非法数据的响应情况。实验报告中需要提交这些数据以及结果和自己的分析。鼓励提出一些错误(Bug)报告和改进建议。对字符串的修改功能，将有三种情况，新串长分

33、别小于、等于、大于原串长。这个细节和一般线性表有着很大的不同。数据构成的多态性学生可以根据自己的实力实现下面的某一个要求或同时实现多种数据类型的实现。字符串可以体现在人名、地名、物品名，可以体现在英语文章，一般性口语造句。可以体现在各种文字中，如 英语或中文。思考题1. 字符串的顺序存储和链表存储的差异？C语言中是如何实现字符串的?2. 在字符串处理方面主要有什么操作？3. 字符串的操作的主要特点是什么？4. 索引结构的最大优点是什么？在哪些实际系统中有应用？5. 举出几个字符串的应用范例？实验使用参考书本实验指导书主要参考书为：数据结构与程序构建马春江付勇智孟繁军编著ISBN 978-7-3

34、02-29404-7清华大学出版社2012年8月第1版四、实验总结和体会湖北汽车工业学院实验报告班 号 学 号姓名选课班中的序号 完成日期年月日_至 节实验四 二维数组基本操作的编程实现一、实验目的1. 了解线性表的逻辑结构和存储结构的工作原理；2. 理解顺序表和链表的工作原理；3. 掌握顺序表和链表的程序设计；二、实验要求掌握二维数组的建立、读取数据、压缩存储等基本操作的编程实现，存储结构可以在顺序结构或链接结构 中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。三、实验内容1. 修改程序：补充推箱子游戏的遗缺的部分，使之能正常运行，逻辑结果正确。之后增加至少一关自己的

35、关数，墙体，箱子的最初位置，人的最初位置由自己设定，要求必须有解，而且有一定的破解难度。主要的问 题是部分移动方向的代码没有给出，另外计数器的整体工作不正常，更完善的修改包括启用栈结构实现后悔的 机制。2. 运行程序了解二维结构：稀疏矩阵的压缩和解压缩、生命繁衍模型、迷宫问题等，通过这些程序的运行 过程或结果体会二维结构在程序设计中的重要性和实用性。原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件读入。 思考问题1. 数组的下标从什么地址开始？好处是什么？2. 二维数组的表达能力仅仅限于横向和纵向的数据关系吗？3. 压缩数据主要的思路是什么？4. 为

36、什么用数组可以存储超出计算机数据要求的范围的数字？5. 举出几个数组的应用范例？实验使用参考书本实验指导书主要参考书为：数据结构与程序构建马春江付勇智孟繁军编著ISBN 978-7-302-29404-7清华大学出版社2012年8月第1版 参考代码void box:right()if(mappositi on hpositi onl+1=0)mappositi on hpositi onl+1=4;if(flag=1)mappositi on hpositi on l=2; flag=0; elsemappositi on hpositi on l=0; positi onl+;else if

37、(mappositi on hpositi onl+1=2) 人要到目标位置上mappositi on hpositi onl+1=4; if(flag=1)mappositi on hpositi on l=2; elsemappositi on hpositi on l=0;恢复目标位置恢复原来的状态flag=1;标志位，记录人在目标位置上positi onl+;else if(mappositi on hpositi onl+1=3&mappositi on hpositi onl+2=0) 位置上mappositi on hpositi onl+2=3;mappositi on hpo

38、siti onl+1=4;if(flag=1) mappositi on hpositi on l=2; flag=0; elsemappositi on hpositi on l=0;positi onl+;else if(mappositi on hpositi onl+1=5&mappositi on hpositi onl+2!=1)位置上推出将箱子推到空白要将箱子从目标if(mappositi on hpositi onl+2=2) mappositi on hpositi onl+2=5;mappositi on hpositi onl+1=4; if(flag=1)mapposi

39、ti on hpositi on l=2;下一个位置还是目标位置else mappositi on hpositi on l=0; flag=1; else if(mappositio nhpositio nl+2=0)下一个位置是空白mappositi on hpositi onl+2=3;mappositi on hpositi onl+1=4;if(flag=1)mappositi on hpositi on l=2;else mappositi on hpositi on l=0; flag=1; positi onl+;要将箱子推到目else if(mappositi on hpos

40、iti onl+1=3&mappositi on hpositi onl+2=2)标位置上mappositio nhpositio nl+2=5;箱子在目标位置上mappositi on hpositi onl+1=4;if(flag=1)人在目标位置上 mappositi on hpositi on l=2; flag=0; else / 人不在目标位置上mappositi on hpositi on l=0;positi onl+;else cou nt-;抵消人不动的情况test_flag();四、实验总结和体会湖北汽车工业学院实验报告班 号 学 号姓名选课班中的序号 完成日期年月日_至

41、 节实验五二叉树基本操作的编程实现一、实验目的1. 了解二叉树的逻辑结构和存储结构的工作原理；2. 理解二叉树的功能；3. 掌握二叉树的程序设计；二、实验要求二叉树基本操作的编程实现二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程 实现，存储结构主要采用链接结构。实验性质验证性实验（学时数：2H）三、实验内容本次实验分为三种模式：第一种：全部自行编程，完成二叉树构建和遍历的操作。第二种：使用教材中的程序构建基本框架，将三种根序遍历的递归实现和层次遍历回填并且调试成功。注意如果仅仅显示成多个数据，三种根序遍历相对是比较简单的。如a b c d 可以先

42、行尝试去完成。如果要把结果显示成线性表的逻辑结构，即带有括号和逗号分隔的形式，就有一定的技巧性。如（a,b,c.d ）比较难，可以在上面的程序设计结束后再改进。注意报告中的二叉树应该是自己设计的，每个学生的都是不同的，结果首先自己分析出来，然后再通过程 序的运行结果进行对比，从而理解一些设计原理。第三种：用c进行程序的改进和提高，把下面的程序源码进行输入和改写，调试，直到成功。1. 建立二叉树，并以前序遍历的方式将结点内容输出。2. 将一个表示二叉树的数组结构转换成链表结构。3. 将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序及后 序遍历结果，并计算出表达

43、式之结果。有兴趣和精力的学生可以自行学习线索二叉树的程序构建，对比某些功能的设计上的差异。思考问题1. 二叉树是树吗？它的定义为什么是递归的?2. 三种根序遍历主要思路是什么？3. 如果不用遍历算法一般启用什么数据结构实现后序遍历？4. 举出二叉树的应用范例？参考代码#i nclude#in clude#in clude#in cludeusing n amespace std;enum returni nfo success,fail,overflow,u nderflow, nolchild, no rchild, no father,haveso nl,haves onr, haveas

44、 on, havetwos on s,ra nge_error,quit;定义返回信息清单#defi ne Maxsize 100/定义广义表数组的长度char defaultbtree1=a(b,c(,d);/默认广义表数据表示的二叉树范例1char defaultbtree2=a(b(c(d,e),f(,g),h(i,j);/ 默认广义表数据表示的二叉树范例2class nodefrie nd class btree;/二叉树类的友元类public:node(char initdata=0,int initdeep=0,node *initl=NULL,node *initr=NULL,n

45、 ode *in itf=NULL, node *initn=N ULL);no de() ;protected:char data;二叉树结点中的数据，此处定义为字符int deep;设置二叉树结点的深度n ode *lchild; 左儿子node *rchild; / 右儿子node *father; /父亲结点n ode *n ext;/用单链表处理所有结点时指向下一个结点;no de: no de(char in itdata,i nt in itdeep ,node *in itl, node *in itr, node *initf,node *in it n)data=in it

46、data;deep=in itdeep;lchild=i nitl;rchild=in itr;father=i nitf;n ext=in it n;class stackdata 创建一个stackdata类，在非递归遍历算法中需要friend class btree;private:node *li nk; int flag;public:stackdata() ; stackdata() ;class btree /创建一个二叉树类 private:char btreedataMaxsize; char an swer;node *root;node *workinp,*linkrea

47、r; int btreeco unt;bool firstbracket; countnow; leafc ount;coun tall;son deep;int/广义表字符数组/用于回答菜单选项/指向根结点位置的指针/定义一个工作指针，尾部指针/结点个数计数器显示广义表时处理第一个括号，为1是,每一次需要使用计数器时临时保存该值变成0就不是了intintintpublic:btree( node *in itrootp);btree()root=NULL;firstbracket=1;coun tall=0;btreeco un t=0;btree() ;void in itfirstbra

48、cket();/创建儿子结点时保存当前深度/递归函数内部统计结点个数/二叉树统计后的结点个数把第一个括号标志位恢复成1为默认数据，2为键盘输入returni nfo createroot();void visit (node *searchp);void showbtreedata();int rgetco unt(node *searchp);int getco un t();retur ninfo cha ngework in pp();retur ninfo findno de(); returninfo addchild();retur ninfo delete no de();ret

49、urni nfo get in formati on();returninfo createbtree(int choice); / 根据广义表字符串生成二叉树，choice=1/建立树根函数/访问当前结点数据域/在主界面中显示当前工作数组/递归统计二叉树中的结点个数/记录二叉树中的结点个数/将工作指针指向左儿子、右儿子或者父亲/查找结点/增加左儿子或者右儿子删除结点/获取二叉树结点和叶子信息returninfo gliststravel(node *searchp);/ 以广义表 glists 表示法输出二叉树 returni nfo in de nttravel( node *search

50、p);/ 以凹入 in de nt 表示法输出二叉树 returninfo preorder (node *searchp);/ 递归先根遍历retur ninfo ino rder returni nfo postorder returni nfo n rpreorder retur ninfo nrino rder(n ode *searchp);递归中根遍历 (n ode *searchp);递归后根遍历 (n ode *searchp);非递归先根遍历 (n ode *searchp);非递归中根遍历returninfo nrpostorder (node *searchp); 非递归后根遍历returni nfo levelorder(node *searchp); 层次遍历;returni nfo btree:preorder( node *se