亿藤互联网站建设开发,购买域名流程,步骤图,wordpress循环文章目录
试题1#xff1a;实现一个单链表#xff0c;并实现以下功能#xff1a;
试题2#xff1a;实现一个双链表#xff0c;并实现以下功能
思路总结#xff1a;
什么情况下可能涉及到用数组实现链表呢#xff1f; 在学习时了解到了可以用数组模拟链表#xff0c;使其…目录
试题1实现一个单链表并实现以下功能
试题2实现一个双链表并实现以下功能
思路总结
什么情况下可能涉及到用数组实现链表呢 在学习时了解到了可以用数组模拟链表使其兼顾数据查找快链表新增和删除快的缺点找来一些试题实现了下如下
试题1实现一个单链表并实现以下功能 Java代码实现
import org.apache.commons.lang3.StringUtils;import java.util.Scanner;public class ArrayLinkedList {public static final int N 100000;private int head; // headprivate int idx; // 存储新元素的索引下标private int[] e; // 存放数据的数组private int[] ne; // 当前节点的下一个节点的地址(数组下标)。比如使用头插法,单向链表,e[5] 5,e[5]的下一个节点的坐标是ne[5],下一个节点是e[ne[5]]public ArrayLinkedList() {e new int[N];ne new int[N];head -1;idx 0;}public void insertToHead(int val) {e[idx] val;ne[idx] head; // head的值是头结点指向的下一个元素的下标值head idx;}/*** 将val插入到索引k后面** param k* param val*/public void insert(int k, int val) {e[idx] val;ne[idx] ne[k];ne[k] idx;}/*** 删除k节点后面的节点(只删一个)** param k*/public void remove(int k) {if (k 1 0) {head ne[head];} else {ne[k] ne[ne[k]];}}public static void main(String[] args) {System.out.println(请输入:);Scanner scanner new Scanner(System.in);ArrayLinkedList arrayLinkedList new ArrayLinkedList();int head arrayLinkedList.head;int[] e arrayLinkedList.e;int[] ne arrayLinkedList.ne;while (scanner.hasNextLine()) {String inputString scanner.nextLine();if (StringUtils.isBlank(inputString)) {break;}String[] inputArr inputString.split( );String f inputArr[0];int s Integer.valueOf(inputArr[1]);switch (f) {case H:arrayLinkedList.insertToHead(s);break;case D:arrayLinkedList.remove(s - 1); // 第k个插入的数idx是k-1break;case I:int val Integer.valueOf(inputArr[2]);arrayLinkedList.insert(s - 1, val);break;}}for (int i head; i ! -1; i ne[i]) {System.out.print(e[i] );}scanner.close();}
}
试题2实现一个双链表并实现以下功能
Java代码实现
import org.apache.commons.lang3.StringUtils;import java.util.Scanner;/*** 支持的操作* 1、在最左侧插入一个数* 2、在最右侧插入一个数* 3、将第k个插入的数删除* 4、在第k个插入的数左侧插入一个数* 5、在第k个插入的数右侧插入一个数*/
public class TwoWayLinkedList2 {public static final int N 100000;// 存放数组的数据private int[] e;// 存放左指针下标数组private int[] l;// 存放右指针地址数组private int[] r;// 数组待存储下标private int idx;// e[0]表示链表头e[1]表示链表尾// 向左侧插入就是插入到上一个节点的右侧。所以插入的逻辑都抽象成插入到具体节点的右侧// 构造方法public TwoWayLinkedList2() {e new int[N];r new int[N];l new int[N];r[0] 1;l[1] 0;idx 2;}/*** 将节点插入到e[k]节点右侧** param k* param val*/public void add(int k, int val) {e[idx] val;l[idx] k;r[idx] r[k];l[r[k]] idx;r[k] idx;idx;}/*** 删除e[k]** param k*/public void remove(int k) {r[l[k]] r[k];l[r[k]] l[k];}public static void main(String[] args) {System.out.println(请输入:);Scanner scanner new Scanner(System.in);TwoWayLinkedList2 linkedList new TwoWayLinkedList2();int[] e linkedList.e;int[] l linkedList.l;int[] r linkedList.r;while (scanner.hasNextLine()) {String inputString scanner.nextLine();if (StringUtils.isBlank(inputString)) {break;}String[] inputArr inputString.split( );String f inputArr[0];Integer s Integer.valueOf(inputArr[1]);switch (f) {case L:linkedList.add(0, s);break;case R:linkedList.add(l[1], s);break;case D:linkedList.remove(s 1); // 第k个插入的数idx是k1,因为我们用了0和1表示链表头和链表尾break;case IL:linkedList.add(l[s 1], Integer.valueOf(inputArr[2]));break;case IR:linkedList.add(s 1, Integer.valueOf(inputArr[2]));break;}}// 遍历输出for (int i r[0]; i ! 1; i r[i]) {System.out.printf( e[i]);}scanner.close();}
}
思路总结 数组实现链表一个数组用于存放数据一个数组存放指针这里的指针用数组下标代替。如果是双向链表要用两个数组存放指针。同时要注意首节点和尾结点的记录方法。在实现双链表时我曾用两个变量表示首尾节点对比起来没有用e[0],e[1]表示简洁而且非常容易搞混。占用第0位和第1位保存链表头和尾时要注意初始的idx2第k个插入的元素的索引下标是k1。大家可以使用更多方法实现过程虽然曲折但一顿操作下来对链表的操作会非常的熟练。
什么情况下可能涉及到用数组实现链表呢 在没有操作系统和内存管理的情况下。
1. 链表的实现需要动态内存分配和释放,这需要操作系统提供的堆内存管理。没有 OS 的动态内存管理,就无法真正实现链表节点的创建和销毁。
2. 链表通过指针链接节点,需要操作系统提供的指针和地址引用机制。没有 OS,就无法真正用指针建立节点之间的链接关系。
3. 数组可以预先分配一块内存,这个内存块可以视为堆内存,用下标代替指针,通过数组操作就可以模拟出指针操作。
4. 数组是一块连续的内存,空间固定,不需要动态扩展,所以定义数组后直接就可以使用,不依赖动态内存管理。
5. 数组中的每个元素是连续存储的,通过下标可以直接访问,不需要指针来进行寻址。可以模拟指针的移动,改变指针的指向来实现链表的操作。 这里我们从算法分析和学习的角度来看这个问题但不适合实际项目,只能处理规模较小的数据。要实现一个真正的可扩展链表,还需在操作系统上进行动态内存管理。
