数据结构

一、概念和术语

数据结构是一门研究非数值计算的程序的操作对象，以及他们之间关系和操作问题的学科。

数据：

能输入到计算机
能被计算机处理
- int ，字符串，图片等等都属于数据

数据元素：

组成数据的基本单位
- 对象就是一个数据元素

数据项：

组成数据元素的基本单位，是不可分割的最小单位

数据对象：（是性质相同的数据元素对象集合，是数据的子集）

数据结构：是相互之间存在一种或多种特定关系的数据元素集合。

2.逻辑结构和物理结构

逻辑结构顾名思义是指数据对象中数据元素之间的相互关系（实例化类的相互关系）
- 集合结构同一个集合没有什么关系终生平等
- 线性结构一一对应
- 树形结构各个数据元素之间存在一种多对多的关系
- 图形结构数据元素是多对多的关系
物理结构（内存中的排列）
- 顺序存储结构数组就是一种典型的
- 链式存储结构

总结

类（数据对象）
- 对象（数据元素）
  - 元数据（数据项）
  - 元数据2
- 对象2..

二、算法

以后再填

三、线性表List

1.顺序存储结构

线性表：0个或者多个数据元素组成的有序序列

最简单的一种数据结构线性表：

头结点只有且仅有一个直接后继，尾结点有且只有一个直接前驱

数组是一种典型的线性表、顺序存储结构

线性表：

地址连续
依次存放
随机读取
类型相同

存储位置计算（只适用于顺序存储）

第i个元素下1位地址计算书

loc(ai + 1) = loc（ai） * (一个元素所需要的存储空间 C中可以使用sizeof()来获取)

ADT 线性表（list）

operation：（基本操作）

initList()；初始化链表

listEmpty(); 若线性表为空返回

clearList（）清空线性表

getElem（）返回第i个元素的值

*localElem（）查找一个元素

*listInsert（）在第i个位置插入新元素

*listDelete() 删除线性表第i个元素，并获取删除的值

listLength（）获取线性表长度

以上是最基本的操作，但也完全足够，复杂的操作我们可以将他们复合在一起实现

实现：基于Java

import javax.xml.crypto.Data;

class DataType{//数据域 可以根据自己需要调整
    int value;
	
    //构造方法
    public DataType() {
    }
    public DataType(int value) {
        this.value = value;
    }
}

class List{
    DataType[] elem;
    //表示线性表长度
    static int length = 0;

    //operation
    boolean initList(int count){//初始化一个拥有count个数据元素的 线性表
        //为数据域分配空间
        try{
            this.elem = new DataType[count];
        }catch (Exception e){
            System.out.println("内存分配失败");
        }

        return true;
    }

    void destroyList(){//销毁线性表 java拥有垃圾自动回收 相比于C、c++ 动态内存管理要好实现
        this.elem = null;
        this.length = 0;
    }

    int getLength(){//返回线性表长度
        return this.length;
    }

    boolean isEmpty(){//判断线性表是否为空
        if (this.length == 0)
            return true;
        else
            return false;
    }

    DataType getElem(int i){//根据i的位置获取相应内容

        if (i > this.length || i < 1)   //下标越界 返回空值
            return null;
        System.out.println("返回元素的值为"+this.elem[i - 1].value);
        return this.elem[i - 1];
    }

    int locateElem(DataType f){  //查找 数据是否在线性表中
        if (this.isEmpty())//判断线性表是否为空
            return -1;//线性表为空直接返回-1
        else
            for (int i = 0; i < this.length; i++) {
                if (f.value == this.elem[i].value)
                    return i;//找到元素返回该元素
            }
        return -1;    //未找到 返回空
    }


    //通过重载插入函数实现参数默认值
    boolean listInsert(DataType insert){//表中插入一个元素
        return listInsert(insert, this.length + 1);    //重载函数实现默认值
    }
    boolean listInsert(DataType insert, int index){//核心思想 把从最后线性表后依次向前移元素
        if (index < 1 || this.length >= 20)  //这里我默认为20位最大
            return false;   //下表越界

        //核心
        for (int i = length - 1; i >= index - 1; i--) {
            this.elem[i] = this.elem[i - 1];
        }
        this.elem[index - 1] = insert;
        this.length ++;
        return true;
        //
    }


