线性表（顺序表和链式表）。 补之前的系列 数据结构系列
栈 https://hubojing.github.io/2017/11/14/%E6%A0%88/
队列 https://hubojing.github.io/2017/11/12/%E9%98%9F%E5%88%97/
树 https://hubojing.github.io/2017/07/23/%E6%A0%91/
顺序表
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
28
| #ifndef LIST_H
#define LIST_H
#include "Coordinate.h"
class List
{
public:
List(int size);
~List();
void ClearList();
bool ListEmpty();
int ListLength();
bool GetElem(int i, Coordinate *e);
int LocateElem(Coordinate *e);
bool PriorElem(Coordinate *currentElem, Coordinate *preElem);
bool NextElem(Coordinate *currentElem, Coordinate *nextElem);
void ListTraverse();
bool ListInsert(int i, Coordinate *e);
bool ListDelete(int i, Coordinate *e);
private:
Coordinate *m_pList;
int m_iSize;
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
|
#include "List.h"
#include <iostream>
using namespace std;
List::List(int size)
{
m_iSize = size;
m_pList = new Coordinate[m_iSize];
m_iLength = 0;
}
List::~List()
{
delete[]m_pList;
m_pList = NULL;
}
void List::ClearList()
{
m_iLength = 0;
}
bool List::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
else
{
return false;
}
}
int List::ListLength()
{
return m_iLength;
}
bool List::GetElem(int i, Coordinate *e)
{
if (i < 0 || i >= m_iSize)
{
return false;
}
*e = m_pList[i];
return true;
}
int List::LocateElem(Coordinate *e)
{
for (int i = 0; i < m_iLength; ++i)
{
if (m_pList[i] == *e)
{
return i;
}
}
return -1;
}
bool List::PriorElem(Coordinate *currentElem, Coordinate *preElem)
{
int temp = LocateElem(currentElem);
if (temp == -1 || temp == 0)
{
return false;
}
else
{
*preElem = m_pList[temp - 1];
}
}
bool List::NextElem(Coordinate *currentElem, Coordinate *nextElem)
{
int temp = LocateElem(currentElem);
if (temp == -1 || 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, Coordinate *e)
{
if (i<0 || i>m_iLength)
{
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, Coordinate *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;
}
|
Coordinate.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #ifndef COORDINATE_H
#define COORDINATE_H
#include <ostream>
using namespace std;
class Coordinate
{
friend ostream &operator<<(ostream &out, Coordinate &coor);
public:
Coordinate(int x = 0, int y = 0);
void printCoordinate();
bool operator==(Coordinate &coor);
private:
int m_iX;
int m_iY;
};
#endif
|
Coordinate.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
| #include "Coordinate.h"
#include <iostream>
using namespace std;
Coordinate::Coordinate(int x, int y)
{
m_iX = x;
m_iY = y;
}
void Coordinate::printCoordinate()
{
cout << "(" << m_iX << "," << m_iY << ")" << endl;
}
ostream &operator<<(ostream &out, Coordinate &coor)
{
out << "(" << coor.m_iX << "," << coor.m_iY << ")" << endl;
return out;
}
bool Coordinate::operator==(Coordinate &coor)
{
if (this->m_iX == coor.m_iX && this->m_iY == coor.m_iY)
{
return true;
}
return false;
}
|
demo.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <stdio.h>
#include "List.h"
int main()
{
Coordinate e1(1, 2);
Coordinate e2(3, 4);
Coordinate e3(5, 6);
List *list = new List(10);
list->ListInsert(0, &e1);
list->ListInsert(1, &e2);
list->ListInsert(2, &e3);
list->ListTraverse();
printf("长度：%d\n", list->ListLength());
return 0;
}
|
运行结果：
1
2
3
4
5
6
7
| (1,2)
(3,4)
(5,6)
长度：3
|
链式表
Node.h
1
2
3
4
5
6
7
8
9
10
11
12
| #ifndef NODE_H
#define NODE_H
class Node
{
public:
int data;
Node *next;
void printNode();
};
#endif
|
Node.cpp
1
2
3
4
5
6
7
8
| #include "Node.h"
#include <iostream>
using namespace std;
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
28
29
| #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 PriorElem(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
210
211
212
|
#include "List.h"
#include <iostream>
using namespace std;
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;
}
bool List::ListInsertHead(Node *pNode)
{
Node *newNode = new Node;
if (newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
newNode->next = m_pList->next;
m_pList->next = newNode;
m_iLength++;
return true;
}
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->data = pNode->data;
newNode->next = NULL;
currentNode->next = newNode;
m_iLength++;
return true;
}
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; ++k)
{
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;
}
void List::ClearList()
{
Node *currentNode = m_pList->next;
while (currentNode != NULL)
{
Node *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList->next = NULL;
m_iLength = 0;
}
bool List::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
else
{
return 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;
Node *currentNodeBefore = NULL;
for (int k = 0; k <= i; ++k)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
pNode->data = currentNode->data;
return true;
}
int List::LocateElem(Node *pNode)
{
Node *currentNode = m_pList;
int count = 0;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
if (currentNode->data == pNode->data)
{
return count;
}
count++;
}
return -1;
}
bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
Node *currentNode = m_pList;
Node *tempNode = NULL;
while (currentNode->next != NULL)
{
tempNode = currentNode;
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (tempNode == m_pList)
{
return false;
}
pPreNode->data = tempNode->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->next->data;
return true;
}
}
return false;
}
void List::ListTraverse()
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
currentNode->printNode();
}
}
|
demo.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
| #include <stdio.h>
#include "List.h"
#include <iostream>
using namespace std;
int main()
{
List *pList = new List();
Node node1;
node1.data = 1;
Node node2;
node2.data = 2;
Node node3;
node3.data = 3;
Node node4;
node4.data = 4;
Node node5;
node5.data = 5;
pList->ListInsertTail(&node1);
pList->ListInsertTail(&node2);
pList->ListInsertTail(&node3);
pList->ListInsertTail(&node4);
pList->ListInsert(1, &node5);
pList->ListTraverse();
delete pList;
pList = NULL;
return 0;
}
|
链表应用之通讯录
Person.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #ifndef PERSON_H
#define PERSON_H
#include <string>
#include <ostream>
using namespace std;
class Person
{
friend ostream &operator<<(ostream &out, Person &person);
public:
string name;
string phone;
Person &operator=(Person &person);
bool operator==(Person &person);
};
#endif
|
Person.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include "Person.h"
ostream &operator<<(ostream &out, Person &person)
{
out << person.name << "----" << person.phone << endl;
return out;
}
Person &Person::operator=(Person &person)
{
this->name = person.name;
this->phone = person.phone;
return *this;
}
bool Person::operator==(Person &person)
{
if (this->name == person.name && this->phone==person.phone)
{
return true;
}
return false;
}
|
Node.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #ifndef NODE_H
#define NODE_H
#include "Person.h"
class Node
{
public:
Person data;
Node *next;
void printNode();
};
#endif
|
Node.cpp
1
2
3
4
5
6
7
8
| #include "Node.h"
#include <iostream>
using namespace std;
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
28
29
| #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 PriorElem(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
210
211
212
|
#include "List.h"
#include <iostream>
using namespace std;
List::List()
{
m_pList = new Node;
m_pList->next = NULL;
m_iLength = 0;
}
List::~List()
{
ClearList();
delete m_pList;
m_pList = NULL;
}
bool List::ListInsertHead(Node *pNode)
{
Node *newNode = new Node;
if (newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
newNode->next = m_pList->next;
m_pList->next = newNode;
m_iLength++;
return true;
}
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->data = pNode->data;
newNode->next = NULL;
currentNode->next = newNode;
m_iLength++;
return true;
}
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; ++k)
{
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;
}
void List::ClearList()
{
Node *currentNode = m_pList->next;
while (currentNode != NULL)
{
Node *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList->next = NULL;
m_iLength = 0;
}
bool List::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
else
{
return 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;
Node *currentNodeBefore = NULL;
for (int k = 0; k <= i; ++k)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
pNode->data = currentNode->data;
return true;
}
int List::LocateElem(Node *pNode)
{
Node *currentNode = m_pList;
int count = 0;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
if (currentNode->data == pNode->data)
{
return count;
}
count++;
}
return -1;
}
bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
Node *currentNode = m_pList;
Node *tempNode = NULL;
while (currentNode->next != NULL)
{
tempNode = currentNode;
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (tempNode == m_pList)
{
return false;
}
pPreNode->data = tempNode->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->next->data;
return true;
}
}
return false;
}
void List::ListTraverse()
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
currentNode->printNode();
}
}
|
demo.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
| #include <stdio.h>
#include "List.h"
#include <iostream>
using namespace std;
int menu()
{
cout << "功能菜单" << endl;
cout << "1.新建联系人" << endl;
cout << "2.删除联系人" << endl;
cout << "3.浏览通讯录" << endl;
cout << "4.退出通讯录" << endl;
cout << "请输入：" << endl;
int order = 0;
cin >> order;
return order;
}
void createPerson(List *pList)
{
Node node;
cout << "请输入姓名：" << endl;
cin >> node.data.name;
cout << "请输入电话：" << endl;
cin >> node.data.phone;
pList->ListInsertTail(&node);
}
void deletePerson(List *pList)
{
Node node;
cout << "请输入姓名：" << endl;
cin >> node.data.name;
cout << "请输入电话：" << endl;
cin >> node.data.phone;
int num = 0;
num = pList->LocateElem(&node);
pList->ListDelete(num, &node);
}
int main()
{
List *pList = new List();
int userOrder = 0;
while (userOrder != 4)
{
userOrder = menu();
switch (userOrder)
{
case 1:
cout << "用户指令--->新建联系人：" << endl;
createPerson(pList);
break;
case 2:
cout << "用户指令--->删除联系人：" << endl;
cout << "请输入被删除者姓名：" << endl;
deletePerson(pList);
break;
case 3:
cout << "用户指令--->浏览通讯录：" << endl;
pList->ListTraverse();
break;
case 4:
cout << "用户指令--->退出通讯录：" << endl;
break;
default:
break;
}
}
delete pList;
pList = NULL;
return 0;
}
|
