《数据结构》课程实验指导书(11一12).doc

《数据结构》课程 实验指导书 XXXX大学 地理信息系统专业 二〇〇八年九月 前 言 《数据结构》是计算机科学与技术专业的专业基础课学生结合实际应用 线性表的链表实现类的设计 实验类型： 验证性 实验学时：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) 进栈直到栈满和出栈直到栈空，检验对这两种情形的正确判断和处理。 可通过应用你设计的栈来实现一个简单图形编辑系统的“后悔”（回退）操作功能，如取消以前的几步不同类型的操作（删除刚画的图形、取消对顶点的编辑、取消图形的几何变换等），关键是对“回退”所需的保存的历史信息的结构设计要合理。 注: 也可以完成课本第三章习题3.13题（P132）的代码设计作为本次课堂实验内容。 四、仪器设备: 计算机、VC++编译环境 五、实验方法： 用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。 六、实验步骤： 在上机前提前完成设计代码； 程序调试通过，可运行； 通过测试数据和对象方法调用验证算法正确性。 七、实验结果处理：对程序调试中的问题要进行总结。 八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。 九、预习与思考题：见课堂讲授课件和作业布置。 十、实验报告要求：本门课程实验报告格式见 附件1，鼓励手写，可以打印。 实验三 字符串的操作类设计 实验类型： 验证性 实验学时：2学时 一、实验目的： 掌握动态分配空间的字符串的顺序存储类（链类）的设计； 掌握实现字符串的基本操作，如求串的长度、串的比较、复制、串的连接，取子串、子串匹配定位和串替换等运算。C++完成设计并上机调试通过。 撰写实验报告，提供实验结果和数据。 : 用堆分配存储表示串，实现串的等基本操作。 : 计算机、VC++编译环境 五、实验方法： 用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。 六、实验步骤：