    //删除线性表中第index个元素
    boolean deleteElem(int index){
        return deleteElem(index, null);
    }
    boolean  deleteElem(int index, DataType dele_temp){
        if (index < 1 || index > this.length)
            return false;//判断下表是否合法  也返回空
        else {//核心
            dele_temp = this.elem[index - 1];
            for (int i = index - 1; i < this.length - 1; i++) {
                this.elem[i] = this.elem[i + 1];
            }
        }
            this.length --;//表长减一
            return true;
            //核心
    }

    //展示数据元素
    boolean showElem(){
        if (this.isEmpty())
            return false;
        for (int i = 0; i < this.length; i++) {
            System.out.print(this.elem[i].value+"   ");
        }
        System.out.println("");
        return true;
    }

}

public class Main{
    public static void main(String[] args) {
        List l = new List();
        l.initList(20);
        DataType[] data = new DataType[20];

        for (int i = 0; i < 20; i++) {
            data[i] = new DataType();
            data[i].value = i + 1;
            if (l.listInsert(data[i]))
                System.out.println("插入成功");

        }
        System.out.println("插入了"+l.getLength()+"个数据元素");

        //查找 22这个元素
        l.showElem();
        int b = l.locateElem(new DataType(22));
        if (b != -1)
            System.out.println("找到了值为这个元素");
        else
            System.out.println("没有找到");

        l.deleteElem(10);
        l.showElem();
        System.out.println("当前长度"+l.getLength());

        l.listInsert(new DataType(10), 10);
        l.showElem();
        System.out.println("当前长度"+l.getLength());
        if (!l.listInsert(new DataType(20)))
            System.out.println("插入失败");

        l.destroyList();//销毁线性表
        l.showElem();
    }
}

以上顺序存储的线性表依旧存在很多缺陷
Java方法没有默认值，因此实现默认值用的是重载方法实现
基本实现了增删改查等功能
本质还是引用传递（Java是值传递），所以各元素内存值并不是连续的，但无伤大雅思想是对的

优点：

随机去表中任意元素 O（1）
存储密度大（节点本身所占存储量/节点结构所占的存储量）

缺点：

增加删除元素 O(n) 最坏的情况就是对表头操作
浪费存储空间
数据元素最大值固定，属于静态存储形式

2.链式存储

对比顺讯存储结构:

优点：

长度不定义可以扩容
插入删除结点 O(1)
内存地址不连续

缺点:

无法随机读取
每个结点需要占用一部分空间存储指针

2.1单链表

对顺序存储结构的链表优化，可以自由扩充链表

Node (单链表)

Data:数据域
 Ptr:指针域

每个数据元素有数据域和指针域（引用）
通过一个头指针来指定线性表也叫作单链表（有头结点（为空时头指正指向null），无头结点都一样（头结点其指针域null））
最后一个节点指向null，头结点指向链表的第一个节点
逻辑结构和物理结构不在相等

Java 实现：

数据域

class ElemType{ //自定义数据类型
    int value;

    public ElemType() {
    }
    public ElemType(int value) {
        this.value = value;
 }

结点类

static int length；可不定义

需要自定义getLength() 方法每次获取时间复杂度为O（n）

class Node
{//结点
    ElemType data;//数据域
    Node next = null;  //指针域

    static int length = 0;

