博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Java 数据结构 | 线性表「顺序存储 + 链式存储」
阅读量：4104 次
发布时间：2019-05-25

本文共 15571 字，大约阅读时间需要 51 分钟。

一、顺序存储

1) 特点

(1) 使用一组地址连续的存储单元依次存放线性表中各个数据元素。

(2) 逻辑上相邻的数据元素，物理上也是相邻的，删除数据会引起大量数据移动。

(3) 便于随机存取。

(4) 不便于插入和删除操作。

(5) 若要扩充存储空间，需要重新创建一个地址连续的更大的存储空间，并把所有数据复制到新的存储空间。

2) 实现

package com.hly.dataStructure.linkedList;import java.util.Arrays;/** * @author :hly * @github :https://github.com/huangliangyun * @blog :http://www.javahly.com/ * @CSDN :blog.csdn.net/Sirius_hly * @date :2019/3/8 *///线性表顺序存储public class SequentialLinearList
   
     {
       //线性表存储空间    private Object[] listElem;    //线性表长度    private int len;    //初始化线性表的大小    public SequentialLinearList(int maxLen) {
           len = 0;        listElem = new Object[maxLen];    }    //将线性表置空    public void clear() {
           len = 0;    }    //判断线性表是否为空    public boolean isEmpty() {
           return len == 0;    }    //返回线性表中元素的个数    public int length() {
           return len;    }    //返回线性表中第 i 个数据    public E get(int i) throws Exception {
           if (i < 0 || i >= len)            throw new Exception("查找范围不正确,第" + i + "个元素不存在");        return (E) listElem[i];    }    //在第 i 个数据之前插入数据    public void insert(int i, E e) throws Exception {
           if (i < 0 || i > len)            throw new Exception("插入范围不正确,第" + i + "个元素不存在");        //若线性表已满，则扩容一倍        if (len == listElem.length)            listElem = Arrays.copyOf(listElem, 2 * listElem.length);        //数据后移一位，让j=i时挑出，将数据插入i        for (int j = len; j > i; j--)            listElem[j] = listElem[j - 1];        listElem[i] = e;        len++;    }    //删除并返回线性表中第 i 个数据    public E remove(int i) throws Exception {
           if (i < 0 || i >= len)            throw new Exception("删除范围不正确,第" + i + "个元素不存在");        E e = (E) listElem[i];        //j=len-1 时跳出循环，最后一步为 listElem[len-2] = listElem[len-1]        for (int j = i; j < len - 1; j++)            listElem[j] = listElem[j + 1];        len--;        return e;    }    //返回线性表中数据元素的位序号，若线性表中不包含返回-1    public int indexOf(E e) {
           for (int i = 0; i < len; i++) {
               if (listElem[i].equals(e)) {
                   return i;            }        }        return -1;    }    //输出线性表中的元素    public void display() {
           for (int i = 0; i < len; i++)            System.out.print(listElem[i] + " ");        System.out.println();    }    public static void main(String[] args) throws Exception {
           SequentialLinearList
    
      list = new SequentialLinearList<>(3);        list.insert(0, 'a');        list.insert(1, 'b');        list.insert(2, 'c');        list.remove(2);        list.display();        list.get(1);        System.out.println(list.indexOf('a'));        list.insert(2,'c');        list.insert(3,'d');        System.out.println(list.length());        System.out.println(list.listElem.length);    }}

二、带头结点的单链表

1) 特点

1.采用链式存储方式存储的线性表

2.每一个节点包含存放数据元素值的数据域和存放指向逻辑上相邻节点的指针域。

3.一个节点包含一个指针。

4.由他的头指针来唯一标识它。

5.最后一个节点没有后继。

6.头结点不存放具体的值，指针域指向第一个节点。

在这里插入图片描述

2) 带头结点单链表实现

