精华内容
下载资源
问答
  •   观察一下,j1=j4, j2=j5且i3=j1,i4=j2,所以回溯i指针到4的位置完全没有必要,根据上述等式关系,我们只需要将j指针的位置移动到j4的位置重新开始匹配。   再看一个例子: str=“aabababcaad” modStr=“babc...

    一. 模式匹配

      当有两个字符串Str = "abdabcde;modStr = "abcd";时,如果要在Str中查找与modelStr相等的子串,则称Str为主串,modelStr为模式串。在查找过程中,从Str中的第一个字符进行比较,如果找到与modelStr相同的子串,函数返回modelStr字符串第一次出现的位置,否则返回-1。以上过程就称为模式匹配.

    二. 模式匹配算法

      模式匹配算法,最广为人知的有两种算法,一种为简单且暴力的BF算法,一种为效率极高的KMP算法。下文将会对两种方法进行详解。

    1. 朴素模式匹配算法

      BF算法为朴素模式匹配算法的经典,该算法的主要思想,从主串的第一个字符与模式串中的第一个字符进行比较,若相等则继续比较,若不相等则从主串中不相等的位置与模式串中的第一个字符进行比较。
    在这里插入图片描述
      指针i指向主串,j指向模式串,当匹配失败时,i移动的位置为i = i - j + 1
      当所有字符串匹配成功后,指针j指向了模式串末尾的下一个,在进行匹配的过程中,不难发现,当每次匹配失败后,i指针都进行了不必要的回溯,这个回溯过程造成了时间的大量浪费。

    2. KMP算法

    1). KMP算法的优势

      上文讲述了BF算法的实现,也阐述了BF算法的效率低下之处,KMP算法就是针对BF算法的改良,当进行模式匹配时,出现字符比较不等的情况,不用回溯i指针,而是利用已经匹配过后的结果,向右尽可能滑动的稍远一些,再继续进行比较。

    2). KMP算法的原理

      以字符串Str = "acabaabaabcacaabc";modStr = "abaabcac";为例,进行说明:
      当i=8, j=6时,发现匹配失败: 如果按照BF算法, i指针会回溯至4的位置重新开始比较。但是这种i的回溯是有必要的吗?显然duck不必。
      观察一下,j1=j4, j2=j5且i3=j1,i4=j2,所以回溯i指针到4的位置完全没有必要,根据上述等式关系,我们只需要将j指针的位置移动到j4的位置重新开始匹配。
    在这里插入图片描述
      再看一个例子: str=“aabababcaad” modStr=“babc”,当i=6, j=4时发生失配,但j1=j3,所以直接将j指针移动到j4的位置,开始匹配。
    在这里插入图片描述
      再看最后一个例子,str=“aacabcd”, modStr=“abcd,当发生失配时,怎么操作。
      在发生失配时,将i指针向后移动一位,继续进行比较。
    在这里插入图片描述
      综合上述例子,不难看出模式串中存在着字符相同的元素,在模式串的子串中构成了前缀与后缀。并且在失配之后对于`i指针的移动存在一定的规律,从而引出了next数组的概念,next数组用于存放模式匹配失配时,模式串的滑动距离。

    3). next数组的构造

      通过上述的例子,已经得知next[]数组存放的内容为,模式串与目标串匹配失败时用于寻找模式串回溯位置的数组。
      如何计算next数组呢?其中最重要的概念就是最大前缀与最大后缀。
    在这里插入图片描述
      公式是这样表示最大前缀与最大后缀的,但是实际中如何求解呢。str="abaabcac"以这个字符串为例,表示出它的前缀与后缀。
    在这里插入图片描述
      对于这个字符串它的前缀与后缀是这样的,所以它的最大前缀=最大后缀的字符串是a;
      接下来就要通过这个最大前缀=最大后缀的概念,来进行失配后模式串回溯的位置计算。

      设模式串为abaabcac( j指向的位置为当前匹配位置,假设在当前位置失配,求出在当前位置失配的回溯位置,j指针前方字符串为要计算回溯位置的子串)
    1.j=1失配 (因为j=0 所以next[j]=0)
    在这里插入图片描述
    2.j=2失配 (没有前后缀,属于其他情况)
    在这里插入图片描述
    3.j=3失配(前缀不等与后缀)
    在这里插入图片描述

    4.j=4失配(最大前缀=最大后缀,所以k=2)
    在这里插入图片描述
    5.j=5失配
    在这里插入图片描述
    6.j=6失配 (最大前缀 ab = 最大后缀 ab, 所以k=3)
    在这里插入图片描述
    7.j=7失配
    在这里插入图片描述
    8.j=8失配

    在这里插入图片描述

      以上为next数组求法,但字符串下表一般从0开始,所以要对next数组中元素-1,得在这里插入图片描述
    至此,next数组已经求解完毕,如何利用next数组进行模式匹配,继续阅读下文。

    4). 利用next数组匹配的过程

      在这一部分,将会说明模式匹配是如何利用next数组进行模式匹配。
      以str = "acabaabaabcacaabc";modStr = "abaabcac";为例,字符串下标从0开始,进行说明:在这里插入图片描述

    1.第一次匹配(i=1,j=1位置发生失配)
    根据next数组可知,将j指针回溯到j0位置进行重新匹配。 在这里插入图片描述

    2.第二次匹配(i=1,j=0位置发生失配)
    next数组中没有相关跳转位置,所以i指针后移一位,开始匹配。 在这里插入图片描述

    3.第三次匹配(i=7,j=5位置发生失配)
    根据next数组,可知j回溯到 2的位置重新开始匹配 在这里插入图片描述
    4.匹配成功在这里插入图片描述
    以上就为KMP算法的匹配过程。

    二. KMP算法的代码实现

    1. 生成next[]数组

    void getNextArr(string modelStr, int* next)
    {
    	// 初始化next数组第一位为-1
    	int i = 0;
    	int j = -1;
    	next[0] = -1;
    
    	int mLen = modelStr.length();
    
    	while (i < mLen - 1)
    	{
    		// 求最大前缀=最大后缀的过程
    		if (j == -1 || modelStr[i] == modelStr[j])
    		{
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else
    		{
    			// 当没有匹配上 则进行回溯 回溯的位置为next数组的指向的下一个匹配项
    			j = next[j];
    		}
    	}
    }
    

    2. KMP查找过程代码

    // 如果查找成功返回位置
    // 如果查找失败返回-1
    int KMP(string dstStr, string modelStr)
    {
    	int i = 0;
    	int j = 0;
    
    	int dstlen = dstStr.length();
    	int modellen = modelStr.length();
    
    	int next[255] = { 0 };
    
    	getNextArr(modelStr, next);
    
    	while ((i < dstlen) && (j < modellen))
    	{
    		if (j == -1 || dstStr[i] == modelStr[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    
    	if (j >= modellen)
    	{
    		return i - modellen;   // 匹配成功 返回子串位置
    	}
    	else
    	{
    		return -1;
    	}
    }
    
    展开全文
  • 因为教材中的概念之间存在冲突,所以广泛浏览各类教材、视频,对数据结构进行系统、辩证的梳理。建议考研看不懂教材或者视频的同学看一看。

    为什么写这篇文章

    《数据结构》这门课有很多教材,各种概念十分混乱。为了解决概念之间的矛盾,写下这篇博客。
    比如严蔚敏的书中存在数据类型和数据结构的混乱,数据类型和ADT的混乱。书上所写本就自相矛盾,因此引用严书中的内容所写的文章或者录制的慕课大概率是存在问题的。

    计算机科学的各种定义是对实践经验的总结,掺杂了人的主观意识,也就是人为规定的,很多定义,包括数据 结构,至今没有被公认,不像自然定理一样亘古不变,所以建议从历史发展的角度,结合实践经验理解,不要死记硬背,但不是不要记!

    信息与数据

    数据是信息的载体,是描述客观事物的数字、字符、图片、声音等符号的集合,所有的数据在计算机中以二进制比特的形式表示。
    信息是数据的内涵。
    少量数据可能包含很多信息。似乎所有的数据都可能有用,正如黑格尔所说的“存在即合理”。

    数据、数据对象、数据元素、数据项之间的关系
    数据元素是数据的基本单位,也称为元素、记录等,通常作为一个整体考虑。
    数据项是组成数据元素的具有独立含义的、不可分割的最小单位。
    数据对象是性质相同的数据元素的集合。

    程序执行中所用的数据都存于内存。任何数据对象在能用期间都有存储位置,占据一定数量的存储单元。内存单元按顺序排,每个单元有一个称为内存地址的编号,内存数据都是通过地址访问的。高级语言把存储单元、地址等低级概念用变量等高级概念掩盖起来,使写程序时可以不必过多关心这方面细节。但内存与地址等仍是最基本的重要概念 。

    个人感觉,严书两个版本对数据元素的理解有不同。这从对数据结构的定义的差别中可以感受到。详见后文存储结构部分。
    若是按照严书1 理解,数据元素和关系区别开。
    若是按照严书2理解,数据元素包括数据和逻辑关系,即表示关系的数据也算是数据元素或数据元素的一部分。

    数据类型

    数据类型的本质是固定内存大小上的储存方案和操作方案
    数据类型关注的是比特组合表示什么,也就是怎么用比特组合表示数据的问题,关注的是一个数据元素的data representation。

    数据类型的概念最早出现在高级程序设计语言,发源于硬件,是一种解释计算机中的数据的手段。
    计算机内所有的的数据都是二进制数字,电路工程师设计一个CPU,需要人工制定一个规则来使用数据,要考虑如何对数字进行编码表示,并根据编码规则设计加法器、乘法器等。
    如果没有了这个规则,就说不清比特串代表什么,不知道从哪里开始到哪里结束代表一个数字,有可能8个比特代表一个整数,有可能16个比特代表一个整数,也可能是浮点数或者其他的数。
    工程师将数字按类别分组,用一个编码方式解释一个类里的所有数字,不同类的数字采用不同的编码方式。这个方法算是一种简单的抽象,毕竟总不能一个数字专门定制一个规则。

    写程序也就是要描述怎么表示数据并处理数据。
    高级程序设计语言,在硬件提供的编码方式的基础上,继续将数据抽象分类,使属于同一类型的数据具有相同的编码规则,并为程序员提供了数据描述机制。
    比如C语言,将若干位的比特数字规定为整型数字,并命名为int类型,还提供声明和定义机制,如int a;标识符a表示内存中的一块区域,按照int类型的规定使用这块区域。
    这种描述数据的机制,在程序设计中被规范地称为数据类型

    数据类型规定了一类数据所有可能取值的范围,以及在这些值上允许进行的操作。可能所有的CPU都提供int类型,但如果编码方式不同,能在其上进行的操作的过程不同,电路实现不同,严格地讲,就不能算作同一种数据类型。
    在计算机发展初期,计算机主要处理数值计算问题,整数、浮点数等是经常用到的运算对象,所以CPU一般会支持整数、浮点数等数字的计算。整数、浮点数等数据模型简单,不需要设计复杂的存储方法,因此不重视数据结构。

    随着程序设计的规范,抽象数据类型被提出。抽象数据类型(Abstract Data Type,简称ADT)是数据类型的数学抽象,是一个数学模型以及定义在该模型上的一组操作,不考虑其具体实现,也不依赖特定的编程语言。

    严蔚敏的数据结构中说,数据类型和抽象数据类型实质上是一个概念1。个人认为将两个概念当作一个是不严谨的。
    书中说是一个概念,是因为书中认为,对于使用数据类型的普通用户来说,不必了解的细节都被封装了,尽管实现不同,但数学特性相同,在用户看来都是一样的。而且数据结构的思想不依赖于特定的编程语言

    但是数据类型即使封装了细节,还是已经包含了具体实现,而抽象数据类型完全不涉及具体实现。当然我们在实际使用中,也确实对两个概念几乎完全不做区分,是因为大多时候我们不依赖于数据类型的实现细节,但这不代表不知道如何实现,有时也需要考虑数据类型的实现。

    对于高级的程序员,要多多少少对实现方法具备一些了解,即使不考虑数据类型的实现,也要或多或少地考虑程序设计语言的特性,并不是完全只需要考虑其数学上的抽象特性。
    对于依赖实现细节的硬件工程师来说,数据类型和抽象数据类型显然是不一样的。

    数据结构

    数据在内存或者硬盘中不是胡乱存储的,就像图书馆的书不是随便放在书架上的,所以为了研究怎么摆放计算机中的数据更好,就有了《数据结构》这门课。

    什么是数据结构

    数据结构是(数据对象)与(对象中数据元素之间的关系)的集合,是(逻辑上) 组织、(物理上)存储数据的方法,当然在计算机里也是数据,当然也是一门
    数据结构关注的是数据对象的data strorage。

    数据结构起源于程序设计,并随着程序设计的发展而发展。人们在进行程序设计时通常关注两个重要的问题,一是如何将待处理的数据存储到计算机内存中,二是如何设计相应的算法操作这些数据,即数据处理。数据表示的本质是数据结构设计,数据处理的本质是算法设计。
    计算机发展初期,人们使用计算机主要处理数值计算问题,所涉及的运算对象是简单的整数、浮点数、字符及布尔型数据,不需要设计复杂的存储方法,因此不重视数据结构。
    非数值计算的问题越来越重要,如何表示数据成为重要的问题,数据结构及抽象数据类型被提出,从而使程序设计越来越规范。

    在早期的面向过程的结构化程序设计中,程序设计一般原则——程序=数据结构+算法,就是先分析数据的数学模型和要对其进行的操作,确定如何存储数据和怎么实现操作,在这之后编写程序就很容易了。
    而结构化程序设计中,数据和过程分离,所以把数据结构定义为二元组(D,S),D为数据元素的有限集,S为关系的有限集,未考虑数据结构上的操作。由于结构化程序设计影响深远,所以习惯性地把数据结构定义为二元组。

    在面向对象程序设计中,数据结构可以看作一个容器对象。利用面向对象的开发方式,数据和过程放在一起,所以有时候,数据结构又包含了其上的操作,变成了三元组(D,S,P)。
    而我们上这门课,肯定是要讨论数据结构上的操作的,所以用面向对象的方法描述数据结构更合适。

    数据结构,作为一门课程,这门课研究的是(数据的逻辑上的组织方法和物理上的存储方法),也就是(先把数据模型化,再研究如何放在计算机里表示)。这门课不是程序设计课2.0,而是要通过精心设计数据结构,为程序带来更高的运行或者存储效率。

    所以数据结构包含逻辑结构存储结构两个层次(不是并列)。
    编写程序将逻辑结构映射成存储结构,并实现可在数据结构上进行的各种操作。

    以下几条来自不同教材里对数据结构的定义,对比体会。

    1. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。12
      个人认为,这句话把关系作为数据元素的定语,关系和数据元素的地位不够平等。书中也说这是书中的一种简单解释。而且第二版2由此出发的对存储结构的定义让人感觉有些疑惑。
    2. 数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系。3
    3. 数据结构是ADT的物理实现。4
      如果把数据结构当成一个容器对象,这个对象的抽象类,即ADT。 编程是在描述解决问题的办法,则在编程中,ADT的实现是对(组织、存储数据的方法和对数据进行的操作)的抽象模型的具体描述。想一想编程中如何实现数据结构,比如C语言,差不多就是声明结构类型和函数,将其定义,再初始化,好像很大一部分工作就是在实现某种ADT,也就是在具体描述组织、存储数据的方法和对数据进行的操作。在程序运行时,ADT的物理实现就可以是一个容器对象。

    逻辑结构

    逻辑结构从逻辑关系上描述数据,也就是数据的数学模型,与数据的在计算机中的存储无关。这个模型考虑的不只限于现有的有限数据,还要考虑范围更广的同类的数据。

    任意一个数据元素可以和n(n>=0)个数据元素有逻辑上的关系。
    逻辑结构可以分为四类:

    • 多对多的关系为图结构或网状结构;
    • 一对多为树结构;
    • 一对一为线性结构;
    • 除了同为一个集合外,别无其它关系为集合结构。
      逻辑结构也可以分为 线性结构 和 非线性结构两大类。
      可以认为,图结构表示的关系最复杂;树是一种特殊的图;线性结构是一种特殊的树结构,也是一种特殊的图结构;集合是没有关系的图结构。

    存储结构

    若是按照严书1,数据元素和关系区别开。
    ​数据结构在计算机中的表示(又称映像)称为数据的物理结构,又称存储结构。它包括数据元素的表示和关系的表示。
    ​数据元素的位串称为元素或节点,他的子位串称为数据域。因此元素或结点可看成是数据元素在计算机中的映像。

    若是按照严书2,数据元素包括数据和逻辑关系。
    数据对象在计算机中的存储表示称为数据的存储结构。把数据对象存储到计算机时,通常既要存储各数据元素的数据,又要存储数据元素之间的逻辑关系

    严书1提到数据元素之间的关系在计算机中有两种不同的表示方法:顺序映像和非顺序映像
    按照严书1的理解,重点在关系的表示。

    1. 顺序映像,借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,即通过相对位置来寻址。
    2. 非顺序映像,使用地址表示数据元素之间的逻辑关系。比如为了表示结点之间的关系,给每个结点附加指针字段,用于存放后继元素的存储地址。

    综合使用顺序映像和非顺序映像来存储数据,总结起来有四种基本方法,即殷人昆的书提到顺序存储方法链式存储方法索引存储方法散列存储方法5

    1. 顺序存储方法,该方法把逻辑上相邻的元素放到物理位置上相邻的存储单元中,数据元素之间的逻辑关系由顺序映像表示,也就是有存储单元的邻接位置关系来体现。由此得到的存储表示称为顺序存储结构。所谓的顺序不只包括无间隔的紧邻,诸如间隔k个字节,a^k个字节,都算是顺序存储。

    2. 链式存储方法,该方法不要求逻辑上相邻的元素在物理上相邻,㢝之间的逻辑关系由附加的指针指示。由此得到的存储表示称为链式存储结构

      1和2基本上是两个极端。顺序存储结构占用内存严重,链式存储结构寻址困难,综合两者的特性,做出寻址容易,插入删除也容易的数据结构。

    3. 索引存储方式,采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为(关键字、地址)。

    4. 散列存储方法,根据结点的关键字计算直接得到该结点的存储地址。

    四种基本存储方法,既可单独使用,也可组合使用。
    同一种逻辑结构使用不同的存储方法可以实现不同的存储结构。

    严书2提到数据元素在计算机中有两种基本的存储结构,分别是顺序存储结构和链式存储结构
    按照2的理解,有这两种基础的存储结构,可以组合成其他数据结构的存储结构,比如,散列表。

    总之,存储结构是逻辑结构在计算机中的物理映射,也就是抽象的数据在内存里的物理实现。
    把数据存储到计算机中,通常既要存储数据元素,又要存储数据元素之间的逻辑关系。
    存储结构=物理结构=存储表示=物理表示=存储映像=物理映像

    ADT、数据类型、数据结构之间的关系

    不同语言的《数据结构》

    数据结构考虑的是数据对象的Data storage——怎么存数据对象的问题,而数据类型考虑的是数据元素的Data representation——怎么表示数据元素的问题。

    6为了描述数据,程序语言提供的数据机制必须足够丰富,以满足人们写程序的实际需要。程序语言的机制不能无限地庞大,使语言过分臃肿,难以使用;这些机制也不应过于低级,一直需要描述一点点东西都非常繁琐。 后面这种情况正是机器语言和汇编语言的一个弱点。
    经过几十年的研究和实践,目前高级语言领域在这个方面已经形成了一套公认有效的方式,一般语言都采用这种模式的数据机制,其基本框架包括几个互相联系的方面:

    1. 把语言要处理的数据对象划分为一些类型,每个类型是一个数据值的集合。例如C语言里的int类型是这个类型能够表示的所有合法整数值的集合。
    2. 提供一组基本数据类型,为他们确定书写方式,提供一组相关的基本操作(运算),以支持程序中队基本数据类型的表示和使用。
    3. 提供了一组由简单的数据类型或数据对象构造更加复杂的数据类型或数据对象的手段,反复使用这些手段可以一层层地构造起任意复杂的数据结构,以满足程序中处理复杂数据的需要。

    市面上有各种语言的数据结构的书,但是程序设计语言只是一种描述数据结构的工具,我们当然可以不使用数据类型这个概念,可以不用某种高级程序设计语言,可以直接用01比特,可以只用自然语言描述数据结构,《数据结构》这门课归根结底是要想办法有组织地把01比特存储在内存中。
    不过为了简化描述抽象算法,分类与评价数据结构,使用高级程序设计语言,尤其是其中的ADT的概念,来讲解数据结构。
    ADT的思想和面向对象是一致的,我们既要考虑数据结构,也要考虑其上的操作,所以用面向对象的方法描述数据结构比较方便、有效,但本课程大都在大学低年级开设,用C语言的描述方法更符合学生的实际情况。
    数据结构是一门介于软件和硬件之间的课,重要的不是用什么语言,而是要理解数据逻辑上的组织方式和在内存中的存储方式,所以说这门课不是程序设计课。

    数据结构与抽象数据类型

    网友认为数据结构是一种抽象的封装,我们平时写程序都是直接去调用这些数据结构,而没有去想它们的内部实现是怎样的。
    这种想法有些不严谨。网友说的是编程语言的数据类型。
    《数据结构》这门课使用哪门语言不重要,重要的是抽象地描述,所以有的教材直接使用ADT的概念,而不是数据类型。
    可以认为,抽象数据类型,是逻辑结构+运算在程序设计中的等价概念,是数据结构的接口描述。

    从程序设计的角度看,抽象数据类型使用不同的存储方法可以实现不同的数据类型,然后在程序运行中,可以使用数据类型来存储数据,从而把逻辑结构表示为存储结构,并实现算法。例如,列表的抽象数据类型可以以数组或链表为基础来实现为数据类型。
    对于可操作数据对象完全相同的数据类型,如果给它定义具有不同功能的一组,则可形成不同的抽象数据类型。例如队列和优先级队列,它们可能使用相同的顺序表结构来实现为数据类型,但队列是先进先出,优先级队列是优先级高的先出,具有各不相同的服务,是不同的抽象数据类型。

    我们平时编程中调用的是封装好的数据类型或者数据类型模板,利用某种数据类型定义数据,把数据组织、存储成数据结构。
    比如C++的STL的vector,他是一个顺序型容器类模板,我们可以利用 vector类模板,定义一个可以存储并管理int类型数据的vector< int >类型的容器,容器是一个能存储并管理对象的对象。这个对象与存储在对象中的其他对象一起构成了一个数据结构,也就是带有关系的数据元素的集合。

    一般我们在高级程序设计语言的层面进行软件设计。抽象数据类型处于软件层面,是编程语言理论的概念。而数据结构是在硬件和软件之中都有被用到,和语言无关,关注的是数据逻辑上的组织方式和在内存中是怎么存储的,最终还是要实现为01比特流。在编程中,我们使用数据类型描述组织、存储数据的方式和操作。在程序运行中,把数据元素组织、存储成带关系的数据元素的集合,也就是数据结构的存储结构。

    反过来说,数据结构是组织和存储的方法,而不是操作方法。我们可以把组织和存储的方法和操作方法结合并抽象成数据类型,在更高的层次上进行软件分析和设计。

    抽象数据类型的概念与面向对象方法的思想是一致的。。。。未完待续

    未完待续

    孤立地理解某一个概念,而不注意他们之间的联系是不可取的。
    比如,我们想定义一个整数类型,数学里的整数取值范围是无穷的。
    由于CPU的工作机制决定了它每次计算的数得是定长的,而定长就表示它只能表示有限范围内的数。虽然只要内存无限,当然可以设计出没有位数上限的整数运算的硬件。但是CPU为了通用,只提供最基本数据类型,不提供其他多余的功能。
    那么我们通过软件的方式来实现一个取值范围无穷的整数类型,使用高级程序设计语言提供的int类型构造这个ADT,显然逻辑上是线性结构,存储上可以选择链表或者顺序表。

    未完待续


    1. 严蔚敏,吴伟民,数据结构(C语言版) ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

    2. 严蔚敏,李冬梅,吴伟民,数据结构(C语言版)(第二版) ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

    3. Clifford A.Shaffer, 数据结构与算法分析 ↩︎

    4. Sartaj Sahni,数据结构、算法与应用 ↩︎

    5. 殷人昆,数据结构(用面向对象方法与C++语言描述)(第二版) ↩︎

    6. 裘宗燕,从问题到程序——程序设计与C语言引论 ↩︎

    展开全文
  • 王道考研数据结构笔记

    万次阅读 多人点赞 2021-04-15 22:43:48
    ##2022王道考研数据结构笔记 第二章 线性表(更新中) 我也看得太慢了吧sos 2.1 线性表的定义和基本操作 要点: 线性表的基本操作——创销、增删、改查 传入参数时,何时要用引用 & 2.2 线性表的顺序表示 ...
    王道考研数据结构笔记

    第二章 线性表

    2.1 线性表的定义和基本操作

    要点:

    1. 线性表的基本操作——创销、增删、改查
    2. 传入参数时,何时要用引用 &

    2.2 线性表的顺序表示

    2.2.1 顺序表的定义

    1. 顺序表的实现———静态分配
    #include <stdio.h>
    #define MaxSize 10      //定义最大长度 
    typedef struct{
        int data[MaxSize];  //用静态的“数组”存放数据元素 ElemType:int
        int Length;         //顺序表的当前长度
    }SqList;                //顺序表的类型定义
    
    //基本操作——初始化一个顺序表
    void InitList(SqList &L){
        for(int i=0; i<MaxSize; i++){
            L.data[i]=0;   //将所有数据元素设置为默认初始值0,如果没有这一步,内存中会有遗留的“脏数据”
        }
        L.Length=0;        //顺序表初始长度为0
    }
    
    int main(){
        SqList L;          //声明一个顺序表
                           //在内存里分配存储顺序表L的空间
                           //包括MaxSize*sizeof(ElemType)和存储length的空间
        InitList(L);       //初始化这个顺序表
        //...
        return 0;
    }
    
    1. 顺序表的实现——动态分配

    malloc函数:

    L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize) 其中(ElemType*)可强制转换数据类型

    #include <stdlib.h> //malloc,free函数的头文件
    #define InitSize 10 //默认的最大长度
    
    typedef struct{
        int *data;       //指示动态分配数组的指针
        int MaxSize;    //顺序表的最大容量
        int length;     //顺序表的当前长度
    }SeqList;
    
    void InitSize(SeqList &L){
        L.data = (int*)malloc(sizeof(int)*InitSize);  //用malloc函数申请一片连续的存储空间
        L.length = 0;
        L.MaxSize = InitSize;
    }
    
    int main(){
        SeqList L;
        InitSize(L);
        //...其余操作
        IncreaseSize(L,5);
        return 0;
    }
    
    //增加动态数组的长度
    void IncreaseSize(SeqList &L, int len){
        int *p=L.data
        L.data = (int*)malloc((L.MaxSize+len)*sizeof(int));
        for(int i=0; i<L.length; i++){
            L.data[i] = p[i]         //将数据复制到新区域
        }
        L.MaxSize = L.MaxSize + len; //顺序表最大长度增加len
        free(p);                     //释放原来的内存空间
    }
    

    2.2.2 顺序表上基本操作的实现 (插入和删除)

    1. 顺序表基本操作——插入

    ListInsert(&L,i,e)

    基于静态分配的代码实现

    #define MaxSize 10      //定义最大长度 
    typedef struct{
        int data[MaxSize];  //用静态的“数组”存放数据元素 ElemType:int
        int Length;         //顺序表的当前长度
    }SqList;                //顺序表的类型定义
    
    //基本操作——在L的位序i处插入元素e
    bool ListInsert(SqList &L, int i, int e){ 
        //判断i的范围是否有效
        if(i<1||i>L.length+1) 
            return false;
        if(L.length>MaxSize) //当前存储空间已满,不能插入  
            return false;
    
        for(int j=L.length; j>i; j--){    //将第i个元素及其之后的元素后移
            L.data[j]=L.data[j-1];
        }
        L.data[i-1]=e;  //在位置i处放入e
        L.length++;      //长度加1
        return true;
    }
    
    int main(){
        SqList L;          //声明一个顺序表
        InitList(L);       //初始化这个顺序表
        //...插入几个元素
        ListInsert(L,3,3);
        return 0;
    }
    

    时间复杂度分析

    • 关注最深层循环语句——L.data[j]=L.data[j-1]的执行次数与问题规模n——L.length的关系;
    • 最好情况:插入表尾,不需要移动元素,i=n+1,循环0次;最好时间复杂度 = O(1)
    • 最坏情况:插入表头,需要将原有的n个元素全都向后移动,i=1,循环n次;最坏时间复杂度 = O(n)
    • 平均情况:假设新元素插入到任何一个位置的概率p(=1/n+1)相同
    插入到第i个位置循环次数
    1n
    2n-1
    3n-2
    n+10

    平均循环次数 = np + (n-1)p + (n-2)p + … + 1×p = [ n(n+1)/2 ]×[ 1/(n+1) ] = n/2

    平均时间复杂度 = O(n)

    1. 顺序表基本操作——删除

    ListDelete(&L,i,e):删除表L中的第i个位置的元素,并用e返回删除元素的值
    基于静态分配的代码实现

    #define MaxSize 10      //定义最大长度 
    typedef struct{
        int data[MaxSize];  //用静态的“数组”存放数据元素 ElemType:int
        int Length;         //顺序表的当前长度
    }SqList;                //顺序表的类型定义
    
    bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数 
        //判断i的范围是否有效
        if(i<1||i>L.length) 
            return false;
    
        e = L.data[i-1]    //将被删除的元素赋值给e
    
        for(int j=L.length; j>i; j--){    //将第i个后的元素前移
            L.data[j-1]=L.data[j];
        }
        L.length--;      //长度减1
        return true;
    }
    
    int main(){
        SqList L;          //声明一个顺序表
        InitList(L);       //初始化这个顺序表
        //...插入几个元素
        int e = -1;        //用变量e把删除的元素“带回来”
        if(LisDelete(L,3,e))
            printf("已删除第三个元素,删除元素值=%d\n",e);
        else
            printf("位序i不合法,删除失败\n");
        return 0;
    }
    

    时间复杂度分析

    • 关注最深层循环语句——L.data[j-1]=L.data[j]的执行次数与问题规模n——L.length的关系;
    • 最好情况:删除表尾元素,不需要移动元素,i=n,循环0次;最好时间复杂度 = O(1);
    • 最坏情况:删除表头元素,需要将后续的n-1个元素全都向前移动,i=1,循环n-1次;最坏时间复杂度 = O(n);
    • 平均情况:假设删除任何一个元素(1,2,3,…,length)的概率相同 p=1/n
    删除第i个元素循环次数
    1n-1
    2n-2
    3n-3
    n0

    平均循环次数 = (n-1)p + (n-2)p + … + 1×p = [ n(n-1)/2 ]×[ 1/(n) ] = n-1/2

    平均时间复杂度 = O(n)

    1. 顺序表基本操作——按位查找(顺序表)

    GetElem(L,i) : 按位查找操作——获取表L中第i个位置元素的值

    基于静态分配的代码实现

    #define MaxSize 10            //定义最大长度 
    typedef struct{
        ElemType data[MaxSize];  //用静态的“数组”存放数据元素 
        int Length;              //顺序表的当前长度
    }SqList;                     //顺序表的类型定义
    
    ElemType GetElem(SqList L, int i){
        // ...判断i的值是否合法
        return L.data[i-1];      //注意是i-1
    }
    

    基于动态分配的代码实现

    #define InitSize 10  //顺序表的初始长度
    
    typedef struct{
        ElemType *data;  //指示动态分配数组的指针
        int MaxSize;     //顺序表的最大容量
        int length;      //顺序表的当前长度
    }SeqList;
    
    ElemType GetElem(SqList L, int i){
        // ...判断i的值是否合法
        return L.data[i-1]; //就算是指针也能用数组下标哦!
    }
    

    时间复杂度分析

    O(1)
    由于顺序表的各个数据元素在内存中连续存放,因此可以根据起始地址数据元素大小立即找到第i个元素———“随机存取”特性;

    1. 顺序表基本操作——按值查找

    LocateElem(L, e): 按值查找操作,在表L中查找具有给定关键字值的元素;

    基于动态分配的代码实现

    #define InitSize 10            //定义最大长度 
    typedef struct{
        ElemTyp *data;  //用静态的“数组”存放数据元素 
        int Length;              //顺序表的当前长度
    }SqList;   
    
    //在顺序表L中查找第一个元素值等于e的元素,并返回其位序
    int LocateElem(SqList L, ElemType e){
        for(int i=0; i<L.lengthl i++)
            if(L.data[i] == e)  
                return i+1;     //数组下标为i的元素值等于e,返回其位序i+1
        return 0;               //推出循环,说明查找失败
    }
    

    Q: 如果顺序表里存放的是结构类型的数据元素,可不可以用 == 进行比较?

    A: 不能!结构类型的比较,需要依次对比各个分量来判断两个结构体是否相等;

    例:

    typedef struct{
        int num;
        int people;
    }Customer;
    
    void test(){
        Customer a;
        Customer b;
        //...
        if (a.num == b.num && a.people == b.people){
            printf("相等");
        }else{
            printf("不相等");
        }
    }
    

    时间复杂度分析

    • 最深处循环语句: if(L.data[i] == e) 与问题规模n=L.length(表长)的关系;
    • 最好情况:查找目标元素在表头,循环1次,最好时间复杂度=O(1)
    • 最坏情况:查找目标元素在表尾,循环n次,最好时间复杂度=O(n)
    • 平均情况:假设目标元素出现在任何一个位置的概率相同,p=1/n
    目标元素所在位置i循环次数
    11
    22
    33
    nn

    平均循环次数 = 1×1/n + 2×1/n +…+ n×1/n = [ n(n+1)/2 ] × 1/n = (n+1)/2

    平均时间复杂度 = O(n)

    在这里插入图片描述

    2.3 线性表的链式表示

    2.3.1 单链表的定义

    1. 何为单链表?
    • 链式存储
    • 每个结点存储:数据元素自身信息 & 指向下一个结点(后继)的指针
    • 优点:不要求大片连续空间,改变容量方便
    • 缺点:不可随机存取,要耗费一定空间存放指针
    1. 代码定义单链表
    struct LNode{            //定义单链表节点类型  LNode:结点
        ElemType data;       //每个结点存放一个数据元素 data:数据域
        struct LNode *next;  //指针指向下一个结点 next:指针域
    };
    

    增加一个新的结点:在内存中申请一个结点所需的空间,并用指针p指向这个结点

    struct LNode* p = (struct LNode*) malloc(sizeof(struct LNode))
    

    如果每次都要写struct很麻烦,所以可以利用typedef关键字——数据类型重命名:type<数据类型><别名>

    Eg:

    typedef int zhengshu;
    typedef int *zhengshuzhizhen;  //指向int型的指针
    

    上面操作可以化简为:

    typedef struct LNode LNode;
    
    LNode* p = (LNode*) malloc(sizeof(LNode))
    

    最简洁代码实现:

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    

    以上代码等同于:

    struct LNode{           
        ElemType data;       
        struct LNode *next; 
    };
    
    typedef struct LNode LNode; //重命名
    typedef struct LNode *LinkList; 
    

    要表示一个单链表时,只需声明一个头指针L,指向单链表的第一个结点:

    LNode *L;    // 声明一个指向单链表第一个结点的指针,强调这是结点
    //或者
    LinkList L;  // 声明一个指向单链表第一个结点的指针,强调这是链表
    
    1. 两种实现方法
    • 不带头结点的单链表
    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    //初始化一个空的单链表
    bool InitList(LinkList &L){  //注意用引用 &
        L = NULL; //空表,暂时还没有任何结点;
        return true;
    }
    
    void test(){
        LinkList L;  //声明一个指向单链表的指针: 头指针
        //初始化一个空表
        InitList(L);
        //...
    }
    
    //判断单链表是否为空
    bool Empty(LinkList L){
        if (L == NULL)
            return true;
        else
            return false;
    }
    
    
    • 带头结点的单链表
    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    //初始化一个单链表(带头结点)
    bool InitList(LinkList &L){  
        L = (LNode*) malloc(sizeof(LNode));  //头指针指向的结点——分配一个头结点(不存储数据)
        if (L == NULL)          //内存不足,分配失败
            return false;
        L -> next = NULL;       //头结点之后暂时还没有结点
        return true;
    }
    
    void test(){
        LinkList L;  //声明一个指向单链表的指针: 头指针
        //初始化一个空表
        InitList(L);
        //...
    }
    
    //判断单链表是否为空(带头结点)
    bool Empty(LinkList L){
        if (L->next == NULL)
            return true;
        else
            return false;
    }
    

    不带头结点 V.S. 带头结点

    • 不带头结点:写代码麻烦!对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑,对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
    • 带头结点:头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据;

    2.3.2 单链表上基本操作的实现

    1. 单链表的插入

    • 按位序插入 (带头结点)

    ListInsert(&L, i, e): 在表L中的第i个位置上插入指定元素e = 找到第i-1个结点(前驱结点),将新结点插入其后;其中头结点可以看作第0个结点,故i=1时也适用。

    代码实现

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    //在第i个位置插入元素e(带头结点)
    bool ListInsert(LinkList &L, int i, ElemType e){  
        //判断i的合法性, i是位序号(从1开始)
        if(i<1)
            return False;
        
        LNode *p;       //指针p指向当前扫描到的结点 
        int j=0;        //当前p指向的是第几个结点
        p = L;          //L指向头结点,头结点是第0个结点(不存数据)
    
        //循环找到第i-1个结点
        while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
            p = p->next;             //p指向下一个结点
            j++;
        }
    
        if (p==NULL)                 //i值不合法
            return false;
        
        //在第i-1个结点后插入新结点
        LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
        s->data = e;
        s->next = p->next;
        p->next = s;                 //将结点s连到p后,后两步千万不能颠倒qwq
    
        return true;
    }
    
    

    时间复杂度分析

    最好情况:插入第1个位置 O(1)

    最坏情况:插入表尾 O(n)

    平均时间复杂度 = O(n)

    • 按位序插入 (不带头结点)

    ListInsert(&L, i, e): 在表L中的第i个位置上插入指定元素e = 找到第i-1个结点(前驱结点),将新结点插入其后; 因为不带头结点,所以不存在“第0个”结点,因此!i=1 时,需要特殊处理——插入(删除)第1个元素时,需要更改头指针L;

    代码实现

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    bool ListInsert(LinkList &L, int i, ElemType e){
        if(i<1)
            return false;
        
        //插入到第1个位置时的操作有所不同!
        if(i==1){
            LNode *s = (LNode *)malloc(size of(LNode));
            s->data =e;
            s->next =L;
            L=s;          //头指针指向新结点
            return true;
        }
    
        //i>1的情况与带头结点一样!唯一区别是j的初始值为1
        LNode *p;       //指针p指向当前扫描到的结点 
        int j=1;        //当前p指向的是第几个结点
        p = L;          //L指向头结点,头结点是第0个结点(不存数据)
    
        //循环找到第i-1个结点
        while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
            p = p->next;             //p指向下一个结点
            j++;
        }
    
        if (p==NULL)                 //i值不合法
            return false;
        
        //在第i-1个结点后插入新结点
        LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
        s->data = e;
        s->next = p->next;
        p->next = s;          
        return true;
    
    }
    

    除非特别声明,否则之后的代码都默认为带头结点哦,做题注意审题

    • 指定结点的后插操作

    InsertNextNode(LNode *p, ElemType e): 给定一个结点p,在其之后插入元素e; 根据单链表的链接指针只能往后查找,故给定一个结点p,那么p之后的结点我们都可知,但是p结点之前的结点无法得知;

    代码实现

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    bool InsertNextNode(LNode *p, ElemType e){
        if(p==NULL){
            return false;
        }
    
        LNode *s = (LNode *)malloc(sizeof(LNode));
        //某些情况下分配失败,比如内存不足
        if(s==NULL)
            return false;
        s->data = e;          //用结点s保存数据元素e 
        s->next = p->next;
        p->next = s;          //将结点s连到p之后
    
        return true;
    }                         //平均时间复杂度 = O(1)
    
    
    //有了后插操作,那么在第i个位置上插入指定元素e的代码可以改成:
    bool ListInsert(LinkList &L, int i, ElemType e){  
        if(i<1)
            return False;
        
        LNode *p;       //指针p指向当前扫描到的结点 
        int j=0;        //当前p指向的是第几个结点
        p = L;          //L指向头结点,头结点是第0个结点(不存数据)
    
        //循环找到第i-1个结点
        while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
            p = p->next;             //p指向下一个结点
            j++;
        }
    
        return InsertNextNode(p, e)
    }
    
    • 指定结点的前插操作

    Q: 如何找到p结点的前驱节点?

    A: 传入头指针L!就可以知道整个链表的信息了!

    InsertPriorNode(LinkList L, LNode *p, ElemType e):循环查找p的前驱q,再对q进行后插操作,时间复杂度为O(n);

    Q: 那如果不传入头指针L呢?

    不传入头指针L的代码实现

    //前插操作:在p结点之前插入元素e
    bool InsertPriorNode(LNode *p, ElenType e){
        if(p==NULL)
            return false;
        
        LNode *s = (LNode *)malloc(sizeof(LNode));
        if(s==NULL) //内存分配失败
            return false;
    
        //重点来了!
        s->next = p->next;
        p->next = s;       //新结点s连到p之后
        s->data = p->data; //将p中元素复制到s
        p->data = e;       //p中元素覆盖为e
    
        return true;
    }  //时间复杂度为O(1)
    

    王道书版本代码

    bool InsertPriorNode(LNode *p, LNode *s){
        if(p==NULL || S==NULL)
            return false;
        
        s->next = p->next;
        p->next = s;  ///s连接到p
        ELemType temp = p->data;  //交换数据域部分
        p->data = s->data;
        s->data = temp;
    
        return true;
    }
     
    

    2. 单链表的删除

    • 按位序删除(带头结点)

    ListDelete(&L, i, &e): 删除操作,删除表L中第i个位置的元素,并用e返回删除元素的值;头结点视为“第0个”结点;

    思路:找到第i-1个结点,将其指针指向第i+1个结点,并释放第i个结点;

    代码实现

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    bool ListDelete(LinkList &L, int i, ElenType &e){
        if(i<1) return false;
    
        LNode *p;       //指针p指向当前扫描到的结点 
        int j=0;        //当前p指向的是第几个结点
        p = L;          //L指向头结点,头结点是第0个结点(不存数据)
    
        //循环找到第i-1个结点
        while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
            p = p->next;             //p指向下一个结点
            j++;
        }
    
        if(p==NULL) 
            return false;
        if(p->next == NULL) //第i-1个结点之后已无其他结点
            return false;
    
        LNode *q = p->next;         //令q指向被删除的结点
        e = q->data;                //用e返回被删除元素的值
        p->next = q->next;          //将*q结点从链中“断开”
        free(q)                     //释放结点的存储空间
    
        return true;
    }
    
    

    时间复杂度分析:

    最坏,平均时间复杂度:O(n)

    最好时间复杂度:删除第一个结点 O(1)

    • 指定结点的删除

    删除结点p,需要修改其前驱结点的next指针(两个方法);

    "偷天换日"代码实现

    bool DeleteNode(LNode *p){
        if(p==NULL)
            return false;
        
        LNode *q = p->next;      //令q指向*p的后继结点
        p->data = p->next->data; //让p和后继结点交换数据域
        p->next = q->next;       //将*q结点从链中“断开”
        free(q);
        return true;
    } //时间复杂度 = O(1)
    

    但是 如果p是最后一个结点,那么p->next = q->next and p->data = p->next->data 就会出错,只能从表头开始依次寻找o的前驱,时间复杂度为O(n); 这就是单链表的局限性——无法逆向检索。

    3. 单链表的查找

    探讨带头结点!

    • 按位查找

    GetElem(L, i): 按位查找操作,获取表L中第i个位置的元素的值;

    代码实现

    LNode * GetElem(LinkList L, int i){
        if(i<0) return NULL;
        
        LNode *p;               //指针p指向当前扫描到的结点
        int j=0;                //当前p指向的是第几个结点
        p = L;                  //L指向头结点,头结点是第0个结点(不存数据)
        while(p!=NULL && j<i){  //循环找到第i个结点
            p = p->next;
            j++;
        }
    
        return p;               //返回p指针指向的值
    }
    

    平均时间复杂度 = O(n)

    王道书版本代码

    LNode * GetElem(LinkList L, int i){
        int j=1;                //从第一个结点开始
        LNode *p = L->next      //p先指向第一个结点
    
        if(i==0) return L;
        if(i<1)  return NULL;
    
        while(p!=NULL && j<i){  //循环找到第i个结点
            p = p->next;
            j++;
        }
    
        return p;               //返回p指针指向的值
    }
    

    那么上一节的按位插入和按位删除就可以封装了!
    在这里插入图片描述

    • 按值查找

    LocateElem(L, e):按值查找操作,在表L中查找具有给定关键字值的元素;

    代码实现

    LNode * LocateElem(LinkList L, ElemType e){
        LNode *P = L->next;    //p指向第一个结点
        //从第一个结点开始查找数据域为e的结点
        while(p!=NULL && p->data != e){
            p = p->next;
        }
        return p;           //找到后返回该结点指针,否则返回NULL
    }
    

    注意当ElemType是结构体时的操作

    4. 求单链表的长度

    Length(LinkList L)

    代码实现 (带头结点)

    int Length(LinkList L){
        int len=0;       //统计表长
        LNode *p = L;
        while(p->next != NULL){
            p = p->next;
            len++;
        }
        return len;
    }
    

    平均时间复杂度= O(n)

    5. 单链表的建立

    思路: 初始化一个单链表 -> 每取一个数据元素,插入到表尾/表头

    核心: 初始化操作 and 指定结点的后插操作

    探讨带头结点!

    • 尾插法建立单链表
    初始化单链表
    
    设置变量length记录链表当前的长度
    
    while循环{
        每次取一个数据元素e;
        ListInsert(L, length+1, e)插到尾部;
        length++;
    }
    
    

    但是,因为每次都要执行↓,就是每次都要从头开始遍历,时间复杂度为O(n²)

    while(p!=NULL && j<i-1){     
        p = p->next;             
        j++;
    }
    

    解决方法:设置一个表尾指针r,对r这个结点进行后插操作InsertNextNode()

    最终代码实现

    LinkList List_TailInsert(LinkList &L){       //正向建立单链表
        int x;                                   //设ElemType为整型int
        L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)
        LNode *s, *r = L;                        //r为表尾指针
        scanf("%d", &x);                         //输入要插入的结点的值
        while(x!=9999){                          //输入9999表结束
            s = (LNode *)malloc(sizeof(LNode));
            s->data = x;
            r->next = s;
            r = s                                //r指针指向新的表尾结点
            scanf("%d", &x);   
        }
        r->next = NULL;                          //尾结点指针置空
        return L;
    }
    

    平均时间复杂度:O(n)

    • 头插法建立单链表

    对头结点进行后插操作InsertNextNode()

    初始化单链表
    
    while循环{
        每次取一个数据元素e;
        InsertNextNode(L, e);
    }
    

    最终代码实现

    LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表
        LNode *s;
        int x;
        L = (LinkList)malloc(sizeof(LNode));     //建立头结点
        L->next = NULL;                          //初始为空链表,这步不能少!
    
        scanf("%d", &x);                         //输入要插入的结点的值
        while(x!=9999){                          //输入9999表结束
            s = (LNode *)malloc(sizeof(LNode));  //创建新结点
            s->data = x;
            r->next = L->next;
            L->next = s;                         //将新结点插入表中,L为头指针
            scanf("%d", &x);   
        }
        return L;
       
    }
    

    PS: 只要是初始化单链表,都先将头指针指向NULL — L->next = NULL;

    重要应用:链表的逆置

    详细见CSDN:单链表逆置—头插法图解

    • 算法思想:逆置链表初始为空,原表中结点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空;
    LNode *Inverse(LNode *L)
    {
    	LNode *p, *q;
    	p = L->next;     //p指针指向第一个结点
    	L->next = NULL;  //头结点指向NULL
    
    	while (p != NULL){
    		q = p;
    		p = p->next;
    		q->next = L->next;  
    		L->next = q;
    	}
    	return L;
    
    

    2.3.3 双链表

    双链表中节点类型的描述:

    typedef struct DNode{            //定义双链表结点类型
        ElemType data;               //数据域
        struct DNode *prior, *next;  //前驱和后继指针
    }DNode, *DLinklist;
    
    1. 双链表的初始化 (带头结点)
    typedef struct DNode{            //定义双链表结点类型
        ElemType data;               //数据域
        struct DNode *prior, *next;  //前驱和后继指针
    }DNode, *DLinklist;
    
    //初始化双链表
    bool InitDLinkList(Dlinklist &L){
        L = (DNode *)malloc(sizeof(DNode));      //分配一个头结点
        if(L==NULL)                              //内存不足,分配失败
            return false;
        
        L->prior = NULL;   //头结点的prior指针永远指向NULL
        L->next = NULL;    //头结点之后暂时还没有结点
        return true;
    }
    
    void testDLinkList(){
        //初始化双链表
        DLinklist L;         // 定义指向头结点的指针L
        InitDLinkList(L);    //申请一片空间用于存放头结点,指针L指向这个头结点
        //...
    }
    
    //判断双链表是否为空
    bool Empty(DLinklist L){
        if(L->next == NULL)    //判断头结点的next指针是否为空
            return true;
        else
            return false;
    }
    

    与单链表中一样,DLinklist 强调链表, DNode *强调结点,二者本质上等价;

    1. 双链表的插入操作
    • 后插操作

    InsertNextDNode(p, s): 在p结点后插入s结点

    代码实现:

    bool InsertNextDNode(DNode *p, DNode *s){ //将结点 *s 插入到结点 *p之后
        if(p==NULL || s==NULL) //非法参数
            return false;
        
        s->next = p->next;
        if (p->next != NULL)   //p不是最后一个结点=p有后继结点  
            p->next->prior = s;
        s->prior = p;
        p->next = s;
        
        return true;
    }
    
    • 按位序插入操作

    思路:从头结点开始,找到某个位序的前驱结点,对该前驱结点执行后插操作;

    • 前插操作

    思路:找到给定结点的前驱结点,再对该前驱结点执行后插操作;

    1. 双链表的删除操作

    删除p的后继结点q

    p->next = q->next;
    q->next->prior = p;
    free(q);
    

    如果要删除的结点q是最后一个结点,会出现错误,故增加条件判断以提高代码健壮性

    代码实现

    //删除p结点的后继结点
    bool DeletNextDNode(DNode *p){
        if(p==NULL) return false;
        DNode *q =p->next;            //找到p的后继结点q
        if(q==NULL) return false;     //p没有后继结点;
        p->next = q->next;
        if(q->next != NULL)           //q结点不是最后一个结点
            q->next->prior=p;
        free(q);
    
        return true;
    }
    
    //销毁一个双链表
    bool DestoryList(DLinklist &L){
        //循环释放各个数据结点
        while(L->next != NULL){
            DeletNextDNode(L);  //删除头结点的后继结点
        free(L); //释放头结点
        L=NULL;  //头指针指向NULL
    
        }
    }
    
    1. 双链表的遍历操作
      后向遍历
    while(p!=NULL){
        //对结点p做相应处理,eg打印
        p = p->next;
    }
    

    前向遍历

    while(p!=NULL){
        //对结点p做相应处理,eg打印
        p = p->prior;
    }
    

    如果我们不想处理头结点,那就跳过头结点!

    while(p->prior!=NULL){
        //对结点p做相应处理
        p = p->prior;
    }
    

    注意 双链表不可随机存取,按位查找和按值查找操作都只能用遍历的方式实现,时间复杂度为O(n)

    在这里插入图片描述

    2.3.4 循环链表

    1. 循环单链表

    最后一个结点的指针不是NULL,而是指向头结点

    typedef struct LNode{            
        ElemType data;               
        struct LNode *next;  
    }DNode, *Linklist;
    
    /初始化一个循环单链表
    bool InitList(LinkList &L){
        L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
        if(L==NULL)             //内存不足,分配失败
            return false;
        L->next = L;            //头结点next指针指向头结点
        return true;
    }
    
    //判断循环单链表是否为空
    bool Empty(LinkList L){
        if(L->next == L)
            return true;    //为空
        else
            return false;
    }
    
    //判断结点p是否为循环单链表的表尾结点
    bool isTail(LinkList L, LNode *p){
        if(p->next == L)
            return true;
        else
            return false;
    }
    

    单链表 & 循环单链表

    • 单链表:从一个结点出发只能找到该结点后续的各个结点;对链表的操作大多都在头部或者尾部;设立头指针,从头结点找到尾部的时间复杂度=O(n),即对表尾进行操作需要O(n)的时间复杂度;

    • 循环单链表:从一个结点出发,可以找到其他任何一个结点;设立尾指针,从尾部找到头部的时间复杂度为O(1),即对表头和表尾进行操作都只需要O(1)的时间复杂度;

    可以让L指向表尾元素(插入,删除时可能需要修改L)

    2. 循环双链表

    表头结点的prior指向表尾结点,表尾结点的next指向头结点

    typedef struct DNode{          
        ElemType data;               
        struct DNode *prior, *next;  
    }DNode, *DLinklist;
    
    //初始化空的循环双链表
    bool InitDLinkList(DLinklist &L){
        L = (DNode *) malloc(sizeof(DNode));    //分配一个头结点
        if(L==NULL)            //内存不足,分配失败
            return false;  
        L->prior = L;          //头结点的prior指向头结点
        L->next = L;           //头结点的next指向头结点
    }
    
    void testDLinkList(){
        //初始化循环单链表
        DLinklist L;
        InitDLinkList(L);
        //...
    }
    
    //判断循环双链表是否为空
    bool Empty(DLinklist L){
        if(L->next == L)
            return true;
        else
            return false;
    }
    
    //判断结点p是否为循环双链表的表尾结点
    bool isTail(DLinklist L, DNode *p){
        if(p->next == L)
            return true;
        else
            return false;
    }
    

    双链表 & 循环双链表

    • 插入操作

    对于循环双链表,操作 p->next->prior = s 不会出问题辣!因为就算p是最后一个结点,也不会出现空指针现象了(这个问题在双链表里会出现!)

    bool InsertNextDNode(DNode *p, DNode *s){ 
        s->next = p->next;
        p->next->prior = s;
        s->prior = p;
        p->next = s;
    
    • 删除操作

    和插入操作一样!q->next->prior 对于循环双链表不会出错了

    //删除p的后继结点q
    p->next = q->next;
    q->next->prior = p;
    free(q);
    

    2.3.5 静态链表

    1. 何为静态链表
    • 单链表: 各个结点散落在内存中的各个角落,每个结点有指向下一个节点的指针(下一个结点在内存中的地址);

    • 静态链表——用数组的方式实现的链表: 分配一整片连续的内存空间,各个结点集中安置,包括了——数据元素and下一个结点的数组下标(游标)

      • 其中数组下标为0的结点充当"头结点"
      • 游标为-1表示已经到达表尾
      • 若每个数据元素为4B,每个游标为4B,则每个结点共8B;假设起始地址为addr,则数据下标为2的存放地址为:addr+8*2
      • 注意: 数组下标——物理顺序,位序——逻辑顺序;
      • 优点:增、删操作不需要大量移动元素;
      • 缺点:不能随机存取,只能从头结点开始依次往后查找,容量固定不变!
    1. 代码定义一个静态链表
    #define MaxSize 10        //静态链表的最大长度
    
    struct Node{              //静态链表结构类型的定义
        ElemType data;        //存储数据元素
        int next;             //下一个元素的数组下标(游标)
    };
    
    //用数组定义多个连续存放的结点
    void testSLinkList(){
        struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node
        //...
    }
    

    也可以这样:

    #define MaxSize 10        //静态链表的最大长度
    
    typedef struct{           //静态链表结构类型的定义
        ELemType data;        //存储数据元素
        int next;             //下一个元素的数组下标
    }SLinkList[MaxSize];
    
    void testSLinkList(){
        SLinkList a;
    }
    

    上面这个代码等同于

    #define MaxSize 10        //静态链表的最大长度
    
    struct Node{              //静态链表结构类型的定义
        ElemType data;        //存储数据元素
        int next;             //下一个元素的数组下标(游标)
    };
    
    typedef struct Node SLinkList[MaxSize]; //重命名struct Node,用SLinkList定义“一个长度为MaxSize的Node型数组;
    
    

    PS: SLinkList a 强调a是静态链表;struct Node a 强调a是一个Node型数组;

    1. 静态链表基本操作的实现
    • 初始化静态链表:把a[0]next设为-1

    • 查找某个位序(不是数组下标,位序是各个结点在逻辑上的顺序)的结点:从头结点出发挨个往后遍历结点,时间复杂度O=(n)

    • 在位序为i上插入结点:① 找到一个空的结点,存入数据元素;② 从头结点出发找到位序为i-1的结点;③修改新结点的next;④ 修改i-1号结点的next;

    Q:如何判断结点为空?

    A:在初始化时,将空闲结点的next设置为某个特殊值,eg:-2;

    • 删除某个结点:① 从头结点出发找到前驱结点;② 修改前驱节点的游标;③ 被删除节点next设为-2;
    #define MaxSize 10        //静态链表的最大长度
    
    typedef struct{           //静态链表结构类型的定义
        ELemType data;        //存储数据元素
        int next;             //下一个元素的数组下标
    }SLinkList[MaxSize];
    

    2.3.6 顺序表和链表的比较

    1. 逻辑结构

    • 顺序表和链表都属于线性表,都是线性结构

    2. 存储结构

    • 顺序表:顺序存储
      • 优点:支持随机存取,存储密度高
      • 缺点:大片连续空间分配不方便,改变容量不方便
    • 链表:链式存储
      • 优点:离散的小空间分配方便,改变容量方便
      • 缺点:不可随机存取,存储密度低

    3. 基本操作 - 创

    • 顺序表:需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源;

      • 静态分配:静态数组,容量不可改变
      • 动态分配:动态数组,容量可以改变,但是需要移动大量元素,时间代价高(malloc(),free()
    • 链表:只需要分配一个头结点或者只声明一个头指针

    4. 基本操作 - 销毁

    • 顺序表:修改 Length = 0

      • 静态分配:静态数组——系统自动回收空间
        typedef struct{
            ElemType *data;
            int MaxSize;
            int length;
        }SeqList;
        
      • 动态分配:动态数组——需要手动free
        //创
        L.data = (ELemType *)malloc(sizeof(ElemType) *InitSize)
        //销
        free(L.data);
        
        //!malloc() 和 free() 必须成对出现
        
    • 链表:依次删除各个结点 free()

    5. 基本操作 - 增/删

    • 顺序表:插入/删除元素要将后续元素后移/前移;时间复杂度=O(n),时间开销主要来自于移动元素;

    • 链表:插入/删除元素只需要修改指针;时间复杂度=O(n),时间开销主要来自查找目标元素

    6. 基本操作 - 查

    • 顺序表

      • 按位查找:O(1)
      • 按值查找:O(n),若表内元素有序,可在O(log2n)时间内找到
    • 链表:

      • 按位查找:O(n)
      • 按值查找:O(n)

    7. 开放式问题答题思路

    Q: 请描述顺序表和链表的balabalabala…实现线性表时,用顺序表还是链表好?

    A: 顺序表和链表的存储结构都是线性结构,都属于线性表;但是二者的存储结构不同,顺序表采用顺序存储…(特点,优缺点);链表采用链式存储…(特点,优缺点);由于采用不同的存储方式实现,因此基本操作的实现效率也不同;当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…;当查找一个数据元素时…;

    第三章 栈和队列

    3.1 栈 (stack)

    3.1.1 栈的基本概念

    1. 栈的定义
    • 栈是特殊的线性表:只允许在一端进行插入或删除操作, 其逻辑结构与普通线性表相同;
    • 栈顶:允许进行插入和删除的一端 (最上面的为栈顶元素);
    • 栈底:不允许进行插入和删除的一端 (最下面的为栈底元素);
    • 空栈:不含任何元素的空表;
    • 特点:后进先出(后进栈的元素先出栈);
    • 缺点:栈的大小不可变,解决方法——共享栈;
    1. 栈的基本操作 (运算)

    "创&销"

    • InitStack(&S) 初始化栈:构造一个空栈S,分配内存空间;
    • DestroyStack(&S) 销毁栈:销毁并释放栈S所占用的内存空间;

    "增&删"

    • Push(&S, x) 进栈:若栈S未满,则将x加入使其成为新栈顶;
    • Pop(&S, &x) 出栈:若栈S非空,则弹出(删除)栈顶元素,并用x返回;

    "查&其他"

    • GetTop(S, &x) 读取栈顶元素:若栈S非空,则用x返回栈顶元素;(栈的使用场景大多只访问栈顶元素);
    • StackEmpty(S) 判空: 断一个栈S是否为空,若S为空,则返回true,否则返回false
    1. 栈的常见题型
    • 给个进栈顺序,判断有哪些合法的出栈顺序;
    例:进栈顺序为:a -> b -> c -> d -> e
        
        合法的出栈顺序:e d c b a / b e d c a (出栈和进栈交替进行) / ... 
        
    

    3.1.2 栈的顺序存储

    1. 顺序栈的定义
    #define MaxSize 10         //定义栈中元素的最大个数
    
    typedef struct{
        ElemType data[MaxSize];       //静态数组存放栈中元素
        int top;                      //栈顶元素
    }SqStack;
    
    void testStack(){
        SqStack S;       //声明一个顺序栈(分配空间)
                         //连续的存储空间大小为 MaxSize*sizeof(ElemType)
    }
    
    1. 顺序栈的基本操作
    #define MaxSize 10         //定义栈中元素的最大个数
    
    typedef struct{
        ElemType data[MaxSize];       //静态数组存放栈中元素
        int top;                      //栈顶元素
    }SqStack;
    
    //初始化栈
    void InitStack(SqStack &S){
        S.top = -1;                   //初始化栈顶指针
    }
    
    //判栈空
    bool StackEmpty(SqStack S){
        if(S.top == -1)      //栈空
            return true;
        else                 //栈不空
            return false;
    }
    
    //新元素进栈
    bool Push(SqStack &S, ElemType x){
        if(S.top == MaxSize - 1)        //栈满
            return false;
        
        S.top = S.top + 1;    //指针先加1
        S.data[S.top] = x;    //新元素入栈
    
        /*
        S.data[++S.top] = x;
        */
        return true;
    }
    
    //出栈
    bool Pop(SqStack &x, ElemType &x){
        if(S.top == -1)          //栈空
            return false;
        
        x = S.data[S.top];       //先出栈
        S.top = S.top - 1;       //栈顶指针减1
        return true;
    
        /*
        x = S.data[S.top--];
        */
    
        //只是逻辑上的删除,数据依然残留在内存里
    
    }
    
    //读栈顶元素
    bool GetTop(SqStack S, ElemType &x){
        if(S.top == -1)
            return false;
        
        x = S.data[S.top];      //x记录栈顶元素
        return true; 
    }
    
    
    void testStack(){
        SqStack S;       //声明一个顺序栈(分配空间)
        InitStack(S);
        //...
    }
    

    PS: 也可以初始化时定义 S.top = 0 :top指针指向下一个可以插入元素的位置(栈顶元素的后一个位置);

    • 判空:if(S.top == 0)

    • 进栈使用:S.data[S.top++] = x;

    • 出栈使用:x = S.data[--S.top];

    • 判断栈满:s.top == MaxSize

    1. 共享栈

    两个栈共享同一片空间

    #define MaxSize 10         //定义栈中元素的最大个数
    
    typedef struct{
        ElemType data[MaxSize];       //静态数组存放栈中元素
        int top0;                     //0号栈栈顶指针
        int top1;                     //1号栈栈顶指针
    }ShStack;
    
    //初始化栈
    void InitSqStack(ShStack &S){
        S.top0 = -1;        //初始化栈顶指针
        S.top1 = MaxSize;   
    }
    
    

    栈满条件:top0 + 1 == top1

    3.1.3 栈的链式存储结构

    1. 用链式存储方式实现的栈
    • 进栈和出栈都只能在栈顶一端进行(链头作为栈顶)
    • 链表的头部作为栈顶,意味着:
      • 在实现数据"入栈"操作时,需要将数据从链表的头部插入;
      • 在实现数据"出栈"操作时,需要删除链表头部的首元节点;

    因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表;

    typedef struct Linknode{
        ElemType data;              //数据域
        struct Linknode *next;      //指针域
    }*LiStack;                      //栈类型的定义
    
    1. 链栈的基本操作 (类比单链表的操作 / 带头结点&不带头结点)

    参考:链栈基本操作(带头结点及不带头结点)

    • 初始化
    • 进栈
    • 出栈
    • 获取栈顶元素
    • 判空、判满

    带有头结点的链栈基本操作

    #include<stdio.h>
    
    struct Linknode{
        int data;             //数据域
        Linknode *next;       //指针域
    }Linknode,*LiStack;   
    
    typedef Linknode *Node;   //结点结构体指针变量
    typedef Node List;        //结点结构体头指针变量
    
    //1. 初始化
    void InitStack(LiStack &L){   //L为头指针
        L = new Linknode; 
        L->next = NULL;
    }
    
    //2.判栈空
    bool isEmpty(LiStack &L){
        if(L->next == NULL){
            return true;
        }
        else
            return false;
    }
    
    //3. 进栈(:链栈基本上不会出现栈满的情况)
    void pushStack(LiStack &L, int x){
        Linknode s;          //创建存储新元素的结点
        s = new Linknode;
        s->data = x;
    
        //头插法
        s->next = L->next;
        L->next = s;
    }
    
    //4.出栈
    bool popStack(LiStack &L, int &x){
        Linknode s;
        if(L->next == NULL) //栈空不能出栈
            return false;
        
        s = L->next;
        x = s->data;
        L->next = L->next->next;
        delete(s);
    
        return true;
    }
    
    
    

    不带头结点的链栈基本操作

    #include<stdio.h>
    
    struct Linknode{
        int data;             //数据域
        Linknode *next;       //指针域
    }Linknode,*LiStack;   
    
    typedef Linknode *Node;   //结点结构体指针变量
    typedef Node List;        //结点结构体头指针变量
    
    //1.初始化 
    void initStack(LiStack &L){
        L=NULL;
    }
    
    //2.判栈空
    bool isEmpty(LiStack &L){
        if(L == NULL)
            return true;
        else
            teturn false;
    }
    
    //3.进栈
    void pushStack(LiStack &L, int x){
        Linknode s;          //创建存储新元素的结点
        s = new Linknode;
    
        s->next = L;
        L = s;
    }
    
    //4.出栈
    bool popStack(LiStack &L, int &x){
        Linknode s; 
        if(L = NULL)     //栈空不出栈
            return false;
    
        s = L;
        x = s->data;
        L = L->next;
        delete(s);
        
        return true;
    }
    

    3.2 队列(Queue)

    3.2.1 队列的基本概念

    1. 队列的定义
    • 队列是操作受限的线性表,只允许在一端进行插入 (入队),另一端进行删除 (出队)
    • 操作特性:先进先出 FIFO
    • 队头:允许删除的一端
    • 队尾:允许插入的一端
    • 空队列:不含任何元素的空表
    1. 队列的基本操作

    "创&销"

    • InitQueue(&Q): 初始化队列,构造一个空列表Q
    • DestroyQueue(&Q): 销毁队列,并释放队列Q所占用的内存空间

    "增&删"

    • EnQueue(&Q, x): 入队,若队列Q未满,将x加入,使之成为新的队尾
    • DeQueue(&Q, &x): 出队,若队列Q非空,删除队头元素,并用x返回

    "查&其他"

    • GetHead(Q,&x): 读队头元素,若队列Q非空,则将队头元素赋值给x
    • QueueEmpty(Q): 判队列空,若队列Q为空,则返回true

    3.2.2 队列的顺序存储结构

    • 队头指针:指向队头元素;

    • 队尾指针:指向队尾元素的后一个位置(下一个应该插入的位置)

    1. 队列的顺序存储结构的基本操作
    //队列的顺序存储类型
    # define MaxSize 10;     //定义队列中元素的最大个数
    typedef struct{
        ElemType data[MaxSize];   //用静态数组存放队列元素
                                  //连续的存储空间,大小为——MaxSize*sizeof(ElemType)
        int front, rear;          //队头指针和队尾指针
    }SqQueue;
    
    //初始化队列
    void InitQueue(SqQueue &Q){
        //初始化时,队头、队尾指针指向0
        Q.rear = Q.front = 0;
    }
    
    void test{
        SqQueue Q;                //声明一个队列
        InitQueue(Q);
        //...
    }
    
    // 判空
    bool QueueEmpty(SqQueue 0){
        if(Q.rear == Q.front)    //判空条件后
            return true;
        else 
            return false;
    }
    
    1. 循环队列

    Q: 能否用 Q.rear == MaxSize 作为队列满的条件?

    A: 不能!会有假溢出, 所以需要用 模运算 将存储空间 {0,1,2,…,MaxSize} 在逻辑上变成“环状”——循环队列!

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7CPbzxxS-1620744230788)(循环队列.PNG)]

    a%b == a除以b的余数

    初始:Q.front = Q.rear = 0;

    队首指针进1:Q.front = (Q.front + 1) % MaxSize

    队尾指针进1:Q.rear = (Q.rear + 1) % MaxSize —— 队尾指针后移,当移到最后一个后,下次移动会到第一个位置

    队列长度:(Q.rear + MaxSize - Q.front) % MaxSize

    循环队列如何判满

    Q: 能否用Q.rear == Q.front 作为队列满的条件?

    A: 不能!这已经作为队列空的判断条件了;

    方案一: 牺牲一个单元来区分队空和队满

    队尾指针的再下一个位置就是队头,即 (Q.rear+1)%MaxSize == Q.front

    • 循环队列——入队:只能从队尾插入(判满使用方案一)
    bool EnQueue(SqQueue &Q, ElemType x){
        if((Q.rear+1)%MaxSize == Q.front)        //队满
            return false;
        Q.data[Q.rear] = x;                      //将x插入队尾
        Q.rear = (Q.rear + 1) % MaxSize;         //队尾指针加1取模
    
        return true;
    }
    
    
    • 循环队列——出队:只能让队头元素出队
    //出队,删除一个队头元素,用x返回
    bool DeQueue(SqQueue &Q, ElemType &x){
        if(Q.rear == Q.front)              //队空报错
            return false;  
    
        x = Q.data[Q.front];
        Q.front = (Q.front + 1) % MaxSize; //队头指针后移动
    
        return true;
    }
    
    • 循环队列——获得队头元素
    bool GetHead(SqQueue &Q, ElemType &x){
        if(Q.rear == Q.front)              //队空报错
            return false;  
    
        x = Q.data[Q.front];
        return true;
    }
    

    方案二: 不牺牲存储空间,设置size

    定义一个变量 size用于记录队列此时记录了几个数据元素,初始化 size = 0,进队成功 size++,出队成功size--,根据size的值判断队满与队空

    队满条件:size == MaxSize

    队空条件:size == 0

    # define MaxSize 10;     
    typedef struct{
        ElemType data[MaxSize];   
        int front, rear;        
        int size;               //队列当前长度
    }SqQueue;
    
    //初始化队列
    void InitQueue(SqQueue &Q){
        Q.rear = Q.front = 0;
        size = 0;
    }
    

    方案三: 不牺牲存储空间,设置tag

    定义一个变量 tagtag = 0 --最近进行的是删除操作;tag = 1 --最近进行的是插入操作;

    • 每次删除操作成功时,都令tag = 0;只有删除操作,才可能导致队空;
    • 每次插入操作成功时,都令tag = 1;只有插入操作,才可能导致队满;

    队满条件:Q.front == Q.rear && tag == 1

    队空条件:Q.front == Q.rear && tag == 0

    # define MaxSize 10;     
    typedef struct{
        ElemType data[MaxSize];   
        int front, rear;        
        int tag;               //最近进行的是删除or插入
    }SqQueue;
    
    

    其他出题方法——队尾指针指向队尾元素

    • 判空
    (Q.rear + 1) % MaxSize == Q.front
    
    • 判满

      • 方案一:牺牲一个存储单元
      • 方案二:增加辅助变量
    • 入队操作

    Q.rear = (Q.rear + 1) % MaxSize; //后移一位
    Q.data[Q.rear] = x; 
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bJHGyMSI-1620744230792)(队列顺序实现.PNG)]

    3.2.3 队列的链式存储结构

    1. 队列的链式存储
    typedef struct LinkNode{      //链式队列结点
        ElemType data;
        struct LinkNode *next;
    }
    
    typedef struct{               //链式队列
        LinkNode *front, *rear;   //队列的队头和队尾指针
    }LinkQueue;
    
    1. 链式队列的基本操作——带头结点
    • 初始化 & 判空
    void InitQueue(LinkQueue &Q){
        //初始化时,front、rear都指向头结点
        Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
        Q.front -> next = NULL;
    }
    
    //判断队列是否为空
    bool IsEmpty(LinkQueue Q){
        if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
            return true;
        else
            return false;
    }
    
    • 入队操作
    //新元素入队 (表尾进行)
    void EnQueue(LinkQueue &Q, ElemType x){
        LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
        s->data = x;
        s->next = NULL;     //s作为最后一个结点,指针域指向NULL
        Q.rear->next = s;   //新结点插入到当前的rear之后
        Q.rear = s;         //表尾指针指向新的表尾
    }
    
    • 出队操作
    //队头元素出队
    bool DeQueue(LinkQueue &Q, ElemType &x){
        if(Q.front == Q.rear)
            return false;                    //空队
        
        LinkNode *p = Q.front->next;         //p指针指向即将删除的结点 (头结点所指向的结点)
        x = p->data;
        Q.front->next = p->next;             //修改头结点的next指针
        if(Q.rear == p)                      //此次是最后一个结点出队
            Q.rear = Q.front;                //修改rear指针
        free(p);                             //释放结点空间
    
        return true;
    }
    
    • 队列满的条件

    顺序存储:预分配存储空间

    链式存储:一般不会队满,除非内存不足

    • 计算链队长度 (遍历链队)

    设置一个int length 记录链式队列长度

    1. 链式队列的基本操作——不带头结点
    • 初始化 & 判空
    void InitQueue(LinkQueue &Q){
        //初始化时,front、rear都指向NULL
        Q.front = NULL;
        Q.rear = NULL;
    }
    
    //判断队列是否为空
    bool IsEmpty(LinkQueue Q){
        if(Q.front == NULL)     //也可以用 Q.rear == NULL
            return true;
        else
            return false;
    }
    
    • 入队操作
    //新元素入队 (表尾进行)
    void EnQueue(LinkQueue &Q, ElemType x){
        LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
        s->data = x;
        s->next = NULL;
    
        //第一个元素入队时需要特别处理
        if(Q.front = NULL){            //在空队列中插入第一个元素
            Q.front = s;               //修改队头队尾指针
            Q.rear = s;
        }else{
            Q.rear->next = s;           //新结点插入到rear结点之后
            Q.rear = s;                 //修改rear指针指向新的表尾结点
        }
    }
    

    3.2.4 双端队列

    1. 定义
    • 双端队列允许从两端插入两端删除的线性表;
    • 如果只使用其中一端的插入、删除操作,则等同于栈;
    • 输入受限的双端队列:允许一端插入两端删除的线性表;
    • 输出受限的双端队列:允许两端插入一端删除的线性表;
    1. 考点: 判断输出序列的合法化(视频07)

    : 数据元素输入序列为 1,2,3,4,判断 4!=24 个输出序列的合法性

    PS: 栈中合法的序列,双端队列中一定也合法

    输入受限的双端队列输出受限的双端队列
    14个合法(卡特兰数)验证在栈中不合法的序列验证在栈中不合法的序列
    只有 4213 和 4231 不合法只有 4132 和 4231 不合法

    3.3 栈的应用

    3.3.1 栈在括号匹配中的应用

    用栈实现括号匹配

    • ((())) 最后出现的左括号最先被匹配 (栈的特性—LIFO);
    • 遇到左括号就入栈;
    • 遇到右括号,就“消耗”一个左括号 (出栈);

    匹配失败情况:

    • 扫描到右括号且栈空,则该右括号单身;
    • 扫描完所有括号后,栈非空,则该左括号单身;
    • 左右括号不匹配;

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UBr5m1ue-1622726764306)(括号匹配.png)]

    #define MaxSize 10   
    
    typedef struct{
        char data[MaxSize];
        int top;
    } SqStack;
    
    //初始化栈
    InitStack(SqStack &S)
    
    //判断栈是否为空
    bool StackEmpty(SqStack &S)
    
    //新元素入栈
    bool Push(SqStack &S, char x)
    
    //栈顶元素出栈,用x返回
    bool Pop(SqStack &S, char &x)
    
    
    
    bool bracketCheck(char str[], int length){
        SqStack S;      //声明
        InitStack(S);   //初始化栈
    
        for(int i=0; i<length; i++){
            if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
                Push(S, str[i]);       //扫描到左括号,入栈
            }else{
                if(StackEmpty(S))      //扫描到右括号,且当前栈空
                    return false;      //匹配失败
                
                char topElem;          //存储栈顶元素
                Pop(S, topElem);       //栈顶元素出栈
    
                if(str[i] == ')' && topElem != '(' )
                    return false;
    
                if(str[i] == ']' && topElem != '[' )
                    return false;
    
                if(str[i] == '}' && topElem != '{' )
                    return false;       
            }
        }
    
        StackEmpty(S);                //栈空说明匹配成功
    }
    
    

    3.3.2 栈在表达式求值中的应用

    1. 中缀表达式 (需要界限符)

    运算符在两个操作数中间:

    ① a + b
    ② a + b - c
    ③ a + b - c*d
    ④ ((15 ÷ (7-(1+1)))×3)-(2+(1+1))
    ⑤ A + B × (C - D) - E ÷ F
    

    2. 后缀表达式 (逆波兰表达式)

    运算符在两个操作数后面:

    ① a b +
    ② ab+ c - / a bc- +
    ③ ab+ cd* -
    ④ 15 7 1 1 + - ÷ 3 × 2 1 1 + + -
    ⑤ A B C D - × + E F ÷ - (机算结果)
      A B C D - × E F ÷ - + (不选择)
    
    • 中缀表达式转后缀表达式-手算

    步骤1: 确定中缀表达式中各个运算符的运算顺序

    步骤2: 选择下一个运算符,按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数

    步骤3: 如果还有运算符没被处理,继续步骤2

    “左优先”原则: 只要左边的运算符能先计算,就优先算左边的 (保证运算顺序唯一);

    中缀:A + B - C * D / E + F
           ①   ④   ②   ③   ⑤     
    后缀:A B + C D * E / - F +
    

    重点:中缀表达式转后缀表达式-机算

    初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素,直到末尾。可能遇到三种情况:

    • 遇到操作数: 直接加入后缀表达式。
    • 遇到界限符: 遇到 '(' 直接入栈; 遇到 ')' 则依次弹出栈内运算符并加入后缀表达式,直到弹出 '(' 为止。注意: '(' 不加入后缀表达式。
    • 遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到 '(' 或栈空则停止。之后再把当前运算符入栈。

    按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式。

    • 后缀表达式的计算—手算:

    从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应的运算,合体为一个操作数;

    注意: 两个操作数的左右顺序

    重点:后缀表达式的计算—机算

    用栈实现后缀表达式的计算(栈用来存放当前暂时不能确定运算次序的操作数)

    步骤1: 从左往后扫描下一个元素,直到处理完所有元素;

    步骤2: 若扫描到操作数,则压入栈,并回到步骤1;否则执行步骤3;

    步骤3: 若扫描到运算符,则弹出两个栈顶元素,执行相应的运算,运算结果压回栈顶,回到步骤1;

    注意: 先出栈的是“右操作数”

    3.前缀表达式 (波兰表达式)

    运算符在两个操作数前面:
    ① + a b
    ② - +ab  c
    ③ - +ab *cd
    
    • 中缀表达式转前缀表达式—手算

    步骤1: 确定中缀表达式中各个运算符的运算顺序

    步骤2: 选择下一个运算符,按照[运算符 左操作数 右操作数]的方式组合成一个新的操作数

    步骤3: 如果还有运算符没被处理,就继续执行步骤2

    “右优先”原则: 只要右边的运算符能先计算,就优先算右边的;

    中缀:A + B * (C - D) - E / F
           ⑤   ③    ②    ④   ①
    前缀:+ A - * B - C D / E F
    
    • 前缀表达式的计算—机算

    用栈实现前缀表达式的计算

    步骤1: 从右往左扫描下一个元素,直到处理完所有元素;

    步骤2: 若扫描到操作数则压入栈,并回到步骤1,否则执行步骤3

    步骤3: 若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到步骤1

    注意: 先出栈的是“左操作数”

    4.中缀表达式的计算(用栈实现)

    两个算法的结合: 中缀转后缀 + 后缀表达式的求值

    • 初始化两个栈,操作数栈运算符栈

    • 若扫描到操作数,压人操作数栈

    • 若扫描到运算符或界限符,则按照“中缀转后缀”相同的逻辑压入运算符栈 (期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈项元素并执行相应运算,运算结果再压回操作数栈)

    3.3.3 栈在递归中的应用

    函数调用的特点:最后被调用的函数最先执行结束(LIFO)

    函数调用时,需要用一个栈存储:

    • 调用返回地址
    • 实参
    • 局部变量

    递归调用时,函数调用栈称为 “递归工作栈”:

    • 每进入一层递归,就将递归调用所需信息压入栈顶;
    • 每退出一层递归,就从栈顶弹出相应信息;

    缺点:太多层递归可能回导致栈溢出;

    适合用“递归”算法解决:可以把原始问题转换为属性相同,但规模较小的问题;

    3.3 队列的应用

    3.3.1 树的层次遍历

    (详见“树”章节)

    3.3.2 图的广度优先遍历

    (详见“图”章节)

    3.3.3 队列在操作系统中的应用

    多个进程争抢着使用优先的系统资源时,FCFS(先来先服务)是一种常用策略

    Eg: CPU资源分配、打印数据缓冲区

    3.4 特殊矩阵的压缩存储

    3.4.1 数组的存储结构

    1. 一维数组
    Elemtype a[10];
    

    各数组元素大小相同,物理上连续存放;

    起始地址:LOC

    数组下标:默认从0开始!

    数组元素 a[i] 的存放地址 = LOC + i × sizeof(ElemType)

    1. 二维数组
    Elemtype b[2][4]; //2行4列的二维数组
    

    行优先/列优先存储优点:实现随机存储

    起始地址:LOC

    M行N列的二维数组 b[M][N] 中,b[i][j]的存储地址:

    • 行优先存储: LOC + (i×N + j) × sizeof(ElemType)
    • 列优先存储:LOC + (j×M + i) × sizeof(ElemType)

    3.4.2 普通矩阵的存储

    二维数组存储

    • 描述矩阵元素时,行、列号通常从1开始;
    • 描述数组时,通常下标从 0 开始;

    3.4.3 特殊矩阵的存储

    特殊矩阵——压缩存储空间

    1. 对称矩阵(方阵)

    2. 三角矩阵(方阵)

    3. 三对角矩阵(方阵)

    4. 稀疏矩阵

    • 顺序存储——三元组

    • 链式存储——十字链表法

    第四章 串

    4.1 串的定义和实现

    4.1.1 串的定义

    1. 串: 零个或多个字符组成的有限序列,如 S = 'iPhone 11 Pro Max?'
    2. 串名:S是串名;
    3. 串的长度:串中字符的个数n;
    4. 空串:n=0时的串;
    5. 子串:串中任意多个连续的字符组成的子序列称为该串的子串;
    6. 主串:包含子串的串;
    7. 字符在主串中的位置:某个字符在串中的序号(从1开始);
    8. 子串在主串中的位置:子串的第一个字符在主串中的位置;
    9. 空串 V.S 空格串:
      • M = '' 是空串;
      • N = ' ' 是空格串;
    10. 串 V.S 线性表:
      • 串是特殊的线性表,数据元素之间呈线性关系(逻辑结构相似);
      • 串的数据对象限定为字符集:中文字符、英文字符、数字字符、标点字符…
      • 串的基本操作,如增删改除通常以子串为操作对象

    4.1.2 串的基本操作

    假设有串 T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'

    • StrAssign(&T, chars): 赋值操作,把串T赋值为chars;
    • StrCopy(&T, S): 复制操作,把串S复制得到串T;
    • StrEmpty(S): 判空操作,若S为空串,则返回TRUE,否则返回False;
    • StrLength(S): 求串长,返回串S的元素个数;

      返回length

    • ClearString(&S): 清空操作,将S清为空串

      length = 0,逻辑上清空,但是内存中还有

    • DestroyString(&S): 销毁串,将串S销毁——回收存储空间
    • Concat(&T, S1, S2): 串联联接,用T返回由S1和S2联接而成的新串———可能会导致存储空间的扩展;

      Concat(&T, S, W)

      T = ‘iPhone 11 Pro Max?Pro’

    • SubString(&Sub, S, pos, len): 求子串,用Sub返回串S的第pos个字符起长度为len的子串;

      SubString(&T, S, 4, 6)

      T = ‘one 11’

    • Index(S, T): 定位操作,若主串S中存在与串T值相同的子串,则返回它再主串S中第一次出现的位置,否则函数值为0;

      Index(S, T)

      11

    • StrCompare(S, T): 串的比较操作,参照英文词典排序方式;若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;

    拓展:字符集编码

    1. 字符集:
    2. 编码方案
    3. 乱码问题

    4.1.3 串的存储结构

    1. 定长顺序存储表示
    #define MAXLEN 255   //预定义最大串长为255
    
    typedef struct{
        char ch[MAXLEN];   //静态数组实现(定长顺序存储)
                           //每个分量存储一个字符
                           //每个char字符占1B
        int length;        //串的实际长度
    }SString;
    
    • 串长的两种表示法:

      • 方案一:用一个额外的变量length来存放串的长度(保留ch[0]);
      • 方案二:用ch[0]充当length
        • 优点:字符的位序和数组下标相同;
      • 方案三:没有length变量,以字符'\0'表示结尾(对应ASCII码的0);
        • 缺点:需要从头到尾遍历;
      • 方案四——最终使用方案:ch[0]废弃不用,声明int型变量length来存放串的长度(方案一与方案二的结合)
    • 基本操作实现(基于方案四)

    #define MAXLEN 255
    
    typedef struct{
        char ch[MAXLEN];   
        int length;       
    }SString;
    
    // 1. 求子串
    bool SubString(SString &Sub, SString S, int pos, int len){
        //子串范围越界
        if (pos+len-1 > S.length)
            return false;
        
        for (int i=pos; i<pos+len; i++)
            Sub.cn[i-pos+1] = S.ch[i];
        
        Sub.length = len;
    
        return true;
    }
    
    // 2. 比较两个串的大小
    int StrCompare(SString S, SString T){
        for (int i; i<S.length && i<T.length; i++){
            if(S.ch[i] != T.ch[i])
                return S.ch[i] - T.ch[i];
        }
        //扫描过的所有字符都相同,则长度长的串更大
        return S.length - T.length;
    }
    
    // 3. 定位操作
    int Index(SString S, SString T){
        int i=1;
        n = StrLength(S);
        m = StrLength(T);
        SString sub;        //用于暂存子串
    
        while(i<=n-m+1){
            SubString(Sub,S,i,m);
            if(StrCompare(Sub,T)!=0)
                ++i;
            else 
                return i;    // 返回子串在主串中的位置
        }
        return 0;            //S中不存在与T相等的子串
    }
    

    ps:结合顺序表思考优缺点

    1. 堆分配存储表示
    //动态数组实现
    typedef struct{
        char *ch;           //按串长分配存储区,ch指向串的基地址
        int length;         //串的长度
    }HString;
    
    HString S;
    S.ch = (char *) malloc(MAXLINE * sizeof(char)); //基地址指针指向连续空间的起始位置
                                                    //malloc()需要手动free()
    S.length;
    
    1. 串的链式存储
    typedef struct StringNode{
        char ch;           //每个结点存1个字符
        struct StringNode *next;
    }StringNode, * String;
    

    问题:存储密度低,每个字符1B,每个指针4B;
    解决方案:每一个链表的结点存储多个字符——每个结点称为块——块链结构

    typedef struct StringNode{
        char ch[4];           //每个结点存多个个字符
        struct StringNode *next;
    }StringNode, * String;
    

    ps:结合链表思考优缺点

    • 存储分配角度:链式存储的字符串无需占用连续空间,存储空间分配更灵活;
    • 操作角度:若要在字符串中插入或删除某些字符,则顺序存储方式需要移动大量字符,而链式存储不用;
    • 若要按位序查找字符,则顺序存储支持随机访问,而链式存储只支持顺序访问;

    4.2 串的模式匹配

    4.2.1 朴素模式匹配算法

    int Index(SString S, SString T){
        int i=1;                //扫描主串S
        int j=1;                //扫描模式串T
        while(i<=S.length && j<=T.length){
            if(S.ch[i] == T.ch[j]){
                ++i;
                ++j;             //继续比较后继字符
            }
            else{
                i = i-j+2;
                j=1;             //指针后退重新开始匹配
            }
        }
        if(j>T.length)
            return i-T.length;
        else
            return 0;
    }
    

    时间复杂度分析:

    • 主串长度为n,模式串长度为m
    • 最多比较n-m+1个子串
    • 最坏时间复杂度 = O(nm)
      • 每个子串都要对比m个字符(对比到最后一个字符才匹配不上),共要对比n-m+1个子串,复杂度 = O((n-m+1)m) = O(nm - m^2 + m) = O(nm)
      • PS:大多数时候,n>>m
    • 最好时间复杂度 = O(n)
      • 每个子串的第一个字符就匹配失败,共要对比n-m+1个子串,复杂度 = O(n-m+1) = O(n)

    4.2.2 改进的模式匹配算法——KMP算法

    • 不匹配的字符之前,一定是和模式串一致的;
    • 根据模式串T,求出next数组(只与模式串有关,与主串无关),利用next数组进行匹配,当匹配失败时,主串的指针 i 不再回溯!

      当第一个元素匹配失败时,匹配下一个相邻子串,令j=0,i++,j++

    1. next数组(会手算即可)
    • 作用:当模式串的第j个字符失配时,从模式串的第next[j]继续往后匹配;
    • 对于任何模式串,当第1个字符不匹配时,只能匹配下一个子串,因此,next[1] = 0——表示模式串应右移一位,主串当前指针后移一位,再和模式串的第一字符进行比较;
    • 对于任何模式串,当第2个字符不匹配时,应尝试匹配模式串的第一个字符,因此,next[2] = 0;

    例:对于串 T = 'abaabc'

    next[0]next[1]next[2]next[3]next[4]next[5]next[6]
    011223
    1. 利用next数组进行模式匹配
    int Index_KMP(SString S, SString T, int next[]){
        int i=1;     //主串
        int j=1;     //模式串
        while(i<S.length && j<=T.length){
            if(j==0 || S.ch[i]==T.ch[j]){      //第一个元素匹配失败时
                ++j;
                ++i;         //继续比较后继字符
            }
            else
                j=next[j]   //模式串向右移动
        }
        if(j>T.length)
            return i-T.length; //匹配成功
    }
    

    3. 时间复杂度分析:

    • 求next数组时间复杂度 = O(m)
    • 模式匹配过程最坏时间复杂度 = O(n)
    • KMP算法的最坏时间复杂度 = O(m+n)

    4.2.3 KMP算法的进一步优化

    第五章 树与二叉树

    5.1 树的基本概念

    5.1.1 树的定义

    • 空树
    • 根结点、分支结点、叶子结点
    • 非空树的特性
    • 子树

    5.1.2 基本术语

    1. 结点之间的关系描述
      • 祖先、子孙、双亲、兄弟…结点
      • 路径、路径长度
    2. 结点、树的属性描述
      • 结点的层次(深度)——从上往下
      • 结点的高度——从下往上
      • 树的高度——总共多少层
      • 结点的度——有几个孩子
      • 树的度——各结点的度的最大值
    3. 有序树、无序树
    4. 森林

    5.1.3 树的性质

    1. 结点数 = 总度数 + 1
    2. 度为m的数、m叉数的区别
    度为 m 的树m 叉树
    树的度:m为各结点的度的最大值m叉树:每个结点最多只能有 m 个孩子的树
    任意结点的度 ≦ m任意结点的度 ≦ m
    至少有一个结点度 = m允许所有结点的度 < m
    一定是非空树,至少有m+1个结点可以是空树
    第i层至多有 m^(i-1)个结点第i层至多有 m^(i-1)个结点
    高度为h、度为 m 的树至少有h+m-1个结点高度为hm叉树至多有(m^h-1)/(m-1)个结点;至少有h个结点
    具有n个结点的m叉树,最小高度为⌈ logm(n(m-2)+1)⌉

    5.2 二叉树的概念

    5.2.1 二叉树的定义与特性

    1. 二叉树有左右之分,次序不能颠倒

    5.2.2几种特殊的二叉树

    1. 满二叉树
    2. 完全二叉树
    3. 二叉排序树
    4. 平衡二叉树

    5.2.3 二叉树的存储结构

    1. 顺序存储

    二叉树的顺序存储中,一定要把二叉树的结点编号与完全二叉树对应起来;

    #define MaxSize 100
    
    struct TreeNode{
       ElemType value; //结点中的数据元素
       bool isEmpty;   //结点是否为空
    }
    
    main(){
       TreeNode t[MaxSize];
       for (int i=0; i<MaxSize; i++){
          t[i].isEmpty = true;
       }
    }
    

    考点:

    • i的左孩子:2i
    • i的右孩子:2i + 1
    • i的父节点:⌊i/2⌋
    • i所在的层次:⌊log2n + 1⌋ or ⌈ log2n+1)⌉

    若完全二叉树中共有n个结点(非完全二叉树不能用)

    • 判断i是否有左孩子:2i ≦ n
    • 判断i是否有右孩子:2i+1 ≦ n
    • 判断i是否时叶子/分支结点:i > ⌊n/2⌋

    最坏情况: 高度为h且只有h个结点的单支树(所有结点只有右孩子),也至少需要2^h-1个存储单元;

    结论: 二叉树的顺序存储结构,只适合存储完全二叉树和满二叉树

    1. 链式存储
    //二叉树的结点
    
    struct ElemType{
       int value;
    };
    
    typedef struct BiTnode{
       ElemType data;          //数据域
       struct BiTNode *lchild, *rchild; //左、右孩子指针
    }BiTNode, *BiTree;
    
    //定义一棵空树
    BiTree root = NULL;
    
    //插入根节点
    root = (BiTree) malloc (sizeof(BiTNode));
    root -> data = {1};
    root -> lchild = NULL;
    root -> rchild = NULL;
    
    //插入新结点
    BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
    p -> data = {2};
    p -> lchild = NULL;
    p -> rchild = NULL;
    root -> lchild = p; //作为根节点的左孩子
    
    • 找到指定结点p的左/右孩子;
    • 找到指定节点p的父结点: 只能从根结点开始遍历,也可以使用三叉链表
    typedef struct BiTnode{
       ElemType data;          //数据域
       struct BiTNode *lchild, *rchild; //左、右孩子指针
       struct BiTNode *parent;          //父节点指针
    }BiTNode, *BiTree;
    
    • n个结点的二叉链表共有n+1个空链域

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

    5.3.1 二叉树的遍历

    1. 先序遍历(根左右)
    • 若二叉树为空,不用操作
    • 若二叉树非空:
      • 访问根节点
      • 先序遍历左子树
      • 先序遍历右子树
    typedef struct BiTnode{
       ElemType data;          
       struct BiTNode *lchild, *rchild; 
    }BiTNode, *BiTree;
    
    void PreOrder(BiTree T){
       if(T!=NULL){
          visit(T);                 //访问根结点
          PreOrder(T->lchild);      //递归遍历左子树
          PreOrder(T->rchild);      //递归遍历右子树
       }
    }
    

    空间复杂度: O(h)

    1. 中序遍历(左根右)
    • 若二叉树为空,不用操作
    • 若二叉树非空:
      • 先序遍历左子树
      • 访问根节点
      • 先序遍历右子树
    typedef struct BiTnode{
       ElemType data;          
       struct BiTNode *lchild, *rchild; 
    }BiTNode, *BiTree;
    
    void InOrder(BiTree T){
       if(T!=NULL){
          InOrder(T->lchild);       //递归遍历左子树
          visit(T);                 //访问根结点
          InOrder(T->rchild);       //递归遍历右子树
       }
    }
    
    1. 后续遍历(左右根)
    • 若二叉树为空,不用操作
    • 若二叉树非空:
      • 先序遍历左子树
      • 先序遍历右子树
      • 访问根节点
    typedef struct BiTnode{
       ElemType data;          
       struct BiTNode *lchild, *rchild; 
    }BiTNode, *BiTree;
    
    void PostOrder(BiTree T){
       if(T!=NULL){
          PostOrder(T->lchild);       //递归遍历左子树    
          PostOrder(T->rchild);       //递归遍历右子树
          visit(T);                 //访问根结点
       }
    }
    
    1. 二叉树的层次遍历

    算法思想:

    • 初始化一个辅助队列
    • 根节点入队
    • 若队列非空,则队头结点出队,访问该结点,依次将其左、右孩子插入队尾(如果有的话)
    • 重复以上操作直至队列为空
    //二叉树的结点(链式存储)
    typedef struct BiTnode{
       ElemType data;          
       struct BiTNode *lchild, *rchild; 
    }BiTNode, *BiTree;
    
    //链式队列结点
    typedef struct LinkNode{
       BiTNode * data;
       typedef LinkNode *next;
    }LinkNode;
    
    typedef struct{
       LinkNode *front, *rear;  
    }LinkQueue;
    
    //层序遍历
    void LevelOrder(BiTree T){
       LinkQueue Q;
       InitQueue (Q);          //初始化辅助队列
       BiTree p;
       EnQueue(Q,T);           //将根节点入队
       while(!isEmpty(Q)){     //队列不空则循环
          DeQueue(Q,p);        //队头结点出队
          visit(p);            //访问出队结点
          if(p->lchild != NULL)
             EnQueue(Q,p->lchild);   //左孩子入队
          if(p->rchild != NULL)
             EnQueue(Q,p->rchild);   //右孩子入队
       }
    }
    
    1. 由遍历序列构造二叉树
    • 先序序列 + 中序序列
    • 后序序列 + 中序序列
    • 层序序列 + 中序序列

    key: 找到树的根节点,并根据中序序列划分左右子树,再找到左右子树根节点、

    5.3.2 线索二叉树

    1. 线索二叉树的概念与作用

    2. 线索二叉树的存储结构

    • 中序线索二叉树——线索指向中序前驱、中序后继
    //线索二叉树结点
    typedef struct ThreadNode{
       ElemType data;
       struct ThreadNode *lchild, *rchild;
       int ltag, rtag;                // 左、右线索标志
    }ThreadNode, *ThreadTree;
    

    tag == 0: 指针指向孩子

    tag == 1: 指针是“线索”

    • 先序线索二叉树——线索指向先序前驱、先序后继

    • 后序线索二叉树——线索指向后序前驱、后序后继

    1. 二叉树的线索化
    • 中序线索化
    typedef struct ThreadNode{
       int data;
       struct ThreadNode *lchild, *rchild;
       int ltag, rtag;                // 左、右线索标志
    }ThreadNode, *ThreadTree;
    
    //全局变量pre, 指向当前访问的结点的前驱
    TreadNode *pre=NULL;
    
    void InThread(ThreadTree T){
        if(T!=NULL){
            InThread(T->lchild);    //中序遍历左子树
            visit(T);               //访问根节点
            InThread(T->rchild);    //中序遍历右子树
        }
    }
    
    void visit(ThreadNode *q){
       if(q->lchid = NULL){                 //左子树为空,建立前驱线索   
          q->lchild = pre;
          q->ltag = 1;
       }
    
       if(pre!=NULL && pre->rchild = NULL){ 
          pre->rchild = q;           //建立前驱结点的后继线索
          pre->rtag = 1;
       }
       pre = q;
    }
    
    //中序线索化二叉树T
    void CreateInThread(ThreadTree T){
       pre = NULL;                //pre初始为NULL
       if(T!=NULL);{              //非空二叉树才能进行线索化
          InThread(T);            //中序线索化二叉树
          if(pre->rchild == NULL)
             pre->rtag=1;         //处理遍历的最后一个结点
       }
    }
    
    • 先序线索化

    注意【转圈】问题,当ltag==0时,才能对左子树先序线索化

    typedef struct ThreadNode{
       int data;
       struct ThreadNode *lchild, *rchild;
       int ltag, rtag;                // 左、右线索标志
    }ThreadNode, *ThreadTree;
    
    //全局变量pre, 指向当前访问的结点的前驱
    TreadNode *pre=NULL;
    
    //先序遍历二叉树,一边遍历一边线索化
    void PreThread(ThreadTree T){
       if(T!=NULL){
          visit(T);
          if(T->ltag == 0)         //lchild不是前驱线索
             PreThread(T->lchild);
          PreThread(T->rchild);
       }
    }
    
    void visit(ThreadNode *q){
       if(q->lchid = NULL){                 //左子树为空,建立前驱线索   
          q->lchild = pre;
          q->ltag = 1;
       }
    
       if(pre!=NULL && pre->rchild = NULL){ 
          pre->rchild = q;           //建立前驱结点的后继线索
          pre->rtag = 1;
       }
       pre = q;
    }
    
    //先序线索化二叉树T
    void CreateInThread(ThreadTree T){
       pre = NULL;                //pre初始为NULL
       if(T!=NULL);{              //非空二叉树才能进行线索化
          PreThread(T);            //先序线索化二叉树
          if(pre->rchild == NULL)
             pre->rtag=1;         //处理遍历的最后一个结点
       }
    }
    
    • 后序线索化
    typedef struct ThreadNode{
       int data;
       struct ThreadNode *lchild, *rchild;
       int ltag, rtag;                // 左、右线索标志
    }ThreadNode, *ThreadTree;
    
    //全局变量pre, 指向当前访问的结点的前驱
    TreadNode *pre=NULL;
    
    //先序遍历二叉树,一边遍历一边线索化
    void PostThread(ThreadTree T){
       if(T!=NULL){
          PostThread(T->lchild);
          PostThread(T->rchild);
          visit(T);                  //访问根节点
       }
    }
    
    void visit(ThreadNode *q){
       if(q->lchid = NULL){                 //左子树为空,建立前驱线索   
          q->lchild = pre;
          q->ltag = 1;
       }
    
       if(pre!=NULL && pre->rchild = NULL){ 
          pre->rchild = q;           //建立前驱结点的后继线索
          pre->rtag = 1;
       }
       pre = q;
    }
    
    //先序线索化二叉树T
    void CreateInThread(ThreadTree T){
       pre = NULL;                //pre初始为NULL
       if(T!=NULL);{              //非空二叉树才能进行线索化
          PostThread(T);            //后序线索化二叉树
          if(pre->rchild == NULL)
             pre->rtag=1;         //处理遍历的最后一个结点
       }
    }
    
    1. 线索二叉树中找前驱、后继
    • 中序线索二叉树找中序后继:在中序线索二叉树中找到指定节点 *p 的中序后继 next

      p->rtag == 1, 则 next = p->rchild;

      p->rtag == 0, 则 p 必有右孩子, 则 next = p的右子树中最左下结点;

    //1. 找到以P为根的子树中,第一个被中序遍历的结点
    ThreadNode *Firstnode(ThreadNode *p){
       //循环找到最左下的结点(不一定是叶结点)
       while(p->ltag == 0)
          p=p->lchild;
       return p;
    }
    
    //2. 在中序线索二叉树中找到结点p的后继结点
    ThreadNode *Nextnode(ThreadNode *p){
       //右子树最左下结点
       if(p->rtag==0)
          return Firstnode(p->rchild);
       else 
          return p->rchild; //rtag==1,直接返回后继线索
    }
    
    //3. 对中序线索二叉树进行中序遍历
    void Inorder(ThreadNode *T){            //T为根节点指针
       for(ThreadNode *p = Firstnode(T); p!=NULL; p = Nextnode(p))
          visit(p);
    }
    

    时间复杂度 = O(1)

    • 中序线索二叉树找中序前驱:在中序线索二叉树中找到指定节点 *p 的中序前驱 pre

      p->ltag == 1, 则 next = p->lchild;

      p->ltag == 0, 则 p 必有左孩子, 则 next = p的左子树中最右下结点;

    //1. 找到以P为根的子树中,第一个被中序遍历的结点
    ThreadNode *Lastnode(ThreadNode *p){
       //循环找到最右下的结点(不一定是叶结点)
       while(p->rtag == 0)
          p=p->rchild;
       return p;
    }
    
    //2. 在中序线索二叉树中找到结点p的前驱结点
    ThreadNode *Prenode(ThreadNode *p){
       //左子树最右下结点
       if(p->ltag==0)
          return Lastnode(p->lchild);
       else 
          return p->lchild; //rtag==1,直接返回前驱线索
    }
    
    //3. 对中序线索二叉树进行逆向中序遍历
    void RevInorder(ThreadNode *T){            //T为根节点指针
       for(ThreadNode *p = Lastnode(T); p!=NULL; p = Prenode(p))
          visit(p);
    }
    
    • 先序线索二叉树找先序后继:在先序线索二叉树中找到指定节点 *p 的先序后继 next

      p->rtag == 1, 则 next = p->rchild;

      p->rtag == 0, 则 p 必有右孩子(左孩子不知道)

      case1: 若p有左孩子 ——— 根 右 / 根 ( 左 右) 右

      case2: 若p没有左孩子 ——— 根 / 根 (* *左 右)

    • 先序线索二叉树找先序前驱:在先序线索二叉树中找到指定节点 *p 的先序前驱pre

      p->ltag == 1, 则 next = p->lchild;

      p->ltag == 0, 则 p 必有左孩子,但是先序遍历中,左右子树的结点只可能是根的后继,不可能是前驱,所以不能从左右孩子里寻找p的先序前驱,(除非从头开始遍历/三叉链表

      case1: 如果能够找到p的父节点,且p是左孩子 —— p的父节点就是p的前驱;

      case2: 如果能够找到p的父节点,且p是右孩子,且其左兄弟为空 —— p的父节点就是p的前驱;

      case3: 如果能够找到p的父节点,且p是右孩子,且其左兄弟非空 —— p的前驱为左兄弟子树中最后一个被先序遍历到的结点(根节点出发,先往右,右没有往左,找到最下一层的结点);

      case4: p没有父节点,即p为根节点,则p没有先序前驱

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YjVVJjtQ-1623943811481)(先序线索二叉树找先序前驱.PNG)]

    • 后序线索二叉树找后序前驱:在后序线索二叉树中找到指定节点 *p 的后序前驱pre

      p->ltag == 1, 则 next = p->lchild;

      p->ltag == 0, 则 p 必有左孩子(不知道有没有右孩子)

      case1: 若p有右孩子 ——— 左 根 / 左 (左 右 ) 根

      case2: 若p没有右孩子 ——— 根 (左子树按后序遍历,最后一个结点,p的左孩子)

    • 后序线索二叉树找后序后继:在后序线索二叉树中找到指定节点 *p 的后序后继next

      p->rtag == 1, 则 next = p->rchild;

      p->rtag == 0, 则 p 必有右孩子, 左孩子不知道, 但是在后序遍历中,左右子树中的结点只有可能是根的前驱,而不可能是根的后继,所以找不到后继,(除非从头开始遍历/三叉链表

      case1: 如果能找到p的父节点,且p是右孩子 —— p的父节点即为其后继

      case2: 如果能找到p的父节点,且p是左孩子,其右兄弟为空 —— p的父节点即为其后继

      case3: 如果能找到p的父节点,且p是左孩子,其右兄弟非空 —— p的后继为其右兄弟子树中第一个被后序遍历的结点;

      case4: p没有父节点,即p为根节点,则p没有后序后继;

    总结

    中序线索二叉树先序线索二叉树后续线索二叉树
    找前驱TFT
    找后继TTF

    5.4 树、森林

    5.4.1 树的存储结构

    1. 双亲表示法(顺序存储):每个结点中保存指向双亲的指针
    #define MAX_TREE_SIZE 100  //树中最多结点数
    
    typedef struct{      //树的结点定义
       ElemType data; 
       int parent;      //双亲位置域
    }PTNode;
    
    typedef struct{                   //树的类型定义
       PTNode nodes[MAX_TREE_SIZE];   //双亲表示
       int n;                         //结点数
    }PTree;
    
    • 增:新增数据元素,无需按逻辑上的次序存储;(需要更改结点数n
    • 删(叶子结点):① 将伪指针域设置为-1;②用后面的数据填补;(需要更改结点数n
    • 查询:①优点-查指定结点的双亲很方便;②缺点-查指定结点的孩子只能从头遍历,空数据导致遍历更慢;
    1. 孩子表示法(顺序+链式)
    struct CTNode{
       int child;    //孩子结点在数组中的位置
       struct CTNode *next;    // 下一个孩子
    };
    
    typedef struct{
       ElemType data;
       struct CTNode *firstChild;    // 第一个孩子
    }CTBox;
    
    typedef struct{
       CTBox nodes[MAX_TREE_SIZE];
       int n, r;   // 结点数和根的位置
    }CTree;
    
    1. 孩子兄弟表示法(链式)
    typedef struct CSNode{
       ElemType data;                               //数据域
       struct CSNode *firstchild, *nextsibling;     //第一个孩子和右兄弟指针, *firstchild 看作左指针,*nextsibling看作右指针
    }CSNode. *CSTree;
    

    5.4.2 树、森林与二叉树的转换

    本质:森林中各个树的根节点之间视为兄弟关系

    5.4.3 树、森林的遍历

    1. 树的遍历
    • 先根遍历:若树非空,先访问根节点,再依次对每棵子树进行先根遍历;(与对应二叉树的先序遍历序列相同)
    void PreOrder(TreeNode *R){
       if(R!=NULL){
          visit(R);    //访问根节点
          while(R还有下一个子树T)
             PreOrder(T);      //先跟遍历下一个子树
       }
    }
    
    • 后根遍历:若树非空,先依次对每棵子树进行后根遍历,最后再返回根节点;(与对应二叉树的中序遍历序列相同)
    void PostOrder(TreeNode *R){
       if(R!=NULL){
          while(R还有下一个子树T)
             PostOrder(T);      //后跟遍历下一个子树
          visit(R);    //访问根节点
       }
    }
    
    • 层序遍历(队列实现):
      • 若树非空,则根结点入队;
      • 若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队;
      • 重复以上操作直至队尾为空;
    1. 森林的遍历
    • 先序遍历:等同于依次对各个树进行先根遍历;也可以先转换成与之对应的二叉树,对二叉树进行先序遍历
    • 中序遍历:等同于依次对各个树进行后根遍历;也可以先转换成与之对应的二叉树,对二叉树进行中序遍历

    5.5 树与二叉树的应用

    5.5.1 二叉排序树(BST)

    1. 二叉排序树的定义

    左子树结点值<跟结点值<右子树结点值

    1. 查找操作
    typedef struct BSTNode{
       int key;
       struct BSTNode *lchild, *rchild;
    }BSTNode, *BSTree;
    
    //在二叉排序树中查找值为key的结点(非递归)
    //最坏空间复杂度:O(1)
    BSTNode *BST_Search(BSTree T, int key){
       while(T!=NULL && key!=T->key){        //若树空或等于跟结点值,则结束循环
          if(key<T->key)       //值小于根结点值,在左子树上查找
             T = T->lchild;
          else                  //值大于根结点值,在右子树上查找
             T = T->rchild;
       }
       return T;
    }
    
    //在二叉排序树中查找值为key的结点(递归)
    //最坏空间复杂度:O(h)
    BSTNode *BSTSearch(BSTree T, int key){
       if(T == NULL)
          return NULL;
       if(Kry == T->key)
          return T;
       else if(key < T->key)
          return BSTSearch(T->lchild, key);
       else 
          return BSTSearch(T->rchild, key);
    }
    
    1. 插入操作
    //在二叉排序树中插入关键字为k的新结点(递归)
    //最坏空间复杂度:O(h)
    int BST_Insert(BSTree &T, int k){
       if(T==NULL){           //原树为空,新插入的结点为根结点
          T = (BSTree)malloc(sizeof(BSTNode));
          T->key = k;
          T->lchild = T->rchild = NULL;
          return 1;                       //插入成功
       }
       else if(K == T->key)               //树中存在相同关键字的结点,插入失败
          return 0;
       else if(k < T->key)                 
          return BST_Insert(T->lchild,k);
       else 
          return BST_Insert(T->rchild,k);
    }
    
    1. 二叉排序树的构造
    //按照str[]中的关键字序列建立二叉排序树
    void Crear_BST(BSTree &T, int str[], int n){
       T = NULL;                     //初始时T为空树
       int i=0;
       while(i<n){
          BST_Insert(T,str[i]);     //依次将每个关键字插入到二叉排序树中
          i++;
       }
    }
    
    1. 删除操作
    2. 查找效率分析
    • 查找长度:查找运算中,需要对比关键字的次数,反映了查找操作时间复杂度;
    • 查找成功的平均查找长度ASL
    • 查找失败的平均查找长度ASL

    5.5.2 平衡二叉树(AVL)

    1. 平衡二叉树的定义
    //平衡二叉树结点
    typedef struct AVLNode{
       int key;         //数据域
       int balance;     //平衡因子
       struct AVLNode *lchild; *rchild; 
    }AVLNode, *AVLTree;
    
    
    1. 平衡二叉树的插入
    2. 插入新节点后如何调整“不平衡”问题

    调整最小不平衡子树

    • LL: 在A结点的左孩子的左子树中插入导致不平衡
      • 调整: A的左孩子结点右上旋
    • RR: 在A结点的右孩子的右子树中插入导致不平衡
      • 调整: A的右孩子结点左上旋
    • LR: 在A结点的左孩子的右子树中插入导致不平衡
      • 调整: A的左孩子的右孩子,先左上旋再右上旋
    • RL: 在A结点的右孩子的左子树中插入导致不平衡
      • 调整: A的右孩子的左孩子,先右上旋再左上旋
    1. 平衡二叉树的查找与效率分析

    若树高为h,则最坏情况下,查找一个关键字最多需要对比h次,即查找操作的时间复杂度不可能超过O(h);

    5.5.3 哈夫曼树

    1. 带权路径长度
    2. 哈夫曼树的定义
    3. 哈夫曼树的构造(重点)
    4. 哈杜曼编码(重点)

    第六章 图

    第七章 查找

    第八章 排序

    8.1 排序的基本概念

    1. 排序:重新排列表中的元素,使表中元素满足按关键字有序的过程(关键字可以相同)
    2. 排序算法的评价指标:时间复杂度、空间复杂度;
    3. 排序算法的稳定性:关键字相同的元素在排序之后相对位置不变,称为稳定的;(选择题考查)
      Q: 稳定的排序算法一定比不稳定的好?
      A: 不一定,要看实际需求;
    4. 排序算法的分类:
      内部排序: 数据都在内存——关注如何使时间、空间复杂度更低;
      外部排序: 数据太多,无法全部放入内存——关注如何使时间、空间复杂度更低,如何使读/写磁盘次数更少;

    美国旧金山大学-可视化学习网站

    8.2 插入排序

    8.2.1 直接插入排序

    1. 算法思想: 每次将一个待排序的记录按其关键字大小,插入(依次对比、移动)到前面已经排好序的子序列中,直到全部记录插入完成
    2. 代码实现:
    • 不带“哨兵”
    void InsertSort(int A[], int n){    //A中共n个数据元素
        int i,j,temp;
        for(i=1; i<n; i++)
            if(A[i]<A[i-1]){    //A[i]关键字小于前驱
                temp = A[i];  
                for(j=i-1; j>=0 && A[j]>temp; --j)
                    A[j-1] = A[j];     //所有大于temp的元素都向后挪
                A[j+1] = temp;         //复制到插入位置
            }
    }
    
    • 带“哨兵” ,优点:不用每轮循环都判断j>=0
    void InsertSort(int A[], int n){    //A中从1开始存储,0放哨兵
        int i,j;
        for(i=1; i<n; i++)
            if(A[i]<A[i-1]){    
                A[0] = A[i];     //复制为哨兵
                for(j=i-1; A[0] < A[j]; --j)  //从后往前查找待插入位置
                    A[j+1] = A[j];     //向后挪动
                A[j+1] = A[0];          //复制到插入位置
            }
    }
    
    1. 算法效率分析
    • 空间复杂度:O(1)
    • 时间复杂度:主要来自于对比关键字、移动关键字,若有n个元素,则需要n-1躺处理
      • 最好情况: 原本为有序,共n-1趟处理,每一趟都只需要对比1次关键字,不需要移动元素,共对比n-1次 —— O(n)
      • 最差情况: 原本为逆序 —— O(n²)
      • 平均情况: O(n²)
    • 算法稳定性:稳定
    1. 对链表进行插入排序
    • 移动元素的次数变少了,因为只需要修改指针,不需要依次右移;
    • 但是关键字对比的次数依然是O(n²)数量级,因此整体看来时间复杂度仍然是O(n²)

    8.2.2 折半插入排序

    1. 思路: 先用折半查找找到应该插入的位置,再移动元素;

    2. 为了保证稳定性,当查找到和插入元素关键字一样的元素时,应该继续在这个元素的右半部分继续查找以确认位置; 即当 A[mid] == A[0] 时,应继续在mid所指位置右边寻找插入位置

    3. low>high时,折半查找停止,应将[low,i-1]or[high+1,i-1]内的元素全部右移,并将A[0]复制到low所指的位置;

    4. 代码实现

    void InsertSort(int A[], int n){ 
        int i,j,low,high,mid;
        for(i=2;i<=n;i++){
            A[0] = A[i];                    //将A[i]暂存到A[0]
            low = 1; high = i-1;            //折半查找的范围
    
            while(low<=high){               //折半查找
                mid = (low + high)/2;       //取中间点
                if(A[mid]>A[0])             //查找左半子表
                    high = mid - 1;
                else                        //查找右半子表
                    low = mid + 1;
            }
            
            for(j=i-1; j>high+1;--j)       //统一后移元素,空出插入位置
                A[j+1] = A[j];
            A[high+1] = A[0]
        }
    }
    
    1. 直接插入排序相比,比较关键字的次数减少了,但是移动元素的次数没有变,时间复杂度仍然是O(n²)

    8.2.3 希尔排序

    1. 思路: 先追求表中元素的部分有序,再逐渐逼近全局有序;

    2. 更适用于基本有序的排序表和数据量不大的排序表,仅适用于线性表为顺序存储的情况

    3. 代码实现:

    void ShellSort(ElemType A[], int n){
        //A[0]为暂存单元
        for(dk=n/2; dk>=1; dk=dk/2)   //步长递减(看题目要求,一般是1/2
            for(i=dk+1; i<=n; ++i)
                if(A[i]<A[i-dk]){
                    A[0]=A[i];
                    for(j=i-dk; j>0&&A[0]<A[j];j-=dk)
                        A[j+dk]=A[j];         //记录后移,查找插入的位置
                    A[j+dk]=A[0;]             //插入
                }
    }
    
    1. 算法效率分析
    • 空间效率:空间复杂度=O(1)
    • 时间效率: 最坏情况下时间复杂度=O(n²)
    • 稳定性:希尔排序是一种不稳定的排序方法

    8.3 交换排序

    **基于“交换”的排序:**根据序列中两个元素关键字的比较结果来对换这两个记录再序列中的位置;

    8.3.1 冒泡排序

    1. 第一趟排序使关键字值最小的一个元素“冒”到最前面(其最终位置)—— 每趟冒泡的结果是把序列中最小元素放到序列的最终位置,这样最多做n-1趟冒泡就能把所有元素排好序

    2. 为保证稳定性,关键字相同的元素不交换;

    3. 代码实现

    //交换
    void swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
    }
    
    //冒泡排序
    void BubbleSort(int A[], int n){   //从0开始存放
        for(int i=0; i<n-1; i++){
            bool flag = false; // 表示本趟冒泡是否发生交换的标志
            for(int j=n-1; j>i; j--) //一趟冒泡过程
                if(A[j-1]>A[j]){      //若为逆序
                    swap(A[j-1],A[j]);  //交换
                    flag=true;
                }
            if(flag==false)
                return;       //本趟遍历后没有发生交换,说明表已经有序,可以结束算法
        }
    }
    
    1. 算法效率分析
    • 空间复杂度:O(1)
    • 时间复杂度
      • 最好情况 (有序) :只需要一趟排序,比较次数=n-1,交换次数=0,最好时间复杂度=O(n)
      • 最坏情况 (逆序) :比较次数 = (n-1)+(n-2)+...+1 = n(n-1)/2 = 交换次数,最坏时间复杂度 = O(n²),平均时间复杂度 = O(n²)
    1. 冒泡排序可以用于链表、顺序表

    8.3.2 快速排序

    1. 每一趟排序都可使一个中间元素确定其最终位置
    2. 用一个元素(不一定是第一个)把待排序序列“划分”为两个部分,左边更小,右边更大,该元素的最终位置已确认
    3. 算法实现(重点)
    //用第一个元素将待排序序列划分为左右两个部分
    int Partition(int A[], int low, int high){
        int pivot = A[low];          //用第一个元素作为枢轴
        while(low<high){
            while(low<high && A[high]>=pivot) --high; //high所指元素大于枢轴,high左移
            A[low] = A[high];   //high所指元素小于枢轴,移动到左侧
    
            while(low<high && A[low]<=pivot)  ++low; //low所指元素小于枢轴,low右移
            A[high] = A[low];   //low所指元素大于枢轴,移动到右侧
        }
        A[low] = pivot   //枢轴元素存放到最终位置
        return low;     //返回存放枢轴的最终位置
    } 
    
    //快速排序
    void QuickSort(int A[], int low, int high){
        if(low<high)   //递归跳出条件
            int pivotpos = Partition(A, low, high);   //划分
            QuickSort(A, low, pivotpos - 1);    //划分左子表
            QuickSort(A, pivotpos + 1, high);   //划分右子表
    }
    
    1. 算法效率分析
    • 每一层的QuickSort只需要处理剩余的待排序元素,时间复杂度不超过O(n);

    • 把n个元素组织成二叉树,二叉树的层数就是递归调用的层数,n个结点的二叉树最小高度 = ⌊log₂n⌋ + 1, 最大高度 = n

    • 时间复杂度 = O(n×递归层数) (递归层数最大为n)

      • 最好 = O(nlog₂n) : 每次选的枢轴元素都能将序列划分成均匀的两部分;
      • 最坏 = O(n²) :序列本就有序或逆序,此时时间、空间复杂度最高;
      • 平均时间复杂度 = O(nlog₂n) (接近最好而不是最坏)
    • 空间复杂度 = O(递归层数)(递归层数最小为log₂n)

      • 最好 = O(log₂n)
      • 最坏 = O(n)
    • 若每一次选中的“枢轴”可以将待排序序列划分为均匀的两个部分,则递归深度最小,算法效率最高;

    • 若初始序列本就有序或者逆序,则快速排序的性能最差;

    • 快速排序算法优化思路: 尽量选择可以把数据中分的枢轴元素

      • 选头、中、尾三个位置的元素,取中间值作为枢轴元素;
      • 随机选一个元素作为枢轴元素;
    • 快速排序使所有内部排序算法中平均性能最优的排序算法;

    • 稳定性: 不稳定;

    8.4 选择排序

    选择排序思想: 每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列;

    8.4.1 简单选择排序

    1. n个元素的简单选择排序需要n-1趟处理;
    2. 代码实现
    //交换
    void swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
    }
    
    void SelectSort(int A[], int n){       //A从0开始
        for(int i=0; i<n-1; i++){          //一共进行n-1趟,i指向待排序序列中第一个元素
            int min = i;                   //记录最小元素位置
            for(int j=i+1; j<n; j++)       //在A[i...n-1]中选择最小的元素
                if(A[j]<A[min]) min = j;   //更新最小元素位置
            if(min!=i)                     
                swao(A[i],A[min]);         //交换
        }
    }
    
    1. 算法效率分析
    • 空间复杂度 = O(1)
    • 无论有序、逆序、乱序,都需要n-1的处理,总共需要对比关键字 (n-1)+(n-2)+...+1 = n(n-2)/2 次,元素交换次数 < n-1; 时间复杂度 = O(n²)
    • 稳定性: 不稳定
    • 适用性: 既可以用于顺序表,也可以用于链表;

    8.4.2 堆排序

    1. 什么是“堆(Heap)”?

    可理解为顺序存储的二叉树,注意

    可以将堆视为一棵 完全二叉树 (✔)

    可以将堆视为一棵 二叉排序树 (✖)

    • 大根堆:完全二叉树中,根 ≥ 左、右
    • 小根堆:完全二叉树中,根 ≤ 左、右
    1. 如何基于“堆”进行排序

    基本思路:每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列,堆顶元素的关键字最大或最小 (以下以大根堆为例)

    ① 将给定初始序列(n个元素),建立初始大根堆:把所有非终端结点 从后往前都检查一遍,是否满足大根堆的要求——根 ≥ 左、右,若不满足,则将当前结点与更大的孩子互换

    • 在顺序存储的完全二叉树中:

      • 非终端结点的编号 i≤⌊n/2⌋
      • i 的左孩子 2i
      • i 的右孩子 2i+1
      • i 的父节点⌊i/2⌋
    • 更小的元素“下坠”后,可能导致下一层的子树不符合大根堆的要求,则采用相同的方法继续往下调整 —— 小元素不断“下坠”

    基于大根堆进行排序:每一趟将堆顶元素加入有序子序列中,堆顶元素与待排序序列中最后一个元素交换后,即最大元素换到末尾,之后该位置就不用改变,即移出完全二叉树(len=len-1),把剩下的待排序元素序列再调整为大根堆;————“一趟处理”

    ③ 剩下最后一个元素则不需要再调整;

    1. 代码实现
    //对初始序列建立大根堆
    void BuildMaxHeap(int A[], int len){
        for(int i=len/2; i>0; i--)   //从后往前调整所有非终端结点
            HeadAdjust(A, i, len);
    }
    
    /*将以k为根的子树调整为大根堆
    从最底层的分支结点开始调整*/
    void HeadAdjust(int A[], int k, int len){
        A[0] = A[k];                      //A[0]暂存子树的根结点
        for(int i=2*k; i<=len; i*=2){     //沿key较大的子结点向下筛选
                                          // i为当前所选根结点的左孩子
                                          //i*=2是为了判断调整后再下一层是否满足大根堆
            if(i<len && A[i]<A[i+1])      //判断:当前所选根结点的左、右结点哪个更大
                i++;                      //取key较大的子结点的下标
            if(A[0] >= A[i]) 
                break;                    //筛选结束:i指向更大的子结点
            else{
                A[k] = A[i];              //将A[i]调整至双亲结点上
                k=i;                      //修改k值,以便继续向下筛选
            }
        }
        A[k] = A[0]                       //被筛选的结点的值放入最终位置
    }
    
    //交换
    void swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
    }
    
    //基于大根堆进行排序
    void HeapSort(int A[], int len){
        BuildMaxHeap(A, len);          //初始建堆
        for(int i=len; i>1; i--){      //n-1趟的交换和建堆过程
            swap(A[i], A[1]);          //堆顶元素和堆底元素交换
            HeadAdjust(A,1,i-1);       //把剩余的待排序元素整理成堆
        }
    }
    

    8.5 归并排序和基数排序

    8.5.1 归并排序

    • 归并(Merge):把两个或多个已经有序的序列合并成一个;

    • k路归并:每选出一个元素,需对比关键字k-1次;

    • 外部排序通常采用归并排序,内部排序一般采用2路归并;

    • 代码实现

    //创建辅助数组B
    int *B=(int *)malloc(n*sizeof(int));
    
    //A[low,...,mid],A[mid+1,...,high] 各自有序,将这两个部分归并
    void Merge(int A[], int low, int mid, int high){
        int i,j,k;
        for(k=low; k<=high; k++)
            B[k] = A[k];           //将A中所有元素复制到B中
        for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
            if(B[i]<=B[j])          //为保证稳定性两个元素相等时,优先使用靠前的那个
                A[k]=B[i++];        //将较小值复制到A中
            else
                A[k]=B[j++];
        }//for
         
        //没有归并完的部分复制到尾部,while只会执行一个 
        while(i<=mid)  A[k++]=B[i++];     //若第一个表未检测完,复制
        while(j<=high) A[k++]=B[j++];     //若第二个表未检测完,复制
    }
    
    //递归操作
    void MergeSort(int A[], int low, int high){
        if(low<high){
            int mid = (low+high)/2;    //从中间划分
            MergeSort(A, low, mid);    //对左半部分归并排序
            MergeSort(A, mid+1, high); //对右半部分归并排序
            Merge(A,low,mid,high);     //归并
        }if
    }
    
    
    • 算法效率分析
      • 归并排序的比较次数与序列的初始状态无关;

      • 2路归并的“归并树”——倒立的二叉树,树高h,归并排序趟数m = h-1,第h层最多2^(h-1)个结点,则满足n ≤ 2^(h-1),即h-1 = ⌈log₂n⌉; 结论: n个元素进行2路归并排序,归并趟数 m = ⌈log₂n⌉

      • 每趟归并时间复杂度为O(n), 算法总时间复杂度O(nlog₂n);

      • 空间复杂度O(n); (归并排序算法可视为本章占用辅助空间最多的排序算法)

      • 稳定性:归并排序是稳定

      • 对于N个元素进行k路归并排序,排序的趟数m满足 k^m = N, m = ⌈logkN⌉

    8.5.2 基数排序

    1. 算法效率分析
    • 空间效率:O(r), 其中r为基数,需要的辅助空间(队列)为r;
    • 时间效率:一共进行d趟分配收集,一趟分配需要O(n), 一趟收集需要O(r), 时间复杂度为 O[d(n+r)],且与序列的初始状态无关
    • 稳定性:稳定!
    1. 基数排序擅长解决的问题

    ①数据元素的关键字可以方便地拆分为d组,且d较小;
    ②每组关键字的取值范围不大,即r较小;
    ③数据元素个数n较大;

    8.6 总结

    1. 稳定性

    稳定不稳定
    直接插入排序简单选择排序
    冒泡排序希尔排序
    归并排序快速排序
    基数排序堆排序

    2. 时间复杂度

    • 平均情况下:快速排序、希尔排序、归并排序、堆排序 均为 O(nlog2n); 基数排序为O(d(n+r)); 其余全是O(n²);
    • 最坏情况下:快速排序、希尔排序 为O(n²),其余与平均情况一样;
    • 最好情况下:直接插入排序、冒泡排序、希尔排序 为 O(n),其余与平均情况一样;

    3. 空间复杂度

    • 快速排序 :平均 —— O(log2n);最坏 —— O(n);
    • 2路归并排序:O(n);
    • 基数排序:O®;
    • 其余都是 O(1);
    • 就辅助空间而言:堆排序<快速排序<归并排序

    4. 过程特征

    • 经过一趟排序,能够保证一个元素到达最终位置: 交换类——冒泡、快速;选择类———简单选择、堆
    • 排序方法的元素比较次数与原始序列无关简单选择、折半插入
    • 排序方法的排序趟数与原始序列有关交换类——冒泡、快速
    • 排序方法中,元素的移动次数与原始序列无关基数排序
    • 初始序列有序时,冒泡排序比较n-1次,不需要移动元素;
    • 希尔排序堆排序利用顺序存储的随机访问特征,注意链式存储不支持这种性质;

    5. 排序算法的选择

    • n较小,可采用时间复杂度为**O(n²)**的排序方法:直接插入排序、简单选择排序,该情况下,若记录本身信息量较大,用简单选择排序;
    • n较大,应采用时间复杂度为**O(nlog2n)**的排序方法:快速排序、归并排序、堆排序
    • 快速排序——目前基于比较的内部排序方法中最好的方法,当关键字随机分布时,平均实际最短;
    • n很大,记录的关键字位数较少且可分解,选择基数排序
    • 若记录本上信息量较大,可用链表作为存储结构;
    • 若要求排序稳定且时间复杂度为O(nlog2n),则选择归并排序,通常和直接插入排序结合使用:先利用直接插入排序求得较长的有序子文件,再两两归并,仍是稳定;
    • 基数排序不能对floatdouble类型的实数进行排序;
    展开全文
  • 关系数据模型是什么

    千次阅读 2021-02-02 05:15:34
    关系数据模型中有三大要素,分别为:关系数据结构关系完整性约束和关系操作。下面我们就来简单了解一下。【相关视频教程推荐:MySQL视频教程】关系数据结构关系模型把数据库表示为关系的集合(关系模型中数据的...

    关系数据模型是一种数据模型,以关系或表格的形式对数据进行建模,是用来表示数据在关系数据库中的存储和处理方式,在关系数据库中会以关系(表)的形式来存储数据。

    a4ec93f36dffd67b53ef16c8b82647b4.png

    关系数据模型中有三大要素,分别为:关系数据结构、关系完整性约束和关系操作。下面我们就来简单了解一下。【相关视频教程推荐:MySQL视频教程】

    关系数据结构:

    关系模型把数据库表示为关系的集合(关系模型中数据的逻辑结构是一张二维表)。下面我们来看看主要的一些结构概念:

    1、表

    在关系数据模型中,关系以表格的形式保存。它存储实体之间的关系,具有行和列,其中行表示记录,列表示特定属性的值集。例:

    b861f0f52181fabc3e48d823f23c0633.png

    2、元组

    表的一行,包含该关系的单个记录称为元组。使用“基数”来表示元组的数量,例:上面定义的学生关系的基数就是4(有4条记录)。

    3、属性

    定义了关系的属性,例如:姓名、年龄都是学生的属性。关系中的属性总数称为关系“度”,例:上面定义的学生关系的度为4

    6b8948b3cb44ca6f7a112f6fd574c76f.png

    4、关系模式

    关系模式描述关系名称(表名称),属性及其名称。如果模式具有多个关系,则称为关系模式。

    5、关系实例

    关系数据库系统中的一组有限元组表示关系实例。关系实例没有重复的元组。

    6、关键键

    每行都有一个或多个属性,称为关系键,可以唯一地标识关系(表)中的行。

    7、属性域

    每个属性都有一些预定义的值范围,称为属性域。

    关系的完整性约束

    每个关系都必须有一些条件,使其成为有效关系;而这些条件称为关系完整性约束,有三个主要的完整性约束,下面我们来看看:

    1、关键约束

    关系中必须至少有一个属性的最小子集,它可以唯一地标识元组。这个最小的属性子集称为该关系的密钥。如果存在多个这样的最小子集,则这些子集称为候选密钥。

    关键限制

    1)、在与键属性的关系中,没有两个元组可以具有相同的键属性值。

    2)、键属性不能具有NULL值。

    说明:关键约束也称为实体约束。

    2、域约束

    属性在实际场景中具有特定值。例如,年龄只能是正整数。已经尝试对关系的属性采用相同的约束。每个属性都必须具有特定的值范围。例如,年龄不能小于零,电话号码不能包含0-9之外的数字。

    3、参照完整性约束

    参照完整性约束表明如果关系引用不同或相同关系的键属性,则该关键元素必须存在。它适用于外键的概念。外键是可以在其他关系中引用的关系的关键属性。

    关系操作:

    关系操作主要是包括:查询、插入、删除、更新等操作。

    以上就是本篇文章的全部内容,希望能对大家的学习有所帮助。

    展开全文
  • 最近开始做数据库的大实验,其中有一条实验要求如下:通过网络查找相关文献并参考所给资料进行需求分析,画出系统的 E-R 图,给出实体或联系的属性,标明联系的种类,并写出关系模式。画ER图没有什么问题,但是关系...
  • 专升本数据结构复习

    千次阅读 多人点赞 2021-03-03 13:48:51
    数据结构知识点总汇 主要参考书目: 程海英老师的《数据结构(C语言版)》教材 严蔚敏,李冬梅,吴伟民.《数据结构(C语言版)》 说明:这是本人专升本上岸一年后写的,本篇包含知识点和例题总结。因为是当时自己...
  • 数据结构面试常见问题

    千次阅读 2021-01-04 16:00:05
    (1)数据结构是指所有数据元素以及数据元素之间的关系,可以看作是相互之间存在着某种特定关系的集合,因此可以我们将数据结构看成是带结构的数据元素的集合。此外,在通常情况下,选择合适的数据结构可以带来提高...
  • 30 个重要数据结构和算法完整介绍(建议收藏保存)

    万次阅读 多人点赞 2021-06-07 08:02:06
    数据结构和算法 (DSA)通常被认为是一个令人生畏的话题——一种常见的误解。它们是技术领域最具创新性概念的基础,对于工作/实习申请者和有经验的程序员的职业发展都至关重要。话虽如此,我决定在CSDN新星计划挑战...
  • 什么?程序竟然等于数据结构 + 算法?这个公式是大师 Niklaus Wirth 在 1976 年提出来的,40 多年过去了,这个公式还成立吗?对于做 Java 开发的朋友,可能会更加的赞...
  • 展开全部数据库中“关系模式”的定义是对关系的描述,其必须指出这个元组集合的结构,也就是它32313133353236313431303231363533e4b893e5b19e31333366306435由哪些属性构成,这些属性来自哪些域,以及属性与域之间的...
  • 关系数据模型——三个组成部分

    千次阅读 2021-09-04 15:17:03
    关系模型的三个组成部分,是指关系数据模型的数据结构关系数据模型的操作集合和关系数据模型的完整性约束。 关系数据模型的数据结构 主要描述数据的类型、内容、性质以及数据间的联系等,是目标类型的集合。 目标...
  • 数据库原理-关系模式的规范化

    千次阅读 2021-08-26 12:29:02
    关系数据库的规范化理论是数据库逻辑设计的工具 一个关系只要其分量都是不可分的数据项,它就是规范化...关系模式集合,这种过程就叫关系模式的规范化。 1.关系模式规范化的步骤 消除决定属性集非码的非平凡函数依赖 1
  • 模式是数据库结构的描述、关系模式是表的结构的描述 学生记录型: (学号,姓名,性别,系别,年龄,籍贯) 一个记录值: (900201,李明,男,计算机,22,江苏) 模式(Schema) 数据库逻辑结构和特征的描述 是...
  • Redis的五种数据结构的底层实现原理

    万次阅读 2021-01-31 02:49:22
    Redis的五种数据结构的底层实现原理: 1、String底层实现方式:动态字符串sds 或者 long; 2、Hash底层实现方式:压缩列表ziplist 或者 字典dict; 3、List在Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向...
  • 贝尔梅尔娜美2019.03.15采纳率:60%等级:39已帮助:91565人数据库系统的基本概念数据:实际上就是描述事物的符号记录。数据的特点:有一定的结构,有型与值之分,如...数据库存放数据是按数据所提供的数据模式存...
  • 数据库关系模式的规范化

    千次阅读 2021-04-03 15:23:11
    在任何一个关系数据库中,第一范式(1NF)是对关系模式的基本要求,不满足第一范式(1NF)的数据库就不是关系数据库。 所谓第一范式(1NF)是指数据库表的每一列都是不可分割的基本数据项,同一列中不能有多个值,即...
  • 写在前面:本文写于吴签时期,在家备考时刷完数据结构王道书之后想着把书中重点梳理汇总一下。本文内容包括但不局限于王道数据结构每章的知识点及其课后习题所涵盖的知识点。本人曾在大三期间打过一些程序设计类比赛...
  • 3 第2章 线性表5 【习2.1】 习2-5 图2.19的数据结构声明。5 【习2.2】 习2-6 如果在遍历单链表时,将p=p.next语句写成p.next=p,结果会怎样?5 【习2.3】 实验2.2 由指定数组中的多个对象构造单链表。5 【习2.4】 ...
  • 关系模式是对这个表的结构进行叙述。它可以形象化的表示为 【R(U,D,DOM,F) R为关系名,U为组成该关系的属性名集合,D为U中属性所来自的域,DOM为属性向域的映像集合,F为属性间数据的依赖关系集合。】以上,对于...
  • 大家好,我是小林。 昨天有位关注我一年的读者找我,他去年关注我公众后,开始...这里先给大家分享些计算机必读书籍,获取方式:计算机必读书籍(含下载方式),包含数据结构与算法、操作系统、计算机网络、数据库、L
  • 《王道》数据结构笔记整理2022

    千次阅读 多人点赞 2021-08-06 15:17:51
    数据结构第一章绪论1.1数据结构的基本概念1.2数据结构的三要素1.3算法的基本概念1.4算法的时间复杂度1.5算法的空间复杂度 第一章绪论 1.1数据结构的基本概念 1.数据:数据是信息的载体,是描述客观事物属性的数、...
  • 关系数据库模式->关系数据库管理 用户需求->概念模型(E/R Model)->逻辑模型(三层结构) 现实世界->信息世界->机器世界 概念设计工具E-R图 E-R图的组成元素:实体、属性、联系(而不是关系) ...
  • 《算法和数据结构》学习路线指引

    万次阅读 多人点赞 2021-07-01 11:16:15
    本文已收录于专栏 《画解数据结构》 饭不食,水不饮,题必须刷 C语言免费动漫教程,和我一起打卡! 《光天化日学C语言》 LeetCode 太难?先看简单题! 《C语言入门100例》 数据结构难?不存在的! 《画解数据结构》 ...
  • 数据模型和数据模式的理解和区别

    千次阅读 2021-02-10 01:38:22
    数据模型和数据模式的理解和区别     ...一般来说,数据的描述包括两个方面,一是数据的静态特征,包括数据的基本结构数据间的联系和数据的约束。二是数据的动态特征,是指定
  • 爆锤数据结构(期末复习笔记)

    千次阅读 多人点赞 2021-11-22 00:18:29
    数据结构期末机考大致有5道题,难度由浅入深,根据去年实际体验,大致人均AC2~3题。 例题 这部分的两道题大概是去年机考的第四第五题(前面题记不清了),凭着回忆把题目重新写了下,又做了一遍,自己敲了标程。 ...
  • E-R图向关系模式的转换需要考虑的是:将实体型和实体间的联系转换为关系模式。 由此可以得出:向关系模式的转换即需要 1:实体的转换 2:联系的转换 其中两个实体间的联系的类型有三种: 即: 1:1型,1:n型,m:n型 故与之...
  • 数据库系统结构(1)两种角度(2)数据库系统模式的概念(3)数据库系统的三级模式结构模式(Schema)② 外模式(External Schema)③ 内模式(Internal Schema)(4)数据库的二级映像功能与数据独立性① 外模式...
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。能换你一个收藏了吧?
  • mysql表关系

    千次阅读 2021-01-19 23:33:19
    表与表之间的关系"""把所有数据都存放于一张表的弊端1.组织结构不清晰2.浪费硬盘空间3.扩展性极差"""#上述的弊端产生原因类似于把代码全部写在一个py文件中,你应该怎么做?>>>解耦合!将上述一张表拆成...
  • 复习数据结构的时候遇到了这两个词,就想着记录一下,因为我起初有点混淆了emmm…… 一、存取结构 存取结构分为顺序存取和随机存取 顺序存取:不能通过下标访问,只能按照存储顺序存取,与存储位置有关,例如链表。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 665,906
精华内容 266,362
热门标签
关键字:

数据结构的关系模式

数据结构 订阅