数据结构-线性表

线性表及其逻辑和存储结构,适合有一定基础的同学进行复习,新同学可能看不太懂…

另外,本篇博客的所有代码都是有联系的,请不要仅复制部分,可能无法运行。

线性表

线性表是n个类型相同数据元素的有限序列。在一个线性表中,要做到相同数据类型、具有顺序性、序列有限这三个要求。相同数据类型意味着在内存中存储时,每个元素都会占有相同的内存空间,便于后续的查询定位。实现线性表的方式有顺序存储和链式存储两种方式。下面给出一个实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
* 线性表接口
* 和存储结构无关--即下面的顺序表和单链表、双向链表都会实现这些功能。
*/
public interface ILinearList<E> {
//添加元素
boolean add(E item);
//插入元素
boolean add(int index,E item);
//删除元素 并返回该元素
E remove(int index);
//查看元素索引
int indexOf(E item);
//取元素
E get(int index);
//替换元素 并返回要被替换下来的元素
E set(int index,E item);
//求线性表长度
int size();
//清空线性表
void clear();
//判断线性表是否为空
boolean isEmpty();
}

补充:自定义异常,作为练习,在下面的顺序表和链表中使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 自定义异常: 我的数组越界异常
* @author x1aolin
*
*/
public class MyIndexOutOfBoundsException extends RuntimeException{

public MyIndexOutOfBoundsException() {
super();
}

public MyIndexOutOfBoundsException(String message) {
super(message);
}
}

顺序存储结构

顺序表

特点:在内存中分配连续空间,只存储数据,不需要存储地址信息,因为其位置就隐含着地址。逻辑上相邻的两个元素在物理位置上也相邻。

优点索引查找效率高,它的存储位置可用一个简单、直观的公式来表示。即每一个节点对应一个序号,由该序号可以直接计算出来节点的存储地址。一次计算即可:地址 = 初始地址+索引*每个元素大小。

缺点(一)插入删除效率低,在进行插入和删除操作时,需要向前或者向后移动大量元素。(二)必须提前分配好固定数量的空间,若给长度变化较大的线性表预先分配空间时,必须按照最大空间分配,如果存储元素少,可能导致空闲浪费。(三)表的容量难以扩充

代码实现:这里没有设置可扩展数组,后续可以进行改进。这里最重要的就是设置了一个一维数组,并定死了数组的大小,其余函数则是针对这个数组的一些操作。 整体不难,但要注意一些细节。

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
import java.lang.reflect.Array;

public class SeqList<E> implements ILinearList<E> {
//顺序表结构
private int maxsize; //顺序表最大容量
private E[] data; //一维数组,顺序表的存储方法 !!!
private int size; //顺序表实际长度
//初始化顺序表
@SuppressWarnings("unchecked")
public SeqList(Class<E> type,int maxsize) {
this.maxsize = maxsize;
//定义对应数据类型的一维数组
data = (E[])Array.newInstance(type, maxsize);
this.size = 0;
}
//判断是否为满
public boolean isFull(){
return size==maxsize;
}
//判断数组是否越界
public void rangeCheck(int index){
if(index<0||index>size){
throw new MyIndexOutOfBoundsException("Index:" + index + ",Size:"+size);
}
}
//添加元素
public boolean add(E item) {
if(isFull()) return false;
else{
data[size++] = item; //先运行,再加一
return true;
}
}
//插入元素
public boolean add(int index, E item) {
rangeCheck(index);
if(!isFull()){
for(int i = size-1;i>=index;i--){
data[i+1] = data[i];
}
data[index] = item;
size++;
return true;
}
else return false;
}
//删除元素
public E remove(int index) {
//判断index的合法性 注意这里加了=号,因为size位置也没有元素
if(index<0||index>=size){
throw new IndexOutOfBoundsException("Index:" + index + ",Size:"+size);
}
//0位置元素需要单独判定
if(!isEmpty()){
E tmp = data[index];
for(int i=index;i<size-1;i++){ //细节
data[i] = data[i+1];
}
data[--size] = null; //最后位置清空
return tmp;
}
return null;
}
//查找元素对应的序号
public int indexOf(E item) {
//空指针也是需要比较的对象,因为可以插入
if(item==null){
for(int i=0;i<size;i++){
if(data[i]==null){
return i;
}
}
}else{
for(int i=0;i<size;i++){
if(data[i].equals(item)){
return i;
}
}
}
return -1;
}
//查找元素,放回顺序表中指定索引位置index处的数据元素
public E get(int index) {
rangeCheck(index);
return data[index];
}
//替换元素
public E replace(int index, E item) {
rangeCheck(index);
E oldValue = data[index];
data[index] = item;
return oldValue;
}
//返回真实数组大小
public int size() {
return size;
}
//清空顺序表
public void clear() {
//我感觉下面这句可有可无,size清零就好了
for(int i=0;i<size;i++) data[i] = null;
size = 0;
}
//判断是否为空
public boolean isEmpty() {
return size==0;
}
//重写toString方法
public String toString() {
if(size==0) return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for(int i=0;i<size;i++){
sb.append(data[i]+",");
}
sb.setCharAt(sb.length()-1, ']');
return sb.toString();
}
}

