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;}}
}

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

在Golang中简化日志记录：提升性能和调试效率

在Golang中简化日志记录：提升性能和调试效率

最大化效率和有效故障排除&#xff1a;在Golang中简化日志记录 日志记录是软件开发的一个基本方面&#xff0c;有助于调试、监控和理解应用程序的流程。在Golang中&#xff0c;有效的日志记录实践可以显著提高性能并简化调试过程。本文探讨了优化Golang日志记录的技术&#xf…
阅读更多...
Android WebView实现网页滚动截图

Android WebView实现网页滚动截图

WebView 网页滚动截屏&#xff0c;可对整个网页进行截屏而不是仅当前屏幕哦&#xff01; 注意若Web页面存在position:fixed; 的话得在调用前设置为 position:absolute; 哦&#xff0c;否则会出现很多次的&#xff0c;请看下面的具体解说吧&#xff01;&#xff01; private s…
阅读更多...
一周学会Django5 Python Web开发-Django5列表视图ListView

一周学会Django5 Python Web开发-Django5列表视图ListView

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计27条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…
阅读更多...
[数据集][目标检测]狗狗表情识别VOC+YOLO格式3971张4类别

[数据集][目标检测]狗狗表情识别VOC+YOLO格式3971张4类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;3971 标注数量(xml文件个数)&#xff1a;3971 标注数量(txt文件个数)&#xff1a;3971 标注…
阅读更多...
Spring注解之前后端传值

Spring注解之前后端传值

目录 PathVariable 和 RequestParam RequestBody PathVariable 和 RequestParam PathVariable用于获取路径参数&#xff0c;RequestParam用于获取查询参数。 举个简单的例子&#xff1a; GetMapping("/lazzes/{clazzId}/teachers") public List<Teacher> …
阅读更多...
HP笔记本电脑如何恢复出厂设置？这里提供几种方法

HP笔记本电脑如何恢复出厂设置？这里提供几种方法

要恢复出厂设置Windows 11或10的HP笔记本电脑，你可以使用操作系统的标准方法。如果你运行的是早期版本，你可以使用HP提供的单独程序清除计算机并重新安装操作系统。 恢复出厂设置运行Windows 11的HP笔记本电脑​ 所有Windows 11计算机都有一个名为“重置此电脑”的功能，可…
阅读更多...
【Nginx笔记02】通过Nginx服务器转发客户端的WebSocket接口到后端服务

【Nginx笔记02】通过Nginx服务器转发客户端的WebSocket接口到后端服务

这篇文章&#xff0c;主要介绍如何通过Nginx服务器转发客户端的WebSocket接口到后端服务【知识星球】。 目录 一、Nginx配置WebSocket 1.1、Nginx配置内容 1.2、客户端请求地址 1.3、创建WebSocket测试工程 1.4、启动测试 1.5、WebSocket超时问题 1.5.1、设置超时时间 …
阅读更多...
数据结构与算法(数组,栈,队列,链表,哈希表,搜索算法,排序算法,查找算法,策略算法,递归算法,二叉搜索树BST,动态规划算法)

数据结构与算法(数组,栈,队列,链表,哈希表,搜索算法,排序算法,查找算法,策略算法,递归算法,二叉搜索树BST,动态规划算法)

文章目录 1 课程介绍1.1 前置知识1.2 为什么要学习算法1.3 大厂面试常见数据结构题目(基础)1.4 数据结构和算法的关系 2 数据结构2.1 数据结构概述2.1.1 数据结构是什么2.1.2 数据结构分类2.1.2.1 线性结构2.1.2.2 非线性结构2.1.2.3 小总结 2.1.3 数据结构范围 2.2 数组Array2…
阅读更多...
关于电脑一天24小时多少度电电脑的一天用电量计算

关于电脑一天24小时多少度电电脑的一天用电量计算

随着这几年物价的上涨&#xff0c;一些地区的电价越来越高&#xff0c;而我们经常需要使用电脑&#xff0c;那么一台电脑一天24小时用多少度电呢&#xff1f; 如何计算电脑一天的用电量&#xff1f; 让我们跟随小编来了解更多吧。 1、功耗、主机箱功耗 现在的计算机中&#xf…
阅读更多...
IDEA如何开启Dashboard

IDEA如何开启Dashboard

普通的面板 Run Dashboard面板 修改配置文件 找到项目的.idea文件夹 点击编辑workspace.xml文件 添加下方代码 <component name"RunDashboard"><option name"ruleStates"><list><RuleState><option name"name" valu…
阅读更多...
sublime双击后无法正常打开的解决方案

