数据结构与算法(一)

当前位置:

首页 > 编程开发 > Java教程 >

数据结构与算法(一)

在计算机科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。主要分为两大类：线性结构和非线性结构。程序 = 数据结构 + 算法。

常见的数据结构

栈（Stack）：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。
队列（Queue）：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
数组（Array）：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
链表（Linked List）：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
树（Tree）：树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。
图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
堆（Heap）：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
散列表（Hash table）：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

常用算法

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
插入：往数据结构中增加新的节点。
删除：把指定的结点从数据结构中去掉。
更新：改变指定节点的一个或多个字段的值。
排序：把节点按某种指定的顺序重新排列。例如递增或递减。

稀疏数组和队列

稀疏数组

稀疏数组引出

编写五子棋程序中的存盘退出和续上盘功能

我们首先想到的肯定是一个二维数组记录棋盘的信息，使用1表示黑棋，2表示蓝棋，这样确实能够解决问题，但是会出现储存了大量没有意义的数据0，浪费我们的存储空间，有没有既能够解决问题又能节省空间的方法呢？稀疏数组就能够很好的解决这个问题。

稀疏数组基本概念

当我们定义一个数组的时候，其中大部分数据是0或者同一个数据的时候，就可以使用稀疏数组来保存数据，将该数组转换成稀疏数据保存。

稀疏数组的第一行记录原始数组的行，列，多少个不同的值
从第2行开始，每一行记录一个不同值的行，列，数据

实际应用

将上面的棋盘数据保存在稀疏数组中，并能够从稀疏数组中读取数据恢复棋盘数据。

复制代码

public class Sparse1 {
    public static void main(String[] args) {
        //二维数组转换成稀疏数组
        //约定使用1表示黑棋，2表示蓝棋，0表示该位置没有棋子
        int[][] array1 = new int[11][11];
        //保存黑蓝棋数据
        array1[1][2] = 1;
        array1[2][3] = 2;
        array1[3][4] = 1;
        array1[4][4] = 2;
        //数组原始数组
        System.out.println("原始数组:");
        print(array1);
        //将原始数组转换成稀疏数组
        int count = 0;//记录原始数组中非零数据个数
        for(int[] a : array1){
            for(int b : a){
                if(b != 0){
                    count++;
                }
            }
        }
        //创建稀疏数组
        int[][] sparse1 = new int[count+1][3];
        //记录原始数组的行列非零值
        sparse1[0][0] = 11;
        sparse1[0][1] = 11;
        sparse1[0][2] = count;
        //记录每个非零的数据
        count = 0;
        for(int i = 0; i < array1.length; i++){
            for(int j = 0; j < array1[i].length; j++){
                if(array1[i][j] != 0){
                    sparse1[++count][0] = i;
                    sparse1[count][1] = j;
                    sparse1[count][2] = array1[i][j];
                }
            }
        }
        System.out.println("稀疏数组为:");
        print(sparse1);

        //稀疏数组转成成原始数组
        //创建原始数组
        int[][] array2 = new int[sparse1[0][0]][sparse1[0][1]];
        for(int i = 1; i < sparse1.length;i++){
            array2[sparse1[i][0]][sparse1[i][1]] = sparse1[i][2];
        }
        //输出原始数组
        System.out.println("稀疏数组转换成原始数组");
        print(array2);
    }
    private static void print(int[][] arr){
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr[i].length; j++){
                System.out.printf("%d\t",arr[i][j]);
            }
            System.out.println();
        }
    }
}

后续思考：我们的数据一般存储在磁盘中，我们需要将稀疏数组保存到磁盘中，或者从磁盘中读取稀疏数组的数据，这就要通过我们的IO来完成。

复制代码

