最新数据结构实验指导书

《最新数据结构实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验指导书（适用于计算机科学与技术、网络工程、软件工程专业）计算机科学与技术学院软件教研室2006-811目录前言3实验一、单链表的基本操作4实验二、二叉树的遍历5实验三、折半查找和二叉排序树7实验四、内部排序911前言《数据结构》是计算机科学与技术、网络工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。《数据结构》是

2、一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。11实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。4、熟练掌握单链表的取元素操作二、实验内容1、定义单链表类型并动态创建单链表2、实现线性表链式存储结构下元素的插入操作3、实现线性

3、表链式存储结构下元素的删除操作4、实现线性表链式存储结构下取元素操作三、实验环境TC或VC++或Java四、实验步骤1、单链表的存储定义2、从键盘上依次输入21、18、30、75、42、56，逆序创建单链表，并输出单链表中的各元素值。3、分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单链表中的各元素值。4、删除单链表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。5、取单链表中的第5个数据元素和第7个数据元素五、问题讨论1、单链表具有什么优缺点？2、单链表的定义与顺序表的定义有什么区别？3、

4、逆序创建单链表有什么好处？4、为什么单链表中取元素、插入和删除操作在开始不判断给定位置i的合法性？115、如何改进单链表的定义，使其可以在操作前判断判断给定位置i的合法性？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题回答7、实验心得11实验二、二叉树的遍历一、实验目的1、掌握二叉树的特点及其存储方式。2、掌握二叉树的创建。3、掌握二叉树前序、中序、后序遍历的基本方法及应用。二、实验内容1、用前序方法建立一棵二叉树。2、编写前序遍历二叉树的程序。3、

5、编写中序遍历二叉树的程序。4、编写后序遍历二叉树的程序。5、编写统计二叉树叶子结点个数的程序三、实验环境TC或VC++或Java四、实验步骤1、二叉树的二叉链表存储类型定义2、建立下图所示的二叉树cabefd3、编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列4、统计以上二叉树中叶子结点的个数五、问题讨论1、先序、中序、后序遍历二叉树的区别？112、在先序、中序非递归算法中为什么使用栈？能不能借助其它数据结构来实现？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及

6、相应的运行结果6、问题回答7、实验心得11实验三、折半查找和二叉排序树一、实验目的1、掌握查找的特点。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。二、实验内容1、设有关键字序列k={5,14,18,21,23,29,31,35}，查找key=21和key=25的数据元素。2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成插入13删除关键字53和24的操作。三、实验环境TC或VC++或Java四、实验步骤1、折半查找（1）从键盘输入上述8个整数5,14,18,21,23,29,31,35，存放

7、在数组bub[8]中，并输出其值。（2）从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中的位置，否则给出查找失败的信息。（3）从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。2、二叉排序树（1）二叉排序树存储定义（2）从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树（3）输出其中序遍历结果。（4）插入数据元素13，输出其中序遍历结果。（5）删除数据元素24和53，输出其中序遍历结果。五、问题讨论111、折半查找递归算法该怎么描述？2、二叉排序树中序遍历结果有什