01数据结构

这是一个关于01数据结构的思维导图，包含逻辑结构、卡特兰数、物理结构、 数据运算等。

数据结构 （存在关系的数据元素的集合）

• 逻辑结构
  • 线性结构
    • 一般线性表
      • 顺序表示
        • 顺序表
          • 用地址连续的存储单元存储表中元素
            • 特点
              • 逻辑顺序与物理顺序一致
              • 插入与删除的代价极高
              • 随机存取
            • 插入
              • 最好情况：表尾插入O(n) 最坏情况：表头插入，所有元素都要后移O(n)
              • for(int j=L. length; j>=i; j--)//将第1个元素及之后的元素后移 L. data[j]=L. data[j-1]; L. data[i-1]=e;//在位置i处放入e L. length++;//线性表长度加1
            • 删除
              • 最好情况，O(1) 最坏情况，O(n)
              • e=L. data[i-1];//将被删除的元素赋值给e for(int j=i; j<L. length;j++);//将第i个位置后的元素前移 L. data[j-1]=L. data[j]; L. length--;//线性表长度减1
            • 按值查找
              • 最好情况，O(1) 最坏情况，O(n)
              • for(i=0; i<L. length;i++) if(L. data[i]==e) return i+1;//因为表下标从0开始存储，下标为i的元素值等于e,返回其位序i+1 return 0;//退出循环，说明查找失败
      • 链式表示
        • 逻辑上相邻，不要求物理上相邻，通过链建立逻辑关系
        • 优点
          • 插入和删除不需要移动元素，修改指针即可
        • 缺点
          • 无法随机存取
        • 主要分类
          • 单链表
            • 存储单元存放元素信息以及一个指向后续的指针
            • 定义法
              • type struct LNoed｛ ElemType data; Struct LNoed *next; ｝LNode,*Llinklist;
            • 插入
              • 头插法
                • S->data=x； S->next=L->next; //L为头指针 L->next=S；
                  • L为头指针
              • 尾插法
                • S->data=x; r->next=S;. //r为表尾指针 r=S; //移动r到新的尾结点上，为下一次尾插做准备
            • 删除
              • p-q-x 删除q
                • q=p->next； p->next=q->next； free（q）；
            • 按值查找
              • lnode *p=l->next；//指针p指向头结点的下一个结点 while（p！=null&&p！=待查的值） p=p->next； return p；
          • 双链表
            • 与单链表相比多了一个指向前一结点的pre指针
              • 定义法
                • type struct LNoed｛ ElemType data; Struct LNoed *pre,*next; ｝LNode,*Llinklist;
              • 插入
                • ① s->next=p->next； ② p->next->pre=s； ③ s->pre=p； ④ p->next=s；
                  • ①②必须在④之前
              • 删除
                • p→next=q→next； q→next→pre=p； free（q）；
          • 循环链表
            • 循环单链表
            • 循环双链表
          • 静态链表
            • 这里的指针是指下一个元素的数组下标
    • 广义表
      • head
        • 取出位于表头部的元素，或者子表
      • tail
        • 取出表尾的元素
    • 受限制的线性表
      • 栈
        • 特点
          • 后进先出
          • 只允许在栈顶插入或删除
          • 不可以随便读取中间某个元素
        • 分类
          • 顺序栈
            • 基本操作
              • 判栈空 bool StackEmpty(SqStack S){ if(S.top==-1) //栈空 return true; else //不空 return false; ｝
              • 进栈 bool Push(SqStack &S,ElemType x){ if(S.top==MaxSize-1) //栈满，报错 return false; S. data[++S. top]=x; //指针先加1，再入栈 return true; ｝
              • 出栈 bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) //栈空，报错 return false; x=S. data[S. top--]; //先出栈，指针再减1 return true; }
              • 读栈顶元素 bool GetTop(SqStack S,ElemType &x) { if(S.top==-1）//栈空，报错 return false; x=S. data[S. top]; //x记录栈顶元素 return true; ｝
            • 共享栈
              • 两个顺序栈共享一个栈空间，达到节约存储空间的目的
                • 栈A的指针top0指向栈顶，栈B的指针top1指向栈顶 元素入栈A：top0先加一再入栈 元素入栈B：top1先减一再入栈 top1-top0=1时栈满 top0==-1时栈A空 top1==Maxsize时栈B空
          • 链栈
            • 没有头结点 Lhead指向栈顶元素 链栈便于插入与删除
        • 栈的应用
          • 括号匹配
          • 表达式求值
          • 递归调用
      • 队列
        • 特点
          • 先进先出
          • 不允许随便读取中间某个元素
        • 分类
          • 队列的顺序存储
            • 顺序队列
              • 进队
                • rear+1，再赋值
              • 出队
                • 先出队，再front+1
            • 循环队列
              • 队空
                • front==rear
              • 队满
                • （rear+1）%Maxsize==front
              • 当前元素个数
                • （rear-front+maxsize）%maxsize
              • 入队
                • 入队 bool EnQueue(SqQueue &Q, ElemType x){ if((Q. rear+1)MaxSize==Q. front) return false; //队满则报错 Q. data[Q. rear]=x; //没空则插在尾部 Q. rear=(Q. rear+1)MaxSize; //队尾指针加1取模 return true; ｝
              • 出队
                • 出队 bool DeQueue(SqQueue &Q, ElemType &x){ if(Q. rear==Q. front) return false; //队空则报错 x=Q. data[Q. front]; Q. front=(Q. front+1)%MaxSize; //队头指针加1取模 return true; }
          • 队列的链式存储
            • 本质是带有队头指针和队尾指针的单链表
              • 尾进头出
              • 判队空 bool IsEmpty(LinkQueue Q){ if(Q.front==Q. rear) return true; else return false; ｝
              • 入队 void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; //创建新结点，插入到链尾 Q. rear->next=s; Q. rear=s; ｝
              • 出队 bool DeQueue(LinkQueue &Q, ElemType &x){ if(Q.front==Q. rear) return false;//空队 LinkNode *p=Q. front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q. rear=Q. front; //若原队列中只有一个结点，删除后变空 free(p); return true; ｝
          • 双端队列
            • 输出受限
              • 只允许一端输出
            • 输入受限
              • 只允许一端输入
        • 队列的应用
          • 层次遍历
          • 缓冲区
      • 串
        • 模式匹配
          • 简单匹配
          • kmp算法
            • next值求法
              • ① 前两个next值为0，1
              • ② 后续next值通过前缀，后缀匹配，取最长成功匹配的串长+1
          • kmp算法的优化
            • nextval值求法
              • 根据next值向前找编号相同的，其next值即为待求的nextval值，若已有nextval值则更新
    • 线性表的推广
      • 数组
        • 存储方式
          • 行优先
          • 列优先
          • 特殊矩阵的压缩存储
            • 上三角矩阵 下三角矩阵
            • 对称矩阵
            • 三对角矩阵
              • 行优先
                • 存放在一维数组 k=2i+j-3
            • 稀疏矩阵
              • 三元组存储法
                • （行，列，data）
              • 十字链表存储法
  • 非线性结构
    • 集合
      • 元素同属于一个集合
    • 树结构
      • 树
        • 树的性质
          • 是一种递归的数据结构
          • 是一种分层结构
          • ① 树的结点数 = 所有结点的度数之和 + 1
          • ② 度为m的树在第i层最多有 mⁱ⁻¹ 个结点
          • ③ 高为h的m叉树最多有(mʰ -1) / (m-1)个结点
          • ④ 有n个结点的x叉树的最小高度 ┍ logₓ （n(m-1）+1）┒
      • 二叉树
        • 性质
          • n₀=n₂+1
          • n=n₀+n₁+n₂
            • n=1+n₁+2n₂
          • 高为h的二叉树最多有2ʰ-1个结点
        • 分类
          • 空二叉树
          • 满二叉树
          • 完全二叉树
            • 结点与编号一一对应
            • 度为1的结点只能有一个或者没有
              • 此结点决定了完全二叉树结点总数的奇偶性
            • 具有n个结点的完全二叉树的树高
              • ┍ log₂（n+1）┒ 向上取整
              • ┕ log₂n┙ +1 向下取整
          • 二叉排序树
            • 左小右大
          • 平衡二叉树
            • 左右子树高度差不超过 1
        • 二叉树的存储结构
          • 顺序存储
            • 完全二叉树
            • 满二叉树
          • 链式存储
            • 有n个结点的二叉链表 含有 n+1 个空链域
        • 线索二叉树
          • 线索二叉树是个物理结构
          • 空链域用来存放指向前序或者后续的线索
          • 分类
            • 中序线索二叉树
            • 先序线索二叉树
            • 后序线索二叉树
        • 二叉树的遍历
          • 先序遍历
            • 根左右
          • 中序遍历
            • 左根右
          • 后序遍历
            • 左右根
      • 树的存储结构
        • 双亲表示法
        • 孩子表示法
        • 孩子兄弟表示法
          • 二叉树表示法
            • 易于查找结点的孩子
            • 找双亲比较麻烦
            • type struct csnode｛ elemtype data； struct csnode *liftchild，*rightbro；//定义孩子和右兄弟指针 ｝csnode，*cstree；
      • 树，森林，二叉树的转换
        • 左孩子右兄弟
          • 根的左边孩子结点作为新树中根的孩子结点， 根的右兄弟变为新树中根的孩子
      • 树与二叉树的应用
        • 哈夫曼树/哈树
          • 带权路径长度WPL最小的二叉树
          • 特点
            • ① 左小右大型 或者 左大右小型
            • ② 每次选取两个权值最小的合并，其和作为新根的权值
            • ③ 哈树的形态不唯一，但是WPL值永远是最小的
            • ④ 哈树中不存在度为1点结点
              • 因为哈树是两两合并出来的
          • 哈夫曼编码
            • 可变长
              • 二进制位字符长度可变
            • 固定长
              • 二进制位字符长度固定
        • 并查集
          • 是一种集合（逻辑结构）
          • 顺序存储的双亲表示法的树
          • 并
          • 查
          • 并查集的应用
            • 判断图的连通性
              • 遍历无向图的所有边， 每遍历到一条边，就将其两顶点并到一个集合， 以此所有的连通的顶点都会在一个集合，而不连通的不在此集合里
    • 图结构
      • 图的定义
        • 顶点集V与边集E构成
      • 图的分类
        • 无向图
          • 无向图的全部顶点的度的和=边数×2
        • 有向图
          • 弧尾 → 弧头
          • 有向图的全部顶点的入度之和=出度之和
        • 简单图
          • 不存在重复的边 不存在顶点到自身的边
        • 完全图
          • 无向完全图
            • n(n-1)/2 条边
          • 有向完全图
            • 两顶点间存在方向相反的两条弧
        • 子图
        • 连通
          • 无向图中
            • 任意两顶点都是连通的
            • 极大连通子图称为连通分量
        • 强连通
          • 有向图中
            • 任意两点是强连通的
        • 简单路径与简单回路
          • 顶点不重复出现→简单路径
          • 除了第一个与最后一个点，其他的点不重复出现→简单回路
        • 生成树
          • 包含全顶点的极小连通子图
            • 既要图连通又要边数最少
        • 注意
          • 非连通情况下边数最多:
            • 由n-个顶点构成一个完全图，此时再加入一个点即为非连通图
          • 有向图强连通情况下边数最少:
            • 至少n条边，构成环路
        • 其他图
          • 稀疏图
            • |E| = |V|*log|V|时
          • 稠密图
      • 图的存储
        • 邻接矩阵法
          • 存储
            • 无向图
            • 有向图
          • 空间复杂度O(n²) → n为顶点数
          • 更适合存稠密图
        • 邻接表法
          • 存储
            • 无向图
              • 空间复杂度(V+2E)
                • 因为边会出现2次
            • 有向图
              • 空间复杂度(V+E)
        • 十字链表法
          • 有向图的链式存储
        • 多重表法
          • 无向图的链式存储
      • 图的遍历
        • 广度优先
          • 类似于层次遍历
        • 深度优先
          • 对一个点一直深挖
        • 对于无向图，调用DFS或BFS的次数 = 此图的连通分量个数
      • 图的应用
        • ① 最小生成树
          • ① 包含所有顶点
          • ② 包含尽可能少的边
          • ③ 权值和唯一
          • ④ 边数 = 顶点数-1
          • ⑤ 树形态不唯一
        • ② Prim算法
          • 算法过程
            • ① 任选一点
            • ② 寻找权值最小
            • ③ 依次相连，含所有点，尽可能少的边
          • 适用于求解边稠密的图的最小生成树
          • 时间复杂度
            • O(V²)
        • ③ 克鲁斯卡尔算法
          • 在整个图中找最小的边，优先选取，并要求包括所有顶点
          • 用到并查集
          • 适用于边少顶点多的图
          • 时间复杂度
            • Elog₂E
        • ④ 最短路径问题
          • ① Dijkstra算法
            • 算法过程
              • 每轮记录
                • ① 每一步的路径以及路径的总权值
                • ② 最短路径集合
            • 解决单源路径问题
              • 无权图，有权图都可
            • 时间复杂度
              • 邻接矩阵
                • O(V²)
              • 邻接表
                • O(V²)
          • ② Floyd算法
            • 带权图
            • 算法过程
              • 不断更新矩阵
              • 如:A，A²，A³……
              • A的角标代表中继结点
            • 时间复杂度
              • O(V³)
        • ⑤ 关键路径问题
          • 手算过程
            • ① 求事件Vk的最早发生时间
              • 从前向后直接算
            • ② 求事件Vl的最迟发生时间
              • 从后向前算，减去最小的权值
            • ③ 求活动的最早发生时间e
              • 弧尾的事件的最早发生时间
            • ④ 求活动的最迟发生时间l
              • 弧头的事件的最迟发生时间 - 此活动的权值
            • ⑤ 用活动最迟l减去活动最早e，为0的活动即为关键活动，其所连顶点即为所求
• 卡特兰数
  • 适用于：
    • 栈
      • n个元素入栈，求出栈序列个数
    • 二叉树
      • n个结点能构成多少种不同形状的二叉树
    • 括号匹配
      • n对括号，有多少种括号匹配序列
  • 使用卡特兰数的前提
    • 栈和二叉树不能有其他限制
      • 比如要求：出栈第一个数为1，此时不能用卡特兰数计算
• 两大方法
  • 查找
    • 顺序查找
      • 适用于
        • 顺序表
        • 链表
    • 折半查找
      • 适用于
        • 有序的顺序表
      • 比较方法
        • 一边倒
      • 要求线性表能随机存储 因此，仅适用于顺序存储结构
      • 时间复杂度 O(log₂n)
    • 分块查找
      • 块内无序，块间有序
      • 长为n的表分为b块，每块有s个记录 s=√n，平均查找长度取最小值√n+1
      • 平均查找长ASL = (S²+2S+n)/2S
        • 顺序
    • 树形查找
      • 二叉排序树
        • 左小右大
        • 构造
        • 插入
        • 删除
      • 平衡二叉树
        • 左右子树高度差不超过1 或者为空树
        • 调整
          • LL型
            • 右旋一次
          • RR型
            • 左旋一次
          • LR型
            • 先左旋再右旋
          • RL型
            • 先右旋再左旋
        • 操作
          • 插入
          • 删除
          • 查找
      • 红黑树
        • 定义
          • ① 左根右
          • ② 根叶黑
          • ③ 不红红
          • ④ 黑路同
        • 先调整再着色
    • 查找长
      • ASL成功 = (Σ笫几层×结点数)/总数
      • ASL失败 = (Σ第几层×结点空链域数)/总数
    • B树&B+树
      • B树
        • m叉B树
          • 支持随机查找
          • 特点
            • ① 每结点至多有m个子树， 至多m-1个关键字
            • ③ 除了根结点外，所有非叶结点至少有┍ m/2 ┒棵子树 至少有┍ m/2 ┒一1 个关键字
            • ④ 叶子结点在同一层，即空链域层
            • ② 若根结点不是叶子，则至少有2个子树
          • 树高
          • 查找
            • 结点内来用顺序查找，折半查找
          • 插入
          • 删除
            • ① 直接删
            • ② 兄弟够借
              • ① 左兄弟够借
                • 用左兄弟的最右结点代替自己，自己补到缺位上
              • ② 右兄弟够借
                • 用右兄弟的最左结点代替自己，自己补到缺位上
            • ③ 兄弟不够借
              • 合并
      • B+树
        • m叉B+树 特点
          • ① 每个关键字对应一棵子树
          • ② ┍ m/2 ┒≤ n ≤ m
          • ③ 叶结点包含了全部关键字且包含信息
          • ④ 非叶仅起索引作用
          • ⑤ 支持顺序查找，随机查找
    • 散列表
      • 查找效率取决于比较次数
      • 散列函数
        • ①直接定址法
        • ②除留余数法
          • H（key）= key%P
            • P:不大于表长的最大素数
        • ③数字分析法
        • ④平方取中法
      • 散列查找
        • 装填因子α =记录数/表长
      • 处理冲突的方法
        • 开放定址法
          • ①线性探测
            • 后移补位
            • 手算线性探测
              • ASL失败= 分子/分母
                • 分子:将表序号后移，直到遇到空位，记录后移的次数再+1 将P个元素内的所有记录的(后移的次数再+1)以及空位数(若空位在P内)
                • 分母:P
          • ②平方探测
            • 解决冲突
              • （ 余数+ d¡ ）%表长
              • d¡ = 0²，1²，-1²，2²，-2² ......
          • ③双散列
          • ④伪随机
        • 拉链法
  • 排序
    • 大多数排序只适用于顺序存储的线性表
    • 内部排序
      • 插入排序
        • 直接插入排序
          • 适用于顺序和链式存储的线性表
          • 选择出一个作为哨兵
            • 大元素放哨兵后面，小元素放哨兵前面
            • 完成后选择刚刚排好的那个元素作为新哨兵
          • 时间复杂度
            • O(n²)
          • 稳定
        • 折半插入排序
          • 适用于顺序存储的线性表
          • 时间复杂度
            • O(n²)
        • 希尔排序
          • 适用于顺序存储的线性表
          • 时间复杂度
            • O(n²)
          • 不稳定
      • 交换排序
        • 冒泡排序
          • 时间复杂度
            • O(n²)
          • 稳定
        • 快速排序
          • 选基准，①从后向前与基准比较，②从前向后与基准比较，①②交替进行
          • 时间复杂度
            • 最好 O(nlog₂n)
            • 最坏 O(n²)
            • 平均 O(nlog₂n)
          • 不稳定
      • 选择排序
        • 简单选择排序
          • 时间复杂度 O(n²)
          • 不稳定
        • 堆排序
          • 适用于关键字多的情况
          • 堆可视为完全二叉树
            • 建立过程
              • 从最后一个非叶节点开始，判断是否符合堆的要求
          • 时间复杂度 O(nlog₂n)
          • 不稳定
      • 基数排序
        • 时间效率与初始序列无关
        • 最高位优先/最低位优先
        • 排序年月日
        • 时间复杂度 O(d(n+r))
        • 稳定
      • 归并排序
        • 时间复杂度 O(nlog₂n)
        • 稳定
    • 外部排序
      • 外部排序总时间 = 内部排序时间 + 外存读写时间 + 内部归并时间
      • 对于r个初始归并段，做x路归并
        • 树高h - 1 = ┍ logₓr ┒= 归并趟数
      • 败者树
        • 可视为完全二叉树
        • 每轮比较，胜者继续向上，一直到根结点
        • k路归并的败者树深度为：┍ log₂k ┒
      • 置换选择排序
        • 算法过程
          • ①从待排序序列中选取一定数量元素，放入工作区
          • ②在工作区中选择最小数放入归并段，且miniMax改为此数
          • ③保证下一次放入归并段的数要比miniMax值要大
          • ④当工作区中没有比miniMax更大的数时，则第一个归并段生成
      • 最佳归并
• 数据运算
  • 四则运算
    • 加 +
    • 减 -
    • 乘 *
    • 除 /
  • 运算 （a为数据）
    • 异或 ^ 相同为0，相异为1
    • 逻辑与 && 同1为1，否则为0
    • 逻辑或 || 全0才0，否则为1
    • 先自增再赋值 ++a
    • 先赋值再自增 a++
    • 先自减再赋值 --a
    • 先赋值再自减 a--
    • 取余 %a
    • 取反 !a
• 物理结构
  • 索引存储
    • 不仅存储元素，还要为其构建索引表，索引表包含多个索引项 修改数据的同时也要修改索引表
  • 链式存储
    • 元素在逻辑上相邻，但是在物理上不一定相邻
  • 顺序存储
    • 逻辑上相邻的元素在物理上存储也是相邻的
  • 散列储存 （哈希）
    • 根据关键字直接计算存储地址

数据结构 （存在关系的数据元素的集合）

• 逻辑结构
  • 线性结构
    • 一般线性表
      • 顺序表示
        • 顺序表
          • 用地址连续的存储单元存储表中元素
            • 特点
              • 逻辑顺序与物理顺序一致
              • 插入与删除的代价极高
              • 随机存取
            • 插入
              • 最好情况：表尾插入O(n) 最坏情况：表头插入，所有元素都要后移O(n)
              • for(int j=L. length; j>=i; j--)//将第1个元素及之后的元素后移 L. data[j]=L. data[j-1]; L. data[i-1]=e;//在位置i处放入e L. length++;//线性表长度加1
            • 删除
              • 最好情况，O(1) 最坏情况，O(n)
              • e=L. data[i-1];//将被删除的元素赋值给e for(int j=i; j<L. length;j++);//将第i个位置后的元素前移 L. data[j-1]=L. data[j]; L. length--;//线性表长度减1
            • 按值查找
              • 最好情况，O(1) 最坏情况，O(n)
              • for(i=0; i<L. length;i++) if(L. data[i]==e) return i+1;//因为表下标从0开始存储，下标为i的元素值等于e,返回其位序i+1 return 0;//退出循环，说明查找失败
      • 链式表示
        • 逻辑上相邻，不要求物理上相邻，通过链建立逻辑关系
        • 优点
          • 插入和删除不需要移动元素，修改指针即可
        • 缺点
          • 无法随机存取
        • 主要分类
          • 单链表
            • 存储单元存放元素信息以及一个指向后续的指针
            • 定义法
              • type struct LNoed｛ ElemType data; Struct LNoed *next; ｝LNode,*Llinklist;
            • 插入
              • 头插法
                • S->data=x； S->next=L->next; //L为头指针 L->next=S；
                  • L为头指针
              • 尾插法
                • S->data=x; r->next=S;. //r为表尾指针 r=S; //移动r到新的尾结点上，为下一次尾插做准备
            • 删除
              • p-q-x 删除q
                • q=p->next； p->next=q->next； free（q）；
            • 按值查找
              • lnode *p=l->next；//指针p指向头结点的下一个结点 while（p！=null&&p！=待查的值） p=p->next； return p；
          • 双链表
            • 与单链表相比多了一个指向前一结点的pre指针
              • 定义法
                • type struct LNoed｛ ElemType data; Struct LNoed *pre,*next; ｝LNode,*Llinklist;
              • 插入
                • ① s->next=p->next； ② p->next->pre=s； ③ s->pre=p； ④ p->next=s；
                  • ①②必须在④之前
              • 删除
                • p→next=q→next； q→next→pre=p； free（q）；
          • 循环链表
            • 循环单链表
            • 循环双链表
          • 静态链表
            • 这里的指针是指下一个元素的数组下标
    • 广义表
      • head
        • 取出位于表头部的元素，或者子表
      • tail
        • 取出表尾的元素
    • 受限制的线性表
      • 栈
        • 特点
          • 后进先出
          • 只允许在栈顶插入或删除
          • 不可以随便读取中间某个元素
        • 分类
          • 顺序栈
            • 基本操作
              • 判栈空 bool StackEmpty(SqStack S){ if(S.top==-1) //栈空 return true; else //不空 return false; ｝
              • 进栈 bool Push(SqStack &S,ElemType x){ if(S.top==MaxSize-1) //栈满，报错 return false; S. data[++S. top]=x; //指针先加1，再入栈 return true; ｝
              • 出栈 bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) //栈空，报错 return false; x=S. data[S. top--]; //先出栈，指针再减1 return true; }
              • 读栈顶元素 bool GetTop(SqStack S,ElemType &x) { if(S.top==-1）//栈空，报错 return false; x=S. data[S. top]; //x记录栈顶元素 return true; ｝
            • 共享栈
              • 两个顺序栈共享一个栈空间，达到节约存储空间的目的
                • 栈A的指针top0指向栈顶，栈B的指针top1指向栈顶 元素入栈A：top0先加一再入栈 元素入栈B：top1先减一再入栈 top1-top0=1时栈满 top0==-1时栈A空 top1==Maxsize时栈B空
          • 链栈
            • 没有头结点 Lhead指向栈顶元素 链栈便于插入与删除
        • 栈的应用
          • 括号匹配
          • 表达式求值
          • 递归调用
      • 队列
        • 特点
          • 先进先出
          • 不允许随便读取中间某个元素
        • 分类
          • 队列的顺序存储
            • 顺序队列
              • 进队
                • rear+1，再赋值
              • 出队
                • 先出队，再front+1
            • 循环队列
              • 队空
                • front==rear
              • 队满
                • （rear+1）%Maxsize==front
              • 当前元素个数
                • （rear-front+maxsize）%maxsize
              • 入队
                • 入队 bool EnQueue(SqQueue &Q, ElemType x){ if((Q. rear+1)MaxSize==Q. front) return false; //队满则报错 Q. data[Q. rear]=x; //没空则插在尾部 Q. rear=(Q. rear+1)MaxSize; //队尾指针加1取模 return true; ｝
              • 出队
                • 出队 bool DeQueue(SqQueue &Q, ElemType &x){ if(Q. rear==Q. front) return false; //队空则报错 x=Q. data[Q. front]; Q. front=(Q. front+1)%MaxSize; //队头指针加1取模 return true; }
          • 队列的链式存储
            • 本质是带有队头指针和队尾指针的单链表
              • 尾进头出
              • 判队空 bool IsEmpty(LinkQueue Q){ if(Q.front==Q. rear) return true; else return false; ｝
              • 入队 void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; //创建新结点，插入到链尾 Q. rear->next=s; Q. rear=s; ｝
              • 出队 bool DeQueue(LinkQueue &Q, ElemType &x){ if(Q.front==Q. rear) return false;//空队 LinkNode *p=Q. front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q. rear=Q. front; //若原队列中只有一个结点，删除后变空 free(p); return true; ｝
          • 双端队列
            • 输出受限
              • 只允许一端输出
            • 输入受限
              • 只允许一端输入
        • 队列的应用
          • 层次遍历
          • 缓冲区
      • 串
        • 模式匹配
          • 简单匹配
          • kmp算法
            • next值求法
              • ① 前两个next值为0，1
              • ② 后续next值通过前缀，后缀匹配，取最长成功匹配的串长+1
          • kmp算法的优化
            • nextval值求法
              • 根据next值向前找编号相同的，其next值即为待求的nextval值，若已有nextval值则更新
    • 线性表的推广
      • 数组
        • 存储方式
          • 行优先
          • 列优先
          • 特殊矩阵的压缩存储
            • 上三角矩阵 下三角矩阵
            • 对称矩阵
            • 三对角矩阵
              • 行优先
                • 存放在一维数组 k=2i+j-3
            • 稀疏矩阵
              • 三元组存储法
                • （行，列，data）
              • 十字链表存储法
  • 非线性结构
    • 集合
      • 元素同属于一个集合
    • 树结构
      • 树
        • 树的性质
          • 是一种递归的数据结构
          • 是一种分层结构
          • ① 树的结点数 = 所有结点的度数之和 + 1
          • ② 度为m的树在第i层最多有 mⁱ⁻¹ 个结点
          • ③ 高为h的m叉树最多有(mʰ -1) / (m-1)个结点
          • ④ 有n个结点的x叉树的最小高度 ┍ logₓ （n(m-1）+1）┒
      • 二叉树
        • 性质
          • n₀=n₂+1
          • n=n₀+n₁+n₂
            • n=1+n₁+2n₂
          • 高为h的二叉树最多有2ʰ-1个结点
        • 分类
          • 空二叉树
          • 满二叉树
          • 完全二叉树
            • 结点与编号一一对应
            • 度为1的结点只能有一个或者没有
              • 此结点决定了完全二叉树结点总数的奇偶性
            • 具有n个结点的完全二叉树的树高
              • ┍ log₂（n+1）┒ 向上取整
              • ┕ log₂n┙ +1 向下取整
          • 二叉排序树
            • 左小右大
          • 平衡二叉树
            • 左右子树高度差不超过 1
        • 二叉树的存储结构
          • 顺序存储
            • 完全二叉树
            • 满二叉树
          • 链式存储
            • 有n个结点的二叉链表 含有 n+1 个空链域
        • 线索二叉树
          • 线索二叉树是个物理结构
          • 空链域用来存放指向前序或者后续的线索
          • 分类
            • 中序线索二叉树
            • 先序线索二叉树
            • 后序线索二叉树
        • 二叉树的遍历
          • 先序遍历
            • 根左右
          • 中序遍历
            • 左根右
          • 后序遍历
            • 左右根
      • 树的存储结构
        • 双亲表示法
        • 孩子表示法
        • 孩子兄弟表示法
          • 二叉树表示法
            • 易于查找结点的孩子
            • 找双亲比较麻烦
            • type struct csnode｛ elemtype data； struct csnode *liftchild，*rightbro；//定义孩子和右兄弟指针 ｝csnode，*cstree；
      • 树，森林，二叉树的转换
        • 左孩子右兄弟
          • 根的左边孩子结点作为新树中根的孩子结点， 根的右兄弟变为新树中根的孩子
      • 树与二叉树的应用
        • 哈夫曼树/哈树
          • 带权路径长度WPL最小的二叉树
          • 特点
            • ① 左小右大型 或者 左大右小型
            • ② 每次选取两个权值最小的合并，其和作为新根的权值
            • ③ 哈树的形态不唯一，但是WPL值永远是最小的
            • ④ 哈树中不存在度为1点结点
              • 因为哈树是两两合并出来的
          • 哈夫曼编码
            • 可变长
              • 二进制位字符长度可变
            • 固定长
              • 二进制位字符长度固定
        • 并查集
          • 是一种集合（逻辑结构）
          • 顺序存储的双亲表示法的树
          • 并
          • 查
          • 并查集的应用
            • 判断图的连通性
              • 遍历无向图的所有边， 每遍历到一条边，就将其两顶点并到一个集合， 以此所有的连通的顶点都会在一个集合，而不连通的不在此集合里
    • 图结构
      • 图的定义
        • 顶点集V与边集E构成
      • 图的分类
        • 无向图
          • 无向图的全部顶点的度的和=边数×2
        • 有向图
          • 弧尾 → 弧头
          • 有向图的全部顶点的入度之和=出度之和
        • 简单图
          • 不存在重复的边 不存在顶点到自身的边
        • 完全图
          • 无向完全图
            • n(n-1)/2 条边
          • 有向完全图
            • 两顶点间存在方向相反的两条弧
        • 子图
        • 连通
          • 无向图中
            • 任意两顶点都是连通的
            • 极大连通子图称为连通分量
        • 强连通
          • 有向图中
            • 任意两点是强连通的
        • 简单路径与简单回路
          • 顶点不重复出现→简单路径
          • 除了第一个与最后一个点，其他的点不重复出现→简单回路
        • 生成树
          • 包含全顶点的极小连通子图
            • 既要图连通又要边数最少
        • 注意
          • 非连通情况下边数最多:
            • 由n-个顶点构成一个完全图，此时再加入一个点即为非连通图
          • 有向图强连通情况下边数最少:
            • 至少n条边，构成环路
        • 其他图
          • 稀疏图
            • |E| = |V|*log|V|时
          • 稠密图
      • 图的存储
        • 邻接矩阵法
          • 存储
            • 无向图
            • 有向图
          • 空间复杂度O(n²) → n为顶点数
          • 更适合存稠密图
        • 邻接表法
          • 存储
            • 无向图
              • 空间复杂度(V+2E)
                • 因为边会出现2次
            • 有向图
              • 空间复杂度(V+E)
        • 十字链表法
          • 有向图的链式存储
        • 多重表法
          • 无向图的链式存储
      • 图的遍历
        • 广度优先
          • 类似于层次遍历
        • 深度优先
          • 对一个点一直深挖
        • 对于无向图，调用DFS或BFS的次数 = 此图的连通分量个数
      • 图的应用
        • ① 最小生成树
          • ① 包含所有顶点
          • ② 包含尽可能少的边
          • ③ 权值和唯一
          • ④ 边数 = 顶点数-1
          • ⑤ 树形态不唯一
        • ② Prim算法
          • 算法过程
            • ① 任选一点
            • ② 寻找权值最小
            • ③ 依次相连，含所有点，尽可能少的边
          • 适用于求解边稠密的图的最小生成树
          • 时间复杂度
            • O(V²)
        • ③ 克鲁斯卡尔算法
          • 在整个图中找最小的边，优先选取，并要求包括所有顶点
          • 用到并查集
          • 适用于边少顶点多的图
          • 时间复杂度
            • Elog₂E
        • ④ 最短路径问题
          • ① Dijkstra算法
            • 算法过程
              • 每轮记录
                • ① 每一步的路径以及路径的总权值
                • ② 最短路径集合
            • 解决单源路径问题
              • 无权图，有权图都可
            • 时间复杂度
              • 邻接矩阵
                • O(V²)
              • 邻接表
                • O(V²)
          • ② Floyd算法
            • 带权图
            • 算法过程
              • 不断更新矩阵
              • 如:A，A²，A³……
              • A的角标代表中继结点
            • 时间复杂度
              • O(V³)
        • ⑤ 关键路径问题
          • 手算过程
            • ① 求事件Vk的最早发生时间
              • 从前向后直接算
            • ② 求事件Vl的最迟发生时间
              • 从后向前算，减去最小的权值
            • ③ 求活动的最早发生时间e
              • 弧尾的事件的最早发生时间
            • ④ 求活动的最迟发生时间l
              • 弧头的事件的最迟发生时间 - 此活动的权值
            • ⑤ 用活动最迟l减去活动最早e，为0的活动即为关键活动，其所连顶点即为所求
• 卡特兰数
  • 适用于：
    • 栈
      • n个元素入栈，求出栈序列个数
    • 二叉树
      • n个结点能构成多少种不同形状的二叉树
    • 括号匹配
      • n对括号，有多少种括号匹配序列
  • 使用卡特兰数的前提
    • 栈和二叉树不能有其他限制
      • 比如要求：出栈第一个数为1，此时不能用卡特兰数计算
• 两大方法
  • 查找
    • 顺序查找
      • 适用于
        • 顺序表
        • 链表
    • 折半查找
      • 适用于
        • 有序的顺序表
      • 比较方法
        • 一边倒
      • 要求线性表能随机存储 因此，仅适用于顺序存储结构
      • 时间复杂度 O(log₂n)
    • 分块查找
      • 块内无序，块间有序
      • 长为n的表分为b块，每块有s个记录 s=√n，平均查找长度取最小值√n+1
      • 平均查找长ASL = (S²+2S+n)/2S
        • 顺序
    • 树形查找
      • 二叉排序树
        • 左小右大
        • 构造
        • 插入
        • 删除
      • 平衡二叉树
        • 左右子树高度差不超过1 或者为空树
        • 调整
          • LL型
            • 右旋一次
          • RR型
            • 左旋一次
          • LR型
            • 先左旋再右旋
          • RL型
            • 先右旋再左旋
        • 操作
          • 插入
          • 删除
          • 查找
      • 红黑树
        • 定义
          • ① 左根右
          • ② 根叶黑
          • ③ 不红红
          • ④ 黑路同
        • 先调整再着色
    • 查找长
      • ASL成功 = (Σ笫几层×结点数)/总数
      • ASL失败 = (Σ第几层×结点空链域数)/总数
    • B树&B+树
      • B树
        • m叉B树
          • 支持随机查找
          • 特点
            • ① 每结点至多有m个子树， 至多m-1个关键字
            • ③ 除了根结点外，所有非叶结点至少有┍ m/2 ┒棵子树 至少有┍ m/2 ┒一1 个关键字
            • ④ 叶子结点在同一层，即空链域层
            • ② 若根结点不是叶子，则至少有2个子树
          • 树高
          • 查找
            • 结点内来用顺序查找，折半查找
          • 插入
          • 删除
            • ① 直接删
            • ② 兄弟够借
              • ① 左兄弟够借
                • 用左兄弟的最右结点代替自己，自己补到缺位上
              • ② 右兄弟够借
                • 用右兄弟的最左结点代替自己，自己补到缺位上
            • ③ 兄弟不够借
              • 合并
      • B+树
        • m叉B+树 特点
          • ① 每个关键字对应一棵子树
          • ② ┍ m/2 ┒≤ n ≤ m
          • ③ 叶结点包含了全部关键字且包含信息
          • ④ 非叶仅起索引作用
          • ⑤ 支持顺序查找，随机查找
    • 散列表
      • 查找效率取决于比较次数
      • 散列函数
        • ①直接定址法
        • ②除留余数法
          • H（key）= key%P
            • P:不大于表长的最大素数
        • ③数字分析法
        • ④平方取中法
      • 散列查找
        • 装填因子α =记录数/表长
      • 处理冲突的方法
        • 开放定址法
          • ①线性探测
            • 后移补位
            • 手算线性探测
              • ASL失败= 分子/分母
                • 分子:将表序号后移，直到遇到空位，记录后移的次数再+1 将P个元素内的所有记录的(后移的次数再+1)以及空位数(若空位在P内)
                • 分母:P
          • ②平方探测
            • 解决冲突
              • （ 余数+ d¡ ）%表长
              • d¡ = 0²，1²，-1²，2²，-2² ......
          • ③双散列
          • ④伪随机
        • 拉链法
  • 排序
    • 大多数排序只适用于顺序存储的线性表
    • 内部排序
      • 插入排序
        • 直接插入排序
          • 适用于顺序和链式存储的线性表
          • 选择出一个作为哨兵
            • 大元素放哨兵后面，小元素放哨兵前面
            • 完成后选择刚刚排好的那个元素作为新哨兵
          • 时间复杂度
            • O(n²)
          • 稳定
        • 折半插入排序
          • 适用于顺序存储的线性表
          • 时间复杂度
            • O(n²)
        • 希尔排序
          • 适用于顺序存储的线性表
          • 时间复杂度
            • O(n²)
          • 不稳定
      • 交换排序
        • 冒泡排序
          • 时间复杂度
            • O(n²)
          • 稳定
        • 快速排序
          • 选基准，①从后向前与基准比较，②从前向后与基准比较，①②交替进行
          • 时间复杂度
            • 最好 O(nlog₂n)
            • 最坏 O(n²)
            • 平均 O(nlog₂n)
          • 不稳定
      • 选择排序
        • 简单选择排序
          • 时间复杂度 O(n²)
          • 不稳定
        • 堆排序
          • 适用于关键字多的情况
          • 堆可视为完全二叉树
            • 建立过程
              • 从最后一个非叶节点开始，判断是否符合堆的要求
          • 时间复杂度 O(nlog₂n)
          • 不稳定
      • 基数排序
        • 时间效率与初始序列无关
        • 最高位优先/最低位优先
        • 排序年月日
        • 时间复杂度 O(d(n+r))
        • 稳定
      • 归并排序
        • 时间复杂度 O(nlog₂n)
        • 稳定
    • 外部排序
      • 外部排序总时间 = 内部排序时间 + 外存读写时间 + 内部归并时间
      • 对于r个初始归并段，做x路归并
        • 树高h - 1 = ┍ logₓr ┒= 归并趟数
      • 败者树
        • 可视为完全二叉树
        • 每轮比较，胜者继续向上，一直到根结点
        • k路归并的败者树深度为：┍ log₂k ┒
      • 置换选择排序
        • 算法过程
          • ①从待排序序列中选取一定数量元素，放入工作区
          • ②在工作区中选择最小数放入归并段，且miniMax改为此数
          • ③保证下一次放入归并段的数要比miniMax值要大
          • ④当工作区中没有比miniMax更大的数时，则第一个归并段生成
      • 最佳归并
• 数据运算
  • 四则运算
    • 加 +
    • 减 -
    • 乘 *
    • 除 /
  • 运算 （a为数据）
    • 异或 ^ 相同为0，相异为1
    • 逻辑与 && 同1为1，否则为0
    • 逻辑或 || 全0才0，否则为1
    • 先自增再赋值 ++a
    • 先赋值再自增 a++
    • 先自减再赋值 --a
    • 先赋值再自减 a--
    • 取余 %a
    • 取反 !a
• 物理结构
  • 索引存储
    • 不仅存储元素，还要为其构建索引表，索引表包含多个索引项 修改数据的同时也要修改索引表
  • 链式存储
    • 元素在逻辑上相邻，但是在物理上不一定相邻
  • 顺序存储
    • 逻辑上相邻的元素在物理上存储也是相邻的
  • 散列储存 （哈希）
    • 根据关键字直接计算存储地址