//将稀疏数组记录到磁盘位置为E:\\map.data
ObjectOutputStream oos = null;
try {
    oos = new ObjectOutputStream(new FileOutputStream("E:\\map.data"));
    oos.writeObject(sparse1);
    System.out.println("稀疏数组已经存储到磁盘");
} catch (IOException e) {
    e.printStackTrace();
} finally {
    if(oos != null){
        try {
            oos.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
//从磁盘读取稀疏数据，并恢复数据
//从磁盘读取稀疏数据数据
ObjectInputStream ois = null;
int[][] sparse11 = null;
try {
    ois = new ObjectInputStream(new FileInputStream("E:\\map.data"));
    Object o = ois.readObject();
    sparse1 = (int[][]) o;
    System.out.println("稀疏数组数据读取完成");

} catch (IOException | ClassNotFoundException e) {
    e.printStackTrace();
} finally {
    if(ois != null){
        try {
            ois.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

队列

队列的引出

银行业务排队叫号

如果银行柜台个数有限，人数很多的时候，就需要排队等待服务，这种队列是一种先到先服务的特点，也就是先进先出。

基本介绍

队列是一个有序列表，可以使用数组和链表两种方式来实现，特点：先进先出

front：队首，队列头部
rear：队尾，队列尾部
左 1 图：队列初始化的两个变量值
中图：存入数据后，的首尾变化
右图：取数据时，从队首取，队首的变量指向也在发生变化

数组实现队列

队列本身是 有序列表，使用数组结构来存储队列的数据，则如前面基本介绍中的示意图一样。

声明 4 个变量：

arr：用来存储数据的数组
maxSize：该队列的最大容量
front：队首下标，随着数据输出而改变
rear：队尾下标，随着数据输入而改变

队列中常用操作分析，以 add，把数据存入队列为例，思路分析：

将尾指针往后移：rear + 1，前提是当 front == rear 时，队列是空的
若尾指针 rear < maxSize -1：
- 则将数据存入 rear 所指的数组元素中，
- 否则无法存入数据。rear = maxSize -1 表示队列满了

复制代码

class ArrayQueue{
    private int maxSize;//队列的最大长度
    private int front;//指向队列头部的前一个位置
    private int rear;//指向队列的尾部的元素位置
    private int[] arr;//保存数据

    //初始化队列
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        front = -1;
        rear = -1;
        arr = new int[maxSize];
    }

    //判断是否为空
    private boolean isEmpty(){
        return rear == front;
    }

    //判断是否为满
    private boolean isFull(){
        return rear == maxSize-1;
    }
    //添加数据
    public void add(int num){
        if(isFull()){
            System.out.println("队列已满，不能添加数据");
            return;
        }
        arr[++rear] = num;
    }
    //取出数据
    public int get(){
        if(isEmpty()){
            throw new RuntimeException("队列没有数据，取出数据失败");
        }
        return arr[++front];
    }
    //显示队列
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列没有数据");
            return;
        }
        for(int i = 0; i < arr.length; i++){
            System.out.printf("队列数据arr[%d] = %d\n",i,arr[i]);
        }
    }
    //查看队列头部数据
    public int head(){
        if(isEmpty()){
            throw new RuntimeException("队列没有数据，取出数据失败");
        }
        return arr[front + 1];
    }
}

//测试
ArrayQueue arrayQueue = new ArrayQueue(3);
char order = ' ';
boolean flag = true;
Scanner scanner = new Scanner(System.in);

while (flag){
    System.out.println("s(显示队列数据)");
    System.out.println("a(向队列添加数据)");
    System.out.println("g(向队列取出数据)");
    System.out.println("h(查看队列头部数据)");
    System.out.println("e(退出)");
    System.out.println("请输入一个指令:");
    order = scanner.next().charAt(0);
    int num;
    switch (order){
        case 's':
            arrayQueue.showQueue();
            break;
        case 'a':
            System.out.println("请输入一个数据:");
            num = scanner.nextInt();
            arrayQueue.add(num);
            break;
        case 'g':
            try {
                num = arrayQueue.get();
                System.out.println(num);
            } catch (Exception e) {
                System.out.println(e.getMessage());;
            }
            break;
        case 'h':
            try {
                num = arrayQueue.head();
                System.out.println(num);
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
            break;
        case 'e':
            flag = false;
            break;
        default:
            break;
    }

}
System.out.println("程序退出");

目前实现了一个 一次性的队列（不能复用），因为可以往队列中添加数据，基本功能也是可以的，当队列满之后，再添加就加不进去了，获取数据也不能清空原队列中的数据。

优化方向：使用算法将这个数组改进成一个环形队列。

front：含义调整

表示：队列的第一个元素，也就是说 arr[front] 就是队列的第一个元素

初始值：0
rear：含义调整

表示：队列的最后一个元素的下一个位置

初始值：0
队列满计算公式：（rear+1) % maxSize == front
队列为空的条件: front == rear
队列中有效元素的个数计算公式：(rear + maxSize - front) % maxSize

复制代码

class CircleQueue{
    private int maxSize;//实现循环队列数组的容量
    private int front;//指向队列的第一个元素的位置
    private int rear;//指向队列的最后一个元素的后一个位置
    private int[] arr;

    public CircleQueue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

    //判断队列是否为空
    private boolean isEmpty(){
        return front == rear;
    }

    //判断队列是否满
    private boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    //添加元素
    public void add(int num){
        if(isFull()){
            System.out.println("队列已满，添加失败");
            return;
        }
        arr[rear] = num;
        //将指针后移
        rear = (rear + 1) % maxSize;
    }

    //获取元素
    public int get(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，获取失败");
        }
        int temp = arr[front];
        //指针后移
        front = (front + 1) % maxSize;
        return temp;
    }

    //获取队列中有效元素的个数
    private int size(){
        return (rear + maxSize - front) % maxSize;
    }

    //遍历队列元素
    public void showQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，遍历失败");
        }
        for(int i = front; i < front + size(); i++){
            //i可能越界，取模保证在循环队列中
            System.out.printf("arr[%d] = %d\n",i%maxSize,arr[i%maxSize]);
        }
    }
    //获取队列头节点数据
    public int head(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，获取头节点数据失败");
        }
        return arr[front];
    }

}


