2016.06.30 – 07.12
读《数据结构》（严蔚敏 吴伟明）“5、6章”的个人笔记。

5 数组和广义表

07.04
本笔记的两种数据结构 —— 数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。

5.1 数组

(1) 数组的定义

数组抽象数据类型数组定义

在数据元素的逻辑关系中，每个非结尾元素都有一个后继元素，每个非最开始元素都有一个前驱元素。根据数组的定义，a[m][n][k]的数组元素总数为m x n x k，即对于n维数组，数组元素个数为$\prod_{i=1}^{n}b_i$，$b_i$为数组第i维长度。n维数组的数据元素存储位置的计算公式（n维数组的映像函数）为（主要依据数组定义/数组元素枚举而来）：

$$loc(j_1,j_2,…,j_n) = loc(0,0) + (b_2 \times b_3 \times … b_n \times j_1 + b_3 \times b_4 \times … \times b_n \times j_2 + … + b_n \times j_{n - 1} + j_n) \times L$$
L为每个数组元素所占存储单元个数。 b@H_957_502@i $b_i$为数组第i维长度。

（数组一般不进行插入、删除元素操作 —— 复杂度）

n维数组类型为其 数据元素为n – 1维数组类型 的一维数组类型（的定义）

(2) 数组的顺序表示和实现

/* sequence_array.c * 数组的顺序表示描述和简单实现 * 2016.07.05 */
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX_ARRAY_DIM 8 // 规定数组维数最大值
#define OK 0 // 函数正常返回状态
#define NK 1 // 函数非正常返回

typedef char ElemType;      // 数组元素类型

/* 描述数组的结构体 */
typedef struct {
    ElemType    *base;      // 数组元素基址
    int         dim;        // 数组维数
    int         *bounds;    // 数组各维界基址
    int         *constants; // 数组映像函数常量基址
}Array;

/* 数组基本操作 */
// 构造相应合法的维数和各维度的数组
int init_array(Array *pa,int dim,...)
{
    int         i;
    va_list     ap;
    unsigned    elemtotal;  // 类型由动态分配最大量决定

    if (dim < 1 || dim > MAX_ARRAY_DIM) return NK;

    pa->dim     = dim;
    pa->bounds  = (int *)malloc(dim * sizeof(int)); // 保存各维长度的首地址
    if (!pa->bounds) exit(NK);

    // 求数组内存空间总大小
    elemtotal   = 1;
    va_start(ap,dim);
    for (i = 0; i < dim; ++i) {
        pa->bounds[i]   = va_arg(ap,int);
        if (pa->bounds[i] < 0) exit(NK);    // man va_arg()发生错误没说是小于0的错误
        elemtotal   *= pa->bounds[i];       // n维数组元素个数计算
    }
    va_end(ap);

    pa->base    = (ElemType *)malloc(elemtotal * sizeof(elemtotal));
    if (!pa->base) exit(NK);

    // 数组映像函数计算
    pa->constants   = (int *)malloc(dim * sizeof(int));
    if (!pa->constants) exit(NK);
    pa->constants[dim - 1]  = 1;    // 只以数组最右一列变化的数组元素直接数
    for (i = dim - 2; i >= 0; --i)
        pa->constants[i]    = pa->bounds[i + 1] * pa->constants[i + 1];
    return OK;
}

// 销毁数组
void destroy_array(Array *pa)
{
    if (!pa) return ;
    if (pa->base) {
        free(pa->base);
        pa->base    = NULL;
    }
    if (pa->bounds) {
        free(pa->bounds);
        pa->bounds  = NULL;
    }
    if (pa->constants) {
        free(pa->constants);
        pa->constants   = NULL;
    }
}

// 给数组指定元素赋值
int assign_array_value(Array *pa,ElemType e,...)
{
    int         i;
    int         arg;
    va_list     ap;
    unsigned    off;

    if (!pa) return NK;
    off = 0;
    va_start(ap,e);
    for (i = 0; i < pa->dim; ++i) {
        arg = va_arg(ap,int);
        if (arg < 0 || arg > pa->bounds[i]) return NK;
        off += pa->constants[i] * arg;  // 数组下标顺序要求是从左到右 - 得看constants存储数组下标对应
    }
    va_end(ap);
    *(pa->base + off)   = e;
    printf("%2d = %d ",off,e);
    return OK;
}