链式存储结构

链表是一系列的存储数据元素的结点通过指针串接起来的,因此每个结点有两种域,一种域用于数据元素的存储,另一种域是指向其他单元的引用。

对于单向链表,具有一个数据域和一个引用域,引用域指向它的直接后继节点。双向链表则具有一个数据域和两个引用域,引用域指向它的直接前驱和直接后继。元素之间的逻辑关系通过存储节点之间的链接关系反映出来,逻辑上相邻的结点物理上不必相邻。

优点(一)插入、删除灵活,不必移动节点,只要改变节点中的指针,但是需要先定位到元素上。(二)不会有闲置结点,因为有元素才会动态的分配节点。

缺点(一)存储密度小,每个节点都是由数据域和指针域构成,所以相同空间内假设全存满的话顺序比链式存储更多。(二)查找速度慢,每个节点地址不连续、无规律,导致按照索引查询效率低下。

下面则分别这两种结构实现上面接口中的功能。

单链表

单向链表存储结构:

data next
数据域 直接后继节点

node.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 单链表的结点
*/
public class Node<E> {
//正经的可以设置为private,然后使用get和set方法
E data;
Node<E> next;

public Node(){
this.data = null;
this.next = null;
}
public Node(E data, Node<E> next) {
super();
this.data = data;
this.next = next;
}
}

SLinkList.java

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
public class SLinkList<E> implements ILinearList<E>{
//头节点 不存储数据,为了编程方便 有的代码中head也可以作为结点使用
private Node<E> head;
private int size; //链表长度

//初始化线性表 头节点不存储数据
public SLinkList() {
head = new Node<>();
size = 0;
}
//判断是否越界
public void rangeCheck(int index){
if(index<0||index>=size){
throw new MyIndexOutOfBoundsException("Index:" + index + ",Size:"+size);
}
}
//在末尾添加数据
public boolean add(E item) {
if(head.next==null){
head.next = new Node<E>(item,null);
}
else{
Node<E> current = head;
while(current.next!=null){
current = current.next;
}
current.next = new Node<E>(item,null);
}
size++;
return true;
}
//在指定位置插入数据
public boolean add(int index, E item) {
rangeCheck(index);
Node<E> current = head;
Node<E> newNode = new Node<>(item,null);
while(index!=0){
current = current.next;
index--;
}
newNode.next = current.next;
current.next = newNode;
size++;
return true;
}
//删除指定位置元素
public E remove(int index) {
rangeCheck(index);
Node<E> previous = head;
while(index!=0){ //刚好差一个位置
previous = previous.next;
index--;
}
Node<E> tmp = previous.next;
previous.next = tmp.next;
tmp.next = null;
size--;
return tmp.data;
}
//返回元素对应位置
public int indexOf(E item) {
Node<E> current = head;
int index = 0;
while(current.next!=null){
current = current.next;
if(current.data==null&&item==null) return index;
else{
if(current.data.equals(item)) return index;
}
index++;
}
return -1;
}
//返回对应位置的元素
public E get(int index) {
rangeCheck(index);
Node<E> current = head.next;
while(index!=0){
current = current.next;
index--;
}
return current.data;
}
//替换对应位置结点 这个方法太笨,直接替换节点中的数据即可
public E replace(int index, E item) {
rangeCheck(index);
Node<E> previous = head;
while(index!=0){
previous = previous.next;
}
Node<E> node = new Node<>(item,null);
Node<E> tmp = previous.next;
node.next = tmp.next;
previous.next = node;
tmp.next = null;
return tmp.data;
}
//返回链表长度
public int size() {
return size;
}
//清空链表
public void clear() {
Node<E> tmp = head;
while(tmp!=null){ //全部指向空
Node<E> next = tmp.next;
tmp.data = null;
tmp.next = null;
tmp = next;
}
head = null;
size = 0;
}
//判断是否为空
public boolean isEmpty() {
return size==0;
}
//重写toString方法
public String toString() {
if(size==0) return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
Node<E> current = head.next;
while(current!=null){
sb.append(current.data+",");
current = current.next;
}
sb.setCharAt(sb.length()-1, ']');
return sb.toString();
}
}