package com.hly.dataStructure.linkedList;/** * @author :hly * @github :https://github.com/huangliangyun * @blog :http://www.javahly.com/ * @CSDN :blog.csdn.net/Sirius_hly * @date :2019/3/8 *///带头结点的单链表public class LinkedList
   
    > {
       //定义静态内部类节点    private static class Node
    
     {
           public AnyType data;        public Node
     
       next;        public Node() {
               this(null,null);        }        public Node(AnyType data) {
               this.data = data;        }        public Node(AnyType data, Node
      
        next) {
               this.data = data;            this.next = next;        }    }    //头指针    private Node
       
         head;    private int size;    public LinkedList() {
           size = 0;        head = new Node<>();    }    public LinkedList(Node
        
          head, int size) { this.head = head; this.size = size; } public int size(){ return size; } //将单链表置成空表 public void clear(){ head.data = null; head.next = null; } //判断单链表是否为空 public boolean isEmpty(){ return head.next == null; } //求单链表的长度 public int length(){ int length = 0; Node
         
           p = head.next; while(p!=null){ p = p.next; length ++ ; } return length; } //获取第 i 个节点 public AnyType get(int i) throws Exception { Node
          
            p = head.next; int j = 0; while (j
           
            i,i<0时不合法 //p==null,说明了已经退出了while循环，i大于了表长-1 if(p==null||j>i) throw new Exception("第"+i+"个节点不存在！"); return p.data; } //在单链表中第i个节点前插入一个新的值 public void add(int i,AnyType data) throws Exception { int j = -1; Node
            
              p = head; //找到 i 的前驱节点 p while(j
             
              i-1||p ==null) throw new Exception("插入位置不合法"); Node
              
                s = new Node<>(data); s.next = p.next; p.next = s; } //删除单链表中第 i 个节点,返回该节点 public AnyType remove(int i) throws Exception { Node
               
                 p = head; int j = -1; while(j
                
                 i-1||p.next==null) throw new Exception("删除位置不合法"); Node
                 
                   node = p.next; p.next = p.next.next; return node.data; } //查找到值为x的节点 public int indexOf(AnyType x){ Node
                  
                    p = head.next; int i = 0; while (p!=null&&!p.data.equals(x)){ p = p.next; i++; } if(p!=null)//遍历单链表，如果 p 为 null 则说明没有找到 return i; return -1; } //输出所有的节点 public void display(){ Node
                   
                     p = head.next; while(p!=null){ System.out.print(p.data+" "); p = p.next; } System.out.println(); } //Test public static void main(String[] args) throws Exception { LinkedList
                    
                      list = new LinkedList<>(); //添加数据 for(int i=0;i<3;i++) list.add(list.length(),i); //输第 i 个元素 list.display(); //单链表的长度 System.out.println("单链表的长度："+list.length()); //删除元素 System.out.println("删除元素："+list.remove(0)); //查找值为 x 的节点 list.display(); System.out.println("查找值为 x 的节点："+list.indexOf(2)); }}

3) 带头结点单链表分析

(1) 插入新节点
//在单链表中第i个节点前插入一个新的值    public void add(int i,AnyType data) throws Exception {
           int j = -1;        Node
   
     p = head;        //找到 i 的前驱节点 p        while(j
    
     i-1||p ==null)            throw new Exception("插入位置不合法");        Node
     
       s = new Node<>(data);        s.next = p.next;        p.next = s;    }

插入前

在这里插入图片描述

插入后

在这里插入图片描述

若要在第 i 个节点之前插入新的节点，则需要先找出第 i 个节点的前驱节点。

由于是带头结点的单链表，所以 j 从 -1 开始，0 代表首节点，while 循环中临界条件为 j< i-1 当 j = i-1 时 退出，说明此事 j 已经是 第 i-1 个节点。

不合法情况：

1、j>i-1,由于 i 不能小于0，当i = -1 时，-1 < -1-1 = -1 <-2 while 循环直接退出，所以不合法。当 i 为 0 时 ，-1 = -1 ，while 循环不执行，直接在头结点后面插入数据。

2、p == null ,由于 0 <=i<=length(), -1 代表头结点，0 代表首节点，当 i 大于表长时，此条件成立。

(2) 删除节点
//删除单链表中第 i 个节点,返回该节点    public AnyType remove(int i) throws Exception {
           Node
   
     p = head;//p指向1头结点        int j = -1;//头结点下标为-1，首节点为0        while(j
    
     i-1||p.next==null)            throw new  Exception("删除位置不合法");        Node
     
       node = p.next;        p.next = p.next.next;        return node.data;    }