/* 简单测试数组的基本操作函数 */
int main(void)
{
    int     i,j,rv;
    int     dl,dr,dim;
    Array   a;

    dim = 2;
    dl  = dr = 5;
    init_array(&a,dim,dl,dr);
    for (i = 0; i < dl; ++i) {
        for (j = 0; j < dr; ++j) {
            assign_array_value(&a,i + j,i,j);
        }
        printf("\n");
    }
    destroy_array(&a);
    return 0;
}

思路
该段程序是根据数组的定义依据数组的下标（维数）给数组分配一段连续的空间；然后根据数组下标访问形式（含义）定位到相应的内存单元。

man变长参数
void va_start(va_list ap,last)
va_start()宏用以初始化ap以供后续的va_arg()和va_end()使用，它必须被最先调用。last是变参数列表前的最后一个参数名，也就是说，调用函数知道该参数（最后一个参数名）的类型。因为该参数的地址会在va_start()宏中使用，所以该参数不应被声明为寄存器、函数或数组类型的变量。

type va_arg(va_list ap,type)
va_arg()宏获取在本函数参数栈中以type类型获取一个值。ap是经va_start()初始化的va_list ap。每调用va_arg()一次，ap就会被修改指向下一个参数。参数type是一个类型名，以指定获取参数值的方式。第一次在使用va_start()宏后调用va_arg()宏时，将返回last后的一个type类型的参数。后续的调用将一次返回相应类型的参数。如果不再有下一个参数，或者type类型跟下一个参数的实际类型不一致（再以type类型取值一直取下去），将会发生随机的错误。如果ap被传递给一个使用va_arg(ap,type)的函数，那么在该函数返回后，ap的值是不定的。

void va_end(va_list ap)
在同一个函数中，每个va_start()调用都必须对应一个va_end()调用。在调用va_end(ap)后，变量ap的值是不定的。在每个va_start()和va_end()之间多次遍历参数是可能的。va_end()可以是宏或者函数。

[变长参数宏实现 —— 根据参数在栈中的分布得来：《汇编语言》、《程序员的自我修养》]

(3) 矩阵的压缩存储

07.06
如何存储矩阵的元，使矩阵的各种运算能有效地进行。在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是0元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定的规律，则我们称此类矩阵为特殊矩阵；反正，称为稀疏矩阵[值相同或零元素分布无规律且这些值占矩阵维数的比例较小，如小于0.05]。

5.2 广义表

(1) 广义表的定义

广义表一般记作

$$LS = (\alpha _1,\alpha _2,\alpha _n)$$
在线性表中， $\alpha _i只限于单个元素$。而在广义表中， $\alpha _i$可以是单个元素，也可以是广义表，分别称为广义表的 原子和 子表。当广义表非空时，称第一个元素 $\alpha _1$为LS的 表头，称其余元素组成的表 $(\alpha _2,\alpha _3,\alpha _n)$是LS的 表尾。[ 结合例子和描述广义表存储结构的结构体理解广义表]

(2) 广义表的存储结构

由于广义表中的数据元素可以具有不同的结构（原子或子表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。

6 树和二叉树

6.1 树

07.07

结点。组成树的基本元素，如上图树中的A到M都是结点。
度。结点拥有的子树数称为结点。
树的度。树内各节点的度的最大值。
叶子（终端结点）。度为0的结点。
孩子、双亲。结点子树的根称为该结点的孩子，该结点称为孩子的双亲。[如A结点下的B、E、K、L结点为一个子树，A结点是B结点的双亲，B结点是A结点的孩子]
兄弟。同一个双亲的孩子之间互称为兄弟。
层次。结点的层次从根开始定义起，根为第一层，根的孩子为第二层。
堂兄弟。若某结点在第l层，则其子树的根就在第l + 1层。其双亲在同一层的结点互为堂兄弟（G与E、F、H、I、J）。
树的深度。树中结点的最大层次称为树的深度或高度。
祖先和子孙。结点的祖先是从根结点到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
有/无序树。如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则为无序树。在有序树中最左边子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林。森林是m（m >= 0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

6.1 二叉树

(1) 定义 & 性质

二叉树。二叉树的特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树性质。
[1] 在二叉树的第i层上至多有$2^{i-1}$个结点。
[2] 深度为k的二叉树最多有$2^k - 1$个结点。（具n个结点的二叉树的深度为 @H_404_1316@└logn2┘+1 $\llcorner log _2 ^ n \lrcorner + 1$）
[3] 对任何一棵二叉树T，如果其终端结点数为$n_0$，度为2的结点数为@H_823_1404@ n2 $n_2$，则$n_0 = n_2 + 1$。

