1.数据结构与算法（基础讲解笔记）

喔，整理完基础笔记之后，会再整理一份数据结构的python描述笔记。

1. 数据结构与算法

1.1 算法

• 可行性、确定性、有穷性、拥有足够信息
• 列举、归纳、递推、递归、减半递推、回溯法
• 时间复杂度
  • 平均性态

  A(n)=\sum_{x\in D_n}p(x)t(x)
  

  • 最坏情况复杂性

  W(n)= \max_{x \in D_n} \ \{t(x)\}
  

  • t(x)表示算法在输入x时的运行次数；p(x)表示x出现的基本概率
• 空间复杂性

1.2 数据结构的基本概念

• 逻辑结构、存储结构、数据结构的运算

1.2.1 什么是数据结构

• 数据结构：相互关联的数据元素的集合
• 逻辑结构：前后件关系
• 存储结构：数据的逻辑结构在计算机空间中的存放形式，也称数据的物理结构

1.2.2 数据结构的图形表示

• 根结点：没有前件
• 终端结点：叶子结点，没有后件
• 中间结点：称为内部结点

1.2.3 线性结构与非线性结构

• 线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件；在线性结构中插入或者删除一个结点后还是线性结构。
• 非线性结构：

1.3 线性表及其顺序存储结构

举个例子，在sql中的学生信息关系表就是一种线性表。

• 顺序存储：线性表中的每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。

ADR(a_i) = ADR(a_1)+(i-1)k

在顺序存储结构中就是一个萝卜一个坑，如果要插入元素到某个位置，那么后面的元素先一一后退一个坑位，然后才能将新的元素插进去，因此效率极其低。
删除元素是，该元素后面的元素一一前进一个坑位。

注意上溢错误————就是坑位满员了，插不进去新元素，会使算法直接结束。

线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的。

1.4 栈和队列

1.4.1 栈

• 栈是一种特殊的线性表。

• 一端是封闭的，不允许进行插入与删除元素；另一端是开口的，允许插入与删除元素。这种限定一端进行插入与删除的线性表就是栈。

• 允许插入和删除的一端是栈顶，另一端是栈底。

• “先进后出”“记忆功能”

• 比如：子弹夹就是一种栈的结构。

• 入栈：首先判断指针是否只想存储空间的最后一个位置，是，则栈空间已满； 然后栈顶指针进一；最后将新元素插入栈顶指针指向的位置。

• 退栈：先判断栈顶指针是否为0；然后将栈顶元素付给一个指定的变量；最后将栈顶指针退一。

• 读栈顶元素：先判断栈顶指针是否为0；然后将栈顶元素付给一个指定的变量。

1.4.2 队列及其基本运算

• 指允许在一端进行插入、而在另一端进行删除的线性表。
• 允许插入的一端称为队尾，一个队尾指针指向队尾元素；允许删除的一端称为排头（对头）。
• “先进先出”

1.5 线性链表

1.5.1 线性链表的基本概念

线性表的顺序存储具有以下缺点：

• 插入与删除的效率低下
• 线性表的存储空间不便于扩充
• 线性表的顺序存储不适合存储空间的动态分配

在链式存储方式中，节点：数据域&指针域。指针指向改结点的前一个或后一个结点。

• 链式存储中可以不连续
• 存储顺序与逻辑顺序可以不一致
• 逻辑结构由指针域确定
• 可以是线性可以是非线性结构

1.线性链表

• 线性表的链式存储
• 双向链表

2.带链的栈
3.带链的队列

1.5.2 线性链表的基本运算

• 查找元素、插入元素、删除元素

1.5.3 循环列表

克服线性单链表的空表与非空表的运算不统一的缺点。定义了一个表头结点。

循环队列的长度：（rear-front+Queuesize）% Queuesize

1.6 树与二叉树

1.6.1 树的基本概念

