【转帖】数据结构复习笔记

huangyhg

数据结构复习笔记
Chapter 1 线性表

线性表的逻辑结构

逻辑结构

逻辑定义
    　线性表（Linear List）是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。
   　 ① 数据元素的个数n定义为表的长度（n=0时称为空表）。
    　② 将非空的线性表（n＞0）记作：（a1，a2，…，an）
    　③ 数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。

逻辑结构特征
　　对于非空的线性表:
    　① 有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；
   　 ② 有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；
    　③ 其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个ai+1。

顺序存储结构

顺序表

顺序表的定义
(1) 顺序存储方法
　    即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
(2) 顺序表（Sequential List）
　    用顺序存储方法存储的线性表简称为顺序表（Sequential List）。

结点ai 的存储地址：LOC（ai）= LOC（a1）+（i-1）*c   1≤i≤n （每个结点所占用存储空间大小亦相同，占用c个存储单元）
顺序表上的基本运算

链式存储结构

单链表

链接方式存储的线性表简称为链表（Linked List）。
    　链表的具体存储表示为：
　　① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
　　② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
单链表的运算

1、建立单链表：（1） 头插法建表（2） 尾插法建表（3）尾插法建带头结点的单链表

2、单链表的查找运算：（1）按序号查找（2） 按值查找

3、插入运算 4、删除运算
循环链表 循环链表是一种首尾相接的链表。

1、循环链表
（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。
（2）多重链的循环链表——将表中结点链在多个环上。

2、带头结点的单循环链表

3、仅设尾指针的单循环链表
    　用尾指针rear表示的单循环链表对开始结点a1和终端结点an
双链表

双向链表（Double Linked List）
    　双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
顺序表和链表的比较

分配方式：

前者：静态分配；后者：动态分配

存取方式：

     前者：随机存取；后者：顺序存取（扫描）

插入或删除操作：

     前者：需要移动近一半的节点；后者：只需要修改指针



Chapter 2栈与队列

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表

栈

栈的定义及基本运算

1、栈的定义
    　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
