数据结构

第一章：数据结构

基本概念

定义

• 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

逻辑结构

• 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的
• 数据的逻辑结构分为线性结构和非线性结构
  • 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 类似于数学上的集合
  • 线性结构 结构中的数据元素之间只存在一对一的关系。比如排队
  • 树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
  • 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 比如地图

物理结构

• 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
  • 顺序存储：存储的物理位置相邻。（p.s. 物理位置即信息在计算机中的位置。）
  • 链接存储：存储的物理位置未必相邻，通过记录相邻元素的物理位置来找到相邻元素。
  • 索引存储：类似于目录，以后可以联系操作系统的文件系统章节来理解。
  • 散列存储：通过关键字直接计算出元素的物理地址（以后详解）。

算法的五个特征

• 1，有穷性：有限步之后结束
• 2，确定性：不存在二义性，即没有歧义
• 3，可行性：比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。
• 4，输入：能被计算机处理的各种类型数据，如数字，音频，图像等等。
• 5，输出：一至多个程序输出结果。

算法的复杂度

• 时间复杂度：
  • • 它用来衡量算法随着问题规模增大，算法执行时间增长的快慢；
  • • 是问题规模的函数：T(n)是时间规模函数 时间复杂度主要分析T(n)的数量级
  • • T(n)=O(f(n)) f(n)是算法中基本运算的频度 一般我们考虑最坏情况下的时间复杂度
• 空间复杂度：
  • • 它用来衡量算法随着问题规模增大，算法所需空间的快慢；
  • • 是问题规模的函数：S(n)=O(g(n)) ；算法所需空间的增长率和g(n)的增长率相同。

概要: 复杂度计算为重点

• 常用的时间复杂度大小关系：
• 复杂度如何计算
  • 时间复杂度计算（单个循环体）
    • 直接关注循环体的执行次数，设为k
  • 时间复杂度计算（多个循环体）
    • 两个运算规则：乘法规则，加法规则。

第二章：线性表

线性表的逻辑结构

• 定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。其中n为表长。当n=0时 线性表是一个空表
• 特点：线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。
  除第一个元素外，每个元素有且仅有一个直接前驱。
  除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的顺序存储结构

• 线性表的顺序存储又称为顺序表。
  它是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素，从而使得逻
  辑上相邻的两个元素在物理位置上也相邻。
• 建立顺序表的三个属性:
  1.存储空间的起始位置（数组名data）
  2.顺序表最大存储容量（MaxSize）
  3.顺序表当前的长度（length）
• 其实数组还可以动态分配空间，存储数组的空间是在程序执行过程中通过动态存储分配语句分配
• 总结：
  • 1.顺序表最主要的特点是随机访问（C语言中基于数组），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
  • 2.顺序表的存储密度高，每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系（因为物理位置相邻特性决定）
  • 3.顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表的操作

• 1.插入
  • 算法思路：
    • 1.判断i的值是否正确
    • 2.判断表长是否超过数组长度
    • 3.从后向前到第i个位置，分别将这些元素都向后移动一位
    • 4.将该元素插入位置i 并修改表长
  • 代码
  • 分析：
    • 最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)。
    • 最坏情况：在表头插入（即i=1），元素后移语句将执行
      n次，时间复杂度为O(n)。
    • 平均情况：假设pi（pi=1/(n+1) ）是在第i个位置上插入
      一个结点的概率，则在长度为n的线性表中插入一个结
      点时所需移动结点的平均次数为