双向链表

双向链表存储结构:

prev data next
直接前驱结点地址 数据域 直接后继结点地址

相比于单向链表,双向链表可以直接访问它的前驱节点,而不用再从头遍历,提高了性能。当然,也就因为加了前驱引用,导致空间变多了。在双向链表中,我们设置两个引用firstlast来分别记录链表的第一个结点和最后一个结点,方便遍历。

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
164
165
166
167
168
169
public class DLinkList<E> implements ILinearList<E> {
private int size;
private DNode<E> first; //指示第一个结点
private DNode<E> last; //指示最后一个结点

private static class DNode<E> {
E data;
DNode<E> prev;
DNode<E> next;

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

public DNode(DNode<E> prev,E data, DNode<E> next) {
this.data = data;
this.prev = prev;
this.next = next;
}
}
//添加
public boolean add(E item) {
DNode<E> l = last;
DNode<E> newNode = new DNode<>(l,item,null);
last = newNode;
if(l==null){ //仅针对第一个节点
first = newNode;
}
else{
l.next = newNode;
}
size++;
return true;
}

//看距离头尾哪一边更近,来决定从头还是从尾开始寻找
public boolean add(int index, E item) {
DNode<E> current = findNode(index);
DNode<E> newNode = new DNode<>(item);
if(current==first){
newNode.next = first.next;
first = newNode;
}
else{
DNode<E> previous = current.prev;
previous.next = newNode;
newNode.prev = previous;
current.prev = newNode;
newNode.next = current;
}
size++;
return true;
}

@Override
public E remove(int index) {
DNode<E> current = findNode(index);
if(current==first){
first = first.next;
current.next = null;
}
else if(current==last){
last = last.prev;
current.prev = null;
}
else{
DNode<E> prevNode = current.prev;
DNode<E> nextNode = current.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
//可写可不写
current.next = null;
current.prev = null;
}
size--;
return current.data;
}

@Override
public int indexOf(E item) {
DNode<E> current = first;
int index = 0;
while(current!=null){
if(current.data.equals(item)){
return index;
}
index++;
current = current.next;
}
return -1;
}

@Override
public E get(int index) {
return findNode(index).data;
}

//替换结点
public E replace(int index, E item) {
DNode<E> current = findNode(index);
E data = current.data;
current.data = item;
return data;
}

@Override
public int size() {
return size;
}

//搞清楚垃圾回收机制 再来清除 它是怎们判定已用空间和未用空间的?
public void clear() {
DNode<E> tmp = first;
while(tmp!=null){ //全部指向空
DNode<E> nextNode = tmp.next;
tmp.prev = null;
tmp.data = null;
tmp.next = null;
tmp = nextNode;
}
first = null;
last = null;
size = 0;
}

@Override
public boolean isEmpty() {
return size==0;
}
//重写toString方法
public String toString() {
if(size==0) return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
DNode<E> current = first;
while(current!=null){
sb.append(current.data+",");
current = current.next;
}
sb.setCharAt(sb.length()-1, ']');
return sb.toString();
}
//判断是否越界
public void rangeCheck(int index){
if(index<0||index>=size){
throw new MyIndexOutOfBoundsException("Index:" + index + ",Size:"+size);
}
}
//查找结点
public DNode<E> findNode(int index){
rangeCheck(index);
DNode<E> current;
if(index<size/2){
current = first;
while(index!=0){
current = current.next;
index--;
}
}
else{
current = last;
while(index<size-1){
current = current.prev;
index++;
}
}
return current;
}
}

循环链表

循环链表可分为循环单链表和循环双向链表,和面唯一的区别就是首尾相连,该机制也就导致了判断链头和链尾的方式发生了改变。此处不再详细描述,请读者自行思考。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------