数据结构

1. 线性表[矩阵 | 数组 | 字符串 | 堆栈 | 队列]

1). 概念
    除首尾元素外, 每个元素都有唯一一个直接前驱和唯一直接后继
2). 特点
    同一性, 有穷性, 有序性
3). 存储方式
    a. 顺序存储(连续空间)
    b. 链式存储
        a). 单链表(数据域 + 指针域)
        b). 循环链表(首尾相接的链表)
        c). 双向链表(前驱指针域 + 数据域 + 后驱指针域)
        d). 静态链表(顺序存储数组模拟链表, 设置游标模拟指针)
4). 栈 | 队列 | 串 | 数组
    a. 栈(限定性线性表)
        a). 后进先出
        b). 栈顶入栈, 出栈
        c). 顺序栈 | 链栈
    b. 队列(限定性线性表)
        a). 先进先出
        b). 队尾入, 队首出
        c). 链队列 | 循环队列
    c. 串(特定的线性表)
        a). 定长顺序串 | 块链串
    d. 数组(线性表的扩充)
        a). 三角矩阵 | 带状矩阵 | 稀疏矩阵(三元组表示 & 十字链表)
    e. 广义表(线性表的扩充)
        a). 头尾链表(表结点(标志域 + 表头指针 + 表尾指针), 元素结点(标志域 + 值域))
        b). 扩展线性链表(表结点(标志域 + 表头指针 + 表尾指针), 原子结点(标志域 + 值域 + 表尾指针))

2. 树

1). 表示法
    a. 倒置树结构
    b. 文氏图
    c. 广义表[嵌套括号](A(B(C,D)),E(F),G)
    d. 陷入式
2). 二叉树
    a. 概念
        每个结点的度都不大于 2 & 每个结点的孩子结点次序不能任意颠倒
    b. 存储结构
        a). 顺序存储 | 链式存储 ([二叉链表] 左孩子域 + 数据域 + 右孩子域)
    c. 遍历顺序
        a). 先序(根左右) | 中序(左根右) | 后序(左右根)
3). 线索二叉树
    a. 结构(左孩子域 + 前驱结点指针 + 数据域 + 后继结点指针 + 右孩子域)
4). 哈夫曼树
    a. 概念
        带权路径长度最短的二叉树
    b. 哈夫曼编码(左分支 0 右分支 1)

3. 图

1). 网状数据结构
2). 存储方法
    a. 邻接矩阵(数组)
    b. 邻接表(稀疏图)
        a). 表头结构(数据域 + 链域) 
        b). 弧结点结构(邻接点域 + 数据域 + 链域)
    c. 邻接多重表
        a). 顶点结构(data+firstedge)
        b). 边结点结构(mark+ivex+ilink+jvex+jlink+info)
    d. 十字链表
        a). 顶点结构(data+firstin+firstout)
        b). 弧结点结构(tailvex+headvex+hlink+tlink+info)
3). 遍历
    a. 深度优先
    b. 广度优先

4. 查找

1). 比较式查找
    a. 基于线性表查找
        a). 顺序查找
        b). 折半查找(二分查找) (顺序存储 & 有序)
        c). 分块查找(块内无序 & 块块有序 & 关键字有序)
    b. 基于树查找
        a). 二叉排序树
            若左子树非空左子树小于根 & 若右子树非空右子树大于根 & 左右子树分别为二叉排序树
        b). 平衡二叉排序树
            左右子树深度之差的绝对值小于等一
        c).B_树(平衡的 m 路查找树)
2). 计算式查找(哈希查找)

5. 排序

1). 内排序(内存中排序)
    a. 插入排序
        a). 直接插入排序
            新元素与已排序好的数据进行比较, 关键字大于新元素向后移位
        b). 折半插入排序
            有序表进行折半查找
        c). 希尔排序
            拆分子序列进行插入排序
    b. 交换排序
        a). 冒泡排序
        b). 快速排序
            选取首个记录 (k) 作为枢轴, 小于 k 移到枢轴前边
    c. 选择排序
        a). 简单选择排序
            最小值的与首个比较, 剩余最小值与第二个比较...
        b). 树形选择排序
        c). 堆排序
    d. 归并排序
    e. 分配排序
    a). 链式基数排序(低位优先)

2). 外排序(内存无法容纳, 需要借助外部存储设备)

a. 归并排序
    a). 文件分批次输入到内存中进行排序，再将排序好的归并段写回外存
    b). 使用归并方法进行多边归并
b. 磁盘排序
    a). 减少数据扫描遍数
    b). 增大批次读取数据量    

内容出自 << 数据结构 >> 仅供学习 / 复习参考