《数据结构》实验教学大纲课程名称：数据结构英文名称：DataStructures课程编号：2215990506课程性质：课程类型：专业基础课是否为独立设课的实验课：否适用专业：计算机与软件学院学时与学分：总学时：72总学分：3.5实验学时：18实验学分：0.5执笔人：张小健/蔡茂国制定时间：2010年8月一、实验课的任务、性质与目的本实验课程与《数据结构》课堂教学有机结合，相辅相成。在课堂教学中，比较全面、概括性地讲述数据结构学科中一些基础性知识、重要概念及各种算法，而在本实验课程中，将这些基础性知识、重要概念及各种算法，在计算机上编程实现，使学生能够达到以下教学目标：⑴、掌握计算机处理数据的基本方法⑵、了解算法需用的时间及空间分析方法⑶、能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法⑷、通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。二、主要仪器设备及环境计算机Windows软件环境TurboC/VC编程环境实验项目的设置与实验内容序号实验项目名称实验内容实验要求实验时数每组人数实验类型1多项式相加对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去必做21验证2表达式计算先将中缀表达式（就是我们通常所见的）转换为后缀表达式，比如a+b*c+d要变成abc*+d+；转换的方法用栈来实现，涉及到运算符的优先级；然后用另一个栈来对表达式计算结果选做21验证3Kmp算法求出子串（模式串）的next，利用kmp算法实验模式与主串的匹配算法选做21验证4Huffman编码根据给定一串字符（或一个文本文件），自动生成n个权值(w1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点；在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和；在F中删除这两棵树，同时将新得到的二叉树加入F中；4.重复2,3，直到F只含一棵树为止；然后求出每个字符对应的Huffman编码，继而求出整个字符串（或文本文件）的Huffman码流必做21验证5关键路径根据输入的弧，生成AOE-网。从始点开始，找出到终点的多条路径，求这些路径上的关键活动。由关键活动组成的从始点到终点的路径，即为关键路径。选做21验证6最短路经给定若干个路由器（顶点）及各路由器之间的代价值（顶点之间的权值），求从指定路由器（始点v0）开始，到其它各路由器（其余各顶点）的最短路径，直到所有路由器（顶点）计算完成为止必做21设计7二叉排序树给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根结点的值，则向左子树查找；如果大于根结点的值，则向右子树查找。如果查找到叶子结点leaf，仍没有找到记录，则：如果关键字的值小于leaf的值，则插入该leaf结点的左边，做leaf的左孩子，否则做leaf的右孩子必做21验证8希尔排序先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序必做21验证9快速排序通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小。再对两个部分分别进行快速排序。选做21验证10堆排序首先将一个无序序列建成一个堆；然后输出堆顶元素；在输出堆顶元素之后，调整剩余的元素成为一个新堆。选做21验证四、教材、实验教材（指导书）教材：严蔚敏、吴伟民，数据结构，C语言版，清华大学出版社，2010.3实验教材：自编五、考核方式与评分办法1、设计型实验（最短路径）考核方式：现场检查与实验报告评分方法：⑴、实验态度20分，⑵、实验设计40分，⑶、实验结果40分2、验证型实验考核方式：实验报告与现场检查评分方法：⑴、实验态度20分，⑵、实验结果80分六、大纲审核人/执笔人：蔡茂国编写说明：1、教学计划中有安排实验学时的课程和单独设课的实验课程，已开出或即将开出的教学实验均应编写教学实验大纲。2、课程编号、课程名称、课程类型按教学计划的要求编写。课内上机学时可视为实验学时。3、实验类型是指：验证型、综合型、设计型和研究探索型；4、实验要求是指：必做、选做和其它；