数据结构

参考书：《数据结构（C语言版）》，严蔚敏、吴伟民编著

1 线性表

1.1 顺序存储结构

只要确定了线性表的起始位置，线性表中的任一数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机存取的存取结构。

1.2 链式线性表

单链表是非随机存取的存储结构

2 栈和队列

2.1 栈

栈，后进先出（last in first out，LIFO）

2.2 队列

队列，先进先出（first in first out，FIFO），在队头删除数据，队尾插入数据。
双端队列：两端都可以插入删除
输出受限的双端队列：一个端点允许插入删除，另一个端点只允许插入
输入受限的双端队列：一个端点允许插入删除，另一个端点只允许删除

3 串

3.1 串的表示和实现

定长顺序表示：类似数组
堆分配存储：使用malloc和free进行动态分配内存
块链存储表示：类似线性表的链式存储结构，但每个结点可以存储一个或多个字符

3.2 串的模式匹配算法

求子串的位置Index（S,T,pos）:
返回子串T在主串S中第pos个字符之后的位置，若不存在则返回0
经典算法：

int Index(sstring S,sstirng T,int pos){//时间复杂度O（m*n）
  i=pos; j=1;
  while(i<=s[0]&&j<=T[0]){
    if(s[i]==T[j]){
      ++i;++j;
    }
    else{
      i=i-j+2;j=1;
    }
  }
  if(j>T[0])
    return i-T[0];
  else
    return 0;
}

KMP算法：

int Insex_KMP(sstring S,sstring T,int pos){//时间复杂度O（m+n）
  i=pos;j=1;
  while(i<=s[0]&&j<=T[0]){
    if(j==0||s[i]==T[i]){
      ++i;++j;
    }
    else j=next[j];
  }
  if(j>T[0])
    return i-T[0];
  else 
    return 0;
}

void get_next(sstring T,int next[]){//时间复杂度O（m）
   i=1;next[0]=1;
  while(i<T[0]){
    if(j==0||T[i]==T[j]){
      ++i;++j;
      next[i]=j;
    }
    else 
      j=next[j];
  }
}

void get_nextval(sstring T,int nextval[]){
  i=1;nextval[1]=0;j=0;
  while(i<T[0]){
    if(j==0||T[i]==T[j]){
      ++i;++j;
      if(T[i]!=T[j])
        nextval[i]=j;
      else
        nextval[i]=nextval[j];
    }
    else 
      j=nextval[j];
  }
}

KMP算法仅当子串与主串之间存在许多部分匹配的情况下才比经典算法快很多，其最大的特点是主串指针不需回溯，可以边读入边匹配

4 数组和广义表

4.1 稀疏矩阵的压缩

稀疏矩阵：矩阵中非零元素的分布不规律
压缩方法：
1.三元顺序表

2.行逻辑链接的顺序表

3.十字链表
矩阵的非零元个数和位置变化较大时通常使用十字链表。
十字链表中，每个非零元可用一个含5个元素的节点表示，其中i,j,e分别表示该元素所在的行，列和值，向右域right用以连接同一行中下一个非零元，向下域down连接同一列中下一个非零元。

 typedef struct OLNode{   //单个非零元节点
  int i, j;  //该非零元的行和列的下标
  ElemType e;  //该非零元的值
  struct OLNode *right, *down;  //该非零元所在行表和列表的后继域
}OLNode； *OLink

typedef struct {   //表示稀疏矩阵的十字链表
  OLink *rhead, *chead; //行和列链表头基址
  int mu, nu, tu;  //稀疏矩阵的行数、列数和非零元素个数
}CrossList；

4.2 广义表

广义表一般记作
LS=（a1,a2,...,an）
ai可以是单个元素，称为原子，也可以是广义表，称为子表。
当广义表非空时，称第一个元素为表头，其余元素组成的表成为表尾。广义表有以下性质：
1.列表的元素可以是子表，子表的元素也可以是子表
2.列表可以为其他列表所共享
3.列表可以是递归结构，即列表可以是其本身的一个子表
存储结构
广义表内有两种元素：
表节点，由3个元素组成，标志域，用于指示表头的指针域和指示表尾的指针域
原子节点，由两个元素组成，标志域，值域
其中，标志域用于指示该节点是表节点还是原子节点
广义表可以用于表示m元多项式

5 树和二叉树

5.1 树

