数据结构学习

介绍

数据结构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)。