Java玩转《啊哈算法》之模拟链表

人应该支配习惯，而绝不是让习惯支配人。一个人要是不能改掉坏习惯，那么他就一文不值。

目录

  • 缘
  • 代码地址
  • 模拟链表
    • 创建
    • 遍历打印
    • 插入
    • 插入优化
  • 完整代码

缘

各位小伙伴们好呀！本人最近看了下《啊哈算法》，写的确实不错。

但稍显遗憾的是，书籍示例代码是c语言，而不是本人常用的Java。

那就弥补遗憾，说干就干，把这本书的示例语言用java写一遍， 顺带附上一些自己的理解！

今天这篇博客讲的是如何用数组来模拟链表。
在这里插入图片描述

来不及买纸质书但又想尽快感受算法魅力的童鞋也甭担心，电子版的下载链接已经放到下方了，可尽情下载。

链接：https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取码：jmgs

代码地址

本文代码已开源：

git clone https://gitee.com/guqueyue/my-blog-demo.git

请切换到gitee分支，

然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_2_StackAndChainTable即可！

模拟链表

在往期的博客中，我们用数组模拟了队列、栈，并且说了用链表也可以模拟队列、栈。

于是乎，我们还介绍了链表，但是链表指来指去的难免让人奇奇怪怪、晕头转向。

  1. Java玩转《啊哈算法》解密QQ号之队列
  2. Java玩转《啊哈算法》解密回文之栈
  3. Java玩转《啊哈算法》之链表

那么，这期博客，我们来讲一下如何用数组来模拟链表。

数组可以模拟队列、栈，链表也可以模拟队列、栈，数组也能模拟链表？没想到吧。

创建

那么，要怎么用数组来模拟链表呢？我们需要准备两个数组，一个数组存元素，一个数组用来存元素对应的下一个元素的位置。
在这里插入图片描述
如上图所示，我们data数组用于存放元素内容，right数组用以存放相同索引处对应data数组的下一个元素的索引。

如图我们头节点的元素为data[1]也就是2，下一个元素为data[right[1]]也就是3。

当然，我们这里可以做一些小小的改动：

  1. 为了不浪费空间，我们的存放数组的索引从0开始而不是从1开始。
  2. 链表尾节点的下一个位置的索引，我们用-1表示，而不是0。

首先，我们声明一下需要使用的两个数组、链表的长度以便于录入数据以及控制台输入的对象：

   // 用于控制台输入
    private static Scanner scanner = new Scanner(System.in);

    private static int[] data = new int[101]; // 元素数组
    private static int[] right = new int[101]; // 索引数组

    private static int n = 0; // 链表长度

然后，我们就可以愉快的编写创建链表的方法了：

   /**
     * @Description 创建链表
     * @return void
     **/
    private static void createChainTable() {

        System.out.print("请输入数字个数： ");
        n = scanner.nextInt();

        System.out.printf("请输入%d个数，中间用空格隔开，输入完回车： ", n);
        for (int i = 0; i < n; i++) {
            data[i] = scanner.nextInt();
        }

        // 初始化right数组
        for (int i = 0; i < n; i++) {

            right[i] = i == n-1 ? -1 : i+1;
        }
    }

遍历打印

有了创建链表的方法，当然要有一个打印的方法，不然怎么验证：

  /**
     * @Description 打印链表
     * @return void
     **/
    private static void printChainTable() {

        // 输出
        int t = 0;
        System.out.print("链表为：" + data[t]);
        while(right[t] != -1) {

            t = right[t]; // 获取下一个元素的索引
            System.out.print("->" + data[t]);
        }
        System.out.println();
    }

ok了，下面让我们来验证一下：

package com.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;

import java.util.Scanner;

/**
 * @Author: guqueyue
 * @Description: 用数组模拟链表
 * @Date: 2024/1/15
 **/
public class ChainTableTest2 {

    // 用于控制台输入
    private static Scanner scanner = new Scanner(System.in);

    private static int[] data = new int[101]; // 元素数组
    private static int[] right = new int[101]; // 索引数组

    private static int n = 0; // 链表长度

    public static void main(String[] args) {

        // 创建链表
        createChainTable();
        
        // 打印链表
        printChainTable();
    }