满二叉树。一个深度为k且有@H_529_1502@ 2k−1 $2^k-1$个结点的二叉树称为满二叉树。
完全二叉树。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的节点一一对应时（自上而下，自左至右），称之为完全二叉树。

完全二叉树的性质。
[1] 具有n个结点的完全二叉树的深度为$\llcorner log_2^n \lrcorner + 1$。
[2] 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到最后一层，编号从左至右），则对任一结点i（1 <= i <= n），有

• ·若i = 1，则结点i是二叉树的根；若i > 1，则双亲结点是结点$\llcorner i /2 \lrcorner$。
• ·如果2i > n，则结点i无左孩子（结点i为叶子结点）；否则（2i < n）其左孩子是结点2i。
• ·若2i + 1 > n，则结点i无右孩子；否则其右孩子是结点2i + 1。

07.08

(2) 存储结构

(3) 二叉树的遍历

遍历对于线性结构来说，是一件容易的事情。对于像二叉树这样的非线性结构，需要寻找一种规律，以便使二叉树上的结点能排列在一个现行队列上，从而便于遍历。
根据二叉树的递归定义和各结点先后顺序（完全二叉树顺序）[好大的跳跃]，二叉树的遍历可分为“先序”、“中序”以及“后续”遍历三种。

6.3 赫夫曼树

07.11

(1) 赫夫曼树含义

树中两个结点之间的路径长度。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。

树的路径长度。从树根到每一个结点的路径长度之和。
结点的带权路径长度。从该结点到树根之间的路径长度与该结点上权（如搜索到该结点的概率）的乘积。
树的带权路径长度。树中所有叶子结点的带权路径长度之和。
赫夫曼树。假设有n个权值$\{ \omega _1,\omega _2,\omega _n \}$，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为$\omega _i$，其中带权路径长度最小的二叉树为最优二叉树或赫夫曼树。[对于遍历来说，倘若叶子结点的双亲为某条件，显然将条件发生概率大者的双亲和相应的叶子结点放在离根结点更近的位置有利于减少遍历次数，这是霍夫曼树（应用或思想）的一个体现]

(2) 构造赫夫曼树

根据赫夫曼算法构造赫夫曼树：
[1] 根据给定的n个权值$\{ \omega _1,\omega _n \}$构成n棵二叉树的集合$F=\{ T_1,T_2,T_n \}$，其中每棵二叉树$T_i$中只有一个带权为$\omega _i$的根结点，其左右子树均为空。
[2] 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
[3] 在F中删除这两棵树，同时将新得到的二叉树加入F中。
[4] 重复[2]和[3]，直到F只含一棵树为止。这棵树便是赫夫曼树。

例。

07.12

(3) 赫夫曼编码

6.4 红黑树

[-来自度娘-]

二叉查找树。也称有序二叉树（排序二叉树），是指一棵空树或者具有以下性质的二叉树：[1] 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；[2] 若任意结点的右子树不为空，则右子树上所有结点的值绝大于它的根结点值；[3] 没有键值相等的结点。

平衡二叉树。平衡二叉树具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（常用算法有红黑树、AVL、Treap、伸展树等）

红黑树。红黑树是一种具有二叉查找树性质的自平衡二叉树：在进行插入和删除操作时通过特定的操作保持二叉树的平衡，从而获得较高的查找性能。[它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并在在实践中是高效的：它可以在$O(log_2 ^ n)$时间内做查找、插入和删除，n为树中元素的数目。二叉查找树若退化成了一棵具有n个结点的线性链后，则操作的最坏的运行时间为O(n)。红黑树：运行时间$O(n)$到$O(log_2 ^n)$的算法（对二叉查找树的限制） —— 具体被优化的时间可参看《编程珠玑》]

红黑树性质。

一棵红黑树

[众多网址引用，据说来自维基百科]

树的旋转。左旋：当在某个结点node上，做左旋操作时，假设右孩子不为NULL，则node结点所代表的子树可以作为其右孩子的左结点，原来右节点中的左子结点依照具体情况成为node上的左结点或右结点。（右旋同理）左旋如下图

[图来自http://blog.csdn.net/v_JULY_v/article/details/6105630]
红黑树的插入和删除。红黑树的插入相当于在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作（插入结点着色、旋转，具体不详，先点到为止）。

[2016.07.01 - 0:09]