0%

数据结构

数据之间有3种基本结构

  • 线性结构 数据元素之间为一对一关系

  • 树形结构 数据元素之间为一对多关系

  • 网状结构 数据元素之间为多对多关系

线性结构

线性表

线性表分为顺序线性表和链式线性表,顺序存储结构和链式存储结构,顺序存储结构的线性表称为顺序表,链式存储的线性表称为链表

线性表数据结构具有以下特征:

  • 存在唯一的”首元素”

  • 存在唯一的”尾元素”

  • 除尾元素外,其余元素均有唯一的后继元素

  • 除首元素外,其余元素均有唯一的前驱元素

顺序表

在内存中用一组地址连续的存储空间顺序存放线性表的各个元素,保证线性表元素逻辑上的有序性。

顺序表是将数据按顺序保存到内存中的,因此在顺序表中存取数据很方便,但是插入数据时,需要移动大量的数据,java中的ArrayList实现原理就是数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/**
* 简单的线性表实现
*/
public class ShunXuBiao<T> {
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 顺序表主体
private Object[] array;
// 顺序表长度,表示顺序表中当前元素个数
private int size;

//数组长度
private int length;

public static void main(String[] args) {
ShunXuBiao<Integer> shunXuBiao = new ShunXuBiao<>(2);
System.out.println(shunXuBiao.isEmpty());
shunXuBiao.add(100);
System.out.println(shunXuBiao.size());
shunXuBiao.add(10);
shunXuBiao.print();
shunXuBiao.add(0, 20);
shunXuBiao.print();
shunXuBiao.remove(1);
shunXuBiao.print();
shunXuBiao.clearAll();
shunXuBiao.add(30);
shunXuBiao.print();
}

public void print() {
System.out.println("-------------------");
for (int i = 0; i < size; i++) {
System.out.printf("%s\t", array[i]);
}
System.out.println();
System.out.println("-------------------");
}

/**
* 定义容量
*
* @param capacity
*/
public ShunXuBiao(int capacity) {
this.array = new Object[capacity];
this.size = 0;
this.length = capacity;
}

public ShunXuBiao() {
this(DEFAULT_CAPACITY);
}

/**
* 清空顺序表
*/
public void clearAll() {
this.size = 0;
}

/**
* 顺序表元素个数
*
* @return
*/
public int size() {
return this.size;
}

/**
* 添加元素
*
* @param element
*/
public void add(T element) {
ensureCapacity();
if (size < array.length) {
array[size] = element;
size++;
} else {
throw new RuntimeException("已超过数组容量");
}
}

/**
* 指定位置添加元素
*
* @param index
* @param element
*/
public void add(int index, T element) {
ensureCapacity();
if (index < size && size < array.length) {
// Object[] oldArray = Arrays.copyOf(array, array.length);
// array[index] = element;
// for (int i = index; i < size; i++) {
// array[i + 1] = oldArray[i];
// }
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i]; // 节点后移
}
array[index] = element;
size++;

} else {
throw new RuntimeException("数组下标越界");
}
}

/**
* 自动扩容
*/
public void ensureCapacity() {
if (size >= length) {
// 容量增加一倍
length = length << 1;
array = Arrays.copyOf(array, length);
}
}

/**
* 删除指定元素
*
* @param index
*/
public void remove(int index) {
if (index < size) {
// Object[] oldArray = Arrays.copyOf(array, array.length);
// for (int i = index; i < size; i++) {
// array[i] = oldArray[i + 1];
// }
for (int i = index; i < size-1; i++) {
array[i] = array[i + 1]; // 节点前移
}
array[size - 1] = null;
size--;
}
}


/**
* 获取数据
*
* @param index
* @return
*/
public T get(int index) {
if (index < size) {
return (T) array[index];
}
throw new RuntimeException("数组越界");
}

/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
}

链表

链表是采用动态存储分配的一种结构,可以根据需要申请内存单元。链表中每个节点都包含两部分,一部分是实际数据,一部分是下一节点的地址,操作链表时,需定义一个头指针变量,该变量指向链表的第一个节点,第一个节点又指向第二个节点,直到最后一个节点。最后一个节点不在指向其他节点,称为表尾,在表尾的地址部分放一个NULL,表示空指针,链表到此结束。

单向链表每个节点中只包含一个指针,双向链表每个节点包含两个指针,一个指向上一节点,一个指向下一节点

根据链接方式不同,链表分为单链表、循环链表、循环链表、双向链表。

