《数据结构B》课程教学大纲（本科）.docx

数据结构B(Data Structures B)课程代码：06410036学分：3.5学时：64 （其中：课堂教学学时：48实验学时： 上机学时：16课程实践学时：） 先修课程：程序设计基础A、面向对象程序设计A、离散数学适用专业：信息安全教材：数据结构一C+实现，缪淮扣，科学出版社，2014年第二版一、课程性质与课程目标（-）课程性质数据结构B在计算机科学中是一门重要的专业基础课，它不仅是一般程序设计的基础, 而且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基 础。本课程学习和讨论在不同应用需求之下各种数据的组织方式和处理方法，包括数据的逻辑 结构、存储结构以及相关结构之下的各种操作。通过本课程的学习，旨在使学生掌握计算机处 理中数据特征的分析、组织、存储和操作的典型方法，具备根据实际应用需求选择合适的数据 结构和设计相应算法的能力。（二）课程目标课程目标1:理解与掌握数据结构的基本概念、算法的描述方法和复杂度分析方法。课程目标2：理解各种典型数据结构的逻辑特性，掌握不同数据结构的存储表示与操作方法。 课程目标3：理解查找与排序的基本概念，掌握各种查找、排序方法及其性能分析方法。课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据。课程目标5：能够为解决实际应用问题进行算法分析与设计。课程目标6：能够运用程序开发语言实现解决实际应用问题的程序。注：工程类专业通识课程的课程目标应覆盖相应的工程教育认证毕业要求通用标准；（三）课程目标与专业毕业要求指标点的对应关系实验2：栈和队列1.实验目标（1）理解与掌握栈和队列的表示与操作方法。（2）通过解决栈和队列的应用问题，训练学生解决实际编程问题的分析、设计等思维能力。2.实验要求（1）利用两个顺序栈共享一个存储空间的设计，完成入栈、出栈和判断栈空的函数。（2）设计利用两个栈si, s2模拟一个队列，实现入队、出队和判队列空的函数。（3）在循环队列中，以front和length分别表示循环队列中的队头位置和队列中所含元 素的个数。完成循环队列判断队空、判断队满、入队和出队函数。（4）二项式（a+bF展开后，其系数构成杨辉三角形，利用队列实现打印杨辉三角形的前n 行的算法。实验3：树和森林1.实验目标（1）理解与掌握二叉树与树的表示与操作方法。（2）通过解决二叉树与树的应用问题，训练学生解决实际编程问题的分析、设计等思维能 力。2.实验要求（1）二叉树采用二叉链表存储，编写计算二叉树最大宽度的算法（二叉树的最大宽度是指 二叉树所有层中结点个数的最大值）。（2）树以孩子兄弟链表为存储结构，请设计算法求树的深度。（3）以二叉链表作存储结构，编写求二叉树中叶子结点数目的递归函数。（4）以孩子一兄弟表示法作为树的存储结构，编程求树的度。实验4：图.实验目标（1）理解与掌握图的表示与操作方法。（2）通过解决图的应用问题，训练学生解决实际编程问题的分析、设计等思维能力。1 .实验要求（1）基于图的深度优先搜索策略写一个算法，判别以邻接表方式存储的有向图中是否存在 由顶点Vi到顶点Vj的路径（i!=j）。（2）基于图的广度优先搜索策略写一个算法，判别以邻接表方式存储的有向图中是否存在 由顶点Vi到顶点Vj的路径（i!=j）。（3）以邻接表为存储结构实现从源点到其余各顶点的最短路径的Dijkstra算法。实验5：查找.实验目标（1）理解与掌握二叉排序树的定义与操作。（2）通过解决二叉排序树的应用问题，训练学生解决实际编程问题的分析、设计等思维能 力。1 .实验要求采用二叉链表实现一个二叉排序树的应用，完成如下功能，要求实现一个简单的字符界面, 根据用户选择完成相应处理，并输出处理结果。（1）建立一棵二叉排序树：对从键盘输入的顺序任意的若干个正整数建立一颗二叉排序树，以T作为结束，例如：输入39 11 68 46 75 23 71 8 86 34 -1（2）中序遍历，输出遍历结果。（3）查找：输入一个关键字，进行查找。（4）插入：输入一个关键字，进行插入。（5）删除：输入一个关键字，进行删除。（6）编写递归算法，从大到小输出二叉排序树中所有关键字不小于x的数据元素。四、学时分配及教学方法注：1.课程实践学时按相关专业培养计划列入表格;章教学形式及学时分配主要教学方法支撑的课程目标课堂 教学实 验上机课程 实践小 计第一章33讲授、研究1第三章7411讲授、演示、研究2、 4、 5、 6第四章426讲授、演示、研究2、 4、 5、 6第五章44讲授、演示2、 4、 5、 6第六章12416讲授、演示、研究2、 4、 5、 6第七章8412讲授、演示、研究2、 4、 5、 6第八章527讲授、演示、研究3、 4、 5、 6第九章55讲授、演示、研究3、 4、 5、 6合计4816642 .主要教学方法包括讲授法、讨论法、演示法、研究型教学方法（基于问题、项目、案例 等教学方法）等。五、课程考核考核形式考核要求考核权重备注平时作业作业次数不少于5次，主要考核学 生对课堂讲授的知识点的复习、理 解和掌握程度10%取作业平均值实验五次实验，主要考核学生的应用、 设计与开发能力20%取实验平均值，评 分细则见附录1期末考试闭卷70%注：1,分学期设置和考核的课程应按学期分别填写上表。3 .考核形式主要包括课堂表现、平时作业、阶段测试、期中考试、期末考试、大作业、小 论文、项目设计和作品等。4 .考核要求包括作业次数、考试方式（开卷、闭卷）、项目设计要求等。5 .考核权重指该考核方式或途径在总成绩中所占比重。六' 参考书目及学习资料.数据结构（C语言版），严蔚敏，清华大学出版社，1997年第1版。1 .数据结构（用面向对象方法与C+语言描述），殷人昆，清华大学出版社，2007年第2版。2 .数据结构、算法与应用:C+语言描述，美Sartaj. Sahni著，王立柱 等译，机械工 业出版社，2015年第2版。七、大纲说明.本课程采用多媒体教学。1 .根据各章节的具体情况，课后可布置适当的书面作业或思考题，以加深学生对所学内容 的理解和掌握。2 .本课程有16个学时的实验，具体实验内容任课教师可以根据实际教学情况适当安排。2016年9月附录1实验报告内容与评分细则实验报告考查内容与评分比重参见下表:评分项 编号实验评价内容所占 比重要求对毕业要求指 标点支撑1问题分析和设计40%能够说清问题分析与设计3-12编程实现60%能够编程实现5-2实验报告评分细则（按100分计算）项目100-9080-8970-7960-6960以下问题分析与 实现40%问题分析正问题分析正问题分析正问题分析基本问题分析存在确，解决步骤确，解决步骤确，解决步骤正确，解决步错误，解决步正确基本正确不完整骤不完整骤不完整编程实现60%程序正确并清 晰易读程序正确程序有少许错 误程序有一定量 的错误程序有较多错 误本课程支撑专业培养计划中毕业要求指标点1-2. 3-1和5-2o.毕业要求1-2：掌握计算机基础知识。1 .毕业要求3-1：掌握对计算机系统进行分析和总体设计的方法与过程。2 .毕业要求5-2：针对信息安全复杂工程问题，具备对所需工具进行分析及二次开发的能 力。程目标毕业要输标&课程目标1课程目标2课程目标3课程目标4课程目标5课程目标6毕业要求1-2毕业要求3-1毕业要求5-2注：课程目标与毕业要求指标点对接的单元格中可输入也可标注“H、M、L-o二、课程内容与教学要求第一章绪论（一）课程内容.数据结构的基本概念。（讲授+案例）1 .算法性能与复杂度。（讲授+案例）（二）教学要求本章支持课程目标1:理解与掌握数据结构的基本概念、算法的描述方法和复杂度分析方 法。1 .理解与掌握数据结构的基本概念。2 .掌握算法复杂度的分析方法。3 . 了解算法的描述方法。（三）重点与难点.重点（1）数据、数据元素和数据项的概念与区别。（2）数据的逻辑结构与存储结构的联系与区别。（3）算法复杂度的分析方法。1 .难点（1）数据的逻辑结构与存储结构的联系与区别。（2）算法的时间复杂度分析方法。第三章线性表（一）课程内容1 .线性表的定义。（讲授+案例）2 .线性表的顺序表示。（讲授+演示+案例）3 .线性表的链式表示。（讲授+演示+案例）（二）教学要求本章支持课程目标2：理解各种典型数据结构的逻辑特性，掌握不同数据结构的存储表示 与操作方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标 5：能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现 解决实际应用问题的程序。1 .掌握线性表的基本概念和类型定义。2 .掌握顺序表和单链表上的基本操作方法及算法描述。3 .掌握循环链表和双向链表的定义和插入、删除等操作方法。（三）重点与难点1 .重点顺序表和链式表（单链表、双向链表）的基本操作。2 .难点链式表（单链表、双向链表）的基本操作。第四章栈、队列和递归（一）课程内容1 .栈的定义与表示。（讲授+演示+案例）2 .队列的定义与表示。（讲授+演示+案例）3 .递归。（讲授+自学）（二）教学要求本章支持课程目标2：理解各种典型数据结构的逻辑特性，掌握不同数据结构的存储表示 与操作方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标 5：能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现 解决实际应用问题的程序。1 .掌握栈和队列的定义。2 .掌握栈和队列的顺序存储表示与链式存储表示。3 .掌握表达式求值等方法。4 . 了解递归的概念。（三）重点与难点1 .重点栈和队列的顺序存储表示、链式存储表示及基本操作的实现。2,难点（1）顺序栈的溢出判断。（2）循环队列的队空与队满的判断。（3）递归。第五章串、数组和广义表（一）课程内容2 .字符串。（讲授+演示+自学）3 .数组。（讲授+自学）4 .稀疏矩阵。（讲授+演示）5 .广义表。（讲授+演示+自学）（二）教学要求本章支持课程目标2：理解各种典型数据结构的逻辑特性，掌握不同数据结构的存储表示 与操作方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标 5：能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现 解决实际应用问题的程序。1 . 了解字符串的基本概念。2 .掌握数组的定义与存储结构，具备存储地址换算的能力。3 .掌握稀疏矩阵的定义和压缩存储表示。4 .掌握稀疏矩阵的转置方法并了解其算法。5 .掌握广义表的概念和操作。（三）重点与难点1 .重点（1）数组的定义和存储结构。（2）稀疏矩阵的压缩存储。2 .难点压缩存储表示的稀疏矩阵运算的实现。第六章树和森林（-）课程内容1 .树的概念。（讲授+案例）2 .二叉树的定义、性质、基本操作和存储结构。（讲授+演示+案例）3 .二叉树的遍历。（讲授+演示+案例）4 .线索二叉树。（讲授+演示+案例）5 .二叉树的应用。（讲授+演示+案例）6 .树和森林的实现。（讲授+演示+案例）（二）教学要求本章支持课程目标2：理解各种典型数据结构的逻辑特性，掌握不同数据结构的存储表示 与操作方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标 5：能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现 解决实际应用问题的程序。1 .掌握树的定义、术语与基本操作。2 .理解与掌握二叉树的定义、性质与存储结构。3 .掌握二叉树的各种遍历方法，能够解决基于遍历方法的二叉树运算。4 .掌握线索二叉树的定义和算法实现，能够线索化二叉树工5 .掌握哈夫曼树及其应用。6 .掌握树、森林与二叉树的转换方法，树和森林的遍历方法。（三）重点与难点1 .重点（1）二叉树的定义、性质与存储结构。（2）二叉树的遍历与线索化方法。（3）哈夫曼树及其应用。（4）树、森林与二叉树的转换方法。（5）树和森林的遍历方法。2 .难点（1）二叉树的复杂运算。（2）线索二叉树的算法实现。第七章图（-）课程内容1 .图的概念、术语与基本操作。（讲授+演示+案例）2 .图的存储结构。（讲授+演示+案例）3 .图的遍历与连通性。（讲授+演示+案例）4 .图的最小生成树。（讲授+演示+自学）5 .最短路径。（讲授+演示+自学）6 .活动网络。（讲授+演示+自学）（二）教学要求本章支持课程目标2：理解各种典型数据结构的逻辑特性，掌握不同数据结构的存储表示 与操作方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标 5：能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现 解决实际应用问题的程序。1 .理解与掌握图的定义和术语。2 .掌握图的存储结构表示方法。3 .掌握图的深度和广度优先搜索方法，能够解决基于遍历方法的图的运算。4 .掌握构造最小生成树的普里姆算法和克鲁斯卡尔算法。5 .掌握求解图的最短路径及其长度的方法，能够解决构造单源点最短路径问题。6 .掌握拓扑排序的方法，能够构造拓扑有序序列。（三）重点与难点7 .重点（1）图的存储结构。（2）图的遍历方法及其实现。（3）图的最小生成树、最短路径问题的求解方法。（4）有向无环图的拓扑有序序列的构造方法。8 .难点（1）图的遍历方法与基于遍历方法的图的运算。（2）求解图的最短路径的算法思想及其算法实现。第八章查找（-）课程内容1 .查找的基本概念。（讲授）2 .顺序表与索引顺序表查找。（讲授+演示+案例）3 .二叉排序树。（讲授+演示+案例）4 .散列表。（讲授+演示+案例）（二）教学要求本章支持课程目标3：理解查找与排序的基本概念，掌握各种查找、排序方法及其性能分 析方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标5： 能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现解决 实际应用问题的程序。1 .理解查找的基本思想与相关概念，掌握平均查找长度的定义和计算方法。2 .掌握顺序表和有序表的查找方法，能够分析顺序表、有序表和索引顺序表的查找性能。3 .掌握二叉排序树的定义、查找、插入和删除方法，能够分析查找性能。4 .掌握散列表的构造方法，并具有对散列表进行查找和分析的能力。（三）重点与难点1 .重点（1）顺序表的查找方法。（2）二叉排序树的查找、插入和删除方法，以及查找性能的分析。（3）散列表的构造、查找方法，以及查找性能分析。2 .难点二叉排序树的删除方法。第九章排序（一）课程内容1 .基本概念。（讲授）2 .交换排序。（讲授+演示+案例）3 .插入排序。（讲授+演示+案例）4 .选择排序。（讲授+演示+案例）5 .归并排序。（讲授+演示+案例）6 .基数排序。（讲授+演示+案例）7 .各种排序方法的比较讨论。（讲授+自学）（二）教学要求本章支持课程目标3：理解查找与排序的基本概念，掌握各种查找、排序方法及其性能分 析方法；课程目标4：能够分析实际应用问题的需求，合理地组织与存储数据；课程目标5： 能够为解决实际应用问题进行算法分析与设计；课程目标6：能够运用程序开发语言实现解决 实际应用问题的程序。1 .理解排序的基本思想和基本概念。2 .理解并掌握各种排序方法的基本思想、步骤、算法，并具有时空效率分析的能力。3 .了解各种典型的内部排序算法的特点和适用范围。（三）重点与难点1 .重点各种排序方法及时空效率分析。2 .难点快速排序、堆排序及其算法实现。三、本课程开设的实验项目编号实验项目名称学时类型要求支撑的课程目标1线性表4设计性必做2、 4、 5、 62栈和队列2设计性必做2、 4、 5、 63树和森林4设计性必做2、 4、 5、 64图4设计性必做2、 4、 5、 65查找2设计性必做3、 4、 5、 6注：1. “类型”填验证性、综合性、设计性等；3 . “要求”填必做、选做。实验L线性表.实验目标(1)理解与掌握线性表的顺序存储和链式存储的表示与操作方法。(2)通过解决线性表应用的相关问题，训练学生解决实际编程问题的分析、设计等思维能 力。1 .实验要求(1)在顺序表中设计函数实现以下操作：(a)从顺序表中删除具有最小值的元素(假设顺序表中元素都不相同)，并由函数返 回被删元素的值，空出的位置由最后一个元素填补。(b)从顺序表中删除具有给定值e的所有元素。(c)在一个顺序表中如果一个数据值有重复出现，则留下第一个这样的数据值，并删 除其他所有重复的元素，使表中所有元素的值均不相同。(2)设计一个有序顺序表类，即表中的数据元素按数据元素值递增有序。实现以下函数：(a)把给定值e插入有序表中。(b)删除值为e的所有数据元素。(c)合并两个有序表，得到一个新的有序表。(d)从有序顺序表中删除其值在给定值s与t之间(s<t)的所有元素，如果set 或顺序表为空，则显示出错信息，并退出运行。(3)针对带头结点的单链表，试编写下列函数：(a)定位函数：在单链表中寻找第i个结点。若找到，则返回第i个结点的地址，否 则返回空指针。(b)统计函数：统计单链表中等于给定值e的元素个数。(4)设计一个带头结点的有序单链表类。实现以下函数：(a)插入函数：把元素值e作为数据元素插入表中。(b)删除函数：删除数据元素等于e的结点。