《《数据结构》实验》由会员分享，可在线阅读，更多相关《《数据结构》实验（6页珍藏版）》请在金锄头文库上搜索。
1、说明：1、实验报告上应在相应位置填写“课程名称” “班级”、“姓名”、“日期”和“指导教 师”等内容。2、实验报告开头要有“实验题目”、“实验目的”、“实验内容”（这三部分内容见后）， 后面的内容包括“算法设计思想（可用文字描述）”，“每个算法的N-S图”,“源代 码（要求在关键代码处写注释）”、“测试数据和（预期）结果”、“实验小结（即本次 实验遇到的问题、采取的解决办法、收获和心得等）”3、每次实验之前将实验报告写好，有关实验小结的内容可以先不写，在做完实验后再 写上，同时，还需将报告上有错的代码和结果进行订正。4、实验报告在每次下机时上交,实验报告将计入平时成绩。实验一 线性表及其应用实
2、验目的】1 、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4、通过本章实验帮助学生加深对 C 语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。顺序表实验内容】（2 学时）1. 从键盘依次输入10个整数（彼此以若干空格隔开），在内存中建立一个顺序表。然 后完成以下操作： 查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在顺序表中所 处的位置，若不存在，则显示“Not Found”。 删除：输入一个表示欲删除整数的位置的整数i
3、 （注意i的合法性），在顺序表 中删除该数，并保证删除后依然是顺序表。 插入：输入一个欲插入位置i和欲插入元素e,将e插入到第i个整数之前（注 意i的合法性）。2. 分别创建两个有序的顺序表（每个表的元素个数以及每个元素的值在运行时由键盘 输入），现将两个有序表合并，并保证新表依然为有序的顺序表。链表实验内容】（2学时）1. 从键盘依次输入10个整数（彼此以若干空格隔开），在内存中建立一个单链表。然 后完成以下操作： 查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所 处的位置，若不存在，则显示“Not Found”。 删除：输入一个欲删除的整数e,若存在则在单链表中删除第一
4、个值为e的元 素。 插入：输入一个欲插入位置i和欲插入元素e,将e插入到第i个整数之前（注 意i的合法性）。2. 分别创建两个有序的单链表（每个表的元素个数以及每个元素的值在运行时由键盘 输入），现将两个单链表合并，并保证新表依然为有序的单链表。说明：4、实验报告上应在相应位置填写“课程名称” “班级”、“姓名”、“日期”和“指导教 师”等内容。5、实验报告开头要有“实验题目”、“实验目的”、“实验内容”（这三部分内容见后）， 后面的内容包括“算法设计思想（可用文字描述）”，“每个算法的N-S图”,“源代 码（要求在关键代码处写注释）”、“测试数据和（预期）结果”、“实验小结（即本次 实验遇到
5、的问题、采取的解决办法、收获和心得等）”6、每次实验之前将实验报告写好，有关实验小结的内容可以先不写，在做完实验后再 写上，同时，还需将报告上有错的代码和结果进行订正。4、实验报告在每次下机时上交,实验报告将计入平时成绩。实验二 栈和队列的应用（2 学时）实验目的】1、熟练掌握栈和队列的结构以及这两种数据结构的特点。2、能够在两种存储结构上实现栈的基本运算。3、熟练掌握链队列和循环队列的基本运算。实验内容】假设一个算术表达式中可包含三种括号：圆括号（）、方括号以及花括号，且这三 种括号可以按任意的次序相互嵌套使用。试编写判别给定的表达式所含括号是否正确配 对出现的算法。实验四 树和二叉树的建立
6、和应用（第一次）实验目的】1、掌握树的基本概念，二叉树的基本操作及其在链式存储结构上的实现2、重点掌握二叉树的生成、遍历算法。3、掌握哈夫曼树及其应用。实验内容】按照先序序列构造一棵以二叉链表表示的二叉树T,然后对T进行非递归中序遍历、递 归后续遍历和层序遍历。实验四 树和二叉树的建立和应用（第二次）实验目的】1、掌握树的基本概念,二叉树的基本操作及其在链式存储结构上的实现2、重点掌握二叉树的生成、遍历算法。3、掌握哈夫曼树及其应用。实验内容】根据任意给定的一组权值,构造一棵哈夫曼树。具体要求如下 权值的个数以及每个权值由运行时由键盘输入。 构造完哈夫曼树后,输出每个权值的哈夫曼编码。 输出哈
7、夫曼树的带权路径长度WPL。实验五 图的建立和应用实验目的】1、熟练掌握图的邻接矩阵和邻接表的存储方式。2、实现图的一些基本算法，特别是深度和广度优先搜索。3、掌握图的一些常用算法，如最小生成树、拓扑排序、最短路径等。实验内容】建立一无向图的邻接表存储结构，并对其进行广度优先搜索，输出得到的序列。实验六 查找算法的实现（综合性实验第一次）实验目的】1、熟练掌握各种静态查找表的查找方法。2、熟练掌握二叉排序树的构造方法和查找算法3、掌握哈希表的构造方法。实验内容】任意给出一组关键字（关键字的个数和值在运行时由键盘输入），构造对应的二叉排序树 （每次先找到当前关键字的插入位置，然后将其插入），并对
8、其进行中序遍历，输出得到 的序列。实验六 查找算法的实现（综合性实验第二次） 实验目的】4、熟练掌握各种静态查找表的查找方法。5、熟练掌握二叉排序树的构造方法和查找算法。6、掌握哈希表的构造方法。实验内容】设哈希函数为Hash（key）=key%ll，解决冲突的方法为链地址法，对于任意给出一组关键 字（关键字的个数和值在运行时由键盘输入），构造对应的哈希表，在此基础上对任给的 数据进行查找，输出查找的结果。（选做：对构造好的哈希表计算成功情况下的平均查找长度。）实验七 内部排序算法的实现实验目的】1、掌握各种排序算法的思想、方法和稳定性。2、掌握快速排序、堆排序、归并排序算法的实现3、了解每一种排序算法的时间以及空间复杂度。实验内容】 任意给出一组关键字（关键字的个数和值在运行时由键盘输入），分别采用直接插入排序 希尔排序和快速排序算法对其进行排序，并输出每个排序算法得到的序列。
