数据结构

stvsl 2022-6-22 2,637 6/22

此文档为个人数据结构学习笔记(写着写着快变成书了),对应课程内容为严蔚敏的C语言数据结构课程(B站BV号为BV1ns411r7Cn)可配合视频使用(严蔚敏yyds!!!),因此内容举例代码均为C代码(含伪代码),部分内容完成了与java等其他语言对接(均按照对应的C实现书写),但请注意,笔记内容可能存在个人主观理解和解释方便阅读,此外其体系内的知识量相当大且复杂,而且晦涩难懂,内容偏向底层,建议用于深入学习和理解计算机,并不适用于应对考试,因此,请作为活的知识点来深入理解数据结构而非考试用资料来使用 !!!

1. 绪论

1.1 数据结构讨论的范畴

算法 + 数据结构 = 程序设计

​ 程序设计:为计算机处理问题编制一组指令集

​ 算法:处理问题的策略

​ 数据结构:问题的数学模型

​ 纯数字计算问题模型:

​ eg:

​ 1.结构静力分析计算转变为 线性代数方程组

​ 2.全球天气预报转变为球坐标下的一般环流模式方程

​ 非数字计算问题模型:

​ eg:

​ 1.求一组整数中的最大值,其算法的基本操作是比较两个数的大小,而数学模型问题是因计算机整形数据范围造成的问题,即如何表示数据以及边界

​ 2.人机下棋对弈问题,其算法的主要问题是对弈的规则和策略,而其数学问题则是如何去表示棋盘和棋子

​ 3.为足协编写一个数据库的管理程序,其算法问题是需要管理的项目是什么,如何管理(如条例,规则,需求是什么),如何设计用户界面逻辑,而数学模型则是各种的数据表格和数据库

综合各种程序设计问题,可以知道抽取问题的各种物理含义,就可以的到几类数学模型如和数学计算相关的数学模型,如线性代数方程,非线性代数方程,常微分方程等等,它们的数字解问题,就是计算数学要研究的问题,类似的,非数字求解问题,它们的数学模型表示和求解的方法就是数据结构所要研究的内容,所以数据结构所讨论的是描述现实世界实体的数学模型(非数值计算)及其的操作在计算机中的表示的方法和实现

1.2 基本概念

​ 常见的名词和俗语以及相关定义和基本概念

  1. 数据和数据结构

    数据 : 所有能被输入到计算机中,且能被计算机处理的所有符号的集合,即对计算机可以操作的内容的总称,是计算机处理的信息的载体,是信息的一种特定的符号表示形式,因此其包含的内容在随着计算机的发展而逐步扩大,如声音,图像,视频等多媒体信息

    数据元素 :数据中的每个个体,也是数据结构问题讨论中的基本单位(但不是最小单位),因为其小到可以是一个字符,一个数,大到可以由多个数据项共同组成用以描述某个现实中的某个事物

    数据项 :数据结构中的最小单位,数据元素是数据项的集合,例如在构建一个人的信息时,其人的信息可以有身高,体重,性别,名称,出生日期等等而出生日期分为年月日,因此它是由三个数据组成的,被称为组合项

    数据结构 :数据结构是带结构的数据元素的集合,这里的结构指的是数据之间存在的各种约束和包含关系,例如一个12位的十进制数可以用三个四位的十进制数来表示或者使用一个2行3列的二维数组来表示等等,但无论哪一种表示方式,其中都会产生次序关系以保证数据的正确,在或者在一维数组中存在次序关系,例如
    $$

    \left{
    \begin{matrix}
    a1,a2,a3,a4,a5,a6
    \end{matrix}
    \right}
    中存在以下关系:
    \left{
    \begin{matrix}
    <ai,ai+1>|i=1,2,3,4,5
    \end{matrix}
    \right}
    $$

    通常,数据的结构有以下四类:

    • 线性结构(序列)
    • 树形结构
    • 图状结构(网状关系)
    • 集合结构(与数学中的集合概念相同),其中的数据项之间没有任何关系的一种,这种没有关系在某种程度上也是一种关系,如一个人的名和姓,相互之间没有本质关系,但也有关系

    数据结构的形式定义:

    ​ 数据结构是一个二元组,即Data_Structures=(D,S),其中,D是数据元素的有限集,S是D上关系的有限集

    ​ 严格的讲,这个形式定义只是说明了数据结构的一个方面,强调的是数据元素间的逻辑关系,由于数据结构是计算机操作的对象,实际上还需要有相应的存储内容,因此还有另一个方面,即数据的存储结构,因此,数据结构的形式定义被称为数据的逻辑结构,而数据的存储结构是数据的逻辑结构在存储器中的映像(即逻辑结构在计算机中的表示)

    ​ 此部分可以使用linux的原理进行解释,即在linux中遵循一切皆文件的宗旨,即一切程序,设备,组件在操作系统中均视为文件,即运行过程中数据和存储器中的内容本质上都是文件,而数据在这里也是一样,将会以文件的形式在系统中存在,而数据在此过程中的文件形式分别体现了数据的逻辑结构和存储结构,即在CPU中执行的文件和在存储设备中的文件这两种状态

  2. 映像方法:

    • 数据结构的映像方法:

      ​ 在计算机中使用的是二进制位(bit)的位串来表示数据元素,对于任何一个数均可以使用二进制数实现其在计算机中的表达,这种表达方法就是数据结构的映像方法

    • 关系的映像方法:(表示<x,y>的方法,类似离散数学中的笛卡尔积)

      顺序映像 :

      ​ 以存储位置的相邻表示后继关系(即使用固定的位置关系来表示数据元素之间的关系)例如y的存储位置和x的存储位置之间差一个常量C,而C是一个隐含值,整个存储结构中只含元素本身的信息,即其结构为a1,c,a2,c,a3

      链式映像:

      ​ 以附加信息(指针)表示后继关系(即需要一个和x绑定在一起的附加信息指示y的存储位置),换机话说,这个x的存储映像是一个节点包含两部分信息,其中一部分是数据元素x的映像,第二部分信息是指向后续数据元素所在位置的指针,在不同的编程环境中,存储结构可有不同的描述方法,当用高级程序设计语言进行编程时,可以使用高级编程语言中提供的数据类型描述数据的存储结构

      ​ 例如:以三个带有次序关系的整数表示一个长整数时,可以利用C语言中提供的整数数组类型,定义长整数为

      typedef int Long_int[3]

      ​ 对应java代码为

      int[] Long_int = new int[3]
  3. 数据类型:

    在用强类型高级编程语言编写的程序中,必须对程序中出现的每个变量,常量或表达式,明确声明它们所属的数据类型,以此让编程语言明确其可以被执行的操作,数据的范围信息等,弱类型的可以不对其定义,例如python,只需声名其名称和值即可,类型将由语言内部运行时动态决定,因此数据类型是一个值的集合和定义在此集合上的一组操作的总称,因为数据类型有两种,简单型和结构类型(对应java为基本数据类型和引用数据类型),对于结构类型,例如数组,它的内部值可以分割且相互独立,因此可以看作是一个集合,所以数据类型也可以看成是一个数据结构(对应java的数组对象的单元数据独立性),和定义在数据结构上的一组操作的总称,即数据类型=数据结构+操作集合

  4. 抽象数据类型(ADT)

    抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作

    ADT的两个重要特征:

    • 数据抽象

      当用抽象数据类型来描述现实世界的实体的时候,强调的是它本质上的特征和能实现的功能以及外部用户的接口,因此将会忽略与之无关的外部属性,而描述的外部用户的接口使得外部用户能够正确的使用它们

    • 数据封装

      将实体的外部特性与其内部实现相分离,并对外部用户隐藏其内部实现的细节,即将原本复杂的计算机内部实现方法隐藏,使得上级用户可以无需在意相关的实现过程和原理,从而能够专注于应用以及使用的过程上

    抽象数据类型的描述方法:

    抽象数据类型可用(D,S,P)三组元素表示,其中,D是数据对象即具有相同特性的数据元素的集合,S是D上的关系集(D+S就是数据结构),P是定义在D上的基本操作集,也就是说数据结构和定义在数据结构上的操作实质上是一个整体(此部分内容对应java的抽象类)

    ADT抽象数据类名{
       数据对象:<数据对象的定义>
       数据关系:<数据关系的定义>
       基本操作:<基本操作的定义>
    }ADT抽象数据类型名
    
    其中,数据对象和数据关系的定义使用伪码描述,基本操作的定义格式为
    基本操作名(参数表)
       初始条件:<初始条件的描述>
       操作结果:<操作结果的描述>

    抽象数据类型的表示和实现

    抽象数据类型需要借助固有数据类型(编程语言中已经实现的数据类型)来表示和实现(对应java中的自定义类和泛型的综合实现)

1.3 算法及其度量

  1. 算法

    算法是为了解决某类问题而规定的一个有限长的操作序列,即解决某个实际问题的一种描述,一个算法必须满足以下五个重要特性

    • 有穷性 :对于任何一组合法输入值,在执行有穷步骤之后一定能结束,即算法中的每个步骤都能在有限(合理)时间内完成
    • 确定性 :对于每一种在运行时可能发生的问题在算法里都有确切的解决方案,使算法的执行着和阅读者都能明确其含义和如何执行,并在任何条件下,算法都有且仅有唯一的一条可执行路径
    • 可行性 :算法是一个有限的操作序列,那么每一个操作都必须足够基本,都可以通过已经实现的基本操作的有限次执行实现
    • 有输入 :作为算法加工的对象的量值通常体现为算法中的一组变量,有些输入需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上相关的输入已被嵌入算法当中
    • 有输出 :它是一组与输入确定关系的量值,是算法进行信息加工后得到的结果,这种确定的关系即为算法的功能(没有输出就等于是白干了)
  2. 算法的设计原则

    • 正确性 :

      算法应该满足以特定的“规格说明”方式给出的需求,其次,对算法是否正确的理解可以有以下4个层次:

      • 程序中不含语法错误(简单)
      • 程序对于输入的数据能得到满足需求的结果(较简单)
      • 对于精心选择的典型,苛刻的带有刁难性的几组数据的输入要有能返回够满足要求的结果(考虑到特殊情况的发生时的处理)(有点难)
      • 程序对于一切合法的输入数据都能的出满足要求的结果(很难)
    • 可读性 :

      算法主要是为了人的阅读与交流,其次才是计算机的执行,因此算法应该易于人的理解,另一方面,晦涩难懂的程序易于隐藏较多的错误而难以调试

    • 健壮性(即抗异常能力) :

      当输入的数据非法时,算法应恰当的做出反应或者进行相应处理(即异常处理),并且,处理出错的方法不应该是中断程序的执行,而且应该是返回一个错误信息或表示错误性质的值,以便在更高的抽象层次上进行异常处理

    • 高效率与低存储量需求 :

      通常,效率指的是算法执行的时间,存储量指的是算法执行过程中所需的最大存储空间,两者都与需要解决的问题的大小有关

  3. 算法效率的衡量方法与准则(时间复杂度)

    两种方法:事后统计法和事前分析估算法(事后统计法缺点:必须先执行代码,其他因素容易掩盖算法的本质问题)

    和算法执行时间相关的因素:

    • 算法选用的策略(即解决问题的思路)
    • 问题的规模
    • 编写程序的语言(不同编程语言的适用性和优势不同,且往往高级语言的执行时间比汇编语言的执行时间要长)
    • 编译程序产生的机器代码的质量(编译器对代码编译时的优化问题)
    • 计算机执行指令的速度(计算机的性能问题)

    一个算法的运行工作量的大小,只依赖于问题的规模(通常用整数量n表示),假如随着规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可以记作
    $$
    T{(n)}=O(f{(n)})\quad\quad\quad其中,T_{(n)}称为算法的(渐进)时间复杂度
    $$
    一般情况下,默认讨论的时间复杂度均是指最坏时间复杂度(即最长的时间复杂度)且只考虑n无穷大的情况

    此时可将算法理解为: 算法 = 控制结构 + 原操作(固有数据类型的操作)

    执行时间计算公式:
    $$
    算法的执行时间 = \Sigma原操作(i)的执行次数 * 原操作(i)的执行时间(实际场合下往往此部分被忽略掉)
    $$
    计算方法:从算法中选取一种属于基本操作的原操作,以该基本操作在算法中重复执行的次数作为算法运行的时间的衡量准则

    例如矩阵乘法的计算(通用代码)的时间复杂度为 $O_{(n^3)}$​

    /***
    示例代码如下,此代码不针对编程语言,如想要尝试请自行根据内部逻辑书写对应语言的代码
    a[i,j],b[i,j],c[i,j]分别是三个矩阵(使用二维数组表示),n分别表示数组在一维空间和二维空间的长度
    ***/
    for(int i = 0;i < n;++i){
       for(int j = 0;j <= n;++j){
           c[i,j] = 0;
           for(int k = 1;k <= n;++k){
               c[i,j] += a[i;k] * b[k,j];
           }
       }
    }

    选择排序(通用代码)的时间复杂度为$O_{(n^2)}$

    /***
    示例代码如下,此代码不针对编程语言,如想要尝试请自行根据内部逻辑书写相应语言的代码
    a[]是一个用于存储数据的数组,n表示数组的长度
    ***/
    int j
    for(int i = 0;i < n-1;++i){
       j = i;
       for(int k = i+1;k < n;++k){
           if(a[k] < a[i]){
               j = k;
           }
           if(j != i){
               /*异或交换法实现数据的值的互换,若无特殊问题和需求,本文档全程使用异或交换实现数据值的互换*/
               a[i] = a[i] ^ a[j];
               a[j] = a[i] ^ a[j];
               a[i] = a[i] ^ a[j];
           }
       }
    }

    冒泡排序(通用代码)的时间复杂度为$O{(n^2)}$​​​(但其最低时间复杂度为$O{(n-1)}$​)

    /***
    示例代码如下,此代码不针对编程语言,如想要尝试请自行根据内部逻辑书写相应语言的代码
    a[]是一个用于存储数据的数组,n表示数组的长度,flag表示序列的已排序状态
    ***/
    bool flag = true;
    int n2 = n - 1;
    for(int i = 0;i < n2;++i){
       for(int j = 0;j < n2-i && 发;j++){
           flag = false;
           if(a[j] > a[j + 1){
               a[j] = a[j] ^ a[j + 1]]
               a[j + 1] = a[j] ^ a[j + 1]]
               a[j] = a[j] ^ a[j + 1]]
               flag = true;
           }
       }
    }
  4. 算法的存储空间需求(空间复杂度)

    算法的空间复杂度公式:
    $$
    S{(n)}=O(g{(n)})\quad\quad\quad 其中,S_{(n)}称为算法的空间复杂度且只考虑n无穷大的情况
    $$
    其表示随着问题的规模n的增大,算法运行所需的存储量的增长率与g(n)的增长率相同

    算法的存储量所包含的内容:

    • 输入数据所占的空间(在比较算法的时间复杂度的时候可省略此部分,因为输入的数据在不同算法中的大小一般相同,特殊情况下部分算法需要传入经过处理的数据,此时这一部分需要考虑)
    • 程序本身所占的空间
    • 辅助变量所占的空间

    若输入数据所占空间只取决于问题本身而和算法无关,则只需要分析除输入和程序之外的辅助变量所占的额外空间,若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作

    若所需存储量依赖于特定的输入,则通常按照最坏的情况考虑

