数据结构-1-线性表

数据结构-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企服之家，中国第一个企服评测及商务社交产业平台。