data_struct - decoqt/mywiki GitHub Wiki
#数据结构
【考查目标】 1.掌握数据结构的基本概念、基本原理和基本方法； 2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与 空间复杂度的分析。 3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用 C 或 C++语言设计与实现算法的能力。
##目录
一道选择题，一道大题
####（一）线性表的定义和基本操作 1.1 数据结构：逻辑结构，物理结构，数据运算
- 逻辑结构：线性，非线性，和计算机无关
- 物理结构：
- 顺序结构：放在一起，随机存取
- 链接结构：顺序存取，不会碎片，只能消耗空间
- 索引结构：附加索引表，检索速度快
- 散列结构：受限于散列函数
1.2 算法：特定问题的求解序列
- 特性：有穷性，确定性，可行性，输入，输出
- 评价算法的好坏是：正确性，可读性，健壮性，效率和低存储量需求
- 算法效率的衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度
1.3 线性表：是由n(n≥0)个数据元素组成的有限序列（a,b,c,d,....,z）
- 特点：长度可变，可访问，删除，插入
####（二）线性表的实现
- 顺序表：线性表的顺序存储,可以有动态分配和静态分配
- 单链表:插入,删除(可以使用后插入代替前插入,然后交换元素),查找;带头结点和不带头结点
- 双链表:插入和删除时候注意赋值顺序,先解决未指向的元素
- 循环单链表:判断空得条件
- 循环双链表:
- 静态链表
#####对比
- 存取方式:顺序表随机,链表从头
- 复杂度:插入和删除使用链表,寻找使用顺序表
- 空间分配:链表更为灵活
<a id='stack_and_queue' name=stack_and_queue'> ###2、 栈、队列和数组
两道选择题，重点栈和队列的操作及特征
###（一）栈和队列的基本概念 1.1 受限的线性表 1.2 栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。 1.3 队列： 队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。 1.3.1 顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。 1.3.2 顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。 1.3.3 为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize
（二）栈和队列的顺序存储结构 2.1 顺序栈 2.2 顺序列表 2.3 循环列表： 循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。 解决的方法有： a.另设一个布尔变量以区别队列的空和满； b.少用一个元素，在入队前测试rear在循环意义下加1是否等于front； c.使用一个记数器记录元素总数。 （三）栈和队列的链式存储结构 3.1 链栈：表头操作 3.2 链式队列： 3.3 双端队列：输入受限（出问题，只能是1234全入）输出受限（看前3个位置） （四）栈和队列的应用 4.1 括号匹配，表达式（波兰式） （五）特殊矩阵的压缩存储 5.1数组：存取和修改元素，大小一定 5.2 矩阵的压缩存储：对称，三角，三对角，稀疏（三元组）
3-4道选择题；遍历方式，转换
（一）树的基本概念
1.1 树：递归的数据结构
1.1.1 结点，度，叶子，深度，高度，森林
1.1.2 性质
（二）二叉树
1.二叉树的定义及其主要特征
1.1 二叉树：每个结点至多有两棵子树
1.1.1 满二叉树：高度为h，且有2^h-1个结点的二叉树
1.1.2 完全二叉树：和满二叉树前n个结点一一对应
1.1.3 排序二叉树：左子树的关键字小于根，右子树的关键字大于根
1.1.4 平衡二叉树：任一结点的左子树和右子树的深度之差不超过1
1.2 二叉树性质：
a.非空二叉树上叶子的结点数等于度为2的结点数加1
b.非空二叉树第k层最多2^(k-1)个结点
c.高度为h的二叉树最多2^h-1个结点
d.N个结点的完全二叉树高度为log(N+1)或logN+1
2.二叉树的顺序存储结构和链式存储结构
2.1 顺序存储：完全二叉树适合顺序存储，从数组下标1开始
2.2 链式存储：（lchild,data,rchild）
3.二叉树的遍历
3.1 遍历：先序，中序，后序
3.2 递归和非递归算法
a.先序遍历
void preOrder2(BinTree root) //非递归前序遍历
{
stack<BinTree> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
visit（p）;
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
b.中序遍历
void inOrder2(BinTree root) //非递归中序遍历
{
stack<BinTree> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
visit(p);
s.pop();
p=p->rchild;
}
}
}
c.后序遍历
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶
void postOrder2(BinTree root) //非递归后序遍历
{
stack<BTNode> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //第二次出现在栈顶
{
visit(temp->btnode);
p=NULL;
}
}
}
}
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
void postOrder3(BinTree root) //非递归后序遍历
{
stack<BinTree> s;
BinTree *cur; //当前结点
BinTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
visit(cur); //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
3.3 遍历构造二叉树
3.4 层次遍历：借助队列实现
4.线索二叉树的基本概念和构造
4.1 N个结点会有N+1个空指针
4.2 二叉树的线索化
4.3 线索二叉树的遍历：寻找前驱和后继
（三）树、森林
1.树的存储结构
1.1 双亲表示法：采用连续空间来存储每个结点（data，parent）
1.2 孩子表示法：每个结点的孩子都用单链表链接起来，方便寻找子女，不利寻找双亲
1.3 孩子兄弟表示法：（data,指向结点第一个孩子的指针，指向结点下一个兄弟的指针），方便树转化为二叉树
2.森林与二叉树的转换
2.1 从物理结构来看：树的孩子兄弟表示法和二叉树的二叉链表表示法相同
2.2 树和二叉树转换
2.3 森林转化二叉树
3.树和森林的遍历
3.1 树的遍历：先根遍历（先序），后根遍历（中序）
3.2 森林的遍历：先序遍历，中序遍历
（四）树与二叉树的应用
1.二叉排序树
1.1 查找，插入，构造，删除（3种情况）
2.平衡二叉树
2.1 插入，删除，调整（LL,RR,LR,RL）
2.2 深度为h的平衡树含有的最少结点：0，1，2，4，7，12，20...
3.哈夫曼（Huffman）树和哈夫曼编码
3.1 Huffman树：带权路径长度最小的二叉树
3.2 Huffman树构造：最小的两个权值结点构成二叉树
3.3 Huffman编码：长度最短的二进制前缀编码
3道选择题，可能大题
（一） 图的基本概念 1.1 顶点，边，有向图，无向图，没有空图，简单图，多重图，完全图，子图，连通图，连通分量，强连通图，强连通分量，生成树，生成森林，度，入度，出度，权，网，稠密图，稀疏图，路径，回路，路径长度，距离，有向树 （二） 图的存储及基本操作 1. 邻接矩阵法 1.1使用一位数组存储顶点，二维数组存储边，适合稠密图 typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网} typedef struct ELEM//作为二维数组中的元素出现 { int adj;//标示顶点关系类型，对于无权图用0，1表示。对于带权图，则表示权值。 char *p;//该弧相关信息描述 }ArcCell; typedef struct { int vexs[MAX];//顶点向量（例如结点分别为v1,v2,v3...,在此处输入） ArcCell arcs[MAX][MAX]//邻接表 int vexnum,arcnum;//图的当前顶点数和弧数 GraphKind kind;//图的种类标志 }MGraph； 2. 邻接表法 2.1图中每个顶点建立一个单链表：顶点表顺序存储，边表链式，适合稀疏图 顶点表（data，边表头指针）边表（adjvex，nextvex）  3. 邻接多重表、十字链表(新增考点) 3.1邻接多重表： 顶点表（data，边表头指针）边表(mark,ivex，ilink,jvex,jlink,info）    3.2 十字链表：可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表， 顶点表（data，firstin,firstout）边表（tailvexheadvex,hlink,tlink）  
（三） 图的遍历 1. 深度优先搜索 1.1 从访问顶点v开始，访问v的邻接点w，访问w的邻接点 ；时间复杂度为 O(|V|^2)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。 2. 广度优先搜索 2.1 从访问顶点v开始，依次访问v的邻接顶点，再访问邻接顶点的未访问邻接顶点；时间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。+ |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。 （四） 图的基本应用 1.最小（代价）生成树 1.1 prime 1.2 kruskal 2.最短路径 2.1 Dijkstra 2.2 Floyed-Warshall 3.拓扑排序 3.1无环有向图排序 4. 关键路径 4.1 带权无环有向图最大路径长度的路径
###五、 查找 （一） 查找的基本概念 （二） 顺序查找法 （三） 分块查找法(新增考点) （四） 折半查找法 （五） B 树及其基本操作、B+树的基本概念 （六） 散列（Hash）表 （七） 字符串模式匹配(新增考点) （八） 查找算法的分析及应用
<a id='sort' name=sort'> ###六、 内部排序 （一） 排序的基本概念 1.1 排序：重新排列列表中的元素，使表中元素满足按照关键字递增或递减的关系 1.2 算法稳定性：若key(Ri)=key(Rj),则在排序过程中，Ri和Rj顺序不能改变 1.3 内部排序和外部排序 1.4 复杂度：时间复杂度由比较和移动的次数来决定的 （二） 插入排序 1. 直接插入排序 2. 折半插入排序 （三） 起泡排序（bubble sort） （四） 简单选择排序 （五） 希尔排序（shell sort） （六） 快速排序 （七） 堆排序 （八） 二路归并排序（merge sort） （九） 基数排序 （十） 外部排序 （十一） 各种排序算法的比较
（十二） 排序算法的应用