服务器之家

服务器之家 > 正文

利用C++简单实现顺序表和单链表的示例代码

时间:2021-05-26 14:18     来源/作者:Suhw

本文主要给大家介绍了关于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;
};

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对服务器之家的支持

原文链接:http://blog.csdn.net/sssssuuuuu666/article/details/75400679

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部