结点的度：结点拥有的子树的数量
树的度：树内各结点的度的最大值
树的深度：树中结点的最大层次
若树的子树从左至右是有次序的则成为有序树，有序树最左边的子树的根结点称为树的第一个子结点。
森林是m棵互不相交的树的集合

5.2 二叉树

5.2.1定义和性质

二叉树（binary tree）是一种特殊的树结构，其每个结点至多只能有两棵子树，且有次序之分
二叉树有以下重要性质：

在第i层上至多有 $ 2^(i-1) $ 个结点
深度为k的二叉树的最大结点数为2^（k）-1个结点
2.1 一棵深度为k，且有2^（k）-1个结点的二叉树称为满二叉树
2.2 按照从上到下，从左到右的顺序从根结点开始对满二叉树的结点编号，则若深度为k且其每一个结点的编号都与满二叉树的结点一一对应时，则为完全二叉树。完全二叉树的终端结点只可能在层次最大的两层上出现；对任意结点，若其右分支下的子孙最大层次为l，则其左分支下的子孙最大层为l或l+1
对任意一棵二叉树，如果其终端结点数为m，度为2的结点数为n，则m=n+1
具有n个结点的完全二叉树的深度为floor（（log_2 n ）+1）
如果对一棵有n个结点的完全二叉树进行编号，则对任一结点i，有：
5.1 若i=1，则结点i为根结点；若i>1,则其父结点为floor（i/2）
5.2 若2i>n,则结点i为终端结点；否则其左结点为2i
5.3 若（2i+1）>n则其无右结点；否则其右结点为2i+1

5.2.2二叉树的存储结构

顺序存储结构
用一组连续的地址单元从上到下从左到右存储二叉树的元素，没有元素的节点用0表示。
只适用于完全二叉树。
链式存储结构
二叉链：数据域，左右指针域
三叉链：数据域，左右指针域，父结点指针域

5.3 遍历二叉树和线索二叉树

5.3.1遍历二叉树

遍历二叉树是以一定规则将二叉树的节点排成一个线性序列，实际上是对一个非线性结构进行线性化操作

先序
中序
后序

5.3.2线索二叉树

为保存遍历过程中的信息，在每个结点中增加两个指针域，fwd和bkwd分别指示结点的前驱结点和后继结点，但是会增加所需存储空间，因此规定：
若结点有左子树，则lchild指针指向其左侧子结点，否则指示遍历过程中其前驱结点；若结点有右子树，则rchild指针指向其右侧子结点，否则指示遍历过程中其后继结点。为避免子结点和前驱后继结点混淆，增加两个标志域LTag和RTag（同样增大了所需存储空间？）

以这种结点构成的二叉链表称为线索链表，指向前驱结点和后继结点的指针称为线索。
对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
线索化的过程即在遍历中修改指针的过程

5.4 树和森林

5.4.1树的存储结构

父结点表示法
假设以一组连续空间存储树的节点，同时在每个结点中增加一个指示器指示其父结点的位置
子结点表示法
兄弟子结点表示法

5.4.2二叉树和森林的转换

二叉树转换为森林
森林转换为二叉树

5.4.3 树与等价问题

（没看懂，待补充）

5.5 赫夫曼树及其应用

5.5.1 最优二叉树

树的路径长度：从树根到每一个结点的路径长度之和。
树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和。
假设有n个结点，构造一棵有n个叶子结点的二叉树，其中带权路径长度最小的树称为最优二叉树或赫夫曼树。
构造赫夫曼树：

根据给定的权值构成n棵二叉树的集合F，其中每棵二叉树仅有一个结点。
在集合F中选择权值最小的两棵树作为左右子树构造一棵新的二叉树，且置新的二叉树根结点的权值为左右两棵子树根结点的权值之和。
在F中删掉这两棵树，同时将新的二叉树加入到F中。
重复2-3，直到F中仅剩一棵树为止。

5.5.2 赫夫曼编码

若有一棵二叉树，其左分支为0，右分支为1，则可以用从根结点到叶子结点路径上组成的字符作为该结点的编码。

image.png

6 图

7 动态存储管理

8 查找

本节内容如下：

查找表

8.1 静态查找

功能：查找摸个元素是否在表中。检索某个特定元素的各种属性。

8.1.1 顺序表的查找

