首页 数据结构

# 线性表 (Linear List)

定义

零个或多个数据元素的有限序列

存储结构和存取结构

  • 存储结构是数据及其逻辑结构在内存中的表示
  • 存取结构是一个数据结构对查找操作的时间性能的一种描述
    1
    2
    3
    4
    5
    6
    7
    8
    graph LR;
    StorageStructure("存储结构(Storage Structure)")-->SequentialStorageStructure("顺序存储结构(Sequential Storage Structure)")
    StorageStructure-->LinkedStorageStructure("链式存储结构(Linked Storage Structure))")
    StorageStructure-->IndexedStorageStructure("索引存储结构(Indexed Storage Structure)")
    StorageStructure-->HashStorageStructure("散列存储结构(Hash Storage Structure)")
    AccessMethod("存取方式(Access Method)")-->
    SequentialAccess("顺序存取(Sequential Access)")
    AccessMethod-->RandomAccess("随机存取(Random Access)")

# 1. 顺序表 (Sequential List)

# 1.1 定义

一段地址连续的存储单元依次存储线性表的数据元

# 1.2 存储结构和存取结构

顺序表是一种随机存取的顺序存储结构

# 1.3 使用场景

  • 顺序表适用于元素存取操作多，增删操作少的场景

# 1.4 顺序表代码实现

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
#include<iostream>
using namespace std;
const int MAX_SIZE=100;

template<class T>
class SeqList{
private:
	T data[MAX_SIZE];
	int length;
public:
	SeqList():length(0){}
	SeqList(const T arr[],const int len);
	int length()const;//the length of SeqList
	T searchByIndex(const int index)const;// Find by index
	int searchByValue(const T value)const;// Find by value
	bool insert(const int index,const T value);// insert 
	bool removeByIndex(const int index);// remove by index
	bool removeByValue(const T value);// 	remove by value
	void printSeqList()const;// print the SeqList
}

template<class T>
SeqList<T>::SeqList<const T arr[],const int len){
	if(len >MAX_SIZE){
		cerr<<"Insufficient LIST";
		exit(1);
	}
	length=len;
	for(int i=0;i<len;i++){
		data[i]=arr[i];
	}
}

template<class T>
int SeqList<T>::length() const{
	return length;
}

template<class T>
T SeqList<T>::searchByIndex(const int index) const{
	if(index<1||index>length){
		cerr<<"Illegal Search Index";
		exit(1);
	}
	return data[index-1];
}

template<class T>
int SeqList<T>::searchByValue(const T value) const{
	for(int i=0;i<length;i++){
		if(data[i]==value){
			return i+1;
		}
	}
	return  -1; //Not found
}

template<class T>
bool SeqList<T>::insert(const int index,const T value){
	if(length>=MAX_SIZE){
		cerr<<"Array Overflow";
		return false;
	}
	if(index<1||index>length+1){
		cerr<<"Illegal Insert Position";
		return false;
	}
	for(int i=length-1;i>=index-1;i--){
		data[i+1]=data[i];
	}
	data[index-1]=value;
	length++;
	return true;
}

template<class T>
bool  SeqList<T>::removeByIndex(const int index){
	if(length==0){
		cerr<<"Array Out of Bounds";
		return false;
	}
	if(index<1||index>length){
		cerr<<"Illegal Remove Position";
		return false;
	}
	for(int i=index;i<length;i++){
		data[i-1]=data[i];
	}
	length--;
	return true;
}

template<class T>
bool SeqList<T>::removeByValue(const T value){
	int index=-1;
	for(int i=0;i<length;i++){
		if(data[i]==value){
			index=i;
			break;
		}
	}
	if(index!=-1){
		for(int i=index+1;i<length;i++){
			data[i-1]=data[i];
		}
		length--;
		return true;
	}
	return false;
}

template<class T>
void SeqList<T>::printSeqList() const{
	for(int i=0;i<length;i++){
		cout<<data[i]<<"\t";
	}
	cout<<endl;
}

# 2. 链表

# 2.1 定义

一个或多个结点 组合而成的数据结构称为链表

# 2.2 结点

结点一般由数据域和指针域构成

# 2.3 头指针和头结点

