数据结构探险-03线性表篇

发表于   |   分类于   |  

数据结构探险之线性表篇-慕课网
C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l03_list at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

本课程主要以顺序表和链表作为内容主体，详细讲述了顺序表及链表的实现原理，并手把手完成顺序表及链表的基本结构操作，课程的最后通过通讯录的经典实例进一步深化讲解较为复杂的链表，使学员可以将知识融会贯通以至于学以致用。

1 线性表

说明：线性表是 N 个数据元素的有限序列。

2 顺序表

说明： 基于数组来实现，因此随机访问速度和遍历效率高，但插入和删除效率低。

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <iostream>

using namespace std;

// 顺序表
class List
{
public:
	List(int size);
	~List();
	void ClearList(); // 清空数据
	bool ListEmpty(); // 判空
	int ListLength(); // 获取链表长度
	bool GetElem(int i, int *e); // 获取指定下标元素
	int LocateElem(int *e); // 获取指定元素的下标
	bool PrevElem(int *currentElem, int *preElem); // 获取前驱
	bool NextElem(int *currentElem, int *nextElem);// 获取后继
	void ListTraverse(); // 遍历
	bool ListInsert(int i, int *e); // 插入元素
	bool ListDelete(int i, int *e); // 删除元素
private:
	int *m_pList;
	int m_iSize;
	int m_iLength;
};

int main(void)
{
	int e1 = 3;
	int e2 = 5;
	int e3 = 7;
	int e4 = 2;
	int e5 = 9;
	int e6 = 1;
	int e7 = 8;

	List *list1 = new List(10);
	list1->ListInsert(0, &e1);
	list1->ListInsert(0, &e2);
	list1->ListInsert(0, &e3);
	list1->ListInsert(0, &e4);
	list1->ListInsert(0, &e5);
	list1->ListInsert(0, &e6);
	list1->ListInsert(0, &e7);
	
	int temp = 0;
	list1->ListDelete(0, &temp);
	list1->ListTraverse();

	cout << "length:" << list1->ListLength() << endl;

	list1->GetElem(0, &temp);
	cout << "temp:" << temp << endl;

	delete list1;
	list1 = NULL;
	return 0;
}

List::List(int size)
{
	m_iSize = size;
	m_pList = new int[m_iSize];
	m_iLength = 0;
}

List::~List()
{
	delete []m_pList;
	m_pList = NULL;
}

void List::ClearList()
{
	m_iLength = 0;
}

bool List::ListEmpty()
{
	return m_iLength == 0 ? true : false;
}

int List::ListLength()
{
	return m_iLength;
}
bool List::GetElem(int i, int *e)
{
	if(i < 0 || i >= m_iSize)
	{
		return false;
	}
	*e = m_pList[i];
	return true;
}

int List::LocateElem(int *e)
{
	for(int i = 0; i < m_iLength; i++)
	{
		if(m_pList[i] == *e)
		{
			return i;
		}
	}
	return -1;
}

bool List::PrevElem(int *currentElem, int *preElem)
{
	int temp = LocateElem(currentElem);
	// 指定元素没有找到
	if(temp == -1)
	{
		return false;
	}
	else
	{
		// 载链表首位，没有前驱
		if(temp == 0)
		{
			return false;
		}
		else
		{
			*preElem = m_pList[temp - 1];
			return true;
		}
	}
}

bool List::NextElem(int *currentElem, int *nextElem)
{
	int temp = LocateElem(currentElem);
	if(temp == -1)
	{
		return false;
	}
	else
	{
		// 在链表尾部，没有后继
		if(temp == m_iLength - 1)
		{
			return false;
		}
		else
		{
			*nextElem = m_pList[temp + 1];
			return true;
		}
	}	
}

void List::ListTraverse()
{
	for(int i = 0; i < m_iLength; i++)
	{
		cout << m_pList[i] << endl;
	}
}

bool List::ListInsert(int i, int *e)
{
	// 不能随便插入
	if(i < 0 || i >= m_iSize)
	{
		return false;
	}
	// 移动
	for(int k = m_iLength - 1; k >= i; k--)
	{
		m_pList[k+1] = m_pList[k];
	}
	// 插入
	m_pList[i] = *e;
	// 长度加一
	m_iLength++;
	return true;
}

bool List::ListDelete(int i, int *e)
{
	if(i < 0 || i >= m_iLength)
	{
		return false;
	}
	// 获取要删除的元素
	*e = m_pList[i];

	// 从删除点往后的数据向前移动
	for(int k = i + 1; k > m_iLength; k++)
	{
		m_pList[k - 1] = m_pList[k];
	}
	// 长度减一
	m_iLength--;
	return true;
}

3 链表

说明： 相比顺序表，链表伸缩性好，插入删除效率高，遍历和随机访问效率低。

3.1 基础

3.1.1 单链表（单向链表）

