搜索
《数据结构》课程实验指导书河南理工大学地理信息系统专业二〇〇八年九月前言《数据结构》是计算机科学与技术及GIS专业的一门重要专业基础课，它主要介绍线性结构、树型结构、图状结构三种逻辑结构的存储实现，在此基础上介绍一些典型算法，以及算法的时间、空间效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过本课程的学习，使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法（存储结构），以及相关基本操作的算法实现；掌握典型算法的设计思想及程序实现；熟悉各种数据结构在GIS软件开发、程序设计中的基本应用；培养和训练学生结合实际应用，根据实际问题选取合适的数据结构、存储方案设计出简洁、高效、实用的算法；并为学习《空间数据库原理》、《GIS设计与开发》等后续课程和研制开发各种系统和应用软件打下扎实的理论与实践基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写此实验指导书。实验指导书按照实验教学大纲的要求，为每个主要的知识点精选了的典型的实验题目，对每个实验题目提出具体实现要求，并对算法的实现进行提示，希望对同学们完成实验有所帮助。目录实验一线性表的链表实现类的设计…………………………………………………………1实验二顺序栈的自定义类设计………………………………………………………………2实验三字符串的操作类设计…………………………………………………………………3实验四树和二叉树的自定义类的设计………………………………………………………4实验五图的最短路径算法设计………………………………………………………………5实验六自定义类应用综合设计………………………………………………………………6实验一线性表的链表实现类的设计实验类型：验证性实验学时：2学时一、实验目的：1、掌握C++面向对象类的设计和用VC++上机调试线性表的基本方法；2、掌握线性表的基本操作，如插入、删除、查找，以及线性表合并等运算在链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。二、实验要求：1、C++完成类的设计及基本操作算法并上机调试通过。2、撰写实验报告，提供实验结果和数据。三、实验内容:设计你的线性表的链式存储结构类，编程实现通过键盘输入数据建立链表、查找、插入结点、删除结点、显示链表以及两链表的合并运算等操作。测试数据示例：(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、程序调试通过，可运行；3、通过测试数据和对象方法调用验证算法正确性。七、实验结果处理：对程序调试中的问题要进行总结。八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、实验报告要求：本门课程实验报告格式见附件1，鼓励手写，可以打印。实验二顺序栈的自定义类设计实验类型：验证性实验学时：2学时一、实验目的：1、掌握用VC++上机调试通过栈的顺序存储结构类的设计；2、掌握顺序栈的基本操作，如进栈、出栈、判断栈空和栈满，取栈顶元素等运算在顺序存储结构上的运算；并能够运用栈的基本操作解决问题，实现相应算法。二、实验要求：1、C++完成类的设计及基本操作算法并上机调试通过。2、撰写实验报告，提供实验结果和数据。三、实验内容:设计你的栈的顺序存储结构类，编程实现栈的基本操作。栈中的数据元素类型最好为字符类型，方便今后对字符串的算法设计和应用。测试数据示例：(1)以“ABCDEFG”的字符串顺序进栈；(2)以合适顺序出栈得到序列“CDBAGFE”；(3)取栈顶元素得到‘F’；(4)进栈直到栈满和出栈直到栈空，检验对这两种情形的正确判断和处理。可通过应用你设计的栈来实现一个简单图形编辑系统的“后悔”（回退）操作功能，如取消以前的几步不同类型的操作（删除刚画的图形、取消对顶点的编辑、取消图形的几何变换等），关键是对“回退”所需的保存的历史信息的结构设计要合理。注:也可以完成课本第三章习题3.13题（P132）的代码设计作为本次课堂实验内容。四、仪器设备:计算机、VC++编译环境五、实验方法：用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、实验步骤：1、在上机前提前完成设计代码；2、程序调试通过，可运行；3、通过测试数据和对象方法调用验证算法正确性。七、实验结果处理：对程序调试中的问题要进行总结。八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、实验报告要求：本门课程实验报告格式见附件1，鼓励手写，可以打印。实验三字符串的操作类设计实验类型：验证性实验学时：2学时一、实验目的：1、掌握动态分配空间的字符串的顺序存储类（链类）的设计；2、掌握实现字符串的基本操作，如求串的长度、串的比较、复制、串的连接，取子串、子串匹配定位和串替换等运算。二、实验要求：1、C++完成类的设计并上机调试通过。2、撰写实验报告，提供实验结果和数据。三、实验内容:用堆分配存储表示串，实现串的比较、复制、串的连接，取子串、子串匹配定位和串替换等基本操作。测试数据示例：(1)以“abcde”构造一个串s1，以“gabcdef”构造另一个串s2；(2)比较s1和s2是否相等；(3)在s2中定位s1子串；(4)复制s2串并连接在s1串后。可尝试对下面的一段文本进行字符串的分析处理，自动提取其中不同的英文单词并另存为一个新的文本，示例文本：原文：美国职业篮球赛组织叫做全国篮球协会（theNationalBasketballAssociation，简称NBA）。每年夏初，协会举办称为theWorldChampionship(即NBA决赛)的年度锦标赛。分析提取英文文本格式：theNationalBasketballAssociationNBAWorldChampionship注:也可以完成课本第四章习题4.17题（P185）的代码设计作为本次课堂实验内容。四、仪器设备:计算机、VC++编译环境五、实验方法：用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、实验步骤：1、在上机前提前完成设计代码；2、程序调试通过，可运行；3、通过测试数据和对象方法调用验证算法正确性。七、实验结果处理：对程序调试中的问题要进行总结。八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、实验报告要求：本门课程实验报告格式见附件1，鼓励手写，可以打印。实验四树和二叉树的自定义类的设计实验类型：验证性实验学时：2学时一、实验目的：1、进一步掌握树的结构及非线性特点，递归特点和动态性。2、巩固对指针的使用和二叉树的三种遍历方法、建立方法及树的输入输出。二、实验要求：1、C++完成类的设计并上机调试通过。2、撰写实验报告，提供实验结果和数据。三、实验内容:实现二叉树的遍历，实现先序、中序和后序递归遍历算法；利用栈实现二叉树先序、中序遍历的非递归算法。测试数据示例：(1)以层序遍历序列为abcdefghijklmn构造一棵二叉树；(2)分别输出其先序、中序和后序遍历结果；可尝试通过设计合适的树结构对地图矢量或栅格数据建立高效的格网索引算法，用于地图的快速显示和查询。注:也可以完成课本第五章习题5.37题（P250）的代码设计作为本次课堂实验内容。四、仪器设备:计算机、VC++编译环境五、实验方法：用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、实验步骤：1、在上机前提前完成设计代码；2、程序调试通过，可运行；3、通过测试数据和对象方法调用验证算法正确性。七、实验结果处理：对程序调试中的问题要进行总结。八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、实验报告要求：本门课程实验报告格式见附件1，鼓励手写，可以打印。实验五图的最短路径算法设计实验类型：验证性实验学时：2学时一、实验目的：了解最短路径的概念，掌握求最短路径的方法(Dijkstra算法或Floyd算法)。二、实验要求：1、C++完成图的相关类及算法的设计并上机调试通过。2、撰写实验报告，提供实验结果和数据。三、实验内容:建立一个包含6个结点的带权有向图，并求顶点V0到其它顶点的最短路径。测试数据由同学们自行选择。模拟简单的道路网数据进行交互式的最短路径查询算法（Dijkstra算法）示例。注:也可以完成课本第八章习题8.23题（P395）的代码设计作为本次课堂实验内容。四、仪器设备:计算机、VC++编译环境五、实验方法：用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。六、实验步骤：1、在上机前提前完成设计代码；2、程序调试通过，可运行；3、通过测试数据和对象方法调用验证算法正确性。七、实验结果处理：对程序调试中的问题要进行总结。八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。九、预习与思考题：见课堂讲授课件和作业布置。十、实验报告要求：本门课程实验报告格式见附件1，鼓励手写，可以打印。实验六自定义类应用综合设计实验类型：综合性实验学时：2学时一、实验目的：1、进一步掌握各种数据结构的特点和适合解决问题的分析；2、通过具体的有实际应用意义的问题解决和对前面设计的类的使用进一步提高程序设计能力和算法设计、分析能力。3、考察学生的程序设计中的逻辑思维能力和软件开发设计能力。二、实验要求：1、完成程序或简单系统的设计并上机调试通过。2、撰写实验报告，提供实验结果和数据。三、实验内容:从下面给出的题目中选做其中的一题（多做可加分）：1.约瑟夫环问题1）问题描述：有编号为1,2…n的n个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。2）实验要求:采用链式存储结构实现，结果可视化要友好。3)实现提示：用链式存储解决此问题时可以采用循环链表。2.停车场管理问题1）问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车走开，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编写程