信息技术学院数据结构课程实施方案 玉溪师范学院

溪师范学院信息技术工程学院计算机科学与技术专业数据结构课程教学实施方案吴红庆2010年3月数据结构课程教学实施方案数据结构课程教学实施方案、课程描述1、 课程名称2、 课程性质3、 本课程与其他课程间的关系4、 基本学时、课程定位与要求1、 教学定位2、 基本要求3、 能力培养要求4、 实践教学要求5、 授课要求6、 考核要求三、课程目标四、内容大纲1、 内容矩阵2、 各章节讲授要求五、教学内容的组织方式六、课程实验1、 实验地位2、 实验提示3、 实验安排4、 实验要求5、 实验考核方式及成绩评定6、 实验内容七、考核要求和成绩评分办法1、 考核要求2、 成绩评分办法八、教学进度表九、学习指导十、多媒体课件制作要求目录151923242525一、课程描述1、 课程名称：数据结构（datastructure）2、 课程性质：计算机科学与技术专业的核心基础课程3、本课程与其他课程间的关系： （如下图所示）Web信息外理人工智能Web信息外理人工智能图形图像操作系统II数据库原理及应用 II编译系统图数据结构高级程序设计语言离散数学高等数学线性代数计算机导论高级程序设计语言离散数学高等数学线性代数计算机导论36学时。4、基本学时：基本学时108学时，其中理论课7236学时。它是研究非数值计本课程涉及数《数据结构》是计算机科学与技术专业的一门重要的核心基础课程，算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。据在计算机中的表示、组织和处理，以及相应结构上的算法设计和初步的算法性能分析技术；它主要讨论现实世界中数据（即事物的抽象描述）的各种逻辑结构在计算机中的存储结构，以及进行各种非数值运算的方法， 让学生学习、分析和研究计算机加工数据对象的特性， 掌它是研究非数值计本课程涉及数握数据的组织方法，以便选择合适的数据的逻辑结构和存储结构， 设计相应的操作运算，把现实中的问题转化为在计算机内部的表示和处理。 其内容丰富，涉及面广，在培养学生数据分析、组织、处理能力和编程能力有着极深的影响；对培养、锻炼学生抽象思维和创造能力起着十分重要的作用。随着计算机应用技术的发展，数据结构的内容也随之更新。二、教学定位与要求1、教学定位《数据结构》课程定位于地方性“应用型”人材的培养，它在整个课程体系中处于承上启下的核心地位，它不仅是对离散数学、高级程序设计语言等先修课程中学到的知识和技能的扩展和深化，同时又为进一步学习操作系统、 编译原理、数据库等专业课奠定了坚实的理论与实践基础。如何使学生更好地掌握最常用的数据结构， 理解数据结构内在的逻辑关系， 数据与关系在计算机中存储表示以及在这些数据结构上的运算和实际的执行算法，培养学生提出问题、分析问题、解决问题的能力，是这一门课程的目的和宗旨。2、 基本要求通过本课程的学习，让学生掌握求解非数值类问题的基本模型（表、树、图）的特点和适用场合，能够根据问题设计和选择好的算法， 为学习后续的操作系统、 编译原理和软件工程等专业课程，设计应用程序打下良好的基础。3、 能力培养要求通过典型数据结构和处理算法的学习， 以及算法设计和实现的训练，培养学生分析问题、解决问题的能力，学生一方面应能够根据求解问题选择合适的数据结构，设计高效的算法，提高程序设计的质量；另一方面，能够整合信息，提炼数据和数据结构简单建模，配置相应的运算和处理算法，完成信息化系统的集成。4、 实践教学要求实践教学主要是培养学生注重数据结构原理和应用的结合， 引导学生应用书本知识解决实际问题，提高学生的实际动手能力和团队合作能力。本课程实践教学环节按三个层次展开：验证性实验7设计性实验7课程设计。实践教学要求：强调基础实验内容一一验证性实验，加强设计性实验，辅以实际问题的简单应用。5、 授课要求本课程内容概念多、内容抽象，学生学习起来较为困难。教学中以数据的逻辑结构为主线，讲清概念，理清思路是首要条件。应根据最优化教学模式，设计一个好的最优化教学方案，首先要对教学对象的情况进行分析， 了解学生的基础知识掌握程度、 具备的程序设计的能力等实际情况，在课堂教学、网络多媒体辅助教学系统的设计和使用过程中要做到心中有数、有的放矢。教学方法应多样化。认真进行教学设计，积极将新教学理念和教学方法引入教学， 合理组织课堂教学，根据不同的内容及不同的需求选择诸如：讲授法、问题驱动法、讨论法、案例分析法进行教学。在授课过程中，应采用启发式教学，通过提出问题、启发思路，给出方法、分析对比，提炼思想、掌握精髓，培养学生分析问题和解决问题的能力。建议由问题驱动引出概念，从案例分析出发讲授相关知识，注重激发学生的学习积极性。教学过程中，建议合理地利用多媒体设备辅助教学，采用“课件 +板书”的教学手段，将多媒体教学与传统教学方法有机地结合起来。 在课件中将抽象的、学生难于理解的教学内容通过形象生动的动画演示出来，并在课件中融入教学意图，通过设疑、解疑等方式，引领学生的思维过程，改善教学效果。6、 考核要求紧紧围绕“以学生能力形成为核心”的教育理念，建议改变以往的笔试为主的考核方式，加大实践教学的考核比重，加强过程性考核。三、课程目标本课程的教学目标是全面系统地介绍数据的逻辑结构、 存储结构和算法实现，并介绍常用的非数值计算方法，如数据排序、查找检索等。通过本门课程的学习，培养学生抽象思维能力和逻辑推理能力，增强分析问题、解决问题和总结问题的能力， 更重要的是培养学生的专业兴趣，树立创新意识，在求解问题过程中能合理地选择数据的存储结构， 有效地设计算法，从而提高程序设计的质量。 本课程是一门理论与工程实践密切相关的综合性课程， 在相关专业的教学中占有十分重要的地位。 加强数据结构课程的建设，提高数据结构课程的教学质量，有利于教学改革和教育创新，有利于培养高素质的应用型人才。四、内容大纲本大纲定位于应用型的数据结构课程， 内容的选取和对各知识点的要求均以 “应用”为