3.1.2 循环两表

3.1.3 双向链表

3.1.4 静态链表

说明：用数组实现的链表。

3.2 代码

以单链表实现为例，其它大同小异。

1
2
3
4
5
6
7
.
├── List.cpp
├── List.h
├── Node.cpp
├── Node.h
├── main.cpp
└── makefile

Node.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef NOOD_H
#define NOOD_H
#include <iostream>
using namespace std;

class Node 
{
public:
	int data;
	Node *next;
	void printNode();
};
#endif

Node.cpp

1
2
3
4
5
6
#include "Node.h"

void Node::printNode()
{
	cout << data << endl;
}

List.h

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
#ifndef LIST_H
#define LIST_H
#include "Node.h"

class List
{
public:
	List();
	~List();
	void ClearList(); // 清空数据
	bool ListEmpty(); // 判空
	int ListLength(); // 获取链表长度
	bool GetElem(int i, Node *pNode); // 获取指定下标元素
	int LocateElem(Node *pNode); // 获取指定元素的下标
	bool PrevElem(Node *pCurrentNode, Node *pPreNode); // 获取前驱
	bool NextElem(Node *pCurrentNode, Node *pNextNode);// 获取后继
	void ListTraverse(); // 遍历
	bool ListInsert(int i, Node *pNode); // 插入元素
	bool ListDelete(int i, Node *pNode); // 删除元素
	bool ListInsertHead(Node *pNode); // 从头部插入
	bool ListInsertTail(Node *pNode); // 从尾部插入
private:
	Node *m_pList;
	int m_iLength;
};

#endif

List.cpp

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <iostream>
#include "List.h"

List::List()
{
	m_pList = new Node;
	m_pList->data = 0;
	m_pList->next = NULL;
	m_iLength = 0;
}

List::~List()
{
	ClearList();
	delete m_pList;
	m_pList = NULL;
}

void List::ClearList()
{
	Node *currentNode = m_pList->next;
	while(NULL != currentNode)
	{
		Node *temp = currentNode->next;
		delete currentNode;
		currentNode = temp;
	}
	m_pList->next = NULL;
	m_iLength = 0;
}

bool List::ListEmpty()
{
	return m_iLength == 0 ? true : false;
}

int List::ListLength()
{
	return m_iLength;
}

bool List::GetElem(int i, Node *pNode)
{
	if(i < 0 || i >= m_iLength)
	{
		return false;
	}
	Node *currentNode = m_pList;
	for(int k = 0; k < i; k++)
	{
		currentNode = currentNode->next;
	}
	pNode->data = currentNode->data;
	pNode->next = currentNode->next;

	return true;
}

// 只能拿到第一个数据域匹配的节点
int List::LocateElem(Node *pNode)
{
	Node *currentNode = m_pList;
	for(int i = 0; i < m_iLength; i++)
	{
		currentNode = currentNode->next;
		if(currentNode->data== pNode->data)
		{
			return i;
		}
	}
	return -1;
}

bool List::PrevElem(Node *pCurrentNode, Node *pPreNode)
{
	Node *currentPrevNode = NULL;
	Node *currentNode = m_pList;
	while(currentNode->next != NULL)
	{
		currentPrevNode = currentNode;
		currentNode = currentNode->next;
		if(currentNode->data == pCurrentNode->data)
		{
			// 头节点不用来存储数据，因此不能作为符合条件的节点返回
			if(currentNode == m_pList)
			{
				return false;
			}
			pPreNode->data = currentPrevNode->data;
			return true;
		}
	}
	return false;
}

bool List::NextElem(Node *pCurrentNode, Node *pNextNode)
{
	Node *currentNode = m_pList;
	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;
		if(currentNode->data == pCurrentNode->data)
		{
			// 尾节点没有下一个节点了
			if(currentNode ->next ==  NULL)
			{
				return false;
			}
			pNextNode->data = currentNode->data;
			return true;
		}
	}
	return false;	
}

void List::ListTraverse()
{
	Node *currentNode = m_pList;
	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;
		currentNode->printNode();
	}
}

bool List::ListInsert(int i, Node *pNode)
{
	// 不能随便插入
	if(i < 0 || i > m_iLength)
	{
		return false;
	}
	// 找到插入位置的前一个节点
	Node *currentNode = m_pList;
	for(int k = 0; k < i; i++)
	{
		currentNode = currentNode->next;
	}
	// 创建新节点
	Node *newNode = new Node;
	if(newNode == NULL)
	{
		return false;
	}
	newNode->data = pNode->data;
	// 插入
	newNode->next = currentNode->next;
	currentNode->next = newNode;
	return true;
}

