刚刚开始学习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访问这些方法比较好。
// linked_list.h
// Base class linked list "linkList", derived "linkStack" & "linkQueue"
typedef int DataType; // constructing struct "listNode"
struct listNode
{
DataType nodeVal;
listNode* nextNode;
listNode(const DataType x); // listNode construct func
}; // constructing base class "linklist"
class linkList
{
private: // private variables headNode & tailNode
listNode* headNode;
listNode* tailNode;
// construction functions, and operator overload
public:
linkList();
linkList(const linkList& lista);
linkList& operator=(linkList& lista);
DataType operator[](int index);
// other functions, public
public:
bool isEmpty();
void PrintList();
void PushBack(const DataType& x);
void PushFront(const DataType& x);
void PopBack();
void PopFront();
DataType PeekBack();
DataType PeekFront();
void InsertNext(listNode* pos, DataType x);
void DeleteNext(listNode* pos);
void Delete(listNode* pos);
void Clear();
void Remove(DataType x);
void RemoveAll(DataType x);
void Sort();
int GetLength();
listNode* Find(DataType x);
}; // derived class linkStack
class linkStack : private linkList
{
public:
linkStack();
linkStack(const linkStack& stack1);
linkStack& operator=(linkStack& stack1);
// the least functions needed
public:
bool isEmpty();
int getSize();
void PushBack(const DataType& x);
void PopBack();
DataType PeekBack();
}; // derived class linkQueue
class linkQueue : private linkList
{
public:
linkQueue();
linkQueue(const linkQueue& queue1);
linkQueue& operator=(linkQueue& queue1); public:
bool isEmpty();
int getSize();
void PushBack(const DataType& x);
void PopFront();
DataType PeekFront();
}
对struct listNode，class linkList, linkStack, linkQueue的方法的具体实现，后两者基本只是对于linkList的重新封装，为了能在private继承的子类中实现，也不得不在linkList中添加了一些没什么用处的函数。其中构造函数和赋值下标运算重载的写法都是现学的…如果现学的不到位请不吝赐教！
#include <iostream>
#include "linked_list.h"
using namespace std;
// construction func for listNode
listNode::listNode(const DataType x)
:nodeVal(x), nextNode(nullptr)
{}
// construction funcs for linkList
linkList::linkList() // without argument
: headNode(nullptr), tailNode(nullptr)
{} linkList::linkList(const linkList& lista) // with argument
: headNode(nullptr), tailNode(nullptr)
{
if (lista.headNode) {
listNode* tmp = lista.headNode;
while (tmp->nextNode) {
PushBack(tmp->nodeVal);
tmp = tmp->nextNode;
}
PushBack(tmp->nodeVal);
}
}
// operator reload =
linkList& linkList::operator=(linkList &lista) {
if (this != &lista) {
swap(headNode, lista.headNode);
swap(tailNode, lista.tailNode);
}
return *this;
}
// operator reload [](index)
DataType linkList::operator[](int index) {
if (index < || headNode == nullptr) {
cout << "Invalid index!" << endl;
return -;
}
else {
listNode* tmp = headNode;
int i;
while (tmp != nullptr && i < index) {
tmp = tmp->nextNode;
i++;
}
if (tmp == nullptr) {
cout << "Invalid index!" << endl;
return -;
}
else {
return tmp->nodeVal;
}
}
} bool linkList::isEmpty() {
if (headNode) {
return true;
}
else {
return false;
}
} int linkList::GetLength() {
int count = ;
listNode* tmp = headNode;
while (tmp) {
count++;
tmp = tmp->nextNode;
}
return count;
} void linkList::PrintList() {
listNode* tmp = headNode;
if (tmp) {
cout << tmp->nodeVal;
tmp = tmp->nextNode;
while (tmp) {
cout << "->" << tmp->nodeVal;
tmp = tmp->nextNode;
}
cout << endl;
}
else {
cout << "Empty linked list!" << endl;
}
} void linkList::PushBack(const DataType& x) {
if (headNode) {
tailNode->nextNode = new listNode(x);
tailNode = tailNode->nextNode;
}
else {
headNode = new listNode(x);
tailNode = headNode;
}
} void linkList::PushFront(const DataType& x) {
if (headNode) {
listNode* tmp = new listNode(x);
tmp->nextNode = headNode;
headNode = tmp;
}
else {
headNode = new listNode(x);
tailNode = headNode;
}
} void linkList::PopBack() {
if (headNode) {
if (headNode->nextNode) {
listNode* tmp = headNode;
while (tmp->nextNode != tailNode) {
tmp = tmp->nextNode;
}
delete tailNode;
tmp->nextNode = nullptr;
tailNode = tmp;
}
else {
delete headNode;
headNode = nullptr;
tailNode = nullptr;
}
}
else {
cout << "Empty linked list!" << endl;
}
} void linkList::PopFront() {
if (headNode) {
if (headNode->nextNode) {
listNode* tmp = headNode->nextNode;
delete headNode;
headNode = tmp;
}
else {
delete headNode;
headNode = nullptr;
tailNode = nullptr;
}
}
else {
cout << "Empty linked list!" << endl;
}
} DataType linkList::PeekBack() {
if (tailNode) {
return tailNode->nodeVal;
}
else {
cout << "Empty linked list!" << endl;
return -;
}
} DataType linkList::PeekFront() {
if (headNode) {
return headNode->nodeVal;
}
else {
cout << "Empty linked list!" << endl;
return -;
}
} listNode* linkList::Find(DataType x) {
listNode* targetNode = headNode;
while (targetNode) {
if (targetNode->nodeVal == x) {break;}
}
return targetNode;
} void linkList::InsertNext(listNode* pos, DataType x) {
if (pos) {
if (pos == tailNode) {
listNode* tmp = new listNode(x);
pos->nextNode = tmp;
tailNode = tmp;
}
else {
listNode* tmp = new listNode(x);
tmp->nextNode = pos->nextNode;
pos->nextNode = tmp;
}
}
else {
cout << "Invalid position!" << endl;
}
} void linkList::DeleteNext(listNode* pos) {
if (pos) {
if (pos == tailNode) {
cout << "Invalid node!" << endl;
}
else {
listNode* tmp = (pos->nextNode)->nextNode;
delete pos->nextNode;
pos->nextNode = tmp;
}
}
else {
cout << "Invalid node!" << endl;
}
} void linkList::Remove(DataType x) {
if (headNode) {
if (headNode->nextNode) {
listNode* tmp = headNode;
while (tmp->nextNode) {
if ((tmp->nextNode)->nodeVal == x) {
DeleteNext(tmp);
break;
}
tmp = tmp->nextNode;
}
}
else {
if (headNode->nodeVal == x) {PopFront();}
}
}
} void linkList::RemoveAll(DataType x) {
if (headNode) {
listNode* tmp = headNode;
while (tmp->nextNode) {
if ((tmp->nextNode)->nodeVal == x) {
if (tmp->nextNode == tailNode){
PopBack();
break;
}
else {DeleteNext(tmp);}
}
tmp = tmp->nextNode;
}
if (tmp->nodeVal == x) {
PopBack();
}
}
} void linkList::Clear() {
if (headNode) {
listNode* prev = headNode;
listNode* tmp;
while (prev->nextNode) {
tmp = prev->nextNode;
delete prev;
prev = tmp;
}
headNode = nullptr;
tailNode = nullptr;
}
}
// construction funcs for linkStack
linkStack::linkStack() // without arguments
:linkList()
{} linkStack::linkStack(const linkStack& stack1) // with an argument
:linkList(stack1)
{}
// other public funcs for linkStack
bool linkStack::isEmpty() {
return linkList::isEmpty();
} int linkStack::getSize() {
return linkList::GetLength();
} void linkStack::PushBack(const DataType& x) {
linkList::PushBack(x);
} void linkStack::PopBack() {
linkList::PopBack();
} DataType linkStack::PeekBack() {
return linkList::PeekBack();
}
// construction funcs for linkQueue
linkQueue::linkQueue()
:linkList()
{} linkQueue::linkQueue(const linkQueue& queue1)
:linkList(queue1)
{}
// other public funcs for linkQueue
bool linkQueue::isEmpty() {
return linkList::isEmpty();
} int linkQueue::getSize() {
return linkList::GetLength();
} void linkQueue::PushBack(const DataType& x) {
linkList::PushBack(x);
} void linkQueue::PopFront() {
linkList::PopFront();
} DataType linkQueue::PeekFront() {
return linkList::PeekFront();
}
最后还有测试代码，和主题没什么关系，但是从以前用python学习数据结构开始我就喜好把测试代码写成假交互式，所以索性贴在这里方便取用。
#include <iostream>
#include "linked_list.h"
#include <stdlib.h>
#include <map> using namespace std; static map<string, int>stringVal {
{"Exit", },
{"Printlist", },
{"Pushback", },
{"Pushfront", },
{"Popback", },
{"Popfront", },
{"Clear", },
{"Remove", },
{"Removeall", },
{"Sort", },
{"Getlength", },
{"Index", },
{"Peekback", },
{"Peekfront", }
}; int test_list() {
linkList list1;
cout << ">> Linked list tesing.\n"
">> Enter a direction, namely Printlist, Pushback, Pushfront, Popback, Peekback, "
"Popfront, Peekfront, Clear, Remove, Removeall, Sort, Getlength or Index,"
"enter Exit to exit." << endl;
string direction;
DataType parameter;
int param;
while () {
cout << ">> ";
cout.flush();
cin >> direction;
switch(stringVal[direction])
{
case :
return ;
case :
list1.PrintList();
break;
case :
cin >> parameter;
list1.PushBack(parameter);
break;
case :
cin >> parameter;
list1.PushFront(parameter);
break;
case :
list1.PopBack();
break;
case :
list1.PopFront();
break;
case :
list1.Clear();
break;
case :
cin >> parameter;
list1.Remove(parameter);
break;
case :
cin >> parameter;
list1.RemoveAll(parameter);
break;
/* case 9:
list1.Sort();
break;*/
case :
param = list1.GetLength();
cout << ">> " << param << endl;
break;
case :
cin >> param;
parameter = list1[param];
cout << ">> " << parameter << endl;
break;
case :
parameter = list1.PeekBack();
cout << ">> " << parameter << endl;
break;
case :
parameter = list1.PeekFront();
cout << ">> " << parameter << endl;
}
}
return ;
} int test_stack() {
linkStack stack1;
cout << ">> Linked list stack tesing.\n"
">> Enter a direction, namely Pushback, Popback or Peekback, "
"enter Exit to exit." << endl;
string direction;
DataType parameter;
int param;
while () {
cout << ">> ";
cout.flush();
cin >> direction;
switch(stringVal[direction])
{
case :
return ;
case :
cin >> parameter;
stack1.PushBack(parameter);
break;
case :
stack1.PopBack();
break;
case :
parameter = stack1.PeekBack();
cout << ">> " << parameter << endl;
break;
}
}
return ;
} int main() {
test_stack();
return ;
}
假交互式测试代码, test(), main()