数据结构-1-线性表

老婆出轨  金牌会员 | 2025-1-3 11:54:12 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 881|帖子 881|积分 2643

数据结构-1-线性表

1、线性表的概念
线性表是有N个数据元素构成的有序序列，所有元素的性子必须相同，元素之间呈线性关系，即除开始元素以外，每个元素只有唯一的前驱， 除终端元素之外每个元素只有唯一的后继。
2、分类
线性表根据存储结构可以分别为顺序表和链表（包含单链表、双链表以及循序链表）
顺序表的特点：
逻辑结构上它是一种线性结构，其特点是元素在逻辑上相邻，即顺序表中在逻辑结构上相邻的数据元素在存储结构上也相邻。
物理结构采用数组存放元素，所有内存单元地址必须是连续的。既可以顺序查找，也可以随机查找。
链表的特点：
逻辑结构它是一种线性结构，它通过节点之间的链接来实现数据的存储和访问。每个节点包含数据域和指针域，数据域存储数据元素，指针域指向下一个节点的地址。
物理结构是物理存储单元上可连续也可非连续且非顺序的存储结构
3、单链表
节点示例：
  1. @Data
  2. public class Node {
  3.     private Object data;
  4.     private Node next;
  6.     public Node() {}
  7.     public Node(Object data, Node next) {
  8.         this.data = data;
  9.         this.next = next;
  10.     }
  11. }
复制代码


  • 构建单链表
  1. public static Node getLink() {
  2.     Node head = new Node();
  3.     Node tail = head;
  5.     for (int i = 0; i < 10; i++) {
  6.         Node node = new Node(i, null);
  7.         if (i == 0) {
  8.             head.setNext(node);
  9.         } else {
  10.             tail = tail.getNext();
  11.             tail.setNext(node);
  12.         }
  13.     }
  15.     return head;
  16. }
复制代码


  • 打印链表
  1. public static void  printLink(Node head) {
  2.    Node headLoop = head;
  3.    while(headLoop != null) {
  4.        if (headLoop.getData() != null) {
  5.            if (headLoop.getNext() != null) {
  6.                System.out.print("Node[data=" + headLoop.getData() + "]->");
  7.            } else {
  8.                System.out.print("Node[data=" + headLoop.getData() + "]");
  9.            }
  10.        } else {
  11.            System.out.print("head->");
  12.        }
  13.        headLoop = headLoop.getNext();
  14.    }
  15.    System.out.println();
  16. }
复制代码
打印结果



  • 插入链表
  1. public static Node insertLink(int index, Object data) {
  2.     Node head = getLink();
  3.     Node tail = head;
  4.     int i = 0;
  5.     while (i++ < index) {
  6.         tail = tail.getNext();
  7.     }
  8.     Node newNode = new Node(data,null);
  9.     Node tmp = tail.getNext();
  10.     tail.setNext(newNode);
  11.     newNode.setNext(tmp);
  12.     return head;
  13. }
复制代码


  • 反转链表
  1. public static Node reverseLink() {
  2.    Node head = getLink();
  3.    Node p = head.getNext(); // 指向首节点
  4.    head.setNext(null);  // 将头节点指向新的空链表
  5.    Node q;
  6.    while (p != null) {
  7.        q = p.getNext();   // 指向当前节点p的下个节点
  8.        p.setNext(head.getNext());  // 设置当前节点的下个节点为头节点指向的下个节点
  9.        head.setNext(p);  // 将头节点指向当前节点
  10.        p = q;  // 移动当前节点到下个节点
  11.    }
  12.    return head;
  13. }
复制代码


  • 查找最大节点
  1. public static Node findMax() {
  2.     Node head = getLink();
  3.     Node maxNode = null;
  4.     int  maxData = 0;
  5.     while(head != null) {
  6.         if (head.getData() != null && (int)head.getData() > maxData) {
  7.             maxNode = head;
  8.         }
  9.         head = head.getNext();
  10.     }
  11.     return maxNode;
  12. }
复制代码


  • 删除指定节点
  1. public static Node remove(Object data) {
  2.    Node head        = getLink();
  3.    System.out.println("---删除前链表---");
  4.    printLink(head);
  6.    Node pre         = head;
  7.    Node newHead     = head;
  8.    Node removedNode = null;
  9.    while (head != null) {
  10.        if (null != head.getData() && head.getData().equals(data)) {
  11.            removedNode = head;
  12.            pre.setNext(head.getNext());
  13.        }
  14.        pre  = head;
  15.        head = head.getNext();
  16.    }
  17.    System.out.println("---删除后链表---");
  18.    printLink(newHead);
  19.    return removedNode;
  20. }
复制代码
打印结果:



  • 更新节点
  1. // 如果链表中有多个相同的目标节点，则一并更新
  2. public static boolean update(Object target, Object newData) {
  3.    boolean backResult = false;
  4.     Node head = getLink();
  5.     while (head != null) {
  6.         if (head.getData() != null && head.getData().equals(target)) {
  7.             head.setData(newData);
  8.             backResult = true;
  9.             // break;  如果仅更新第一个目标节点，则此处退出即可
  10.         }
  11.     }
  12.     return backResult;
  13. }
