科技公司 网站 石家庄,wordpress改背景,苏州网站建设书生,广州软件定制人应该支配习惯#xff0c;而绝不是让习惯支配人。一个人要是不能改掉坏习惯#xff0c;那么他就一文不值。 目录 缘代码地址模拟链表创建遍历打印插入插入优化 完整代码 缘
各位小伙伴们好呀#xff01;本人最近看了下《啊哈算法》#xff0c;写的确实不错。
但稍显遗憾…人应该支配习惯而绝不是让习惯支配人。一个人要是不能改掉坏习惯那么他就一文不值。 目录 缘代码地址模拟链表创建遍历打印插入插入优化 完整代码 缘
各位小伙伴们好呀本人最近看了下《啊哈算法》写的确实不错。
但稍显遗憾的是书籍示例代码是c语言而不是本人常用的Java。
那就弥补遗憾说干就干把这本书的示例语言用java写一遍 顺带附上一些自己的理解
今天这篇博客讲的是如何用数组来模拟链表。
来不及买纸质书但又想尽快感受算法魅力的童鞋也甭担心电子版的下载链接已经放到下方了可尽情下载。 链接https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwdjmgs 提取码jmgs 代码地址
本文代码已开源
git clone https://gitee.com/guqueyue/my-blog-demo.git请切换到gitee分支
然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_2_StackAndChainTable即可
模拟链表
在往期的博客中我们用数组模拟了队列、栈并且说了用链表也可以模拟队列、栈。
于是乎我们还介绍了链表但是链表指来指去的难免让人奇奇怪怪、晕头转向。 Java玩转《啊哈算法》解密QQ号之队列Java玩转《啊哈算法》解密回文之栈Java玩转《啊哈算法》之链表 那么这期博客我们来讲一下如何用数组来模拟链表。
数组可以模拟队列、栈链表也可以模拟队列、栈数组也能模拟链表没想到吧。
创建
那么要怎么用数组来模拟链表呢我们需要准备两个数组一个数组存元素一个数组用来存元素对应的下一个元素的位置。 如上图所示我们data数组用于存放元素内容right数组用以存放相同索引处对应data数组的下一个元素的索引。
如图我们头节点的元素为data[1]也就是2下一个元素为data[right[1]]也就是3。
当然我们这里可以做一些小小的改动
为了不浪费空间我们的存放数组的索引从0开始而不是从1开始。链表尾节点的下一个位置的索引我们用-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 : i1;}}遍历打印
有了创建链表的方法当然要有一个打印的方法不然怎么验证 /*** 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 : i1;}}
}运行代码控制台输入可得
插入 同样的按照书上的逻辑我们来写一个往链表中插入元素的方法 /*** 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();}运行得 看起来好像没啥问题但是同上期博客一样存在着两个问题
如果插入的节点值大小小于头节点该节点会被插入到头节点后面违背了从小到大的顺序。如果插入的节点值大于等于尾结点则该节点不会被插入甚至于直接报错
如 又比如 插入优化
因此我们来把插入方法优化一下增加插入头节点和尾节点的逻辑 /*** 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 : i1;}}
}
