3.1 线性结构
线性结构：主要用于客观世界中具有单一前驱和后继的数据关系描述
3.1.1 线性表
线性表：是n个元素的有限序列，存在唯一的一个称为第一个的元素；存在唯一的称为最后一个的元素；除第一个外每个元素只有一个直接前驱，除最后一个外，只有一个直接后继
存储结构：顺序存储和链式存储
顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的两个元素在物理上也相邻
链式存储：通过指针连接起来的结点来存储数据元素，结点由数据域和指针域组成，数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继的位置信息
3.1.2 栈和队列
栈：后进先出的线性表，只能通过访问它的一端来实现数据存储和检索
栈的基本运算：初始化栈、判栈空、入栈、出栈、读取栈顶元素
队列：先进先出的线性表，队尾插入元素，对头删除元素
队列的基本运算：初始化队列、判队空、入队、出队、读队头元素
3.1.3 串
串：仅由字符构成的有限序列；
相关概念：空串、空格穿、子串、串相等、串比较
基本操作：赋值操作、连接操作、求串长、串比较、求子串
串的模式匹配：子串的定位操作
3.2 数组/矩阵和广义表
3.2.1 数组
数组：定长线性表在维数上的扩展，即线性表中的元素又是一个线性表
特点：数目固定、元素类型相同、上下标关系具有上下界的约束且下标有序
运算：给定下标存取相应的数据元素、给定下标修改相应数据值
3.2.2 矩阵
矩阵存储时，为0的元素不分配存储空间，不为0的元素分配存储空间
3.2.3 广义表
广义表是线性表的推广，其元素可以是单元素，也可以是有结构的表
3.3 树
3.3.1 树与二叉树的定义
树的概念：双亲、孩子和兄弟；度；叶子结点；内部结点；层次；高度；有序/无序树
3.3.2 二叉树的性质与存储结构
二叉树的性质：二叉树第i层上最多有2（i-1）个结点；高度为k的二叉树最多有2（k）-1个节点；对于任何一棵二叉树，若其终端节点数为n0，度为2的节点数为n2，n0=n2+1；具有n个节点的完全二叉树的深度为log2n+1
二叉树的存储：完全二叉树适用于顺序存储、链式存储适用于一般二叉树
3.3.3 二叉树的遍历
遍历：先序、中序、后序（以根结点的遍历位置来定）
3.3.4 线索二叉树
3.3.5 最优二叉树
最优二叉树：哈夫曼树，带权路径长度最短的树
树的路径长度：树根到每个叶子结点的路径长度之和
带权路径长度：树中所有叶子结点的带权路径长度之和
哈夫曼编码：
3.3.6 树与森林
树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法
3.4 图
3.4.1 图的定义与存储
图：由顶点和边组成的数据结构
图的概念：有向图、无向图、完全图、度、出度、入度、路径、子图、连通图与连通分量、强连通图与强连通分量、网、有向树
图的存储：邻接矩阵表示法、邻接链表表示法
邻接矩阵表示法：用一个矩阵来表示图中顶点之间的关系
邻接链表表示法：为图的顶点建立一个单链表，第i个单链表的结点表示依附于顶点vi的边
3.4.2 图的遍历
图的遍历：深度优先搜索、广度优先搜索
深度优先搜索：设置指针p指向顶点v；访问p所指顶点，并使p指向与其向邻接的且尚未被访问的顶点；若p存在重复上一步，若不存在则沿刚才的次序方向回溯到一个未被访问的顶点，使p指向该顶点，重复，直到所有的顶点均被访问
广度优先搜索：从某一顶点出发，在访问该顶点后访问与之相邻的顶点，直到所有顶点均被访问
3.4.3 生成树及最小生成树
生成树：对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图，生成树不唯一
最小生成树：对于连通网来说，边是带权值的，生成树的各边也带权值，因此将生成树的各边的权值总和成为生成树的权，把权值最小的的生成树成为最小生成树
最小生成树的求解算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法
普里姆（Prim）算法：以一个顶点集合U={u0}作为初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直到U=V时为止。
克鲁斯卡尔（Kruskal）算法：假设连通图N=(V，E)，另最小生成树的初始状态是只有n个顶点而无边的非连通图T=(T,{})，图中每个顶点自成一个连通分量，在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边，以此类推，直到T中所有的顶点都在同一连通分量上分支
3.4.4 拓扑排序与关键路径
AOV网：在有向图中，以顶点表示活动，用有向边表示活动之间的优先关系的网，AOV网中不应出现有环（Activity On Vertex Network）
拓扑排序：是AOV网中的所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中，从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在vj之前
AOE网：若在带权有向图G中以顶点表示时间，以有向边表示活动，一边上的权值表示活动持续的时间(Activity On Edge Network)。
关键路径：从源点到汇点的路径中，长度最长的路径
关键活动：关键路径上的所有活动
3.4.5 最短路径
单源点最短路径：指给定带权有向图G和源点V0，求从v0到G中其余各顶点的最短路径（迪杰斯特拉算法）
每队顶点间的最短路径：若每次以一个顶点为源点，重复执行上述算法n次，便可得到网中每一对顶点之间的最短路径（弗洛伊德算法）
3.5 查找
3.5.1 查找的基本概念
查找表（动态、静态）、关键字、平均查找长度
3.5.2 静态查找表的查找方法
顺序查找：从表的一端开始、逐个将记录的关键字和给定值比较，若匹配则查找成功，若一直未找到，则失败；查找长度：（n+1）/2
折半查找：对于有序序列，首先将查找元素的关键字值与表中间位置上记录的关键字进行比较，若成功，则查找成功，若key>中间值，则说明待查记录只可能在后半个子表中，下一步应该在后半个子表中进行查找，key<中间值类似；查找长度log2(n+1)-1
分块查找：首先将表分成若干块，每一块的关键字不一定有序，但块之间是有序的，即后一块的记录大于前一块的记录，此外还建立了索引表；查找过程分两步：第一步在索引表中确定待查记录所在的快，第二步在块中顺序查找查找长度（n/s+s）/2+1
3.5.3 动态查找表
动态查找表：表格结构本身在查找过程中动态生成
二叉排序树：又称为二叉查找树，若左子树非空，则均小于根结点，若右子树非空，则均大于根结点，左右子树本身为二叉排序树
二叉排序树查找：二叉排序树非空时，将给定值与根结点的值进行比较，若成功，这查找成功，若不成功，视其与根结点的比较选择查找范围，若一直未查找成功，则失败
平衡二叉树：左右子树均为平衡二叉树；左右子树的高度差不超过1
m_树：树中每个节点最多有m棵子树；若根结点不是叶子结点，则最少有两棵子树；除根结点外的所有非终端节点最少有m/2棵子树；所有非终端节点包含指向子树根结点的指针，关键字和节点中关键字的个数；所有叶子结点均出现在同一层，并且不带信息。
3.5.4 哈希表
哈希表比较方式：通过计算一个以记录的关键字为自变量的函数，来得到该记录的存储地址，所以在哈希表中进行查找操作时，需要同一哈希函数计算得到待查记录的存储地址，然后到相应的储存单元去获得有关信息再判定查找是否成功
哈希函数的构造方法：直接定址法、数据分析发、平方取中法、折叠法、随机数法和除留余数法
解决冲突的方法：开放地址法
哈希表查找：哈希表查找时，用与存入元素时相同的哈希函数和冲突处理方法计算得到待查记录的储存地址，然后到相应的存储单元获得有关信息在判定查找是否成功；虽然哈希表在关键字和记录的存储位置之间监理了直接映射，但由于冲突的产生，该过程仍然是一个给定值和关键字进行比较的过程；比较关键字的个数取决于哈希函数、处理冲突的方法和哈希表的装填因子
3.6 排序
3.6.1 排序的基本概念
内部排序：待排记录全部存在内存中进行排序的过程
外部排序：排序过程中需要对外存进行访问的排序过程
3.6.2 简单排序
直接插入排序：在插入第i个记录时，原记录已经排好序，这时将该记录插入到对应位置上，然后其后的记录向后移动
冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若出现逆序这交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直到所有的记录比较完毕为止，此时最大的记录被交换到第n个记录的位置上，然后进行第二趟冒泡排序，对前面的n-1个记录进行重复操作。时间复杂度n2
简单选择排序：通过n-i在次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i等于n时所有记录有序排列
3.6.3 希尔排序
基本思想：现将整个待排记录序列分割成若干个子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序
3.6.4 快速排序
基本思想：通过一趟排序将待排的记录划分成独立的两部分，成为前半区和后半区，其中，前半区记录的关键字均不大于后半区记录的关键字，然后分别对着两部分记录继续进行快速排序，从而使整个排列有序
3.6.5 堆排序
基本思想：对一组待排序记录的关键字，首先按堆的定义排列成一个序列，从而可以输出堆顶的最大关键字，然后将剩余的关键字在调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止
3.6.6 归并排序
归并：将两个或两个以上的有序文件合并成一个新的有序文件
实现方法：将一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，得到n/2个长度为2或者1的有序文件，在归并，重复，知道最后形成包含n个记录的有序文件为止
3.6.7 基数排序
基本思想：设立r个队列，队列编号分别为0......r-1，首先按最低有效位的值把n个关键字分配到这r个队列中，然后按照队列编号从小到大将各队列中的关键字依次收集起来，接着在依次低有效位的值把刚收集起来的关键字分配到r个队列中；重复以上步骤，知道按照最高有效为分配和收集，这样就得到一个从小大道有序的关键字序列。
3.6.8 内部排序方法小结
若排序的记录数目n较小，可采用直接插入排序和简单选择排序
若待排序记录按照关键字基本有序，宜采用直接插入排序或冒泡【】排序
若n很大且关键字的位数较少时，采用链式基数排序较好
若n较大，则因采用时间复杂度少的排序方法，快速排序、堆排序或归并排序
3.6.9 外部排序
外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序过程中内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换
一般采用归并排序，分两个阶段：第一个阶段，把文件中的记录分段读入内存，利用某种内部排序方法对记录段进行排序并输出到外存的另一个 文件中，在新文件中形成许多有序的记录段，成为归并段；第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟的归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止
