- 数据结构之单链表C++版
- 包含的头文件
- 结构体描述链表节点
- 链表再封装
- 各个成员函数的实现
- 获取当前链表的大小
- 判断链表是否为空链表
- 头插法插入数据
- 尾插法插入数据
- 指定位置插入数据
- 打印链表中的数据
- 清理链表中的节点
- 从链表头部开始删除节点
- 从链表尾部开始删除节点
- 指定位置删除节点
- 查找链表中的数据
- 指定位置修改数据
- 主函数测试
C++中有STL的list底层是双向链表，这里重新写一个单链表，就是写着玩。 包含的头文件
#include
其他就是不用了，如果想严谨一点就再加一个new头文件
#include结构体描述链表节点
struct Node
{
int data;
Node* next;
Node(int data = 0):data(data),next(nullptr){}
};
因为C++可以直接使用结构体名定义结构体变量，所以就是不用typedef来起别名了。
链表再封装class List
{
public:
//构造函数
List()
{
this->size = 0;
this->headNode = nullptr;
}
//析构函数
~List()
{
clear(); //清理链表中的节点
delete[] this->headNode; //释放头节点内存
}
int getSize() { return this->size; } //获取当前链表的大小
bool empty() { return this->size == 0; } //判断链表是否为空链表
void push_front(int data); //头插法插入数据
void push_back(int data); //尾插法插入数据
void insertByPos(int pos, int data); //指定位置插入数据
void print_front(); //打印链表中的数据
void clear(); //清理链表中的节点
void pop_front(); //从链表头部开始删除节点
void pop_back(); //从链表尾部开始删除节点
void deleteByPos(int pos); //指定位置删除节点
bool scearch(int num); //查找链表中的数据
void changeData(int newNum, int pos); //指定位置修改数据
protected:
int size; //万金油参数，当前链表的大小
Node* headNode; //指向链表的头节点
};
这样一个链表就已经写好了，后面的事情就是一个个去实现链表中的成员函数。
各个成员函数的实现只供参考使用
获取当前链表的大小直接返回List类中的size数据成员，size数据成员在一开始调用构造函数的时候默认初始化为零，然后在增加和删除操作会对应的进行自增和自减操作。
int getSize() { return this->size; }
判断链表是否为空链表
直接判断size成员是否为零，如果为零返回true不为零则返回false。
bool empty() { return this->size == 0; }
头插法插入数据
从外界接收一个要插入的数据，然后在函数中动态申请一个节点的内存newNode，判断链表是否为空，如果为空就直接让链表的头节点指针指向newNode，如果不为空就采用先连接后移动头节点位置，防止断链。连接完成后不要忘记给size属性做自增运算。
void List::push_front(int data)
{
Node* newNode = new Node(data);
if (this->size == 0)
{
this->headNode = newNode;
}
else
{
newNode->next = this->headNode;
this->headNode = newNode;
}
this->size++;
}
尾插法插入数据
从外界接收一个数据，用来初始化节点中的data数据，然后在函数中申请一段内存newNode，判断链表是否为空，为空就直接把链表的头节点指针指向newNode，如果不为空就是定义一个移动指针pMove让pMove走到表尾，然后就直接让pMove->next指针指向newNdoe，这样就链接完成了。还是一样，新节点连接到链表中后不要忘记给size属性做自增运算。
void List::push_back(int data)
{
Node* newNode = new Node(data);
if (this->size == 0)
{
this->headNode = newNode;
}
else
{
Node* pMove = this->headNode;
while (pMove->next != nullptr)
{
pMove = pMove->next;
}
pMove->next = newNode;
}
this->size++;
}
指定位置插入数据
这个函数的参数除了需要一个节点data属性需要的外，还需要一个pos数据表示链表的第几个节点，进入到函数之后先判断size属性是否为零，因为size属性为零就不存在坐标pos的说法了，内存都没有谈什么坐标。然后就是pos是否在size属性范围之内，如果超出了size能控制的那也可以直接结束掉整个函数了。上面的情况都不满足就是直接判断pos是否为0如果为零就直接调用已经写好的头插入插入数据函数，如果pos刚好等于size那就调用表尾法插入数据的函数。最后才是pos在1到size-1节点内的范围。用一个移动指针pMove去遍历链表，直到遍历到pos对应的节点为止，这个用循环来做，跳出循环的时候就可以直接做插入操作了，至于要在找到pos对应的节点的左边插入新节点还是在它的右边插入新节点看个人想法，想怎么插入就怎么插入。
void List::insertByPos(int pos, int data)
{
if (this->size == 0 || pos > this->size || pos < 0)
return;
else if (pos == 0)
push_front(data);
else if (pos == this->size)
push_back(data);
else
{
Node* pMove = this->headNode;
Node* newNode = new Node(data);
while (pos > 0)
{
pMove = pMove->next;
pos--;
}
newNode->next = pMove->next;
pMove->next = newNode;
this->size++;
}
}
打印链表中的数据
因为这个链表是单链表，所以只能从头开始打印链表的数据。思路很简单，就是用一个移动指针去遍历整个链表，边移动边打印，直到移动指针pMove指向空为止。最后可以来一个换行，让结果好看一点。
void List::print_front()
{
Node* pMove = this->headNode;
while (pMove != nullptr)
{
cout << pMove->data << 't';
pMove = pMove->next;
}
cout << endl;
}
清理链表中的节点
这个和一开始写C语言般的单链表是一样的其实，思路就是让移动指针遍历链表，删除指针做记录，记录了之后就删除掉删除指针指向的节点，一直遍历到链表尾部。这里一开始不删除头节点，防止断链。因为这个程序中调用clear函数是在析构函数的时候调用所以size属性置不置为零都问题不大，因为当我调用这个函数的时候，我也不想要这个链表了。
void List::clear()
{
Node* pDelete;
Node* pMove = this->headNode->next;
while (pMove != nullptr)
{
pDelete = pMove;
pMove = pMove->next;
delete pDelete;
pDelete = nullptr;
}
}
从链表头部开始删除节点
和上面clear函数不同的就是，上面clear函数释放掉链表的所有节点，而当前这个函数只会把头节点删除，在删除头节点之前先做记录，记录完，让头节点指向写一个节点，最后删除刚刚记录的节点。整个函数的思路就是这样。记得删除了之后给size属性做自减运算。
void List::pop_front()
{
Node* pDelete = this->headNode;
this->headNode = this->headNode->next;
pDelete->next = nullptr;
delete pDelete;
pDelete = nullptr;
this->size--;
}
从链表尾部开始删除节点
因为单链表只能从头开始往后走，不能反着来，所以先定义一个移动指针pMove和一个做记录的指针pMove_left，当pMove->next指向空的时候意味着pMove已经走到链表的最后一个节点了，然后就可以做删除操作了。删除操作就直接使用pMove_left->next指向空或者是指向pMove->next然后释放pMove指针就行。
void List::pop_back()
{
Node* pMove_left = this->headNode;
Node* pMove = this->headNode->next;
while (pMove->next != nullptr)
{
pMove_left = pMove;
pMove = pMove->next;
}
pMove_left->next = nullptr;
delete pMove;
pMove = nullptr;
this->size--;
}
指定位置删除节点
既然说是指定位置，那就肯定需要一个pos数据表示坐标，传进来，传进来之后先判断这个pos是不是在size能管理的范围之内，如果不是就直接结束掉整个函数，如果pos等于0或者等于size就直接调用对应的pop_front函数或pop_back函数。最后才是在1到size-1区间里。思路也很简单，定义一个移动指针pMove用于遍历，还有一个指针pMove_left用于记录pMove走过的节点。走到pos的位置之后就用pMove_left->next指向pMove->next，然后pMove->next指向空然后释放pMove中的内存，最后pMove指向空，这样指定位置删除的操作就做完了，最后别忘了给size属性做自减运算。
void List::deleteByPos(int pos)
{
if (pos<0 || pos>this->size)
return;
else if (pos == 0)
pop_front();
else if (pos == this->size)
pop_back();
else
{
Node* pMove = this->headNode->next;
Node* pMove_left = this->headNode;
while (pos > 1)
{
pMove_left = pMove;
pMove = pMove->next;
pos--;
}
pMove_left->next = pMove->next;
pMove->next = nullptr;
delete pMove;
pMove = nullptr;
this->size--;
}
}
查找链表中的数据
函数需要的参数是要查找链表中的数据，然后对这个数据去判断链表中是否有这样的数据，如果有就返回true如果没有就返回false。找的时候也是通过一个移动指针去遍历链表，每走一步就判断一下pMove指向的节点的data数据是否和形参num的数据是一样的。找到了就跳出循环，没找到就是继续往后找直到pMove走到了空位置。
bool List::scearch(int num)
{
Node* pMove = this->headNode;
while (pMove != nullptr && pMove->data != num)
{
pMove = pMove->next;
}
if (pMove == nullptr)
return false;
else
return true;
}
指定位置修改数据
函数需要的参数是新的数据newNum和指定的坐标pos。指定位置系列的函数，我都比较喜欢先判断pos是不是size属性的范围之内的，不是就直接结束掉函数，然后判断要修改是数据是不是头节点或者是尾节点，如果刚好是的话就是直接调用已经写好的函数，然后这个修改的操作刚刚好没有，那就直接来吧。当pos等于零的时候就直接将头节点headNode里的data数据修改成newNum；当pos等于size的时候就定义一个移动指针pMove走到链表表尾，然后执行pMove->data=newNum就可以了；最后是pos是在1到size-1的区间，也是先定义一个移动指针pMove去找pos位置的节点，找到了之后就直接修改就行。整个思路就是这么简单，代码实现起来也不是特别困难。
void List::changeData(int newNum, int pos)
{
if (pos<0 || pos>this->size)
return;
else if (pos == 0)
this->headNode->data = newNum;
else if (pos == this->size)
{
Node* pMove = this->headNode;
while (pMove->next != nullptr)
{
pMove = pMove->next;
}
pMove->data = newNum;
}
else
{
Node* pMove = this->headNode;
while (pos > 1)
{
pMove = pMove->next;
pos--;
}
pMove->data = newNum;
}
}
主函数测试
上面的各个成员函数已经写好，然后通过主函数来测试一下我写的代码：
int main()
{
List myList;
for (int i = 0; i < 3; i++)
{
myList.push_front(i);
}
cout << myList.getSize() << endl;
myList.print_front();
myList.pop_front();
cout << "====================" << endl;
cout << myList.getSize() << endl;
myList.print_front();
myList.push_back(99);
myList.print_front();
myList.insertByPos(2, 1001);
cout << myList.getSize() << endl;
myList.print_front();
myList.insertByPos(4, 520);
cout << myList.getSize() << endl;
myList.print_front();
myList.pop_back();
cout << myList.getSize() << endl;
myList.print_front();
myList.deleteByPos(2);
cout << myList.getSize() << endl;
myList.print_front();
if (myList.scearch(99))
cout << "找到目标" << endl;
else
cout << "未找到目标" << endl;
cout << "================" << endl;
if (myList.scearch(1001))
cout << "找到目标" << endl;
else
cout << "未找到目标" << endl;
myList.changeData(88, 3);
cout << myList.getSize() << endl;
myList.print_front();
cout << "===================" << endl;
myList.changeData(66, 2);
cout << myList.getSize() << endl;
myList.print_front();
return 0;
}
输出结果：
3 2 1 0 ==================== 2 1 0 1 0 99 4 1 0 99 1001 5 1 0 99 1001 520 4 1 0 99 1001 3 1 0 1001 未找到目标 ================ 找到目标 3 1 0 88 =================== 3 1 66 88
