《数据结构》课程教学大纲课程代码：030731022课程英文名称：Data Structures课程总学时：40 讲课：40 实验：0 上机：0适用专业：电子信息科学与技术专业大纲编写（修订）时间：2017.5一、大纲使用说明（一）课程的地位及教学目标数据结构是电子信息科学与技术专业的一门专业基础必修课，是主干课。
课程主要讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及各种算法的设计问题。
通过本课程的学习，使学生掌握组织数据、存储数据以及处理数据的基本概念和软件设计的基本方法，培养学生程序设计能力，提高程序设计兴趣，为后续专业课的学习打下坚实的基础。
（二）知识、能力及技能方面的基本要求通过本课程的学习，在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，能够在不同存储结构上实现不同的运算，对不同的问题选择不同的数据结构，并对算法设计的方式和技巧有所体会，学生应用此能力能完成将一个具体的问题进行抽象地表示的任务。
（三）实施说明本课程主要包括基于不同数据结构的“算法思想设计”和“编程实现”两部分，要求学生理论和实际相结合，不仅要学会较为复杂的数据结构的设计，而且要求在计算机上编程实现。
教学中首先要使学生理解不同数据结构的逻辑关系，通过较多的实例说明它们的作用和应用背景，再通过大量的编程练习，使学生掌握数据结构和算法的设计和实现，进一步提高程序设计的能力。
（四）对先修课的要求本课程的教学必须在完成先修课程之后进行。
本课程主要的先修课程是C语言程序设计。
（五）对习题课、实践环节的要求1．对重点、难点章节（如：算法分析、线性表的应用、栈和队列的应用、树的应用、图的应用、排序的应用等）应安排习题课，习题课重点在于引导学生牢固掌握基本数据结构及其实现，并利用数据结构的知识解决常见实际问题，故采取精讲多练，用以解决实际问题为目的。
2．课后布置适量的作业，适时反馈作业问题。
学生必须独立、按时完成课外习题和作业，作业的完成情况应作为评定课程成绩的一部分。
3．每个学生要完成大纲中规定的必修实验，通过实验环节，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、物理结构和操作实现算法，培养学生进行模块化软件设计的能力。
实验成绩作为评定课程成绩的一部分。
4．本课程的课程设计单独设课，单独考核，具体要求参见相应的课程设计教学大纲。
（六）课程考核方式1．考核方式：考试2．考核目标：在考核学生对数据结构基本概念和实现方法的基础上，重点考核学生的算法设计和分析能力。
3．成绩构成：本课程的总成绩主要由四部分组成：平时成绩（包括作业情况、出勤情况等）占10%~20%，实践能力（结合《数据结构与算法实践》课程的最终成绩，以及依据平时学生完成算法设计与实现作业的实际情况给分）占10%，期中考试成绩（依据实际授课情况而定）占0~10%，期末考试成绩占70%。
（七）参考书目《数据结构：C语言版》，严蔚敏编，清华大学出版社，2007《数据结构：使用C语言》，朱战立编，电子工业出版社，2009《数据结构》，田鲁怀编，电子工业出版社，2006《算法与数据结构：C语言描述》，张乃孝编，高等教育出版社，2006《实用数据结构基础》，陈元春编，中国铁道出版社，2007二、中文摘要本课程是电子信息科学与技术专业的一门专业基础必修课，是主干课。
课程主要讲授数据结构中的线、树、图的结构及查找、排序技术，使学生掌握组织数据、存储数据以及处理数据的基本概念和软件设计的基本方法，培养学生程序设计能力。
本课程将为后续课程的学习以及相关课程设计、毕业设计等奠定重要的基础。
三、课程学时分配表注：表中（）内的数字代表此部分内容的建议选修学时四、教学内容及基本要求第1部分绪论总学时（单位：学时）：2 讲课：2 实验：0 上机：0 第1.1部分学习数据结构的意义及要求（讲课0.5学时）具体内容：1) 学习数据结构的意义2) 学习数据结构的要求第1.2部分数据结构的主要内容（讲课0.5学时）具体内容：数据结构的研究内容第1.3部分基本术语（讲课0.5学时）具体内容：掌握数据结构的基本术语重点:了解数据类型和抽象数据类型的概念第1.4部分算法描述及分析（讲课0.5学时）具体内容：1) 算法的相关概念2) 算法分析重点:掌握算法的时间复杂度分析方法难点:掌握算法的时间复杂度分析方法习题:求算法的时间复杂度第2部分线性表总学时（单位：学时）：6 讲课：6 实验：0 上机：0 第2.1部分线性表的逻辑结构、顺序表的实现（讲课2学时）具体内容：1) 线性表的逻辑结构2) 线性表的顺序表示和实现重点：顺序存储结构和顺序表的设计方法难点：顺序表的设计方法，主要是顺序表的各种操作第2.2部分单链表的实现（讲课2学时）具体内容：线性表链式表示和实现重点：链式存储结构和单链表的设计方法难点：单链表的设计方法，主要是单链表的各种操作第2.3部分线性表的应用（讲课2学时）具体内容：线性表的应用举例习题:线性表的归并实现建议实验：熟悉上机环境，C语言基础练习(实验2学时)建议实验：线性表的应用（实验2学时）第3部分栈和队列总学时（单位：学时）：6 讲课：6 实验：0 上机：0 第3.1部分栈（讲课2学时）具体内容：1) 栈的定义及特点2) 栈的顺序存储表示和链式存储表示重点：掌握栈在两种存储结构上实现的基本运算第3.2部分栈的应用（讲课2学时）具体内容：栈的应用举例难点：利用栈解决实际问题的方法习题:利用栈实现表达式求值第3.3部分队列（讲课2学时）具体内容：1 队列的定义及特点2) 队列的顺序存储表示和链式存储表示重点：掌握队列在两种存储结构上实现的基本运算难点：利用队列解决实际问题的方法第4部分数组和广义表总学时（单位：学时）：2 讲课：2 实验：0 上机：0 第4.1部分数组的定义（讲课0.5学时）具体内容：数组的定义第4.2部分数组的顺序表示和实现（讲课1学时）具体内容：数组的顺序存储表示和实现第4.3部分矩阵的压缩存储（讲课0.5学时）具体内容：矩阵的压缩存储重点：稀疏矩阵的压缩存储方法难点：稀疏矩阵的三元组表示下实现的算法习题:计算数组元素在计算机内存中的存放位置，稀疏矩阵的转置实现第5部分树和二叉树总学时（单位：学时）：6 讲课：6 实验：0 上机：0第5.1部分树和二叉树的定义与基本术语（讲课2学时）具体内容：1) 树的定义和基本术语2) 二叉树的定义、性质3) 二叉树的顺序存储结构和链式存储结构重点：二叉树的性质，二叉树的存储结构第5.2部分遍历二叉树（讲课2学时）具体内容：二叉树的先序遍历、中序遍历和后序遍历重点：二叉树的遍历算法，二叉树遍历算法的应用习题:二叉树的遍历及其应用第5.3部分哈夫曼树及其应用（讲课2学时）具体内容：哈夫曼树和哈夫曼编码重点：哈夫曼树在编码方面的应用难点：结合本章所学算法，解决与树或二叉树相关的应用问题习题:哈夫曼编码的实现建议实验：二叉树的基本操作（2学时）第6部分图总学时（单位：学时）：8 讲课：8 实验：0 上机：0第6.1部分图的定义和术语、图的存储结构（讲课2学时）具体内容：1) 图的定义和术语2) 图的存储结构重点：图的邻接矩阵和邻接表存储结构第6.2部分图的遍历（讲课2学时）具体内容：图的深度优先遍历和广度优先遍历重点：图的深度和广度优先遍历算法难点：图操作的实现方法习题:已知图的邻接表写出深度优先遍历和广度优先遍历序列第6.3部分最小生成树（讲课2学时）具体内容：最小生成树问题重点：普里姆算法和克鲁斯卡尔算法求最小生成树习题:对指定的带权图求最小生成树第6.4部分最短路径（讲课2学时）具体内容：最短路径问题重点：迪杰斯特拉算法求最短路径建议实验：图的操作（2学时）第7部分查找总学时（单位：学时）：6 讲课：6 实验：0 上机：0 第7.1部分线性表的查找（讲课2学时）具体内容：1) 顺序查找2) 折半查找重点：折半查找算法习题：折半查找算法的实现第7.2部分树表的查找（讲课2学时）具体内容：二叉排序树查找重点：二叉排序树的构造和操作习题：二叉排序树的构造第7.3部分哈希表的查找（讲课2学时）具体内容：1) 构造哈希表2) 处理冲突的方法3) 哈希查找重点：哈希表的构造方法难点：哈希表及其查找算法建议实验：查找算法的应用（2学时）第8部分内部排序总学时（单位：学时）：4 讲课：4 实验：0 上机：0第8.1部分插入排序（讲课2学时）具体内容：1) 直接插入排序2) 希尔排序重点：希尔排序的算法习题：写出对待排序序列进行直接插入排序和希尔排序的每一趟排序结果第8.2部分快速排序、堆排序（讲课2学时）具体内容：1) 快速排序2) 堆排序3) 各种内部排序方法的比较重点：快速排序和堆排序的算法难点：快速排序、堆排序的算法设计方法习题：写出对待排序序列进行快速排序和堆排序的每一趟排序结果建议实验：排序算法的应用（2学时）。