数据结构-1-线性表
数据结构-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 voidprintLink(Node head) {
Node headLoop = head;
while(headLoop != null) {
if (headLoop.getData() != null) {
if (headLoop.getNext() != null) {
System.out.print("Node->");
} else {
System.out.print("Node");
}
} else {
System.out.print("head->");
}
headLoop = headLoop.getNext();
}
System.out.println();
}
打印结果
https://i-blog.csdnimg.cn/direct/ec904af44d9a43d2b631d9691cf5696a.png
[*]插入链表
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;
intmaxData = 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;
}
打印结果:
https://i-blog.csdnimg.cn/direct/9831c3fc78e04d46a8ed84c345af3d6a.png
[*]更新节点
// 如果链表中有多个相同的目标节点，则一并更新
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;
}
@Override
public 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 voidprintLink(DoubleNode head) {
DoubleNode headLoop = head;
while(headLoop != null) {
if (headLoop.getData() != null) {
if (headLoop.getNext() != null && headLoop.getPre() != null) {
System.out.print("<-Node->");
}
else if (headLoop.getNext() != null && headLoop.getPre() == null) {
System.out.print("head->");
}
else {
System.out.print("<-Node");
}
} else {
System.out.print("head->");
}
headLoop = headLoop.getNext();
}
System.out.println();
}
打印结果
https://i-blog.csdnimg.cn/direct/d333eba8d4a044eaa720d9591ccbb990.png
[*]插入节点
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);
}
打印结果
https://i-blog.csdnimg.cn/direct/785c89129a1445838a5d9cf383c42581.png
[*]删除节点
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;
}
打印结果
https://i-blog.csdnimg.cn/direct/7cd3fd2944594e638760c767b0e63318.png
[*]更新节点
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);
}
打印结果
https://i-blog.csdnimg.cn/direct/aa778d38ce624fafbc462cdbb9b3e40d.png
[*]查找节点
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) 打印结果
https://i-blog.csdnimg.cn/direct/d320322716f548abac2f31a1b5aca38e.png
get(10)打印结果
https://i-blog.csdnimg.cn/direct/41da8b96f3aa43fa9faa5ea7c71fd8ff.png
[*]反转链表
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;
}
打印反转后的结果
https://i-blog.csdnimg.cn/direct/dbf83d3c265b4cb98710055a070d5bd4.png
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 voidprintCircleLink(Node head) {
Node headLoop = head;
do {
if (headLoop.getData() != null) {
if (headLoop.getNext() != head) {
System.out.print("Node->");
} else {
System.out.print("Node");
}
} else {
System.out.print("head->");
}
headLoop = headLoop.getNext();
} while (headLoop != head); // 注意结束标识
System.out.println();
}
打印结果
https://i-blog.csdnimg.cn/direct/a81b49b5bf2d4acfbc150e6f7cbbf519.png
对循环单链表的增、删、改、查与单链表类似， 不再例证
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 voidprintCircleLink(DoubleNode head) {
DoubleNode headLoop = head;
do {
if (headLoop.getData() != null) {
if (headLoop.getNext() != head) {
System.out.print("<-Node->");
}
else {
System.out.print("<-Node");
}
} else {
System.out.print("head->");
}
headLoop = headLoop.getNext();
} while (headLoop != head);
System.out.println();
}
打印结果
https://i-blog.csdnimg.cn/direct/7c6c8e6dca6a40a3877973ce6f7400d1.png
对循环双向链表的增、删、改、查与非循环双向链表类似， 不再例证
7、顺序表
对顺表的操作即是对数组的操作, 这里不思量扩容问题
public class CArrayList {
private final int defaultCapacity = 10;
private Object[] array;
private int size = 0;
private int capacity;
public CArrayList() {
array = new Object;
}
public CArrayList(int capacity) {
this.capacity = capacity;
array = new Object;
}
// 添加元素
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 == null) {
array = 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 = array;
}
array = value;
size++;
}
// 删除元素
public void remove(Object value) {
if (value == null) throw new RuntimeException("被删除的元素不能为空");
for (int i = 0; i < array.length; i++) {
if (array == value || array.equals(value)) {
array = null;
size--;
break;
}
}
}
// 更新元素
public void update(int index, Object value) {
if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");
array = value;
}
// 获取元素
public Object get(int index) {
if (index < 0 || index >= array.length) throw new IndexOutOfBoundsException("数组越界");
return array;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]