    public Node() {
    }
    public Node(ElemType data){
        this.data = data;
    }
    public Node(ElemType data, Node next) {//初始化方便插入 造的构造
        this.data = data;
        this.next = next;
    }
}

基本方法

基于Java类实现，其他语言需要传入头指针参数 this改为head

isEmpty()检查是否为空链

boolean isEmpty() {
    if (this.next == null)
        return true;
    else
        return false;
}

getLength()获取链表长度

1
2
3

int getLength() {//获取链表长度
    return this.length;//自定义的静态int 每个结点需要单独的增加一块int 空间 并且每次添加删除 都需要单独递增 递减
}

initLinkList（）初始化化链表

Java 没有默认值，用重载方法为其添加默认值
这里使用的头插法初始化链表

Node initList() {//初始化一个链表
    int count = 1;
    return initList();
}

Node initList(int count) {//创建count个node 的链表并使其递增赋值
    if (count < 1)
        return null;    //创建失败返回空值
    Node head = this;  //头结点

    for (int i = 0; i < count; i++) {
        head.next = new Node(new ElemType(i + 1), head.next);
        head = head.next;
        this.length++;
    }
    return this;    //返回头结点引用
}

initLinkList_end（）尾插法实现的链表初始化

boolean initList_end(int count) {
        this.destoryList(); //清空链表
//        核心
        Node head = this;
        for (int i = 0; i < count; i++) {
            head.next = new Node(new ElemType(i + 1), head.next);
            head = head.next;
            this.length++;
        }
        return true;
//        核心
    }

insertList(int index, Node data) 插入一个元素在index位置前插入一个结点

    boolean insertList(int index, Node data) {//插入 链表结点
        if (index > this.getLength() || index < 1)
            return false;//判断下标是否合法

        Node head = this.next;//头指遍历链表
        int count = 1;
//        核心
        while (head != null && count < index - 1) {
            head = head.next;
            count++;
        }
        data.next = head.next;
        head.next = data;
        this.length++;
        return true;
//        h核心
    }

getNode(int index ) 获取下标为index 的数据元素并返回其地址（引用）


Node getNode(int index){//获取下标为index 的元素 返回改结点
        if (index < 1 || index > this.length)
            return null;    //下标越界
        Node ret_val = this;
        int i = 0;
        while (ret_val != null || i < index){//为空 小于下标结束
            ret_val = ret_val.next;
            i++;
        }
        return ret_val.next;
    }

删除一个结点 deleteNode（）返回成功与否

可改返回删除Node，方便回溯

boolean deleteNode(int index){ //删除第index 个结点
        if (index < 1 || index > this.length)
            return false;//访问越界


        int i = 0;
        Node head = this; //定义一个头指针来遍历
        while (head != null && i < index - 1){
            head = head.next;
            i++;
        }
        head.next = head.next.next; //删除元素
        this.length --;

        return true;
    }

查找一个元素

//在链表中查找一个数据元素  这里通过java 重载实现默认参数
    int locaList(ElemType loacl){
        return this.locaList(loacl, null);
    }
    int locaList(ElemType local, ElemType value){//查找一元素是否存在不存在返回其下标 没有返回
        Node head = this.next;//创建头指针用于访问
        int index = 0;  //返回的下标

//        核心
        while (head != null) {
            if (local.value == head.data.value){//数据元素相等
                value.value = head.data.value;
                return index;
        }
            head = head.next;
            index ++;
        }
        return -1;   //未找到
    }

2.2静态链表

数组实现的链表 statickLinkList

结点类:

public class Node {//结点
    //    下标为0 是一个备用链表 模拟内存中的剩余空间
//    下标MaxSIze - 1 存储当前链表中第一个数据元素 充当头结点的功能 为0 时标识链表为空
    ElemType arrNode;//数据域
    int cur;  //游标  相当于单链表中的next

    public Node(){}

    public Node(int i){  //重载实现 参数默认值
        this.arrNode = new ElemType(i);
    }
}

数据域:

public class ElemType {//数据域

    int data;