** 头结点的数据域可以不存储任何信息，其指针域指向头指针 **

  1. 头指针：链表的第一个结点
  2. 头结点：在头指针前附设一个结点

为什么有时候头结点不必须存在呢？

  • 空链表情况：当链表为空时，头结点可以省略，直接用头指针为 null 或者指向第一个实际节点。
  • 操作方便性：有时在操作链表时，不需要头结点，直接用头指针指向第一个节点即可。
  • 节省空间：省略头结点可以节省一个节点的空间，在链表数据量较大时可能会显著节省空间。

# 2.4 存储结构和存取结构

单链表是一种顺序存取的链式存储结构

# 2.4 使用场景

  • 链表适用于插入或删除操作频繁的场景

# 2.5 常用链表

# 2.5.1 单向链表代码实现

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
#include<iostream>
using namespace std;
template<class T>
struct Node{
	T data;
	Node<T>* next;
	Node(T value):data(value),next(nullptr){}
};
template<class T>
class LinkList{
private:
	Node<T>* head;// head node
public:
	LinkList();
	LinkList(const T arr[],const int len);//tail insertion
	~LinkList();
	int length()const;
	T searchByIndex(const int index)const;
	int searchByValue(const T value)const;
	bool insert(const int index, const T value);
	bool removeByIndex(const int index);
	bool removeByValue(const T value);
	void printLinkList()const;
}

template<class T>
LinkList<T>::LinkList(){
	head= new Node<T>;
	head->next= nullptr;
}

template<class T>
LinkList<T>::LinkList(const T arr[],const int len){
	head=new Node<T>;
	Node<T>* rear=head;//point to the last node
	for(int i=0;i<len;i++){
		Node<T>* s=new Node<T>(arr[i]);
		rear->next=s;
		rear=s;
	}
	rear->next=nullptr;
}

template<class T>
LinkList<T>::~LinkList(){
	Node<T>* current=head;
	while(current){
		Node<T>* temp=current;
		current=current->next;
		delete temp;
	}
	head=nullptr;
}

template<class T>
int LinkList<T>::length()const{
	Node<T> *cur=head->next;
	int len=0;
	while(cur){
		cur=cur->next;
		len++;
	}
	return len;
}

template<class T>
T LinkList<T>::searchByIndex(const int index)const{
	Node<T>* cur=head->next;
	int j=1;
	while(cur&&j<index){
		cur=cur->next;
		j++;
	}
	if(!cur||j>index){
		cerr<<"Illegal Search Index";
		exit(1);
	}
	else{
		return cur->data;
	}
}

template<class T>
int LinkList<T>::searchByValue(const T value)const{
	Node<T>* cur=head->next;
	int j=1;
	while(cur&&cur->data!=value){
		cur=cur->next;
		j++;
	}
	if(cur){
		return j;
	}
	else{
		return -1;
	}
}

template<class T>
bool LinkList<T>::insert(const int index,const T value){
	Node<T>* cur=head;
	int j=0;
	while(cur&&j<index-1){
		cur=cur->next;
		j++;
	}
	if(!cur||j>i-1){
		cerr<<"Illegal Insert Position";
		return false;
	}
	else{
		Node<T>* temp=new Node<T>(value);
		temp->next=cur->next;
		cur->next=temp;
		return true;
	}
}

template<class T>
bool LinkList<T>::removeByIndeX(const int index){
		Node<T>* cur=head;
		int j=0;
		while(cur&&j<index-1){
			cur=cur->next;
			j++;
		}
		if(!cur||!cur->next){
			cerr<<"Illegal Delete Position";
			return false;
		}
		else{
			Node<T>* temp=cur->next;
			cur->next=temp->next;
			delete temp;
			return true;
		}
}

template<class T>
bool LinkList<T>::removeByValue(const T value){
	Node<T>* cur=head;
	while(cur&&cur->data!=value){
		cur=cur->next;
	}
	if(!cur||!cur->next){
		cerr<<"Illegal Delete Position";
		return false;
	}
	else{
		Node<T>* temp=cur->next;
		cur->next=temp->next;
		delete temp;
		return true;
	}
}

template<class T>
void LinkList<T>::printLinkList()const{
	Node<T>*cur=head-next;
	while(cur){
		cout<<cur->data<<"\t";
		cur=cur-next;
	}
}

