C++实现单链表和子类栈(Stack)及单向队列(Queue)

刚刚开始学习c++。之前c的内容掌握的也不多，基本只是一本概论课的程度，以前使用c的struct写过的链表、用python写过简单的数据结构，就试着把两者用c++写出来，也是对c++的class，以及继承中的public/protected/private的性质进行初步了解。第一次写头文件.h和源文件.cpp分开的c++代码。过程中参考了ProLyn和kgvito的代码，基本就是百度“单链表 c++”的前几个搜索结果。

节点listNode还是用struct来写了，因为我想节点除了构造没有什么方法需要实现，变量和构造也总是需要处于public的状态方便其他类函数调用。

栈是保持先进后出(First In Last Out,或者FILO)的数据结构，在这里只是定义了最基本的五种方法，实现从尾部添加、从尾部弹出；队列是保持先进先出(First In First Out,FIFO)的数据结构，同样定义了最基本的方法实现从尾部添加从头部弹出。二者我都使用了private继承，因为除了重新封装list的几种方法外，多数list的方法都不需要出现在这两种数据结构中，我认为禁止public访问这些方法比较好。

1 // linked_list.h

2 // Base class linked list "linkList",derived "linkStack" & "linkQueue"

3 typedef int DataType;

4

5 // constructing struct "listNode"

6 struct listNode

7 {

8 DataType nodeVal;

9 listNode* nextNode;

10 listNode(const DataType x); // listNode construct func

11 };

12

13 // constructing base class "linklist"

14 class linkList

15 {

16 private: // private variables headNode & tailNode

17 listNode* headNode;

18 listNode* tailNode;

19 // construction functions,and operator overload

20 public:

21 linkList();

22 linkList(const linkList& lista);

23 linkList& operator=(linkList& lista);

24 DataType operator[](int index);

25 // other functions,public

26 public:

27 bool isEmpty();

28 void PrintList();

29 void PushBack(const DataType& x);

30 void PushFront(const DataType& x);

31 void PopBack();

32 void PopFront();

33 DataType PeekBack();

34 DataType PeekFront();

35 void InsertNext(listNode* pos,DataType x);

36 void DeleteNext(listNode* pos);

37 void Delete(listNode* pos);

38 void Clear();

39 void Remove(DataType x);

40 void RemoveAll(DataType x);

41 void Sort();

42 int GetLength();

43 listNode* Find(DataType x);

44 };

45

46 // derived class linkStack

47 class linkStack : private linkList

48 {

49 public:

50 linkStack();

51 linkStack(const linkStack& stack1);

52 linkStack& operator=(linkStack& stack1);

53 // the least functions needed

54 public:

55 bool isEmpty();

56 int getSize();

57 void PushBack(const DataType& x);

58 void PopBack();

59 DataType PeekBack();

60 };

61

62 // derived class linkQueue

63 class linkQueue : private linkList

64 {

65 public:

66 linkQueue();

67 linkQueue(const linkQueue& queue1);

68 linkQueue& operator=(linkQueue& queue1);

69

70 public:

71 bool isEmpty();

72 int getSize();

73 void PushBack(const DataType& x);

74 void PopFront();

75 DataType PeekFront();

76 }

对struct listNode，class linkList,linkStack,linkQueue的方法的具体实现，后两者基本只是对于linkList的重新封装，为了能在private继承的子类中实现，也不得不在linkList中添加了一些没什么用处的函数。其中构造函数和赋值下标运算重载的写法都是现学的…如果现学的不到位请不吝赐教！

1 #include

2 #include "linked_list.h"

3 using namespace std;

4 // construction func for listNode

5 listNode::listNode(const DataType x)

6 :nodeVal(x),nextNode(nullptr)

7 {}

8 // construction funcs for linkList

9 linkList::linkList() // without argument

10 : headNode(nullptr),tailNode(nullptr)

11 {}

12

13 linkList::linkList(const linkList& lista) // with argument

14 : headNode(nullptr),tailNode(nullptr)

15 {

16 if (lista.headNode) {

17 listNode* tmp = lista.headNode;

18 while (tmp->nextNode) {

19 PushBack(tmp->nodeVal);

20 tmp = tmp->nextNode;

21 }

22 PushBack(tmp->nodeVal);

23 }

24 }

25 // operator reload =

26 linkList& linkList::operator=(linkList &lista) {

27 if (this != &lista) {

28 swap(headNode,lista.headNode);

29 swap(tailNode,lista.tailNode);

30 }

31 return *this;

32 }

33 // operator reload [](index)