在这里插入图片描述

在这里插入图片描述
不合法情况：

1、j>i-1, i 不能小于 0 ，当 i 小于 0 时，while 循环直接退出，例 i =-1 ，j = -1,循环退出时，-1>-1-1.

2、p.next == null , 删除位置大于单链表的长度。

三、不带头结点的单链表

1) 特点

在这里插入图片描述

2) 不带头结点单链表实现

package com.hly.dataStructure.linkedList;/** * @author :hly * @github :https://github.com/huangliangyun * @blog :http://www.javahly.com/ * @CSDN :blog.csdn.net/Sirius_hly * @date :2019/3/9 *///不带头结点的单链表public class LinkedListWithoutHead
   
    > {
       //定义节点    private static class Node
    
      {
           private Node
     
       next;        private AnyType data;        public Node() {
               this(null, null);        }        public Node(AnyType data) {
               this.data = data;        }        public Node(Node
      
        head, AnyType data) {
               this.next = head;            this.data = data;        }    }    private Node
       
         head;//头指针    private int size;    public LinkedListWithoutHead(Node
        
          head, int size) { this.head = head; this.size = size; } public LinkedListWithoutHead() { this(null, 0); } //返回单链表的大小 public int size() { return size; } //返回单链表的长度 public int length() { int j = 0; Node
         
           p = head; if (head == null)//头指针为空，则长度为 0 return 0; while (p != null) { p = p.next; j++; } return j; } //返回单链表的位置 public int indexOf(AnyType x) { int j = 0; Node
          
            p = head; while (p != null && !p.data.equals(x)) { p = p.next; j++; } if (p != null) return j; return -1; } //返回第 i 个节点 public AnyType get(int i) throws Exception { Node
           
             p = head; int j = 0; while (j < i && p != null) { p = p.next; j++; } if (j > i || p == null) throw new Exception("查找位置不合法"); return p.data; } //插入节点 public void add(int i, AnyType x) throws Exception { Node
            
              p = head; int j = 0; while (j < i - 1 && p != null) { p = p.next; j++; } if (j > i && p == null) throw new Exception("插入位置不合法!"); Node
             
               s = new Node<>(x); //插入的位置为表头时 if (i == 0) { s.next = head; head = s; size++; } else { s.next = p.next; p.next = s; size++; } } //删除并返回节点 public AnyType remove(int i) throws Exception { Node
              
                p = head; int j = 0; while (j < i - 1 && p != null) { p = p.next; j++; } if (j > i || p == null) throw new Exception("删除位置不合法"); Node
               
                 node; //如果删除的是首节点 if (i == 0) { node = head; head = head.next; } else { node = p.next; p.next = p.next.next; size--; } p.next = p.next.next; size--; return node.data; } //输出所有节点 public void display() { Node
                
                  p = head;//从头指针指向的第一个节点开始 while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } //单链表就地逆置 public Node
                 
                   reverse() { Node
                  
                    p = head; head = null; while (p != null) { Node
                   
                     q = p.next; p.next = head; head = p; p = q; }/// return head; } public static void main(String[] args) throws Exception { LinkedListWithoutHead
                    
                      list = new LinkedListWithoutHead<>(); //添加数据 for (int i = 0; i < 3; i++) list.add(list.length(), i); list.display(); //单链表的长度 System.out.println("单链表的长度：" + list.length()); //查找值为 x 的节点 System.out.println("查找值为 x 的节点："+list.indexOf(2)); //就地逆置 list.reverse(); list.display(); //删除元素 System.out.println("删除第i个元素：" + list.remove(0)); list.display(); }}

3) 不带头结点单链表分析

(1) 插入新节点
//插入节点    public void add(int i, AnyType x) throws Exception {
           Node
   
     p = head;        int j = 0;        while (j < i - 1 && p != null) {
               p = p.next;            j++;        }        if (j > i && p == null)            throw new Exception("插入位置不合法!");        Node
    
      s = new Node<>(x);        //插入的位置为表头时        if (i == 0) {
               s.next = head;            head = s;            size++;        } else {
               s.next = p.next;            p.next = s;            size++;        }    }