基点，紧紧围绕“点面结合、突出重点、服务应用”的主导思想。核心内容主要包括（ 1）数据结构的基本概念，它对后续内容起到基础作用和主导作用； （2）各种基本数据结构的特点、存储表示、处理算法和效率，提示出不同数据结构的区别和内在联系； （3）通过经典问题和经典算法展示算法设计的一般规律。1、内容矩阵《数据结构》内容矩阵如下表所示:知识领域一级知识点二级知识点要求学时分配（72+36）数据结构定义数据单值类型（整形、、布尔型、字符型、指针类型，复合类型）掌握2数据结构逻辑结构，存储结构，基本运算熟练掌握抽象数据类型信息封装，数学模型了解算法与问题求解算法概念可行性，有效性，确定性，有穷性掌握2+2算法分析语句频度，正确性，时间和空间复杂度的大0表示法理解问题求解问题抽象，数据和数据结构抽象，运算抽象，算法设计掌握线性结构线性表前驱，后继，长度，存储方式；数组，单链表，双链表，循环链表；基本运算；查找，插入，删除熟练掌握8+6栈LIFO，栈顶，栈底；顺序栈，表达式求值熟练掌握4+2链式栈掌握嵌套调用，递归程序转换为非递归程序了解队列FIFO，队头，队尾；顺序队，循环队；熟练掌握4+2链式队，队的应用掌握字符串存储，运算；简单模式匹配算法掌握4+2KMP算法了解广义表原子结构，结点，表头，表尾，深度，长度，存储方式了解2矩阵数组的表示和实现特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵的转置运算掌握4+4树型结构二叉树概念定义和术语，满二叉树和完全二叉树，五条性质熟练掌握14+6二叉树遍历先序遍历，中序遍历，后序遍历熟练掌握按层次遍历了解二叉树存储顺序存储，二叉链表存储熟练掌握二叉树应用哈夫曼树及哈夫曼编码熟练掌握判定树了解树和森林树和森林的定义；树、森林与二叉树的转换熟练掌握

树的存储双亲表示法，孩子表示法，孩子兄弟表示法了解图型结构图的概念定义，术语，种类，生成树掌握10+4图的存储方法邻接矩阵，邻接表熟练掌握图的遍历广度优先遍历，深度优先遍历熟练掌握DAG拓扑排序，关键路径了解最小生成树Prim算法，Kruskal算法掌握最短路径Dijkstra算法，Floyd算法了解查找与索引基本概念查找长度，平均查找长度掌握8+4表结构的查找顺序查找，二分查找熟练掌握分块查找，索引查找了解哈希表基本概念，哈希函数，冲突处理，哈希表的构造，查找算法熟练掌握二叉排序树插入，删除掌握平衡树AVL树理解B/B+树基本概念，插入/删除操作，读盘和写盘次数分析，索引效率分析了解内部排序基本概念正序，逆序，稳定性，排序方法种类，衡量排序算法的指标掌握8+4插入排序直接插入排序，熟练掌握Shell排序掌握交换排序冒泡排序熟练掌握快速排序掌握选择排序直接选择排序熟练掌握堆排序掌握归并排序二路归并掌握基数排序顺序基数排序，链式基数排序理解排序算法分析查找和移动次数，时间复杂度和空间复杂度，排序问题的下界理解说明：依据当今计算机科学与技术的前沿技术， 结合现代数据结构的观点，织上，应注意以下几点：（1）抽象数据类型ADT适合用C++等面向对象的语言来表达。不用 C来描述，以免导致师生们的困惑。说明：依据当今计算机科学与技术的前沿技术， 结合现代数据结构的观点，织上，应注意以下几点：（1）抽象数据类型ADT适合用C++等面向对象的语言来表达。不用 C来描述，以免导致师生们的困惑。（2） 线索化二叉树已被摒弃。该部分内容可以作为例题讲解。（3） 三元组主要用于有权图输入输出，不宜于矩阵运算。（4） 索引技术中，散列和倒排，是非常主流和实用的技术；存索引，应该重点强调。（5）平衡二叉树的主流为红黑树、伸展树； AVL树删除操作难于实现和维护，不常用。B+树是比在教学内容的组等过程式的语言B树更实用的外［教学内容］（1） 什么是数据结构：主要讲授数据结构的含义，数据的分类、数据结构的存储方法、数据结构的基本运算（2） 基本概念和术语：主要讲授数据、数据元素、数据对象、数据结构、逻辑结构与存储结构、数据类型和抽象数据类型、算法、语句频度，算法的时间复杂度（3） 抽象数据类型的表示与实现：用一个实例讲解（4） 算法和算法分析：主要讲授算法的含义，算法的五个特性、算法设计的要求，算法时间复杂度的求解方法［重点］数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤。［难点］评价算法的标准和评价方法，最差和平均时间复杂度的区分。［教学要求］了解抽象数据类型及面向对象概念；理解数据结构基本概念及数据结构的抽象层次、算法的定义及算法的特性；熟练掌握算法的性能分析与度量方法。［授课提示］此部分教学内容是提纲挈领的一章， 在课程中居于首位，它覆盖了课程教学的内核知识，它是帮助学生了解课程目标、 把握课程基本内容和方法的重要环节。 教学中，要注意把握以下几点：（1） 建立“模型”意识。使学生明白表、树、图等数据结构是对客观世界的抽象，是描述数据中数据之间关系的基本模型，培养抽象描述问题的能力。（2） 建立研究主线。依照“逻辑结构7物理结构7基本运算7基本算法7算法评价”脉络，研究每种结构的特点，给学生一个清晰的研究主过程，培养学生的组织能力。（3） 注意强调下列概念的内涵：数据元素、元素集合、元素关系；逻辑结构和物理结构（即存储形式）；运算、算法和程序。（4） 讲清楚最坏情况下和平均情况下的时间复杂度的内涵，要使学生能够从低到高罗列出常用的表示算法时间耗用函数的阶，学会选择好的算法。（5） 教学策略。俗话说：“良好的开端是成功的一半”，“兴趣是学习之母”。在组织本章教学时，建议不要急于介绍理论，而是强调应用。首先通过介绍数据结构在实际生活、工作中的应用来激发学生的学习兴趣。线性表（8+6学时）I［教学内容］（［教学内容］（1） 基本概念与术语：主要讲授线性表、单链表、双向链表、空指针、头结点、头指针、首元结点（2） 线性表的类型定义及逻辑结构特征（3）线性表的顺序表示和实现：主要讲授顺序表的存储特点，查找操作的实现（4）线性表的链式表示和实现：主要讲授单链表的存储方式，循环链表、结点、指针、顺序表的插入、删除、单链表的插入、删除、查找操作的实现；双向链表及循环链表的特点及插入、删除操作的核心步骤［重点］线性表的顺序存储和式存储的特点；顺序表的基本运算（插入、删除、查找）算法和效率分析；单链表的基本运算（插入、删除、查找）算法和效率分析；循环链表和双向链表。［难点］链表概念的建立，结点、指针和结点的指针域之间的关系；单链表的基本运算；不同的链表（是否加头、加尾、循环、单向双向等）适用的场合。

