2016《数据结构》(-中加合作)上机实验要求.doc

数据结构（中加合作）课程实验内容与要求一、 课程简介本课程着重讲述 线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。各种查找算法 典型内部排序算法。二、 实验的作用、地位和目的数据结构是一门技术基础课，通过本课程的实验，使学生加深对课程基本内容的理解，掌握各种数据节结构的逻辑特性和存储结构；培养学生针对具体问题选择逻辑结构、存储结构、设计算法的能力，学会把书上学到的知识用于解决实际问题，培养软件开发工作所需要的专业能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。三、 实验方式与要求首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。实验时，每位学生使用一台微机，独立调试，完成程序。程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。学生记录程序的输入数据，运行结果及源程序。在一周内完成实验报告。四、 考核方式与实验报告要求实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。学生在实验后的一周内提交实验报告。实验报告按照附件中实验报告模版书写。实验报告中应包括如下内容： 实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； 实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 源程序清单与实验结果或其它说明可打印，并装订在实验报告之后。 实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分五、 实验的软硬件环境硬件环境：P以上微型计算机软件环境：Windows98/2000, turbo C或VC+6.0六、 实验内容安排实验一 链表及栈的应用（4学时）实验时间：2016年10月13日 第1-2节，10月20日第1-2节，7-0215实验目的： 理解线性表、栈的逻辑特点；掌握链表存储结构，以及插入、删除、查找等基本操作的实现算法；掌握顺序栈存储结构，以及入栈、出栈等基本操作的实现；并能够在实际问题背景下的灵活运用线性表和栈结构来解决问题。具体实验题目与要求： 每位同学按要求完成下面2个题目：编写程序实现下面算法：1一元稀疏多项式简单的计算器（实验类型：设计型）1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算2十进制数与N进制数据的转换 （实验类型：设计型）1）问题描述：将从键盘输入的十进制数转换为N（如二进制、八进制、十六进制）进制数据。2）要求: 利用顺序栈实现数制转换问题； 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四）实验二 二叉树的遍历（4学时）实验时间：2016年11月10日 第1-2节7-0215，11月11 日第5-6节，7-0219实验目的：理解二叉树的逻辑特点和二叉树的性质；掌握二叉树的二叉链表存储结构，掌握二叉树的遍历算法。具体实验题目： 第1题为必做题，第2题为选做题目：1.每位同学按下述要求实现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法1）问题描述：在主程序中提供下列菜单： 1建立树 2前序遍历树 3中序(非递归)遍历树 4后序遍历树 0结束2）实验要求： 定义下列过程： CreateTree(): 按从键盘输入的前序序列，创建树 PreOrderTree()：前序遍历树（递归） InOrderTree()：中序(非递归)遍历树 LaOrderTree(): 后序遍历树（递归） 每位同学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。2. 树的转换：我们都知道用“孩子兄弟”表示法可以将一棵一般的树转换为二叉树。请设计算法将一棵树用这种方法转换为二叉树，并输出转换前和转换后树的前序遍历序列。实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四）实验三 图的遍历（4学时）实验时间：2016年11月24日 第1-2节7-0215，11月25 日第5-6节7-0219实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。具体实验题目： 每位同学按下述要求实现相应算法： 根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索（实验类型：验证型）1）问题描述：在主程序中提供下列菜单： 1图的建立 2深度优先遍历图 3广度优先遍历图 0结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程： CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四）实验报告学院（系）名称：计算机与通信工程学院姓名* *学号* *专业计算机科学与技术(合作办学)班级*级*班实验项目实验*：* 课程名称数据结构课程代码0666126实验时间年 月 日第节实验地点7-215考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见: 教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。功能完善, 功能不全有小错无法运行正确基本正确有提示无法回答完整较完整一般内容极少无报告有无有无一、实验目的参照所给实验要求中每个实验目的。二、实验题目与要求 参照所给实验要求中每个实