1.4 语言对接——指针

指针在有些编程语言中被隐藏以防止发生安全性问题和降低开发难度,但也因此导致以下内容中出现的指针使用无法看懂和使用,因此在此粗略介绍指针

首先要知道,计算机中的CPU在执行任务时是如何在内存中寻找所需要的目标内容的,此处可以将内存想象成一个仓库,里面存放着计算机运行时所需要的各种数据,这些数据将会交给CPU处理,此时CPU就需要从内存中获取数据,请思考:CPU应该如何寻找所需要的数据?一个一个数据翻出来筛选吗?显然不可能,那样子会增加大量不必要的资源和时间浪费,就像是寄送快递一样,不可能为了每一个快递全国的挨家挨户的去问和送,那么应该怎么办?那快递是怎么解决这个问题的?一个收寄地址解决的,通过地址精确的实现收寄快递,而计算机中也是同理,内存可以想象成一个个小格子,每个格子里面都存放一个小的数据片段,因此,可以给每个格子分配一个物理内存地址实现精准的读写内存数据,此逻辑亦被操作系统和编程语言所使用,即通过内存地址来访问数据,而这个内存地址就是指针

指针变量就是用来存放内存地址的变量,和其他变量或常量一样,必须在使用指针存储其他变量地址之前,对其进行声明如int *a;(*表示声明这是个指针),此外,所有实际数据类型,不管是整型、浮点型、字符型,还是其他的数据类型,对应指针的值的类型都是一样的,都是一个代表内存地址的长的十六进制数(因为内存地址只需要表示一个位置信息而不需要表示其它任何东西),不同数据类型的指针之间唯一的不同是,指针所指向的变量或常量的数据类型不同

使用用指针时会频繁进行以下几个操作:定义一个指针变量、把变量地址赋值给指针、访问指针变量中可用地址的值,以下为示例代码:

int *a;         //声明一个int型指针a
int b = 20;     //声明一个int 型数据b = 20
a = &b;         //将b的内存地址赋值给a

此处需要注意,a是一个指针,它存储的是b的内存地址,访问a将会得到b的值,但a本身的内存地址与b无关!!!

空指针:

空指针就是被赋值为null的指针,即它指向的内存地址为 0x0,在大多数的操作系统上,程序不允许访问地址为 0 的内存,因为该内存是操作系统保留的,然而,内存地址 0 有特别重要的意义,它表明该指针不指向一个可访问的内存位置,但按照惯例,如果指针包含空值(零值),则假定它不指向任何东西,以此来提高程序的安全性

2. 线性表

线性结构是一个数据的有序集(次序层面上而非数值层面)

线性结构的基本特征:

  1. 集合中必存在唯一的一个“第一元素”
  2. 集合中必存在唯一的一个“最后元素”
  3. 除最后一个元素外,均有唯一的后继
  4. 除第一个元素外,均有唯一的前驱

2.1 线性表的类型定义

抽象数据类型线性表的定义如下:

ADT List{
    数据对象:
        D = {ai|ai 属于ElemSet,i = 1,2,3...n,n>0}
        //n为线性表的表长,当n=0时的线性表称为空表
    数据关系:
        R = {<ai-1,ai>|ai-1,ai属于D,i= 2....n}
        //设线性表为(a1,a2,a3...ai...an)此时称i为a在线性表中的位序
    基本操作
}

基本操作(java与C区别过大,因此此部分两种语言分开,此外具体的原子功能实现省略,请自行编写)

  • 结构的初始化

    InitList(&L);

    操作的结果:构造了一个空的线性表L

  • 销毁结构

    DestroyList(&L)

    初始条件:线性表L已经存在

    操作的结果:销毁线性表L

  • 引用型操作(基础内容使用C代码,代码块中使用java代码,此部分内容java需要使用接口进行定义,除此之外,以下内容中的函数命名均尽量保证与java的源代码一致,除此之外,下面的java代码均使用list作为线性表的类型声明,所有代码均为模块化的代码片段,如需实际测试请自行补全)

    1. 判空 ListEmpty(L)

      初始条件:线性表 L 已存在

      操作结果:若L为空表,则返回TRUE,否则返回FALSE

      /*java代码*/
      public boolean isEmpty();
    2. 元素数查询 ListLength(L)

      初始条件:线性表 L 已存在

      操作结果:返回 L 中元素的个数(长度)

      /*java代码*/
      public int length();
    3. 查询前一个数据元素(查询前驱) PriorElem(L,cur_e,&pre_e)

      初始条件:线性表L已存在

      操作结果:若cur_e是 L 的元素,且不是第一个元素,则pre_e返回它的前驱,否则操作失败,pre_e无意义

    4. 查询后一个数据元素(查询后继)NextElem(L,cur_e,&next_e)

      初始条件:线性表L已存在

      操作结果:若cur_e是 L 的元素,但不是最后一个元素,则pre_e返回它的后继,否则操作失败,next_e无意义

    5. 查询指定的第几个元素 GetElem(L,i,&e)

      初始条件:线性表 L 已存在且 i 在 L 的长度范围内

      操作结果:用 e 返回 L 中第 i 个元素的值

      /*java代码*/
      public Object get(int index) throws Exception;
    6. 查询某个元素的位置 LocaleElem(L,e,compare())

      初始条件:线性表 L 已存在,compare()是元素判定函数

      操作结果:返回元素中第一个与e满足compare()的元素的位序,若不存在则返回值为0

      /*java代码*/
      public int indexOf(object o);
    7. 遍历元素 ListTraverse(L,visit())

      初始条件:线性表 L 已存在

      操作结果:依次对 L 的每个元素调用函数visit(),一旦visit()失败,则操作失败

  • 加工型操作

    1. 清空线性表ClearList(&L)

      初始条件:线性表 L 已存在

      操作结果:将 L 重置为空表

      /*java代码*/
      public void clear(); 
    2. 为元素赋值PutElem(&L,i,&e)

      初始条件:线性表 L 已存在且 i 在 L 的长度范围内

      操作结果:为 L 中第 i 个元素赋予 e 的值

      /*java代码*/
      public Object set(int index,element) throws Exception;
    3. 插入元素 ListInsert(&L,i,e)

      初始条件:线性表 L 已存在且 i 在 L 的长度 -1范围内

      操作结果:在 L 的第 i个元素之前插入新的元素 e ,且 L 的长度自加 1

      /*java代码*/
      public void insert(int index, element) throws Exception;
    4. 删除元素ListDelete(&L,i,e)

      初始条件:线性表 L 已存在且 i 在 L 的长度范围内

      操作结果:删除 L 的第 i 个元素,并用 e 返回其值,L 的长度减 1

      /*java代码*/
      public void remove(int i) throws Exception;

利用线性表 完成复杂工作:

  1. 设有2个集合A 和 B,分别用两个线性表La和Lb表示,现要求集合 La = La U Lb​

    原理:对Lb中的每个元素都在La进行查找,若查找结果为无则将该元素插入(添加)到La里面

    void union (List &La,List Lb){
       int e;
       int La_len = ListLength(La);
       int Lb_len = ListLength(Lb);
       for(int i = 1,i <= Lb_len;++i){
           GetElem(Lb,i,e);             //取Lb中的第i个元素赋值给e(查询La指定位置的元素的值)
           if(!LocaleElem(La,e,equal())){
               ListInsert(La,++la_len,e)    //若La中不存在和e相同的数据元素,则将其插入
           }
       }
    }
    /*java代码*/
    void union (List La,list Lb){
    int Lb_len = Lb.length();
    for(int i = 0;i < Lb_len;i++){
        if(!La.contains(Lb.get(i))){    //匹配元素,若有相同的元素则返回ture
            La.add(Lb.get(i));
        }
    }
    }

    其时间复杂度为:$O_{(ListLength^2)}$​

  2. 已知一个非纯集合B(集合内有相同的元素),试图构造一个纯集合A,使A中只包含B中所有值各不相同的元素

    原理:对B中的每个元素都在A中进行查找,若A中没有则将这个元素插入(添加)到A里面

    void purge(List &A,List B){
       InitList(A);                         //初始化线性表
       int e;
       int A_len = ListLength(A);
       int B_len = ListLength(B);
       for(int i = 0;i < B_len;i++){
           GetElem(B,i,e);                  //查询B指定位置的元素的值
           if(!LocateElem(A,e,equal())){
               ListInsert(A,++A_len;e)      //若La中不存在和e相同的数据元素,则将其插入
           }
       }
    }
    /*java代码*/
    void purge(List A,List B){
       A.clear();                           //清空A中的内容
       int B_len = B.length();
       for(int i = 0;i < B_len;i++){
           if(!A.contains(B.get(i))){
               A.add(B.get(i));         //如果A中没有这个B的元素,则将这个元素添加到A里面
           }
       }
    }

    上述算法中if和for循环的时间复杂度均为$O{(n)}$,因此整个算法的时间复杂度为$O{(n^2)}$

    此问题在特殊情况下的优化问题:

    若B中的元素已经排序,那么在检查A中是否有这个元素的流程就不需要对A的全部元素进行比较,因此可以减少对A的查询次数

    void purge(List &A,List B){
       int e;
       int en;
       InitList(A);                         //初始化线性表
       int A_len = ListLength(A);
       int B_len = ListLength(B);
       for(int i = 0;i < B_len;i++){
           GetElem(B,i,e);                  //查询B指定位置的元素的值
           if(ListEmpty(A||!equal(en,e))){
            ListInsert(A,++A_len,e);
            en = e;
           }/*此for循环的功能是先判定A是否是空的,若A是空的,则将B的当前位置值插入到A中的对应位置
            (由于此情况的发生只会在i = 1时发生,因此表示当第一次for循环时,将B的第一个元素插入到A的第一位),
             由于此流程是依靠e作为中间暂存元素实现的,因此e的值就是当前A的末端元素的值,e的值通过en进行保存,
             当下一次for循环时,通过比较en的e是否相同即可实现判定当前A的末端元素是否与B的当前位置的元素相同
           */
       }
    }
    /*java代码*/
    void purge(){
       A.clear();                           //清空A中的内容
       int A_len = A.length();
       int B_len = B.length();
       int en;
       for(int i = 0;i < A_len;i++){
           if(a.isEmpty()||en != B.get(i)){
                en = B.get(i);
               A.add(en);  
           }
       }
    }

    此算法中for循环的时间复杂度为$O{(n)}$​​,if循环的时间复杂度为$O{(1)}$​​​,因此时间复杂度为$O{(n)}$​​,由此可发现线性表的有序和无序,它的时间复杂度是差一个数量级的,但当使用链表完成时,此时间复杂度为$O{(n^2)}$

  3. 归并其数据元素按值递增有序排列”的线性链表La和Lb,求得线性表LC也具有同样的特性即

    设 $L_a = (a_1,a_2...a_i),\quad L_b = (b_1,b_2...b_3),\quad L_c = (C_1,C2....C{m+n})$​

    则 $C_k$ 中 $k = 1,2,3 ...m+n$​

    原理:分别从La和Lb取得当前元素ai和bj,若ai <= bj,则将ai插入到Lc中,否则将bj插入到Lc中

    void MergeList(List La,List Lb,List &Lc){
       InitList(Lc);
       int i = 1;
       int j = 1;
       int k = 0;
       int ai;
       int bj;
       int La_len = ListLength(La);
       int Lb_len = ListLength(Lb);
       while((i <= La_len)&&(j <= Lb_len)){ //当La与Lb均非空时执行
           GetElem(La,i,ai);
           GetElem(Lb,j,bj);                 //获取并保存La与Lb的第i和j个元素的值到队员临时变量
           if(ai <= bj){
               ListInsert(Lc,++k,ai);
               ++i;                      //如果ai小于bj就向Lc放ai
           }else{
               ListInsert(Lc,++k,bj);
               ++j;                      //反之放bj
           }
       }                                     //此时一个表结束,另一个表还有元素
       while(i <= La_len){
           GetElem(La,i++,ai);
           ListInsert(Lc,++k,ai);
       }
       while(j <= Lb_len){
           GetElem(Lb,j++,bj);
           ListInsert(Lc,++k,bj);
       }                                     //这两个while循环将有一个会被执行,以此结束元素的插入
    }
    /*java代码*/
    void MergeList(List La,List Lb,List Lc){
       int i;
       int j;
       int ai;
       int bj;
       int La_len = La.length;
       int Lb_len = Lb.length;
       while((i < La_len)&&(j < Lb_len)){
           ai = La.get(i);
           bj = Lb.get(j);
           if(ai <= bj){
               Lc.add(ai);
               ==i;
           }else{
               Lc.add(bj);
               ++j;
           }
       }
       while(i <= La_len){
           ++i;
           Lc.add(La.get(i));
       }
       while(j <= Lb_len){
           ++j;
           Lc.add(Lb.get(j))
       }
    }

    其时间复杂度为$O{(La.length+Lb.length)}$在链表下的其时间复杂度为:$O{((La.length+Lb.length)^2)}$​

