数据结构

数据结构复习笔记， 包括绪论、线性结构、树形结构、图状结构、查找，包含名词解释、代码、图示，条理清晰、内容详尽，适用于期中期末复习以及书本逻辑梳理。

数据结构

• 线性结构
  • 线性表
    • 实现
      • 顺序表
        • 特点
          • 试用于随机存取等操作
          • 逻辑上相邻的数据元素，其物理次序也是相邻的
            • LOC（ai+1）=LOC（ai）+l
          • 取值效率高 O（1）
        • 操作
          • 定义
            • 存储空间的基地址
            • 当前长度
          • 初始化
            • 分配MAXSIZE的数组空间
              • 分配失败退出
            • 空表长度为0
          • 取值
            • e=L.elem[i-1];
          • 查找
            • 平均移动（n➕1）/2
            • if（L.elem[i]==e） return i+1；
          • 插入
            • i值不合法、存储空间已满
            • for ( j=L.lenth-1; j>=i-1 ; j-- ) L.elem[j+1] = L.elem[j]; L.elem[i-1]=e;
            • L.length++;
            • 平均移动n/2
          • 删除
            • 平均移动（n➖1）/2
            • i值合法
            • for（j=i ; j <=L.length-1 ; j++ ） L.elem[j-1] = L.elem[j];
            • L.length--;
        • 时间复杂度
          • 求表长/取第i个数据元素：O(1)
          • 查找/插入/删除：O(n)
            • 插入移动次数：n/2
            • 删除移动次数
              • (n-1)/2
      • 链表
        • 线性链表/单链表
          • 特点
            • 非随机存取的存储结构
            • 插入和删除效率高 O（1）
          • 操作
            • 定义
              • ElemType data
              • struct LNode *next
            • 初始化
              • L = new LNode
              • L->next = NULL
            • 创建
              • 前插法
                • L=new LNode; L->next = NULL; for(i=0;i<n;i++) { p=new LNode; cin>>p->data; p->next = L->next; L->next=p; }
              • 后插法
                • L=new LNode; L->next = NULL; r=L; //尾指针r指向头结点 for(i=0; i<n; i++) { p=new LNode; cin>>p->data; p->next = NULL; r->next=p; r=p;}
            • 取值
              • while（p && j<i） { p=p->next; ++j;} e=p->data;
            • 查找
              • while(p&&p->data!=e) p=p->next; return p;
            • 插入
              • p=L; while( p &&(j<i-1)) {p=p->next;++j} s=new LNode; s->data=e; s->next=p->next; p->next=s;
            • 删除
              • p=L; while( p->next &&(j<i-1)) {p=p->next;++j} q=p->next; p->next=q->next; delete q;
            • 时间复杂度O(n)
    • 应用
      • 一元多项式的表示和相加
  • 栈和队列
    • 栈
      • 后进先出（仅在表尾进行插删除操作）
        • 实现
          • 顺序栈
            • 非空栈中的栈顶指针始终在栈顶元素的下一个位置上
            • 注意判断栈满和栈空
            • 定义
              • SElemType *base; SElemType *top; int stacksize;
            • 初始化
              • S.top = S.base; S.stacksize = MAXSIZE;
            • 入栈
              • *S.top++=e
            • 出栈
              • e=*--S.top
            • 取栈顶元素
              • return *（S.top-1)
          • 链栈
            • 初始化
              • S=NULL
            • 入栈
              • p = new StackNode; p->data = e ; p->next = S ; S=p;
            • 出栈
              • e = S->data; p = S; S = S->next;
            • 取栈顶元素
              • return S->data
        • 应用
          • 数值转换
          • 表达式求值算法
            • 中缀表达式求值
            • 中缀表达式转换为后缀表达式
            • 后缀表达式求值
    • 队列
      • 先进先出（在表的一端进行插入，在另一端进行删除操作）
        • 实现
          • 循环队列
            • front\rear,非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置
            • 判断满/空
              • 空
                • Q.fornt==Q.rear
              • 满
                • Q.front==(Q.rear+1)%MAxSize
            • 定义
              • QElemType *base; int front; int rear;
            • 初始化
              • Q.base = new QElemType[MAXQSIZE]; Q.front = Q.rear = 0;
            • 求队列长度
              • return(Q.rear-Q.front+MAXSIZE)%MAXSIZE
            • 入队
              • Q.base[Q.rear] = e Q.rear = (Q.rear+1)%MAXQSIZE //队尾指针＋1
            • 出队
              • e=Q.base[Q.front] Q.front = (Q.front+1)%MAXQZSIZE //队头指针＋1
            • 取队头元素
              • return Q.base[Q.front]
          • 链队列
            • 头指针和尾指针
              • 队列为空：头指针和尾指针均指向头节点
            • 定义
              • QElemType data; struct QNode *next；
              • QueuePtr front QueuePtr rear
            • 初始化
              • Q.front = Q.rear = new QNode; Q.front->next = NULL
            • 入队
              • p = new QNode; p->next = NULL; Q.rear->next = p; Q.rear = p
            • 出队
              • p = Q.front->next; e=p.data; Q.front ->next = p->next; if(Q.rear==p) Q.rear = Q.front; delete p;
            • 取队头元素
              • if(Q.front!= Q.rear) return Q.front->next->data
