总结了一下数据结构算法的非常基础的知识，帮助到你的话请关注我呀，持续更新中……
第二章 数据结构与算法
2.1 算法
2.1.1算法的基本概念
定义：算法是指对解题方案的准确而完整的描述
特征：
（1）可行性
- 算法的每一个步骤必须能够实现
- 算法的执行要能够达到预期的目的
（2）确定性
- 步骤有明确定义
（3）有穷性
- 有限步骤
（4）用有足够的情报
2.1.2算法设计的基本方法
（1）列举法
（2）归纳法
通过列举少量特殊情况，经过分析，找出一般的关系
（3）递推法
从已知的条件出发逐次推出所要求的各中间结果和最后结果
（4）递归法
将问题逐层分解成简单问题，解决简单问题后沿着分解逆过程逐步综合
- 递归调用
自己调用自己 - 递归分类
直接递归、间接递归
（5）减半递推技术
（类似于闭区间套的构造，二分区间）
（6）回溯法
通过尝试可行的解法，若进行到不可解，回退换别的路线
2.1.3算法复杂度
2.1.3.1 时间复杂度
与 基本运行的次数、问题规模 有关
分析算法工作量
（1）平均性态
各种特定输入下的基本运算的加权平均
（2）最坏情况复杂性
在规模为n时，算法所执行的基本运算的最大次数
2.1.3.2 空间复杂度
指执行这个算法所需要的内存空间
（具体包括：算法程序、输入初始数据、算法执行过程中 所需要占用的空间）
2.2 数据结构的基本概念
2.2.1是什么
定义：指互相有关联的数据元素的集合
例：矩阵、向量
2.2.1.1数据的逻辑结构
（1）表示数据的逻辑信息
（2）表示数据的前后件关系
2.2.1.2数据的存储结构
2.2.2 数据结构的图形表示
- 根结点 ： 没有前件的结点
- 终端结点 ： 没有后件的结点
- 内部节点 ： 不是以上两种的结点
2.2.3 线性结构与非线性结构
- 空数据结构
没有数据元素 - 非空数据结构
1.线性结构
（1）有且只有一个根结点
（2）每一个结点自己多只有一个前件，也最多只有一个后件
2.非线性数据结构
2.3 线性表及其顺序存储结构
2.3.1 线性表的基本概念
由一组数据组成
矩阵也是一个线性表
（一行或一列向量）简单线性表
由若干数据项组成的数据元素–>记录
多个记录构成的线性表 -->文件
线性表中结点的个数n–> 线性表的长度n
2.3.2 线性表的顺序存储结构
线性表的顺序存储特点
（1）线性表的所有存储空间是连续的
（2）线性表中各数据是按逻辑顺序一次存放的
通常定义一个一维数组存放线性表
（一维数组通常定义的比线性表实际长度大一些，以便于对线性表进行运算）
主要的运算：
- 插入
- 删除
- 查找
- 排序
- 分解
- 合并
- 复制
- 逆转
2.3.3顺序表的插入运算
表中插入a,a后元素整体后移，列表长度增加
（插入多于储存空间–>上溢）
2.3.4 顺序表的删除运算
删除表中元素b,b后元素整体上移，列表长度减小
（线性表为空时删除–>下溢）
（b位置<1或>n时，认为不能删除，算法结束）
2.4 栈和队列
2.4.1 栈及其基本运算
2.4.1.1 什么是栈
一种特殊的线性表
基本原则
- 开始执行程序前，建立一个线性表，其初始状态为空
- 当发生调用时，将当前调用的返回点地址插入到线性表的末尾
- 当遇到某个子程序返回时，其返回点地址从线性表的末尾取出（即删除线性表后的一个元素）
定义
栈是限定在一端进行插入和删除的线性表
栈顶
允许插入和删除的一端
栈底
不允许插入和删除的另一端
指针top
指示栈顶的位置
指针bottom
指示栈底的位置
入栈运算
在栈中插入一个元素
退栈运算
从栈中删除一个元素
2.4.1.2 栈的顺序存储及其运算
一维数组S（1：m）为栈的顺序存储空间，（其中m为栈的最大容量）
栈底元素：S（bottom）
栈顶元素：S（top）
top=0 栈空 top=m 栈满
基本运算
（1）入栈运算
判断top是否指向最后一个元素—不为m–top+1—新元素插入top指向位置 》》》否则上溢
（2）退栈运算
判断top是否=0 —不为0—栈顶元素赋给指定变量—top-1
》》》否则下溢
（3）读栈顶运算
判断top是否=0 —不为0—栈顶元素赋给指定变量
》》》否则读不到栈顶元素
2.4.2 队列及其基本运算
(1)什么是队列
定义 ：允许在一端插入、另一端删除的线性表
原则 ： 初始为空、队尾等待、队头执行
“先来先服务”
尾指针rear ： 指向队尾允许被插入的一端
头指针front ：指向排头允许被删除的一端
入队运算：队尾插入
退队运算： 队头删除
(2)循环队列及其运算
在实际应用中，队列的顺序存储结构一般采用循环队列的形式
初始状态为空：rear=front=m
入队运算：判断循环队列是否为满—rear+1—（ rear=m+1时，置rear=1
退队运算：判断循环队列是否为空—front+1—（front=m+1时，置front= 1
队列空 ：s=0
队列满 ：s=1 且 front=rear=m
2.5 线性链表
2.5.1 线性链表的基本概念
（1）线性表的线性存储结构缺点
1.插入语删除的运算效率都很低
2.线性表的存储空间不便于扩充
3.存储空间不便于对存储空间的动态分配
（2）线性表的链式存储结构
存储结点（简称：结点） ：数据结构中的每一个数据结点对应于一个存储单元，这种存储单元叫作~
结点组成：
数据域：用于存放数据元素值
指针域：用于存放指针（指针用于指向该结点的前一个或后一个结点，即前件或后件）
tips：
1.在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的顺序可以不一致，而数据之间的逻辑关系有指针域来确定。
2.链式存储方式既可以用于表示线性结构，也可以用于表示非线性结构。
3.在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。
1. 线性链表
头指针HEAD ： 指向线性表中第一个结点的指针HEAD
HEAD=NULL或0时，称为空表
单线性链表 ： 每个结点只有一个指针域（右指针）
双向链表 ： 每个结点有两个指针
左指针 ： 指向前件
右指针 ： 指向后件
2. 带链的栈
应用： 用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
运算：栈的初始化、入栈、退栈、读栈顶元素
3. 带链的队列
运算：栈的初始化、入栈、退栈
2.5.2 线性链表的基本运算
- 插入
从可利用栈取得一个结点，链接插入前后的结点，实现内存动态分配、不会上溢 - 删除
将数据删除，结点放回可利用栈，不需要移动表的数据元素，只需要改变被删除元素所在结点的前一个结点的指针域即可。 - 合并
- 分解
- 逆转
- 复制
- 排序
- 查找
2.5.3 循环链表
为了克服空表和对第一个节点需要单独考虑的问题（空表和非空表不统一）
循环链表的特点：
（1）增加表头结点，其数据域为任意或者1根据需要来设置，指针域指向线性表的第一个元素的结点。头指针指向表头结点。
（2）最后一个结点的数据域不是空，而是指向表头结点
循环链表的优点：
（1）只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。
（2）由于表头结点的存在，在任何情况下，循环链表至少有一个结点存在，从而使空表与非空表的运算统一。
2.6 树与二叉树
2.6.1 树的基本概念
树是一种简单非线性结构（层次结构）
父结点：每一个结点只有一个前件，这个前件是它的~
根结点： 没有前件的结点
子结点： 每一个结点有多个后件，这个后件是它的~
叶子结点：没有后件的结点
度： 一个结点拥有的后件个数，称为该结点的~
深度：树的最大层次数
2.6.2 二叉树及其基本性质
1.什么是二叉树
（1）非空二叉树只有一个根结点
（2）每一个结点最多有两棵子树，分别称为该数的左子树与右子树。
2.二叉树的基本性质
（1）在二叉树的第k层上，最多有
2
k
?
1
(
k
>
=
1
)
2^{k-1} (k>=1)
2k?1(k>=1)个结点
（2）深度为m的二叉树最多有
2
m
?
1
2^m-1
2m?1 个结点
（3）在任意一颗二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多1个
（4）具有结点的二叉树，其深度至少为
[
l
o
g
2
n
]
+
1
[log_2 n]+1
[log2?n]+1,其中
[
l
o
g
2
n
]
[log_2n]
[log2?n] 表示取
l
o
g
2
n
log_2n
log2?n的整数部分
3.满二叉树与完全二叉树
1）满二叉树
每一层都是满的
2）完全二叉树
只有最后一层只缺少右边的若干结点，其他均满
除上述4条性质外，还有性质：
（5）具有n个结点的完全二叉树的深度为
[
l
o
g
2
n
]
+
1
[log_2 n]+1
[log2?n]+1
2.6.3 二叉树的存储结构
在计算机中，二叉树通常采用链式结构储存
两个后件
2.6.4 二叉树的遍历
二叉树的遍历指不重复的访问二叉树中所有结点。
遍历方法：
1.前序遍历
优先级：根-左-右 FCADBEGHP
2.中序遍历
优先级：左-根-右 ACDBFEHGP
3.后序遍历
优先级： 左-右-根 ADBCHPGEF
2.7 查找技术
2.7.1 顺序查找
只能用顺序查找的情况：
（1）线性表为无序表
（2）有序线性表采用链式存储结构
2.7.2 二分法查找
只适用于顺序存储的有序表
查找顺序：根-左-右
对于长度为n的有序线性表，在最坏情况下，只需要比较
l
o
g
2
n
log_2n
log2?n
次
2.8 排序技术
定义：排序指将一个无序序列整理成按值非递减顺序排列的有序序列
2.8.1 交换类排序法
1.冒泡排序法
相邻元素比较，元素值小的往前交换
2.快速排序法
分割子表，比元素小的移到前面，大的移到后面
2.8.2 插入类排序法
1. 简单插入排序法
将无序序列中个元素依次插入到已经有序的线性表中
2.希尔排序法
将整个无序序列分割成若干小的子序列分别进行插入排序
2.8.3 选择类排序法
1.简单选择排序法
扫描所有的元素，选出最小的元素将它交换到表的最前面
2.堆排序法
堆的定义：
定义1：
{
h
i
>
=
h
2
i
h
i
>
=
h
2
i
+
1
\begin{cases}h_i>=h_{2i}\\h_i>=h_{2i+1} \end{cases}
{hi?>=h2i?hi?>=h2i+1??
定义2：
{
h
i
<
=
h
2
i
h
i
<
=
h
2
i
+
1
\begin{cases}h_i<=h_{2i}\\h_i<=h_{2i+1} \end{cases}
{hi?<=h2i?hi?<=h2i+1??
即，父结点值>=子结点值
原创总结，转载请注明出处qaq
更多章节更新中……