《数据结构》实验.doc

《《数据结构》实验.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、说明：1、实验报告上应在相应位置填写“课程名称”、“班级”、“姓名”、“日期”和“指导教师”等内容。2、实验报告开头要有“实验题目”、“实验目的”、“实验内容”（这三部分内容见后），后面的内容包括“算法设计思想（可用文字描述）”，“每个算法的N-S图”，“源代码（要求在关键代码处写注释）”、“测试数据和（预期）结果”、“实验小结（即本次实验遇到的问题、采取的解决办法、收获和心得等）”3、每次实验之前将实验报告写好，有关实验小结的内容可以先不写，在做完实验后再写上，同时，还需将报告上有错的代码和结果进行订正。4、实验报告在每次下机时上交，实验报告将计入平时成绩。实验一线性表及其应用【实验目

2、的】1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。【顺序表实验内容】（2学时）1.从键盘依次输入10个整数（彼此以若干空格隔开），在内存中建立一个顺序表。然后完成以下操作：①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在顺序表中所处的位置，若不存在，则显示“NotFound”。②删除：输入一个表示欲删除整数的位置的整数i（注意i的合法

3、性），在顺序表中删除该数，并保证删除后依然是顺序表。③插入：输入一个欲插入位置i和欲插入元素e，将e插入到第i个整数之前（注意i的合法性）。2.分别创建两个有序的顺序表（每个表的元素个数以及每个元素的值在运行时由键盘输入），现将两个有序表合并，并保证新表依然为有序的顺序表。【链表实验内容】（2学时）1.从键盘依次输入10个整数（彼此以若干空格隔开），在内存中建立一个单链表。然后完成以下操作：①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示“NotFound”。②删除：输入一个欲删除的整数e，若存在则在单链表中删除第一个值为e的元素。③插入：

4、输入一个欲插入位置i和欲插入元素e，将e插入到第i个整数之前（注意i的合法性）。2.分别创建两个有序的单链表（每个表的元素个数以及每个元素的值在运行时由键盘输入），现将两个单链表合并，并保证新表依然为有序的单链表。说明：1、实验报告上应在相应位置填写“课程名称”、“班级”、“姓名”、“日期”和“指导教师”等内容。2、实验报告开头要有“实验题目”、“实验目的”、“实验内容”（这三部分内容见后），后面的内容包括“算法设计思想（可用文字描述）”，“每个算法的N-S图”，“源代码（要求在关键代码处写注释）”、“测试数据和（预期）结果”、“实验小结（即本次实验遇到的问题、采取的解决办法、收获和心得

5、等）”3、每次实验之前将实验报告写好，有关实验小结的内容可以先不写，在做完实验后再写上，同时，还需将报告上有错的代码和结果进行订正。4、实验报告在每次下机时上交，实验报告将计入平时成绩。实验二栈和队列的应用（2学时）【实验目的】1、熟练掌握栈和队列的结构以及这两种数据结构的特点。2、能够在两种存储结构上实现栈的基本运算。3、熟练掌握链队列和循环队列的基本运算。【实验内容】假设一个算术表达式中可包含三种括号：圆括号（）、方括号[]以及花括号{}，且这三种括号可以按任意的次序相互嵌套使用。试编写判别给定的表达式所含括号是否正确配对出现的算法。实验四树和二叉树的建立和应用（第一次）【实验目的】

6、1、掌握树的基本概念，二叉树的基本操作及其在链式存储结构上的实现。2、重点掌握二叉树的生成、遍历算法。3、掌握哈夫曼树及其应用。【实验内容】按照先序序列构造一棵以二叉链表表示的二叉树T，然后对T进行非递归中序遍历、递归后续遍历和层序遍历。实验四树和二叉树的建立和应用（第二次）【实验目的】1、掌握树的基本概念，二叉树的基本操作及其在链式存储结构上的实现。2、重点掌握二叉树的生成、遍历算法。3、掌握哈夫曼树及其应用。【实验内容】根据任意给定的一组权值，构造一棵哈夫曼树。具体要求如下：①权值的个数以及每个权值由运行时由键盘输入。②构造完哈夫曼树后，输出每个权值的哈夫曼编码。③输出哈夫曼树的带权

7、路径长度WPL。实验五图的建立和应用【实验目的】1、熟练掌握图的邻接矩阵和邻接表的存储方式。2、实现图的一些基本算法，特别是深度和广度优先搜索。3、掌握图的一些常用算法，如最小生成树、拓扑排序、最短路径等。【实验内容】建立一无向图的邻接表存储结构，并对其进行广度优先搜索，输出得到的序列。实验六查找算法的实现（综合性实验第一次）【实验目的】1、熟练掌握各种静态查找表的查找方法。2、熟练掌握二叉排序树的构造方法和查找算法。3、掌握哈希表