# 数据结构学习 **Repository Path**: lkq55421/data-structure-learning ## Basic Information - **Project Name**: 数据结构学习 - **Description**: 数据结构java 学习 - **Primary Language**: Java - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-12-29 - **Last Updated**: 2022-08-01 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 数据结构学习 #### 介绍 数据结构java 学习 数据 数据之间的关系 线性表 树 图 链式存储 对元素施加的操作 运算 抽象数据类型=逻辑结构+抽象运算 存储 组织 算法 ### 算法特性： 1.有穷性 2.可行性 3.确定性 4.有输入 5.有输出 ### 算法设计目标： 1.健壮性 2.可读性 ### 算法描述方法： 1.自然语言 2.流程图 3.程序设计语言 4.伪代码（自然与程序的结合，便于整体逻辑掌握） ### 算法分析： #### 时间代价（复杂度）： #### 空间代价（复杂度）： 事先分析估算： 原操作的内增长积 ## linearList线性表 双链表是每个结点有两个地址域的线性链表，两个地址域分别指向前驱结点和后继结点。 ### 循环链表 #### 循环单链表 将最后一个结点的next域指向head，将最后一个结点的next域指向head，就是循环单链表 ##### 区别： 循环单链表与单链表操作算法基本相同，只是判断条件不同： 单链表p指向尾结点时：p.next=null 循环单链表p指向尾结点时：p.next=head 循环单链表设置尾指针找开始结点和终端结点都很方便： 开始结点：rear.next.next 等同于 this.head.next 终端结点：rear 因此，实际应用中多采用尾指针指示的循环单链表。 ``` -com -linearList 线性表分组 -SeqList 线性表数据结构 实现类（数组） -SeqListTest 线性表数据结构 测试类 -Node 单向结点类 -SinglyList 单链表数据结构 实现类 -SinglyListTest 单链表数据结构 测试类 -SinglyListCycle 循环单链表数据结构 实现类 -SinglyListCycleTest 循环单链表数据结构 测试类 -DoubleNode 双向结点类 -DoubleLinkedList 双向链表数据结构 实现类 -DoubleLinkedListTest 双向链表数据结构 测试类 ``` 当线性表中元素个数变化较大或未知时 最好采用链表实现 如果事先知道线性表的大致长度 使用顺序表的空间利用率会更高 ## 栈和队列 栈和队列是两种特殊类型的线性表 特殊之处在于插入和删除操作的位置受到限制 ### 栈和队列的实际应用 栈的主要特点：是只能在栈顶操作（插入和删除操作只允许在线性表的一端进行），也就是遵循后进先出（先进后出） 的运算规则。 队列的主要的特点：是只能在一端插入，另一端删除的一种线性表（插入和删除操作分别在线性表的两端进行） ，也就 是遵循先进先出的运算规则 ### 栈 栈的定义： 栈(Stack)是一种特殊的线性表，其插 入和删除操作只允许在线性表的一端 进行。通常称允许插入、删除操作的 这一端为栈顶(Top)，不允许操作的一 端称为栈底(Bottom)。当表中没有元 素时称为空栈。 假设栈S=(a0，a1，a2，a3，…an-1)， 则a0称为栈底元素，an-1为栈顶元素， 标识栈顶位置的指针称为栈顶指针。 栈中元素按a0， a1，a2，a3，… an-1 的次序进栈，退栈的第一个元素应为 栈顶元素。换句话说，栈的修改是按 后进先出的原则进行的。因此，栈称 为后进先出表（LIFO）。 栈的操作： 习惯上将每次删除（也称为退栈）操 作又称为出栈或弹出（POP）操作。 删除的元素总是当前栈中“最新”的 元素（栈顶元素）。 每次插入（称为进栈）操作称为入栈 或压入（PUSH）操作，入栈的元素 总是当前栈中“最新”的元素。 在空栈中最先插入的元素总被放在栈 的底部，只有所有元素被弹出之后它 才能被删除。 栈的数据元素： 栈的数据元素和线性表的数据元素完 全相同，即栈的数据元素是n（n>=0） 个相同类型的数据元素a0，a1，。。。 an-1组成的有限序列，记为： {a0,a1,…an-1}。 其中，n为数据元素的个数，称为栈的 长度。n=0时，为空栈。 栈的运算： 栈的基本运算一般有以下几种： • ① InitStack（S）构造一个空栈S。 • ② StackEmpty（S）判栈空，若S为空栈 返回TRUE，否则返回FALSE。 • ③ StackFull（S）判栈满，若S为满栈， 则返回TRUE，否则返回 FALSE。该运 算只适用于栈的顺序存储结构。 • ④ Push（S，x）入栈。若栈S不满，则 将元素x压入S的栈顶。 • ⑤ Pop（S）出栈。若栈S非空，则将S 的栈顶元素弹出，并返回该元素。 • ⑥ StackTop（S）取栈的栈顶元素，不 修改栈顶指针。 比较重要的运算就是入栈和出栈两种。 栈的溢出： • 当栈满时进栈运算称为“上溢”。 • 当栈空时退栈运算称为“下溢”。 • 栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通 常下溢用来作为程序控制转移的条件。 栈的分类： 就线性表而言，实现栈的方法有很多， 由于栈也是线性表，因此线性表的存 储结构对栈也适用，我们着重介绍顺 序栈（arrary-based stack）和链式栈 （linked stack） ，它们类似于顺序表 和链式表。。 #### 栈抽象数据类型 栈的抽象接口 #### 顺序栈 顺序栈的定义：  由于栈是运算受限的线性表，因此线 性表的存储结构对栈也适应。  栈的顺序存储结构简称为顺序栈 （Sequential Stack），它是运算受 限的线性表。因此，可用数组来实现 顺序栈。 因为栈底位置是固定不变的，所以可 以将栈底位置设置在数组的两端的任 何一个端点；栈顶位置是随着进栈和 退栈操作而变化的，一般需用一个整 型变量top。 #### 链式栈 链式栈的定义：  栈的链式存储，称为链栈。  链式栈的基本运算同顺序栈，定义也同 线性表的链表定义，它是对链表实现的 简单化（因为它只是对链表的头部操 作）。  可用单向链表实现链栈。  它的元素只能在表头进行插入和删除。 在链式存储结构中，不需要给出表头结 点（head），因为其中惟一的已知条件 是栈顶指针top，它是指向链式栈的第一 个结点（相当于头指针）。 #### 顺序栈和链式栈的比较  实现链式栈和顺序栈的操作，都是需要 常数时间，即时间复杂度为O（1）。主 要两者从空间和时间两个方面考虑： • 初始时，顺序栈必须说明一个固定的 长度，当栈不够满时，造成一些空间 的浪费，而链式栈的长度可变则是长 度不需要预先设定，相对比较节省空 间，但是在每个结点中，设置了一个 指针域，从而产生了结构开销。 • 当需要多个栈共享时，顺序存储中可 以充分利用顺序栈的单向延伸性。可 以使用一个数组存储两个栈，使每个 栈从各自的端点向中间延伸，这样浪 费的空间就会减少。但这种情况只有 当两个栈的空间需求有相反的需求时， 这种方法才有效。 • 也就是说，最好一个栈增长，一个栈 缩短。反之，如果两个栈同时增长， 则可能比较容易造成栈的溢出。如果 多个顺序栈共享空间，则可能需要大 量的数据移动，造成时间的开销增大。 而链式栈由于存储的不连续性，一般 不存在栈满的问题，所以一般不需要 栈的共享。 ### 队列 队列的定义： •队列(Queue)也是一种运算受限的特殊线 性表。其插入和删除操作分别在线性表 的两端进行（只允许在表的一端进行插 入，而在另一端进行删除）。允许删除 的一端称为队头(front)，允许插入的一 端称为队尾(rear)。 •当队列中没有元素时称为空队列。 •在空队列中依次加入元素a0,a1,…an-1之 后，a0是队头元素，an-1是队尾元素。则 退出队列的次序也只能是a0,a1,…an-1 ， 也就是说队列的修改是依先进先出的原 则进行的，例如：排队购物。 •先进入队列的成员总是先离开队列。因 此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 队列的操作： • 一般情况下，入队(enqueue)操作又称 为队列的插入。 • 出队(dequeue)操作又称为队列的删除。 队列的数据元素： • 队列的数据元素和线性表的数据元素 完全相同，即队列的数据元素是n （n>=0）个相同类型的数据元素a0， a1，。。。an-1组成的有限序列，记为： {a0,a1,…an-1}。 • 其中，n为数据元素的个数，称为队列 的长度。n=0时，为空队列 。 队列的运算：  队列的基本运算通常和栈的基本运算类 似，有以下6种： • ① 置空队； //构造一个空队列。 • ② 判队空； //队空返回真，否则返回 假。 • ③ 判队满； //队满返回真，否则返回 假，仅限于顺序存储结构。 • ④ 入队； //队列非满时，从队尾插入元素。 • ⑤ 出队； //队列非空时，从队首删除元素。 • ⑥ 取队首元素； //返回队首元素，不修改 队首指针。 队列的溢出： • 队列在顺序存储时，经常出现“假溢 出”现象，解决“假溢出”现象的方 法有很多种，但通常采用循环队列方 式存储。 #### 队列的抽象数据类型 队列的分类： • 队列的存储具有顺序和链式存储两种， 因此队列可分为顺序队列和链式队列。 #### 顺序队列 顺序队列的定义：  队列的顺序存储结构称为顺序队列。  顺序队列实际上是运算受限的顺序 表。和顺序表一样，顺序队列也用 一个数组空间来存放当前队列中的 元素。  由于队列的队头和队尾的位置是 变化的，因而要设置两个指针 front和和rear分别指示队头元素 和队尾元素在数组空间中的位置， 它们的初值在队列初始化时可以 置为0（或-1） 顺序队列的操作：  入队时将rear加1，然后将新元 素插入rear所指的位置。  出队时，删去front所指的元素， 然后将front加1并返回被删元素  在非空队列里，头指针始终指向 队头元素，而尾指针始终指向队 尾元素。  所谓“假溢出”是指在入队和出队操作 中，头尾指针不断增加而不减小或只减 小而不增加，致使被删除元素的空间无 法重新利用，最后造成队列中有空闲空 间，但是不能够插入元素，也不能够删 除元素的现象。 循序循环队列的定义：  现在解决“假溢出”比较好的解决方案 是使用循环向量，存储在循环向量中的 队列称为循环队列（Circular Quene）。  将顺序队列设计成在逻辑上首尾相接的 循环结构，则可循环使用顺序队列的连 续存储单元。 循环队列的操作： • 假设数组的空间是m，只要在入、出 队列时，将队首和队尾的指针对m做 求模运算即可实现队首和队为指针的 循环，即队首和队尾指针的取值范围 是0到m-1之间。 • 入队时：rear=（rear+1）% maxsize • 出队时：front=（front+1）% mixsize  在入队时，先不修改rear的值，而是先判断 （rear+1） % maxsize==front，如果成立， 表示队列已满（此时实际还有front指向的 位置空闲）  出队时，只要判断front==rear，如果成立 表示队已空，否则只要front=（front+1） % maxsize直接删除元素即可。  此种方法存储的数据元素个数是maxsize-1 front=(front+1) % length; rear=(rear+1) % length; #### 链式队列 链式队列的定义：  链式队列的基本概念： • 定义链队列的存储结构基本和线性表 的定义相同，是对链表实现的简单化。 • 队列的各种运算比链式存储的普通线 性表运算实现时要方便得多，主要原 因是队列的各种运算只能在队列的两 端操作。 • 队列是特殊的线性表，只考虑对线性 表的两端操作的情况，并且只能一端 插入（队首），另一端删除（队尾）。 • 而线性表除此之外，还需要考虑中间 结点的插入、删除、查询等操作。 • 理解时，可以把队列的入、出队运算 当作线性表两端进行插入删除的特例 即可。 • 队列的操作都是在头尾进行的，链表 刚好可以支持这种操作。 •队列的链式存储结构简称为链队列， 它是限制仅在表头删除和表尾插入的 链表 •显然仅有链表的头指针不便于在表尾 做插入操作，为此再增加一个尾指针， 指向链表的最后一个结点。 •于是，一个链队列由头指针和尾指针 唯一确定。 ## 字符串、数组和广义表 ### 字符串 #### 串的概念与存储结构 1.串的基本概念 • 一个串是由n（n≥0）个字符组成的有限序列，记为s=“s0s1 ⋯ sn-1”，其 中，s是串名，双引号括起来的字符序列s0s1 ⋯ sn-1是串值。 • 一个字符在串中的位置称为该字符在串中的序号，约定串第一个字符 的序号为0。 • 由串s中任意连续字符组成的子序列称为s的子串，s称为主串。 空串是任意串的子串； 任意串都是它自身的子串； 除自身外，串的其他子串称为其真子串。 • 子串的序号是指该子串首字符在主串中的序号。 • 两个串相等是指，串长度相同且对应位置上的字符也相同。 2.串的存储结构 •串的顺序存储结构 采用字符数组将串中的字符序列依次存储在数组的相邻单元中。 顺序串具有随机存取特性，存取指定位置字符的时间复杂度为O(1)； 缺点是插入、删除时需要移动数据元素，平均移动数据量是串长度 的一半，插入、删除操作的时间复杂度为O(n)。 • 串的链式存储结构 串的链式存储结构有单字符链表和块链表两种，如下图所示。 链式存储的串，存取指定位置字符的时间复杂度为O(n)； 单字符链表虽然插入删除操作不需要移动数据元素，但占用存储空间太 多；块链表的插入和删除操作需要移动元素，效率较低。 3.不同语言的比较 c/c++语言采用字符数组或字符指针表示字符串，但字符串不同于字 符数组，字符串只是采用字符数组作为其存储结构，它要实现字符串抽 象数据类型所要求的操作。 Java语言将字符串及其操作封装成字符串类，实现字符串抽象数据 类型，这正是数据结构的理论成果促进程序设计语言发展的体现。 Java语言的字符串类主要由常量字符串String、变量字符串 StringBuffer。这两种字符串类都采用顺序存储结构，能够存储任意长度 的字符串，实现串的基本操作。 #### 串的模式匹配 1.定义 设有两个串：目标串target和模式串pattern，在目标串target中查找 与模式串pattern相等的一个子串并确定该子串位置的操作称为串的模式 匹配（Pattern Matching）。 匹配结果有两种：如果target中存在与pattern相等的子串，则匹配成 功，获得该子串在target中的位置；否则匹配失败，给出失败信息。 2.模式匹配算法 • Brute-Force（BF）算法 BF算法的基本思想是蛮力匹配，即从目标串target的每 一 个字符开始依次与模式串pattern的字符进行比较。 • KMP算法 KMP算法是一种无回溯的模式匹配算法，它改进了BF算 法，目标串不回溯。 匹配不成功时，j从0开始后移 了j个位置，同理，i也后移了j个位 置，则这一次匹配中目标串的开始 位置是i-j，那么下一次匹配的开始 位置就是i-j+1。 匹配成功时，j从0向后移动 了j个位置，i也向后移动了j个位 置，则目标串中本次匹配的开始 位置就是i-j，也就是匹配成功时 子串的位置。 BF算法效率分析 （a）最好情况，"t0t1…tm-1"="p0p1…pm-1"，比较次数为模式串长度m，时间复杂度为O(m) （b）最坏情况，每轮匹配比较m次，匹配n-m+1轮，时间复杂度为O(n×m) KMP算法 KMP算法是一种无回溯的模式匹配算法，目标串不回溯， 它改进了BF算法。 总之，当t2≠P2时，无论p1与p0是否相同，目标串下次匹配都从t2开 始比较，不回溯；而模式串要根据p1与p0是否相同，确定从p0或p1开始 比较。 因此，KMP算法关键是要找到模式串开始比较的位置。 至此，问题转化为对模式串中每一个字符pj，找出”p0…pj-1”串中相同 的最长前缀子串和后缀子串的长度k，k取值只与模式串有关，与目标串 无关。 由于模式串中每个字符pj的k不同，将每个pj对应k值保存在一个next 数组中。 KMP算法分析 KMP算法的最好情况同BF算法，比较次数为m，时间复杂 度为O(m)； 最坏情况，比较次数为n，算法的时间复杂度为O(n)。