    //构造
    public ElemType(){
        this.data = 0;
    }
    public ElemType(int vlaue) {
        this.data = vlaue;
    }
}

init初始化

public static Node[] initStaticLinkList(Node[] sl, int length){
       for (int i = 0; i < length - 1; i++) {   //创建备用链表
           //创建数据域引用
           sl[i] = new Node(i + 0);// 分配内存地址
           sl[i].cur = i + 1;
       }

       sl[length - 2].cur = -1; //-1表示 线性表已经满了
       sl[length - 1] = new Node();
       sl[length - 1].cur = 0;  // 头结点 游标为0表示空
       System.out.println("初始化成功");
       return sl;
   }

insertStaticLinkList插入

public boolean insertStaticLinkList(Node[] sl ,int index, ElemType insert){//插入一个数据元素
        int i = malloc(sl);//获取空结点的下标
        if (i == -1)    //内存不足分配失败
            return false;

        int head = sl.length - 1;
        int count = 0;
        while (count < index && sl[head].cur != 0){
            head = sl[head].cur;
            count ++;
        }
        sl[0].cur = sl[i].cur;  //新结点从备用结点中删除

        //插入新的结点
        sl[i].cur = sl[head].cur;
        sl[head].cur = i;


        return true;
    }

delectNode删除

public boolean deletNode(Node[] ls, int index){
        if (isEmpty(ls))
            return false;   //空表

        int head = ls.length - 1;   //头结点
        int count = 0;

        while (ls[head].cur != 0 && count < index){
            head = ls[head].cur;    //下一个结点
            count ++;
        }
        if (ls[head].cur <= 0)  //添加这句是为了 index 为负值
            return false;

        //删除前记录其下标
        int next = ls[head].cur;
        ls[head].cur = ls[ls[head].cur].cur;    //将删除前结点 指向删除后一个结点

        //将空闲的这个结点添加到 备用链表（可用内存中）
        ls[next].cur = ls[0].cur;
        ls[0].cur = next;
        return true;
    }

localNode 查找

int localElem(Node[] sl, ElemType getElem){//查找找到getElem 这个数据元素
        if (this.isEmpty(sl)) {
            System.out.println("链表为空");
            return 0;   //为空链表 结束
        }
        int count = 0;  // 返回的数据元素位置

        int head = sl.length - 1;   //头指针
        while (sl[head].cur != 0){  //游标指向0为空值
            head = sl[head].cur;    //游标（next） 指向下一个元
            if (sl[head].arrNode.data == getElem.data)
                return count + 1;
            count ++;
        }

        return 0;
    }

getLength() & destoryList() & isEmpty() 基本方法

public int getLength(Node[] sl){
        return sl.length;
    }
public void destroyStaticLinkList(Node[] sl){//这里我直接调用初始化函数 销毁
        this.initStaticLinkList(sl, 20);
    }

public boolean isEmpty(Node[] sl){
        if (sl[sl.length - 1].cur == 0)
            return true;
        return false;
    }

2.2双链表

Node (单链表)

数据域: 自定义数据类型

指针域:
Ptr: next
Ptr2: prior 

数据域：

package Demo1;

// 双向链表
public class DuLinkList
{
    ElemType data;// 数据域

    DuLinkList prior;//前驱
    DuLinkList next;//后继

    public DuLinkList(){
        this.data = new ElemType(0);
    }
    public DuLinkList(ElemType data) {
        this.data = data;
    }

    //operation


}

class ElemType{// 数据域

    int value;

    public ElemType(){}
    public ElemType(int value){
        this.value = value;
    }
}

基本方法实现：

getLength
isEmpty
destroyList
inser, delect, local,getElem

package Demo1;

public class Test {
    public static void main(String[] args) {
        DuLinkList head;
        head = initDuLinkList();
        System.out.println("链表初始化成功");

        for (int i = 0; i < 10; i++) {
            insertDuLinkList(head, i + 1,new ElemType(i + 1));
        }

        System.out.println("当前链表长度" + getLength(head));
        show(head);

        System.out.println("在链表最后插入一个数据");
        insertDuLinkList(head, 11,new ElemType(99));


        System.out.println("当前链表长度" + getLength(head));
        show(head);

        System.out.println("在链表中查找99这个元素");
        int serch = locaNode(head, new ElemType(99));
        if (serch > 0)
            System.out.println("在第"+serch+"个位置找到该元素");
        else
            System.out.println("No find");

        System.out.println("获得第11个元素值");
        ElemType data = getElem(head, 11);
        if (data != null)
            System.out.println("get value = " + data.value);

        System.out.println("删除第11个元素");
        delectNode(head, 11);
        System.out.println("删除后的链表");

        System.out.println("当前链表长度" + getLength(head));
        show(head);

        destoryDuLinkList(head);
        if(isEmpty(head))
            System.out.println("当前链表为空");
    }