34 DataType linkList::operator[](int index) {

35 if (index < 0 || headNode == nullptr) {

36 cout << "Invalid index!" << endl;

37 return -1;

38 }

39 else {

40 listNode* tmp = headNode;

41 int i;

42 while (tmp != nullptr && i < index) {

43 tmp = tmp->nextNode;

44 i++;

45 }

46 if (tmp == nullptr) {

47 cout << "Invalid index!" << endl;

48 return -1;

49 }

50 else {

51 return tmp->nodeVal;

52 }

53 }

54 }

55

56 bool linkList::isEmpty() {

57 if (headNode) {

58 return true;

59 }

60 else {

61 return false;

62 }

63 }

64

65 int linkList::GetLength() {

66 int count = 0;

67 listNode* tmp = headNode;

68 while (tmp) {

69 count++;

70 tmp = tmp->nextNode;

71 }

72 return count;

73 }

74

75 void linkList::PrintList() {

76 listNode* tmp = headNode;

77 if (tmp) {

78 cout << tmp->nodeVal;

79 tmp = tmp->nextNode;

80 while (tmp) {

81 cout << "->" << tmp->nodeVal;

82 tmp = tmp->nextNode;

83 }

84 cout << endl;

85 }

86 else {

87 cout << "Empty linked list!" << endl;

88 }

89 }

90

91 void linkList::PushBack(const DataType& x) {

92 if (headNode) {

93 tailNode->nextNode = new listNode(x);

94 tailNode = tailNode->nextNode;

95 }

96 else {

97 headNode = new listNode(x);

98 tailNode = headNode;

99 }

100 }

101

102 void linkList::PushFront(const DataType& x) {

103 if (headNode) {

104 listNode* tmp = new listNode(x);

105 tmp->nextNode = headNode;

106 headNode = tmp;

107 }

108 else {

109 headNode = new listNode(x);

110 tailNode = headNode;

111 }

112 }

113

114 void linkList::PopBack() {

115 if (headNode) {

116 if (headNode->nextNode) {

117 listNode* tmp = headNode;

118 while (tmp->nextNode != tailNode) {

119 tmp = tmp->nextNode;

120 }

121 delete tailNode;

122 tmp->nextNode = nullptr;

123 tailNode = tmp;

124 }

125 else {

126 delete headNode;

127 headNode = nullptr;

128 tailNode = nullptr;

129 }

130 }

131 else {

132 cout << "Empty linked list!" << endl;

133 }

134 }

135

136 void linkList::PopFront() {

137 if (headNode) {

138 if (headNode->nextNode) {

139 listNode* tmp = headNode->nextNode;

140 delete headNode;

141 headNode = tmp;

142 }

143 else {

144 delete headNode;

145 headNode = nullptr;

146 tailNode = nullptr;

147 }

148 }

149 else {

150 cout << "Empty linked list!" << endl;

151 }

152 }

153

154 DataType linkList::PeekBack() {

155 if (tailNode) {

156 return tailNode->nodeVal;

157 }

158 else {

159 cout << "Empty linked list!" << endl;

160 return -1;

161 }

162 }

163

164 DataType linkList::PeekFront() {

165 if (headNode) {

166 return headNode->nodeVal;

167 }

168 else {

169 cout << "Empty linked list!" << endl;

170 return -1;

171 }

172 }

173

174 listNode* linkList::Find(DataType x) {

175 listNode* targetNode = headNode;

176 while (targetNode) {

177 if (targetNode->nodeVal == x) {break;}

178 }

179 return targetNode;

180 }

181

182 void linkList::InsertNext(listNode* pos,DataType x) {

183 if (pos) {

184 if (pos == tailNode) {

185 listNode* tmp = new listNode(x);

186 pos->nextNode = tmp;

187 tailNode = tmp;

188 }

189 else {

190 listNode* tmp = new listNode(x);

191 tmp->nextNode = pos->nextNode;

192 pos->nextNode = tmp;

193 }

194 }

195 else {

196 cout << "Invalid position!" << endl;

197 }

198 }

199

200 void linkList::DeleteNext(listNode* pos) {

201 if (pos) {

202 if (pos == tailNode) {

203 cout << "Invalid node!" << endl;

204 }

205 else {

206 listNode* tmp = (pos->nextNode)->nextNode;

207 delete pos->nextNode;

208 pos->nextNode = tmp;

209 }

210 }

211 else {

212 cout << "Invalid node!" << endl;

213 }

214 }

215

216 void linkList::Remove(DataType x) {

217 if (headNode) {

218 if (headNode->nextNode) {

219 listNode* tmp = headNode;

220 while (tmp->nextNode) {

221 if ((tmp->nextNode)->nodeVal == x) {

222 DeleteNext(tmp);

223 break;

224 }

225 tmp = tmp->nextNode;

226 }

227 }

228 else {

229 if (headNode->nodeVal == x) {PopFront();}

230 }

231 }

232 }

233

