本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容，分享出来供大家参考学习，话不多说，来一起看看详细的介绍：
一、顺序表示例代码：
?
|
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
|
#include <assert.h>
#include <iostream>
using namespace std;
typedef int Datatype;
class SeqList
{
public:
SeqList()
:_array(NULL)
,_size(0)
,_capacity(0)
{
}
SeqList(const SeqList& s)
{
_array = (Datatype*)malloc(s._size*(sizeof(Datatype)));
memcpy(_array, s._array, s._size*(sizeof(Datatype)));
_size = _capacity = s._size;
}
SeqList& operator=(SeqList& s)
{
free(_array);
Swap(s);
return *this;
}
void Swap(SeqList& s)
{
_array = s._array;
_size = s._size;
_capacity = s._capacity;
}
~SeqList()
{
if (_array)
{
free(_array);
_array = NULL;
_size = _capacity = 0;
}
}
void Print()
{
for (size_t i = 0; i < _size; i++)
{
cout << _array[i] << " ";
}
cout << endl;
}
void CheckCapcacity()
{
if (_size == _capacity)
{
_capacity = 2 * _capacity + 3;
_array = (Datatype*)realloc(_array, _capacity*sizeof(Datatype));
assert(_array);
}
}
//后插
void PushBack(Datatype x)
{
Insert(_size, x);
}
//前插
void PushFront(Datatype x)
{
Insert(0, x);
}
//删除最后一个
void PopBack()
{
Erase(_size);
}
//删除第一个
void PopFront()
{
Erase(0);
}
//[]运算符重载
Datatype& operator[](size_t pos)
{
assert(pos < _size);
return _array[pos];
}
//pos位置前插入x
void Insert(size_t pos, Datatype x)
{
assert(pos <= _size);
CheckCapcacity();
int end = (int)_size - 1;
if (pos == 0)
{
while (end >= 0)
{
_array[end + 1] = _array[end];
end--;
}
_array[0] = x;
}
else
{
while (end >= (int)pos)
{
_array[end + 1] = _array[end];
end--;
}
_array[pos] = x;
}
_size++;
}
//删除pos位置的元素
void Erase(size_t pos)
{
assert(pos < _size);
//popfront的实现
if (_size > 0)
{
if (pos == 0)
{
int end = 0;
while (end < (int)_size - 1)
{
_array[end] = _array[end + 1];
end++;
}
_size--;
}
//popback的实现
else if (pos == _size)
{
_size--;
}
//erase
else
{
int end = pos;
while (end < (int)_size - 1)
{
_array[end] = _array[end + 1];
end++;
}
_size--;
}
}
return;
}
private:
Datatype* _array;
size_t _size;
size_t _capacity;
};
|
二、单链表（不含头结点）示例代码
?
|
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
|
#include <iostream>
#include <assert.h>
using namespace std;
typedef int DataType;
struct SListNode
{
SListNode* _next;
DataType _data;
SListNode(DataType x)
:_data(x)
, _next(NULL)
{}
};
typedef SListNode Node;
class SList
{
public:
SList()
:_head(NULL)
, _tail(NULL)
{}
SList(const SList& s)
:_head(NULL)
,_tail(NULL)
{
Copy(s);
}
SList& operator=(const SList& s)
{
Destroy();
Copy(s);
return *this;
}
~SList()
{
Destroy();
}
void Copy(const SList& s)
{
Node* cur = s._head;
while (cur)
{
PushBack(cur->_data);
cur = cur->_next;
}
}
void Destroy()
{
Node* cur = _head;
while (_head != NULL)
{
cur = _head;
_head = cur->_next;
delete cur;
}
_head = _tail = NULL;
}
void PushBack(DataType x)
{
if ((_head == NULL)&&(_tail == NULL))
{
_head = _tail = new Node(x);
}
else
{
_tail->_next = new Node(x);
_tail = _tail->_next;
}
}
void PopBack()
{
if (_head == NULL)
{
return;
}
else if (_head ->_next == NULL)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* tmp = _head;
while (tmp->_next->_next != NULL)
{
tmp = tmp->_next;
}
_tail = tmp;
tmp->_next = NULL;
}
}
void PushFront(DataType x)
{
if ((_head == NULL) && (_tail == NULL))
{
_head = _tail = new Node(x);
}
else
{
Node* tmp = new Node(x);
tmp->_next = _head;
_head = tmp;
}
}
void PopFront()
{
if (_head == NULL)
{
return;
}
Node* cur = _head;
_head = _head->_next;
delete cur;
}
Node* Find(DataType x)
{
Node* tmp = _head;
while (tmp)
{
if (tmp->_data == x)
return tmp;
tmp = tmp->_next;
}
return NULL;
}
// 插入一个节点在pos的前面
void Insert(Node* pos, DataType x)
{
assert(pos);
if (pos == 0)
{
PushFront(x);
}
else
{
Node* cur = _head;
while (cur->_next != pos)
{
cur = cur->_next;
}
Node* tmp = new Node(x);
tmp->_next = pos;
cur->_next = tmp;
}
}
void Erase(Node* pos)
{
assert(pos);
if (pos == 0)
{
PopFront();
}
else if (pos->_next == NULL)
{
PopBack();
}
else
{
Node* cur = _head;
while (cur->_next != pos)
{
cur = cur->_next;
}
Node* tmp = cur->_next;
cur->_next = tmp->_next;
delete tmp;
}
}
void Print()
{
Node* tmp = _head;
while (tmp != NULL)
{
cout <<tmp->_data << "->";
tmp= tmp->_next;
}
cout <<"NULL"<<endl;
}
private:
Node* _head;
Node* _tail;
};
|
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对快网idc的支持
相关文章
猜你喜欢