sublime双击后无法正常打开的解决方案

大家好，我是爱编程的喵喵。双985硕士毕业，现担任全栈工程师一职，热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…
阅读更多...
4核8g服务器能支持多少人访问？

4核8g服务器能支持多少人访问？

腾讯云4核8G服务器支持多少人在线访问&#xff1f;支持25人同时访问。实际上程序效率不同支持人数在线人数不同&#xff0c;公网带宽也是影响4核8G服务器并发数的一大因素&#xff0c;假设公网带宽太小&#xff0c;流量直接卡在入口&#xff0c;4核8G配置的CPU内存也会造成计算…
阅读更多...
云计算时代的运维： 职业发展方向与岗位选择

云计算时代的运维： 职业发展方向与岗位选择

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua&#xff0c;在这里我会分享我的知识和经验。&#x…
阅读更多...
素皮材质的手机壳，如何才能做到经久耐用？

素皮材质的手机壳，如何才能做到经久耐用？

近几年&#xff0c;素皮材质开始在手机背壳上开始应用&#xff0c;各家手机厂商&#xff0c;基本都给自己的旗舰系列设备推出了带素皮材质版本的手机款式&#xff0c;比如华为的Mate 60系列&#xff0c;不仅Pro版本有素皮材质&#xff0c;Pro版本更是黑白两款全是素皮材质。 那…
阅读更多...
Qt6.8 GRPC功能使用(2)标准 Qt实现客户端

Qt6.8 GRPC功能使用(2)标准 Qt实现客户端

简介 基于之前的文章所说&#xff0c; Qt6.7之后才开始支持客户端、服务端、及双向流&#xff0c;恰好电脑需要重装&#xff0c;看到Qt6.8版本就直接安装了&#xff0c;内容也是使用Qt6.8的版本进行编译的 客户端实现步骤 1. 安装Qt6.8, 包含GRPC功能模块 Qt 6.8安装目录下包…
阅读更多...
php基础学习之错误处理（其一）

php基础学习之错误处理（其一）

一&#xff0c;错误处理的概念 错误处理指的是系统(或者用户)在执行某些代码的时候&#xff0c;发现有错误&#xff0c;就会通过错误处理的形式告知程序员&#xff0c;俗称报错 二&#xff0c;错误分类 语法错误&#xff1a;书写的代码不符合 PHP 的语法规范&#xff0c;语法错…
阅读更多...
开源大模型LLM大爆发，数据竞赛已开启！如何使用FuseLLM实现大语言模型的知识融合？

开源大模型LLM大爆发，数据竞赛已开启！如何使用FuseLLM实现大语言模型的知识融合？

开源大模型LLM大爆发&#xff0c;数据竞赛已开启&#xff01;如何使用FuseLLM实现大语言模型的知识融合&#xff1f; 现在大多数人都知道LLM是什么&#xff0c;以及可以做什么。 人们讨论着它的优缺点&#xff0c;畅想着它的未来&#xff0c; 向往着真正的AGI&#xff0c;又有…
阅读更多...
LeetCode_Java_动态规划系列(3)（题目+思路+代码）

LeetCode_Java_动态规划系列(3)（题目+思路+代码）

338.比特位计数 给你一个整数 n &#xff0c;对于 0 < i < n 中的每个 i &#xff0c;计算其二进制表示中 1 的个数 &#xff0c;返回一个长度为 n 1 的数组 ans 作为答案。 class Solution {public int[] countBits(int n) {/** 思路&#xff1a;* 1.创建一个长度为 n…
阅读更多...
ubuntu20下使用 torchviz可视化计算图

ubuntu20下使用 torchviz可视化计算图

安装 torchviz&#xff1a; pip install torchviz示例代码&#xff1a;下面是一个简单的示例代码&#xff0c;展示如何使用 torchviz 可视化计算图&#xff1a; python import torch from torchviz import make_dot# 创建一个简单的模型 model torch.nn.Sequential(torch.nn…
阅读更多...
Neoverse S3 系统 IP：机密计算和多芯片基础设施 SoC 的基础

Neoverse S3 系统 IP：机密计算和多芯片基础设施 SoC 的基础

第三代Neoverse系统IP Neoverse S3 产品推出了我们的第三代基础设施特定系统 IP&#xff0c;这是下一代基础设施 SOC 的理想基础&#xff0c;适用于从 HPC 和机器学习到 Edge 和 DPU 的各种应用。S3 机箱专注于为我们的合作伙伴提供 Chiplet、机密计算等关键创新以及 UCIe、DD…
阅读更多...
最新文章

Copyright @ 2022~2023