234 void linkList::RemoveAll(DataType x) {

235 if (headNode) {

236 listNode* tmp = headNode;

237 while (tmp->nextNode) {

238 if ((tmp->nextNode)->nodeVal == x) {

239 if (tmp->nextNode == tailNode){

240 PopBack();

241 break;

242 }

243 else {DeleteNext(tmp);}

244 }

245 tmp = tmp->nextNode;

246 }

247 if (tmp->nodeVal == x) {

248 PopBack();

249 }

250 }

251 }

252

253 void linkList::Clear() {

254 if (headNode) {

255 listNode* prev = headNode;

256 listNode* tmp;

257 while (prev->nextNode) {

258 tmp = prev->nextNode;

259 delete prev;

260 prev = tmp;

261 }

262 headNode = nullptr;

263 tailNode = nullptr;

264 }

265 }

266 // construction funcs for linkStack

267 linkStack::linkStack() // without arguments

268 :linkList()

269 {}

270

271 linkStack::linkStack(const linkStack& stack1) // with an argument

272 :linkList(stack1)

273 {}

274 // other public funcs for linkStack

275 bool linkStack::isEmpty() {

276 return linkList::isEmpty();

277 }

278

279 int linkStack::getSize() {

280 return linkList::GetLength();

281 }

282

283 void linkStack::PushBack(const DataType& x) {

284 linkList::PushBack(x);

285 }

286

287 void linkStack::PopBack() {

288 linkList::PopBack();

289 }

290

291 DataType linkStack::PeekBack() {

292 return linkList::PeekBack();

293 }

294 // construction funcs for linkQueue

295 linkQueue::linkQueue()

296 :linkList()

297 {}

298

299 linkQueue::linkQueue(const linkQueue& queue1)

300 :linkList(queue1)

301 {}

302 // other public funcs for linkQueue

303 bool linkQueue::isEmpty() {

304 return linkList::isEmpty();

305 }

306

307 int linkQueue::getSize() {

308 return linkList::GetLength();

309 }

310

311 void linkQueue::PushBack(const DataType& x) {

312 linkList::PushBack(x);

313 }

314

315 void linkQueue::PopFront() {

316 linkList::PopFront();

317 }

318

319 DataType linkQueue::PeekFront() {

320 return linkList::PeekFront();

321 }

最后还有测试代码，和主题没什么关系，但是从以前用python学习数据结构开始我就喜好把测试代码写成假交互式，所以索性贴在这里方便取用。

1 #include

2 #include "linked_list.h"

3 #include

4 #include

5

6 using namespace std;

7

8 static mapstringVal {

9 {"Exit",0},

10 {"Printlist",1},

11 {"Pushback",2},

12 {"Pushfront",3},

13 {"Popback",4},

14 {"Popfront",5},

15 {"Clear",6},

16 {"Remove",7},

17 {"Removeall",8},

18 {"Sort",9},

19 {"Getlength",10},

20 {"Index",11},

21 {"Peekback",12},

22 {"Peekfront",13}

23 };

24

25 int test_list() {

26 linkList list1;

27 cout << ">> Linked list tesing.n"

28 ">> Enter a direction,namely Printlist,Pushback,Pushfront,Popback,Peekback,"

29 "Popfront,Peekfront,Clear,Remove,Removeall,Sort,Getlength or Index,"

30 "enter Exit to exit." << endl;

31 string direction;

32 DataType parameter;

33 int param;

34 while (1) {

35 cout << ">> ";

36 cout.flush();

37 cin >> direction;

38 switch(stringVal[direction])

39 {

40 case 0:

41 return 0;

42 case 1:

43 list1.PrintList();

44 break;

45 case 2:

46 cin >> parameter;

47 list1.PushBack(parameter);

48 break;

49 case 3:

50 cin >> parameter;

51 list1.PushFront(parameter);

52 break;

53 case 4:

54 list1.PopBack();

55 break;

56 case 5:

57 list1.PopFront();

58 break;

59 case 6:

60 list1.Clear();

61 break;

62 case 7:

63 cin >> parameter;

64 list1.Remove(parameter);

65 break;

66 case 8:

67 cin >> parameter;

68 list1.RemoveAll(parameter);

69 break;

70 /* case 9:

71 list1.Sort();

72 break;*/

73 case 10:

74 param = list1.GetLength();

75 cout << ">> " << param << endl;

76 break;

77 case 11:

78 cin >> param;

79 parameter = list1[param];

80 cout << ">> " << parameter << endl;

81 break;

82 case 12:

83 parameter = list1.PeekBack();

84 cout << ">> " << parameter << endl;

85 break;

86 case 13:

87 parameter = list1.PeekFront();

88 cout << ">> " << parameter << endl;

89 }

90 }

91 return

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!