《《数据结构》实验》由会员分享,可在线阅读,更多相关《《数据结构》实验(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、了解每一种排序算法的时间以及空间复杂度。实验内容】 任意给出一组关键字(关键字的个数和值在运行时由键盘输入),分别采用直接插入排序 希尔排序和快速排序算法对其进行排序,并输出每个排序算法得到的序列。