数据结构实验new

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构实验课程,陈红英,公共邮箱,密码：,computer,老师会将每次实验的要求及相关文献发到信箱中，大家可到信箱中查看，也可预习实验内容。,数据结构课程实验重要性,数据结构实验单独学分。,数据结构实验是数据结构课程考试主要内容。,数据结构课程考试：手工题目,25%,，编程题目,75%,，编程内容集中在实验内容中。,实验要求,一共八个实验，我们分单双周。每个实验,4,个学时。,大家尽量在课堂上完成。如课堂没有完成在下次实验前完成。,下次做实验会抽查上次实验。,重要注意事项（,1,）,大家每次实验时提交上次实验的内容（包括实验源程序和实验报告）。,不是每个实验都需要实验报告，需要实验报告的实验有：,利用链表实现的学生健康系统,利用二叉树实现的学生健康系统,哈夫曼编码,/,译码,每个同学注意保留自己每次实验的源程序和实验报告（每次提交给老师的文档只供老师检查，不负责保存），期末时提交给班干部，由班干部刻录成光盘，交给老师。,重要注意事项（,2,）,提交的源程序不能只是,CPP,文件，应该包含相关的工程文件，并经过压缩。,重要注意事项（,3,）,-,学期末上交文件夹名及其排列示例,提交的实验报告要求,实验报告一共三个，是实验课程打分的重要依据，请大家注意。,不要雷同。,主要内容包括实验内容，实验思路，解决方案，流程图，程序主要界面图，部分源程序，要求不少于,8-10,页。,不要把源程序原样拷贝在,word,中就当做实验报告就上交。,实验报告内容要求,封面,1,、综设实验题目,2,、中文摘要,3,、关键词,4,、前言（实验目的、意义和实验内容概述）,5,、实验设计（采用的关键技术、主要设计思想与设计流程等）,6,、实验实现（主要功能模块分析、采用的软硬件平台介绍）,7,、结果及结果分析,8,、参考文献,实验报告中参考文献格式,1,数据结构,，,朱振元，,2003,，清华大学出版社,2,数据结构实验指导书,，,2008,，华南师范大学计算机学院自用教材,。,注意参考文献不要太少。,各实验内容要求,尽量用教材中的类。,在此基础上编写自己的类或主函数。,注意：教材中的类一定要理解。在理解的基础上加以应用。,如果教材中有些内容不明白也可以问。,实验,1,利用顺序表实现学生健康系统,题目 学生健康情况管理系统,【,问题描述,】,实现学生健康情况管理的几个操作功能（新建、插入、删除、从文件读取、写入文件和查询、屏幕输出等功能）。健康表中学生的信息有学号、姓名、出生日期、性别、身体状况等。,【,实验内容,】,必做内容,1,利用顺序存储结构来实现,2,系统的菜单功能项如下：,1-,新建学生健康表,2-,向学生健康表插入学生信息,3-,在健康表删除学生信息,4-,从文件中读取健康表信息,5-,向文件写入学生健康表信息,6-,在健康表中查询学生信息（按学生学号来进行查找）,7-,在屏幕中输出全部学生信息,8-,退出,实验,1,几个注意事项,1.,如何将学生信息加入到我们教材中顺序表的类结合起来。,提示：建立,struct,student ,代替顺序表中的,Telem,.,2.,注意操作顺序。应该是,这三个操作不能反：,新建学生健康表,向学生健康表插入学生信息,在健康表删除学生信息,这两个操作不能反：,向文件写入学生健康表信息,从文件中读取健康表信息,。,大家理解为什么？,与实验,1,类似的课后练习,设线性表存储在数组,A1.arrsize,的前,elenum,个分量中，且递增有序。试编写一个算法：将,x,插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。,实验,2,利用链表实现学生健康系统,大实验,（需要实验报告）,题目 学生健康情况管理系统,【,问题描述,】,实现学生健康情况管理的几个操作功能（新建、插入、删除、从文件读取、写入文件和查询、屏幕输出等功能）。健康表中学生的信息有学号、姓名、出生日期、性别、身体状况等。,【,实验内容,】,必做内容,1,利用链式存储结构来实现,2,系统的菜单功能项如下：,1-,新建学生健康表,2-,向学生健康表插入学生信息,3-,在健康表删除学生信息,4-,从文件中读取健康表信息,5-,向文件写入学生健康表信息,6-,在健康表中查询学生信息（按学生学号来进行查找）,7-,在屏幕中输出全部学生信息,8-,退出,与实验,2,要求类似，只是在用链表实现。,注意要用教材上的,class Node,和,class,LinkList,，为什么用两类？,如何将学生信息与我们教材中链表的类结合起来。,提示：建立,struct,student,代替顺序表中的,Telem,.,实验,3,顺序栈实现算术表达式,注意：采用书中的堆栈（顺序栈）的类，不要用,C,语言自有的,stack,。,步骤：,首先建立堆栈类。,主函数中调用教材算术表达式的程序。,实验,4,用二叉树实现学生健康系统,（大实验）,（需要实验报告）,用二叉树实现学生健康系统（,1,）,需要实验报告,具体做法,建立二叉树类（包括二叉树结点类和二叉树类）。,在主函数中调用,build0,建立二叉树。,提示：,build0,采用的先根遍历，输入时应该输入你要建立的树的先根遍历的顺序。,Build0,在数组中调数据，那么数组中的数据应该是需要建立的树的先根遍历顺序。,在主函数中调用其他函数。,实验,5,哈夫曼编码,/,译码（大实验）,（需要实验报告）,哈夫曼编码,/,译码,需要实验报告,详见实验说明书,实验,6,图的遍历,图的遍历,1.,分别写出用邻接矩阵和邻接表做图的存储结构，并分别实施广度优先遍历和深度优先遍历。,选做题：,1.,写出求最小生成树的算法。,实验,7,查找算法,查找算法,1.,写出二分查找算法。,2.,编写一个采用二叉链式结构做存储结构的二叉排序树建立和查找算法。,选做题：,1.,用拉链方法解决冲突的散列存储及查找。,实验,8,排序算法,实验,8,排序算法,1.,写出快速排序算法。,2.,写出冒泡排序算法。,3.,写出直接选择排序算法。,其他选作内容（,1,）,1.,设线性表存储在数组,A1.arrsize,的前,elenum,个分量中，且递增有序。试编写一个算法：将,x,插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。,2.,已知单链表,L,中的结点是按值非递减有序排列的，试编写一算法将值为,X,的结点插入到表,L,中，使得,L,仍然有序。,3.,用单链表作存储结构，编写一个实现线性表中元素逆置的算法。,4.,已知一个单链表中的数据元素含有三类字符（即字母字符，数字字符和其它字符），试编写算法，构造三个循环链表，使每个循环链表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间。,5.,试编写一个算法，找出一个循环链表中的最小值。,其他选作内容（,2,）,1.,以二叉链表作存储结构，编写一个算法将二叉树左、右子树进行交换的算法。,2.,一棵具有,n,个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行前序遍历。,3.,试编写算法判别两棵二叉树是否等价。如果,T1,和,T2,都是空二叉树，或,T1,和,T2,的根结点的值相同，并且,T1,的左子树与,T2,的左子树是等价的；,T1,的右子树与,T2,的右子树是等价的。,4.,设计一个实现一棵二叉树复制的算法。,5.,编写一个将二叉树的所有叶子结点从左向右链接成单链表的算法。,6.,设具有,n,个结点的完全二叉树采用顺序存储结构，试写一个算法将该顺序存储结构转换为二叉链式存储结构。,7.,设具有,n,个结点的二叉树采用二叉链式存储结构，试写出一个算法将该二叉链式存储结构转换为顺序存储结构。,