bool List::ListDelete(int i, Node *pNode)
{
	if(i < 0 || i >= m_iLength)
	{
		return false;
	}
	Node *currentNode = m_pList;
	Node *currentNodeBefore = NULL;
	for(int k = 0; k <= i; k++)
	{
		currentNodeBefore = currentNode;
		currentNode = currentNode->next;
	}
	currentNodeBefore->next = currentNode->next;
	pNode->data = currentNode->data;
	delete currentNode;
	currentNode = NULL;
	m_iLength--;
	return true;
}

bool List::ListInsertHead(Node *pNode)
{
	Node *temp = m_pList->next;
	Node *newNode = new Node;
	if(newNode == NULL)
	{
		return false;
	}
	newNode->data = pNode->data;
	m_pList->next = newNode;
	newNode->next = temp;
	m_iLength++;
	return false;
}

bool List::ListInsertTail(Node *pNode)
{
	Node *currentNode = m_pList;
	// 找到最后一个节点
	while(currentNode->next != NULL)
	{
		currentNode = currentNode->next;
	}
	// 创建新节点
	Node *newNode = new Node;
	if(newNode == NULL)
	{
		return false;
	}
	// 初始化新节点
	newNode->next = NULL;
	newNode->data = pNode->data;
	// 插入
	currentNode->next = newNode;
	m_iLength++;
	return true;
}

main.cpp

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
#include <iostream>
#include "List.h"
#include "Node.h"

int main(void)
{
	// 创建链表
	List *pList = new List();

	// 初始化需要的节点
	Node node1, node2, node3, node4, node5, node6;
	node1.data = 3;
	node2.data = 4;
	node3.data = 5;
	node4.data = 6;
	node5.data = 7;
	node6.data = 8;

	// 插入节点
	pList->ListInsertHead(&node1);
	pList->ListInsertHead(&node2);
	pList->ListInsertHead(&node3);
	pList->ListInsertHead(&node4);
	pList->ListInsertHead(&node5);
	pList->ListInsertHead(&node6);

	// 遍历
	pList->ListTraverse();

	// 根据第1个数据获取节点
	Node temp;
	pList->GetElem(1, &temp);
	cout << "GetElem: " << temp.data << endl;
	
	return 0;
}
`

4 链表应用-通讯录

4.1 需求

联系人信息：姓名 电话
功能菜单：

  1. 新建联系人
  2. 删除联系人
  3. 浏览通讯录
  4. 推出通讯录
    请输入：

4.2 程序设计

  • Person 类需要重载 << 、==、= 三种运算符。
  • Node 的 data 属性改为 Person 类型。
1
2
3
4
5
6
7
8
9
.
├── List.cpp
├── List.h
├── Node.cpp
├── Node.h
├── Person.cpp
├── Person.h
├── main.cpp
└── makefile

4.3 核心代码

C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l03_list/0401_phone_book at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

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
#include <iostream>
#include “List.h”
#include “Node.h”
using namespace std;

// 功能提示、接收用户的指令
int menu()
{
	// 显示通讯录功能菜单
	cout << "功能菜单" << endl;
	cout << "1. 新建联系人" << endl;
	cout << "2. 删除联系人" << endl;
	cout << "3. 浏览通讯录" << endl;
	cout << "4. 退出通讯录" << endl;

	cout << "请输入：";
	int order = 0;
	cin >> order;
	return order;
}

// 创建联系人
void createPerson(List *pList)
{
	Person person;
	Node node;
	cout << "请输入姓名：";
	cin >> person.name;
	cout << "请输入电话：";
	cin >> person.phone;
	node.data = person;
	pList->ListInsertTail(&node); // 事实上并没有真的把这个 node 插入了链表，而是将 node 的 data 数据赋值给了载堆中新创建的节点
}

// 删除联系人
void deletePerson(List *pList)
{
	Node node;
	Person person;
	cout << "请输入要删除的联系人的姓名:";
	cin >> person.name;
	cout << "请输入要删除的联系人的电话:";
	cin >> person.phone;
	node.data = person;
	int index = pList->LocateElem(&node);
	cout << "index:" << index << endl;
	if(pList->ListDelete(index, &node))
	{
		cout << "删除成功！" << endl;
	}
	else
	{
		cout << "没有找到!" << endl;
	}
}

int main(void)
{	
	int userOrder = 0;
	List *pList = new List();
	while(userOrder != 4)
	{
		userOrder = menu();
		switch(userOrder)
		{
			case 1:
				cout << "用户指令--->>新建联系人：" << endl;
				createPerson(pList);
				break;
			case 2:
				cout << "用户指令--->>删除联系人：" << endl;
				deletePerson(pList);
				break;
			case 3:
				cout << "用户指令--->>浏览通讯录：" << endl;
				pList->ListTraverse();
				break;
			case 4:
				cout << "用户指令--->>退出通讯录：" << endl;
				break;
			default:
				cout << "非法指令！" << endl;
				break;
		}
	}

	delete pList;
	pList = NULL;
	return 0;
}