# 2.5.2 循环链表

由于循环链表循环判断为cur->next=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
121
#include<iostream>
using namespace std;
template<class T>
struct Node{
	T data;
	Node<T>* next;
	Node(T value):data(value),next(nullptr){}
};
template<class T>
class CircularLinkList{
private:
	Node<T>* head;
	Node<T>* tail;//suppose there is a head node and tail node
public:
	CircularLinkList();
	CircularLinkList(const T arr[],const int len);
	~CircularLinkList();
	int length() const;
	bool insertByFront(const T value);//front insertion
	bool insertByRear(const T value);// rear insertion
	bool searchByValue(const T value)const;
	void printCircularLinkList() const;
}
template<class T>
CircularLinkList<T>::CircularLinkList(){
	head=new Node<T>;
	head->next=head;
	tail=head;
}

template<class T>
CircularLinkList<T>::CircularLinkList(const T arr[],const int len){
	for(int i=0;i<len;i++){
		insertByRear(arr[i]);
	}	
}

template<class T>
CircularLinkList<T>::~CircularLinkList(){
	Node<T>* cur=head;
	while(cur){
		Node<T>* temp=cur;
		crur=cur->next;
		delete temp;
	}
	head=nullptr;
	tail=nullptr;
}


template<class T>
int CircularLinkList<T>::length()const{
	if(!head) return 0;
	int len=0;
	Node<T>* cur=head;
	while(cur->next!=head){
		cur=cur->next;
		len++;
	}
	return len;
}

template<class T>
bool CircularLinkList<T>::insertByFront(const T value){
	Node<T>* temp=new Node<T>(value);
	if(!head){
		head=temp;
		tail=temp;
		temp->next=temp;
	}
	else{
		temp->next=head;
		tail->next=temp;
		head=temp;//
	}
	return true;
}

template<class T>
bool CircularLinkList<T>::insertByRear(const T value){
	Node<T>* temp=new Node<T>(value);
	if(!head){
		head=temp;
		tail=temp;
		temp->next=temp;
	}
	else{
		temp->next=head;
		tail->next=temp;
		tail=temp;//
	}
}

template<class T>
bool CircularLinkList<T>::searchByValue(const T value)const{
	if(!head)	return false;
	Node<T>*cur=head;
	while(cur->next!=head){
		if(cur->data==value){
			return true;
		}
		cur=cur->next;
	}
	return false;
}

template<class T>
void CircularLinkList<T>::printCircularLinkList(){
	if(!head){
		cerr<<"Circular LinkList is Empty";
		exit(1);
	}
	else{
		Node<T>*cur=head;
		while(cur->next!=head){
			cout<<cur->data<<"\t";
			cur=cur->next;		
		}
		cout<<endl;
	}
}

# 2.5.3 双向链表

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
#include<iostream>
using namespace std;
template<class T>
struct Node{
	T data;
	Node<T>* prev,next;
	Node(T value):data(value),prev(nullptr),next(nullptr){}
};
template<class T>
class DoublyLinkList{
private:
	Node<T>*head;
public:
	DoublyLinkList();
	DoublyLinkList(const T arr[],const int len);
	~DoublyLinkList();
	int length()const;
	bool insertByFront(const T value);
	bool insertByRear(const T value);
	bool searchByValue(const T value)const;
	bool removeByValue(const T value);
	void printDoublyLinkList()const;
}

template<class T>
DoublyLinkList<T>::DoublyLinkList(){
	head=new Node<T>;
	head->prev=nullptr;
	head->next=nullptr;
}

template<class T>
DoublyLinkList<T>::DoublyLinkList(const T arr[],const int len){
	for(int i=0;i<len;i++){
		insertByRear(arr[i]);
	}
}

template<class T>
DoublyLinkList<T>::~DoublyLinkList(){
	Node<T>*cur=head;
	while(cur){
		Node<T>* temp=cur;
		cur=cur->next;
		delete temp;
	}
}

template<class T>
int DoublyLinkList<T>::length()const{
	if(!head) return 0;
	int len=0;
	Node<T>* cur=head;
	while(cur->next!=head){
		cur=cur->next;
		len++;
	}
	return len;
}