2022年数据结构实验指导书 3.pdf

《2022年数据结构实验指导书 3.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验指导书 3.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导书综合说明本实验指导书结合课本，着重于指导学生理解课本讲解的数据结构和算法实现思路， 因此不直接提供可编译运行的代码，要求学生按照课本的类 C语言代码，自行调试程序， 从而提高代码编写能力和设计能力。课本中类 C语言代码，大部分符合C语言语法，不符之处说明如下：1、 类 C语言代码，没有给出类型声明，在编程过程中必须补全。2、 代码中找不到的类型和常量定义，参见课本第一章第三节。3、 类 C语言代码输入输出函数： scanf和 printf没有给出格式串，在编写 C语言代码是必须补全。4、 形如 a1.n=b1.n的赋值形式 C语言不支持， 需要通过循环来完成元素的逐个赋值5、

2、 没有 exit函数，可使用 return替代。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 实验一：线性表1. 实验目的要求本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现；掌握动态链表结构及相关算法设计实验要求：输入和验证程序例题。正确调试程序，记录程序运行结果。完成实验报告。2. 实验主要内容2.1 实现顺序表的创建、插入、删除和输出功能。2.2 线性表的单链表设计以及各种基本操作的实现。2.3 实现两个有

3、序单链表的合并。3. 实验步骤2.1 实验步骤建立 main 函数。输入 P22 线性表 SqList 的定义和相关的常量定义。输入调试算法2.3 ，初始化顺序表（注意初始化前声明顺序表变量）。编写函数，为顺序表录入数据。编写线性表输出函数， 通过循环依次输出SqList 中的各个元素的内容。输入调试算法2.4 ，插入元素（在插入元素方法前后分别输出顺序表，观察插入结果是否正确） 。输入调试算法2.5 ，删除元素（在删除元素方法前后分别名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

4、2 页，共 7 页 - - - - - - - - - 输出顺序表，观察删除结果是否正确） 。2.2 实验步骤建立 main 函数。输入 P28链表 LinkList和结点 LNode的定义。实现算法 2.11 ，创建单链表。编写链表表输出函数，通过While 循环依次输出 LinkList中的各个元素的内容。输出刚创建的链表。实现算法 2.8 ，获得第 i 个数据元素实现算法 2.9 ，在链表中插入数据元素，可通过输入链表检查结果。实现算法 2.10 ，在链表中删除元素，可通过输入链表检查结果。2.3 实验步骤使用链表创建函数，创建链表a 和链表 b，输出链表 a 和链表 b实现算法 2.1

5、2输出合并链表 b，比对结果是否正确实践二：栈和队列1. 实验目的要求本次实验的目的在于使学生深入了解栈和队列的特征，掌握在实际问题背景下的灵活运用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 实验要求，正确调试本程序，记录输出结果。完成实验报告。2. 实验主要内容2.1 用顺序结构表示栈并实现栈的各种基本操作2.2 十进制数向 N进制数据的转换。2.3 使用栈检查括号匹配的检验2.4 采用链式结构表示队列并实现各种基本操作

6、实现（选做）。3实验步骤2.1 实验步骤建立 main 函数按 p46 录入 SqStack 类型定义和相关常量定义，注意常量定义后没有分号 （课本上有错误），函数原型说明部分可不录入。录入并调试 p47 方法 InitStack、 GetTop、Push、 Pop方法编写方法输出栈中元素内容调用方法，出栈入栈若干元素，通过输出栈内容，观察栈内容变化2.2 实验步骤将 2.1 中完成的栈定义和方法，形成头文件由于本实验项目处理的是整数，因此需要将SElemType定义为 int录入并调试算法3.1 ，注意调用 Scanf 方法录入数据时，变量前要加地址符 &，即：scanf( “%d ”，&N

7、);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 2.3 实验思路栈操作为字符，因此需要将SElemType定义为 char循环：获取一个字符，当字符，如果是左括号，入栈；如果是右括号，判断栈顶括号是否和右括号匹配，如匹配，栈顶元素出栈，读入下一个字符，继续循环；如果不匹配，退出循环，返回false ；如果字符不是括号，提示输入错误， 退出方法。如果所有字符读取完毕， 栈为空，返回 true ，则括号匹配，否则括号不匹配，返回

8、false 。2.4 实验步骤录入 p66链队列定义实现 p67，链队列 InitQueue、DestroyQueue 、EnQueue、DeQueue 方法。实现输出队列内元素方法入队列、出队列若干数据，观察队列内容变化实践三：树的应用1. 实验目的要求通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树，正确调试本程序。能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

9、- - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 实验报告。2. 实验主要内容2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。2.2 根据已知的字符及其权值， 建立哈夫曼树， 并输出哈夫曼编码。3实验步骤2.1 实验步骤输入 p127 二叉链表的定义录入调试 p131算法 6.4 ，实现二叉树的构造函数编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的形式，以方便观察树的结构。参考算法 6.1 ，实现二叉树的前序、中序和后序的递归遍历算法。为简化编程，可以将visit函数直接使用 printf函数输出

10、结点内容来代替。实践四：图及图的应用1. 实验目的要求理解图的基本概念， 两种主要的存储结构。 掌握在邻接链表存储结构下的图的深度优先递归遍历、广度优先遍历。通过选做题最短路径问题 认识图及其算法具有广泛的应用意义。实验要求：正确调试程序。写出实验报告。2. 实验主要内容2.1在邻接链表存储结构下的图的深度优先递归遍历、广度优先名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 遍历。2.2最短路径问题 ，以校园导游图为实际背景进行

11、设计。（选做）实践五：查找1. 实验目的要求了解静态搜索、动态搜索和哈希（散列）搜索表的基本方法。实验要求：正确调试程序，记录结果，写出实验报告。2. 实验主要内容2.1编写折半查找算法。2.2选用一种方法构造哈希表，并提供该哈希表查找元素的方法。实践六：排序1. 实验目的要求理解并掌握内部排序的各种算法和使用场合实验要求：正确调试程序，记录结果，写出实验报告。2. 实验主要内容2.1编写实现希尔排序、快速排序算法。2.2构造大量数据，比较算法之间的花费时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -