【java数据结构】线性表(顺序表及链表)及其实现

您所在的位置：网站首页 › linkedlist数据结构图 › 【java数据结构】线性表(顺序表及链表)及其实现

【java数据结构】线性表(顺序表及链表)及其实现

2023-04-02 02:08| 来源: 网络整理| 查看: 265

01 引入：多项式的表示

02 什么是线性表

2.1 线性表抽象数据类型概述

2.2 线性表顺序存储实现

2.3 线性表的链表存储实现

2.3.1 单链表实现

2.3.2 双向链表实现代码

2.3.3单向环形链表和约瑟夫环

01 引入：多项式的表示

方法一：顺序结构直接表示（数组）

方法二：顺序存储结构存储非零项

方法三：链表结构存储非零项

02 什么是线性表

线性表”：由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的长度线性表没有元素时，称为空表表起始位置称为表头，表结束位置称表尾

说明：线性表也就是数组的一种特殊储存方式：从头到尾依次储存数据。

2.1 线性表抽象数据类型概述

线性表操作接口描述

public interface IList { public void clear(); // 将一个已经存在的线性表置成空表 public boolean isEmpty(); // 判断当前线性表中的数据元素个数是否为0,若为0则函数返回true，否则返回false public int length(); // 求线性表中的数据元素个数并由函数返回其值 public Object get(int i) throws Exception;// 读取到线性表中的第i个数据元素并由函数返回其值。其中i取值范围为：0≤i≤length()-1,如果i值不在此范围则抛出异常 public void insert(int i, Object x) throws Exception;// 在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x public void remove(int i) throws Exception;// 将线性表中第i个数据元素删除。其中i取值范围为：0≤i≤length()- 1,如果i值不在此范围则抛出异常 public int indexOf(Object x);// 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1 public void display();// 输出线性表中的数据元素 } 2.2 线性表顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

注：顺序存储中是序号是下标，从 0 开始

public class SeqList implements List{ private Object[] listArray; // 初始化线性表存储空间 private int size; //数组当前长度 private int maxSize; // 数组允许的最大长度 public SeqList(int maxSize) { //初始化 this.size = 0; this.maxSize = maxSize; listArray = new Object[maxSize]; } @Override public void clear() { size = 0; // 置当前长度为0 } @Override public boolean isEmpty() { return size == 0; // 判断当前长度是否为0，是则返回true } @Override public int length() { return size; // 返回数组当前长度 } @Override public Object get(int i) throws Exception { if(i < 0 || i >= size){ throw new Exception("第" + i + "个元素不存在"); }else{ return listArray[i]; } } @Override //在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i取值范围为：0≤i≤length()。 // 如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,当i=length()时表示在表尾插入一个数据元素x public void insert(int i, Object x) throws Exception { if(size == maxSize){ // 判断表已满 throw new Exception("顺序表已满"); } if (i < 0 || i > size){ //这里不能是maxSize 因为线性表必须连续 throw new Exception("插入位置错误"); } // 插入位置正确，索引为 i-（size-1）数据后移 for(int j = size-1 ; j >= i ; j--){ listArray[j + 1] = listArray[j]; } listArray[i] = x; //插入x size++; // 表长加一 } @Override public void remove(int i) throws Exception { // 删除 if(i < 0 || i >= size){ throw new Exception("第" + i + "个元素不存在"); } for(int j = i ; j < size; j++){ listArray[j] = listArray[j + 1]; } size--; // 表长减一 } @Override //返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1 public int indexOf(Object x) { int j = 0; // 计数器 while ( j < size && !(listArray[j].equals(x))){ j++; } if(j < size){ // j位于表中 return j; }else{ return -1; // 如果不存在返回-1 } } @Override public void display() { for (int j = 0; j < size; j++) System.out.print(listArray[j] + " "); System.out.println();// 换行 } } 2.3 线性表的链表存储实现

不要求逻辑上相邻的两个元素物理上也相邻，通过"链"建立起数据之间的逻辑关系

插入、删除不需要移动数据元素，只需要修改"链"

注：链表存储中序号从 1 开始

单链表：由结点组成，每个结点包含两部分，数据域和指针域，数据域存储真正需要存储的数据部分，指针域是一个指向其后继结点（或前驱结点）的指针。双链表：双链表也是由结点组成，不同的是除了数据域以外，它有两个指针域，一个指向其前驱结点，另一个指向其后继结点。循环列表：循环列表一般指单循环列表，即只有一个指针域的链表，在与单链表不同的是，在单链表中其尾结点的指针通常为null，而循环列表其尾结点的指针指向其头节点，构成一个循环结构。

// 定义一个链表接口 public interface List { public int size(); public boolean isEmpty(); public void insert(int index,Object obj) throws Exception; public void delete(int index) throws Exception; public Object get(int index) throws Exception; }

定义结点

// 定义结点，每个node对象是一个节点 class Node{ public int no; public String name; public Node next; public Node(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + '}'; } } 2.3.1 单链表实现

添加结点

class SingleLingked{ // 初始化头结点 private Node head = new Node(0, " "); // 头结点不存放具体数据，只是为了编程方便 // 添加结点到单向链表末尾 public void add(Node node){ // 头结点不能动，需要一个辅助指针 Node temp = head; // 遍历链表 while(true){ if (temp.next == null){ // 找到链表的最后 break; } // 如果没有找到， temp后移 temp = temp.next; } // 退出循环时，指向链表最后 temp.next = node; }

按顺序添加结点

// 按编号顺序添加结点 public void addByOrder(Node node){ // 头结点不能动，需要辅助指针找到要添加的位置 // 找的temp位于要添加的前一个结点 Node temp = head; boolean flag = false; // 标识编号是否存在，默认为false while(true){ if (temp.next == null){ break; } if(temp.next.no > node.no){ // 位置找到，就在temp后面插入 break; }else if(temp.next.no == node.no){ // 说明要添加的编号存在 flag = true; break; } temp = temp.next; } // 退出循环首先要判断flag值 if(flag == true){ System.out.println("准备插入的结点已存在"); }else { // 插入到temp后面 node.next = temp.next; temp.next = node; } } }

遍历链表

// 遍历显示链表 public void list(){ // 先判断是否为空 if(head.next == null){ System.out.println("链表为空"); return; } // 如果不为空，因为头结点不能动，因此需要辅助变量来遍历 Node temp = head.next; while(true){ // 判断是否到链表最后 if(temp == null){ break; } // 如果不为空，打印 System.out.println(temp); //后移 temp = temp.next; } }

修改结点

// 修改结点，根据编号no修改，即 no 不能变 public void update(Node newNode){ // 先判断是否为空 if(head.next == null){ System.out.println("链表为空"); return; } // 找到要修改的结点 Node temp = head.next; boolean flag = false; // 确认是否找到编号 while(true){ if(temp == null){ break; // 遍历完成 } if(temp.no == newNode.no){// 找到要修改的结点 flag = true; break; } temp = temp.next; } // 根据flag判断是否找到要修改的结点 if(flag){ temp.name = newNode.name; // 如找到了，修改结点内容 }else { // 没找到 System.out.println("您要修改的结点不存在"); } }

删除结点

/* 删除结点，要找到需要删除结点的前一个结点temp temp.next = temp.next.next 被删除的结点会被垃圾回收机制删除 */ public void remove(int no){ Node 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 == true){ temp.next = temp.next.next; }else{ System.out.println("结点不存在"); } }

返回链表长度

// 获取单链表节点个数（带头结点则不统计头结点） /* head: 头结点返回有效结点个数 */ public static int getLength(Node head){ if(head.next == null){ // 空链表 return 0; } int length = 0; Node cur = head.next; while(cur != null){ length++; cur = cur.next; } return ; } 2.3.2 双向链表实现代码

双向链表遍历与单向链表相同，只是可以向前，也可以向后

添加：默认添加到链表末尾

先找到末尾结点------》temp.next = newNode -------> newNode.prev = temp;

修改：和单项链表一样

删除：

1.因为是双向链表，可以实现自我删除某个结点

2. 直接找到要删除结点，temp.prev.next = temp.next

temp.next.prev = temp.prev

代码实现

结点类：

class NodeDouble{ public int no; public String name; public NodeDouble next; // 指向下一个结点，默认为null public NodeDouble pre; // 指向上一个结点，默认为null public NodeDouble(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + '}'; } }

双向链表实现

// 首先创建双向链表 class DoubleLinkedList{ // 头结点 public NodeDouble head = new NodeDouble(0, " "); // 返回头结点 public NodeDouble getHead() { return head; } // 遍历双向链表 public void list(){ // 判断链表是否为空 if(head.next == null){ System.out.println("链表为空"); } // 不为空则遍历 NodeDouble temp = head.next; while (temp != null){ System.out.println(temp); temp = temp.next; } } // 添加 public void add(NodeDouble node){ // 遍历链表，找到最后一个结点 NodeDouble temp = head; while(temp.next != null){ temp = temp.next; // 此时temp为链表最后一个结点 } // 形成一个新的链接 temp.next = node; node.pre = temp; } // 第二种添加方式，按顺序添加 public void addByOrder(NodeDouble node){ NodeDouble temp = head; boolean flag = false; // 标识编号是否存在，默认为false // 遍历链表找到要添加的位置 while(true){ if(temp.next == null){ // 遍历完成,如果为空。也添加再temp后面 break; } if((temp.no < node.no) && (node.no < temp.next.no)){ // 此时添加在temp后面 break; }else if(temp.no == node.no){ flag = true; break; } temp = temp.next; } if(flag == true){ System.out.println("编号已存在，不能添加"); }else{ node.next = temp.next; temp.next = node; node.pre = temp; if(temp.next != null){ temp.next.pre = node; } } } // 修改,和单向链表几乎一样 // 修改结点，根据编号no修改，即 no 不能变 public void update(NodeDouble newNode){ if(head.next == null){ System.out.println("链表为空"); } // 如果不为空找到要修改的结点，遍历 NodeDouble temp = head.next; boolean flag = false; // 标识：是否找到要修改的节点 while(true){ if(temp == null){ break; // 遍历到结尾了 }else{ if(temp.no == newNode.no){ // 找到了 flag = true; break; } } temp = temp.next; } if(flag == true){ temp.name = newNode.name; }else{ // 没找到 System.out.println("您要修改的结点不存在"); } } // 删除结点：对于双向链表可以直接找到待删除结点进行自我删除 public void remove(int no){ if(head.next == null){ System.out.println("空链表，不能删除"); return; } NodeDouble temp = head.next; // 双向链表是直接找待删除结点，所以可以直接令temp比较 boolean flag = false; // 标识是否找到待删除结点 while(true){ if(temp == null){ break; } if(temp.no == no){ flag = true; break; } temp = temp.next; } if(flag == true){ // 找到了待删除结点： temp就是 temp.pre.next = temp.next; //如果要删除的是最后一个结点，不需要执行下面这句话否则会空指针异常： temp.next == null if (temp.next != null){ temp.next.pre = temp.pre; } }else{ System.out.println("没找到要删除的结点"); } } } 2.3.3单向环形链表和约瑟夫环

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

用一个不带头结点的循环链表来处理约瑟夫问题，先构成一个n个结点的单向循环链表，由k结点起从1开始计数，计数到m时，对应结点从链表中删除，从被删除的下一个结点继续从1 开始计数，直到最后一个结点从链表中删除

构建环形单向链表的思路：先创建第一个结点， first指向该结点，并形成环状每创建一个新的结点，就将该结点加入到环形链表中遍历环形链表辅助指针cur指向first结点通过while循环遍历, cur.next == first 时遍历完毕

结点类

// 创建结点类 class NodeCircle{ private int no; //编号 private NodeCircle next; public NodeCircle(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public NodeCircle getNext() { return next; } public void setNext(NodeCircle next) { this.next = next; } }

约瑟夫环问题的解决代码

// 创建环形单向链表 class CircleLinkedList{ // 创建一个first结点，当前没有编号 private NodeCircle first = null; // 添加结点构建成环形 public void add(int num){ if(num < 1){ System.out.println("num数据不正确"); return; } NodeCircle curNode = null; // 辅助指针 // 创建环形链表 for(int i = 1; i nums){ System.out.println("参数输入有误"); return; } // 创建辅助指针helper，帮助出列 NodeCircle helper = first; while (true) { if(helper.getNext() == first){ // 说明指向最后一个节点 break; } helper = helper.getNext(); } // 移动指针到初始计数结点 startNum for(int j = 0; j < startNum - 1 ;j++ ){ first = first.getNext(); helper = helper.getNext(); } // 报数时：移动m-1次 while(true){ if(helper == first){ // 说明圈中只有一个节点 break; } for (int j = 0 ; j < countNum - 1 ; j++){ first = first.getNext(); helper = helper.getNext(); } // 此时first指向的节点为要出圈的结点 System.out.println("出列编号为" + first.getNo()); // first指向结点出圈 first = first.getNext(); helper.setNext(first); } System.out.println("最后留在圈中的编号为" + first.getNo()); } }

测试

public class JosepfuQuestion { public static void main (String[] args){ // 构建环形链表实例 CircleLinkedList circleLinkedList = new CircleLinkedList(); circleLinkedList.add(6); // 5ge结点的环形链表 circleLinkedList.showlist(); circleLinkedList.countNode(1,5,6); } }

【本文地址】

公司简介

联系我们