数据结构学习笔记
1.概念
数据：
成都创新互联公司是一家专业的成都网站建设公司，我们专注成都做网站、成都网站制作、
成都外贸网站建设、网络营销、企业网站建设，
友情链接，
广告投放为企业客户提供一站式建站解决方案，能带给客户新的互联网理念。从网站结构的规划UI设计到用户体验提高，创新互联力求做到尽善尽美。
数据元素：
数据项：
关键字：
数据对象：
数据结构：
内容：
性质：
形式定义：（D，R）
D：数据元素有限集
R：D上的关系有限集
D = { a , b , c , d }
R = { ( a , b ) , ( a , c ) , ( b , d ) }
数据类型：（值 + 操作）DT
抽象数据类型：（数据结构 + 操作）ADT
数据结构
其结构上的操作
可用（D，S，P）表示
D：数据对象
S：D上关系集
P：对D的操作集
ADT Complex{ //ADT 类型名{
D = { e1 , e2 }, // 数据对象
R = {< e1 , e2 >}, // 数据关系
InitComplex( &Z , v1 , v2 ) // 基本操作
}ADT Complex // }ADT 类型名
算法：指令的有限序列
算法分析:
2.算法分析
算法分析-----大"O"符号
若两个正常数 c , n0 ,对任意n >= n0 都有T(n)<= c × f(n), 则称T(n) = O(f(n))
若
A
(
n
)
=
a
m
n
m
+
a
m
−
1
n
m
−
1
+
.
.
.
a
0
A(n) = a_mn^m + a_{m-1}n^{m-1} + ...a_0
A(n)=amnm+am−1nm−1+...a0
是一个m次多项式,则A(n) = O(n^m).
算法执行时间 = Σ(基本操作(i)的执行次数x基本操作(i)的执行时间)
算法空间复杂度: 算法执行所需空间的增长率
- S(n) = O(g(n))
- 若所需额外空间是常数,称"原地工作"
- 程序本身所占空间
- 输入数据所占空间
- 辅助变量所占空间
3.线性表
定义:
- n(n >= 0)个具有相同类型的数据元素的有限序列
长度:
特征:
- 唯一"第一元素"
- 唯一"最后元素"
- 除最后元素,均有唯一后继
- 出第一元素,均有唯一前驱
- 线性表的基地址即起始地址
线性表链式存储
任意存储单元存放线性表元素,无连续性(淡化"位序")
便于插入,删除的操作
逻辑相邻,物理未必相邻,即"链式存储"
节点:
单链表:表节点中只包含一个指针域
- 头指针: 指向链表第一个节点的指针
- 头节点: 通常在单链表前加一节点
- 首节点: 第一个元素节点
- 尾节点: 最后一个元素节点
查找（按位查找）
- 删除单链表元素时，只要改前节点指针即可，但要注意释放不用的内存
- 由于顺序存取结构，为找第i个元素，必须先找到第i-1个元素
templateT linklist::GetElem(int i){
P = Head->next; //工作指针（首节点），也可头节点
j = 1; //计数器，初始为1（首节点），若头节点，为0
while(p && j< i){ //顺位工作指针，直至i
P = P->next;
j++;
}
if(!P || j >i){ //空表或i<0或i>表长
throw "位置" //查找位置不合理
}else{
return P->data;
}
} //O(n)
插入
头插法：每次新申请节点放在“头节点”后
templatevoid LinkList::CreatList(int n){
for(int i = 1;i<= n;i++){
s = new Node;
cin>>s->data;
s->next = head->next
head->next = s;
}
}
尾插法：保证工作指针指向最后节点，方便插入
templatevoid LinkList::CreatList(int n){
Node*P,*S; //工作指针，P指向尾节点
P = Head;
for(int i =1，i<= n;i++){
s = new Node;
cin>>s->data;
s->next = p->next; //新节点链插入表尾
p->next = s;
p = s;
}
}
4.链表
循环链表：终点指针指向head
双向链表
单链中每个节点再设置一个指向其前驱节点的指针域
静态链表
用数组描述链表，包括：
- data域：存放数据
- next域：存放该元素后继所在数组下标
- 其中0单位的next存放首元素下标
缺点：
- 没有解决连续存储分配带来的表长难以确定
- 其还需要维护一个空闲链
- 不可随机存储
间接寻址
- 存储不相邻，但地址存储位置相邻，可随机存取，但仍存在表厂难以确定的情况
5.顺序存储和链式存储
顺序存储
链式存储
6.栈
- 栈顶指向an的上方
- 后进先出
- 出入栈要检查上下是否溢出
常用操作
- InitStack(&S) //初始化
- DestroyStack(&S) //销毁
- Push(&S,e) //入栈
- Pop(&S) //出栈
- GetTop(S) //获取栈顶元素
- StackEmpty(S) //测栈空
- ClearStack(&S) //清空栈
顺序栈
templateclass SqStack{
Private:
T *base; //栈底指针
int top; //栈顶
int stackSize; //栈容量
public:...
}
链栈
不带头结点
templatestruct Node{
T data;
Node*next;
}
顺序栈vs链栈
时间：出入栈均为常数级
时间：
链栈特点
- 无栈满问题，空间可扩充
- 插入与删除仅在栈顶执行
- 链栈栈顶在链头
- 适合多栈操作
7.队列
基本操作
- T* base; //存储空间基址
- int front; //队头指针
- int rear; //队尾指针
- queueSize; //队容量
- InitQueue(&Q) //初始化
- DestroyQueue(&Q) //销毁
- GetQueue(Q) //获取头元素
- EnQueue(&Q,e) //入队
- DeQueue(&Q,e) //出队
- QueueEmpty() //判断队空
- QueueFull() //判断队满
- ClearQueue(); //清空队列
- QueueTranverse(); //遍历队列
**特点: **
- 有头空节点
- 只允许在表的一端进行插入，而在另一端删除元素的线性表
- 先进先出
- 假溢出：数组低端根据“先进先出”产生前空闲空间，但后端已满的现象，通过循环队列（头尾相接）解决
链队
仅在表头删除和表尾插入的单链表
循环队列
循环栈
8.串相关
概念
- 串：零或多个字符组成，有限序列，一串字符，即S1S2…Sn
- 空串：零个字符，即NULL
- 空格串：空格组成的串
- 字串：主串中任意连续字符组成
- 空串是任何串的子串
串匹配
- 结果：字串第一字符在主串中的位序
- KMP：仅子串移动，O(n+m)
- BF：主，子串均多次回溯，最好O(n+m)。最差O(n*m)
9.矩阵压缩存放
类型
- 对称矩阵：Aij = Aji
- 三角矩阵：带宽、奇
- 对角矩阵
- 稀疏矩阵:e<= 0.05 e = 非零元个数/元素个数
- 三对角矩阵
10.广义表
- 数据元素有相对次序
- 长度：最外层包含元素个数
- 深度：括号重数
- 可以是一个递归表，深度无穷，长度有限
- 可分为
- 表头Head（）=
- 表尾：Tail（） = （ ， ，）
- 表头可为原子或表
- 表尾一定是表
11.树
- n个有限数据元素集合
- n = 0时，为空树
- 根节点：先祖，无前驱
- 子树：根节点子树
- 节点的度：某节点所拥有的子树个数
- 树的度：树中各节点度的大值
- 叶子节点：终端节点，无子代
- 分支节点：非终端节点
- 孩子，双亲，兄弟
- 祖先，后代
- 路径长度：经过的边数
- 层数：根节点为1
- 有序树，无序树：若一棵树中节点子树从左向右有次序，为有序树
- 森林：树的集合，可谓0
- Tree = （root，F）
二叉树
根的元素，分叉为左子树，右子树。子树数量<=2（大二分叉）
满二叉树
完全二叉树
- 在满二叉树中，从最后节点开始，连续去任意个节点，即为一颗完全二叉树
平衡二叉树
- AVL
- |左子树深度 - 右子树深度|<= 1
- 平衡因子：左子树高度 - 右子树高度 = -1 or 0 or -1
- 按中序遍历会是一个从小到大的排列
性质
- 一棵非空二叉树的第i层上支队2^(i-1)个节点
- 深度为k的而擦函数中，最多有2^k-1个节点
- 对于非空二叉树，若叶子节点数n0，度为2的节点度为n2，则n0 = n2 +1
- 具有n个节点的完全而擦函数的深度为log2n +1
- 对于具有n个节点而擦函数，编号1~n；对于任意的i
- if（i >1）,则i的节点的双亲节点序号为（i/2）
- if（i = 1），则i为根节点
- if（2i<= n）,则i的节点的左孩子节点序号为2i
- if（2i >n）,则i的节点无左孩子
- if（2i + 1<= n）,则i的节点的右孩子节点序号为2i+1
- if（2i + 1 >n ）,则i的节点无右孩子
- 二叉树的顺序存储结构一般仅存“完全二叉树”
- 三叉链表：祖宗节点、左子树、数据、右子树
遍历
- 先序：根节点访问先后
- 中序：默认从左至右
- 后序
- 层序遍历：第一层开始，逐层访问，从上至下，从左至右
线索二叉树
- 线索：序列中的第一个（前驱）和后一个（后继）
- 包含“线索”的存储结构，“线索链表”
- 若有左孩子，则无前驱指向（二占一）
- 若有右孩子，则无后继指向（二占一）
赫夫曼（哈夫曼）树
- 节点路径长度：节点间分支个数
- 树的路径长度：根到每个节点路径长度和
- 树的带权路径长度：书中所有叶子节点的带权路径之和WPL
- WPL最小的二叉树为“最优二叉树”，“哈夫曼树”
- 权值越大的叶子节点越靠近根节点
- 只有度为0（叶子）或2（分支）的节点
赫夫曼编码
- 等长编码：一组对象的二进制位串的长度相等
- 前缀编码：一组编码中任一编码都不是其他任何一个编码的前缀
- 规定赫夫曼树左分支代表0.右分支为1，从根节点到每个叶子节点所经过的路径组成01序列为叶子编码
树转二叉树：
树遍历
- 先根遍历：先访问根节点，再依次访问各子树
- 后根遍历：先访问子树
- 树不动
森林遍历
- 先序遍历：先访问森林中第一棵树的根节点，即依次从左至右队森林中每颗树进行先根遍历
- 中序遍历：依次从左至右队森林中每一颗树进行后根遍历
12.图
- Graph = （V，E），V表示顶点，E表示边集
- 无向图，有向图，无向网，有向网
邻接点：
有向完全图：
- 任意两顶点间都有方向互相反的两条弧相连接
- n(n-1)条边
无向完全图
- 任意两顶点间只有一条边相连接
- [n(n-1)]/2条边
- 稠密图，稀疏图
度：
权：
子图：
连通图：
连通分量：
强连通图：
图生成树
- n个顶点，e条边
- 其中n个顶点和n-1条边构成一个极小的连通子图为生成树
图的存储
- 邻阶矩阵
- A[ i ] [ j ] = 1 (vi,vj)有边
- A[ i ] [ j ] = 0 (vi,vj)无边
- 无向图形成矩阵是对称矩阵
- 矩阵中同一元素行和列”1“的大量数为度数
- 网图即代换”1“的值
- 邻接表
- 无向图：i的度为边表中节点个数
- 有向图：节点数为出度数（逆表中为入度）
- 网图中添加域量赋权
图的遍历
关节点
重连通图
最小生成树
- 无向连通图生成树不唯一（WPL相同）
- 有且仅有n-1条边
- Prim：点扩散式
- kruskal：小组织连接成大组织
最短路径
- 一个源点到其余点
- 此路径上，必定只含一条弧，且权值最小
- Dijkstra：a-b,a-c,a-d（点->线->面）
- Floyd:成邻接矩阵，所有可能路径
DAG图
AOV网与拓扑算法
关键路径：
- 始终点时间大的路径
- e[ i ] = l[ i ]的路径
- e[ i ]活动最早开始时间
- l[ i ]活动最晚开始时间
13.查找
有序折半查找
- 有序、顺序存储
- 流程：
- 查找值与中间元素关键字比较：
- 相等则成功
- 小于则左半区继续折半查找（不包括中点）
- 大于则右半区
- T(n) = O(log2n)
哨兵顺序查找
动态查找
- 又叫树表查找
- 流程：
- 用二叉树排序树（BST）
- 左子树上节点均小于根节点
- 左子树上节点均大于根节点
- 左右子树也遵循上述规则
- 最好Tn = O(log2n)
- 最坏Tn = O(n)
14.哈希函数
散列函数
特点：
- 函数简单,速度快
- 计算出的地址，应在哈希地址集中大致均匀分布
- 解决冲突方案
常用哈希函数
- 直接定址
- Hash(k) = a * k + b
- 线性哈希
- 不会发生冲突
- 除留余数
- Hash(k) = k mod p
- p一般选质数
- 若表长为m，则要求p<= m
- 一定有冲突
- 乘余取整
- 数字分析
- 平方取中
- 折叠
处理冲突
- 开放定址
- 关键字所得hash地址冲突，则区寻找下一个空的哈希地址
- 线性：向后探测是否为空
- 二次探测：12,-12,22,-22···左右平方探测
- 双哈希：伪随机数列
- 建立一个公共溢出区
哈希表查找分析
- 比较次数取决于产生冲突的多少
- 冲突产生因素：
- 哈希函数是否平均
- 处理冲突的方法
- 填满因子α = 元素个数/表长
- 哈希表平均查找长度仅取决于填满因子
15.排序
- 稳定性：相同关键码元素间位置关系是否受排序影响
- 内排序（仅在内存）
- 外排序
- 单键排序
- 多键排序
- 是否基于比较
内排序
三大经典排序方法
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 均稳定
快速排序
- 枢轴
- 左右排形成类似于”树“的结构
- 时间复杂度：O(nlog2n) ~ O(n^2)
- 不稳定
- 最坏情况时就是冒泡排序
- 辅助存储空间：O(log2n) ~ O(n)
堆排序
- 定义满足Ki< K2i且Ki< K(2i+1)
- 或定义满足Ki >K2i且Ki >K(2i+1)
- 是一种具有完全二叉树的性质：根节点小于孩子节点
16.表达式
前缀表达式
- 构造树，从右向左取第一个最低级运算作为根节点
- 左右子树再重复操作
后缀表达式
- 最近的两数与最近的符号进行运算
- 重复操作
hash地址冲突，则区寻找下一个空的哈希地址- 线性：向后探测是否为空
- 二次探测：12,-12,22,-22···左右平方探测
- 双哈希：伪随机数列
- 建立一个公共溢出区
哈希表查找分析
- 比较次数取决于产生冲突的多少
- 冲突产生因素：
- 哈希函数是否平均
- 处理冲突的方法
- 填满因子α = 元素个数/表长
- 哈希表平均查找长度仅取决于填满因子
15.排序
- 稳定性：相同关键码元素间位置关系是否受排序影响
- 内排序（仅在内存）
- 外排序
- 单键排序
- 多键排序
- 是否基于比较
内排序
三大经典排序方法
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 均稳定
快速排序
- 枢轴
- 左右排形成类似于”树“的结构
- 时间复杂度：O(nlog2n) ~ O(n^2)
- 不稳定
- 最坏情况时就是冒泡排序
- 辅助存储空间：O(log2n) ~ O(n)
堆排序
- 定义满足Ki< K2i且Ki< K(2i+1)
- 或定义满足Ki >K2i且Ki >K(2i+1)
- 是一种具有完全二叉树的性质：根节点小于孩子节点
16.表达式
前缀表达式
- 构造树，从右向左取第一个最低级运算作为根节点
- 左右子树再重复操作
后缀表达式
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：数据结构笔记-创新互联
链接分享：
http://cdkjz.cn/article/djopds.html