［教学要求］了解线性表的类型定义。理解线性表的逻辑结构；掌握线性表的顺序表示和链式表示方法；熟练掌握顺序表和单链表的插入、删除等基本算法及其时间复杂度分析。［授课提示］表结构是应用最广泛的一种数据结构， 它是构成其他复杂数据结构的基本单元。 而线性表又是最基本的表结构，是帮助学生开启数据结构与算法的钥匙， 因此，只要将此部分内容讲解透彻了，后续章节的教学就较为轻松了，所以在本章的教学设计中要多下功夫。此部分内容首先要讲清楚表结构的特点，逻辑结构和物理结构，以及基本运算和处理算法。然后，根据表结构的特点引入线性表。在讲授过程中注意突出以下几个方面：（1）顺序存储的特点是“结点的逻辑次序与物理次序一致” ，链式存储的特点是通过结点之间的“链接”体现逻辑次序，讲授时，要通过表结构的顺序存储和链式存储的对比，反映出“时间和空间”之间的相互关系。（2）初学者往往很难建立起“链”的概念，必须先让其弄清“结点、指针和结点的指针域三者之间的关系”，再建立“链”和“链表”的概念，而后再交代清楚如何通过改变链接关系完成插入和删除操作。（3） 不带头结点的单链表是原始的链表，其实现查找、插入、删除运算的程序结构较复杂，也容易出错。根据不同的情况，适当地为链表附加“头”结点（或“尾”结点） ，或构成循环表，不仅可以简化程序结构，在某些情况下，还能提高程序速度。（4） 技术难点的处理方法。学生最难掌握的就是指针的使用及链表的基本运算，在教学设计中，针对学生难于理解的关键点， 注重对线性表两种实现方式进行对比， 强调以下几个内容：sqlistL; L是一个结构体，L是一个结构体指针，取第isqlistL; L是一个结构体，L是一个结构体指针，取第i个元sqlistL;则L中直接就有一个数组分量sqlistL;则L中直接就有一个数组分量L只是一个空的头指针，建立链表p=p-=>next。顺序表和链表的建立和遍历的区别。如：若 !L.elem［］存储数据，遍历时用i++;而若LinklistL;贝U需要动态申请每个结点并动态链接组成链表，遍历时采用对比两种情况的区别： p=p->next及P++。p->next==NULL;而循环链表中p单向链表中判断当前结点 p->next==NULL;而循环链表中p结点是否为表尾结点的条件是： p->next==head。对比：P!=NULL和p->next!=NULL的区别。1：已知第1：已知第i-1个结点的地址P,如何在其后插入一个地址为 s的新结点；子问题2:如何找第i-1个结点。（5）教学策略。以数据的“逻辑结构一一存储结构一一运算”为主线进行教学。建议采用问题驱动法，如：通过对“学生联系方法” 、“文件存储方式”、“猴子选大王”等问题的分析，引入本部分内容；在教学过程中，结合对案例（如“学生成绩管理” 、“约瑟夫问题”）的分析引入线性表的基本运算在两种存储结构下所采用的不同的实现方法；通过动画演示，帮助学生理解链表的插入/删除操作的实现方式，从而得出实现相关操作的核心算法；组织学生讨论，通过对算法效率的分析、比较，总结出各自的优势与不足，归纳得到两种数据结构的适用场合。栈和队列（8+4学时）］［教学内容］（1） 栈：主要讲授栈的含义；栈顶、栈底；栈的抽象数据类型定义；栈的顺序存储表示；栈的链存储表示（2） 栈的应用举例（3） 队列：主要讲授队头指针、队尾指针；队列的抽象数据类型定义；队列的顺序存储表示；队列的链式存储表示（4） 队列的应用举例［重点］栈和队列的概念、特点及适用场合；进栈退栈、进队出队算法。［难点］循环队列的处理算法；栈的应用（表达式求值算法）［教学要求］掌握栈和队列这两种抽象数据类型的特点；特别应注意栈满和栈空时的熟练掌握栈的两种存储结构表示时的基本操作算法的实现，特别应注意栈满和栈空时的条件及对它们的描述方法；特别应注意队满和队空时的描述方掌握循环队列和链队列的基本操作算法的算法实现，特别应注意队满和队空时的描述方法；了解递归算法的执行过程中栈的状态变化过程。［授课提示］此部分内容要在讲清楚线性表的基础上， 对线性表的运算加以限制的思路 （即栈和队列都是运算受限的线性表），引入栈、队列内容。讲授时注意突出以下几个方面：（1） 栈和队列都属于“过渡性的”结构，实现栈和队列（重点介绍顺序栈和循环队列）运算的过程中，关键在于如何设置判定“空 /满”条件。（2）栈的特点主要是“后进先出”，栈顶指针的设置方法， 入栈出栈时栈顶指针的变化。（3）队列与栈的主要区别是“先进先出”，为了便于操作，需要设置队头指针和队尾指针，入队出队时如何修改队头队尾指针。（4） 顺序栈和循环队列处理中的相关技术，需强调以下内容：顺序栈中，若定义栈顶指针： sqstacktop;栈的空间为N,且低端地址为栈底，则：入栈操作执行：top++;出栈操作执行：top--;栈空特征：top==0栈满特征：top==N注意：若高端地址为栈底，相关操作则反之。循环队列中，若定义队头、队尾指针： sqqueuefront,rear;队列空间为N，且以少用一个单元为队满，则：出队操作执行：front=（forin+1）%N;入队操作执行：rear=（rear+1）%N;队满特征：front==（rear+1）%N队空特征：front==rear求队列长度：length=（rear+N-front）%N入栈（队）操作前，需判断栈（队列）是否满；出栈（队）操作前，需判断栈（队）是否空。（5） 教学策略。采用问题驱动法，通过大量例子（如：盘子迭放、手枪弹夹、狭窄通道的进入、函数的调用、火车调度站、打印队列、银行业务的办理流程）弓I入栈和队列的概念；通过动画演示形象展现栈和队列的出入操作；结合案例（如：火车箱的调度）分析，介绍相关基本操作的实现；通过对实际问题（如各种进位计数制的转换、汉诺塔问题、迷宫问题、停车场管理等）的求解来学习栈和队列的应用。串（4+2学时）j［教学内容］（1） 串的类型定义：串的概念（2） 串的表示及实现：串的存储结构及操作算法（3）模式匹配算法的改进： KMP算法（4） 串操作应用举例［重点］串的运算，串库函数的使用方法，简单模式匹配算法的实现方法［难点］KMF算法中next（）函数和nextval（）函数的求解方法［教学要求］了解串的含义及其类型定义；理解串的三种存储表示及实现方法掌握串上实现的模式匹配了解KMP算法［讲授提示］在此部分内容的讲授过程中，注意突出以下几个方面：（1） 字符串（简称串）是一种特殊的线性表，其基本组成元素是单个字符。大多数程序设计语言都支持字符串这种数据类型。（2） 以定长顺序串为基础，重点介绍串的插入、删除、模式匹配等基本操作的实现方法。对于堆串的操作实现，只需提示与定长顺序串的不同之处即可。（3） 朴素模式匹配算法存在的一个问题是，一旦某趟匹配中发生失配，无论模式的具体情况如何，都采用模式右移一位的方式开始下一趟的匹配，这可能导致很多冗余的比较。（4） KMP算法的基本思想为：预先处理模式本身，分析其字符分布状况，并针对模式中的每一个字符，计算失配时应该右移的位数。该算法的巧妙之处在于：计算 next［］本身采用相同的匹配方法。（5） 教学策略。本章的难点是两种模式匹配的原理，因而，应采用动画演示的手段，通过对比的方法为学生形象地描述各种模式匹配在失配情况下， 下一趟匹配的起点问题。当学生真正理解算法思想后，其算法实现就容易了。数组和广义表（6+4学时）I［教学内容］（1） 数组的定义（2） 数组的顺序表示和实现（3） 矩阵的压缩存储（4） 广义表：广义表的概念；广义表的表示及操作；广义表存储结构［重点］数组的存储结构与地址计算， 特殊矩阵的压缩存储，稀疏矩阵（用三元组实现转置运算，广义表的存储结构和基本操作。［难点］多维数组的存储结构与地址计算，特殊矩阵压缩存储公式推导，用三元组表实现矩阵的快速转置，广义表的存储结构。［教学要求］了解数组的定义、矩阵的压缩存储和广义表的含义及存储方法；掌握数组的顺序存储及其实现方法熟练掌握特殊矩阵的压缩存储及其实现方法