2.2 线性表类型的实现——顺序映像(顺序表)

java的此部分内容如需查看其实现。请自行查阅java的源代码或者参考此文章,对应位置的java实现将会参考和使用这些内容

  1. 定义

    顺序映像是用一组地址连续的存储单元以此存放线性表中的数据元素
    $$
    \begin{array}{|c|c|c|}
    \hline a1&a2&a3&...&ai&...&an\
    \hline
    \end{array}
    $$
    其中,a1的存储地址同时也表示线性表的起始地址,称作线性表的基地址 ,以下内存地址使用LOC表示

    在顺序映像中,将数据元素之间的关系隐藏起来了,只存放数据元素,通过存储位置间的特定关系来表达数据元素之间的关系,若以存储位置相邻表示有序实数对$<a{(i-1)},a{(i)}>$​,即:
    $$
    LOC_{(ai)}=LOC{(a{i+1})}+C \quad \quad (C表示一个数据元素的所占存储量)
    $$
    所以所有数据元素的存储位置均取决于第一个数据元素的存储位置即:
    $$
    LOC
    {(a_i)}=LOC(a1)+(i-1)*C \quad \quad (其中,LOC{(a_i)}为基地址)
    $$

  2. 顺序映像的描述

    #define LIST_INIT_SIZE 80                //线性表存储空间的初始分配量
    #define LISTINCREMENT 10             //线性表存储空间的分配增量
    
    typedef struct{
       ElemType *elem;                      //存储空间基址
       int length;                          //当前长度
       int listsize;                        //当前分配的存储容量
    }SqList                                  //俗称顺序表
    /*java实现*/
    public class SqList implements *** {
       private Object[] listElem;           // 线性表存储空间
       private int curLen;                  // 当前长度
    }
  3. 基本功能的实现

    • 线性表的初始化操作

      Status InitList_Sq(SqList&L){
       //构造一个空的数据表
       L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); //为线性表的数组元素开辟一个数据空间
       if(!L.elem){
           exit(OVERFLOW)
       }
       L.length = 0;                                               //初始化长度
       L.listsize = LIST_INIT_SIZE                                     //初始化大小
       return OK;
      }
      /*java代码*/
      public SqList(int maxSize) {               // 顺序表的构造函数,构造一个存储空间容量为maxSize的线性表
           curLen = 0;                    // 置顺序表的当前长度为0
           listElem = new Object[maxSize]; // 为顺序表分配maxSize个存储单元
      }
    • 查找数据元素的实现

      int LocateElem_Sq(SqList L,ElemType e){
       Status(*compare)(ElemType,ElemType){    //默认函数指针指向compare函数
           int i = 1;                          //i的初始值是第一个元素的位序
           int P = L.elem;                         //p的初始值为第一元素的存储位置
           while(i <= L.length && !(*compare)(*p++,e)){
               ++i;
           }
           if(i <= L.length){
               reture i;
           }else{
               return 0;
           }
       }
      }
      /*java代码*/
      public int indexOf(String s) {
       for (int i = 0; i < size; i++) {
           if (Objects.equals(element[i], s))  //比较线性表中的第i个元素与所给元素是否相等(支持泛型化)
               return i;
           }
           return -1;
       }
      }

      时间复杂度为$O_{(n)}$​

    • 插入的功能实现

      在插入被执行时,在$a_{i-1}$与$ai$​之间插入了元素e,此时$e$占据了原来的$a{i}$​​的内存地址,其余元素以此类推后一个占用前一个的内存地址

      Status ListInsert(SqList *L,int i,ElemType e) 
      ElemType *newbase,*q,*p;
      if(i<1||i>(*L).length+1)                //判断i的值是否合法
        return ERROR;
      if((*L).length>=(*L).listsize)              //若当前存储空间已满,则增加空间分配
      {
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase)
          exit(OVERFLOW);                         //存储分配失败
        (*L).elem=newbase;                    //创建新基址
        (*L).listsize+=LISTINCREMENT;             //增加存储容量
      }
      q=(*L).elem+i-1;                        //确定插入位置的内存地址q
      for(p=(*L).elem+(*L).length-1;p>=q;--p){
          *(p+1)=*p;
      }                                       //插入位置及之后的元素右移
      *q=e;                                   //插入元素e
      ++(*L).length;                          //表长增加1
      return OK;
      }
      /*java代码,*/
      public void add(String s, int index) 
       rangeCheckForAdd(index);               //检查索引是否合法
       ensureCapacity(size);                  //保证当前线性表长度满足插入一个元素的要求
      if (index + 1 < element.length){
           System.arraycopy(element, index, element, index + 1, size - index + 1);
       }                                      //插入元素(size-1) - (index-1) +1,防止index + 1溢出
      element[index] = s;
      size++;
      }

      时间复杂度为$O_{(ListLength(L))}$​

      考虑平均的情况则可以进行以下计算:

      假设在第i个元素之前插入的概率为$pi$,则在长度为n的线性表中插入一个元素所需要移动次数的期望值为:$E{dI} = \sum_{i=1}^{n+1}p_i(n-i+1)$​​​​

      若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:$E{dI} = \frac{1}{n+1}\sum{i=1}^{n+1}(n-i+1) = \frac{n}{2}$​​​​​

    • 删除功能的实现

      在删除被执行时,在原有的$a{i-1},a{i},a_{i+1}$上面删除$ai$,此时,原$a{i+1}$使用$a_i$​的内存地址,以此类推

      //删除线性表
      Status deleteList(SqList *L, int i, ElemType &e){
       if(L.length==0){                           //判断目前是否为空
           return ERROR;
       }
       if(i==0||i>L.length){                  //判断当前位置是否非法
           return ERROR;
       }
       int *p = &(L.elem[i-1]); 
          e = *p;                                 //将要删除位置的元素存储起来
       int q = L.elem+L.length-1;             //确定表尾部元素的位置
       if(i!=L.length){                       //如果要删除的位置不在最后,那么要进行线性表的前移操作
           for(++p;p <= q;++p){
               *(p-1) = *p;
           }
           L.length--;
           return e;
       }
       L.data[i-1] = 0;                       //如果要删除的位置在最后,那么直接将最后一个元素置0
       return e;
      }
      /*java代码*/
      public String remove(int index) {
       String toBeRemoved = element[index];
       rangeCheck(index);                     //判断当前位置是否合法
       int numToMove = size - index - 1;      //判断删除所需复制的线性表长度
       if (numToMove > 0){
           System.arraycopy(element, index + 1, element, index, numToMove);
       }                                      //线性表片段复制操作
       element[size - 1] = null;              //清除残留的末位元素
       size--;                                    //修正当前的线性表大小
       return OK;
      }

      此算法的时间复杂度为$O_{(n-1)}$​

      假设删除第i个元素的概率为$qi$​,则在长度为n的线性表中删除一个元素所需移动的次数的期望值为:$E{dI}=\sum_{i=1}^{n}q_i(n-i)$​

      若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:$E{dI}=\frac{1}{n}\sum{i=1}^{n}(n-i)=\frac{n-1}{2}$​

顺序表是线性表的一种表示方法,它的特点是一组地址连续的存储空间来存储线性表中的数据元素,因此可以借用C中的一维数组来表示它(java亦同),但由于其长度可变,因此要对数组进行动态分配,顺序表的优点是可以对每一个数据元素进行随机的存取,其表长是显值,其缺点是当其进行插入或者删除时要进行元素的移动,每进行一次插入或删除大致要移动整个表的12的元素,因此有了线性表的另外一种表示方法

2.3 线性表类型的实现——链式映像(链表)