//测试代码
CircleQueue arrayQueue = new CircleQueue(4);
char order = ' ';
boolean flag = true;
Scanner scanner = new Scanner(System.in);

while (flag){
    System.out.println("s(显示队列数据)");
    System.out.println("a(向队列添加数据)");
    System.out.println("g(向队列取出数据)");
    System.out.println("h(查看队列头部数据)");
    System.out.println("e(退出)");
    System.out.println("请输入一个指令:");
    order = scanner.next().charAt(0);
    int num;
    switch (order){
        case 's':
            try {
                arrayQueue.showQueue();
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
            break;
        case 'a':
            System.out.println("请输入一个数据:");
            num = scanner.nextInt();
            arrayQueue.add(num);
            break;
        case 'g':
            try {
                num = arrayQueue.get();
                System.out.println(num);
            } catch (Exception e) {
                System.out.println(e.getMessage());;
            }
            break;
        case 'h':
            try {
                num = arrayQueue.head();
                System.out.println(num);
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
            break;
        case 'e':
            flag = false;
            break;
        default:
            break;
    }

}
System.out.println("程序退出");

链表

链表是有序的列表，但是在内存中存储图下图所示

链表是以节点的方式来存储，是 链式存储
每个节点包含 data 域、next 域，指向下一个节点
链表的各个节点 不一定是连续存储，如上图所示
链表还分：带头节点、不带头节点，根据实际需求来确定

单链表

单链表（带头节点）逻辑结构 示意图如下，当下一个节点为空的时候，该链表就结束了

单链表的应用

考虑这样一个场景：使用带 head 头的 单向链表 实现水浒英雄排行榜管理

完成对英雄人物的 增删改查 操作
第一种方法：在添加英雄时，直接添加到链表的尾部
第二种方法：在添加英雄时，根据排名将英雄插入到指定位置

如果有这个排名，则添加失败，并给出提示

单链表的无排序实现

复制代码

//定义节点
class HeroNode{
    public int no;//英雄编号
    public String name;//英雄名称
    public String nickName;//英雄花名
    public HeroNode next;//当前节点的下一个节点

    public HeroNode(int no,String name,String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }
    //方便遍历显示信息
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
//定义单链表
class SingleLinkedList{
    //头节点用于主要用于记录初始位置，方便遍历
    private HeroNode head;

    public SingleLinkedList(){
        head = new HeroNode(0,"","");//初始化头节点
    }

    //添加元素
    public void add(HeroNode h){
        //遍历找到最后一个元素，借助辅助变量，头节点不能改变
        HeroNode temp = head;
        while(true){
            //循环遍历
            if(temp.next == null){
                break;
            }
            //指针后移
            temp = temp.next;
        }
        //插入元素
        temp.next = h;
    }

    //显示所有元素
    public void list(){
        //借助辅助变量遍历
        HeroNode temp = head.next;
        while(true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}
//测试代码
//创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

//创建单链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);

singleLinkedList.list();

单链表的排序实现

添加思路如下：

首先找到新添加节点的位置，通过辅助变量 temp，然后循环遍历查找
新的节点.next = temp.next
将 temp.next = 新的节点

简单一点就是：通过遍历找到要插入的位置，然后改变 next 的指向到。

复制代码

//添加有序添加
public void addOrder(HeroNode h){
    //遍历找到最后一个元素，借助辅助变量，头节点不能改变
    HeroNode temp = head;
    boolean flag = false;//知否是重复添加，默认为false
    while(true){
        if(temp.next == null){
            break;//链表遍历结束
        }
        //如果下一个节点的编号大于当前元素就退出
        if(temp.next.no > h.no){
            break;
        }else if(temp.next.no == h.no){//查看是否相等
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if(flag){
        System.out.printf("添加的元素为重复添加，编号为%d的节点添加失败",h.no);
        return;
    }
    //添加元素
    h.next = temp.next;
    temp.next = h;

}

单链表更新

复制代码

//修改指定节点
public void update(HeroNode h){
    //判断链表是否为空，为空退出
    if(head.next == null){
        return;
    }
    HeroNode temp = head;
    boolean flag = false;//用来记录是否找到要修改的编号
    while(true){
        if(temp.next == null){
            break;//已经遍历到链表结尾，退出
        }
        if(temp.no == h.no){
            flag = true;
            break;
        }
        temp = temp.next;
    }

    if(flag){//找到
        //更新数据
        temp.name = h.name;
        temp.nickName = h.nickName;
    }else{//没有找到
        //提示信息
        System.out.printf("修改失败，没有找到%d编号",h.no);
    }
}

单链表的指定节点删除

如上图所示，思路如下：

先找到需要删除的这个节点的 前一个节点 temp

为什么要找到前一个？因为是单向链表，找目标节点就无法完成删除了。
temp.next = temp.next.next
被删除的节点，如果没有其他的引用的话，会被垃圾回收机制回收

复制代码

//删除指定节点
public void remove(int no){
    if(head.next == null){
        return;
    }
    HeroNode temp = head;
    boolean flag = false;//用于记录是否找到要删除的节点
    while(true){
        if(temp.next == null){
            break;//遍历到链表结尾
        }
        if(temp.next.no == no){
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if(flag){
        //找到，删除对应元素
        temp.next = temp.next.next;
    }else{
        //没有找到
        System.out.printf("删除失败，没有找到%d节点",no);
    }
}

单链表面试题

求单链表有效节点个数

复制代码

//返回头节点
public HeroNode getHead(){
    return head;
}

//求单链表有效节点数
public static int getSize(HeroNode head){
    if(head.next == null){
        //单链表为空
        return 0;
    }
    HeroNode temp = head.next;
    int length = 0;
    while(true){
        length++;
        if(temp.next == null){
            break;
        }
        temp = temp.next;
    }
    return length;
}

查找单链表中的倒数第 k 个结点

复制代码

//得到倒数第K个元素
public static HeroNode findLastIndexNode(HeroNode head,int k){
    if(head.next == null){
        return null;//单链表为空
    }
    HeroNode temp = head.next;
    //得到链表长度
    int size = getSize(head);
    //对index进行判断，范围是否合法
    if(k <= 0 || k > size){
        return null;
    }
    //开始遍历
    for(int i = 0; i < size - k; i++){
        temp = temp.next;
    }
    return temp;

}

单链表的反转

思路：

定义一个新的 reverseHead 节点
从原链表中依次取出节点，并 始终添加到 reverseHead 的第一个节点
将原 head 节点的 next 指向 reverseHead.next

如下图所示：

复制代码

//单链表反转
public static void reverseList(HeroNode head){
    /*
        * 先新建一个头节点，指向为null
        * 对原单链表进行从头到尾遍历，一个一个取出节点，新建头节点指向取出的节点，
        * 并将原来的新建头节点指向改为该元素的后一个指向，然后将新建头节点指向该节点
        * */
    if(head.next == null || head.next.next == null){
        //当链表为空或者只有一个元素的时候不用反转
        return;
    }

    HeroNode cur = head.next;
    HeroNode next = null;//指向当前节点的下一个节点
    //新建一个头节点
    HeroNode rHead = new HeroNode(0,"","");
    while(cur != null){
        next = cur.next;
        cur.next = rHead.next;
        rHead.next = cur;
        cur = next;//指针后移
    }
    //遍历完成之后，建头节点从新指向新节点
    head.next = rHead.next;
}

从尾到头打印单链表

百度面试题，要求方式：

反向遍历
Stack 栈

思路：

反向遍历：使用前面翻转操作后，再打印

有一个问题：会破坏原链表的结构
Stack 栈：利用栈先进后出的特点

该数据结构后续讲解，这里做个简单的介绍

如上图所示：

入栈操作：数据往栈底压入
出栈操作：数据从栈顶弹出

将原链表遍历，以此将每个节点压入栈中，然后遍历栈打印即可

复制代码

//栈的简单演示
Stack<String> strings = new Stack<>();
strings.push("无涯子");
strings.push("姚娜");
strings.push("陈璐");
strings.push("彭娟");

while(strings.size() > 0){
    System.out.println(strings.pop());
}

复制代码

 //反向打印链表
public static void reversePrint(HeroNode head){
    if(head.next == null){
        return;//链表为空
    }
    HeroNode temp = head.next;
    Stack<HeroNode> stack = new Stack<HeroNode>();
    while(temp != null){
        stack.push(temp);//入栈
        temp = temp.next;//指针后移
    }
    //反向打印链表
    while(stack.size() > 0){
        System.out.println(stack.pop());
    }
}

合并两个有序的单链表

复制代码

//合并两个链表
public static HeroNode merge(HeroNode head1,HeroNode head2){
    if(head1.next == null || head2.next == null){
        return null;//有链表为空，合并失败
    }
    //新建一个头节点
    HeroNode nhead = new HeroNode(0, "", "");
    HeroNode temp1 = head1.next;//合并第一条链表的第一个元素
    HeroNode temp2 = head2.next;//合并第二条链表的第一个元素
    HeroNode temp = nhead;//指向新建的链表头节点

    //循环遍历
    while(temp1 != null && temp2 != null){
        //两个链表有一个遍历到结尾就退出循环
        if(temp1.no < temp2.no){
            temp.next = temp1;
            //链表1指针后移
            temp1 = temp1.next;
            //新建链表指针后移
            temp = temp.next;
        }else{

            temp.next = temp2;
            //链表2指针后移
            temp2 = temp2.next;
            //新建链表指针后移
            temp = temp.next;
        }
    }
    //有一天链为空，另一条链不知道是否为空
    if(temp1 == null){//假设第一条链表为空
        while(temp2 != null){
            //说明链表2还有元素可以添加
            temp.next = temp2;
            temp2 = temp2.next;
            temp = temp.next;
        }

    }else if(temp2 == null){//假设第二条链表为空
        while(temp1 != null){
            temp.next = temp1;
            temp1 = temp1.next;
            temp = temp.next;
        }
    }
    return nhead;
}

来源：https://www.cnblogs.com/wyzstudy/p/15388059.html

栏目列表