• 树形结构
  • 树
    • 基本术语
      • 结点
        • 根结点
        • 终端结点/叶子
        • 分支结点/内部结点
      • 结点的度
        • 结点拥有的子树数
      • 树的度
        • 树内各结点度的最大值
      • 孩子、双亲、兄弟、堂兄弟
      • 深度
        • 树中节点的最大层次
      • 有序树、无序树
      • 森林
        • m棵互不相交的树的集合
  • 二叉树
    • 定义
      • 每个结点至多只有两棵子树（不存在度大于2的结点），子树次序不能颠倒，有左右之分
      • 5种基本形态
      • 注意：二叉树的度不一定是2
    • 性质
      • 在二叉树第i层上至多有2^(i-1)个结点
      • 深度为k的二叉树至多有2^k-1个结点
      • 任何一棵二叉树，n0=n2+1
        • n=n0+n1+n2=n1+2n2+1
      • 满二叉树
        • 深度为k且有2^k-1个结点
        • 每一层上的结点数都是最大结点数
      • 完全二叉树
        • 具有n个结点的完全二叉树的深度为
        • 对任意结点
    • 存储结构
      • 顺序存储结构
        • 子主题
      • 链式存储结构
        • 在含有n个结点的二叉链表中有n+1个空链域
        • TElemType data; struct BiTNode *lchild,*rchild
    • 应用
      • 遍历二叉树
        • 前序遍历
          • VLR
        • 中序遍历
          • LVR
            • 递归算法
            • 非递归算法
        • 后序遍历
          • LRV
        • 根据遍历序列确定二叉树
          • 已知前序遍历+中序遍历，求后序遍历
            • 前序遍历第一个结点为根结点，中序遍历可断开左右分段
          • 已知后序遍历+中序遍历，求前序遍历
            • 后序遍历最后一个结点是根节点
          • 在二叉树结点的先序、中序、后序遍历中，所有叶子节点的先后顺序相同
          • 前序遍历和中序遍历，得到唯一的一棵二叉树
        • 应用
          • 创建二叉树的存储结构——二叉链表
          • 计算二叉树的深度
      • 线索二叉树
        • 作用
          • 加快查找结点的前驱或后继的速度
        • 特点
        • 二叉树的二叉线索存储表示
          • TElemType data; struct BiThrNode *lchild,*rchild; int LTag,RTag;
        • 前序和后序线索化后，空链域为1； 中序线索化后，空链域为2
        • 线索树的遍历
        • 线索树的创建
  • 树和森林
    • 树的存储结构
      • 双亲表示法
      • 孩子表示法
      • 孩子兄弟表示法
        • 右指针指向兄弟
    • 森林与二叉树的转换
      • 一棵树可转换成唯一的一棵没有右子树的二叉树
    • 树和森林的遍历
      • 树
        • 先根遍历
        • 后根遍历
        • 按层次遍历
        • 以二叉链表做为树的存储结构时，先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历实现
      • 森林
        • 森林的先序
          • 对应二叉树的先序遍历
        • 森林的中序
          • 二叉树的中序遍历
    • 树和森林的遍历
  • 最优二叉树/哈夫曼树
    • 概念
      • 路径长度
        • 路径上的分支数目
      • 树的带权路径长度
    • 特点
      • 具有相同带权结点的哈夫曼树不唯一
      • 哈夫曼树中权越大的叶子离根越近
      • 一颗有n个叶子结点构成的哈夫曼树有2n-1个结点
    • 构造
      • 构造森林全是根
      • 选用两小造新树
      • 删除两小添新人
      • 重复②③剩单根
    • 构造
    • 哈夫曼编码
      • 最优前缀编码
      • 最高n-1层，最多n-1个分支
    • 哈夫曼树的结点个数一定是奇数
  • 应用
    • 利用二叉树求解表达式的值
