基本資料結構
前言
本文為所有常用資料結構的簡單實作，持續更新中......
以下為已實作資料結構的概覽
1. 線性表: 順序表、單向鏈表、雙向鏈表、堆疊
線性表
順序表
1 /** 2 * 順序表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class SequenceList<T> { 8 private final Object[] data; 9 private int length; 10 11 // 創建指定容量的順序表 12 public SequenceList(int capacity) { 13 data = https://www.cnblogs.com/kkelin/archive/2022/09/14/new Object[capacity]; 14 length = 0; 15 } 16 17 // 回傳資料長度 18 public int length() { 19 return length; 20 } 21 22 // 在index位置上插入元素 23 public void insert(int index, T data) { 24 if (index >= 0 && index <= length && index < this.data.length) { // 保證插入的位置不超過最大容量 25 for (int i = length - 1; i >= index; i--) { 26 this.data[i + 1] = this.data[i]; 27 } 28 this.data[index] = data; 29 length++; 30 } 31 } 32 33 // 洗掉index位置上的值 34 public void delete(int index) { 35 if (index >= 0 && index < length) { 36 for (int i = index; i < length; i++) { 37 data[i] = data[i + 1]; 38 } 39 data[length - 1] = null; 40 length--; 41 } 42 } 43 44 // 修改index位置上的值 45 public void set(int index, T data) { 46 if (index >= 0 && index < length) { 47 this.data[index] = data; 48 } 49 } 50 51 // 獲取index位置上的值 52 public T get(int index) { 53 if (index >= 0 && index < length) { 54 return (T) data[index]; 55 } else { 56 return null; 57 } 58 } 59 60 // 搜索data的索引，若不存在，則回傳-1 61 public int find(T data) { 62 for (int index = 0; index < length; index++) { 63 if (this.data[index].equals(data)) { 64 return index; 65 } 66 } 67 return -1; 68 } 69 70 // 列印所有值 71 public void print() { 72 System.out.print("["); 73 if (length > 0) { 74 System.out.print(data[0]); 75 for (int i = 1; i < length; i++) { 76 System.out.print(", " + data[i]); 77 } 78 } 79 System.out.print("]\n"); 80 } 81 }
單向鏈表
1 /** 2 * 單向鏈表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class SinglyLinkedList<T> { 8 private Node<T> head; 9 private int length; 10 11 // 創建單向鏈表 12 public SinglyLinkedList() { 13 } 14 15 // 回傳資料長度 16 public int length() { 17 return length; 18 } 19 20 // 在index位置上插入一個值 21 public void insert(int index, T data) { 22 if (index >= 0 && index <= length) { 23 if (index == 0) { 24 if (length == 0) { 25 this.head = new Node<>(null, data); 26 } else { 27 this.head = new Node<>(this.head, data); 28 } 29 } else { 30 Node<T> p = head; // 插入節點的前驅 31 for (int i = 1; i < index; i++) { 32 p = p.next; 33 } 34 if (index == length) { 35 p.next = new Node<>(null, data); 36 } else { 37 p.next = new Node<>(p.next, data); 38 } 39 } 40 this.length++; 41 } 42 } 43 44 // 洗掉index位置上的值 45 public void delete(int index) { 46 if (index >= 0 && index < length) { 47 if (index == 0) { 48 head = head.next; 49 } else { 50 Node<T> p = head; // 洗掉節點的前驅 51 for (int i = 1; i < index; i++) { 52 p = p.next; 53 } 54 p.next = p.next.next; 55 } 56 this.length--; 57 } 58 } 59 60 // 修改index位置上的值 61 public void set(int index, T data) { 62 if (index >= 0 && index < length) { 63 Node<T> node = head; 64 for (int i = 0; i < index; i++) { 65 node = node.next; 66 } 67 node.data =https://www.cnblogs.com/kkelin/archive/2022/09/14/ data; 68 } 69 } 70 71 // 獲取index位置上的值 72 public T get(int index) { 73 if (index >= 0 && index < length) { 74 Node<T> node = head; 75 for (int i = 0; i < index; i++) { 76 node = node.next; 77 } 78 return node.data; 79 } else { 80 return null; 81 } 82 } 83 84 // 搜索data值的索引，若不存在，則回傳-1 85 public int find(T data) { 86 Node<T> node = head; 87 int index = 0; 88 while (node != null) { 89 if (node.data.equals(data)) { 90 return index; 91 } 92 index++; 93 node = node.next; 94 } 95 return -1; 96 } 97 98 // 列印所有值 99 public void print() { 100 Node<T> p = head; 101 while (p != null) { 102 System.out.print(p.data + " => "); 103 p = p.next; 104 } 105 System.out.print("null\n"); 106 } 107 108 // 鏈表節點 109 private static class Node<T> { 110 Node<T> next; 111 T data; 112 113 Node(Node<T> next, T data) { 114 this.next = next; 115 this.data =https://www.cnblogs.com/kkelin/archive/2022/09/14/ data; 116 } 117 } 118 }
雙向鏈表
1 /** 2 * 雙向鏈表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class DoubleLinkedLis<T> { 8 private Node<T> head; 9 private int length; 10 11 // 創建雙向鏈表 12 public DoubleLinkedLis() { 13 } 14 15 // 回傳資料長度 16 public int length() { 17 return length; 18 } 19 20 // 在index位置上插入一個值 21 public void insert(int index, T data) { 22 if (index >= 0 && index <= length) { 23 if (index == 0) { 24 if (length == 0) { 25 this.head = new Node(null, null, data); 26 } else { 27 this.head = new Node(null, this.head, data); 28 } 29 } else { 30 Node<T> p = head; // 插入節點的前驅 31 for (int i = 1; i < index; i++) { 32 p = p.next; 33 } 34 if (index == length) { 35 p.next = new Node<>(p, null, data); 36 } else { 37 Node<T> node = new Node<>(p, p.next, data); 38 node.next.prev = node; 39 node.prev.next = node; 40 } 41 } 42 this.length++; 43 } 44 } 45 46 // 洗掉index位置上的值 47 public void delete(int index) { 48 if (index >= 0 && index < length) { 49 if (index == 0) { 50 head = head.next; 51 head.prev = null; 52 } else { 53 Node<T> p = head; // 洗掉節點的前驅 54 for (int i = 1; i < index; i++) { 55 p = p.next; 56 } 57 p.next = p.next.next; 58 if (p.next != null) { 59 p.next.prev = p; 60 } 61 } 62 this.length--; 63 } 64 } 65 66 // 設定index位置上的值 67 public void set(int index, T data) { 68 if (index >= 0 && index < length) { 69 Node<T> node = head; 70 for (int i = 0; i < index; i++) { 71 node = node.next; 72 } 73 node.data =https://www.cnblogs.com/kkelin/archive/2022/09/14/ data; 74 } 75 } 76 77 // 獲取index位置上的值 78 public T get(int index) { 79 if (index >= 0 && index < length) { 80 Node<T> node = head; 81 for (int i = 0; i < index; i++) { 82 node = node.next; 83 } 84 return node.data; 85 } else { 86 return null; 87 } 88 } 89 90 // 搜索data值的索引，若不存在，則回傳-1 91 public int find(T data) { 92 Node<T> node = head; 93 int index = 0; 94 while (node != null) { 95 if (node.data.equals(data)) { 96 return index; 97 } 98 index++; 99 node = node.next; 100 } 101 return -1; 102 } 103 104 // 回傳data值的前驅 105 public T prev(T data) { 106 Node<T> node = head; 107 while (node != null) { 108 if (node.data.equals(data)) { 109 if (node.prev == null) { 110 return null; 111 } else { 112 return node.prev.data; 113 } 114 } 115 node = node.next; 116 } 117 return null; 118 } 119 120 // 回傳data值的后繼 121 public T next(T data) { 122 Node<T> node = head; 123 while (node != null) { 124 if (node.data.equals(data)) { 125 if (node.next == null) { 126 return null; 127 } else { 128 return node.next.data; 129 } 130 } 131 node = node.next; 132 } 133 return null; 134 } 135 136 // 列印所有值 137 public void print() { 138 Node<T> p = head; 139 System.out.print("null <=> "); 140 while (p != null) { 141 System.out.print(p.data + " <=> "); 142 p = p.next; 143 } 144 System.out.print("null\n"); 145 } 146 147 // 鏈表節點 148 private static class Node<T> { 149 Node<T> prev; 150 Node<T> next; 151 T data; 152 153 Node(Node<T> prev, Node<T> next, T data) { 154 this.prev = prev; 155 this.next = next; 156 this.data =https://www.cnblogs.com/kkelin/archive/2022/09/14/ data; 157 } 158 } 159 }
堆疊
1 /** 2 * 堆疊 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class Stack<T> { 8 private Node<T> top; // 堆疊頂節點 9 private int length; 10 11 // 創建一個堆疊 12 public Stack() { 13 } 14 15 // 堆疊的大小 16 public int length() { 17 return length; 18 } 19 20 // 向堆疊頂放入一個元素 21 public void push(T value) { 22 if (top == null) { 23 top = new Node<>(null, value); 24 } else { 25 top = new Node<>(top, value); 26 } 27 } 28 29 // 將堆疊頂元素取出并回傳值 30 public T pop() { 31 if (top != null) { 32 T value =https://www.cnblogs.com/kkelin/archive/2022/09/14/ top.value; 33 top = top.next; 34 return value; 35 } else { 36 return null; 37 } 38 } 39 40 // 回傳堆疊頂元素的值 41 public T top() { 42 if (top != null) { 43 return top.value; 44 } else { 45 return null; 46 } 47 } 48 49 // 列印所有值 50 public void print() { 51 System.out.print("["); 52 if (top != null) { 53 Node<T> p = top; 54 System.out.print(p.value); 55 p = p.next; 56 while (p != null) { 57 System.out.print(" => " + p.value); 58 p = p.next; 59 } 60 } 61 System.out.print("]\n"); 62 } 63 64 // 節點 65 private static class Node<T> { 66 Node<T> next; 67 T value; 68 69 Node(Node<T> next, T value) { 70 this.next = next; 71 this.value =https://www.cnblogs.com/kkelin/archive/2022/09/14/ value; 72 } 73 } 74 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/508109.html
標籤：其他
上一篇：以軟體定義物聯網芯片，以技術融合推動LPWAN2.0泛在物聯
下一篇：平衡二叉樹（ALV樹）旋轉問題