网页源代码复制粘贴提取文字_山西网架公司_域名解析ip地址_百度seo可能消失

数据结构-1-线性表

1、线性表的概念
线性表是有N个数据元素组成的有序序列，所有元素的性质必须相同，元素之间呈线性关系，即除开始元素以外，每个元素只有唯一的前驱，除终端元素之外每个元素只有唯一的后继。
2、分类
线性表根据存储结构可以划分为顺序表和链表（包含单链表、双链表以及循序链表）
顺序表的特点：
逻辑结构上它是一种线性结构，其特点是元素在逻辑上相邻，即顺序表中在逻辑结构上相邻的数据元素在存储结构上也相邻。
物理结构采用数组存放元素，所有内存单元地址必须是连续的。既可以顺序查找，也可以随机查找。
链表的特点：
逻辑结构它是一种线性结构，它通过节点之间的链接来实现数据的存储和访问。每个节点包含数据域和指针域，数据域存储数据元素，指针域指向下一个节点的地址。
物理结构是物理存储单元上可连续也可非连续且非顺序的存储结构
3、单链表
节点示例：

@Data
public class Node {private Object data;private Node next;public Node() {}public Node(Object data, Node next) {this.data = data;this.next = next;}
}

构建单链表

public static Node getLink() {Node head = new Node();Node tail = head;for (int i = 0; i < 10; i++) {Node node = new Node(i, null);if (i == 0) {head.setNext(node);} else {tail = tail.getNext();tail.setNext(node);}}return head;
}

打印链表

public static void  printLink(Node head) {Node headLoop = head;while(headLoop != null) {if (headLoop.getData() != null) {if (headLoop.getNext() != null) {System.out.print("Node[data=" + headLoop.getData() + "]->");} else {System.out.print("Node[data=" + headLoop.getData() + "]");}} else {System.out.print("head->");}headLoop = headLoop.getNext();}System.out.println();
}

打印结果
在这里插入图片描述

插入链表

public static Node insertLink(int index, Object data) {Node head = getLink();Node tail = head;int i = 0;while (i++ < index) {tail = tail.getNext();}Node newNode = new Node(data,null);Node tmp = tail.getNext();tail.setNext(newNode);newNode.setNext(tmp);return head;
}

反转链表

public static Node reverseLink() {Node head = getLink();Node p = head.getNext(); // 指向首节点head.setNext(null);  // 将头节点指向新的空链表Node q;while (p != null) {q = p.getNext();   // 指向当前节点p的下个节点p.setNext(head.getNext());  // 设置当前节点的下个节点为头节点指向的下个节点head.setNext(p);  // 将头节点指向当前节点p = q;  // 移动当前节点到下个节点}return head;
}

查找最大节点

public static Node findMax() {Node head = getLink();Node maxNode = null;int  maxData = 0;while(head != null) {if (head.getData() != null && (int)head.getData() > maxData) {maxNode = head;}head = head.getNext();}return maxNode;
}

删除指定节点

public static Node remove(Object data) {Node head        = getLink();System.out.println("---删除前链表---");printLink(head);Node pre         = head;Node newHead     = head;Node removedNode = null;while (head != null) {if (null != head.getData() && head.getData().equals(data)) {removedNode = head;pre.setNext(head.getNext());}pre  = head;head = head.getNext();}System.out.println("---删除后链表---");printLink(newHead);return removedNode;
}

打印结果:
在这里插入图片描述

更新节点