    public static DuLinkList initDuLinkList(){
        DuLinkList lists = new DuLinkList();    //初始化头指针
        lists.next = lists;
        lists.prior = lists;

        return lists;
    }

    public static boolean isEmpty(DuLinkList head){
        if (head.next == head)
            return true;
        return false;
    }

    public static int getLength(DuLinkList list){// 获取长度
        if (!isEmpty(list)){
            DuLinkList head = list; //头指针
            int length = 0;  //length

            while (head.next != list){
                head = head.next;    // 下一个结点
                length++;
            }
            return length;
        }else
            return 0;
    }

    public static boolean insertDuLinkList(DuLinkList list, int index, ElemType data){
        if (index <= 0)
            return false;

        DuLinkList head = list; //头指针

        int count = 0;
        while (count < index - 1 && head.next != list){
            head = head.next;
            count++;
        }
        // 默认 输入长度超过实际长度 插入到末尾
        DuLinkList New = new DuLinkList(data);
        New.prior = head;   //新结点前驱
        New.next = head.next;   //新结点 后继
        head.next.prior = New;  //后继的prior 指向新结点
        head.next = New;    //前驱的next 指向新结点

        return true;
    }

    public static void show(DuLinkList list){
        if (isEmpty(list))
            return;
        DuLinkList head = list; //头指针
        int count = 0;
        while (head.next != list){
            head = head.next;
            count ++;
            System.out.print("第"+count+"个元素值:");
            System.out.print(head.data.value + "  ");
        }
        System.out.println();
    }
    public static boolean delectNode(DuLinkList list, int index){
        return delectNode(list, index, null);
    }
    public static boolean delectNode(DuLinkList list, int index, ElemType get_elem){
        if (getLength(list) < index || index < 1) {
            System.out.println("下标不合法");
            return false;
        }

        //核心
        DuLinkList head = list;
        int count = 0;
        while (head.next != list && count < index -1){
            head = head.next;
            count++;
        }

        //删除元素十分简单 如果是C 这里需要定义一个指向删除结点的指针 并释放内存
        head.next = head.next.next;
        head.next.prior = head;

        return true;
    }

    public static int locaNode(DuLinkList list,ElemType serch_elem){
        return locaNode(list, serch_elem,null);
    }
    public static int locaNode(DuLinkList list, ElemType serch_elem,ElemType get_data){
        if (isEmpty(list)){
            System.out.println("当前链表为空");
            return -1;
        }

        DuLinkList head = list;
        int ret = 0;
        while (head.next != list){
            head = head.next;
            ret++;
            if (head.data.value == serch_elem.value )
                return  ret;
        }
        return 0;
    }

    public static ElemType getElem(DuLinkList list, int index){
        if (index > getLength(list) || index < 1) {
            System.out.println("下标越界");
            return null;
        }
        DuLinkList head = list;
        int count = 0;

        while(head.next != list && count <= index){
            count++;
            head = head.next;
        }
        if (head == list)
            return null;
        else
            return head.data;
    }