    /**
     * @Description 打印链表
     * @return void
     **/
    private static void printChainTable() {

        // 输出
        int t = 0;
        System.out.print("链表为：" + data[t]);
        while(right[t] != -1) {

            t = right[t]; // 获取下一个元素的索引
            System.out.print("->" + data[t]);
        }
        System.out.println();
    }

    /**
     * @Description 创建链表
     * @return void
     **/
    private static void createChainTable() {

        System.out.print("请输入数字个数： ");
        n = scanner.nextInt();

        System.out.printf("请输入%d个数，中间用空格隔开，输入完回车： ", n);
        for (int i = 0; i < n; i++) {
            data[i] = scanner.nextInt();
        }

        // 初始化right数组
        for (int i = 0; i < n; i++) {

            right[i] = i == n-1 ? -1 : i+1;
        }
    }
}

运行代码，控制台输入，可得：
在这里插入图片描述

插入

在这里插入图片描述

同样的，按照书上的逻辑，我们来写一个往链表中插入元素的方法：

   /**
     * @Description 插入链表
     * @return void
     **/
    private static void insertChainTable() {

        // 插入一个数
        int len = n;
        System.out.print("请输入插入的数：");
        data[len] = scanner.nextInt();

        // 按照链表顺序遍历 data 数组，找到比 num 大的数
        int t = 0;
        while (t != -1) {

            if (data[right[t]] > data[len]) { // 如果当前节点的下一个节点大于插入数，则插入

                right[len] = right[t]; // 插入的节点 指向当前节点的下一个节点
                right[t] = len; // 当前节点 指向插入的节点
                break;
            }

            t = right[t];
        }
    }

我们来验证一下(完整代码已开源，在本博客最后也可查看)：

   public static void main(String[] args) {

        // 创建链表
        createChainTable();

        // 打印链表
        printChainTable();

        // 往链表中插入数据
        insertChainTable();

        // 打印链表
        printChainTable();
    }

运行，得：

在这里插入图片描述
看起来好像没啥问题，但是同上期博客一样，存在着两个问题：

  1. 如果插入的节点值大小小于头节点，该节点会被插入到头节点后面，违背了从小到大的顺序。
  2. 如果插入的节点值大于等于尾结点，则该节点不会被插入，甚至于直接报错！

如：
在这里插入图片描述
又比如：

在这里插入图片描述

插入优化

因此，我们来把插入方法优化一下，增加插入头节点和尾节点的逻辑：

	/**
     * @Description 按照从小到大的顺序插入链表
     * @return void
     **/
    private static void insertChainTable2() {

        // 插入一个数
        int len = n;
        System.out.print("请输入插入的数：");
        data[len] = scanner.nextInt();

        // 如果新插入的节点比 头节点 小，则插入到链表头部
        if (data[len] < data[0]) {

            // 头节点和尾节点互换
            int temp = data[0]; data[0] = data[len]; data[len] = temp;

            right[len] = right[0]; // 保持旧头节点原有的连接关系不变
            right[0] = len; // 将新的头节点指向旧的节点

        }else {

            // 按照链表顺序遍历 data 数组，找到比 num 大的数
            int t = 0;
            while (right[t] != -1) {

                if (data[right[t]] > data[len]) { // 如果当前节点的下一个节点大于插入数，则插入

                    right[len] = right[t]; // 插入的节点 指向当前节点的下一个节点
                    right[t] = len; // 当前节点 指向插入的节点
                    break;
                }

                t = right[t];
            }

            // 插入的数如果比链表的最后一个节点大，则插入到链表尾部
            if (right[t] == -1) {

                right[n-1] = len;
                right[len] = -1;
            }
        }
    }

改动代码，来验证一下吧：

public static void main(String[] args) {

        // 创建链表
        createChainTable();

        // 打印链表
        printChainTable();

        // 往链表中插入数据
//        insertChainTable();
        insertChainTable2();

        // 打印链表
        printChainTable();
}

运行代码，分别验证，插入中间节点：

在这里插入图片描述
头节点：
在这里插入图片描述
尾节点：
在这里插入图片描述
很是完美！！！

完整代码

package com.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;

import java.util.Scanner;

/**
 * @Author: guqueyue
 * @Description: 用数组模拟链表
 * @Date: 2024/1/15
 **/
public class ChainTableTest2 {

    // 用于控制台输入
    private static Scanner scanner = new Scanner(System.in);

    private static int[] data = new int[101]; // 元素数组
    private static int[] right = new int[101]; // 索引数组

