课程简介
course introduction
数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基础。主要内容包括:线性表、栈和队列、串、数组和广义表、树、图、查找算法和排序算法。数据结构研究数据的组织方式，内容丰富、学习量大，隐含在各部分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构的算法。要求学生掌握贯穿全课程的动态链表存储结构，掌握算法设计的动态性和抽象性。要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能分析技巧，并培养复杂程序设计的技能。
教学大纲
teaching syllabus
第一章 绪论
本章知识点:理解相关的基本概念；掌握算法五大要素；掌握计算语句频度和估算算法时间复杂度的方法。
重点:数据结构基本概念, 算法的时间和空间复杂度
难点:算法的时间和空间复杂度
第二章 线性表
本章知识点:掌握线性表的逻辑结构、线性表的存储结构、线性表在顺序结构和链式结构上实现定义、查找、插入和删除等基本操作的方法；理解从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合。
重点:线性表的概念
难点:线性表的表示及实现
第三章 栈和队列
本章知识点:了解栈和队列的定义及特点；掌握在两种存储结构上栈的基本操作的实现；掌握循环队列和链队列的基本运算；掌握递归算法执行过程中栈状态的变化过程。
重点:栈和队列的表示和实现
难点:循环队列
第四章 串、数组和广义表
串的逻辑结构，存储结构；串的应用；
本部分知识点:理解串的基本运算的定义，掌握利用这些基本运算来实现串的其它各种运算的方法；掌握在顺序存储结构上实现串的各种操作的方法；重点掌握串上实现的模式匹配算法。
重点:串的各种运算方法
难点:串的模式匹配算法
数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法；(该部分根据学时选讲)
本部分知识点:掌握数组在以行为主的存储结构中的地址计算方法；掌握矩阵实现压缩存储时的下标变换；理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法；掌握广义表的定义及其存储结构，学会广义表的表头，表尾分析方法。
重点:稀疏矩阵存储，矩阵元素地址的计算，广义表的表头、表尾分析
难点:矩阵的三元组存储时算法
第五章 树和二叉树
本章知识点:掌握二叉树的基本概念、性质和存储结构； 熟练掌握二叉树的前、中、后序遍历方法； 了解线索化二叉树的思想 ； 熟练掌握:霍夫曼树的实现方法、构造霍夫曼编码的方法；. 了解:森林与二叉树的转换，树的遍历方法
重点:二叉树概念，性质，遍历算法，最优二叉树
难点:二叉树的非递归算法，最优二叉树
第六章 图
图的基本概念；图的存储结构；图的遍历及应用:最小生成树、最短路径、拓扑排序。
本章知识点:熟悉图的各种存储结构，了解实际问题与采用何种存储结构和算法有密切联系；掌握遍历图的递归和非递归算法；掌握应用图的遍历算法求各种简单路径问题，比如，最小生成树、最短路径、拓扑排序等。
重点:图的相关概念，图的遍历算法
难点:最小生成树，最短路径，拓扑排序
第七章 查找
静态查找表(顺序表,有序表,索引顺序表)； 动态查找表(二叉排序树,平衡二叉树,b-树和b 树)的建立和查找；哈希表的建立，查找及分析；习题讨论课。
本章知识点:理解顺序查找，折半查找和索引查找的方法，并能灵活应用；掌握二叉排序树的构造方法及算法；掌握二叉平衡树的建立方法；了解b-树，b 树的特点以及它们的建立过程；掌握哈希表的构造方法；按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度，理解哈希表在查找不成功时的平均查找长度的计算方法。
重点:折半查找，二叉排序树，哈希表
难点:二叉平衡树的建立方法，哈希表
第八章 内部排序
概念；插入排序；交换排序(起泡,排序)；选择排序(简单选择,堆)；归并排序；基数排序。
本章知识点:理解各种排序方法的特点并能灵活应用；掌握各种方法的排序过程和各种排序方法的时间复杂度分析。重点掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程，难点是这四个排序算法的实现。
重点:插入排序，交换排序，快速排序，堆排序
难点:快速排序，堆排序，归并排序
留言板
message board