• 2.删除
  • 算法思路：
    • 1.判断i的值是否正确
    • 2.取删除的元素
    • 3.将被删元素后面的所有元素都依次向前移动一位
    • 4.修改表长
  • 代码
  • 分析
    • 最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)。
    • 最坏情况：删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)。
    • 平均情况：假设pi(pi=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为

线性表的链式存储结构

• 线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。
• 头结点和头指针的区别？
  • 不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息
• 为什么要设置头结点？
  • 1.处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了
  • 2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

单链表的操作

• 1.头插法建立单链表：
  • 建立新的结点分配内存空间，将新结点插入到当前链表的表头
  • 代码
• 2.尾插法建立单链表：
  • 建立新的结点分配内存空间，将新结点插入到当前链表的表尾
  • 代码
• 3.按序号查找结点
  • 在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL。
  • 代码
• 4.按值查找结点
  • 从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。
  • 代码
• 5．插入
  • 插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。
  • 算法思路：
    1.取指向插入位置的前驱结点的指针
    ① p=GetElem(L,i-1);
    2.令新结点s的指针域指向p的后继结点
    ② s->next=p->next;
    3.令结点p的指针域指向新插入的结点s
    ③ p->next=s;
• 6．删除
  • 删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。
  • 算法思路：
    1.取指向删除位置的前驱结点的指针 p=GetElem(L,i-1);
    2.取指向删除位置的指针 q=p->next;
    3.p指向结点的后继指向被删除结点的后继 p->next=q->next
    4.释放删除结点 free(q);

双链表

• 定义
• 1.插入：(方法不唯一)
  ① s->next=p->next;
  ② p->next->prior=s;
  ③ s->prior=p;
  ④ p->next=s;
• 2.删除：
  ① p->next=q->next;
  ② q->next->prior=p;
  ③ free(q);

循环链表&&静态链表

• 循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环
• 循环双链表：类比循环单链表，循环双链表链表区别于双链表就是首尾结点构成环
  • 当循环双链表为空表时，其头结点的prior域和next域都等于Head。
• 静态链表：静态链表是用数组来描述线性表的链式存储结构。
  • 数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。链表最后一个元素的指针域值为-1。
  • 例子

第三章：栈和队列

栈

• 栈（Stack）：只允许在一端进行插入或删除操作的线性表。
• 栈顶（Top）：线性表允许进行插入和删除的那一端。
• 栈底（Bottom）：固定的，不允许进行插入和删除的另一端
• 特点：
  1.栈是受限的线性表，所以自然具有线性关
  系。
  2.栈中元素后进去的必然先出来，即后进先出
  LIFO（Last In First Out）
  • 栈中元素后进
    去的必然先出
    来，即后进先
    出LIFO（Last In
    First Out）
• 顺序栈
  • 栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作顺序栈。
  • 顺序栈的操作
    • 1.判空：
    • 2.进栈：
    • 3.出栈：
    • 4.读取栈顶元素：
• 共享栈
  • 顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享
  • 示意图
  • 共享栈的结构
  • 共享栈的操作：（进栈）
• 链式栈
  • 栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈。
  • 特点
    1.链栈一般不存在栈满的情况。
    2.空栈的判定条件通常定为top==NULL；
  • 结构
  • 链式栈的操作
    • 1.进栈
    • 2.出栈

队列

• 队列是只允许在一端进行插入，而在另一端进行删除的线性表
• 队头（Front）：允许删除的一端，又称为队首。
• 队尾（Rear）： 允许插入的一端。
• 先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO
• 顺序队列
  • 用数组来实现队列，可以将队首放在数组下标为0的位置。
• 循环队列
  • 把数组“掰弯”，形成一个环。Rear指针到了下标为4的位置还能继续指回到下标为0的地方。这样首尾相连的顺序存储的队列就叫循环队列
  • 入队：rear=(rear+1)%MaxSize
  • 出队：front=(front+1)%MaxSize
  • 循环队列的操作
    • 1.入队：
    • 2.出队：
  • 概要: 那如何分辨队列是空还是满呢？
    • 方法一：设置标志位flag，当flag=0且rear等于front时为队列空，当flag=1且rear等于front时为队列满。
    • 方法二：我们把front=rear仅作为队空的判定条件。当队列满的时候，令数组中仍然保留一个空余单元。我们认为这种情况就是队列满了。
• 链式队列
  • 队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。
  • 为了方便操作，我们分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点。
  • 链式队列的操作

    • 1.入队：我们知道队列只能从队尾插入元素，队头删除元素。于是入队就是在队尾指针进行插入结点操作。链队的插入操作和单链表的插入操作是一致的。

    • 2.出队：出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点。

• 双端队列
  • 双端队列是指允许两端都可以进行入队和出队操作的队列

栈的应用

• 1、括号匹配：假设有两种括号，一种圆的()，一种方的[]，嵌套的顺序是任意的。

  • 算法思想：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。

  • 代码

• 2、表达式求值：
  *
  • 规则：从左到右扫描表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈然后跟这个符号进行运算，最后将运算结果进栈，直到最终获得结果。
• 3、递归：
  • 要理解递归，你要先理解递归，直到你能理解递归。
    如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构称为是递归定义的，简称递归。递归最重要的是递归式和递归边界。
  • 1.阶乘
    • 时间复杂度：O(NlogN)
  • 2.斐波那契数列
    • 时间复杂度 O(2^n)
• 概要: 如何将中缀表达式转换成后缀表达式？
  • 1.按运算符优先级对所有运算符和它的运算数加括号。(原本的括号不用加)
  • 2.把运算符移到对应的括号后。
  • 3.去掉括号。
  • 例子

第四章：树

树的基本概念

• 树是递归定义的结构
• 结点
  • 根节点：树只有一个根结点
  • 结点的度：结点拥有的子树的数量
    • 度为0：叶子结点或者终端结点
    • 度不为0：分支结点或者非终端结点
      • 分支结点除去根结点也称为内部结点
• 树的度：树中所有结点的度数的最大值
• 结点关系
  • 祖先结点
    • 根结点到该结点的唯一路径的任意结点
  • 子孙结点
  • 双亲结点
    • 根结点到该结点的唯一路径上最接近该结点的结点
  • 孩子结点
  • 兄弟结点
    • 有相同双亲结点的结点
• 层次，高度，深度，树的高度
  • 层次：根为第一层，它的孩子为第二层，以此类推
  • 结点的深度：根结点开始自顶向下累加
  • 结点的高度：叶节点开始自底向上累加
  • 树的高度（深度）：树中结点的最大层数
• 树的性质
  • 1.树中的结点数等于所有结点的度数加1。
    • 证明：不难想象，除根结点以外，每个结点有且仅有一个指向它的前驱结点。也就是说每个结点和指向它的分支一一对应。
      假设树中一共有b个分支，那么除了根结点，整个树就包含有b个结点，所以整个树的结点数就是这b个结点加上根结点，设为n，则n=b+1。而分支数b也就是所有结点的度数，证毕。
  • 2.度为m的树中第i层上至多有m^(i−1)个结点（i≥1）。
    • 证明：（数学归纳法）
      首先考虑i=1的情况：第一层只有根结点，即一个结点，i=1带入式子满足。
      假设第i-1层满足这个性质，第i-1层最多有m i-2个结点。
      ……… ..........
      i-1层
      ………
      又因为树的度为m,所以对于第i-1层的每个结点，最多
      有m个孩子结点。所以第i层的结点数最多是i-1层的m
      倍，所以第i层上最多有m ^(i-1)个结点。
  • 3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
  • 4.具有n个结点的m叉树的最小高度为logm(n(m-1)+1)

树的存储结构

• 顺序存储结构
  • 双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置。
• 链式存储结构

  • 孩子表示法：把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就有n个链表；
    如果是叶子结点，那这个结点的孩子单链表就是空的；
    然后n个单链表的的头指针又存储在一个顺序表（数组）中。

  • 孩子兄弟表示法：顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结
    点的第一个孩子结点和这个孩子结点的右兄弟结点。

二叉树

• 定义
  • 二叉树是n（n≥0）个结点的有限集合：
    ① 或者为空二叉树，即n=0。
    ② 或者由一个根结点和两个互不相交的被称为根的左子树
    和右子树组成。左子树和右子树又分别是一棵二叉树。
    • 1.每个结点最多有两棵子树。
    • 2.左右子树有顺序
• 二叉树的五种基本形态：
  • 1.空树
  • 2.只有一个根结点
  • 3.根结点只有左子树
  • 4.根结点只有右子树
  • 5.根结点既有左子树又有右子树
• 特殊二叉树
  • 1.斜树
  • 2.满二叉树:
  • 3.完全二叉树
• 二叉树的性质
  • 1.非空二叉树上叶子结点数等于度为2的结点数加1
  • 2.非空二叉树上第K层上至多有2^k−1个结点（K≥1）
  • 3.高度为H的二叉树至多有2^H-1个结点（H≥1）
  • 4.具有N个（N>0）结点的完全二叉树的高度为 [log2(N+1)]或[log2N] +1。

二叉树的存储结构

• 顺序存储
  • 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
• 链式存储
  • 二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。

二叉树的遍历

• 先序遍历：
  1）访问根结点；
  2）先序遍历左子树；
  3）先序遍历右子树。
  • 递归
  • 非递归
• 中序遍历：
  1）中序遍历左子树；
  2）访问根结点；
  3）中序遍历右子树。
  • 递归
  • 非递归
• 后序遍历：
  1）后序遍历左子树；
  2）后序遍历右子树；
  3）访问根结点。
  • 递归
  • 非递归
• 层次遍历：
  若树为空，则什么都不做直接返回。
  否则从树的第一层开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

线索二叉树

• N个结点的二叉链表，每个结点都有指向左右孩子的
  结点指针，所以一共有2N个指针，而N个结点的二叉
  树一共有N-1条分支，也就是说存在2N-(N-1)=N+1个空指针。比如左图二叉树中有6个结点，那么就有7个空
  指针。

• 大量的空余指针能否利用起来？

  • 指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
  • 对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化

哈夫曼树和哈夫曼编码

• 算法的描述如下：
  1）将这N个结点分别作为N棵仅含一个结点的二叉树，构成森林F。
  2）构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值
  置为左、右子树上根结点的权值之和。
  3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
  4）重复步骤2）和3），直至F中只剩下一棵树为止。