01.数据结构导论一览.md
数据结构一览
# 时间复杂度
O（1）<O（log2n）＜O（n）<O（n^2）<O（n^3）<O（n^4）<O（2^n）
# 线性表的基本运算
若线性表中最常用的操作是求表长和读表元素，则顺序表和链表中，较节省时间的是顺序表
# 顺序表(类似数组)
插入
1）移动次数：当 i=n+1 时，需要比较和移动元素的次数为 0。当 i=1 时，需要比较和移动元素的次数是 n。一般情况下元素比较和移动的次数为 n-i+1 次。
2）平均移动次数：n/2。
3）时间复杂度：O（n）
删除
1）移动次数：最少元素移动次数为 0。最多（最坏情况下）元素移动次数为 n-1。一般情况下元素比较和移动的次数为 n-i 次。
2）平均移动次数：(n-1)/2。
3）时间复杂度：O（n）
定位
比较的平均时间复杂度为 O（n），求表长和读表元素算法的时间复杂度为 O(1)，平均查找长度为（n+1）/2。
# 单链表(对象、套节点)
在一个单链表中，已知指针 q 指向指针 p 所指结点的前驱结点，则删除*p 结点的操作语句是 q->next=p->next。
初始化
typedef struct node
{ DataType data;
struct node *next;
}
node ，*LinkList;
InitiateLinkList（）
LinkList InitiateLinkList（ ） //建立一个空的单链表
{ LinkList head; //头指针
head=malloc（sizeof（node））; //动态构建一个结点，并定义为头结点
head->next=NULL; return head;
}
在带头结点的单链表 L 中，第一个数据元素结点的指针为 L->next。 设有一个单链表，若结点的指针域为 next，则指针 p 所指的结点为最后一个结点的条件是 p->next==NULL。工作指针 p->next 为 NULL 时，说明已经走到了表的尾部，这时已完成对所有结点的访问。
插入 p 指向的新结点的操作
设 r 指向单链表的最后一个结点，要在最一个结点之后插入 s 所指的结点，需执行的语句序列是 r->next=s;r=s;r->next=NULL。
将一个由指针 q 指向的结点插在单链表中由指针 p 所指向的结点之后的操作是：q->next=p->next;p->next=q;
# 循环链表
在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。
1）只有头指针 head：
a.判断 P 所指结点为尾结点的条件：p->next==head；b.判断指针 P 所指结点为首结点的条件：p==rear->next->next；c.判断链表是否为空的条件：head->next==head。
2）有头指针 head 和尾指针 rear（说明：rear-＞next 指向头结点 head）。
在带有头结点的循环链表中，尾指针为 rear，判断指针 P 所指结点为首结点的条件是p==rear->next->next，首节点就是头节点后的第一个数据节点
只有尾指针 rear：
1）删除表首结点的操作可表示为：p=rear->next->next;rear->next->next =p->next;free（p）; 2）已知尾指针的单向循环链表在第一个结点后面插入一个新结点的时间复杂度为 O（1）
# 双向循环链表
每个结点有两个指针，next 指针指向直接后继结点；prior 指针指向直接前驱结点。
带头结点的双向循环链表 L 为空的条件：（L->next==L）&&（L->prior==L）。
p 指向待删结点，删除*p 的操作：p->prior->next=p->next;p->next->prior=p->prior;free（p）
p 所指结点的后面插入一个结点*t 的操作:t->prior=p;t->next=p->next;p->next->prior=t;p->next=t;。
# 栈的实现
# 顺序表方式(用类似数组)
当栈为空，栈顶下标值 top=0，如果此时做出栈运算，则产生“下溢”。当栈中的数据元素已经填满了，如果再进行进桟操作，会发生“上溢”
进栈
Int Push（SeqStk *stk，DataType x）//若栈未满，元素 x 进栈 stk 中，否则提示出错信息
{if（stk->top==maxsize-1） //判断找是否满
{ error（“栈已满”）;return 0;}
else { stk->top++; //栈未满，top 值加 1
stk->data[stk->top]=x; //元素 x 进桟
return 1;}}
出栈
Int Pop(SeqStk *stk)
{ if（EmptyStack（stk）） //判断是否下溢（栈空）
{ error（“下溢”）;return 0;}
else //未下溢，栈顶元素出栈
{ stk->top--; //top 值减 1
return 1;}}
// 也可以理解为：原栈顶的下一个结点成为新的栈顶，即 top=top->next;
取栈顶元素
DataType GetTop（SeqStk*stk）//取栈顶数据元素，栈顶数据元素逋过参数返回
if(EmptyStack（stk）)return NULLData; //栈空，返回 NULLData
else return stk->data[stk->top]; //返回栈顶数据元素 }
# 链表方式
栈的链表实现称为链栈，链栈可以用带头结点的单链表来实现。LS 指向链表的头结点，首结点是栈顶结点，LS->next 指向栈顶结点，尾结点为栈底结点。
出栈操作始终是栈顶结点出栈，即删除头结点之后的结点：原栈顶的下一个结点成为新的栈顶，即top=top->next
链栈由于采用了链表的方式作为存储方式，各结点通过链与链的连接组成栈，由于每个结点空间都是动态分配产生，链栈不用预先考虑容量的大小。
入栈时，使用 malloc 申请空间后，用指针相连接，所以节点个数没有限制；但是出栈时，如果栈中的元素个数为 0，则不能继续出栈，所以需要判断当前栈是否为空。综上，链表不需要判满，只需要判定是否为空即可。
链栈 LS 中，Ls 一>next 指向栈顶结点，则新结点*P 入栈的操作为：P 一>next=LS 一>next；和 LS->next=p；。
# 二叉树
性质
二叉树的第 i（i≥1）层上至多有 2^(i-1)个结点。
深度为 h（h≥1）的二叉树中至多含有 2^h -1 个结点。
若在任意一棵二叉树中，若度数为 0 的结点（叶结点）个数为 n0，度数为 2 的结点个数为 n0=n2+1。
具有 n 个结点的完全二叉树深为\\( \log_2{n} \\)+1
如果将一棵有 n 个结点的完全二叉树按层编号，按层编号是指：将一棵二叉树中的所有 n 个结点按从第一层到最大层，每层从左到右的顺序依次标记为 1，2，...，n。则对任一编号为 i（1≤i≤n）的结点 A 有:
1）当 i=1 时，该结点 A 为根，它无双亲结点。当 i>1 时，该结点 A 的双亲结点的编号为⌊i/2⌋。
2）若 2i>n，则结点 A 既无左孩子，也无右孩子；否则 A 的左孩子的编号为 2i；
3）若 2i+1>n，则结点 A 无右孩子；否则，A 的右孩子的编号为 2i+1。
递归遍历
（1）先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。
（2）中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。
（3）后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。
已知先序遍历和中序遍历，画出二叉树，并写出后序遍历的顺序；已知后序遍历和中序遍历，画出二叉树，并写出先序遍历的顺序。 中序遍历可知道哪些节点在根节点的左边，哪些节点在根节点的右边。先序遍历或后序遍历可以知道根节点是什么
# 图的遍历
深度优先搜索类似于树的先序遍历。借助栈。邻接矩阵作为存储结构的图的时间复杂度：O（n^2），n 为图的顶点数。采用邻接表作为存储结构的图的时间复杂度：O（n+e），n 为图的顶点数，e 为图的边数
广度优先搜索类似于树的按层次遍历的过程。借助队列。
# 查找
顺序表查找，查找成功的平均查找次数为：（n+1）/2，查找不成功查找次数为 n+1。
有序表的二分查找。例如：已知一个有序表为(15，19，30，33，49，50，65，88，93，126，164)，当二分查找值为 126 的元素时，检索成功需进行的比较次数为（3 次）。
二叉排序树：给键值序列，生成的二叉排序树。
# 4 种排序方法
在待排记录有序的前提下，直接插入排序和冒泡排序时间效率最高。
堆排序：对于 n 个元素的关键字序列{k1，k2，...，kn}，当且仅当满足关系 ki≤k2i 且 k_i≤k_2i+1（2i≤n，2i+1≤n）称其为最小堆，反之则为最大堆。
设记录数为 n，冒泡排序算法在最好情况下所作的比较次数为 n-1。
插入排序：直接插入排序，是稳定的，时间复杂度为 O（n^2），空间复杂度为 O（1），即只需要一个记录的辅助空间。
交换排序：
1）冒泡排序：是稳定的，时间复杂度为 O（n^2）。
2）快速排序：是不稳定的，平均时间性能最佳，其时间复杂度为 O（nlog2n）。但在最坏情况下，近似于 O（n^2）。对较大的 n 值效果较好。
选择排序：
1）直接选择排序：是不稳定的，时间复杂度为 O（n^2），但不适宜于 n 较大的情况。
2）堆排序：是不稳定的，平均时间、最坏情况下时间复杂度都为 O（nlog2n），最大优点是只需要一个记录大小的辅助空间。
归并排序：
1）有序序列的合并：此算法的执行时间为 O（n-h+1）。
2）二路归并排序：是稳定的，时间复杂度为 O（nlog2n）。在 n 较大时，归并排序的时间性能优于堆排序，但它所需的辅助存储量较多。
# 代码示例
直接插入排序
function insertSort() {
const arr = [ 3, 1, 4, 5, 6, 7, 8];
for (let i = 1; i < arr.length; i++) {
let next = arr[i];
let insertIndex = i - 1;
while (insertIndex >= 0 && arr[insertIndex] > next) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex + 1] = next;
}
}
冒泡排序
function bubbleSort() {
const arr = [ 3, 1, 4, 5, 6, 7, 8];
let total = arr.length; // 7个
for (let i = 0; i < total - 1; i++) {
for (let j = 0; j < total - i - 1; j++) {
const current = arr[j];
const next = arr[j + 1];
if (current > next) {
arr[j] = next;
arr[j + 1] = current
}
}
}
}
选择排序
function selectionSort() {
const arr = [3, 1, 4, 5, 6, 7, 8];
const total = arr.length;
for (let i = 0; i < total; i++) {
let min = i;
const minValue = arr[min];
for (let j = i + 1; j < total; j++) {
if (arr[j] < minValue) {
min = j
}
}
// 一直选择最小的放在最前面
if (min !== i) {
arr[i] = arr[min];
arr[min] = minValue;
}
}
}
快速排序
const arr = [3, 1, 4, 5, 6, 7, 8];
const left = 0
const hight = 6
function quickSort(arr, low, high) {
if (low < high) {
let pi = findPartition(arr, low, high)
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
function findPartition(arr, low, high) {
let partyQueen = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < partyQueen) {
i++;
const lessPartyQueen = arr[i]
arr[i] = arr[j]
arr[j] = lessPartyQueen
}
}
const tempPartyQueenIndex = i + 1
const originPartyQueen = arr[tempPartyQueenIndex]
arr[tempPartyQueenIndex] = arr[high]
arr[high] = originPartyQueen
return tempPartyQueenIndex
}