西南科技大学本科课程教学大纲 《数据结构》课程教学大纲 【课程代码】:14314021 【英文译名】: Data structure 【适用专业】:计算机科学与技术、软件工程、信息安全 【学分数】:3.5 【总学时数】:56 、本课程教学目的和课程性质 课程教学目的:通过本课程的学习,使学生学会分析研究计算机加工的数据的结构特性,掌握 基本的数据组织、数据存储及数据处理的方法,掌握算法的效率分析方法,培养学生根据实际问题 的需要选择和设计合适的逻辑结构、存储结构及算法的能力。 课程性质:计算机科学与技术、软件工程、信息安全专业的必修专业基础课程,可以作为其它 专业的选修课程。 二、本课程的基本要求 通过本课程的教学,应使学生能从逻辑结构、存储结构和算法三个层面理解和掌握常用数据结 构,并达到以下要求 1、掌握线性表、栈、队列、数组、树、图的逻辑结构及常用的存储结构和算法,了解串、广义 表、文件、优先队列、线索二叉树、回溯法,掌握顺序存储、链式存储、索引存储和散列存储 2、掌握递归方法 3、掌握插入排序、选择排序和交换排序,理解归并排序、基数排序; 4、掌握顺序表査找、索引表查找、散列表查找和树表査找; 能运用时间和空间复杂度分析算法的效率; 6、能针对实际问题,选择和设计合适的逻辑结构、存储结构及算法。 三、本课程与其他课程的关系 本课程要求学生对计算机硬件、离散数学有初步的了解,并有一定的程序设计经验(C/C++) 前修课程:离散数学、C/C++程序设计 后续课程:操作系统、数据库原理 四、课程内容
西南科技大学本科课程教学大纲 1 《数据结构》课程教学大纲 【课程代码】：14314021 【英文译名】：Data Structure 【适用专业】：计算机科学与技术、软件工程、信息安全 【学 分 数】：3.5 【总学时数】：56 一、本课程教学目的和课程性质 课程教学目的：通过本课程的学习，使学生学会分析研究计算机加工的数据的结构特性，掌握 基本的数据组织、数据存储及数据处理的方法，掌握算法的效率分析方法，培养学生根据实际问题 的需要选择和设计合适的逻辑结构、存储结构及算法的能力。 课程性质：计算机科学与技术、软件工程、信息安全专业的必修专业基础课程，可以作为其它 专业的选修课程。 二、本课程的基本要求 通过本课程的教学，应使学生能从逻辑结构、存储结构和算法三个层面理解和掌握常用数据结 构，并达到以下要求： 1、掌握线性表、栈、队列、数组、树、图的逻辑结构及常用的存储结构和算法，了解串、广义 表、文件、优先队列、线索二叉树、回溯法，掌握顺序存储、链式存储、索引存储和散列存储； 2、掌握递归方法； 3、掌握插入排序、选择排序和交换排序，理解归并排序、基数排序； 4、掌握顺序表查找、索引表查找、散列表查找和树表查找； 5、能运用时间和空间复杂度分析算法的效率； 6、能针对实际问题，选择和设计合适的逻辑结构、存储结构及算法。 三、本课程与其他课程的关系 本课程要求学生对计算机硬件、离散数学有初步的了解，并有一定的程序设计经验（C/C++）。 前修课程：离散数学、C/C++程序设计； 后续课程：操作系统、数据库原理； 四、课程内容
计算机科学与技术学院 )数据结构及算法性能分析 1、数据、数据元素、数据项的概念及相互关系; 2、逻辑结构、存储结构的特点及分类; 3、逻辑结构、存储结构、算法的联系与区别; 4、抽象数据类型的概念; 5、算法的时间和空间复杂度。 重点:逻辑结构、存储结构及算法的联系;评价算法效率的标准及方法 难点:算法的时间、空间复杂度分析。 (二)线性表 、线性表逻辑结构 顺序存储结构 3、顺序表的定义及基本算法的实现 4、链式存储结构 5、链表(单链表、单循环链表、双向循环链表)的定义及算法实现; 基本算法的效率分析 重点:线性表的定义及逻辑特点:顺序表上插入、删除和定位算法的实现:单链表、单循环链 表、双向循环链表的结构特点:单链表和双向循环链表的插入、删除算法的实现。 难点:头结点在链表中的作用;双向循环链表的插入、删除算法的指针操作顺序, 三)栈和队列 1、栈的特点; 2、顺序栈和链栈的基本算法的实现 3、队列的特点 4、循环队列和链队列的基本算法的实现 5、优先队列的实现 重点:栈的定义及逻辑特点:栈的顺序(链式)存储结构及入栈、出栈算法的实现:队列的定 义及逻辑特点;队列的顺序(链式)存储结构及入队、出队算法的实现。 难点:循环队列的队空、队满条件:循环队列上的插入、删除算法;优先队列。 (四)数组、串、广义表 多维数组 2、特殊矩阵的压缩存储 2
计算机科学与技术学院 2 （一）数据结构及算法性能分析 1、数据、数据元素、数据项的概念及相互关系； 2、逻辑结构、存储结构的特点及分类； 3、逻辑结构、存储结构、算法的联系与区别； 4、抽象数据类型的概念； 5、算法的时间和空间复杂度。 重点：逻辑结构、存储结构及算法的联系；评价算法效率的标准及方法。 难点：算法的时间、空间复杂度分析。 （二）线性表 1、线性表逻辑结构； 2、顺序存储结构； 3、顺序表的定义及基本算法的实现； 4、链式存储结构； 5、链表（单链表、单循环链表、双向循环链表）的定义及算法实现； 6、基本算法的效率分析。 重点：线性表的定义及逻辑特点；顺序表上插入、删除和定位算法的实现；单链表、单循环链 表、双向循环链表的结构特点；单链表和双向循环链表的插入、删除算法的实现。 难点：头结点在链表中的作用；双向循环链表的插入、删除算法的指针操作顺序。 （三）栈和队列 1、栈的特点； 2、顺序栈和链栈的基本算法的实现； 3、队列的特点； 4、循环队列和链队列的基本算法的实现； 5、优先队列的实现。 重点：栈的定义及逻辑特点；栈的顺序（链式）存储结构及入栈、出栈算法的实现；队列的定 义及逻辑特点；队列的顺序（链式）存储结构及入队、出队算法的实现。 难点：循环队列的队空、队满条件；循环队列上的插入、删除算法；优先队列。 （四）数组、串、广义表 1、多维数组； 2、特殊矩阵的压缩存储；
西南科技大学本科课程教学大纲 3、稀疏矩阵 4、串的定义、存储结构及基本操作 5、串的模式匹配算法 6、广义表的特点及应用。 重点:计算多维数组元素的存储地址;对称矩阵、三角矩阵的压缩存储:稀疏矩阵的三元组表 示法;串的模式匹配算法;广义表的特点 难点:稀疏矩阵的压缩存储算法;串的模式匹配算法。 (五)递归 1、递归的概念 2、递归的设计及应用 3、递归的效率分析 4、回溯法。 重点:适用递归的条件。 难点:递归过程分析:递归的效率分析 (六)树和二叉树 1、树定义、逻辑结构及特点 树的存储结构 3、树和森林: 4、二叉树的定义、性质及存储方法 树和二叉树的转换 6、二叉链表存储 7、二叉树的前序、中序及后序遍历 8、二叉树的线索化方法; 9、哈夫曼树和哈夫曼算法。 重点:树的递归定义;树的存储结构;二叉树的定义、逻辑特点及五个性质;二叉树的链式存 储结构:二叉树的三种遍历方法及算法实现:哈夫曼树和哈夫曼算法 难点:树与二叉树的转换;递归在遍历算法中的应用:哈夫曼算法及其应用。 (七)图 1、图的概念及术语 2、图的操作
西南科技大学本科课程教学大纲 3 3、稀疏矩阵； 4、串的定义、存储结构及基本操作； 5、串的模式匹配算法； 6、广义表的特点及应用。 重点：计算多维数组元素的存储地址；对称矩阵、三角矩阵的压缩存储；稀疏矩阵的三元组表 示法；串的模式匹配算法；广义表的特点。 难点：稀疏矩阵的压缩存储算法；串的模式匹配算法。 （五）递归 1、递归的概念； 2、递归的设计及应用； 3、递归的效率分析； 4、回溯法。 重点：适用递归的条件。 难点：递归过程分析；递归的效率分析。 （六）树和二叉树 1、树定义、逻辑结构及特点； 2、树的存储结构； 3、树和森林； 4、二叉树的定义、性质及存储方法； 5、树和二叉树的转换； 6、二叉链表存储； 7、二叉树的前序、中序及后序遍历； 8、二叉树的线索化方法； 9、哈夫曼树和哈夫曼算法。 重点：树的递归定义；树的存储结构；二叉树的定义、逻辑特点及五个性质；二叉树的链式存 储结构；二叉树的三种遍历方法及算法实现；哈夫曼树和哈夫曼算法。 难点：树与二叉树的转换；递归在遍历算法中的应用；哈夫曼算法及其应用。 （七）图 1、图的概念及术语； 2、图的操作；
计算机科学与技术学院 3、图的邻接矩阵和邻接表存储方法; 4、图的深度优先搜索遍历和广度优先搜索遍历: 5、最小生成树的概念; 6、Prim算法和 Kruskal算法 7、拓扑排序 8、最短路径 重点:图的邻接矩阵和邻接表存储:图的深度优先搜索遍历方法和广度优先搜索遍历方法;生 成树和最小生成树的概念;Prim算法的实现;最短路径的算法实现。 难点:图的存储结构特点;深度优先搜索遍历和广度优先搜索遍历的算法;最短路径算法 (八)排序 1、排序的概念 排序算法的稳定性 3、插入排序 4、选择排序; 5、交换排序 6、归并排序 7、基数排序; 重点:内排序和外排序、稳定排序和非稳定排序的区别;直接插入排序、直接选择排序、冒泡 排序、快速排序、堆排序的思路及算法实现; 难点:希尔排序:快速排序;归并排序 (九)查找 1、查找概念; 2、静态查找和动态查找 3、顺序表查找; 4、索引表查找 5、树表查找 6、散列表(哈希表)查找; 重点:折半査找;索引表查找;二叉排序树:散列表及冲突解决的方法;散列表的查找、插入 和删除算法的实现。 难点:平衡二叉树;B-树和B+树;散列表算法
计算机科学与技术学院 4 3、图的邻接矩阵和邻接表存储方法； 4、图的深度优先搜索遍历和广度优先搜索遍历； 5、最小生成树的概念； 6、Prim 算法和 Kruskal 算法； 7、拓扑排序； 8、最短路径； 重点：图的邻接矩阵和邻接表存储；图的深度优先搜索遍历方法和广度优先搜索遍历方法；生 成树和最小生成树的概念；Prim 算法的实现；最短路径的算法实现。 难点：图的存储结构特点；深度优先搜索遍历和广度优先搜索遍历的算法；最短路径算法。 （八）排序 1、排序的概念； 2、排序算法的稳定性； 3、插入排序； 4、选择排序； 5、交换排序； 6、归并排序； 7、基数排序； 重点：内排序和外排序、稳定排序和非稳定排序的区别；直接插入排序、直接选择排序、冒泡 排序、快速排序、堆排序的思路及算法实现； 难点：希尔排序；快速排序；归并排序。 （九） 查找 1、查找概念； 2、静态查找和动态查找； 3、顺序表查找； 4、索引表查找； 5、树表查找； 6、散列表（哈希表）查找； 重点：折半查找；索引表查找；二叉排序树；散列表及冲突解决的方法；散列表的查找、插入 和删除算法的实现。 难点：平衡二叉树；B-树和 B+树；散列表算法
西南科技大学本科课程教学大纲 (十)文件 1、文件的概念 2、顺序文件; 3、索引文件 4、直接存储文件; 5、多重表文件和倒排文件 重点:文件的逻辑结构;文件存储结构 难点:文件的动态索引结构 五、教学方法建议 课程的难点在于应用,教师可以用案例来示范数据结构知识的综合运用,学生在课后应分析并 完善所讲案例 六、考核方式 采用结构化评分,总成绩中建议平时成绩(作业、课堂提问、案例分析、课堂测试等)占 期末笔试成绩占50%。 七、其它说明 本课程配套有独立开课的实验课程:《数据结构应用设计》(24学时)。 八、选用教材及主要参考书 1、教材 [门]数据结构一使用C++语言(第二版).朱战立.西安电子科技大学出版社,2005 2、参考书 [1]数据结构(用面向对象方法与C++描述).殷人昆.清华大学出版社,2004 [2]数据结构与算法.齐德昱.清华大学出版社,2003 [3]数据结构与问题求解(C+版)(第2版). Mark allen Weiss(美),张丽萍 清华大学出版社,2005
西南科技大学本科课程教学大纲 5 （十）文件 1、文件的概念； 2、顺序文件； 3、索引文件； 4、直接存储文件； 5、多重表文件和倒排文件。 重点：文件的逻辑结构；文件存储结构。 难点：文件的动态索引结构。 五、教学方法建议 课程的难点在于应用，教师可以用案例来示范数据结构知识的综合运用，学生在课后应分析并 完善所讲案例。 六、考核方式 采用结构化评分，总成绩中建议平时成绩（作业、课堂提问、案例分析、课堂测试等）占 50%、 期末笔试成绩占 50%。 七、其它说明 本课程配套有独立开课的实验课程：《数据结构应用设计》（24 学时）。 八、选用教材及主要参考书 1、教材 [1]数据结构--使用 C++语言(第二版).朱战立.西安电子科技大学出版社,2005 2、参考书 [1]数据结构(用面向对象方法与 C++描述).殷人昆.清华大学出版社,2004 [2]数据结构与算法.齐德昱.清华大学出版社,2003 [3]数据结构与问题求解(C++版)(第 2 版).Mark Allen Weiss(美),张丽萍. 清华大学出版社 ,2005