　　(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
　　(2)当表中没有元素时称为空栈。
　　(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。

2、栈的基本运算
（1）InitStack（S）
    　构造一个空栈S。
（2）StackEmpty（S）
    　判栈空。若S为空栈，则返回TRUE，否则返回FALSE。
（3）StackFull（S）
    　判栈满。若S为满栈，则返回TRUE，否则返回FALSE。
注意：
　    该运算只适用于栈的顺序存储结构。
（4）Push（S，x）
    　进栈。若栈S不满，则将元素x插入S的栈顶。
（5）Pop（S）
    　退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
（6）StackTop（S）
    　取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
顺序栈 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

1、 顺序栈的类型定义
  #define StackSize 100 //假定预分配的栈空间最多为100个元素
  typedef char DataType;//假定栈元素的数据类型为字符
  typedef struct{
      DataType data[StackSize];
      int top;
     }SeqStack;
  注意：
　    ①顺序栈中元素用向量存放
    　②栈底位置是固定不变的，可设置在向量两端的任意一个端点
    　③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
2、 顺序栈的基本操作
  前提条件：
    　设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-＞data[0]是栈底元素。
（1） 进栈操作
    　进栈时，需要将S-＞top加1
  注意：
　    ①S-＞top==StackSize-1表示栈满
　　②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。
      上溢是一种出错状态，应设法避免。
（2） 退栈操作
    　退栈时，需将S-＞top减1
  注意：
　    ①S-＞top<0表示空栈
    　②"下溢"现象——当栈空时，做退栈运算产生的溢出现象。
      下溢是正常现象，常用作程序控制转移的条件。
顺序栈在进栈和退栈操作时的具体变化情况【参见动画演示】
3、顺序栈的基本运算
（1） 置栈空
  void InitStack（SeqStack *S）
    {//将顺序栈置空
        S->top=-1;
    }
（2） 判栈空
  int StackEmpty（SeqStack *S）
    {
        return S->top==-1;
    }
（3） 判栈满
  int StackFull（SeqStack *SS）
     {
       return S->top==StackSize-1;
     }
（4） 进栈
  void Push（S，x）
     {
       if (StackFull(S))
             Error("Stack overflow"); //上溢，退出运行
       S->data[++S->top]=x;//栈顶指针加1后将x入栈
     }
（5） 退栈
  DataType Pop（S）
    {
      if(StackEmpty(S))
           Error("Stack underflow"); //下溢，退出运行
      return S->data[S->top--];//栈顶元素返回后将栈顶指针减1
    }

（6） 取栈顶元素
  DataType StackTop（S）
    {
       if(StackEmpty(S))
           Error("Stack is empty");
       return S->data[S->top];
     }
链栈 栈的链式存储结构称为链栈。

2、链栈的基本运算
（1） 置栈空
      Void InitStack(LinkStack *S)
      {
             S->top=NULL;
      }
（2） 判栈空
      int StackEmpty(LinkStack *S)
      {
            return S->top==NULL;
      }
（3） 进栈
      void Push(LinkStack *S,DataType x)
      {//将元素x插入链栈头部
            StackNode *p=(StackNode *)malloc(sizeof(StackNode));
            p->data=x;
            p->next=S->top;//将新结点*p插入链栈头部
            S->top=p;
       }
（4） 退栈
      DataType Pop(LinkStack *S)
      {
            DataType x;
            StackNode *p=S->top;//保存栈顶指针
            if(StackEmpty(S))
                  Error("Stack underflow.");  //下溢
            x=p->data;  //保存栈顶结点数据
            S->top=p->next;  //将栈顶结点从链上摘下
            free(p);
            return x;
       }
（5） 取栈顶元素
      DataType StackTop(LinkStack *S)
       {
            if(StackEmpty(S))
                 Error("Stack is empty.")
             return S->top->data;
        }

队列　

队列的定义及基本运算

1、定义
    　队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

（1）允许删除的一端称为队头（Front）。
　　（2）允许插入的一端称为队尾（Rear）。
　　（3）当队列中没有元素时称为空队列。
　　（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
顺序队列

（1）顺序队列的定义
　 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2） 顺序队列的表示
　　①和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。
　　②由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。

（3） 顺序队列的基本操作
　　①入队时：将新元素插入rear所指的位置，然后将rear加1。
　　②出队时：删去front所指的元素，然后将front加1并返回被删元素。

2、循环队列
    　为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
链队列

1、 链队列的定义
  　队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

2、 链队列的基本运算

栈和队列的应用实例

栈的应用实例
队列的应用实例



Chapter 3 串

串及其运算

串的基本概念：串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。
串的基本运算

1、求串长
        int strlen(char *s);//求串s的长度
    【例】printf("%d",strlen(s1)); //输出s1的串长12
2、串复制
    char *strcpy(char *to,*from)；//将from串复制到to串中，并返回to开始处指针
    【例】strcpy(s3,s1);  //s3="dir/bin/appl",s1串不变
3、联接
    char *strcat(char *to,char *from);//将from串复制到to串的末尾，
                                      //并返回to串开始处的指针
    【例】strcat(s3,"/"); //s3="dir/bin/appl/"
            strcat(s3,s2); //s3="dir/bin/appl/file.asm"
4、串比较
    int strcmp(char *s1,char *s2);//比较s1和s2的大小，
   //当s1<s2、s1>s2和s1=s2时，分别返回小于0、大于0和等于0的值
    【例】result=strcmp("baker","Baker");  //result>0
            result=strcmp("12","12");  //result=0
            result=strcmp("Joe","joseph")  //result<0
5、字符定位
    char *strchr(char *s,char c);//找c在字符串s中第一次出现的位置，
                                 //若找到，则返回该位置，否则返回NULL
    【例】p=strchr(s2,'.'); //p指向"file"之后的位置
　　　　　　if(p) strcpy(p,".cpp"); //s2="file.cpp"

串的存储结构

串的顺序存储：串的顺序存储结构简称为顺序串。静态存储分配和动态存储分配
串的链式存储：用单链表方式存储串值，串的这种链式存储结构简称为链串。
串运算的实现

Chapter 4 多维数组

多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。

多维数组

多维数组

多维数组
1、数组（向量）——常用数据类型
    　一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。
    　同一数组的不同元素通过不同的下标标识。（a1,a2,…,an)
2、二维数组
    　二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。

矩阵的压缩存储

矩阵的存储

1、矩阵的二维数组描述
    　矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。
2、矩阵的压缩存储
   　 矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
特殊矩阵

1．对称矩阵
（1）对称矩阵
    　在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≤i，j≤n-1则称A为对称矩阵

（2）三角矩阵的划分
    　以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
①上三角矩阵　如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。
②下三角矩阵　与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。

（3）对角矩阵
    　所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。
稀疏矩阵 设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，则称A为稀疏矩阵。

其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。

稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储

Chapter 5 广义表

广义表

广义表的概念：广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
  其中：
    　①ai--或者是原子或者是一个广义表。②广义表通常记作：Ls=( a1，a2，…，ai，…，an)。③Ls是广义表的名字，n为它的长度。④若ai是广义表，则称它为Ls的子表。

Chapter 6 树

树的概念

概念 树的递归定义：
      树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
(1)有且仅有一个特定的称为根(Root)的结点；
(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。

1、树的表示：

（1）树形图表示（2）嵌套集合表示法（3）凹入表表示法（4）广义表表示法

2、树结构的基本术语：

（1）结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的度(Degree)。一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子(Leaf)或终端结点。度不为零的结点称分支结点或非终端结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。

（2）孩子(Child)和双亲(Parents) 树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。

（3）路径（path） 若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径(Path)或道路。路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。

（4）祖先(Ancestor)和子孙(Descendant) 若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。

（5）结点的层数(Level)和树的高度（Height）根的层数为1， 其余结点的层数等于其双亲结点的层数加1。双亲在同一层的结点互为堂兄弟。树中结点的最大层数称为树的高度(Height)或深度(Depth)。

（6）有序树(OrderedTree)和无序树(UnoderedTree) 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树；否则称为无序树。

（7）森林(Forest) 森林(Forest)是m(m≥0)棵互不相交的树的集合。

二叉树

二叉树的定义

1.二叉树的递归定义
    　二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的性质

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

满二叉树和完全二叉树是二叉树的两种特殊情形。

满二叉树(FullBinaryTree) 一棵深度为k且有2k-1个结点的二又树称为满二叉树。

完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

性质4  具有n个结点的完全二叉树的深度为
二叉树的存储结构

顺序存储结构  该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。

链式存储结构  二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。

二叉树的遍历

二叉树的遍历 遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
    　（1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。

三种遍历的命名
    　根据访问结点操作发生位置命名：
　　① NLR：前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前。
　　② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。
　　③ LRN：后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后

遍历序列：1．遍历二叉树的执行踪迹　三种递归遍历算法的搜索路线相同（如下图虚线所示）。  

二叉链表的构造

线索二叉树

线索二叉树

n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。

ltag和rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。

线索化：按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。

线索二叉树的运算：

1．   查找某结点*p在指定次序下的前趋和后继结点

2．遍历线索二叉树

树和森林

树、森林和二叉树的转换

（1）将树转换为二叉树
    　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：
　　①在所有兄弟结点之间加一连线；
　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。

（2）将一个森林转换为二叉树
具体方法是：
　　① 将森林中的每棵树变为二叉树
　　② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。

（3）把二叉树转换到树和森林

方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。
树的存储结构

1、   双亲链表表示法：在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parent，惟一地表示任何-棵树。

2、   孩子链表表示法：孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。

3、  孩子兄弟链表表示法 : 在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。
树和森林的遍历

树的遍历

1．树T的前序遍历定义：若树T非空，则：①访问根结点R；②依次前序遍历根R的各子树T1，T2，…，Tk。

2．树T的后序遍历定义：若树T非空，则：①依次后序遍历根T的各子树Tl，T2，…，Tk；②访问根结点R。

森林的两种遍历方法

1．前序遍历森林
    若森林非空，则：①访问森林中第一棵树的根结点；②前序遍历第一棵树中根结点的各子树所构成的森林③前序遍历除第一棵树外其它树构成的森林。

2．后序遍历森林
　　若森林非空，则:①后序遍历森林中第一棵树的根结点的各子树所构成的森林；②访问第一棵树的根结点；③后序遍历除第一棵树外其它树构成的森林。

哈夫曼树及其应用

最优二叉树
哈夫曼编码