    public static boolean destoryDuLinkList(DuLinkList list){
        //销毁链表 这里模仿了c的流程
        DuLinkList head = list.next;
        DuLinkList temp = head;

        while (head != list){//伪释放内存 temp等于头指针时
            temp = head.next;   // 记录下一个结点地址
            head = null;   //这里相当于free(Node)
            head = temp;    // 释放头指针指向下一个结点
        }

        //最后初始化一下头指针  其实只需调用初始化函数就可以完成 这样做接近底层逻辑
        list.next = list;
        list.prior = list;
        return  true;
    }
}

2.3循环链表

在线性表基础上 next -> null 改为指向头结点

重构方法中null 结束遍历的循环改为头结点

优点:

不需额外再开设空间
优化了一些操作

以下实现两个链表组合

//循环链表 实现两个链表拼接 
public static void listConnet(LoopNode list, LoopNode list2){
    if (isEmpty(list) || isEmpty(list2))  
        return;
    LoopNode head = list;
    // 遍历到链表最后 如果有尾指针 传入尾指针参数即可
    while (head.next != list){
        head = head.next;
    }
    // ---！！！ 链表1 的末端结点1 是指向 list2第一个元素而不是头结点
    head.next = list2.next;
    head = list2;
    // 遍历链表二 将末端元素next 指向链表1的头结点
    while (head.next != list2)
        head = head.next;
    head.next = list;   //末端结点指向链表1头指针
    
}

总结

两种结构是互补的，没有哪一种存储方式最优，相对不同问题使用不同结构才是正解

链式存储结构：

优点：
- 不定长扩容非常方便
- 插入删除操作效率高O(1）
缺点：
- 失去了顺序结构的随机读取O(n)
- 有一部分指针域空间开销

顺序存储结构:

优点
- 随机读取
- 存储密度大（连续存储）
缺点
- 占用内存大
- 定长扩容很麻烦
- 插入删除操作O(n)

四、栈Stack

栈

栈是一种线性表，线性表特性他都有

First in Last out 先进后出的线性表
插入操作都在top进行
由于插入删除都在栈顶，所以顺序存储和链式存储结构无差异

顺序存储结构实现

package Demo1;

public class StackDataType {
    //数据域
    int value;

    public StackDataType() {
        this.value = 0;
    }
    public StackDataType(int value) {
        this.value = value;
    }
}

Operation:

package Demo1;

public class Operation {
    private static Demo1.Stack s;

    //初始化栈
    public static boolean initStack(Stack s){
        //这里原本有开辟数组的 被添加到构造方法里
        //栈顶 为0 空栈
        s.top = 0;
        return true;
    }

    //压栈
    public static boolean push(Stack s, StackDataType data){
        //插入操作
        if (s.top == s.data.length){
            System.out.println("栈溢出");
            return false;
        }
        s.data[s.top] = data;
        s.top++;
        return  true;
    }

    //
    public static boolean isEmpty(Stack s){
        if (s.top == 0)
            return true;
        else
            return false;
    }
    //弹出

    public static StackDataType pop(Stack s){
        s.top--;
        return s.data[s.top];
    }

    public static void  show_stack(Stack s){
        System.out.println("栈：");
        for (int i = 0; i < s.data.length; i++) {
            if (i != s.top)
                System.out.print(" --> ");
            else {
                System.out.print(" Top ");
                break;
            }
        }
        System.out.println("");
        for (int i = 0; i < s.top; i++) {
            System.out.printf("%5s", s.data[i].value);
        }
    }
}

双向栈

相比栈多一个栈顶，一个栈顶位于0，另一头栈顶位于MAXSIZE +1
用数组更好实现
判断空栈和满栈
- 空 Top1 = 0 && Top2 = MAXSIZE -1
- 满栈Top1 + 1 = Top2

基本操作

package Demo1;

public class Operation {
    private static Demo1.Stack s;

    //初始化栈
    public static boolean initStack(Stack s){
        //这里原本有开辟数组的 被添加到构造方法里
        //栈顶 为0 空栈
        s.top1 = 0;
        s.top2 = s.data.length - 1;
        return true;
    }

    //压栈
    public static boolean push(Stack s, StackDataType data, int stack_number){
        //判断栈是否满
        if (s.top1 + 1 == s.top2){
            System.out.println("栈溢出");
            return false;
        }

        if (stack_number == 1){
            s.data[s.top1] = data;
            s.top1++;
            return  true;
        }else{
            s.data[s.top2] = data;
            s.top2--;
            return true;
        }
    }

    //
    public static boolean isEmpty(Stack s){
        if (s.top1 == 0 && s.top2 == s.data.length - 1)
            return true;
        else
            return false;
    }
    //弹出

    public static StackDataType pop(Stack s, int stack_number){
       if (isEmpty(s))
           return null;
       if (stack_number == 1){
           s.top1 --;
           return s.data[s.top1+1];
       }else {
           s.top2--;
           return s.data[s.top2-1];
       }
    }

    public static void  show_stack(Stack s){
        System.out.println("栈：");
        for (int i = 0; i < s.data.length; i++) {
            if (i != s.top1)
                System.out.print(" --> ");
            else {
                System.out.print(" Top ");
                break;
            }
        }
        for (int i = s.top2; i < s.data.length; i++) {
            if (i != s.top2)
                System.out.print(" <-- ");
            else {
                System.out.print(" Top2 ");
            }
        }

        //栈1
        System.out.println("");
        for (int i = 0; i < s.top1; i++) {
            System.out.printf("%5s", s.data[i].value);
        }

        //栈二

        System.out.print("         ");
        for (int i = s.top2 + 1; i < s.data.length; i++) {
            System.out.printf("%5s", s.data[i].value);
        }
    }
}

package Demo1;

public class Test {
    public static void main(String[] args) {
        Stack stack = new Stack();
        Operation.initStack(stack);

        //向第一个栈插入元素
        for (int i = 0; i < 5; i++) {
            Operation.push(stack, new StackDataType(i + 1), 1);
        }
        for (int i = 0; i < 5; i++) {
            Operation.push(stack, new StackDataType(i + 1), 2);
        }
        Operation.push(stack, new StackDataType(22), 2);

        Operation.show_stack(stack);
    }
}

链表节点定义

package Demo1;

public class Stack {
    StackDataType[] data;
    //两个栈顶
    //
    int top1;
    int top2;
    public  Stack(){
        this.data = new StackDataType[20];
        this.top1 = -1; //栈不存在-1
    }
    public Stack(int n) {
        this.data = new StackDataType[n];
    }


}

package Demo1;

public class StackDataType {
    //数据域
    int value;

    public StackDataType() {
        this.value = 0;
    }
    public StackDataType(int value) {
        this.value = value;
    }
}

队列

和栈对立的一种线性结构
First in First out 先进先出
插入表尾，出表表头
同样有顺序结构和链式结构

数组实现：

难点用数组实现队列的反复重用，链式存储结构就没这么复杂

空队列判断rear == front
满队列(rear + 1 ) % MAXSIZE == front

五、字符串匹配String

朴素字符串匹配

母串abeabcabce 子串为abcabce

最坏的情况下O(n-m)*n

分析一下我们就能得出每次匹配母串字符需要一个一个的对比其中不乏有重复的对比（母串每次与子串匹配如果不相同会回溯至开头下一个位置而子串是回溯到0）下面的各种算法就是裁剪掉不必要的回溯

public class _String {// 字符串匹配
    //朴素的字符串匹配


    public void comp(char[] str, char[] str2){
        int strlength = str.length;
        int str2lengh = str2.length;

        int i = 0;
        int j = 0;

        while(i < strlength){
            // 记录前一个i 值方便回溯
            j = i;
            System.out.print("运行第");
            System.out.println(i);

            //匹配子串str2 字符是否相等
            int k = 0;
            for (; k < str2lengh;) {
                if (str[i] == str2[k])
                    k++;
                else
                    break;
            }
            if (k == str2lengh) {
                System.out.println("字符串匹配");
                return;
            }
            //回溯
            i = j + 1;
        }
        return;
    }


    public static void main(String[] args) {

        char[] ary = {
                'a','a','a','a','a','a','a','a','a','a','a'
        };
        char[] str = { 'a', 'b' };
        _String s = new _String();

        s.comp(ary, str);
    }
}

KMP 字符串匹配

相对于朴素的字符串匹配，KMP算法会优化不必要的回溯

依据子串的字符串重复率构建一个next数组 (前缀和后缀的相似程度) 优化匹配串不必要的回溯

求abcabf 的next数组 -> 011123

推导next数组第一步

在网上看到不少实现数组下标都是从1开始的，我习惯从0开始

public int[] get_next(char[] str){
        //next数组
        int[] next = new int[str.length];

        int i = 1;  //后缀字符
        int j = 0;  //前缀字符

        next[0] = -1;  //字符串第一个位置 必为0  方便访问下标所以-1

        while  (i < str.length){
            if(str[j] == str[i] || j-1 == -1)  //j 前缀      i 后缀
            {
                j ++;
                i ++;
                next[i - 1] = j - 1; //更新next 数组
            }else{
                j = next[j];
            }

        }
        return next;


    }

i 表示子串后缀字符下标 j表示前缀字符下标

思路：

后缀位置不断后移判断是否与前缀字符相同相同就一起地址比对下一个位置，不相同就回溯j值一直不相同就回溯到0 继续匹配

abcdef 得到next 数组为011111 next数组中的值就是回溯的依据（这里我改成了-10000）

KMP 算法

有了next 这个数组我们就可以使用这个数组来帮助我们减少不必要的回溯

//在字符串中查找子串 并返回下标
    public int index_Kpm(char[] str, char[] str2, int pos){
        int i;  //遍历母串下标
        int j;  //子串下标

        i = pos ; // pos为开始下标
        j = -1;  //子串下标 0开始 这里-1 原因是因为next 习惯下标为0 开始 所以 第一个元素给定-1
        int[] next = this.get_next(str2); //获取我们的next数组
        while(i < str.length && str2.length > j){//满足i j下标都在母串 和子串区间 时 循环对比
            if (j == -1 || str[i] == str2[j]){//相比朴素算法就多 j == -1 的判断 ，这很重要
                i++;
                j++;
            }else
                j = next[j]; //回溯
        }
        if (j == str2.length)
            return i - str2.length; //返回子串在母串开始下标
        else
            return -1;
    }

KMP优化

母串aaaabcd 匹配子串aaaac

aaaac next 数组结果为01231

当i = 4 j = 4 时字符 b ！= a 但是字符串中会不停对比回溯直到j = 0 从头开始匹配，其实这部分回溯我们也可以裁剪掉只需在求next数组时添加一个如果后缀串等于前缀字符我们就把偏移位置和前缀的偏移位置一样如果不相等正常执行next 数组求值即可

只需要更改next 数组让前缀字符等于后缀字符时母串[i] == 子串[j] 时 next 相应位置的next[i] = next[j]即可

next -> 01234 优化后结果 next -> 01114

public int[] get_nextval(char[] str){
    //next数组
    int[] next = new int[str.length];

    int i = 0;  //后缀字符
    int j = -1;  //前缀字符

    next[0] = -1;  //字符串第一个位置 必为0  方便访问下标所以-1

    while  (i < str.length - 1){
        if( j == -1 || str[j] == str[i])  //j 前缀      i 后缀
        {
            j ++;
            i ++;
            if (str[j] == str[i])
                next[i] = next[j];
            else
                next[i] = j; //更新next 数组
        }else{
            j = next[j];
        }

    }
    return next;
}

字符串匹配没有图是真的难受后期把图补上会更好理解一点

总结

KMP算法优化了字符串匹配的一些特殊情况，适用于子串中有很高重复率的字符才能体现KMP算法优势，否则效率并没有比传统字符串匹配高多少

六、树Tree

概念

学到树形结构了，先看看这又臭又长的定义

Tree 是n≥0有限集合， n=0为空，非空数只有一个根节点，同深度的子树之间没有任何关系

度（Degree）：

度等于一个结点的拥有的子树或者孩子

leaf 叶结点或者叫终端结点度为0

非终端结点或称为者分支结点，除根结点之外，分支结点也称为内部结点。

数的度是结点度的最大值

结点关系

线性结构是一对一，树形结构是一对多，同一个双亲结点的孩子互称兄弟，任意子树的根节点是所有结点的祖先

结点层次Level

根为第一层往下递增。

双亲在同一层，互称堂兄弟。

数中结点最大深度为该树的深度

顺序

有序树：每个结点有严格的顺序之分，左子树右子树不能互换，否则就是一个无序树

存储结构

两者都能采用但是对于顺序结构操作有点不同

顺序存储结构：对于数顺序结构并不能直接表现树存储关系，简单的顺序存储不能满足需要

链式存储结构: 同顺序存储结构一样