数据结构01

发表于 | 分类于

以下内容为数据结构一门课程的摘要笔记

多重链表

  • 多重链表： 链表中的节点可能同时隶属于多个链；包含两个指针域的链表并不一定是多重链表，比如双向链表就不是多重链表；多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

  • 稀疏矩阵：矩阵中很多项为0导致非零项b比较稀疏，这种矩阵称为稀疏矩阵；稀疏矩阵采用二维数组将产生空间的较大浪费
    稀疏矩阵

  • 十字链表：对于矩阵中的任意一个Term节点，其既处于改行的循环链表中，又出于该列的循环链表中，故而命名十字链表；而在该矩阵的多重链表表示中,第i行的head和第i列的head表头结点的URegion 域均为零，行链表头结点只用right 指针域，列链表头结点只用down指针域，故这两组表头结点可以合用，也就是说对于第i 行的链表和第i 列的链表可以共用同一个头结点。为了方便地找到每一行或每一列，将每行（列）的这些头结点们链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第i 行（列）的头结点的值域指向第i+1行（列）的头结点，… ，形成一个循环表。这个循环表又有一个头结点，这就是最后的总头结点，指针HA 指向它。总头结点的row 和col 域存储原矩阵的行数和列数，v域存储矩阵中非零项个数。
    十字链表1
    十字链表2

堆栈

  • 前缀表达式，后缀表达式：
    (3 + 4) × 5 - 6 就是中缀表达式
    - × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式

  • 后缀表达式的计算：从左向右依次读取，遇到运算符则向前回溯两个数字作为运算数计算

  • 中缀表达式转换为后缀表达式：

    1. 空格直接忽略，运算数直接输出；
    2. 遇到运算符如果优先级大于栈顶运算符 则压栈，若小于栈顶运算符则将栈顶出栈输出并继续比较，直到该运算符优先级大于栈顶运算符，然后压栈该运算符；
    3. 遇到右括号，则栈内运算符出栈输出，直到遇到左括号
      例子
      中缀转后缀

二叉树

  • 满二叉树（完美二叉树）：

满二叉树

  • 完全二叉树：

完全二叉树

  • 二叉树的遍历是根据根的位置确定：
    • 先序遍历 根左右
    • 中序遍历 左根右
    • 后序遍历 左右根

  • 一个结点的度是其子树的个数。

  • 叶结点总数n0与有两个儿子的结点总数n2之间的关系是：n0=n2+1.

  • 利用中序遍历与先序遍历（或后序遍历）确定树的结构
    确定树结构

搜索树

  • 二叉搜索树定义：可以为空，如果不为空，则非空左子树小于根节点，非空右子树大于根节点，且左右子树都是二叉搜索树。

  • 平衡因子：定义为左子树高度减去右子树高度（根节点高度为0）。

  • 平衡二叉树（Balanced Binary Tree）的定义：又称为AVL树， AVL树或者是一棵空树，或者是具有下列性质的非空二叉搜索树：任一结点左、右子树高度差的绝对值不超过1。

  • 平衡二叉树的调整：将二叉树视为线性结构，根节点与子节点的路径可以滑动

例子一
ll
例子二
lr

  • 高度为h的平衡二叉树的最小结点数：图中h为高度，n为最小节点数，F为斐波那契数列

二叉树的最小结点数

哈夫曼树

  • 哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明如何构建哈夫曼树

    1. 将所有左，右子树都为空的作为根节点。
    2. 在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。
    3. 从森林中删除这两棵树，同时把新树加入到森林中。
    4. 重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
      例子：
      哈夫曼树

  • 哈夫曼编码：利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。
    例子：

堆

  • 最大堆：一个有N>0个元素的最大堆H是一棵完全二叉树，每个结点上的元素值不小于其子结点元素的值。一般而言堆是利用数组来存储的。

  • 堆的两个特性

    • 结构性：用数组表示的完全二叉树；
    • 有序性：根结点到任一结点的关键字序列保持非递增（称“最大堆(MaxHeap)”,也称“大顶堆” ）或者非递减（称“最小堆(MinHeap)”,也称“小顶堆” ）。
      堆

  • 最大堆的插入：可以概括成一句话：从新增的最后一个结点的父结点开始，用要插入元素向下过滤上层结点（相当于要插入的元素向上渗透）
    例子：
    最大堆的插入
    上图中假设第一步6处为空，要插入元素58；则首先将58放在6处，而后将58同31比较，58>31，故两个元素交换；再将58同44比较，58>44，故两个元素交换(在根节点上方为了方便处理一般会添加哨兵元素，存有Maxdata，任何元素都要小于此maxdata)，58<maxdata，不再继续交换。

  • 最大堆的删除：取出根结点（最大值）元素，同时删除堆的一个结点。
    例子：
    最大堆的删除
    上图中，首先将根节点取出，然后将堆最底层最右侧节点移动到根节点，再找出根节点的较大孩子，并将根节点与较大孩子互换，依次交换直至堆重新有序。

  • 最大堆的建立：

    • 可以通过最大堆的插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为O(N logN)。
    • 在线性时间复杂度下建立最大堆。具体分两步进行：
    1. 第一步，将N个元素按输入顺序存入二叉树中，这一步只要求满足完全二叉树的结构特性，而不管其有序性。
    2. 第二步，调整各结点元素，以满足最大堆的有序特性。