《数据结构》课程教学资源（参考资料）数据结构实验指导书

数据结构 实验指导书 信息与计算科学系殷超 二零一五年七月

数据结构 实验指导书 信息与计算科学系 殷超 二零一五年七月

《数据结构》实验指导书 前言 《数据结构》课程是计算机科学与技术专业的一门专业课程。随着面向对象程序设计技 术应用领域越来越广泛，给《数据结构》课程的教学提出了新的更高的要求。 开设数据结构实验，目的就是为了学生能够更好的掌握数据结构的应用，使课堂教学应 该与实践环节紧密结合。为了给学生提供更好的试验环境，在院系领导大力支持下，我们筹 建了《数据结构》的教学实验环境。这个实验环境为同学提供了基本实验的操作和验证功能， 我们编写了实验指导书，调整了实验安排，加大了实践力度。希望同学们能够充分利用实验 条件，认真完成实验，从实验中得到应有的锻炼和培养，为今后本专业课程打下坚实的基础。 希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题， 并提出建议

《数据结构》实验指导书 —1— 前 言 《数据结构》课程是计算机科学与技术专业的一门专业课程。随着面向对象程序设计技 术应用领域越来越广泛，给《数据结构》课程的教学提出了新的更高的要求。 开设数据结构实验，目的就是为了学生能够更好的掌握数据结构的应用，使课堂教学应 该与实践环节紧密结合。为了给学生提供更好的试验环境，在院系领导大力支持下，我们筹 建了《数据结构》的教学实验环境。这个实验环境为同学提供了基本实验的操作和验证功能。 我们编写了实验指导书，调整了实验安排，加大了实践力度。希望同学们能够充分利用实验 条件，认真完成实验，从实验中得到应有的锻炼和培养，为今后本专业课程打下坚实的基础。 希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题， 并提出建议

《数据结构》实验指导书 实验要求 《数据结构》课程实验的目的是为了使学生在课程学习的同时，通过在一个多媒体实验 环境中的实际操作，对数据结构的具体应用有一个初步的了解，使学生加深了解和更好地学 握《数据结构》课程教学大纲要求的内容。 在《数据结构》的课程实验过程中，要求学生做到： (1)预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现 的情况提前作出思考和分析。 (2)认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析。 对需编程的实验，写出程序设计说明，给出源程序框图和清单。 (3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。 (4)实验课程不迟到。如有事不能出席，所缺实验一般不补。 实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第 二部分是提交书面的实验报告。此外，针对以前教学中出现的问题，网铬实验将采用阶段检 查方式，每个实验都将应当在规定的时间内完成并检查通过，过期视为未完成该实验，不计 成绩。以避免期末集中检查方式产生的诸多不良问题，希望同学们抓紧时间，合理安排，认 真完成。 -2

《数据结构》实验指导书 —2— 实验要求 《数据结构》课程实验的目的是为了使学生在课程学习的同时，通过在一个多媒体实验 环境中的实际操作，对数据结构的具体应用有一个初步的了解，使学生加深了解和更好地掌 握《数据结构》课程教学大纲要求的内容。 在《数据结构》的课程实验过程中，要求学生做到： （1）预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现 的情况提前作出思考和分析。 （2）认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析。 对需编程的实验，写出程序设计说明，给出源程序框图和清单。 （3）遵守机房纪律，服从辅导教师指挥，爱护实验设备。 （4）实验课程不迟到。如有事不能出席，所缺实验一般不补。 实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第 二部分是提交书面的实验报告。此外，针对以前教学中出现的问题，网络实验将采用阶段检 查方式，每个实验都将应当在规定的时间内完成并检查通过，过期视为未完成该实验，不计 成绩。以避免期末集中检查方式产生的诸多不良问题，希望同学们抓紧时间，合理安排，认 真完成

《数据结构》实验指导书 目录 实验一线性表的应用一一迷宫求解 实验二二叉村的应用一一哈失曼偏码 5 实验三图的应用一一最短路径 6 -3

《数据结构》实验指导书 —3— 目 录 实验一 线性表的应用-迷宫求解 4 实验二 二叉树的应用-哈夫曼编码 5 实验三 图的应用-最短路径 6

《数据结构》实验指导书 实验一线性表的应用迷宫求解 一、实验目的 1.掌握用C语言调试程序的基本方法。 2.掌握线性表的基本运算，如插入、删除等 二、实验内容 1.线性表在顺序存储结构上的插入元素，刷除元素运算 2.线性表在链式存储结构上的建链表，插入结点，删除结点运算 3.利用线形表实现迷宫。 三、实验要求 1,C+C完成算法设计和程序设计并上机调试通过。 2.撰写实验报告，提供实验结果和数据。 3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。 四、程序实现 写出每个操作的算法（操作过程） 一4

《数据结构》实验指导书 —4— 实验一 线性表的应用-迷宫求解 一、实验目的 1．掌握用 C 语言调试程序的基本方法。 2．掌握线性表的基本运算，如插入、删除等。 二、实验内容 1．线性表在顺序存储结构上的插入元素，删除元素运算 2．线性表在链式存储结构上的建链表，插入结点，删除结点运算 3. 利用线形表实现迷宫。 三、实验要求 1． C++/C 完成算法设计和程序设计并上机调试通过。 2． 撰写实验报告，提供实验结果和数据。 3． 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。 四、程序实现 写出每个操作的算法（操作过程）

《数据结构》实验指导书 实验二二叉树的应用哈夫曼编码 一、实验目的 1.进一步掌握树的结构及非线性特点，递归特点和动态性。 2.进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入 二、实验内容 1,二叉树的实现和运算 2.线索一叉树的实现 3.哈夫曼编码的实现 三、实验要求 1.用C+/C完成算法设计和程序设计并上机调试通过。 2.撰写实验报告，提供实验结果和数据。 3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。 四、程序实现 写出每个操作的算法（操作过程） 程序运行情况 五、写出输入数据及运行结果（可参见教材） 5

《数据结构》实验指导书 —5— 实验二 二叉树的应用-哈夫曼编码 一、实验目的 1．进一步掌握树的结构及非线性特点，递归特点和动态性。 2．进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入 输出。 二、实验内容 1．二叉树的实现和运算 2．线索二叉树的实现 3．哈夫曼编码的实现 三、实验要求 1．用 C++/C 完成算法设计和程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。 四、程序实现 写出每个操作的算法（操作过程） 程序运行情况 五、写出输入数据及运行结果（可参见教材）

《数据结构》实验指导书 实验三图的应用-最短路径 一、实验目的 1.进一步掌握图的结构及非线性特点，递归特点和动态性。 2.进一步巩周图的三种存储结构和二种遍历方法、最小生成树的两种求解算法。 二、实验内容 1.图的遍历 2.最小生成树 3.最短路径 三、实验要求 1.用C+/C完成算法设计和程序设计并上机调试通过。 2.撰写实验报告，提供实验结果和数据。 3.分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。 四、程序实现 1.写出每个操作的算法（操作过程） 2.程序运行情况 五、写出输入数据及运行结果（可参见教材） 6

《数据结构》实验指导书 —6— 实验三 图的应用-最短路径 一、实验目的 1．进一步掌握图的结构及非线性特点，递归特点和动态性。 2．进一步巩固图的三种存储结构和二种遍历方法、最小生成树的两种求解算法。 二、实验内容 1．图的遍历 2．最小生成树 3．最短路径 三、实验要求 1．用 C++/C 完成算法设计和程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。 四、程序实现 1．写出每个操作的算法（操作过程） 2．程序运行情况 五、写出输入数据及运行结果（可参见教材）