理解广义表的定义及其基本运算了解广义表的递归算法[授课提示]数组属于“静态结构”，其元素位置和个数是固定的，不能进行插入和删除操作。n维数组可以看成每个数据元素均是 n-1维的线性表，在讲解多维数组的存储结构与地址计算时，可从二维数组推广至多维数组(掌握到四维数组即可) 。在介绍特殊矩阵的压缩存储时，提示学生注意其特殊性表现在：①元素分布有规律(对称，带状)的矩阵，只需找到对应规律的数学函数，将二维

矩阵元素下标作为转换函数的自变量， 计算出到一维内在空间的地址。注意上三角逐列存储和下三角逐行存储规律的相似之处。②非零元素很少的稀疏矩阵，只存非零元素所在的行号、列号、元素值来实现压缩存

储。压缩存储既可采用三元组表顺序存储结构， 也可采用十字链表的链式存储结构。 注意二者的优缺点。对于用三元组表实现矩阵的快速转置算法，提示学生注意转换后正确地址的计算方法。每个元素同时属于某一行和某一列,十字链表的每一行和每一列都是一个单链表，所以十字链表的操作一般同时涉及行、列两个单链表。每个元素同时属于某一行和某一列,广义表是表结构的推广，主要采用链式存储，可以看作是链表的复合体。只要普通链表弄清楚了，广义表就好理解了。重点介绍广义表的基本操作：求表头、表尾，求表的长度和深度。强调表头可能为原子也可能为表， 但表尾一定是表，通过实例讲解这种求解方(6(6)求解mxn矩阵元素a[i][j]存储位置及难点处理技术，需要强调以下内容:二维数组的按行存储公式：二维数组的按列存储公式：三角矩阵的压缩存储转换公式：k=i*(i-1)/2+j-1k=j*(j-1)/2+i-1LOC(a)=LOC(a11)+(((i-1)*n+j-1)*lLOC(a)=LOC(a11)+(((j-1)*m+i-1)*li>j(下三角)i<j(上三角)三带状矩阵的压缩存储转换公式： k=2*i+j-3稀疏矩阵采用三元组表表示实现矩阵的快速转置的技巧就是：引进两个辅助向量NUM[i](记录新矩阵中第i列非零元素的个数)以及 POS[i](记录每列的第一个非零元素在三元组表中的位置)，并且POS[1]=1,POS[i]=POS[i-1]+NUM[i-1]。(7)难点教学策略。采用启发式教学方法，通过动画演示或画图分析，归纳总结，求解问题。树和二叉树(14+6学时)I[教学内容](1(1)(2)(3)(4)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型二叉树的表示：数组表示；链表存储表示二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树中序遍历算法线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历哈夫曼树：路径长度；哈夫曼树；哈夫曼编码［重点］树的存储方式，二叉树的链式存储和遍历，二叉树的性质，递归的遍历算法及效率分析，遍历算法的应用，二叉树构造算法，二叉树与树和森林的转换，哈夫曼树及其应用，判定树的概念及作用。［难点］利用遍历对二叉树或其结点进行灵活运用， 二叉树的递归遍历算法到非递归遍历算法的转换，哈夫曼树的应用［教学要求］了解树和森林的相关概念；理解二叉树的概念，树的表示方法；熟练掌握二叉树的五条性质、 二叉树的遍历方法、二叉树的存储方式、树和森林与二叉树的转换、哈夫曼树的实现方法及哈夫曼编码的构建。［授课提示］本部分内容是全书的一个重点和难点章节。 树（连通无回路的图）是图的特例，表是树的特例。而本课程中的树专指“有根树” ，且通常不考虑边的方向。在此前提下，说“树用于描述层次关系、分支关系和嵌套关系” ，有关树的一些术语也是在这一前提下引入的。二叉树是树的特例和基础，是本课程的核心内容，所以这部分重点讲授二叉树的存储结构和操作实现。在讲授过程中特别注意以下几点：1开始；二叉链表存储结构，提示（11开始；二叉链表存储结构，提示（2） 二叉树的五条性质的应用较为广泛，建议结合实例来讲授。（3） 二叉树遍历算法是数据访问的基础算法，遍历是一种手段，访问的目的则是因问题的不同而不同。先把遍历运算的特点和遍历路线讲清楚，然后强调递归遍历程序与栈的关系，使学生对递归程序的执行流程有正确的认识和充分的理解， 为更好地应用研究递归遍历算法解决问题打下基础，培养学生举一反三的能力。（4） 二叉树遍历的应用是从易到难的一个过程：利用遍历算法可以输出所有结点，加一些条件即可输出所有叶子结点， 进一步可以实现左右子树交换，树状打印和二叉树的线索化等应用，并注意分析具体问题对遍历顺序的要求。 注意体会栈和队列在二叉树遍历中的应用。二叉树的层次遍历需要借助队列实现， 其他遍历需要借助栈结构实现， 递归算法采用系统隐式栈，非递归算法采用用户自定义的显示栈。（5）构造二叉树的关键是“定根”和“子树” 。“定根”是指确定根结点，“子树”是指可以分出左右子树上的结点，把握住这个特征，就易于求解各种演变的造树问题了。（6） 借助示例讲透如何把对树或森林的运算转化为对二叉树的运算，灵活运用树、森林和二叉树之间的相互转换关系，引导学生学习发散思维，探寻事物之间的内在联系。（7） 二叉树遍历算法的递归调用是较复杂的问题，无法直接转换成循环，需要采用递归栈的方式来消除，即把递归调用的隐式栈转化为非递归的显示栈 （此部分内容较难，提示有能力的学生对该问题的处理方式） 。（8）哈夫曼树是树结构的应用，强调它是为解决数据压缩而提供的方法， 是最优编码。重点讲解构造哈夫曼树的构造及编码的方法。（9） 本部分内容的相关技术。强调采用二叉链表存储前提下，创建二叉树、二叉树的三种遍历方法、求二叉树的叶子结点、求二叉树的深度、交换二叉树的左右子树及哈夫曼树的构造的递归算法即可。（10） 教学策略。采用启发式教学，建议通过“人机对弈”案例的分析引入主题。由于本部分内容较为抽象，因而应充分借助动画演示进行教学。I图（10+4学时）I［教学内容］（1） 图的基本概念：图的基本概念；图的抽象数据类型（2） 图的存储结构：数组表示法；邻接表；十字链表；邻接多重表（3） 图的遍历：深度优先搜索；广度优先搜索（4） 图的连通性：无向图的连通分量（5） 图的生成树及最小生成树：生成树；克鲁斯卡尔算法；普里姆算法（6） 活动网络：用顶点表示活动的网络；用边表示活动的网络；拓扑排序；关键路径（7） 最短路径：从某个源点到其余各顶点的最短路径；每一对顶点之间的最短路径［重点］图的相关术语，图的存储结构（重点是邻接表）和遍历方法（深度优先遍历和广度优先遍历）及其效率分析，最小生成树的生成及其两种方法的对比， 有向无环图的应用和判断，拓扑排序的方法，最短路径，关键路径。［难点］图的遍历算法，图的典型算法（最小生成树、关键路径，最短路径）的实现。［教学要求］了解图的相关术语；掌握图的存储表示、图的两种遍历方法与求解连通性问题的方法、 求解关键路径和最短路径的方法；熟练掌握构造最小生成树的prim和kruskal方法、拓扑排序方法。［授课提示］图属于复杂的数据结构，与网络结构以及若干最优化问题都有联系。 教学中应注意强调以下几方面的问题：（1） 图的基本概念多而杂，建议在离散数学知识的基础上，以够用为原则进行概要介绍。图的存储方式分为顶点集的存储方式和边集的存储方式， 重点在于边集的存储方式，而边集又以邻接表方式为主。邻接表等同于矩阵的行链表组。（2） 为实现图的遍历必须设置访问标志数组，以防止走回路或未访问到某些结点。可用邻接矩阵和邻接表实现 DFS和BFS算法，DFS算法是以栈为基础的递归技术为支持，而BFS算法是以队列技术为支持。在讲授图的 DFS算法时，可以将二叉树的先序遍历算法作为其特例加以扩展。提示学生注意：树的根对应图的当前结点、 树的第一个子结点对应图的第一个邻接点、树的下一个子结点对应图的下一个邻接点。在讲授图的 BFS算法时，可以将二叉树的按层次遍历算法作为其特例加以扩展。（3） 关于遍历方法的应用（如求生成树，连通分量，判决有向图是否是无环图等）的教学只要讲几个应用的原理即可。 BFS的应用没有DFS的应用广泛，因而，对BFS的教学要求可以弱化一些。（4）关于求最小生成树的两个算法： Kruscal算法和Prim算法，前者是子树归并的思想，后者是采用子树延伸的思想，重点讲清楚两个算法的思想，如何确定和选择“当前最短边”的方法和原则。（5） 在讲解求最短路径（Dijkstra算法）和关键路径的方法时，关键是讲清楚算法的思想并提示学生注意掌握算法的本质。（6） 相关技术要求。由于本章内容的算法实现较难，因而，重点掌握图采用邻接矩阵存储下的DFS算法的实现，其它以掌握算法的思想为最低要求。“网络架构”、“五子棋”、（7） 教学策略。借助动画，采用启发式教学。结合实例，如：“网络架构”、“五子棋”、“农夫过河”等问题来引入图的概念及其图的典型应用。查找（8+4学时）I［教学内容］

静态查找：顺序查找；二分查找；分块查找动态查找：二叉排序树和平衡二叉树的查找； B树和B+树哈希表：哈希表的概念；哈希函数的构造方法；处理冲突的方法；哈希表的查找及其算法分析［重点］二分查找法及其效率分析，哈希函数的构造方法，用开放定址法解决冲突，探测序列的选择，二叉排序树的查找和插入方法， AVL树的原理及旋转方法，B/B+树的操作方法和应用场合。［难点］哈布表效率分析的方法，二叉排序树的效率分析和删除方法， AVL树的运算算法实现，B/B+树的实现方法。［教学要求］了解静态查找和动态查找及哈希表的含义、 B树和B+M;熟练掌握：顺序查找、二分查找和分块查找及其实现、二叉排序树的查找、插入和删除；掌握平衡二叉树、哈希表的构造方法及处理冲突的方法；了解哈希表的查找及其算法分析。［授课提示］二分查找仅适用于顺序存储的有序表。折半查找判定树为分析二分查找算法的时间复杂度提供了方便，需要强调折半查找判定树仅以表长有关， 而与表的内容无关；折半查找判定树的内容是元素的下标。讲解二叉排序树要强调它的中序有序性，围绕如何保持中序的有序性，研究查找、插入和删除算法，以及它们的时间复杂度，二叉排序树是 AVL树和B/B+树的基础，一定要讲透。AVL树是用旋转方法维持树的平衡，也就是将高度控制在 0(10ngn)范围之内，是理想的查找结构。关键在于何种情况下需要进行旋转和怎样旋转， 要多举例说明各种旋转方式，便于学生理解。哈希函数的设计,使学生能够根据数据B/B+树是动态的索引结构，是大型平衡树，学生只要学会画图表示插入和删除操作原理即可。哈希函数的设计,使学生能够根据数据哈希表是一种高效的查找表。保证查找效率的关键因素有三个：处理冲突的方法及哈希表的装填因子。 简要介绍常用哈希函数的特点，的特征选用合适的哈希函数。开放定址法则是当在解决冲突的两种方法中，链接法将相互冲突的元素构成一个链表，开放定址法则是当发生冲突时，使用探测的方式在哈希表中寻找下一个合适的位置。 讲授中，要注意比较各种探测方法的特点，强调这些相互冲突的元素之间实际上也构成了一个“隐式”的冲突链表。当冲突发生严重时，查找效率会严重退化。难点的处理技术。学生不易掌握衡旋转、RR型平衡旋转、旋转时，可以伸出左手(是顺时针旋转方向；讲解a的函数，而与特查找元素的数目 难点的处理技术。学生不易掌握衡旋转、RR型平衡旋转、旋转时，可以伸出左手(是顺时针旋转方向；讲解a的函数，而与特查找元素的数目 n无关。无论元a，使哈希表的平均长度较小。等概率情况下，查找成功平1/n,其中n为表中置入元素个数；查找不成功平均查找1/r，其中r为哈希函数取值个数。平衡二叉树的生成过程中平衡调整规律( LL型平LR型平衡旋转、RL型平衡旋转)。在讲解 L旋转，即顺时针方向Left)，慢慢形成拳头，而形成拳头的过程中手指的弯曲方向正好头，此时手指的弯曲方向正好是逆时针旋转方向。整规律简化为直观形象的“左右手原则”。教学策略。结合实例，借助图形来描绘各种查找方法的具体执行过程，从而总结R旋转，即逆时针方向旋转时，伸出右手(Right)，慢慢形成拳因此将原来抽象的顺时针、逆时针旋转调头，此时手指的弯曲方向正好是逆时针旋转方向。整规律简化为直观形象的“左右手原则”。教学策略。结合实例，借助图形来描绘各种查找方法的具体执行过程，从而总结归纳出其算法效率的优劣。［教学内容］基本概念插入排序:［教学内容］基本概念插入排序:交换排序:选择排序:归并排序:基数排序:直接插入排序；折半插入排序；链表插入排序；希尔排序起泡排序；快速排序直接选择排序；堆排序归并多关键码排序；链式基数排序［重点］排序方法的特性，各种排序算法的性能对比和适用场合； 基本插入原理，希尔排序算法；冒泡排序算法的特征，快速排序的基本原理、划分方法；堆排序算法、归并排序算法、基数排序算法的原理(分组和收集)，时间、空间复杂度及稳定性分析。，快速排序和堆［难点］各种排序算法的性能对比和适用场合；希尔排序算法增量序列选择；排序算法效率分析；典型排序算法的综合比较。，快速排序和堆［教学要求］了解排序的基本概念和性能分析方法、基数排序方法及其性能分析掌握插入排序、交换排序、选择排序、归并排序等排序的方法及其性能分析方法熟练掌握希尔排序、快速排序、堆排序的方法［授课提示］对于内部排序，要特别关注各种排序算法的核心思想，时间和空间度以及“稳定性”教学中，注意以下几方面：简单插入排序、冒泡排序和得意选择排序都属于“得意直观”的排序方法。这三个算法共同之处是：在排序过程中，将数据划分为两段：无序段和有序段。反复按照某种规则在无序段中找出一个元素移入有序段， 当无序段的变为零，就完成了排序工作。不同之处于：简单插入排序是将无序段的首元素， 移到有序段中；冒泡排序是通过相邻元素比较和交换，延长有序段的长度；而简单选择排序，是在整个无序段中找最小(或最大)元素，将其接到有序段上。强调三者的共性和个性，才能避免学生混淆这三个算法的主体思想。希尔排序算法中，注意讲清楚增量序列、子序列、子序列有序、子序列的定位方式，以及如何对子序列按插入法进行排序。快速排序算法属于递归的分治法。重点讲清楚如何将一个划分段划分成两段(即一次划分)，以及划分元素(即枢轴)的选取方法和对排序效率的重要影响，并通过分析算法的时间复杂度进一步理解为什么数据排列越随机，算法的效率越高。归并算法也属于递归的分治法。重点讲清楚两路归并的原理，递归终止的条件及排序效率。基数排序是对字符串(或数字串)进行排序的，关键一是要讲清楚“基数”的概念，基数与字符串(或数字串)有序性之间的关系，二是为什么选择链式队结构进行数据的分组和收集，三是分析算法的时间复杂度。对比掌握各种排序算法的时间复杂度、空间复杂度和稳定性，并能根据不同的情况选用最适合的排序算法。教学策略。采用讨论法教学。结合实例，采用对比的方法，借助图示描绘各类排序算法的执行过程，分析归纳各种排序算法的时间效率、 空间效率和稳定性，从而引导学生总结在不同的情形下该如何来选择相应的排序算法。五、教学内容的组织方式学生在学习数据结构时，普遍认为课本内容的理解较为困难， 算法设计无从下手，上机调试程序更是困难重重。究其原因主要有四：①数据结构课程的理论知识较为抽象，教学中难于直观表达；②先修课程不尽人意。如：数学基础薄弱，高级语言程序设计掌握不足；③实践效率低，动手能力不强；④整体学风差，学习习惯不良。 在组织教学时，应结合学生的现状制定恰当的教学方案。如：适当降低要求；补充高级语言中的函数、指针、结构体等内容的讲授；选择学生感兴趣的问题入手；选择直观的教学手段；改革实践课等。在教学内容的组织上，应依据“以学生能力形成为核心” 的教育理念，根据《数据结构》教学大纲及指定教材的要求，融入数据结构和算法的前沿新技术，保证教学内容的先进性、科学性；合理地组织知识结构体系，提炼出该课程、每章、每节的知识结构，构建一个整体的层次框架，注重内容的衔接、联系与继承性，逐步展开各层次的知识点的教学 ；贯穿数据结构的命脉是存储结构和算法描述， 因而，应从数据结构的逻辑结构、存储结构和数据的运算三个方面去组织各章节的教学内容， 教学内容要重点突出，简洁明了而不求面面俱到。详情见下表：知识领域一级知识点二级知识点教学内容的具体组织方式数据结构定义数据单值类型(整形、、布尔型、字符型、指针类型，复合类型)在组织本章教学时，不急于介绍理论，而是强调应用。(1)通过介绍数据结构在实际生活、工作中的应用来激发学生的学习兴趣。如：通过图书检索、人机对弈，叉路口交通灯、语言编译、打印排队、银行柜台业务等典型问题的引入，让学生了解学习《数据结构》的重要性；( 2)从以上例子中分析、归纳出数据的逻辑结构种类；( 3)由相关运算的实现方式，依其所采用的存储结构的不冋而不同，引入数据的物理结构。按照这样的一条主线，就将数据结构所涵盖的内容归纳总结出来了。数据结构逻辑结构，存储结构，基本运算抽象数据类型信息封装，数学模型算法与问题求解算法概念可行性，有效性，确定性，有穷性通过对同一问题采用不同的算法实现的效率不同，引入时间复杂度和空间复杂度的概念；通过对渐进符号0含义的介绍引入时间复杂度的表示方法；通过大量的经典算法的语句频度的分析求解引入时间复杂度的求解方法。算法分析语句频度，正确性，时间和空间复杂度的大0表示法问题求解问题抽象，数据和数据结构抽象，运算抽象，算法设计线性结构线性表前驱，后继，长度，存储方式；数组，单链表，双链表，循环链表；基本运算；查找，插入，删除通过学生的排队问题引入线性表的逻辑结构及相关术语；结合案例(如：约瑟夫问题)的分析引入线性表的基本运算采用顺序存储和链式存储方式下不同的实现方法(用动画演示讲解)及算法描述；比较、归纳各自的缺点，从而引导学生分析各自的适用场合。栈LIFO，栈顶，栈底；顺序栈，表达式求值由线性表引入栈的概念；通过现实生活中的例子讲解栈的原理及栈的用途；通过对比的方法讲授二者的区别与联系，从链式栈而得出栈的运算规则；（3） 结合案例（如火车调度）重点讲授顺序栈下基本运算的实现方法及算法描述。（4） 通过身边的案子引入栈的应用；（5） 采用讨论方式，对比链栈与顺序栈的区别。嵌套调用，递归程序转换为非递归程序队列FIFO,队头，队尾；顺序队，循环队；（1） 通过银行业务流程、学生排队买饭的例子引入队列的概念及术语；（2） 对比队列与线性表、栈的区别与联系；（3） 结合案例分析循环队列的基本操作的实现方式及算法描述。强调队头、尾指针的变化方式。链式队，队的应用字符串存储，运算；简单模式匹配算法（1） 由实例引入串的概念；（2） 通过对比的方法，讲授串与其他线性结构的区别；（3） 结合实例讲授串的基本操作及其顺序存储下常用操作的实现；（4） 通过动画演示，启发学生讨论串的简单模式匹配与KMP算法原理及根本区别。KMP算法广义表原子结构，结点，表头，表尾，深度，长度，存储方式（1） 由实例引入广义表的概念；（2） 通过对比总结线性表与广义表的区别与联系；（3） 结合实例，讲授求解表头、表尾、表的深度、广度的方法；画图讲授广义表的存储方式。矩阵数组的表示和实现特殊矩阵和稀疏矩阵的压缩存储，稀疏矩阵的转置运算（1） 由高级语言中的数组引入数组概念，分析对比二者的不同；（2） 画图讲授二维数组的按行/列存储的特点，推导不冋存储方式下求解兀素地址的公式；进一步推广到多维数据中兀素存储地址的求解公式；（2） 由矩阵的存储特点引入特殊矩阵的压缩存储方式，并结合图形推导求解特殊矩阵的元素存储地址公式；（3） 画图分析，组织学生讨论稀疏矩阵采用压缩存储实现矩阵的转置求解方法。二叉树概念定义和术语，满二叉树和完全二叉树，五条性质（1） 由自然界中的树引入树的概念及其相关术语；（2） 分析由于树的复杂性及难于存储的特点引入二叉树的内容（因为它是最简单、有规律的树） ；（3） 画图分析引入二叉树的定义、特点及种类；（4） 结合图形分析二叉树的五条性质及证明过程；（5） 由二叉树的特点引入其两种存储方法，并通过对比归纳各自的存储特点；（6） 结合案例分析二叉树的遍历方法及二叉树基本操作的实现及算法描述；（7） 通过动画演示，引导学生总结二叉树与树和森林的转换方法；二叉树遍历先序遍历，中序遍历，后序遍历按层次遍历二叉树存储顺序存储，二叉链表存储二叉树应用哈夫曼树及哈夫曼编码判定树树型结构树和森林树的存储图的概念图的存储

方法图的遍历图型

结构DAG最小生成

树最短路径基本概念表结构的

查找查找

与索

引哈希表二叉排序

树

平衡树B/B+树基本概念内部

排序插入排序交换排序选择排序树和森林的定义；树、森林与二叉树的转换双亲表示法，孩子表示法，孩子兄弟表示法定义，术语，种类,生成树邻接矩阵，邻接表广度优先遍历，深度优先遍历拓扑排序，关键路径Prim算法，Kruskal算法Dijkstra算法，Floyd算法查找长度，平均查找长度顺序查找，二分查找分块查找，索引查找基本概念，哈希函数，冲突处理，哈希表的构造，查找算法插入，删除AVL树基本概念，插入/删除操作，读盘和写盘次数分析，索引效率分析正序，逆序，稳定性，排序方法种类，衡量排序算法的指标直接插入排序,Shell排序冒泡排序快速排序直接选择排序通过树和二叉树间的内在联系，弓I入树和森林的遍历方式；结合案例，分析哈夫曼树的特点、哈夫曼树的构造和哈夫曼编码的设计方法。通过实例(如网络的构建，水管道的铺设)引入图的概念，结合图示讲授图的相关术语；结合实例，讲授图的邻接矩阵和邻接表的表示方法，对比个种存储特点，总结各自的适用场合;通过与树的遍历方法的对比，讲授图的两种遍历方法的原理；结合实例，介绍拓扑排序，求关键路径、最短路径的方法；采用对比的方法，讲授求解最小生成树的两种算法的特点及原理。由许多现实生活中的例子，引入查找的概念;通过对线性查找的不足之处的分析引入折半查找和分块查找的内容；由折半查找的特点引入折半查找的判定树，从而得出其时间效率的求解方法；通过实例，讲授哈希表的概念、哈希函数的构建及解决冲突的方法；结合案例，采用不同的方法构造哈希表的不同结果，分析归纳各自的优缺点，从而引导学生能够根据实际选择恰当的构造方法。通过对二叉排序树的特点的分析引入平衡树的内容；结合前沿技术引入B/B+树的概念。由现实生活中的查找效率问题引入排序的相关概念；从而引入排序的种类；结合实例，采用对比的方法，分组介绍相关的简单排序和先进排序的方法，通过从时间效率、空间效率及稳定性方法，总结各自的优缺点及适用场合。堆排序归并排序二路归并基数排序顺序基数排序，链式基数排序排序算法分析查找和移动次数，时间复杂度和空间复杂度，排序问题的下界六、课程实验1、 实验地位：《数据结构》课程的特点决定了必须通过加强实践环节的教学来检验学生所学知识， 加强学生解决实际问题能力的培养。通过对以数据结构与算法设计为核心的课题的设计与实现过程的训练，培养学生综合运用所学数据结构以及程序设计等课程的知识、 能力与方法，系统学习和掌握问题建模、数据结构设计、算法设计与实现、测试等各环节的方法和能力。2、 实验提示：《数据结构》中所涉及的知识点包括线性表、栈、队列、字符串、数组、广义表、二叉树、图等数据结构的运算、存储结构和算法实现，以及最常用的排序和查找等算法。从能力培养的角度，课程重点在以下几方面：对实际问题的建模，由此涉及与数据结构各个方面的联系： 逻辑结构、存储结构和运算的实现与性能分析。存储结构的设计：掌握数据结构的设计技术， 理解存储结构对运算性能的影响。 其中的难点是动态存储结构的设计； 树结构、图的存储结构的设计；根据具体问题的要求设计出合理的存储结构。算法设计技术与能力：对给定的问题能设计并实现满足要求和约束的、 合理的求解算法。线性结构、树形结构和图结构的算法设计各自具有明显的特征，因此，基于各种数据结构的基本运算设计相应问题的求解算法。算法设计中较多地采用到递归技术。算法分析：不仅能分析出常见算法的时间和空间复杂度， 还能掌握验证算法性能的实验方法和实验设计、分析等。由于本课程是实践性较强的一门课， 培养学生的实践能力是教学的首要目的。 数据结构理论知识的传授是为应用服务的。 因此，在授课的同时，如何引导学生利用上机实验来加强实践也是教学中的一个重要问题。 在实践教学设计中，教师应注重实验选题，包括题目的典型性、趣味性、实用性及难易程度(如必选题和可选题)，满足不同层次学生的需要，充分调动学生的学习积极性，将实践训练落到实处。3、 实验安排：实践教学环节按照“验证性实验7设计性实验7课程设计”三个层次展开：验证性实验。在教学过程中穿插对应的实验，将书本上的典型算法或是由教师自己设计的具有代表性的应用程序，提供给学生上机验证，让学生从感性认识上升到理性认识，巩固课堂教学的内容，加深对算法的理解。设计性实验。教师根据相关内容提出与学生息息相关的问题，让学生根据所学过的知识，充分发挥自身的主观能动性， 自行设计算法上机完成。 让学生掌握对所学理论知识的灵活应用。课程设计。课程设计中要求学生综合运用所学知识，上机解决一些与实际应用结合紧密的、规模稍大的问题，通过问题分析、系统设计、程序编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。同时，训练学生具备相互交流及团队合作的能力。鉴于本课程的教学内容和要求，预计安排4~7个验证/设计性实验（分别侧重于顺序表、链表、栈、二叉树、树、图、查找、排序）及3个课程设计。其中课程设计分别穿插在线性结构内容、非线性结构内容、查找和排序内容之后进行，培养学生对相关内容的综合能力的训练。如果因课时方面或学生基础的原因，可根据需要选择其中的部分实验内容。4、实验要求：实验前，要求学生预习，对给定的问题能利用所学知识进行数据结构的设计及算法设计；实验时，要求学生能根据实验的要求，将事先设计的算法采用学生熟悉的高级程序设计语言上机调试实现。为了能对其中的算法和相关程序的有关性能进行必要的测试， 需要事先准备好必要的数据来运行和测试程序， 并且数据的类型和规模应当达到一定的要求， 以便能更多地检测到可能存在的问题。（1） 验证性/设计性实验后要及时总结，写出实验报告。实验报告的内容需包括：实验名称，实验目的，实验要求，实验心得，并附所打印的问题解答程序清单及所输入的数据及相应的运行结果。实验报告是学生表达问题求解的基本能力， 并且也是培养良好治学态度的必要环境。（2）课程设计完成后，要求写出课程设计报告。 课程设计报告应当包括：课题描述：描述要求编程解决的问题；基本要求：给出程序要达到的具体的要求；测试数据：设计测试数据，或具体给出测试数据，求测试数据能全面地测试所设计程序的功能；算法思想：描述解决相应问题算法的设计思想；模块划分：描述所设计程序的各个模块（即函数）功能；数据结构：给出所使用的基本抽象数据类型，所定义的具体问题的数据类型，及新定义的抽象数据类型；源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义测试情况：给出程序的测试情况，并分析运行结果。5、实验考核方式及成绩评定实验考核主要是注重学生的实验过程的考核。实验成绩由以下几个方面构成：出勤（占10%；实验预习（占10%）；实验过程的进展和结果（占 40%；实验报告的制作（占30%；课程设计报告的制作（占10%。6、实验内容:实验一［实验名称］线性表及其应用［实验目的］掌握用学生熟悉的高级语言调试程序的基本方法。掌握线性表在顺序存储结构和链式存储结构上的基本运算，如插入、删除等。［实验内容］线性表在顺序存储结构上的插入元素，删除元素运算线性表在链式存储结构上的建链表，插入结点，删除结点运算［能力考核要求］能按要求完成实验内容并调试通过。初步掌握运用链式结构的编程和调试程序的能力,并能够对问题的需求分析，选择恰当的存储结构。实验二［实验名称］栈和队列及其应用［实验目的］掌握栈和队列的概念及其两种数据结构的特点,构；掌握在顺序栈上实现栈的基本运算，列的基本运算，注意队满和队空的描述方法［实验内容］1.顺序栈的实现和运算2.循环队列的实现和运算［能力考核要求］能按要求完成实验内容并调试通过。换问题、火车调度问题、括号匹配问题等。懂得在什么样的问题中应用利用哪种结注意栈满及栈空的条件及它们的描述方法； 掌握队掌握栈的原理，能够利用顺序栈来实现诸如数制转实验三［实验名称］串及其应用［实验目的］掌握串的运算（赋值，比较，联结，插入子串，模式匹配［实验内容］串的基本操作［能力考核要求］能完成实验内容并调试通过，掌握串的常见基本操作的实现。等）实验四［实验名称］数组和广义表［实验目的］掌握数组的存储表示和实现技术［实验内容］数据的存储及元素的访问方式［能力考核要求］能按要求完成实验内容并调试通过。理解数据的存储方式，掌握数组在采用行（或列）存储结构中的地址计算方法，领会稀疏矩阵运算采用的处理方法。实验五一一课程设计［问题描述］设停车场内有一个可停放N辆汽车的狭长通道，且只有一个大门可供汽车出入。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆汽车停放在车场的最北端） ，若车场内已停满N辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入； 当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路， 等该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编写按上述要求进行管理的模拟程序。［实验要求］以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为： 若是车辆至达，则输出汽车在停车场内或便道上的停车位置； 若是车辆离去，则输出汽车在停车场内仪的时间和应交纳的费用（在便道上仪的时间不收费） 。栈以顺序结构实现，队列以链表结构实现。［实验提示］需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。 栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。［能力考核］能够利用本单元的知识，解决综合性的实际问题实验六［实验名称］树及其应用［实验目的］进一步掌握树的结构及非线性特点，递归特点和动态性。进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法；熟练掌握二叉树的基本操作［实验内容］二叉树的创建、结点的遍历和基本运算哈夫曼树的实现［能力考核要求］能按要求完成实验内容并调试通过。 掌握用二叉链表描述、访问二叉树的方法，并能具备二叉树的创建，求解二叉树的高度、叶子结点数及二叉树左、右子树的交换等问题的实现能力，能够用二叉树结构来解决简单的具体问题。实验七［实验名称］图及其应用［实验目的］进一步掌握图的结构及非线性特点，递归特点和动态性。2•进一步巩固图的两种存储结构和二种遍历方法、最小生成树的两种求解算法。［实验内容］图的遍历最小生成树3•最短路径每一对顶点之间的最短路径拓扑排序［能力考核要求］能按要求完成实验内容并调试通过。 掌握图采用邻接矩阵存储的深度优先遍历的算法实现。实验八一一课程设计

顶点表示城市，边上的［问题描述］如果以无向网表示n个城市之间通信网络的建设计划，权表示该线路的造价，设计一个方案，使这个通信网的总造价最低。顶点表示城市，边上的10条边）表示，若两个城要求在屏幕上显示得到的并显示得到的最小生成树的代价。 最小生成树中包［实验要求］城市间的距离网采用邻接矩阵（要求至少 610条边）表示，若两个城要求在屏幕上显示得到的并显示得到的最小生成树的代价。 最小生成树中包市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。最小生成树中包括了哪些城市间的道路，括的边及其权值，并显示得到的最小生成树的代价。［实验提示］这是一个求连通的带权无向图的最小代价生成树的问题。建立图的邻接矩阵,然后以prime算法来求最小生成树［能力考核］能利用本单元的知识，解决综合性的问题实验九［实验名称］查找与排序［实验目的］掌握常用查找（顺序、二分法、查找树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。巩固在散列查找时解决冲突的方法及特点。掌握基本排序（直接插入，希尔，冒泡，简单选择等）方法及适用场合，并能在解决实际问题时灵活应用。［实验内容］线性表查找查找树的实现各种排序方法的实现［能力考核要求］能按要求完成实验内容并调试通过。掌握顺序查找和折半查找算法的实现，掌握简单选择排序及冒泡排序算法的实现，并能够根据实际情况选取恰当的查找（排序）算法来解决问题。实验十一一课程设计［问题描述］针对某一种行业的库房的