在表头插入节点和在其他位置插入节点不同,不同点在于不带头指针的单链表需要将头指针指向新的节点，而带头结点到的单链表的头指针一直指向头结点。

在这里插入图片描述
在这里插入图片描述

(1) 删除节点
//删除并返回节点    public AnyType remove(int i) throws Exception {
           Node
   
     p = head;        int j = 0;        while (j < i - 1 && p != null) {
               p = p.next;            j++;        }        if (j > i || p == null)            throw new Exception("删除位置不合法");        Node
    
      node;        //如果删除的是首节点        if (i == 0) {
               node = head;            head = head.next;        } else {
               node = p.next;            p.next = p.next.next;            size--;        }        p.next = p.next.next;        size--;        return node.data;    }

若删除的是首节点，则需要改变头结点的指针。

(3) 就地逆置节点
//单链表就地逆置    public Node
   
     reverse() {
           Node
    
      p = head;        head = null;        while (p != null) {
               Node
     
       q = p.next;            p.next = head;            head = p;            p = q;        }///        return head;    }

从第二个节点开始，把所有的节点都放到第一个节点的后面。

1、初始化，将头指针指向的节点赋值给 p。

在这里插入图片描述

2、进入 while 循环，如果 p 不为空 ，将 p 的下一个节点赋值为 q。

在这里插入图片描述

3、p 为第一个节点，将p的下一个节点赋值为 null，第一个节点变成最后一个节点。

在这里插入图片描述

4、把 p 赋值给 head ，q 赋值给p，依次交换位置。

在这里插入图片描述

5、将 p 的指针指向 head(A) 节点。

在这里插入图片描述

6、再次向后移动。

在这里插入图片描述

7、将 p 的下一个节点指向 head(B)

在这里插入图片描述

8、最后一步，将 head 指向 p 完成就地逆置，此时 p 为null，退出循环。

在这里插入图片描述

四、双向循环链表

1) 特点

1、两个指针域，一个指向前驱节点，一个指向后继节点。

2、首尾相连。

在这里插入图片描述

2) 实现

package com.hly.dataStructure.linkedList;/** * @author :hly * @github :https://github.com/huangliangyun * @blog :http://www.javahly.com/ * @CSDN :blog.csdn.net/Sirius_hly * @date :2019/3/11 *///带头结点的双向循环链表public class LinkedListOfDuplex
   
    > {
       private static class Node
    
      {
           AnyType data;        private Node
     
       prior;        private Node
      
        next;        public Node() {
               this(null);        }        public Node(AnyType data) {
               this(data, null, null);        }        public Node(AnyType data, Node
       
         prior, Node
        
          next) { this.data = data; this.prior = prior; this.next = next; } } private Node
         
           head;//初始化头结点 int size; public LinkedListOfDuplex() { head = new Node<>();//初始化头结点 head.prior = head; head.next = head; size = 0; } //获取长度 public int length() { Node
          
            p = head.next; int j = 0; while (p != head) { p = p.next; j++; } return j; } public boolean isEmpty() { return head.next == null; } public void clear() { head.next = null; } //获取第i个节点的数据 public AnyType get(int i) { Node
           
             p; int j; if (i < size / 2) { p = head.next; j = 0; while (j < i) { p = p.next; j++; } } else { p = head; j = size; while (j > i) { p = p.prior; j--; } } return p.data; } //就地逆置 public void reverse() { Node
            
              p, q, k; p = head.next; q = p.next; while (p != head) { k = q.next; q.next = p; p.prior = q; p = q; q = k; } q.next = p; p.prior = q; } //添加数据 public void add(int i, AnyType x) throws Exception { Node
             
               p = head.next;//指向首节点 int j = 0; while (p != head && j < i) { p = p.next; j++; } if (j != i) throw new Exception("插入位置不合法"); Node
              
                s = new Node<>(x); p.prior.next = s; s.prior = p.prior; s.next = p; p.prior = s; size++; } //删除数据 public AnyType remove(int i) throws Exception { Node
               
                 p = head.next; int j = 0; while (p != head && j < i) { p = p.next; j++; } if (j != i) throw new Exception("删除位置不合法"); Node
                
                  node = p; p.prior.next = p.next; p.next.prior = p.prior; size--; return node.data; } public void display() { Node
                 
                   p = head.next; while (p != head) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } //Test public static void main(String[] args) throws Exception { LinkedListOfDuplex
                  
                    list = new LinkedListOfDuplex<>(); //添加数据 for (int i = 0; i < 6; i++) list.add(list.length(), i); list.display(); //单链表的长度 System.out.println("单链表的长度：" + list.length()); //输出第 i 个元素，第 0 个开始 System.out.println("输出第 i 个元素：" + list.get(2)); //删除元素 System.out.println("删除元素：" + list.remove(2)); list.display(); }}

