《数据结构》是一门研究非数值计算程序设计中的操作对象以及这些对象之间的关系和操作的学科，其主要研究数据组织和数据处理的方法。在国外，该课程作为一门独立的课程始于1968年，它出现在美国一些大学的计算机系的教学计划中，目前，该课程已成为计算机类专业一门非常重要的专业基础课程，它所研究的数据组织和数据处理的方法在后续的操作系统、编译原理、人工智能、计算机网络、数据库等课程中都是重要而必备的基础。

课程内容主要包括：数据结构的基本概念、线性表、栈和队列、串、数组和广义表、树、图、查找和排序。

从本质上讲，数据结构属于程序设计类课程，是程序设计语言课程的进阶篇。首先，程序是对数据的操作，由输入产生输出的IPO模式。对于比较复杂的处理对象，就需要从数据结构的角度来组织和存储数据，如采用顺序存储还是链式存储结构更加高效；另外，对于比较复杂的数据操作，就需要采用一些相应的数据结构来求解，如迷宫问题就借助于栈来完成。所以数据结构课程要讲解人们在软件开发中常见的数据结构，并从逻辑结构到存储结构，再到算法设计这三个层面加以学习。程序设计解决问题往往有多种方法，且不同方法之间的效率可能相差甚远。程序的时间和空间效率，不仅跟数据的组织方式有关，也跟处理流程的巧妙程度有关。本课程将介绍有关数据组织、算法设计、时间和空间效率的概念和通用分析方法，帮助学生学会数据的组织方法和一些典型算法的实现，是学生能够针对问题的应用背景分析问题及选择解决该问题应采用的数据结构，从而培养高级程序设计技能。

数据结构是计算机应用专业一门统设必修课和专业基础课，它主要研究数据的各种逻辑结构，在计算机中的存储结构，对数据进行的插入、查找、删除、排序、遍历等运算，这些运算在存储结构上具体实现的算法。学习好该课程将为学好整个计算机专业打下坚实的基础。

第一章  绪论

    重点掌握的内容：

    1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。

    2. 集合结构、线性结构、树结构和图结构的特点。

    3. 抽象数据类型的定义和表示方法。

    4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。

    5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。

    6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。

    7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。

    8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。

    对于本章的其余内容均作一般掌握。

第二章  线性表

    重点掌握的内容：

    1. 线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

    2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。

    3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。

    4. 链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。

    5. 单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。

    6. 带表头附加结点的链表、循环链表、双向链表的结构特点。

    7. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。

    8. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。

    对于本章的其余内容均作一般掌握。

第三章  栈和队列

    重点掌握的内容：

    1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

    2. 栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。

    3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。

    4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。

    5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。

    6. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

    7. 队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。

    8. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。

    9. 利用栈和队列解决简单问题的算法分析和设计。

    一般掌握的内容：

    1. 后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。

    2. 求解阶乘问题和迷宫问题的方法和算法。

    3. 队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。

第四章  串 、数组和广义表

    重点掌握的内容：

    1. 了解串的顺序存储结构和堆存储结构。掌握串的古典的模式匹配算法。

2. 掌握数组的地址计算方法。了解稀疏矩阵的两种压缩存储方法的特点和适用范围。

3.了解广义表的结构特点及其存储方法。

对于本章的其余内容均作一般了解。

第五章  树和二叉树

    重点掌握的内容：

    1. 树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。

    2. 树和二叉树的概念，如结点的度、树的度、树的层数、树的深度等。

    3. 树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。

    4. 二叉树中结点的编号规则和对应的顺序存储结构。

    5. 二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。

    6. 二叉树的先序、中序、后序遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法，每种算法的时间复杂度。

    7. 普通树的链接存储结构，GTreeNode类型的定义和每个域的定义及作用。

    8．普通树的先根、后根和按层遍历的过程及算法。

    9. 在链接存储的二叉树上实现指定功能的算法分析和设计。

    10.二叉搜索树的定义和性质。

    11．叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。

    12．叉搜索树插入的递归算法和非递归算法，相应的时间复杂度，根据一组数据生成一棵二叉搜索树的过程。

    13．的定义和顺序存储结构，小根堆和大根堆的异同。

    14．堆中插入元素的过程、算法描述及时间复杂度。

    15．堆中删除元素的过程、算法描述及时间复杂度。

    16.夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。

    对本章的其余内容均作一般了解。

第六章  图

    重点掌握的内容：

    1. 图的顶点集和边集的表示。

    2. 图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。

    3. 图的邻接矩阵、邻接表和边集数组三种存储结构及相应的空间复杂度。

    4.图的深度优先和广度优先搜索遍历的过程。

    5.对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

    6.对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

    7.图的生成树、生成树的权、最小生成树等的定义。

    8.根据普里姆算法求图的最小生成树的过程和算法描述。

    9.据克鲁斯卡尔算法求图的最小生成树的过程和算法描述。

    10.图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程和算法。

    对本章的其余内容均作一般掌握。它包括建立图的邻接矩阵、邻接表、边集数组算法，建立图的逆邻接表和十字邻接表等内容。      

第七章  查找

    重点掌握的内容：

    1. 在一维数组上进行顺序查找的过程、算法、平均查找长度和时间复杂度。

    2. 在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。

    3. 索引存储的概念，索引表的存储结构和索引项的存储结构，索引查找一个元素的过程、平均查找长度和时间复杂度。

    4. 散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。

    5. 利用除留余数法建立散列函数求元素散列地址的方法。

    6. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。

    7. 根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。

    8. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。

    一般掌握的内容：

    1. 索引查找和分块查找算法。

    2. B_树查找算法。

    3. 向B_树中插入元素的过程。

    对本章的其余内容均作一般了解。

第八章  排序

    重点掌握的内容：

    1. 直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。

    2. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。

    3. 快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。

    4. 快速排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。

    5. 二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。

    一般掌握的内容：

    1. 每一种排序方法的稳定性。

    2. 直接插入排序和直接选择排序的算法。

    一般了解的内容：

    1. 二路归并排序过程中涉及的每个算法。

    2. 冒泡排序算法。

在线答题考试，期中成绩占40%，期末成绩占60%

C语言程序设计

离散数学

1. 教材

严蔚敏、李冬梅、吴伟民等。《数据结构》（C语言版），人民邮电出版社。

2.参考教材：

(1)《数据结构》（C语言版），严蔚敏，吴伟民，清华大学出版社.

(2)《数据结构教程》（第5版），李春葆主编 清华大学出版社.

(3)《数据结构》，陈越、何钦铭等,高等教育出版社.

(4)《数据结构学习与实验指导》，陈越、何钦铭等,高等教育出版社.

(５)《数据结构》 耿国华等编,西安电子科技大学.