--以顺序表或线性链表表示静态查找表。
--过程：从最后一个记录开始，逐个将元素的关键值和给定值进行比较。如果某个元素的关键值和给定值相等，则查找成功；若直到第一个元素都没有找到相应元素，则查找不成功。
--可以将第0个元素的关键值赋值为给定值，可以免去查找过程中检测整个表是否查找完毕的步骤。
--当每个元素的查找概率不相等时，应先按查找概率对元素进行排序以提高查找效率。
--无法预测查找概率时，可以为每个元素增加一个访问频度的属性，并使顺序表中的元素始终按照访问频度次序排列，使概率较大的元素在查找过程中不断后移。或每次查找之后将刚查到的元素直接移动到末尾。
--优点：算法简单，适应面广。
--缺点：平均查找长度大，效率低。

8.1.2 有序表的查找

--以有序表表示静态查找表。一般使用折半查找法（二分法）。
--过程：先确定需要查找的元素所在区间范围，然后逐步缩小范围直到找到或者找不到该元素为止。
--折半查找过程可以看作一棵二叉树（这时二叉树可以称为判定树），找到有序表中任意元素的过程就是走了一套从根节点到该元素对应节点的路径。和给定值比较的次数为该节点在树上的层次数。
--优点：效率高于顺序查找
--缺点：只适用于顺序存储结构，对线性链表无法有效进行。
--除折半查找之外，还有斐波那契查找和插值查找。

8.1.3 静态树表的查找

--当有序表中各元素的查找概率不等时，折半查找法的性能未必最优。
--静态最优查找树：各个元素的带权路径之和最小的判定树称为静态最优查找树，可以使查找性能达到最优状态。
--构造静态最优查找树的方法：（待补充）
--构造次优查找树的方法：在有序表中取元素r构造根节点，应使r左树权值之和与右树的权值之和相差最小。然后分别对左树和右树构造次优查找树。

8.1.4 索引顺序表的查找

--以索引顺序表示静态查找表，可以用分块查找实现。
索引表
--除需要被查找的表之外，还需为它建立一个索引表，如下图所示。

索引表

--上图中，下方为需要被查找的表，可以分为三个子表。在索引表中为每个子表建立索引项，包含：关键字项（该子表内的最大值）、指针项（该子表的第一个元素在表中的位置）。
--索引表按照关键字有序，则表为有序表或者分块有序（即第二个子表中所有元素的值均大于第一个子表中元素的值）。
分块查找
--分块查找的过程：先确定待查记录所在的子表（可以用折半查找或顺序查找），再在子表中顺序查找。

8.2 动态查找

--功能：除静态查找的功能以外，还可以在查找的同时插入表中不存在的元素，或者从表中删除摸个已经存在的元素。
--动态查找表的结构是在查找过程中动态生成的，若表中存在与给定值相等的记录，则查找成功返回，否则在表中插入值等于给定值的元素。

8.2.1 二叉排序树

--二叉排序树：空树，或者有以下性质的二叉树：1.若左子树不为空，则左树上所有结点的值均小于根结点的值；2.若右子树不为空，则右树上所有的结点均大于根结点的值；3.其左右子树也为二叉排序树。
查找
--查找过程：1.判断给定值与根结点是否相同，相同则返回；2.若小于根结点，则进入左树进行查找；3.若大于根结点则进入右树进行查找（递归方法）。
插入
--新插入的结点一定是叶子结点，并且是查找不成功时查找路径上最后一个结点的左结点或右结点。如下图：

插入新结点

删除
--1.若删除的结点为叶子结点，则直接删除不影响其他元素。
--2.若删除的结点只有左子树或右子树，则只要将其子树代替该节点的位置即可，如下图。

删除结点-1

--3.若删除的结点既有左子树也有右子树，设需要删除的结点为P，其父节点为F，有两种方式：
---3.1 设P为F的右结点，则令P的右子树为F的右子树，令P的左子树为S的左子树，其中S为P右子树的左树的尽头结点，如下图。

删除结点-3.1

---3.2 用P的直接前驱或直接后驱代替P，然后再从二叉树中删去他的直接前驱或直接后驱（迭代方法），如下图。

删除结点-3.2

8.2.2 平衡二叉树

--二叉树的结构不唯一，若为单支树，则查找效率最低，因此构造二叉树时需要进行平衡化。
--平衡二叉树：其左子树和右子树的深度之差的绝对值不超过1，且他的左子树和右子树都为平衡二叉树。
--平衡化过程中有4种调整方法：单向左旋、单向右旋、先左旋再右旋、先右旋再左旋，如下图。