复制代码
4、双链表
节点示例：
  1. @Data
  2. public class DoubleNode {
  3.     private Object data;
  4.     private DoubleNode pre;
  5.     private DoubleNode next;
  6.     public DoubleNode() {}
  7.     public DoubleNode(Object data, DoubleNode pre, DoubleNode next) {
  8.         this.data = data;
  9.         this.pre  = pre;
  10.         this.next = next;
  11.     }
  12.     @Override
  13.     public String toString() {
  14.         return "DoubleNode{" +
  15.                 "data=" + data +
  16.                 ", pre=" + pre +
  17.                 ", next=" + next +
  18.                 '}';
  19.     }
  20. }
复制代码


  • 构建双链表
  1. public static DoubleNode getDoubleLink() throws Exception {
  2.     DoubleNode head = new DoubleNode();
  3.     DoubleNode cur = head; // 当前节点
  4.     for (int i = 0; i < 10; i++) {
  5.         DoubleNode node = new DoubleNode(i, null, null);
  6.         if (i == 0) {
  7.             head.setNext(node);
  8.             node.setPre(head);
  9.         } else {
  10.             cur = cur.getNext();
  11.             cur.setNext(node);
  12.             node.setPre(cur);
  13.         }
  14.     }
  15.     return head;
  16. }
复制代码


  • 打印链表
  1. public static void  printLink(DoubleNode head) {
  2.    DoubleNode headLoop = head;
  3.    while(headLoop != null) {
  4.        if (headLoop.getData() != null) {
  5.            if (headLoop.getNext() != null && headLoop.getPre() != null) {
  6.                System.out.print("<-Node[data=" + headLoop.getData() + "]->");
  7.            }
  8.            else if (headLoop.getNext() != null && headLoop.getPre() == null) {
  9.                System.out.print("head->");
  10.            }
  11.            else {
  12.                System.out.print("<-Node[data=" + headLoop.getData() + "]");
  13.            }
  14.        } else {
  15.            System.out.print("head->");
  16.        }
  17.        headLoop = headLoop.getNext();
  18.    }
  19.    System.out.println();
  20. }
复制代码
打印结果



  • 插入节点
  1. public static void add(int index, Object data) {
  2.     System.out.println("-----原始链表----");
  3.     DoubleNode head = getDoubleLink();
  4.     printLink(head);
  5.     DoubleNode cur = head;
  6.     int i = 0;
  7.     while (i++ < index) {
  8.         cur = cur.getNext();
  9.     }
  10.     DoubleNode newNode = new DoubleNode(data,null, null);
  11.     DoubleNode tmp = cur.getNext();
  12.     cur.setNext(newNode);
  13.     newNode.setPre(cur);
  14.     newNode.setNext(tmp);
  15.     tmp.setPre(newNode);
  16.     System.out.println("---添加节点后链表---");
  17.     printLink(head);
  18. }
复制代码
打印结果



  • 删除节点
  1. public static DoubleNode remove(Object data) {
  2.     DoubleNode head        = getDoubleLink();
  3.     System.out.println("---删除前链表---");
  4.     printLink(head);
  6.     DoubleNode cur         = head;
  7.     DoubleNode newHead     = head;
  8.     DoubleNode removedNode = null;
  9.     while (head != null) {
  10.         if (null != head.getData() && head.getData().equals(data)) {
  11.             removedNode = head;
  12.             cur.setNext(head.getNext());
  13.             cur.setPre(head.getPre());
  14.         }
  15.         cur  = head;
  16.         head = head.getNext();
  17.     }
  18.     System.out.println("---删除后链表---");
  19.     printLink(newHead);
  20.     return removedNode;
  21. }
复制代码
打印结果



  • 更新节点
  1. public static void update(int index, Object newData) {
  2.       System.out.println("-----原始链表----");
  3.       DoubleNode head = getDoubleLink();
  4.       printLink(head);
  5.       DoubleNode cur = head;
  6.       int i = 0;
  7.       while (i++ < index) {
  8.           cur = cur.getNext();
  9.       }
  10.       cur.setData(newData);
  11.       System.out.println("---添加节点后链表---");
  12.       printLink(head);
  13. }
复制代码
打印结果



  • 查找节点
  1. public static DoubleNode get(int index) {
  2.     DoubleNode head = getDoubleLink();
  3.     DoubleNode cur  = head.getNext();
  4.     int i = 0;
  5.     while(i++ < index) {
  6.         if (cur != null && cur.getNext() != null) {
  7.             cur = cur.getNext();
  8.         } else {
  9.             if (i <= index) throw new IndexOutOfBoundsException();
  10.         }
  11.     }
  12.     return cur;
  13. }
复制代码
get(9) 打印结果

get(10)打印结果



  • 反转链表
  1. public static DoubleNode reverseLink() {
  2.         DoubleNode head = getDoubleLink();
  3.         DoubleNode p = head.getNext(); // 当前节点
  4.         head.setNext(null);
  5.         head.setPre(null);
  6.         DoubleNode q;
  7.         while(p != null) {
  8.             q = p.getNext(); // 指向了下个节点
  9.             p.setNext(head.getNext());
  10.             p.setPre(head.getPre());
  11.             head.setNext(p); // 指向当前节点
  12.             head.setPre(q);  // 前向节点指向下个节点
  13.             p = q;  // 移动当前节点到下个节点
  14.         }
  15.         return head;
  16.     }