• 查找
  • 查找的基本概念
    • 查找表
    • 关键字
      • 主关键字、副关键字
    • 查找
    • 动态查找表和静态查找表
    • 性能分析
      • 平均查找长度ASL
  • 查找表
    • 静态查找表
      • 查找元素存在性、检索属性
      • 顺序表的查找
        • 顺序查找（可设置哨兵）
          • 查找时从表的最后开始比较
          • 时间复杂度O(n)
          • 在等概率情况下ASL=(n+1)/2
          • 既适用于顺序结构，也适用于链式结构
      • 有序表的查找
        • 折半查找
          • 适用于采用顺序存储结构的有序表（对线性链表无法有效地查找）
          • 比较次数
            • 成功
              • 路径上的结点数/结点的层次
            • 不成功
              • 路径上内部结点数
          • 性能分析
            • 近似ASL=log(n+1)-1
          • 平均查找长度
      • 分块查找
        • 索引表
          • 表有序或者分块有序（块间有序，块内无序）
          • 确定块的查找可以顺序/折半查找，块中只能顺序查找
        • 性能分析
          • 表长为n, 每一块的记录个数为s, 则ASL=log(n/s+1)+s/2
          • 与n、s都有关，可能效率不如折半查找
          • 插入和删除比较容易
    • 动态查找表
      • 查找过程中进行插入/删除操作
      • 二叉排序树
        • 性质
          • 左子树若不为空，左子树上所有结点的值均小于它的根节点的值
          • 右子树若不为空，右子树上所有结点的值均大于它的根节点的值
          • 它的左、右子树也分别为二叉排序树
          • 中序遍历一棵二叉排序树可得到一个结点值递增的有序序列
        • 查找
          • 提高查找效率
            • 平衡二叉树AVL
              • 性质
                • 左子树和右子树均为平衡二叉树，且左右子树深度之差的绝对值不超过1.
              • 平衡因子
                • 左子树深度-右子树深度
                • AVL树只能为1、0、-1
              • 平衡树的生成（调整规律）
                • 单向右旋平衡处理
                • 单向左旋平衡处理
                • 双向旋转（先左后右）平衡处理
                • 先右后左平衡处理
              • 查找性能分析
                • 时间复杂度O(logn)
        • 插入
          • 新插入的结点一定是新添加的叶子结点
        • 创建
        • 删除
          • 三种情况
    • 哈希表
      • 对应关系：哈希函数
        • 函数值以同等概率取其值域的每个值
      • 术语
        • 散列函数和散列地址
        • 散列表
        • 冲突和同义词
      • 构造方法
        • 直接定址法
          • Hash(key) = a key + b
          • 关键字/关键字的线性函数值
        • 除数留余法
          • Hash(key) = key mod p
          • p选择质数或者不包含小于20的质因数的合数
        • 考虑的因素
      • 处理冲突的方法
        • 开放定址法
          • Hi=(H(key)+di)%m(散列表表长)
            • 线性探测再散列
              • di=1,2,3,...
              • 易发生二次聚集
              • S»1/2(1+1/(1-a))
            • 二次探测再散列
              • di=1²，-1²，2²,-2²...
            • 伪随机探测再散列
              • di=伪随机数序列
        • 链地址法
          • m个哈希地址就设m个单链表
          • 前插法效率高
          • 更适合表长不确定的情况
      • 查找效率分析
        • ASL取决于
          • 哈希函数
          • 处理冲突的方法
          • 装填因子
            • α=表中填入的记录数/哈希表的长度
            • 平均查找长度依赖于装填因子
      • 几点结论
        • 链地址法优于开放地址法
          • 除留余数法作哈希函数优于其他类型函数
