《数据结构》培训课程实验书.docVIP

PAGE / NUMPAGES 《数据结构》课程 实验指导书 河南理工大学 地理信息系统专业 二〇〇八年九月 前 言 《数据结构》是计算机科学与技术及GIS专业的一门重要专业基础课，它主要介绍线性结构、树型结构、图状结构三种逻辑结构的存储实现，在此基础上介绍一些典型算法，以及算法的时间、空间效率分析。 这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过本课程的学习，使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法（存储结构），以及相关基本操作的算法实现；掌握典型算法的设计思想及程序实现；熟悉各种数据结构在GIS软件开发、程序设计中的基本应用；培养和训练学生结合实际应用，根据实际问题选取合适的数据结构、存储方案设计出简洁、高效、实用的算法；并为学习《空间数据库原理》、《GIS设计与开发》等后续课程和研制开发各种系统和应用软件打下扎实的理论与实践基础。 学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写此实验指导书。实验指导书按照实验教学大纲的要求，为每个主要的知识点精选了的典型的实验题目，对每个实验题目提出具体实现要求，并对算法的实现进行提示，希望对同学们完成实验有所帮助。 目录 实验一 线性表的链表实现类的设计…………………………………………………………1 实验二 顺序栈的自定义类设计………………………………………………………………2 实验三字符串的操作类设计…………………………………………………………………3 实验四 树和二叉树的自定义类的设计………………………………………………………4 实验五 图的最短路径算法设计………………………………………………………………5 实验六 自定义类应用综合设计………………………………………………………………6 实验一线性表的链表实现类的设计 实验类型： 验证性实验学时：2学时 一、实验目的： 掌握C++面向对象类的设计和用VC++上机调试线性表的基本方法； 掌握线性表的基本操作，如插入、删除、查找，以及线性表合并等运算在链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。 二、实验要求： C++完成类的设计及基本操作算法并上机调试通过。 撰写实验报告，提供实验结果和数据。 三、实验内容: 设计你的线性表的链式存储结构类，编程实现通过键盘输入数据建立链表、查找、插入结点、删除结点、显示链表以及两链表的合并运算等操作。 测试数据示例： (1) 以L1={0, 5, 9, 10, 12, 12, 17, 20, 24}构造链表； (2) 找到重复的第二个元素12并删除它； (3) 在第五个元素后插入55； (4) 生成L2 = {33, 45, 50}的链表并将它与L1的链表合并。 可通过对你设计的链表类的简单应用来验证相应类的成员函数代码的正确性。如：管理以下学生表格信息，能打印表格内容，并能修改表格信息、添加学生、删除学生等操作。 学号 姓名 年龄 专业 106090501 李明 18 计算机信息安全 203090211 赵高朋 19 电气自动化 405090521 周亮 19 地理信息 注: 也可以完成课本第二章习题2.14题（P85）的代码设计作为本次课堂实验内容。 四、仪器设备:计算机、VC++编译环境 五、实验方法： 用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。 六、实验步骤： 在上机前提前完成设计代码； 程序调试通过，可运行； 通过测试数据和对象方法调用验证算法正确性。 七、实验结果处理：对程序调试中的问题要进行总结。 八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。 九、预习与思考题：见课堂讲授课件和作业布置。 十、实验报告要求：本门课程实验报告格式见 附件1，鼓励手写，可以打印。 实验二顺序栈的自定义类设计 实验类型： 验证性 实验学时：2学时 一、实验目的： 掌握用VC++上机调试通过栈的顺序存储结构类的设计； 掌握顺序栈的基本操作，如进栈、出栈、判断栈空和栈满，取栈顶元素等运算在顺序存储结构上的运算；并能够运用栈的基本操作解决问题，实现相应算法。 二、实验要求： C++完成类的设计及基本操作算法并上机调试通过。 撰写实验报告，提供实验结果和数据。 三、实验内容: 设计你的栈的顺序存储结构类，编程实现栈的基本操作。栈中的数据元素类型最好为字符类型，方便今后对字符串的算法设计和应用。 测试数据示例： (1) 以“ABCDEFG”的字符串顺序进栈； (2) 以合适顺序出栈得到序列“CDBAGFE”； (3) 取栈顶元素得到‘F’； (4)