数据结构实验指导书.docx

数据结构实验指导书

第一篇：数据结构实验指导书目录实验规则················································2实验环境················································2实验报告要求············································3实验一单链表（一）······································4实验二单链表（二）······································5实验三栈···············································6实验四二叉树···········································7实验五最短路径·········································8实验六内部排序·········································9实验规则为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则：1、实验前必须充分预习，完成指定的预习任务。预习要求如下：（1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。（3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。2、遵守以下纪律：（1）在实验室不得做和实验无关的事情。（2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。（4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。实验环境本实验在386以上的微机上进行，运行环境为VC6.0。实验报告要求1、实验题目2．实验目的3．实验环境4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案6．实验思考：（学生对本次实验的收获的总结）实验一单链表（一）一、实验目的掌握线性表的链式存储结构及其基本操作。二、预习要求1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。2、根据要求，编写程序准备上机调试。三、实验内容实现一个简单的学生信息管理系统，该系统的功能有：1、利用单链表建立学生基本信息表2、浏览每个学生的信息3、根据学号查询某个学生的基本信息4、添加学生信息到单链表中5、删除一个学生的信息四、实现提示设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。实验二单链表（二）一、实验目的掌握线性表的链式存储结构及其基本操作。二、预习要求1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。2、根据要求，编写程序准备上机调试。三、实验内容1、实现单链表的就地逆置。2、建立两个非递减有序单链表，然后合并成一个非递减链表。3、建立两个非递减有序单链表，然后合并成一个非递增链表。4、编写一个主函数,调试上述算法。四、选做题、思考题1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。2、约毖夫环的实现。3、如何利用文件实现学生信息的存取。实验三栈一、实验目的深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。二、预习要求1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。2、根据要求，编写程序准备上机调试。三、实验内容利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。四、实现提示1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。2、采用顺序存储实现栈的初始化、入栈、出栈操作。五、选做题、思考题1、两栈空间共享时，栈满的条件是什么？2、为停车场编制进行管理的模拟程序（习题集P96，2.1）。3、编写程序，利用栈实现表达式求值。实验四二叉树一、实验目的通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。二、预习要求二叉树的三种遍历方法。三、实验内容1、输入字符序列，建立二叉链表。2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。3、求二叉树的叶子结点个数。4、在主函数中设计一个简单的菜单，分别调试上述算法。四、选做题、思考题1、如何实现二叉树的后序遍历（非递归）。2、如何求二叉树的高度。实验五最短路径（旅游景点导游咨询模拟）一、实验目的利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。二、预习要求学习了解图的存储结构，掌握求最短路径的两种算法。三、