JAVA的LinkedList实现原理就是链表,单向链表实际上是由节点(Node)组成的,一个链表拥有不定数量的节点,数据在内存中存储时不连续,存储的数据分散在内存中,每个节点只能也只有它能知道下一节点的存储位置。由N个Node组成单向链表,每个Node记录本Node的数据和下一个Node。向外暴露的只有一个头节点(Head)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
public class LianBiao<E> {

public static void main(String[] args) {
LianBiao<Integer> lianBiao = new LianBiao<>();
lianBiao.addElement(10);
lianBiao.addElement(20);
lianBiao.print();
lianBiao.deleteElement(0);
lianBiao.print();
lianBiao.addElement(30);
lianBiao.print();
lianBiao.addElement(40);
lianBiao.deleteElement(1);
lianBiao.print();
System.out.println(lianBiao.getElement(0));

}


Node<E> head = null;//头节点
private int length = 0;

/**
* 添加元素
*
* @param element
*/
public void addElement(E element) {
Node<E> newNode = new Node<>(element);
if (head == null) { // 如果是空链表,添加到头节点
head = newNode;
} else {
Node<E> temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
length++;
}

/**
* 删除第index个节点
*
* @param index
*/
public void deleteElement(int index) {
if (index < 0 || index >= length) {
throw new RuntimeException("数组越界,无法删除");
}
// 去除原本头节点 头节点指向下一节点
if (index == 0) {
head = head.next;
length--;
} else {
int count = 1;
Node<E> preNode = head;
Node<E> curNode = preNode.next;
while (curNode != null) {
if (index == count) {
curNode = curNode.next;
preNode.next = curNode;
length--;
break;
} else {
preNode = curNode;
curNode = curNode.next;
count++;
}
}
}
}

/**
* 获取第index个节点数据
*
* @param index
* @return
*/
public E getElement(int index) {
if (index < 0 || index > length) {
throw new RuntimeException("数组越界,无法获取");
}
if (index == 0) {
return head.data;
} else {
Node<E> curNode = head;
int count = 0;
while (curNode != null) {
if (count == index) {
return curNode.data;
}
curNode = curNode.next;
count++;
}
}
return null;
}

public void print() {
System.out.println("------------------------");
Node<E> temp = head;
while (temp != null) {
System.out.printf("%s\t", temp.data);
temp = temp.next;
}
System.out.println();
System.out.println("------------------------");
}


private static class Node<E> {
E data;
Node<E> next;

public Node(E data) {
this.data = data;
}
}
}

队列

队列是一种特殊的线性表,只允许在表的前端进行删除操作(队头),在表的后端进行插入操作(队尾)。当队列中没有元素时,称为空队列。先进先出(First In First Out,FIFO)的结构

栈是一种线性表的特殊表现形式,按照后进先出(Last In First Out,LIFO)原则处理数据,在栈中只能在一端进行操作,该操作端称为栈顶,另一端称为栈底。

基本操作:

  • 入栈(Push) 将数据保存到栈顶。进行该操作时,先修改栈顶指针,使其向上移一个元素位置,然后将数据保存到栈顶指针所指的位置
  • 出栈(Pop) 将栈顶的数据弹出,然后修改栈顶指针,使其指向栈中的下一个元素

非线性结构

线性表、队列、栈都是线性的,这个数据结构不能反映元素之间的层次特性。使用树形结构来描述数据之间的关系。

树的定义

树是n个节点的集合,集合中有一个称为根(root)的特殊节点,在根节点下分布着一些互不相交的集合,每一个集合又是一个树,这些树称为根节点的子树。

  • 在一棵树中,有且仅有一个节点没有前驱,这个节点就是树的根节点

  • 除根节点外,其余每个节点有且仅有一个前驱

  • 每个前驱可以有任意多个后继

相关术语

  • 父节点、子节点、兄弟节点 每个节点的子树的根称为该节点的子节点,相应的,该节点被称为子节点的父节点,具有同一父节点的节点称为兄弟节点

  • 节点的度 一个节点的子树的数量称为该节点的度

  • 树的度 一棵树的度值该树中节点的最大度数

  • 叶节点和分支节点 树中度为0的节点称为叶节点或终端节点。树中度不为0的节点称为分支节点

  • 节点的层数 每个节点都处在一定的层次上,从树根开始计算,根节点为第一层,依次向下

  • 树的深度 一棵树中节点的最大层数称为树的深度

  • 有序树和无序树 若树中各节点的子树(兄弟节点)是按照一定次序从左到右排列的,称为有序树,否则称为无序树

  • 森林 多个互不相交的树的集合

二叉树

二叉树任意节点最多只能有两个子节点;如果只有一个子节点,可以是左子树,也可以是右子树,二叉树的度最大为2,二叉树是有序树

  • 满二叉树 在二叉树中,除最下一层的叶节点外,每层的节点都有两个子节点,就构成了满二叉树
  • 完全二叉树 除二叉树最后一层外,其他各层的节点数都达到最大个数,且最后一层从左到右的叶节点连续存在,只缺右侧若干节点,就是完全二叉树
  • 满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树