// 如果链表中有多个相同的目标节点，则一并更新
public static boolean update(Object target, Object newData) {boolean backResult = false;Node head = getLink();while (head != null) {if (head.getData() != null && head.getData().equals(target)) {head.setData(newData);backResult = true;// break;  如果仅更新第一个目标节点，则此处退出即可}}return backResult;
}

4、双链表
节点示例：

@Data
public class DoubleNode {private Object data;private DoubleNode pre;private DoubleNode next;public DoubleNode() {}public DoubleNode(Object data, DoubleNode pre, DoubleNode next) {this.data = data;this.pre  = pre;this.next = next;}@Overridepublic String toString() {return "DoubleNode{" +"data=" + data +", pre=" + pre +", next=" + next +'}';}
}

构建双链表

public static DoubleNode getDoubleLink() throws Exception {DoubleNode head = new DoubleNode();DoubleNode cur = head; // 当前节点for (int i = 0; i < 10; i++) {DoubleNode node = new DoubleNode(i, null, null);if (i == 0) {head.setNext(node);node.setPre(head);} else {cur = cur.getNext();cur.setNext(node);node.setPre(cur);}}return head;
}

打印链表

public static void  printLink(DoubleNode head) {DoubleNode headLoop = head;while(headLoop != null) {if (headLoop.getData() != null) {if (headLoop.getNext() != null && headLoop.getPre() != null) {System.out.print("<-Node[data=" + headLoop.getData() + "]->");}else if (headLoop.getNext() != null && headLoop.getPre() == null) {System.out.print("head->");}else {System.out.print("<-Node[data=" + headLoop.getData() + "]");}} else {System.out.print("head->");}headLoop = headLoop.getNext();}System.out.println();
}

打印结果
在这里插入图片描述

插入节点

public static void add(int index, Object data) {System.out.println("-----原始链表----");DoubleNode head = getDoubleLink();printLink(head);DoubleNode cur = head;int i = 0;while (i++ < index) {cur = cur.getNext();}DoubleNode newNode = new DoubleNode(data,null, null);DoubleNode tmp = cur.getNext();cur.setNext(newNode);newNode.setPre(cur);newNode.setNext(tmp);tmp.setPre(newNode);System.out.println("---添加节点后链表---");printLink(head);
}

打印结果
在这里插入图片描述

删除节点

public static DoubleNode remove(Object data) {DoubleNode head        = getDoubleLink();System.out.println("---删除前链表---");printLink(head);DoubleNode cur         = head;DoubleNode newHead     = head;DoubleNode removedNode = null;while (head != null) {if (null != head.getData() && head.getData().equals(data)) {removedNode = head;cur.setNext(head.getNext());cur.setPre(head.getPre());}cur  = head;head = head.getNext();}System.out.println("---删除后链表---");printLink(newHead);return removedNode;
}

打印结果
在这里插入图片描述

更新节点

 public static void update(int index, Object newData) {System.out.println("-----原始链表----");DoubleNode head = getDoubleLink();printLink(head);DoubleNode cur = head;int i = 0;while (i++ < index) {cur = cur.getNext();}cur.setData(newData);System.out.println("---添加节点后链表---");printLink(head);
}

打印结果
在这里插入图片描述

查找节点

public static DoubleNode get(int index) {DoubleNode head = getDoubleLink();DoubleNode cur  = head.getNext();int i = 0;while(i++ < index) {if (cur != null && cur.getNext() != null) {cur = cur.getNext();} else {if (i <= index) throw new IndexOutOfBoundsException();}}return cur;
}

get(9) 打印结果
在这里插入图片描述
get(10)打印结果

反转链表

public static DoubleNode reverseLink() {DoubleNode head = getDoubleLink();DoubleNode p = head.getNext(); // 当前节点head.setNext(null);head.setPre(null);DoubleNode q;while(p != null) {q = p.getNext(); // 指向了下个节点p.setNext(head.getNext());p.setPre(head.getPre());head.setNext(p); // 指向当前节点head.setPre(q);  // 前向节点指向下个节点p = q;  // 移动当前节点到下个节点}return head;}

打印反转后的结果
在这里插入图片描述
5、循环单链表

使用单向节点构建循环单链表

public static Node getCircleLink() {Node head = new Node();Node tail = head;for (int i = 0; i < 10; i++) {Node node = new Node(i, null);if (i == 0) {head.setNext(node);tail = head.getNext();} else {tail.setNext(node);tail = tail.getNext();}}tail.setNext(head); // 设置循环链表return head;
}

打印循环单链表

public static void  printCircleLink(Node head) {Node headLoop = head;do {if (headLoop.getData() != null) {if (headLoop.getNext() != head) {System.out.print("Node[data=" + headLoop.getData() + "]->");} else {System.out.print("Node[data=" + headLoop.getData() + "]");}} else {System.out.print("head->");}headLoop = headLoop.getNext();} while (headLoop != head); // 注意结束标识System.out.println();
}

打印结果
在这里插入图片描述
对循环单链表的增、删、改、查与单链表类似，不再例证
6、循环双链表

使用双向节点构建循环单链表

 public static DoubleNode getDoubleCircleLink() {DoubleNode head = new DoubleNode();DoubleNode cur = head; // 当前节点for (int i = 0; i < 10; i++) {DoubleNode node = new DoubleNode(i, null, null);if (i == 0) {head.setNext(node);node.setPre(head);cur = head.getNext();} else {cur.setNext(node);node.setPre(cur);cur = cur.getNext();}}// 设置循环表示cur.setNext(head);head.setPre(cur);return head;
}

打印循环双向链表

public static void  printCircleLink(DoubleNode head) {DoubleNode headLoop = head;do {if (headLoop.getData() != null) {if (headLoop.getNext() != head) {System.out.print("<-Node[data=" + headLoop.getData() + "]->");}else {System.out.print("<-Node[data=" + headLoop.getData() + "]");}} else {System.out.print("head->");}headLoop = headLoop.getNext();} while (headLoop != head);System.out.println();
}

打印结果
在这里插入图片描述
对循环双向链表的增、删、改、查与非循环双向链表类似，不再例证
7、顺序表
对顺表的操作即是对数组的操作, 这里不考虑扩容问题

public class CArrayList {private final int defaultCapacity = 10;private Object[] array;private int size = 0;private int capacity;public CArrayList() {array = new Object[defaultCapacity];}public CArrayList(int capacity) {this.capacity = capacity;array = new Object[capacity];}// 添加元素public void add(Object value) {if (size == array.length) throw new RuntimeException("Container is full, not allowed to add. ");for (int i = 0; i < array.length; i++) {if (array[i] == null) {array[i] = value;size++;break;}}}// 添加元素public void add(int index, Object value)  {if (size == array.length) throw new RuntimeException("Container is full, not allowed to add. ");if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");for (int i = array.length-1; i > index; i++) {array[i] = array[i-1];}array[index] = value;size++;}// 删除元素public void remove(Object value) {if (value == null) throw new RuntimeException("被删除的元素不能为空");for (int i = 0; i < array.length; i++) {if (array[i] == value || array[i].equals(value)) {array[i] = null;size--;break;}}}// 更新元素public void update(int index, Object value) {if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");array[index] = value;}// 获取元素public Object get(int index) {if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");return array[index];}
}