3) 分析

(1) 插入节点
//添加数据    public void add(int i, AnyType x) throws Exception {
           Node
   
     p = head.next;//指向首节点        int j = 0;        while (p != head && j < i) {
               p = p.next;            j++;        }        if (j != i)            throw new Exception("插入位置不合法");        Node
    
      s = new Node<>(x);        p.prior.next = s;        s.prior = p.prior;        s.next = p;        p.prior = s;        size++;    }

在这里插入图片描述

1、while 循环 j<i,在第 i 个节点之前插入节点，与单链表不同，双向链表不需要找前驱节点。

2、不合法情况：

j!=i,当 i 大于表长时，while 循环到了 head 提前退出，此时 j < i ;

3、指针更改顺序

(1)p.prior.next = s;

(2)s.prior = p.prior;
(3)s.next = p;
(4)p.prior = s;

第 4 条语句必须在第 1 和 第 2 条语句之后，如果第 4 条语句先执行，p 的前驱将会直接成为 s ，第 1 ，2 条语句将成为死循环。

(2) 删除节点
//删除数据    public AnyType remove(int i) throws Exception {
           Node
   
     p = head.next;        int j = 0;        while (p != head && j < i) {
               p = p.next;            j++;        }        if (j != i)            throw new Exception("删除位置不合法");        Node
    
      node = p;        p.prior.next = p.next;        p.next.prior = p.prior;        size--;        return node.data;    }

在这里插入图片描述

两条语句的执行顺序可以调换。

(3) 就地逆置
//就地逆置    public void reverse() {
           Node
   
     p, q, k;        p = head.next;        q = p.next;        while (p != head) {
               k = q.next;            q.next = p;            p.prior = q;            p = q;            q = k;        }        q.next = p;        p.prior = q;    }

1、初始化

在这里插入图片描述

2、改变了 a0 的前驱和 a1 的后继。

在这里插入图片描述
3、指针向后移动
在这里插入图片描述
4、继续改变下一个节点的前驱和后继
在这里插入图片描述
5、指针向后移动
在这里插入图片描述
6、这一步将 a0 复制给 k ，然后改变指针指向。
在这里插入图片描述
7、退出 while 循环
在这里插入图片描述
8、退出 while 循环后执行剩下的两步。
在这里插入图片描述
—END—

ABOUT

公众号：【星尘Pro】

github：

推荐阅读

你可能感兴趣的文章
PHP 7 的五大新特性
查看>>
php实现socket(转)
查看>>
PHP底层的运行机制与原理
查看>>
深入了解php底层机制
查看>>
PHP中的stdClass 【转】
查看>>
XHProf-php轻量级的性能分析工具
查看>>
PHP7新特性 What will be in PHP 7/PHPNG
查看>>
比较strtr, str_replace和preg_replace三个函数的效率
查看>>
ubuntu 下编译PHP5.5.7问题：configure: error: freetype.h not found.
查看>>
PHP编译configure时常见错误 debian centos
查看>>
configure: error: Please reinstall the BZip2 distribution
查看>>
OpenCV gpu模块样例注释:video_reader.cpp
查看>>
【增强学习在无人驾驶中的应用】
查看>>
OpenCV meanshift目标跟踪总结
查看>>
人工神经网络——神经元模型介绍
查看>>
Windows 窗口底层原理
查看>>
一种函数指针的运用
查看>>
今天，Python信息量很大！
查看>>
Flash 已死，Deno 当立？
查看>>
编程差的程序员，90%都是吃了数学的亏！骨灰级开发：方法不对，努力也白费...
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-09-21 04:37:00   当前IP: 3.143.239.44   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我