java的此部分内容无极准确的实现被封装成 list ,可以参考此文章,对应位置的java实现将会参考和使用这些内容

  1. 单链表(线性链表)

    用一组地址任意的存储单元存放线性表中的数据元素,其结构为:

    元素(数组元素的映像)+指针(存储后继元素的存储位置)= 结点(表示数据元素)

    单个结点的结构图: $\begin{array}{|c|c|c|}
    \hline 数据元素&后继元素指针\
    \hline
    \end{array}$

    以结点的序列表示表示的线性表成为链表
    $$
    头指针
    \begin{array}{|c|c|c|}
    \hline a1&1\
    \hline
    \end{array},
    \begin{array}{|c|c|c|}
    \hline a2&
    2\
    \hline
    \end{array},
    \begin{array}{|c|c|c|}
    \hline a3&*3\
    \hline
    \end{array}
    \quad...
    \quad \begin{array}{|c|c|c|}
    \hline an&null\
    \hline
    \end{array}
    $$
    但以指向线性表中第一个数据元素的存储地址作为线性表的地址,称作线性表的头指针,即头指针指向数据元素a1,但当链表有头结点时,头指针指向头结点

    但有时为了处理方便起见,通常在线性表的第一个元素前面虚加一个结点,称为头结点,它的结构与后面的结点相同,包含数据元素和指针,但其数据元素为空(无意义,但有时也用来存放链表的长度),其指针指向第一个数据元素的内存地址,当链表为空表时,其指针为空

    结点和单链表的语言描述和生成(构造)

    typedef struct LNode{
    ElemType data;              //数据域
    struct LNode *next;         //指针域
    }
    //头插法
    void CreatList_L(LinkList &L,int n){
       LinkList p;
       L = (LinkList)malloc(sizeof(LNode));
       L->next=NULL;                //建立一个带结点的单链表
    for(int i=0;idata);   //链表元素输入
        p->next=L->next;
        L->next=p;              //插入到表头
    }
    }
    //尾插法
    void CreateList_E (LinkList &head,int n){
    LinkList p;
    LinkList pend;              //定义最后的节点指针; 
    L=(LinkList)malloc(sizeof(LNode)); 
    L->next=NULL;
    pend=L;                     //头结点是最后的节点 ;
    for(int i=0;idata);//链表元素输入
        p->next=NULL;
        pend->next=p;
        pend=p;
    }   
    }
    /*java代码*/
    public class Node {
    public Object data;     //存放结点值
    public Node next;       //后继结点的引用
    /*构造函数*/
       public Node() {
        this(null,null);
    }
    public Node(Object data) {
        this(data,null);
    }
    public Node(Object data,Node next) {
        this.data = data;
        this.next = next;
    }
    }
    
    /*构造函数*/
    public class LinkList {
    public Node head;       //单链表的头指针
    public LinkList() {
        head = new Node();
    }
    }
    
    //头插法
    private void create1(int n) throws Exception {
    Scanner reader = new Scanner(System.in);
    System.out.println("请输入"+n+"个元素");
    for(int i = 0; i < n; i++) {
        Object sc = reader.next();
        insert(0,sc);
    }
    }
    //尾插法
    private void create2(int n) throws Exception {
       Scanner reader = new Scanner(System.in);
    System.out.println("请输入"+n+"个元素");
    for(int i = 0; i < n; i++) {
        Object sc = reader.next();
        insert(length(),sc);
    }
    }

    其头插法生成的时间复杂度为$O_{(LinkList.length)}$

  2. 单链表操作的实现

    • 获取元素GetElem(L,i,&e)在链表中的实现

      基本操作为:使指针p始终指向线性表中第 i +1 个数据元素直到 j 自加到要获取的元素位置

      Status GetElem_L(LinkList L,int i,ElemType &e){
       int *p = L->next;          //p指向第一个结点
       int j = 1;                 //j为计数器
       while((p < i)&&(jnext;
           ++j;
       }
       if((p == null)||(j>i){         //保证这个结点存在
           return ERROR;
       }else{
       e = p->data;               //取元素
       return data;
       }
      }
      /*若将链表长度信息放入头结点将可以简化这段代码*/
      /*java实现*/
      public Object get(int i) throws Exception {
          Node p = head.next;
          int j = 0;
          while(p != null && j < i) {
              p = p.next;
              ++j;
          }
          if(j > i || p == null) {
              throw new Exception("第"+i+"个元素不存在");
          }
          return p.data;
      }
      }

      其时间复杂度为:$O_{(LinkList.length)}$

    • 插入操作ListInsert(&L,i,e)在链表中的实现

      基本操作为:找到线性表中第i - 1个结点,将i-1的结点的后继指针修改成插入的结点的地址,随后对新结点添加新的指针指向原第 i 个结点

      图示如下:
      $$
      将:
      \begin{array}{|c|c|c|}
      \hline a1&2\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a2&
      3\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a3&4\
      \hline
      \end{array}
      ...
      \begin{array}{|c|c|c|}
      \hline an&null\
      \hline
      \end{array} 修改为:
      \begin{array}{|c|c|c|}
      \hline a1&
      2\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a2&x\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a3&
      4\
      \hline
      \end{array}
      ...
      \begin{array}{|c|c|c|}
      \hline an&null\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline ax&*3\
      \hline
      \end{array}
      $$

      Status ListInsert_L(LinkList L,int i,ElemType e){
       int *p = L->next;
       int j = 0;
       while((p < i-1)&&(jnext;
           ++j;
       }
       if((p == null)||(j>i-1){               //i小于1或大于表长
           return ERROR;
       }else{
           s = (LinkList)malloc(sizeof(LNode));//生成新结点
           s->data = e;                       
           s->next = p->next;                 //将其插入到L中
           p->next = s;
           return OK;
       }
      }
      /*java代码*/
      public void insert(int i, Object x) throws Exception {
          Node p = head;
          Node s = new Node(x);
          int j = -1;
          while(p != null && j < i-1) {
              p = p.next;
              ++j;
          }
          if (j > i-1 || p == null) {
              throw new Exception("插入位置不合法");
          }
          s.next = p.next;
          p.next = s;
      }
      }

      算法的时间复杂度为:$O_{(LinkList.length)}$​​

    • 删除操作ListDelete(&L,i,&e)在链表中的实现

      基本操作为:找到线性表中第i - 1个结点,修改其指向后继的指针

      图示如下:
      $$
      将:
      \begin{array}{|c|c|c|}
      \hline a1&2\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a2&
      3\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a3&4\
      \hline
      \end{array}
      ...
      \begin{array}{|c|c|c|}
      \hline an&null\
      \hline
      \end{array} 修改为:
      \begin{array}{|c|c|c|}
      \hline a1&
      3\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a2&x\
      \hline
      \end{array},
      \begin{array}{|c|c|c|}
      \hline a3&
      4\
      \hline
      \end{array}
      ...
      \begin{array}{|c|c|c|}
      \hline an&null\
      \hline
      \end{array},
      $$
      此时,a2结点被跳过起到了删除的效果,随后释放a2的内存空间即可

      Status ListDelete_L(LinkList L,int i,ElemType e){
       int *p = L->next;
       int j = 0;
       while((p < i-1)&&(jnext;
           ++j;
       }
       if((p->next == null)||(j>i-1){             //删除位置不合理
           return ERROR;
       }else{
           inr *q = p->next;                      //修改前一个结点的指针
           p->next = q->next;
           e = q->data;                           //返回删除的结点的数据元素
           free(q);                               //释放被删除的结点的内存空间
           return(OK);
       }
      }
      /*java代码*/
      public void remove(int i) throws Exception {
          Node p = head;
          int j = -1;
          while(p.next != null && j < i-1) {
              p = p.next;
              ++j;
          }
          if(p.next == null || j > i - 1) {
              throw new Exception("删除位置不合适");
          }
          p.next = p.next.next;
      }
      }

      算法的时间复杂度为:$O_{(LinkList.length)}$​

  3. 定义单链表实现线性表的操作时存在的问题:

    • 单链表的长度是一个隐含值(但可被存放到头结点)
    • 在单链表的最后一个元素后面插入元素时需要遍历整个链表
    • 在链表中,元素的位序概念淡化,结点的位置概念强化
  4. 改进链表的设置

    • 增加表长,表尾指针和当前位置指针三个数据域
    • 将基本操作由位序改为指针
  5. 带头结点的线性链表类型&优化

    typedef struct LNode{    //结点类型
    ElemType data;
       struct LNode *next;
    }*Link,*Position;
    
    Status MakeNode(Link &p,ElemType e){
       //分配由p指向的值为e的结点,并返回OK;
       //若分配失败,则返回error
    }
    void FreeNode(Link &p){
       //释放p所指的结点
    }
    typedef struct{          //链表类型
       Link head,tail;      //指向头结点和最后一个结点
       int len;         //指示链表长度
       Link current;        //指向当前访问的结点的指针,其初始位置指向头结点
    }
  6. 链表的基本操作

    • 链表的初始化

      构造一个空的线性链表L,其头指针,尾指针和当前指针均指向头结点,表长为0

    • 链表的销毁

      销毁线性链表L,L不再存在,遍历链表,释放所有空间

    链表的引用型操作(相关功能的实现原理与前面的大致相同,大部分具体实现代码省略,仅给出部分实现)

    • 判空

      Status IistEmpty(LinkList L);

      /*java代码*/
      public boolean isEmpty();
    • 求表长

      int ListLength(LinkList L);

      /*java代码*/
      public int length();
    • 改变当前指针指向其前驱

      Status Prior(LinkList L);

    • 改变当前指针指向其后继

      Status Next(LinkList L);

    • 返回当前指针所指的数据元素

      ElemType GetCurElem(LinkList L);

    • 改变当前指针指向第 i 个结点

      Status LocatePos;

    • 若存在与e满足函数compare()判定关系的函数,则移动当前指针,直到指向第 i 个满足条件的元素,并返回OK,否则返回报错

      Status LocateElem(LinkList L,ElemType e,Status(*compare*)(ElemType,ElemType));

    • 依次对L的每个元素调用函数visit()

      Status ListTraverse(LinkList L,Status(*visit)());

    加工型操作

    • 重置为空表

      Status ClearList(LinkList &L);

    • 更新当前指针所指数据元素

      Status SetCurElem(LinkList &L,ElemType e);

    • 一串结点链接在最后一个结点之后

      Status Append(LinkList &L,Link s);

    • 将元素e插入到当前指针之后

      Status InsAfter(LinkList &L,ElemType e);

      /*java代码*/
      public void insert(int i, Object x) throws Exception;

      代码实现:

      Status InsAfter(LinkList &L,ElemType e){
       if(!L.current){
           return ERROR;
       }
       if(!MakeNode(s,e)){
           return ERROR;
       }
       s->next = L.current->next;
       L.current->next = s;
       return OK;
      }
      public void insert(int i, Object x) throws Exception{
       Node p = head;
      Node s = new Node(x);
      int j = -1;
      while(p != null && j < i-1) {
          p = p.next;
          ++j;
      }
      if (j > i-1 || p == null) {
          throw new Exception("插入位置不合法");
      }
      s.next = p.next;
      p.next = s;
      }
      }
    • 删除当前指针之后的结点

      Status DelAfter(LinkList &L,ElemType *e);

      代码实现:

      Status DelAfter(LinkList &L,ElemType *e){
       if(!(L.current && L.current->next){
           return ERROR;
       }                                  //若当前指针及其后继在链表中,则删除线性表L中当前的指针所指的结点之后的结点
       q = L.current->next;
       L.current->next = q->next;
       e = q->data;
       FreeNode(q);
       return OK;
      }

    利用上面的原子操作实现线性表的其他操作(实现区别过大,不给出java代码)

    • 在第i个元素之前插入元素e

      Status ListInstert_L(LinkList L,int i,ElemType e){
       //在带头结点的线性表i的第i个元素之前插入元素e
       if(!LocatePos(L,i-1)){
           return ERROR;
       }
       if(InsAfter(L,e)){
           return OK;
       }else{
           return ERROR;
       }
      }
    • 排序合并链表(假定原来的两个链表已排序)

      void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc,int(*compare)(ElemType,ElemType)){
      if(!InitList Lc){               //存储空间分配失败
          return ERROR;
      }
      LocatePos(La,0);
      LocalePos(Lb,0);                //令当前指针指向头结点
      if(DelAfter(La,e)){             //删除当前位置的元素(此时为第一个数据元素)并将返回的值传到后面以便于插入到Lc中
          a = e;
      }else{
          a = MAXC;                   //MAXC为常量最大值
      }
      if(DelAfter(Lb,e)){
          b = e;
      }else{
          b = MAXC;
      }
      while(!((a == MAXC) && (b == MAXC)){//保证La或Lb非空以此实现遍历
           if((*compare)(a,b) <= 0){
               InsAfter(Lc,a);
               if(DelAfter(La,el)){    //a <= b
                   a = cl;
               }else{
                   a = MAXC;
               }
           }else{
               InsAfter(Lc,s);
               if(DelAfter(Lb,e)){         //a > b
                   b = el;
               }else{
                   b = MAXC;
               }
           }
      }
       DestroyList(La);                //销毁原来的链表
       DestroyList(Lb);
       return OK;
      }

      此实现的时间复杂度为$O_{(n)}$​

  7. 其它形式的链表

    • 双向链表

      通过在单链表的基础之上添加一个指针用来存放其前驱指针实现链表的向前访问,避免了部分场景下的性能浪费,但会占用更多的空间

      java中已被封装到LinkList,如需查看此实现,请查看java源代码或参考此文章

      双链表的实现

      typedef struct DulNode{
       ElemType data;         //数据域
       struct DulNode *prior; //指向前驱的指针域
       struct DulNode *next;  //指向后继的指针域
      }

      单个结点的结构:$\begin{array}{|c|c|c|}
      \hline &an&\
      \hline
      \end{array}$​,即 $$\begin{array}{|c|c|c|}
      \hline 前驱元素指针&数据元素&后继元素指针\
      \hline
      \end{array}$$

    • 循环链表

      最后一个结点的指针域的指针指向第一个结点的链表

      其结构为:$头指针 \quad \begin{array}{|c|c|c|}
      \hline a1&2\
      \hline
      \end{array},\begin{array}{|c|c|c|}
      \hline a2&
      3\
      \hline
      \end{array},\begin{array}{|c|c|c|}
      \hline a3&1\
      \hline
      \end{array}....\begin{array}{|c|c|c|}
      \hline an&
      1\
      \hline
      \end{array}$

2.4 一元多项式的表示

一元多项式$P_n(x) = p_0 + p_1x+p_2x^2+...+p_nx^n$​ 在计算机中可以使用一个线性表来表示:$P = (p_0,p_1,...,p_n)$​

一般情况下一元多项式可写成$P_n(x) = p_0x^{e1} + p_1x+p_2x^{e2}+...+p_nx^{en}$​ ,其中,$p_i$​是指数为ei的项的非零系数

此时在计算机中表示则需要同时存储系数数据和项数数据,即使用二元组来进行表示$((p_1,e_1),(p_2,e_2)....(p_n,e_n))$​

  1. 结构及其功能

    ADT Polynomial{
    数据对象:D={ai|ai∈TermSet, i=1,2,...,m, m≥0}
            {TermSet中每个元素包含一个表示系数的实数和表示指数的整数}
    数据关系:RI={|ai-1,ai∈D,且ai-1中的指数值<ai的指数值,i=2,…,n}
    基本操作
    CreatePolyn(&P,m)
    操作结果:输入m项的系数和指数,建立一元多项式P
    DestoryPolyn(&P)
    初始条件:一元多项式P已存在
    操作结果:销毁一元多项式
    PrintPolyn(&P)
    初始条件:一元多项式P已存在
    操作结果:打印输出一元多项式P
    AddPolyn(&Pa,&Pb)
    初始条件:一元多项式Pa和Pb已存在。
    操作结果:完成多项式相加运算,即:Pa=Pa+Pb,并销毁多项式Pb。
    SubractPolyn(&Pa,&Pb)
    初始条件:一元多项式Pa和Pb已存在。
    操作结果:完成多项式相减运算,即:Pa=Pa-Pb,并销毁多项式Pb。
    MultiplyPolyn(&Pa,&Pb)
    初始条件:一元多项式Pa和Pb已存在
    操作结果:完成多项式相减运算,即:Pa=Pa*Pb,并销毁多项式Pb
    PolynLength(P)
    初始条件:一元多项式P已存在
    操作结果:返回一元多项式P中的项数
    } 
  2. 实现

    typedef struct{           //类型名
    float coef;          //系数
    int expn;            //指数
    }term,ElemType;           //两个类型名,term用于本ADT,ElemType为LinkList的数据对象名
    
    typedef LinkList polynomial;
    //用带表头结点的有序链表表示多项式
    
    int cmp(term a,term b){
       //通过比较a的指数值 <= 或 > b的指数值,分别返回-1,0,和+1
    }
    
    //建立一元多项式有序表
    void CreatePolyn(polynomial &p, int  m){
       InitList(P);                         //初始化头结点
       e.coef  = 0.0;
       e.expn  = -1;
       SetCurElem(P,  e);                       //设置头结点的数据元素
       for(j  = 1; j <= m; ++ i){               //依次输入m个非零项
           scanf(e.coef,  e.expn);
           if(!  LocateElem(P, e, (*cmp)()))    //查找要插入的位置
               InsAfter(P,  e);             //当前链表中不存在该指数项
            }
    } 

2.5 总结

  1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示线性表简称为顺序表,用后者表示的线性表称为链表
  2. 熟练掌握这两类存储结构的描述方法,以及线性表的各种基本操作的实现
  3. 要能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点极其使用的场合

3. 栈和队列

3.1 栈的类型定义

ADT Stack{
数据对象:
    D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系:
    R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}约定an端为栈顶,a1端为栈底。
基本操作:
}

栈与线性表的结构基本一致,但增加了一部分对操作的限制与要求,栈只允许从栈顶进行插入和删除操作,像是一口井,只有一端可以进出

栈的基本操作

  • InitStack(&S)

    操作结果:构造一个空栈S

  • DestoryStack(&S)

    初始条件:栈S已存在

    操作结果:栈S被销毁

  • StackEmpty(S)

    初始条件:栈S已存在

    操作结果:若栈S为空栈,则返回TRUE,否则返回FALSE

  • StackLength(S)

    初始条件:栈S已存在

    操作结果:返回S的元素个数,即栈的长度

  • GetTop(&S)

    初始条件:栈S已存在且非空

    操作结果:用e返回S的栈顶元素

  • ClearStack(&S)

    初始条件:栈S已存在

    操作结果:将S清为空栈

  • Push(&S,e)

    初始条件:栈S已存在

    操作结果:插入元素e为新的栈顶元素(入栈)

  • Pop(&S,&e)

    初始条件:栈S已存在且非空

    操作结果:删除S的栈顶元素,并用e返回其值(出栈)

3.2 栈的应用举例

  • 数制转换

    算法基于原理:N=(N div d)*d+N mod d(短除法),例如1348的8进制运算过程如下

    ​ $\begin{array}{c|ccc|c}
    ​ &N &N \ div \ 8&N \ mod \ 8\
    ​ 计&348 &168&4&序\
    ​ 算&168 &21&0&顺\
    ​ 顺&21 &2&5&出\
    ​ 序&2 &0&2&输\
    \end{array}$​

    void conversion(){
           InitStack(S);            //构造栈
         int N;
           scanf("%d",N);           //数据输入
           while(N){                //N非空(0)时循环
               Push(S,N%8);     //入栈
               N  = N/8;            //计算
           }
           while(!StackEmpty(S)){   //判空
               Pop(S,e);            //出栈
               printf("%d",e);
           }
    } 

    注:java已将此算法封装在Integer中,但比这个更加复杂,请自行查看源代码,以下为上述C代码的java版

    /*java代码*/
    public static void main(String[] args) throws Exception {
      Stack stack = new Stack();
      reader = new Scanner(System.in);
      int N = reader.nextInt();
      while(N != 0){
          stack.push(N%8);
          N = N/8;
      }
      while(!stack.isEmpty()){
          System.out.print(stack.pop());
      }
    }
  • 括号匹配的检查

    ( [ ] ( ) )[ ( [ ] [ ] ) ]等为正确的格式,[ ( ) ]( [ ( ) ]( ( ) ) )均为不正确的格式

    检验括号是否匹配的方法用“期待的急迫程度”这个概念来描述例如考虑下列括号序列

    [ ( [ ] [ ] ) ]

    实现原理:

    左括弧全部入栈,右括弧先检查栈是否空,若空则入栈,否则和栈顶元素比较,若匹配,则栈顶元素出栈,完成后判断栈空,若空则匹配正确,非空则代表匹配错误

    Status matching(string & exp){
           int  state = 1;
           while(i  <= Length(exp) && state){
               switch  of exp[i]{
               case  左括弧{
                   Push(S,exp[i]);
                   i  ++;
                   break;
               }
               case  右括弧 {
                   if((!StackEmpty(S)) && (GetTop(S) == 右括弧){
                       Pop(S,e);
                       i++;
                   }else{
                       state  = 0;
                   }
                   break;
               }
               }
               if(StackEmpty(S) && state){
                   return  OK;
               }else{
                   return  ERROR;
               }        
           }
    }
    /*java代码(括号仅())*/
    public static boolean isValid(String s) {
      Stack stack = new Stack<>();
      for (int i = 0; i < s.length(); i++) {
          if ((s.charAt(i) == '(') || (s.charAt(i) == '[') || (s.charAt(i) == '{')) {
              stack.push(s.charAt(i));     
          } 
          if ((s.charAt(i) == ')') || (s.charAt(i) == ']') || (s.charAt(i) == '}')) {
              if (stack.empty()) { 
                  return false;
              }
              if ((stack.peek() == '(' && s.charAt(i) == ')') || (stack.peek() == '[' && s.charAt(i) == ']') || (stack.peek() == '{' && s.charAt(i) == '}') ) {
                  stack.pop();
              }
          }
      }
      if (stack.empty()) {
          return true;
      }
      return false;
    }
  • 行编辑程序问题

    在进行文本编辑任务(无屏幕编辑)时,计算机需要将用户输入的数据存入用户数据区,但是由于输入过程中难免会输入错误和需要修改,如果将数据区整个删除重新输入显然不现实,因此需要建立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区,这样,用户输入一行的过程中,就可以允许用户输入出差错,并在发现有误时可以及时更正

    假设从终端接受了这样两行字符:

    whli##ilr#e(s#*s)

    outcha@putchar(*s=#++);

    则有效的是下列两行:

    while(*s)

    putchar(*s++);

    while(ch != EOF){                 //EOF为全文结束符
      while(ch != '\n'){
          switch(ch){
              case  '#':                //接收到#就清除当前栈顶元素
                  Pop(S,c);
                  break;
              case  '@':                //接收到@则清空栈内元素
                  ClearStack(S);
                  break;
              default:              //默认则将接收到的字符入栈
                  Push(S,ch);
                  break;
          }
          ch  = getchar(); //从终端接收下一个字符
      }
      /*将从栈底到栈顶的字符传送至调用过程的数据区*/
      ClearStack(S);  //重置S为空栈
      ...
    }
  • 迷宫求解

    通常用的是“穷举求解”的方法(回溯法)

    求迷宫路径算法的基本思想是:

    若当前位置“可通”,则纳入路径,继续前进

    若当前位置“不可通”,则后退,换向探索

    若四周均“不可通”,则路径中删除

    伪代码:

    设定当前位置的初值为入口位置;
    do{
      若当前位置可通,则{
          将当前位置插入栈顶;
              若该位置是出口位置,则结束;
              否则切换当前位置的东邻方块为新的当前位置
      }否则{
          若栈不空且栈顶位置尚有其它方向未被探索,则设定新的当前位置为:沿顺时针方向旋转找到栈顶位置的下一个邻块;
          若栈不空但栈顶位置的四周均不可通,则{
              删去栈顶位置;//从路径中删去该通道块
              若栈不空,则重新测试新的栈顶位置,直到找到一个可通的相邻块或出栈至栈空;
          }
      }
    }while(栈不空);
  • 表达式求值

    限于二元运算符的表达式定义:

    表达式::=(操作数)+(运算符)+(操作时)

    操作数::=简单变量|表达式

    简单变量::=标识符|无符号整数

    在计算机中,表达式可以有三种不同的标识方法

    设有$E_{xp}=S_1+OP+S_2$​​​​,(OP为运算符)则有:​

    • 前缀表示法:$E_{xp}=OP+S_1+S_2$
    • 中缀表示法:$E_{xp}=S_1+OP+S_2$
    • 后缀表示法:$E_{xp}=S_1+S_2+OP$

    例如: $E_{xp}=ab+(c-d/e)f$​

    前缀式:$+ab-c/def$

    中缀式:$ab+c-d/ef$

    后缀式:$abcde/-f+$​

    特点:

    • 操作数之间的相对次序不变
    • 运算符的相对顺序不变
    • 中缀式丢失了括弧信息,导致使运算的次序不确定
    • 前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠他们的运算符构成一个最小表达式
    • 后缀式的运算规则为:运算符在式中出现的顺序为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式

    由于后缀式正好符合编译运行的顺序规则,因此常在编译过程中先将表达式转换成后缀式

    如何从后缀式求值?

    先找运算符,再找操作数

    如何从原表达式求得后缀式?

    分析“原表达式”和“后缀式”中的运算符

    每个运算符的运算次序要由它之后的一个运算符来定,在后缀式中,优先数高的运算符领先于数低的运算符

    从原表达式求得后缀式的规律为:

    • 设立运算符栈

    • 设表达式的结束符为“#”,予设运算符栈底为“#”

    • 若当前字符是操作数则直接入栈操作数栈

    • 当前运算符对优先级高于栈顶运算符,则入操作数栈

    • (对它前后的运算符起隔离作用)则将()内的运算符入操作数栈

    void transform(char suffix[], char exp[]){
    InitStack(S);
    Push(S,  '#');
    p  = exp;
    ch  = *p;
    while(!StackEmpty(S)){
        if(!IN(ch, OP)){
            Pass(Suffix,  ch);
        }else{
            switch(ch){
                case  '(':{
                    Push(S,  ch);
                    break;
                }
                case  ')':{
                    Pop(S,  c);
                    while(c != '('){
                        Pass(Stuffix,  c);
                        Pop(S,  c);
                    }
                    break;
                }
                default:{
                    while(!Gettop(S, c) && (precede(c, ch))){
                        Pass(Stuffix,  c);
                        Pop(S,  c);
                    }
                    if(ch  != '#'){
                        Push(S,  ch);
                    }
                }
                 break;
            }
        }
        if(ch  != '#'){
            p  ++;
            ch  = *p;
        }
    }
    }
  • 实现递归(递归次数过多易导致栈溢出,请尽量少使用(或不使用)递归 !!!)

    当在一个函数的运行期间调用另一个函数时,在运行该被调用函数之前,需先完成三件事:

    • 将所有的实在参数、返回地址等信息传递给被调用函数保存
    • 为被调用函数的局部变量分配存储区
    • 将控制转移到被调用函数的入口

    从被调用函数返回调用函数之前,应该完成:

    • 保存被调用函数的计算结果
    • 释放被调用函数的数据区
    • 依照被调用函数保存的返回地址将控制转移到调用函数

    多个函数嵌套调用的规则是:

    后调用先返回此时的内存管理实行栈式管理

    递归过程指向过程中占用的数据区,称之为递归工作栈

    每一层的递归参数合成一个记录,称之为递归工作记录

    栈顶记录指示当前层的执行情况,称之为当前活动记录

    栈顶指针,称之为当前环境指针

    void hanoi(int n, char x, char y, char z){
      //将塔座x上按直径由小到大且至上而下编号为1至n
      //的n个圆盘按规则搬到塔座z上,y可以用作辅助塔座
      {
          if(n  == 1){
              move(x,  1, z);               //将编号为1的圆盘从x移到z
          }else{
              hanoi(n-1,  x, z, y);             //将x上编号为1至n-1的圆盘移动到y,z作辅助塔
              move(x,  n, z);               //将编号为n的圆盘从x移到z
              hanoi(n-1,  y, x, z);         //将y上编号为1至n-1的圆盘移动到z,x作辅助塔
          }
      }
    }

3.3 栈的类型的实现

  • 顺序栈

    类似于线性表的顺序映象实现,指向表尾的指针可以作为栈顶指针

    栈的顺序存储表示
    $$
    base指针—\begin{array}{|c|c|c|}
    \hline a&b&c&d&e&f&g\
    \hline
    \end{array}......
    $$

    #define STACK_INIT_SIZE 100;
    #define STACKINCREMENT 10;
    typedef struct{
      SElemType  *base;         //base指针
      SElemType  *top;          //栈顶指针
      int  stacksize;               //栈容量
    }
  • 链栈

    类似于线性表的链式映象实现(使用头插法实现)
    $$
    栈顶指针—\begin{array}{|c|c|}
    \hline a_n&\
    \hline
    \end{array}
    ......
    \begin{array}{|c|c|}
    \hline a_3&\
    \hline
    \end{array},
    \begin{array}{|c|c|}
    \hline a_2&\
    \hline
    \end{array},
    \begin{array}{|c|c|}
    \hline a_1&\
    \hline
    \end{array}
    $$

3.4 队列的类型定义

队列的结构也是和线性表基本一致,但其规定了a1为队列头,an为队列尾,数据元素从队尾进入,从队头输出,单向流动,因此其使用范围也很广(在linux中的管道的结构与之类似),如在排队问题等等均会使用队列

ADT Queue{
    数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
    数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n} 约定其中a1端为队列头,an端为队列尾。
    基本操作:
}
  • 队列的基本操作

    初始化

    InitQueue(&Q)

    销毁

    DestoryQueue(&Q)

    判空

    QueueEmpty(Q)

    查询长度

    QueueLength(Q)

    取得头元素

    GetHead(Q,&e)

    清空

    ClearQueue(&Q)

    入队列

    EnQueue(&Q,e)

    出队列

    DeQueue(&Q,&e)

3.5 队列类型的实现

  • 链队列(链式映像)
    $$
    队头指针—\begin{array}{|c|c|}
    \hline &1\
    \hline
    \end{array},
    \begin{array}{|c|c|}
    \hline a_1&
    2\
    \hline
    \end{array},
    \begin{array}{|c|c|}
    \hline a_2&3\
    \hline
    \end{array},
    \begin{array}{|c|c|}
    \hline a_3&
    ..\
    \hline
    \end{array},
    \begin{array}{|c|c|}
    \hline a_n&\
    \hline
    \end{array}\quad
    (队尾指针指向a_n)
    $$
    当队列为空时,队头指针与队尾指针同时指向头结点:$队头指针—\begin{array}{|c|c|}
    \hline &null\
    \hline
    \end{array}\quad(队尾指针指向头结点,即队头结点与队尾结点同时指向头结点)$​​

    typedef struct QNode{
           QElemType  data;
           struct  QNode * next;
    }QNode, *QueuePtr;
    
    typedef struct{
           QueuePtr  front;         //队头指针
           QueuePtr  rear;      //队尾指针
    }

    入队列:在队尾添加一个新结点并修改原队尾结点的指针指向新的队尾结点,同时修改队尾指针

    出队列:将原来的队头结点删除并将头结点的指针指向第二个结点吗,若队列中只有一个元素则删除结点并修改对尾尾指针指向头结点,同时修改头结点的指针为空

  • 循环队列(顺序映像)
    $$
    \begin{array}{|c|c|}
    \hline &&&a&b&c&d&e&f&&.......&\
    \hline
    \end{array}\quad(空间大小固定)(其中,头指针指向a所在位置,尾指针指向n的后面的下一个位置)
    $$
    当队列为空时,头指针与尾指针同时指向第一个空元素位(栈底):$\begin{array}{|c|c|}
    \hline 栈底&&........&&\
    \hline
    \end{array}\quad(空间大小固定)$​

    由于头尾指针浮动,因此可能发生此类情况:$\begin{array}{|c|c|}
    \hline &&&&&&&&&a&b&c&d\
    \hline
    \end{array}\quad(此时尾指针到达队列末端)$​

    此时,若接下来有数据进入队列,则自动使用队列指针将新数据元素插入到队列的前面的数据区:$\begin{array}{|c|c|}
    \hline e&f&&...&&a&b&c&d\
    \hline
    \end{array}$​

    队满队空判定问题:有时队列会出现此类状态:$\begin{array}{|c|c|}
    \hline ?&?&?&?&?&?&?&?&?&?&?\
    \hline
    \end{array}$​​​,此时头尾指针指向某一个数据元素区域,但此时,无法判定​队列是空队列还是满队列,因此,队列要求当只剩下一个数据区时,视为队列已满,禁止插入新的数据元素,而头尾指针指向同一个数据区域时视为队列为空,因此顺序队列被称为循环队列

    #define MAXQSIZE 100          //最大队列长度
    typedef struct{
           QElemType  *base;        //动态分配存储空间
           int  front;          //头指针,若队列不空,指向队列头元素
           int  rear;           //尾指针,若队列不空,指向队尾元素的下一个位置
    }

3.6 总结

  1. 掌握栈和队列类型的特点,并能在相应的应用问题中正确选用它们

  2. 熟练掌握栈类型的两种实现方法,特别应注意栈满和栈空的条件以及它们的描述方法

  3. 熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的描述方法

  4. 理解递归算法执行过程中栈的状态变化过程(由于目前递归已被不建议使用,因此只做了解即可)

4. 串

4.1串的抽象数据类型的定义

串的结构特征与线性表相似,可视为将数据类型限定为字符的线性表,因此可称为字符串

ADT String{
数据对象:D={ai|ai∈CharacterSet,i=1,2,…n,n≥0}
数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
}

基本操作:

字符串的赋值

StrAssign(&T,chars)

字符串的比较(按大小,如串 ‘a’ 和串 ‘b’ 相比串 ‘b' 大)

StrCompare(S,T)

字符串的复制

StrCopy(&T,S)

字符串的长度

StrLength(S)

字符串的销毁

DestoryString(&S)

字符串的连接

Concat(&T,S1,S2)

字符串的判空

StrEmpty(S)

求子串(返回从一个字符串的第xx位开始的字符串)

SubString(&Sub,S,pos,len)

字符串的定位(返回子串的第一个字符在主串中的位序)

Index(S,T,pos)

字符串的清空

ClearString(&s)

字符串的取代替换(用V替换主串S中出现的所有与T相等的不重叠的子串)

Replace(&S,T,V)

字符串的位删除

StrDelete(&S,pos,len)

字符串的位插入

StrInsert(&S,pos,T)

串的逻辑结构和线性表极为相似,区别是仅在于串的数据对象约束为字符集,然而,串的基本操作和线性表有很大差别,在线性表的基本操作中,大多以“单个元素”作为操作对象,如:在线性表中查找某个元素,求取某个元素、在某个位置上插入一个元素和删除一个元素等;而在串的基本操作中,通常以“串的整体”作为操作对象,如:在串中查找某个子串、求取第一个子串、在串的某个位置上插入一个子串以及删除一个子串等

对于串的基本操作集可以说有不同的定义方法,读者在使用高级程序设计语言中的串类型时,应以语言为准,在上述抽象数据类型定义的13中操作中,串赋值StrAssign、串赋值Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种基本操作构成串类型的最小操作子集,即这些操作不能利用其它串来实现,反之,其他串操作(除串清除ClearString和串销毁DestoryString外)可在这个最小操作子集上完成

例如,可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos),其算法的基本思想为:在主串S中取从第i(i的初值为pos)个字符起、长度和串T相等的子串和串T比较,若相等,则求得函数值为i,否则值i增1直至S中不存在和串T相等的子串为止,等价于StrCompare(SubString(S,i,StrLength(T)),T)≠ 0

int Index(String S, String T, int pos){
    //T为非空串。若主串S中第pos个字符值之前存在与T相等的子串。则返回第一个
    //这样的子串在S中的位置,否则返回0
    if(pos  > 0){
        n  = StrLength(S);
        m  = StrLength(T);
        i  = pos;
        while(i  <= n-m+1){
            SubString(sub,  S, i, m);
            if(StrCompare(sub,  T) != 0){
                ++  i;
            }else{
                return  i;
            }
        }
    }
    return  0;                              //S中不存在与T相等的子串
}

4.2 串的表示和实现

如果在程序设计语言中,串只是作为输入或输出的常量出现,则只需存储此串的串值,即字符序列,但在多数非数值处理的程序中,串也以变量的形式出现

  • 串的定长顺序存储表示(静态)

    #define MAXSTRLEN 255                             //用户可在255以内定义最大串长
    typedef unsigned char Sstring[MAXSTRLEN+1];       //0号单元存放串的长度

    串的实际长度可在这个预定义长度的范围内随意设定,超过预定义长度的串值则被舍去,称之为“截断”

    串的连接算法需要分三种情况进行处理

    Status Concat(SString S1, SString S2,  SString &T){
      //用T返回由S1和S2联接而成的串,若未截断,则返回True,否则返回False
      if(S1[0]  + S2[0] <= MAXSTRLEN){          //不需要截断
          T[1..S1[0]]  = S1[1..S1[0]];
          T[S1[0]+1..S1[0]+S1[0]]  = S2[1..S2[0]];
          T[0]  = S1[0]+S2[0];
          uncut  = TRUE;
      }else if(S1[0] < MAXSTRLEN){          //第一个串全部复制,第二个串只复制一部分
          T[1..S1[0]]  = S1[1..S1[0]];
          T[S1[0]+1..MAXSTRLEN]  = S2[1..MAXSTRLEN-S1[0]];
          T[0]  = MAXSTRLEN;
          uncut  = FALSE;
      }else{                                    //截断,且仅取S1的一部分
          T[0..MAXSTRLEN]  = S1[0..MAXSTRLEN];
          //T[0]  == S1[0] == MAXSTRLEN
          uncut  = FALSE;
      }
      return  uncut;
    }

    按这种串的表示方法实现的串的运算时,其基本操作为字符序列的复制

  • 串的堆分配存储表示(动态)

    不为每一个串分配一个数组空间,而是为所有的串变量提供一个串值的共享空间,而对每个串变量而言,它在计算机中的存储映像只是一个起始地址和一个串的长度

    通常,C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理,为每一个新产生的串分配一个存储区,称串值共享的存储空间为“堆”C语言中的串以一个空字符为结束符,串长是一个隐含值

    这类串操作的实现算法为:先为新生成的串分配一个存储空间,然后进行串值的复制

    typedef struct{
    char *ch;             //字符指针,若是非空串,则按照串长分配存储区,否则ch为NULL
    int length;       //串长度
    }
  • 串的块链存储表示

    此结构与链表类似,但其数据域中的内容不是一个字符,而是一个子串(否则会发生数据域的空间占用严重小于指针域,即存储密度过低,资源浪费)

    #define CHUNKSIZE 80          //可由用户定义块大小
    typedef struct Chunk{         //结点结构
      char  ch[CHUNKSIZE];      //每个结点放一个串
      struct  Chunk *next;
    }
    typedef struct{                   //链表结构
      Chunk  *head, *tail;      //串的头尾指针
      int  curlen;              //串的当前长度
    }

    串值也可用链表来存储,由于串的数据元素是一个字符,它只有8位二进制数,因此用链表存储时,通常一个结点中存放的不是一个字符,而是一个字符串,例如,在编辑器中,整个文本编辑区可以看成是一个串,每一行是一个子串,构成一个结点,即同一行的串定长结构,行和行之间用指针相联接

4.3 串的模式匹配算法(串的内容定位)

串的模式匹配是一个很重要的操作,在很多编辑软件中都有查找功能用于在文本中查找指定的内容,其实现方法就是串的模式匹配

以下为定长顺序结构表示串时的几种算法

  • 简单算法

    此算法的实现原理很简单,就是字符匹配,首先用子串的第一个字符与主串进行匹配,若匹配成功则比较子串的第二位与该匹配位的下一位是否一致,直到子串末位也匹配则结束算法并返回相应的元素位数,否则回退指针继续执行,即从头到尾逐个匹配

    此算法处理一般字符串的能力尚可,但在部分场合下性能损失较大,当其字符串内容为二进制时问题最为严重,其运行效率极其低下

    int Index(SString S, SString T, int pos){
      //返回子串T在主串S中第pos个字符之后的位置,若不存在,则函数值为0
      //其中,T为非空,1<=pos<=StrLength(S).
      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(i  > T[0]){
              return  i - T[0];
          }else{
              return  0;      
          }
      }
    }

    其时间复杂度为$O_{(S.length*T.length)}$​

  • 首位匹配算法

    首尾匹配算法是简单算法的改良版,先将子串的第一个字符与主串中的字符逐个匹配,随后检查子串的最后一个字符与主串中匹配的位置相应的最后一个字符是否匹配,若还是匹配则开始从第二个到第n-1个检查匹配,即先头后尾最后中

    int Index_FL(SString S, SString T, int  pos){
      sLength  = S[0];
      tLength  = T[0];
      i  = pos;
      patStartChar  = T[1];
      patEndChar  = T[tLength];
      while(i  <= sLength - tLength + 1){
          if(S[i]  != patStartChar){                    //匹配第一个字符
              ++  i;
          }else if(S[i  + tLength - 1] != patEndChar){//匹配最后一个字符
                  ++  i;
          }else{                                    //检查中同字符的匹配情况
              k  = 1;
              j  = 2;
              while(j  < tLength && S[i+k] == T[j]){
                  ++  k;
                  ++  j;
              }
              if(j  == tLength){
                  return  i;
              }else{
                  return  ++ i;                         //匹配失败,进入下一轮
              }
          }
      }
      return  0;
    }

    其时间复杂度为$O_{S.length*T.length}$

  • KMP算法

    上面的两个算法尽管可以实现其功能,但其在最坏情况下的时间复杂度均为两个字符串长度的乘积,也就是说性能不佳,极端情况下运行效率低下,因此有了KMP算法,通过避免主串指针回溯实现降低时间复杂度,其时间复杂度最坏仅$O_{(S.length+T.length)}$​

    其核心算法原理为:在简单算法执行到逐个字符匹配时,若某位不匹配的情况发生,则代表其匹配失败,此时主串上的指针将会进行回溯操作从下一位开始进行匹配,而KMP算法则恰恰使用了一个方法避免了该指针的回溯,请注意,当顺序匹配发生了这种情况时,代表主串上面的一部分事实上和子串的一部分是完全匹配的,也就是这一部分主串与子串一致,那么在这部分上面的主串与子串的匹配检查就可以变成子串对子串自身的匹配检查(也就是子串前面的一段与子串当前的后半段有部分完全相等),数字表示为:

    当S[i]<>T[j]时,已经得到的结果:S[i-j+1…i-1] == T[1…j-1]

    若已知 T[1…k-1] == T[j-k+1 … j-1]

    则有 S[i-k+1…i-1] == T[1…k-1]

    图像演示:
    $$
    主串:\begin{array}{|c|c|}
    \hline t&h&i&s&a&p&p&l&e&i&s&r&e&d\
    \hline
    \end{array}\
    子串:\begin{array}{|c|c|}
    \hline t&h&i&s&i&s&b&a&d&a&p&p&l&e\
    \hline
    \end{array}\
    $$
    当执行简单算法时会在this处停止开始回调,但此时可以发现,此部分主串与子串一致,即
    $$
    主串:\begin{array}{|c|c|}
    \hline t&h&i&s&a\
    \hline
    \end{array}\
    子串:\begin{array}{|c|c|}
    \hline t&h&i&s&i\
    \hline
    \end{array}\
    $$
    此时就可以将原本主串与子串的问题转换成子串自身的问题,即子串前面的一段与子串当前的后半段有部分完全相等,此实现方法也很简单,逐步移动子串指针即可,即:
    $$
    主串:\begin{array}{|c|c|}
    \hline t&h&i&s\
    \hline
    \end{array}\
    子串:\qquad\begin{array}{|c|c|}
    \hline t&h&i\
    \hline
    \end{array}\
    子串:\qquad\quad\begin{array}{|c|c|}
    \hline t&h\
    \hline
    \end{array}\
    子串: \qquad\qquad\quad\begin{array}{|c|c|}
    \hline t\
    \hline
    \end{array}\
    $$
    此时发现仍不匹配,则子串指针回溯到第一位结束,继续进行匹配,避免了主串指针的回溯,只需要继续比较即可
    $$
    主串:\begin{array}{|c|c|}
    \hline a&p&p&l&e&i&s&r&e&d\
    \hline
    \end{array}\
    子串:\begin{array}{|c|c|}
    \hline i&s&b&a&d&a&p&p&l&e\
    \hline
    \end{array}\
    $$
    定义next函数:(求子串(模式串)的next值(主串的每位上面子串的可匹配位数+1))

    求next函数值的过程是一个递推过程,分析如下:

    已知:next[1]=0;

    假设:next[j]=k;又T[j]=T[k];则next[j+1]=k+1;

    若:T[j] <> T[k] 则需往前回朔,检查T[j]==T[?]

    这实际上也是一个匹配递推的过程,不同在于:主串和模式串是一同一个串

    代码运算思路:初始为0,匹配则加一,不匹配则取对应位执行next函数的值,由于此算法写法不同编程语言大致相同,以下代码仅提供C版作为参考

    void get_next(SString &T, int &next[]){
      //求模式串T的next函数值并存入数组next
      i = 1;
      next[1] = 0;
      j = 0;
      while (i < T[0]){
          if (j == 0 || T[i] == T[j]){
              ++i;
              ++j;
              next[i] = j;
          }else{
              j = next[j];
          }
      }
    }

    KMP主函数

    int Index_KMP(SString S, SString T, int pos){
      //1  <= pos <= StrLength(S)
      i = pos;
      j = 1;
      while (i <= S[0] && j <= T[0]){
          if (j == 0 || S[i] == T[j]){
              ++i;
              ++j;
          }
        //继续比较后继字符
          else{
              j = next[j]; //模式串(子串)向右移动
          }
      }
      if (j > T[0]){
          return i - T[0]; //匹配成功
      }else{
          return 0;
      }
    }

    特殊情况的优化(next的优化)

    例如当 S=’aaabaaabaaabaaabaaab’,T=’aaaab’,此时会发生资源浪费(aaab与aaaab进行上述代码时会反复运算多次且运算结果多余)

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

4.4 总结

  1. 熟悉串的七种基本操作的定义,并能利用这些基本操作来实现串的其它各种操作方法。
  2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作方法。
  3. 掌握串的堆存储结构以及在其上实现串的基本方法。
  4. 理解串匹配的KMP算法,熟悉NEXT函数的定义,学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。
  5. 了解串操作的例子

5. 数组和广义表

5.1 数组的类型定义

多维数组中存在多个关系,其依靠关系的定义而以线性结构存在,即其内部的关系并非有一个关系或多个关系,而是每个关系均以线性的方式存在,但因其类型特点,只有引用型操作,没有加工型操作,而其多维结构是建立在一维结构的堆积上,因此存储空间均是一维结构,但注意,因为这种特点,在C等语言中直接不支持数组长度的变化(因为一维数组的大小不支持大小变更),但要注意存在动态数组问题,即通过一维数组的变更,临时生成一个新的一维数组来顶替原来位置的一维数组实现动态数组,以二维数组为例,其定义为

$数据成员:D = {a{ij}|a{ij} \in D \quad(0 \leq i \leq a-1,0 \leq j \leq b-1)} \$

$关系集 :\quad R = {R_1,R_2} \$

$行关系:\quad R1 = ROW = { <a{i,j-1},a_{i,j}> (0 \leq i \leq a-1,0 \leq j \leq b-1)}$

$列关系:\quad R2 = COL = { <a{i-1,j},a_{i,j}>(0 \leq i \leq a-1,0 \leq j \leq b-1)}$

即其最终表现形式为:
$$
a{(0,0)} \quad .\quad.\quad.\quad.\quad.\quad.\quad a{(0,b-1)} \
.\qquad \quad\quad\quad\quad\qquad\qquad\quad.\
.\qquad \quad\quad\quad\quad\qquad\qquad\quad.\
.\qquad \quad\quad\quad\quad\qquad\qquad\quad.\
.\qquad \quad\quad\quad\quad\qquad\qquad\quad.\
.\qquad \quad\quad\quad\quad\qquad\qquad\quad.\
\quad a{(a-1,0)}\quad .\quad.\quad.\quad.\quad.\quad.\quad a{(a-1.b-1)}
$$
基本操作:

InitArray(&A, n, bound1,…,boundn)   \\构造

DestoryArray(&A)                    \\销毁

Value(A, &e, index1,…,indexn)       \\赋值
初始条件:A是n维数组,e为元素变量,随后是n个下标值。
操作结果:若各个下标不超界,则e赋值为所指定的A的元素值,并返回OK

Assign(&A, e, index1,…,indexn)      \\取值
初始条件:A是n维数组,e为元素变量,随后是n个下标值。
操作结果:若下标不超界,则将e的值赋值给所指定的A元素,并返回OK.

5.2 数组的顺序表示和实现

因其结构特点以及设计要求,其只采用顺序映像表示(因为其更在乎执行速度而非扩展性),(当然,硬是要重构数组定义以此实现链式映像也不是不可以,只是运行速度以及空间占用问题严重,基本失去了价值,效率太低(时间复杂度直接以n的n次幂超高速增加)

而其有两种顺序映象的方式,一般使用(绝大多数语言都是)第一种

  1. 以行序为主序映像(低下标优先)
  2. 以列序为主序映像(高下标优先)

以行序为主序映像的二维数组的任意元素$a_{(i,j)}$的存储位置:

$LOC[i,j] = LOC[0,0] + (b * i + j)L \quad (其中,LOC[0,0]称为基地址或基址,L表示每个数据的存储占用)$

将其推广到一般情况,就可以得到n维数组数据元素的存储位置(但要注意,尽量不要使数组的维度大于3,因其检索效率会大幅度降低)

5.3 稀疏矩阵的压缩存储

稀疏矩阵是一个较为宽泛的概念,其描述了一个高维度数组中的大多数元素的值均等于0的情况,即利用率不高,因此,假定m行n列的矩阵含有t个非0元素,则有稀疏因子$\delta = \frac{t}{m*n}$

通常认为$\delta \leq 0.05$的矩阵为稀疏矩阵 即空间利用率小于百分之5

以常规方法使用二维数组表示高阶的稀疏矩阵时存在的问题有:

  1. 零值元素占的空间很大
  2. 计算中进行了很多和零值相关的运算降低了运算效率

解决问题的原则

  1. 尽可能少存或不存值为零值元素
  2. 尽可能减少没有实际意义的运算
  3. 运算方便,即可以尽可能快地找到与下标值(i,j)对应的元素;尽可能快地找到同一行或同一列的非零值元

特殊矩阵的压缩存储(如三角矩阵与对角矩阵)

三种随机稀疏矩阵的压缩存储方法(随机矩阵中的非零元分布不规则)

  1. 三元数组顺序表压缩

    #define MAXSIZE 12500
    typedef struct{
            int  i,j; //该非零元的行下标和列下标
            ElemType  e;
    }Triple; //三元组类型
    typedef union{   //使用联合,java可使用自定义类
            Triple  data[MAXSIZE+1];
            int  mu,nu,tu;
    }TSMatrix; //稀疏矩阵类型
    • 压缩原理:将原数组的数据使用一个带有规则定义的顺序表实现压缩存储

    $$
    如\left[
    \begin{matrix}
    0 & 3 & 0 &0 \
    0 & -1 & 0 &0 \
    0 & 0 & 8 &5
    \end{matrix}
    \right]
    可表示为:
    \begin{array}{|c|c|c|c|}
    \hline (1,2,3)&(2,2,-1)&(3,3,8)&(3,4,5)\
    \hline
    \end{array}
    \quad(3,4,4)
    $$

    • 三元组顺序表压缩矩阵的转置

      一般情况下,二维数组的矩阵转置方法如下所示(双for循环转置法)

      for(int i = 0;i < a.length;i++){
       for(int j = 0; j < a[i].length;j++){
          a[i][j] = a[i][j] ^ a[j][i];
           a[j][i] = a[i][j] ^ a[j][i];
           a[i][j] = a[i][j] ^ a[j][i];
       }
      }

      其时间复杂度为$O_{(i*j)}$

      三元组顺序表压缩矩阵的转置

      最简单的方法就是直接将顺序表中的前两个元素互换,但要注意,此时,将会导致原来的以行序为主序的矩阵变为以列序为主序的矩阵,但因为其理论上是可以达到线性的时间复杂度的,因此,以下给出一种方法以实现在不干扰主序的情况下进行矩阵的转置,其大致原理是先计算每个数据元素的在转置后的列序位置随后进行转置,直接将数据元素放置到对应位置以此实现快速转置,同时,其时间复杂度也会大幅度下降

      Status FastTransposeSMatrix(TSMatrix M,  TSMatrix &T){
      T.mu  = M.nu;
       T.nu  = M.mu;
       T.tu  = M.tu;
       if(T.tu){
           for(col  = 1; col <= M.nu; ++ col){
               num[col]  = 0;
           }      
           for(t  = 1; t <= M.tu; ++ t){
                ++  num[M.data[t].j];
           }      
           cpot[1]  = 1;
           for(col  = 2; col <= M.nu; ++ col){
               cpot[col]  = cpot[col-1] + num[col-1];
           }
           for(p  = 1; p <= M.tu; ++ p){
               //转置矩阵元素
           }
       }
       return  OK;
      }

      三元组顺序表又称有序的双下标法,它的特点是,非零元在表中按行序存储,因此便于进行依行顺序处理的矩阵运算。然而,若需随机存取某一行中的非零元,则需从头开始进行查找

  2. 行逻辑联接的顺序表

    修改前述的稀疏矩阵的结构定义,增加一个数据成员rpos,其值在稀疏矩阵的初始化函数中确定

    #define MAXMN 500
    typedef struct{
            Triple  data[MAXSIZE+1];
            int  rops[MAXMN+1];
            INT  mu,nu,tu;
    }RLSMatrix; //行逻辑链接顺序表类型

    矩阵乘法的经典算法

    for(i = 1; i <= m1; ++ i){
       for(j= 1; j <= n2; ++ j){
           Q[i][j]= 0;
           for(k= 1; k <= n1; ++ k){
               Q[i][j]+= M[i][k] * N[k][j];
           }
       }
    }

    其时间复杂度为:$O_{(m1n2n1)}$

    两个稀疏矩阵相乘

    if Q是非零矩阵{
       //逐行求积
       for(arow= 1; arow < M.mu; ++ arow){
        //处理M的每一行
        ctem[]= 0; //累加器清零
        //计算Q中第arow行的积并存入ctemp[]中;
            //将ctemp[]中非零元压缩存储到Q.data;
       }
    }
    Status MultSMatrix(RLSMatrixM, RLMatrixN, RLSMartrix &Q){
            if(M.nu  != N.mu){
                return  ERROR;
            }
            Q.mu  = M.mu;
            Q.nu  = N.nu;
            Q.tu  = 0;
            if(M.tu  * N.tu != 0){
                //Q是非零矩阵
                for(arow  = 1; arow <= M.mu; ++ arow){
                    //处理M的每一行
                    ctemp[]  = 0; //当前行各元素累加器清零
                    Q.rpos[arow]  = Q.tu + 1;
                    for(p  = M.rpos[arow]; p < M.rpos[arow+1]; ++ p){
                        //当前行中每一个非零元
                        brow  = M.data[p].j;
                        if(brow  < N.nu){
                            t  = N.rpos[brow+1];
                        }else{
                            for(q  = N.rpos[brow]; q < t; ++ q){
                                ccol  = N.data[q].j; //乘积元素在Q中列号
                                ctemp[ccol]  += M.data[p].e * N.data[q].e;
                            }
                        }
                    }  //求得Q中第crow(=arow)行的非零元
                    for(ccol  = 1; ccol <= Q.nu; ++ ccol){
                        if(ctemp[ccol]){
                            if(++  Q.tu > MAXSIZE){
                                return  ERROR;
                            }
                            Q.data[Q.tu]  = {arow, ccol, ctemp[ccol]);
                        }
                   }
              }
       }
       return  OK;
    }

    时间复杂度分析:略,生气(视频14)

  3. 十字链表

    没心情了(视频15)

  4. 了解数组的两种存储表示方法,并掌握数组以行为主的存储结构中地址计算方法

  5. 掌握对特殊矩阵进行压缩存储时下标变换公式

  6. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围,领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。

5.4 广义表的类型定义

5.5 广义表的表示方法

5.6 广义表操作的递归函数

6.树&二叉树

6.1树的类型定义

数据对象D:

D是具有相同特性的数据元素的集合

数据关系R:

若D为空集,则称为空树

否则:

  1. 当D中存在唯一的称为根的数据元素root
  2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,tm,其中每一棵子集本身又是一棵复合本定义的树,称为根root的子树
  • 基本术语

结点:数据元素+若干指向子树的分支

结点的度:分支的个数

树的度:树中所有结点的度数的最大值

叶子结点:度为零的结点

分支结点:度大于零的结点

从根到结点的路径:由从根到该结点所经分支和结点构成

孩子结点,双亲结点,兄弟结点,祖先结点,子孙结点

结点的层次:假设根结点的层次为1,第L层的结点的子树跟结点的层次为L+1

树的深度:树中叶子结点所在的最大层次

森林:是m(m>=0)棵互不相交的树的集合

二元组:任何一棵非空树是一个二元组,Tree=(root,F) 其中:root被称为根结点,F被称为子树森林

  • 基本操作

    1. 查找

      Root(T);                   //查找根
      Parent(T,cur_e)                //查找双亲结点
      LeftChild(T,cur_e)         //查找最左面孩子
      RightSibling(T,cur_e)      //查找右兄弟
      TreeEmpty(T)               //判空树
      TreeDepth(T)               //求树深度
      TraverseTree(T,visit())        //树的遍历
      Value(T,cur_e)             //取值
    2. 插入

      InitTree(&T);              //树的初始化
      CreateTree(&T,definition); //根据某些内容生成树
      Assign(T,cur_e,value);     //改变树的某个结点的值
      InsertChild(&T,&p,i,c);        //插入子树
    3. 删除

      ClearTree(&T);             //清空树
      DestoryTree(&T);           //销毁树
      DeleteChild(&T,&p,i);      //删除某个结点上的某棵子树
  • 有向树

    1. 有确定的根
    2. 树根和子树根之间为有向关系
  • 有序树和无序树的区别在于子树之间是否存在次序关系,一般情况下讨论无序树

  • 线性结构与树结构之间的区别

    线性结构 树结构
    第一个数据元素无前驱 根结点无前驱
    最后一个数据元素无后继 多个叶子结点无后继
    其它数据元素一个前驱,一个后继 树中其它结点一个前驱,多个后继

6.2二叉树的类型定义

二叉树或为空树,或是由一个根结点加上两科分别称为左子树和右子树的、互不相交的二叉树组成

二叉树的5种基本形态

数据结构

二叉树的特性

  1. 在二叉树的第i层上至多有$2^{i-1}$个结点 $(i \geq 1 )$
  2. 深度为h的树,它的结点树最多为$2^{h} - 1$个 $(k \geq 1)$
  3. $n_0 + n_1 + n_2 = n$
  4. 对任意一颗二叉树,若它含有$n{0}$个叶子结点,$n{2}$个度为2的结点,则必存在关系式$n_0 = n_2 + 1$
  5. 有 n 个结点的完全二叉树的深度为 $\log_2 n + 1$
  6. 若对含 n 个结点的二叉树从上到下且从左到右进行1到n的编号,则对二叉树中的任意一个编号为 i 的结点有
    • 若 i = 1,则该结点是二叉树的根,无双亲,否则,编号为 i /2 的结点为其双亲结点
    • 若 2i > n,则该结点无左孩子,否则,编号为 2i 的结点为其左孩子的结点
    • 若2i + 1 > n,则该结点无右孩子结点,否则,编号为 2i + 1的结点为其右孩子的结点

两类特殊二叉树

  1. 满二叉树:指的是深度为k且含有$2^k -1$个结点的二叉树
  2. 完全二叉树:树中所含的n个结点和满二叉树中编号为 1 到 n 的结点一一对应

6.3二叉树的存储结构

  • 二叉树的顺序存储表示

    #define MAX_TREE_SIZE 100                         //二叉树的最大结点数
    typedef TElemType SqBiTree[MAX_TREE_SIZE];        //0号单元存储根结点
    SqBiTree bt;

    和顺序表对数组的使用方式类似,其也是使用数组来表达二叉树,但其为了能够表达数的左右子树,因此,对于二叉树上面存在的无左右子树的任意一个的情况,其对应位置需要留空

  • 二叉树的链式存储表示

    由于二叉树存在2个后继,因此很适合使用链式存储的方法实现存储,其存在四种存储表示法:

    1. 二叉链表

      每个点有两个指针与,一个数据域,以此实现存储二叉树,但缺点是只能从上向下操作

      typedef struct BiTNode{
       TElemType  data;
       struct  BiTNode *lchild, *rchild;  //左右孩子指针
      }BiTNode, *BiTree;
    2. 三叉链表

      在二叉链表的基础之上,再添加一个指针域指向其双亲,由于添加了双亲的指针域,因此,其可以实现逆向操作

      typedef struct TriTNode{
       TElemType  data;
       struct TriTNode *lchild, *rchild;  //左右孩子指针
       struct  TriTNode *parent;          //双亲指针
      }TriTNode, *TriTree;
    3. 双亲链表

      双亲链表使用的是一个数组加上指针以实现快速定位的一种存储结构,其是在顺序结构的基础之上进行大幅度的改进实现的,通过指针结构以及标识避免了大量空结点的情况发生,且更加易于查找,即其将每个数据元素划分成三部分,第一部分存储数据,第二部分存储其双亲结点的指针,第三部分存储其是双亲的左孩子结点还是右孩子结点,缺点是插入结点存在效率过低的问题

      typedef struct BPTNode{
       TElemType  data;
       int  *parent;                      //指向双亲的指针
       char  LRTag;                       //左右孩子标识域
      }BPTNode;
      
      typedef struct BPTree{
       BPTNode  nodes[MAX_TREE_SIZE];
       int  num_node;                      //结点数目
       int  root;                              //根结点的位置
      }BPTree;
    4. 线索链表

      在后面

6.4 二叉树的遍历

  • 问题的提出

    遍历是任何类型均有的操作,对线性结构而言,只有一条搜索路径(因为每个结点均只有一个后继),故不需要另加讨论。而二叉树是非线性结构,每个结点有两个后继,则存在如何遍历,即按什么样的搜索路径遍历的问题

  • 解决思路

    对于二叉树而言,可以有三条搜索路径:

    1. 先上后下的按层次遍历
    2. 先左(子树)后右(子树)的遍历
    3. 先右(子树)后左(子树)的遍历

    先左后右的遍历算法

    1. 先(根)序的遍历算法

      若二叉树为空树,则空操作,否则:

      1. 访问根结点
      2. 先序遍历左子树
      3. 先序遍历右子树
    2. 中(根)序的遍历算法

      若二叉树为空树,则空操作,否则:

      1. 中序遍历左子树
      2. 访问根结点
      3. 中序遍历右子树
    3. 后(根)序的遍历算法

      若二叉树为空树,则空操作,否则:

      1. 后序遍历左子树
      2. 后序遍历右子树
      3. 访问根结点
  • 遍历算法的描述

    先序遍历二叉树(递归)

    void Preorder(BiTree T, void(*  visit)(TElemType &c)){
      if(T){
          visit(T->data);               //访问结点
          Preorder(T->lchild,  visit);  //遍历左子树
          Preorder(T->rchild,  visit);  //遍历右子树
      }
    }

    中序遍历二叉树(非递归)(使用栈完成)

    //左子树入栈
    BiTNode *GoFarLeft(BiTree T, Stack *S){
      if(!T){
          return  NULL; 
      }
      while(T->lchild){
          Push(S,  T);
          T  = T->lchild;
      }
      return  T;
    }
    
    //非递归中序遍历的算法
    void Inorder_l(BiTree T, void(*  visit)(TelemType &e)){
      Stack  *S;
      t  = GoFarLeft(T, S);                     //找到最左下的结点
      while(t){
          visit(t->data);                       //访问结点
          if(t->rchild){
              t  = GoFarLeft(t->rchild, S);
          }else  if(! StackEmpty(S)){       //栈不空时退栈
              t  = Pop(S);
          }else{
              t  = NULL;                        //栈空表明遍历结束
          }
      }
    }
  • 遍历算法的应用

    1. 统计二叉树中叶子结点的个数(先序遍历递归)

      void CountLeaf(BiTree T, int &count){
       if(T){
           if((!T->lchild) && (!T->rchild)){
                count  ++;
           }     
           CountLeaf(T->lchild);
           CountLeaf(T->rchild);
       }
      }
    2. 求二叉树的深度(后序遍历)

      int Depth(BiTree T){
       if(!T){
           depthval  = 0;
       }else{
           depthLeft  = Depth(T->lchild);
           depthRight  = Depth(T->rchild);
           depthval  = 1+(depthLeft > depthRight ? depthLeft : depthRight);
       }
       return  depthval;
      }
    3. 复制二叉树(后序遍历)

      //生成一个二叉树
      BiTNode *GetTreeNode(TElemType item,  BiTNode *lptr, BiTNode *rptr){
       if(!  (T = (BiTNode *) malloc(sizeof(BiTNode)))){
           exit(1);
       }    
       T->data  = item;
      T->lchild  = lptr;
      T->rchild  = rptr;
       return  T;
      }
      
      BiTNode *CopyTree(BiTNode *T){
       if(!  T){
           return  NULL;
       }
       if(T->lchild){
           newlptr  = CopyTree(T->lchild);
      `}else{
          newlptr  = NULL;
       }
       if(T->rchild){
           newrptr  = CopyTree(T->rchild);
       }else{
           newrptr  = NULL;
       }  
       newnode  = GetTreeNode(T->data, newlptr, newrptr);
          return  newnode;
      }
    4. 建立二叉树的存储结构

      //按给定的先序序列建立二叉树链表
      Status CreateBiTree(BiTree &T){
       scanf(&  ch);
       if(ch  == ''){
          T  = NULL;
       }else{
           if(!(T = (BiTNode *) malloc(sizeof(BiTNode))){
               exit(OVERFLOW);
           }
           T->data  = ch;                 //生成根结点
           CreateBiTree(T->lchild);   //构造左子树
           CreateBiTree(T->rchild);   //构造右子树
      }
       return  OK;
      }
      
      //按给定的表达式建相应二叉树(先缀表示建树)
      vodi CrtExptree(BiTree &T,  char exp[]){
       InitStack(S);
       Push(S,  '#');
       InitStack(PTR);
       p  = exp;
       ch  = *p;
       while(!  GetTop(S) == '#' && ch == '#')){
           if(!  IN(ch, OP)){
                CrtNode(t,  ch); //建立叶子结点并入栈
           }else{
               switch(ch){
                   case  '(':
                       Push(S,  ch);
                       break;
                   case  ')':
                       Pop(S, c);
                       while(c != '('){
                          CrtSubtree(t,  c); //创建二叉树并入栈
                          Pop(S,  c);
                      }
                  break;
                  while(! Gettop(S, c) &&  (precede(c, ch))){
                      CrtSubtree(t,  c);
                      Pop(S,  c);
                  }
                  if(ch != '#'){
                       Push(S,  ch);
                   }break;
                   default:
               }
           }
           if(ch  != '#'){
               p ++;
               ch  = *p;
           }
       }
       Pop(PTR,  t);
      }
      
      //创建叶子结点
      void CrtNode(BiTree &T, char ch){
       T  = (BiTNode *) malloc(sizeof(BiTNode));
       T->data  = char;
       T->lchild  = T->rchild = NULL;
       Push(PTR,  T);
      }
      
      //创建子树
      void CrtSubtree(BiTree &T, char c){
       T  = (BiTNode *) malloc(sizeof(BiTNode));
       T->data  = c;
       Pop(PTR,  rc);
       T->rchild  = rc;
       Pop(PTR,  lc);
       T->lchild  = lc;
       Push(PTR,  T);
      }

6.5 线索二叉树

  1. 何谓线索二叉树

    遍历二叉树的结果可以看作是求结点的一个线性序列,而指向该线性序列中的“前驱”和“后继”的指针称为“线索”,包含线索的存储结构就称为线索链表,与其相对应的二叉树就叫做线索二叉树

  2. 线索链表的遍历算法

  3. 如何建立线索表

6.6 树和森林的表示方法

6.7 树和森林的遍历

6.8哈夫曼树与哈夫曼编码

7.图

7.1 图的定义和术语

7.2 图的存储结构

7.3 图的遍历

7.4 图的连通性问题

7.5 有向无环图及其应用

7.6 最短路径

8.动态存储管理

8.1 概述

8.2 可利用空间表及分配方法

8.3 边界标识法

8.4 伙伴系统

8.5 无用单元收集

8.6 存储紧缩

9.查找

9.1 静态查找表

9.2 动态查找表

9.3 哈希表

10.内部排序

10.1 概述

10.2 插入排序

10.3 快速排序

10.4 选择排序

10.5 归并排序

10.6 基数排序

10.7 各种内部排序方法的比较讨论

11.外部排序

11.1 外存信息的存取

11.2 外部排序的方法

11.3 多路平衡归并的实现

11.4 置换一选择排序

11.5 最佳归并树

12.文件

12.1 有关文件的基本概念

12.2 顺序文件

12.3 索引文件

12.4 ISAM文件和VSAM文件

12.5 直接存取文件(散列文件)

12.6 多关键字文件

Q

  1. 从顺序表中删除⾃第i个元素起共k个元素

  2. 顺序表元素递减有序,将x插⼊顺序表中,保持其有序性

  3. 返回单链表中和元素x相等的序号,不存在该元素返回

  4. 单链表就地逆置

  5. la,lb为两个带头结点的单链表的头指针,从la中删除⾃第i个元素起共len个元素后,将他们插⼊表lb的第j个元 素前

  6. 顺序表比较大小

  7. 删除有序表中大于a小于b的元素

  8. 已知A,B,C三个有序链表,编写算法从A中删除B表和C表中共有的数据元素(删除三个链表中的共有元素)(有序优化)

  9. 双向循环链表的结点中,增加一个访问频度的数据域freq,编写算法实现搜索功能LOCATE(L,x)(需要根据访问频度对链表结构进行自适应优化)

  10. 给出区分给定的“栈操作”序列是否合法的准则,并证明两个不同的合法序列不可能得到相同的输出元素序列(视频17)(证明)

  11. 递归与递推(将递归程序写成递推程序)

    递归:

    status test(int &sum){
        int x;
        scanf(x);
        if(!x){
            sum = 0;
        }else{
            test(sum);
        }
        sum += x;
        printf(sum);
    }

    递推:

    void test(int sum){
        InitStack(S);
        scanf(x);
        while(x){
            Push(S,x);
            scanf(x);
        }                       //入栈
        sum = 0;
        printf(sum);
        while(!StackEmpty(S)){
            sum += Pop(S);
            printf(sum);
        }                       //出栈
    }
  12. 识别读入的字符是否是一个反对称的字符序列如:abcd的反对陈字符序列为:dcba

  13. 判断读入的字符是否是回文如:asdffdsa(分别出入栈与队列,看是否栈与队列的输出是否相等)(可优化,方法不唯一)

  14. 从串S中删除所有和串T相同的子串(KMP加删除功能实现)(以空串置换串S中所有与串T相同的子串?空连接问题)

  15. 求串S中出现的第一个最长重复子串(长度为S.length-1)及其位置(KMP的next方法,时间复杂度)(视频17 45min)

  16. 链表合并

  17. 复杂链表整理

  18. 回文链表(快慢指针法)

- THE END -

stvsl

6月22日19:57

最后修改:2022年6月22日
5

非特殊说明,本博所有文章均为博主原创。

共有 0 条评论