《数据结构》课程教学大纲
《数据结构》课程教学大纲
Data Structｕｒe
执笔人：编写日期:
一、课程基本信息
1、课程编号：
2、课程性质/类别：必修课/专业主干课
3、学时/学分：48 学时（另实验1６学时)/ 4 学分
4、适用专业:计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业
二、课程教学目标及学生应达到得能力
数据结构课程就是计算机相关专业得专业基础课、必修课程,主要介绍用计算机解决一系列问题特别就是非数值信息处理问题时所用得各种组织数据得方法、存储数据结构得方法以及在各种结构上执行操作得算法。通过本课程得学习,要求学生掌握各种数据结构得特点、存储表示、运算方法以及在计算机科学中最基本得应用，培养、训练学生选用合适得数据结构与编写质量高、风格好得应用程序得能力,培养学生分析问题、解决问题得能力，并为后续课程得学习打下良好得理论基础与实践基础。
三、课程教学内容与基本要求
(一）绪论( 3 学时）
1。主要内容:
（1)介绍什么就是数据结构;
(2)基本概念与术语: 数据、数据元素、数据对象，以及数据结构得定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；
(３)抽象数据类型得表示与实现;
（４)算法与算法分析：算法得概念、算法设计得要求以及算法效率得度量。
2。基本要求
(１）了解学习数据结构得重要性;
（２）掌握数据结构得定义及相关概念与术语;
（3）了解抽象数据类型得定义、表示与实现方法;
（4）理解算法得概念、特点并掌握度量其效率得基本方法.
３。自学内容：
类C语言得书写规范。
(二)线性表（6 学时)
1。主要内容:
（1）线性表得抽象数据类型定义与相关概念:数据项、记录、文件等;
(2）线性表顺序存储表示与基本操作得实现;
(3)线性表得链式存储表示与基本操作得实现;
（4)稀疏多项式得抽象数据类型定义、表示与加法得实现。
2.基本要求
(1）掌握线性表得定义与特点;
（2）熟练掌握线性表得顺序存储表示与插入、删除、查找等实现算法;
（3）熟练掌握单链表、循环链表、双向链表三种链表得表示,以及单链表得查找、插入、删除、创建等实现算法。
3。自学内容：
静态链表。
(三）栈与队列（ 5 学时）
１。主要内容:
(1）栈与队列得结构特性与抽象数据类型定义;
（2)栈与队列得顺序存储表示与实现；
(３）栈与队列得链式存储表示与实现；
(４)栈与队列在程序设计中得应用。
２.基本要求
(１)掌握栈与队列两种抽象数据类型得特点;
(2)掌握栈得两种存储表示与实现，特别注意栈满栈空得条件；
(3）掌握队列得两种存储表示与实现，特别注意队满队空得条件；
(４)了解递归算法与栈得关系。
３．自学内容:
链栈，离散事件模拟
（四)串( 3 学时）
1.主要内容：
(1)串得抽象数据类型定义;
（２）串得表示与实现：定长顺序存储结构与堆分配存储结构;
(3)串得各种基本操作得实现及其应用;
（４）串得模式匹配操作。
２.基本要求
（1）熟悉串得一些基本操作得定义，并能利用基本操作实现串得其它操作;
(2）掌握串得定长顺序存储结构以及基本操作得实现；
（３)掌握串得堆分配存储结构以及基本操作得实现；
(4）掌握串得简单模式匹配算法，理解KMＰ算法。
３.自学内容:
串操作得应用实例。
(五)数组与广义表( ４学时）
1。主要内容：
(１)数组得抽象数据类型定义及其顺序表示与实现;
(2）特殊矩阵与稀疏矩阵得压缩存储;
（3）广义表得抽象数据类型定义与存储结构.
2。基本要求
（1)了解数组得两种存储表示方法，并掌握数组在以行为主得存储结构中得地址计算方法；
(2)掌握对特殊矩阵进行压缩存储时得下标变换公式;
（3)熟悉稀疏矩阵得三元组顺序表存储结构下得一般转置与快速转置算法；了解十字链
表等存储结构;
（4)掌握广义表得结构特点、取表头表尾操作,及其存储表示方法。
3.自学内容：
采用十字链表存储结构创建稀疏矩阵。
(六)树与二叉树(1０学时)
1。主要内容：
(1）树得抽象数据类型定义与基本术语;
(２)二叉树得抽象数据类型定义、性质与存储结构；
(3)二叉树得遍历；
（4）线索二叉树得定义、遍历及线索化二叉树；
（5）树得存储结构、树与森林得遍历以及与二叉树得转换；
(6)Huffmａｎ树及其应用。
2．基本要求
（1）掌握树型结构得特点与基本术语;
（2）熟练掌握二叉树得性质，了解相应得证明方法;
(3）了解二叉树得顺序存储结构与链式存储结构，熟练掌握二叉链表存储结构；
（4)熟练掌握二叉树三种遍历得递归算法与中序遍历非递归算法，能灵活运用遍历算法实现二叉树得其她操作；
（５）熟练掌握二叉树得线索化过程，以及在中序线索二叉树上找结点得前驱与后继得方法;
（6）熟悉树得各种存储结构及其特点,掌握树与森林与二叉树得转换方法；
(7）了解Ｈufｆmａｎ树得特性,掌握建立Ｈｕｆｆman树与Huｆfman编码得方法。
３。自学内容：
先序、后序遍历二叉树非递归算法，层次遍历二叉树算法。
(七）图（9 学时）
１.主要内容:
(1)图得定义与术语;
(2）图得四种存储结构：数组表示法（邻接矩阵）、邻接表、十字链表与邻接多重表；
（3）图得两种遍历策略：深度优先遍历与广度优先遍历；
(4）图得连通性与最小生成树；
(5)有向无环图及其应用：拓扑排序与关键路径；
(6）最短路径问题。
2.基本要求
(1）熟悉图得定义与术语；
(2)了解图得存储结构，熟练掌握数组表示法（邻接矩阵）与邻接表存储表示；
(3）熟练掌握图得深度优先遍历与广度优先遍历算法；
(4)掌握无向连通带权图得最小生成树求解算法;
（5)了解有向无环图、ＡＯV网、ＡOＥ网及其在实际中得应用,熟悉拓扑排序算法与关键路径算法;
（6）熟悉两种最短路径问题求解算法。
3．自学内容：
树得先根遍历算法与图得深度优先遍历算法比较；
树得层次遍历算法与图得广度优先遍历算法比较.
(八)查找( 4学时)
１。主要内容:
(１）查找得基本概念与相关术语;
（2)静态查找表：顺序查找、折半查找与索引顺序表查找；
（3)动态查找表：二叉排序树得查找、插入与删除；
（4)哈希表。
２．基本要求
（1）了解查找得作用,熟悉相关术语；
(2）熟练掌握顺序查找、折半查找与索引顺序表查找;
（3)熟练掌握二叉排序树得特性、构造与查找方法;
(４)熟练掌握哈希表得构造方法，特别就是哈希函数与处理冲突方法得选取；
（5)通过分析等概率下得平均查找长度来衡量各种查找方法得效率。
3.自学内容：
平衡二叉树。
（九)内部排序( 4 学时)
1．主要内容：
(1）排序得基本概念与相关术语;
(2)插入排序:直接插入排序、折半插入排序与希尔排序；
（３）交换排序：起泡排序与快速排序;
（4）选择排序：简单选择排序与堆排序；
（５）归并排序:二路归并排序;
（6)基数排序：链式基数排序；
（7）各种内部排序方法得比较讨论。
2.基本要求
(1)了解排序作用,熟悉相关术语；
(２）掌握多种排序得基本思想、算法特点与排序过程,分析它们得时间复杂度、空间复杂度与稳定性。
3．自学内容:
二路插入排序、表插入排序与树形选择排序。
四、教学安排建议
1、作业练习
?完成每章得教学后进行布置习题,使用教材配套得《数据结构题集(Ｃ语言版）》.尽量选择基础得并且加注了标记得题,应注重于精，而不要求多.要求积极独立完成所布置得习题，建议安排至少六次。
2、案例分析
可参考选择以下一些案例：（1）学生通讯录管理系统，（2）表达式求值问题（3)交通咨询系统，等。
3、专题研讨
可参考选择以下一些:（1）最小生成树问题(2)航班信息查询与检索系统，（3)内部排序算法比较,等。
4、实验安排
为了达到理论与实际应用得结合，让学生能将所学知识应用于实际问题得求解中,培养学生得实际动手能力,从而加深对概念及所学知识得理解，灵活、牢固掌握教材内容，提高程序设计及解决实际问题得能力，实验环节得安排非常重要。
建议实验安排为八次,共16学时,分别如下：
实验1线性表得顺序存储结构得实现（２学时）
实验2 线性表得链式存储结构得实现（2学时）
实验3栈得算法实现（2学时)
实验4 队列得算法实现(２学时)
实验5 串类型及操作（2学时）
实验6 二叉树得建立与遍历(2学时）
实验7图得建立与遍历(2学时)
实验8查找与排序（2学时)
注:教师可根据教学实际情况(如：学生情况及学时情况等)，适当调整实践教学内容及学时分配。
五、课程考核
１、考核形式及成绩评定办法
本课程考核形式为：平时成绩占40%,期末考试成绩占6０％。其中平时成绩得结构分包括：课堂表现１0%、平时作业1０%与实验20%，期末考试为闭卷笔试考试:1２０分钟，卷面分满分１００分。期末考试成绩低于50分者,本课程成绩按不及格论处.
2、本课程考核得基本要求
课堂表现10%:包括课堂考勤与课堂提问，如果缺课课时达到本课程教学时数得1／3，则取消考试资格。
平时作业10%:根据上交次数及完成情况进行评定。
实验２0％:根据各次实验完成情况及实验报告成绩进行评定.
期末考试6０%：本课程得期末考试考核内容主要包括线性表、栈与队列、串、数组与广义表、树与二叉树、图、查找与内部排序。其中，线性表、二叉树、图、查找与内部排序内容为考核得重点。
六、本课程与其它课程得先行后续关系
先行课程:《高级程序设计语言》、《离散数学》
后续课程:《操作系统》、《编译原理》、《数据库理论》、《算法分析与设计》等
七、建议教材及教学参考书
１、教材：
严蔚敏，吴伟民编著，《数据结构(C语言版)》，清华大学出版，２012、5
严蔚敏，吴伟民编著,《数据结构题集（Ｃ语言版)》，清华大学出版，2012、5
2、参考书：
[1］许卓群,张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，20０４、
［2]徐孝凯，《数据结构简明教程》,清华大学出版社，199５
［3］陈文博,朱青,《数据结构与算法》，机械工业出版社，1996
［4］李云清,杨庆红，揭安全编著,《数据结构》（C语言版)，人民邮电出版社，2007、
[5］杨秀金主编,《数据结构》,西安电子科技大学出版社，2０02、
［6] 李廉治,姜文清，郭福顺,《数据结构》，大连理工大学出版社,１9８９
［7] Ａho A V, HｏpcroｆｔJ E, Ullｍan J D、Data Strucｔures anｄAlgorｉthms、Adｄｉｓon－Wesley Ｐublishing pany，Inc、,1983
［8］ＢaｒｏnＲＪ，Shapｉｒo L G、DatａStｒucturｅｓaｎdｔｈｅir Ｉｍplemeｎｔａｔiｏｎ、VanＮｏｓｔｒand Ｒeinｈoｌd ｐany，1９80 ［９］Eｓaｋov J，WeｉｓｓT、Ｄａｔa Structuｒeｓ：AｎＡｄvanｃed Ａp ｐrｏach Uｓｉｎg C、Prｅｎtiｃｅ—Hall, Iｎc、，1９8９
[10］［美］S巴斯《计算机算法：设计与分析引论》朱洪等译，复旦大学出版社，１985