• 树是一种简单的非线性结构
• 树具有明显的层次结构
• 根结点、父结点、子结点、叶子结点
• 结点的度：该结点拥有后件的个数。
• 树的度：所有结点中最大的数称为树的度。
• 树的结点树：树种所有结点的度之和+1

1.6.2 二叉树及其基本性质

• 二叉树：是一种很有用的非线性结构。每个一个结点最多有两颗子树，最大度为2.

• 在第K层，最多有$2^{k-1}$2k−1个结点。

• 深度为m的二叉树最多有$2^{m}-1$2m−1个结点。

• 在任意一颗二叉树中，度为0的结点（叶子结点）总比度为2的结点多一个。

• 具有n个结点的二叉树，其深度至少为 $[\log_2 n]+1$[log2​n]+1。其中[ ]的意思是取整数部分。

• 满二叉树和完全二叉树

  • 满二叉树：就是除了根结点和叶子结点其他结点的度均为2。
  • 在第K层，有$2^{k-1}$2k−1个结点。深度为m的满二叉树有$2^{m}-1$2m−1个结点。

• 完全二叉树：

1.7 查找

1.7.1 顺序查找

• 无序线性表：只能顺序查找
• 链式存储的有序线性表：只能顺序查找

1.7.2 二分查找

• 只适用于顺序存储的有序表
• 最坏$\log_2 n$log2​n

1.8 排序

• 这里不作特殊说明的结构均默认是对顺序存储的线性表而言

1.8.1 交换类排序法（冒泡、快速）

1.冒泡排序法

• 将相邻的数据元素交换，从前往后，将最大的元素换到最后一个位置；从后往前，将最小的元素换到第一个位置；重复这两个过程。
• 这个过程就像最大者沉到底部，最小者冒泡到上面，因此称冒泡法或者下沉法。
• 线性表的长度n，最坏的次数是:正反都需要$\frac{n}{2}$2n​次遍历。进行 $\frac{n(n-1)}{2}$2n(n−1)​ 次比较。

2.快速排序

• 最坏进行 $\frac{n(n-1)}{2}$2n(n−1)​次比较。

1.8.2 插入类排序

• 插入排序：将无序序列中的元素依次插入到已有的有序的线性表中。

1.简单插入排序

• 将第j个元素放到变量T中，然后从有序子表（第j-1个元素）开始，往前逐个与T做比较，将大于T的元素依次向后移动一个位置，直到发现一个元素不大于T，就将T插入到刚移除的空位置上面去，有序子表的长度就变为了J。
• 最坏情况同冒泡排序。

2.希尔排序法

• 将整个无序序列分割成若干个子序列分别进行插入排序。
• 将相隔某个增量h的元素构成一个子序列。然后逐次减少这个增量，最后当h减少到1时，再进行最后一次插入排序，排序就完成了。
• 增量序列一般取 $h_t=\frac{n}{2^k}$ht​=2kn​（k=1,2,3,…,[ $\log_2{n}$log2​n ] ）其中n为待排序序列的长度。

1.8.3 选择类排序

1.简单选择排序法

• 扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同种办法，直到子表为空。
• 扫描n次，最坏进行 $\frac{n(n-1)}{2}$2n(n−1)​次比较。

2.堆排序法

1.9 时间复杂度

1.9.1 常见的时间复杂度

O(1) < O(logn) < O(n) < O($nlog_2n$nlog2​n) < O($n^2$n2) < O($n^3$n3) < O($2^n$2n) < O($n!$n!) < O($n^n$nn)

1.9.2 各种排序的时间复杂度

名称	最坏比较次数	时间复杂度
冒泡（bubble）	$\frac{n(n-1)}{2}$2n(n−1)​	O($n^2$n2)
快速（）		O($n^2$n2)
直接插入（straight insertion）		O($n^2$n2)
希尔（）	与增量序列选取方式有关，本文提到的方式	O($n^{1.5}$n1.5)
直接选择（simple select）	$\frac{n(n-1)}{2}$2n(n−1)​	O($n^2$n2)
堆排序（）		O($nlog_2n$nlog2​n)