    private static int n = 0; // 链表长度

    public static void main(String[] args) {

        // 创建链表
        createChainTable();

        // 打印链表
        printChainTable();

        // 往链表中插入数据
//        insertChainTable();
        insertChainTable2();

        // 打印链表
        printChainTable();
    }

    /**
     * @Description 打印链表
     * @return void
     **/
    private static void printChainTable() {

        // 输出
        int t = 0;
        System.out.print("链表为：" + data[t]);
        while(right[t] != -1) {

            t = right[t]; // 获取下一个元素的索引
            System.out.print("->" + data[t]);
        }
        System.out.println();
    }

    /**
     * @Description 插入链表
     * @return void
     **/
    private static void insertChainTable() {

        // 插入一个数
        int len = n;
        System.out.print("请输入插入的数：");
        data[len] = scanner.nextInt();

        // 按照链表顺序遍历 data 数组，找到比 num 大的数
        int t = 0;
        while (t != -1) {

            if (data[right[t]] > data[len]) { // 如果当前节点的下一个节点大于插入数，则插入

                right[len] = right[t]; // 插入的节点 指向当前节点的下一个节点
                right[t] = len; // 当前节点 指向插入的节点
                break;
            }

            t = right[t];
        }

    }

    /**
     * @Description 按照从小到大的顺序插入链表
     * @return void
     **/
    private static void insertChainTable2() {

        // 插入一个数
        int len = n;
        System.out.print("请输入插入的数：");
        data[len] = scanner.nextInt();

        // 如果新插入的节点比 头节点 小，则插入到链表头部
        if (data[len] < data[0]) {

            // 头节点和尾节点互换
            int temp = data[0]; data[0] = data[len]; data[len] = temp;

            right[len] = right[0]; // 保持旧头节点原有的连接关系不变
            right[0] = len; // 将新的头节点指向旧的节点

        }else {

            // 按照链表顺序遍历 data 数组，找到比 num 大的数
            int t = 0;
            while (right[t] != -1) {

                if (data[right[t]] > data[len]) { // 如果当前节点的下一个节点大于插入数，则插入

                    right[len] = right[t]; // 插入的节点 指向当前节点的下一个节点
                    right[t] = len; // 当前节点 指向插入的节点
                    break;
                }

                t = right[t];
            }

            // 插入的数如果比链表的最后一个节点大，则插入到链表尾部
            if (right[t] == -1) {

                right[n-1] = len;
                right[len] = -1;
            }

        }
    }