复制代码
打印反转后的结果

5、循环单链表


  • 利用单向节点构建循环单链表
  1. public static Node getCircleLink() {
  2.     Node head = new Node();
  3.     Node tail = head;
  4.     for (int i = 0; i < 10; i++) {
  5.         Node node = new Node(i, null);
  6.         if (i == 0) {
  7.             head.setNext(node);
  8.             tail = head.getNext();
  9.         } else {
  10.             tail.setNext(node);
  11.             tail = tail.getNext();
  12.         }
  13.     }
  14.     tail.setNext(head); // 设置循环链表
  15.     return head;
  16. }
复制代码


  • 打印循环单链表
  1. public static void  printCircleLink(Node head) {
  2.     Node headLoop = head;
  3.     do {
  4.         if (headLoop.getData() != null) {
  5.             if (headLoop.getNext() != head) {
  6.                 System.out.print("Node[data=" + headLoop.getData() + "]->");
  7.             } else {
  8.                 System.out.print("Node[data=" + headLoop.getData() + "]");
  9.             }
  10.         } else {
  11.             System.out.print("head->");
  12.         }
  13.         headLoop = headLoop.getNext();
  14.     } while (headLoop != head); // 注意结束标识
  15.     System.out.println();
  16. }
复制代码
打印结果

对循环单链表的增、删、改、查与单链表类似， 不再例证
6、循环双链表


  • 利用双向节点构建循环单链表
  1. public static DoubleNode getDoubleCircleLink() {
  2.     DoubleNode head = new DoubleNode();
  3.     DoubleNode cur = head; // 当前节点
  4.     for (int i = 0; i < 10; i++) {
  5.         DoubleNode node = new DoubleNode(i, null, null);
  6.         if (i == 0) {
  7.             head.setNext(node);
  8.             node.setPre(head);
  9.             cur = head.getNext();
  10.         } else {
  11.             cur.setNext(node);
  12.             node.setPre(cur);
  13.             cur = cur.getNext();
  14.         }
  15.     }
  16.     // 设置循环表示
  17.     cur.setNext(head);
  18.     head.setPre(cur);
  19.     return head;
  20. }
复制代码


  • 打印循环双向链表
  1. public static void  printCircleLink(DoubleNode head) {
  2.     DoubleNode headLoop = head;
  3.     do {
  4.         if (headLoop.getData() != null) {
  5.             if (headLoop.getNext() != head) {
  6.                 System.out.print("<-Node[data=" + headLoop.getData() + "]->");
  7.             }
  8.             else {
  9.                 System.out.print("<-Node[data=" + headLoop.getData() + "]");
  10.             }
  11.         } else {
  12.             System.out.print("head->");
  13.         }
  14.         headLoop = headLoop.getNext();
  15.     } while (headLoop != head);
  16.     System.out.println();
  17. }
复制代码
打印结果

对循环双向链表的增、删、改、查与非循环双向链表类似， 不再例证
7、顺序表
对顺表的操作即是对数组的操作, 这里不思量扩容问题
  1. public class CArrayList {
  2.     private final int defaultCapacity = 10;
  3.     private Object[] array;
  4.     private int size = 0;
  5.     private int capacity;
  6.     public CArrayList() {
  7.         array = new Object[defaultCapacity];
  8.     }
  9.     public CArrayList(int capacity) {
  10.         this.capacity = capacity;
  11.         array = new Object[capacity];
  12.     }
  13.     // 添加元素
  14.     public void add(Object value) {
  15.         if (size == array.length) throw new RuntimeException("Container is full, not allowed to add. ");
  16.         for (int i = 0; i < array.length; i++) {
  17.             if (array[i] == null) {
  18.                 array[i] = value;
  19.                 size++;
  20.                 break;
  21.             }
  22.         }
  23.     }
  24.      // 添加元素
  25.     public void add(int index, Object value)  {
  26.         if (size == array.length) throw new RuntimeException("Container is full, not allowed to add. ");
  27.         if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");
  28.         for (int i = array.length-1; i > index; i++) {
  29.             array[i] = array[i-1];
  30.         }
  31.         array[index] = value;
  32.         size++;
  33.     }
  34.      // 删除元素
  35.     public void remove(Object value) {
  36.         if (value == null) throw new RuntimeException("被删除的元素不能为空");
  37.         for (int i = 0; i < array.length; i++) {
  38.             if (array[i] == value || array[i].equals(value)) {
  39.                 array[i] = null;
  40.                 size--;
  41.                 break;
  42.             }
  43.         }
  44.     }
  45.      // 更新元素
  46.     public void update(int index, Object value) {
  47.         if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");
  48.         array[index] = value;
  49.     }
  51.     // 获取元素
  52.     public Object get(int index) {
  53.         if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");
  54.         return array[index];
  55.     }
  56. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

正序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

老婆出轨

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表