• 图状结构
  • 基本术语
    • 子图
    • 无向完全图、有向完全图
      • 无向图
        • n(n-1)/2条边
      • 有向图
        • n(n-1)条边
    • 稀疏图
    • 网
      • 带权的图
    • 邻接点、依附、相关联
    • 度
      • 顶点的度
        • 和顶点v相关联的边的数目TD(v)
      • 有向图
        • 入度
        • 出度
    • 路径和路径长度
    • 简单路径
      • 顶点不重复出现的路径
    • 回路或环
    • 连通
      • 连通图
        • 图中任意两个顶点间都连通
      • 连通分量
        • 无向图中的极大连通子图
      • 强连通图
        • 有向图中，每两点间都可以相互到达
      • 强连通分量
        • 有向图的极大连通子图
      • 连通图的生成树
        • 一个连通图的生成树是一个极小连通子图
          • 含有图中全部顶点，但只有足以构成一棵树的n-1条边
  • 存储结构
    • 邻接矩阵
      • 对于无向图，顶点Vi的度是邻接矩阵中第i行/列的元素之和
      • 对于有向图，第i行元素的和是顶点Vi的出度OD(Vi), 第j列元素的和是顶点Vj的入度ID(Vj)
      • 创建
        • 顶点表
        • 邻接矩阵
          • VerTexType vex[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum
      • 图
        • 初始化邻接矩阵，使每个权值初始化为0
      • 网
        • 初始化邻接矩阵，使每个权值初始化为极大值
      • 优缺点
        • 优点
          • 便于判断两个顶点之间是否有边
          • 便于计算各个顶点的度
        • 缺点
          • 不便于增加和删除顶点
          • 不便于统计边的数目
          • 空间复杂度高
          • 时间复杂度O(n*n)
        • 适用于稀疏图
    • 邻接表
      • 每个顶点建立一个单链表
      • 若无向图有n个顶点，e条边，则邻接表需要n个头结点和2e个表结点
      • 为方便计算有向图中顶点的入度，可以建立一个有向图的逆邻接表
      • 优缺点
        • 优点
          • 便于增加和删除顶点
          • 便于统计边的数目
          • 时间复杂度、空间复杂度 O(n+e)
        • 缺点
          • 不便于判断两个顶点之间是否有边
          • 不便于计算各个顶点的度
  • 图的遍历
    • 辅助数组visited[n] false=0;true=1
    • 深度优先搜索(DFS)
      • 类似于树的先根遍历
      • 时间复杂度
        • 邻接矩阵 O(n*n)
        • 当用邻接表存储图时 O(n+e)
      • 利用递归/栈来实现
    • 广度优先搜索(BFS)
      • 类似于树的按层次遍历
      • 时间复杂度
        • 和DFS相同
      • 利用队列
  • 图的应用
    • 最小生成树
      • 生成树
        • 一个图可以有许多棵不同的生成树
        • 特点
          • 顶点个数与图的顶点个数相同
          • 是图的极小连通子图
        • 一个有n个顶点的连通图的生成树有n-1条边
        • 在生成树中再加一条边必然形成回路
      • 构造
        • Prim算法
          • 归并顶点
          • 时间复杂度O(n*n)
            • 试用于求边稠密的网
        • Kruskal算法
          • 归并边
          • 时间复杂度O(eloge)
            • 试用于求边稀疏的网
    • 最短路径
      • 从某个源点到其余各顶点的最短路径
        • Dijkstra算法
          • 过程
            • 初始化
            • 选择
            • 更新
          • 时间复杂度O(n*n)
      • 每一对顶点之间的最短路径
    • 拓扑排序
      • 由某个集合上的一个偏序得到集合上的一个全序
      • AOV网
        • 顶点表示活动，弧表示活动间的优先关系的有向图
      • 如何进行拓扑排序
        • 在有向图中选一个没有前驱的顶点且输出
        • 从图中删除该顶点和所有以它为尾的弧
        • 重复以上两步，直至全部顶点均已输出，或者当前不存在无前驱的顶点为止。后一种情况说明有向图中有环。
        • 也可利用DFS,按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列
    • 关键路径
      • 路径长度最长的路径，即为完成工程的最短时间
      • e(i)
        • 活动ai的最早开始时间
      • l(i)
        • 活动ai最迟必须开始的时间
      • 关键活动
        • e(i)=l(i)
        • 关键路径上的活动都是关键活动（提前完成非关键活动不能并不能加快工程进度）
      • ve(i)
        • 事件的最早发生时间
        • 计算时应从ve(0)向前递推
      • vl(i)
        • 事件的最迟发生时间
        • 计算时从vl(n-1)=ve(n-1)向前后递推
      • 求关键路径的算法
• 绪论
  • 数据
    • 基本单位
      • 数据元素
        • 由数据项组成
    • 不可分割的最小单位
      • 数据项
  • 数据结构
    • 逻辑结构
      • 数据元素之间的逻辑关系
        • 线性结构
          • 线性表
          • 栈和队列
          • 字符串
        • 非线性结构
          • 集合结构
          • 树结构
          • 图结构
    • 物理结构
      • 在计算机中存储结构
        • 顺序存储结构
        • 链式存储结构
  • 算法
    • 定义
      • 指令的有序序列
    • 特性
      • 有穷性、确定性、可行性
    • 评价标准
    • 效率度量
      • 时间复杂度
        • 常量阶 O（1）
          • 与问题规模n无关的常数
        • 线性阶 O（n）
        • 平方阶 O（n²）
          • 由最深层循环内的基本语句的频度决定
        • 立方阶O（n³）
        • 对数阶（log₂ⁿ）
      • 空间复杂度