    /**
     * @Description 创建链表
     * @return void
     **/
    private static void createChainTable() {

        System.out.print("请输入数字个数： ");
        n = scanner.nextInt();

        System.out.printf("请输入%d个数，中间用空格隔开，输入完回车： ", n);
        for (int i = 0; i < n; i++) {
            data[i] = scanner.nextInt();
        }

        // 初始化right数组
        for (int i = 0; i < n; i++) {

            right[i] = i == n-1 ? -1 : i+1;
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/414180.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

文生图项目总结

文生图项目总结

文生图 功能点 页面进来获取背景图url和图片宽高&#xff08;根据比例和手机屏幕处理过的宽高&#xff09;渲染图片&#xff08;背景图最后生成图片模糊&#xff0c;换成img展示解决&#xff09;添加多个文字&#xff0c;编辑文字内容&#xff0c;拖拽改变文字位置&#xff0c…
阅读更多...
计算机网络：IP

计算机网络：IP

引言&#xff1a; IP协议是互联网协议族中的核心协议之一&#xff0c;负责为数据包在网络中传输提供路由寻址。它定义了数据包如何在互联网上从源地址传输到目的地址的规则和流程。IP协议使得各种不同类型的网络设备能够相互通信&#xff0c;实现了全球范围内的信息交换。 目录…
阅读更多...
HTML-基础标签

HTML-基础标签

1. HTML初识 1.1 什么是HTML HTML&#xff08;英文Hyper Text Markup Language的缩写&#xff09;中文译为“超文本标签语言”&#xff0c;是用来描述网页的一种语言。所谓超文本&#xff0c;因为它可以加入图片、声音、动画、多媒体等内容&#xff0c;不仅如此&#xff0c;它还…
阅读更多...
nginx---------------重写功能 防盗链 反向代理 （五）

nginx---------------重写功能 防盗链 反向代理 （五）

一、重写功能 rewrite Nginx服务器利用 ngx_http_rewrite_module 模块解析和处理rewrite请求&#xff0c;此功能依靠 PCRE(perl compatible regular expression)&#xff0c;因此编译之前要安装PCRE库&#xff0c;rewrite是nginx服务器的重要功能之一&#xff0c;重写功能(…
阅读更多...
数据结构（C语言）代码实现（九）——迷宫探路表达式求值

数据结构（C语言）代码实现（九）——迷宫探路表达式求值

目录 参考资料 迷宫探路 顺序栈头文件SqStack.h 顺序栈函数实现SqStack.cpp 迷宫探路主函数 表达式求值 链式顺序栈头文件LinkStack.h 链式顺序栈函数实现LinkStack.cpp 表达式求值主函数 测试结果 参考资料 数据结构严蔚敏版 2021-9-22【数据结构/严蔚敏】【顺序…
阅读更多...
Django学习笔记-django使用pandas将上传的数据存到MySQL

Django学习笔记-django使用pandas将上传的数据存到MySQL

1.models中创建与excel表结构相同模型 2.模型映射 python manage.py makemigrations myapp01,python manage.py migrate 3.创建index,添加form,enctype使用multipart/form-data 4.urls中导入views,填写路由 5.views中创建index 6.如果为GET请求,直接返回index.html,如果为PO…
阅读更多...
历史新知网：寄快递寄个电脑显示器要多少钱？

历史新知网：寄快递寄个电脑显示器要多少钱？

以下文字信息由&#xff08;新史知识网&#xff09;编辑整理发布。 让我们赶紧来看看吧&#xff01; 问题1&#xff1a;快递寄电脑显示器要多少钱&#xff1f; 此物有多重&#xff1f; 顺丰寄就可以了&#xff0c;但是必须是原包装的&#xff0c;不然不好寄。 问题2&#xff1…
阅读更多...
阿里云中小企业扶持权益，助力企业开启智能时代创业新范式

阿里云中小企业扶持权益，助力企业开启智能时代创业新范式

在数字化浪潮的推动下&#xff0c;中小企业正面临着转型升级的重要关口。阿里云深知中小企业的挑战与机遇&#xff0c;特别推出了一系列中小企业扶持权益&#xff0c;旨在帮助企业以更低的成本、更高的效率拥抱云计算&#xff0c;开启智能时代创业的新范式。 一、企业上云权益…
阅读更多...
光伏预测 | Matlab基于CNN-SE-Attention-ITCN的多特征变量光伏预测

光伏预测 | Matlab基于CNN-SE-Attention-ITCN的多特征变量光伏预测

光伏预测 | Matlab基于CNN-SE-Attention-ITCN的多特征变量光伏预测 目录 光伏预测 | Matlab基于CNN-SE-Attention-ITCN的多特征变量光伏预测预测效果基本描述模型简介程序设计参考资料 预测效果 基本描述 Matlab基于CNN-SE-Attention-ITCN的多特征变量光伏预测 运行环境: Matla…
阅读更多...
【初中生讲机器学习】12. 似然函数和极大似然估计：原理、应用与代码实现

【初中生讲机器学习】12. 似然函数和极大似然估计：原理、应用与代码实现

创建时间&#xff1a;2024-02-23 最后编辑时间&#xff1a;2024-02-24 作者&#xff1a;Geeker_LStar 你好呀~这里是 Geeker_LStar 的人工智能学习专栏&#xff0c;很高兴遇见你~ 我是 Geeker_LStar&#xff0c;一名初三学生&#xff0c;热爱计算机和数学&#xff0c;我们一起加…
阅读更多...
Day04：APP架构小程序H5+Vue语言Web封装原生开发Flutter

Day04：APP架构小程序H5+Vue语言Web封装原生开发Flutter

目录 常见APP开发架构 APP-开发架构-原生态-IDEA APP-开发架构-Web封装-平台 APP-开发架构-H5&Vue-HBuilderX WX小程序-开发架构-Web封装-平台 WX小程序-开发架构-H5&Vue-HBuilderX 思维导图 章节知识点&#xff1a; 应用架构&#xff1a;Web/APP/云应用/三方服…
阅读更多...
[CISCN 2019华东南]Web11

[CISCN 2019华东南]Web11

打开题目 看到xff就应该想到抓包 看回显也是127.0.0.1&#xff0c;我们盲猜是不是ssti模板注入 输入{{7*7}}显示49 可以看的出来flag在根目录下 输入{system(‘cat /flag’)} 得到flag 知识点&#xff1a; 漏洞确认 一般情况下输入{$smarty.version}就可以看到返回的smarty…
阅读更多...
nebula容器方式安装：docker 安装nebula到windows

nebula容器方式安装：docker 安装nebula到windows

感谢阅读 基础环境安装安装docker下载nebula 安装数据库命令行安装查询network nebula-docker-compose_nebula-net并初始化查询安装初始使用root&#xff08;God用户类似LINUX的root&#xff09; 关闭服务 安装UI 基础环境安装 安装docker 点我下载docker 下载nebula 数据…
阅读更多...
Python 实现Excel自动化办公（中）

Python 实现Excel自动化办公（中）

在上一篇文章的基础上进行一些特殊的处理&#xff0c;这里的特殊处理主要是涉及到了日期格式数据的处理&#xff08;上一篇文章大家估计也看到了日期数据的处理是不对的&#xff09;以及常用的聚合数据统计处理&#xff0c;可以有效的实现你的常用统计要求。代码如下&#xff1…
阅读更多...
Spring Boot项目误将Integer类型写成int来进行传参

Spring Boot项目误将Integer类型写成int来进行传参

在处理项目中Idea中无报错&#xff1a; 问题&#xff1a; localhost:8080/param/m2在浏览器中输入&#xff1a;localhost:8080/param/m2 产生报错&#xff1a; This application has no explicit mapping for /error, so you are seeing this as a fallback. Tue Feb 27 20:55…
阅读更多...
MATLAB_ESP32有限脉冲响应FIR无限脉冲响应IIR滤波器

MATLAB_ESP32有限脉冲响应FIR无限脉冲响应IIR滤波器

要点 ESP32闪烁LED&#xff0c;计时LEDESP32基础控制&#xff1a;温控输出串口监控&#xff0c;LCD事件计数器&#xff0c;SD卡读写&#xff0c;扫描WiFi网络&#xff0c;手机控制LED&#xff0c;经典蓝牙、数字麦克风捕捉音频、使用放大器和喇叭、播放SD卡和闪存MP3文件、立体…
阅读更多...
使用 kubeadm 部署k8s集群

使用 kubeadm 部署k8s集群

一、所有节点系统初始化 1、常规初始化 2、内核版本升级以及内核限制文件参数修改 还可以考虑将旧版本的内核卸载 二、准备nginx负载均衡器和keepalived nginx四层代理&#xff1a; keepalived配置&#xff1a; nginx检测脚本&#xff1a; 三、所有节点部署docker&#xff0c…
阅读更多...
2023年06月CCF-GESP编程能力等级认证Scratch图形化编程二级真题解析

2023年06月CCF-GESP编程能力等级认证Scratch图形化编程二级真题解析

一、单选题（共10题，共30分） 第1题 高级语言编写的程序需要经过以下（ ）操作，可以生成在计算机上运行的可执行代码。 A：编辑 B：保存 C：调试 D：编译 答案：D 第2题 默认小猫角色，执行下列程序，说法错误的是？( ) A：不按下空格键，小猫会随机移动 B：不按下空格…
阅读更多...
高防IP简介

高防IP简介

高防IP可以防御的有包括但不限于以下类型&#xff1a; SYN Flood、UDP Flood、ICMP Flood、IGMP Flood、ACK Flood、Ping Sweep 等攻击。高防IP专注于解决云外业务遭受大流量DDoS攻击的防护服务。支持网站和非网站类业务的DDoS、CC防护&#xff0c;用户通过配置转发规则&#x…
阅读更多...
STM32F103学习笔记（六） RTC实时时钟（应用篇）

STM32F103学习笔记（六） RTC实时时钟（应用篇）

目录 1. RTC 实时时钟的应用场景 2. RTC 的配置与初始化 2.1 设置 RTC 时钟源 2.2 初始化 RTC 寄存器 2.3 中断配置 2.4 备份寄存器配置 2.5 校准 RTC 3. 实例演示代码 4. 总结 1. RTC 实时时钟的应用场景 实时时钟&#xff08;RTC&#xff09;在嵌入式系统中具有广泛…
阅读更多...
最新文章

Copyright @ 2022~2023