数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

单链表的基本操作实现

1.头文件

  头文件和源文件分开有很多好处：可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性，同时也可以使代码结构更清晰，方便代码的管理和维护。

LinkList.h

#pragma once#include<assert.h>//定义单链表节点
typedef struct LNode
{int data;LNode* next;}LNode;

test.cpp

#include<iostream>
using namespace std;#include"LinkList.h"

             

2.类定义和多种算法的实现

  （下面所有函数都默认在类中实现）

  我们以带头单向非循环链表为例:

  带头单向非循环链表是一种链表数据结构，其中每个节点包含一个数据域和一个指向下一个节点的指针域。在这种链表中，有一个特殊的节点称为头节点，它指向链表的第一个节点。头节点不是链表的一部分，仅用于方便操作。

             

2.1创建空表

  我们定义了一个名为LinkList的类，代表一个单链表。这个类有两个私有成员：一个指向LNode类型的指针_head，代表链表的头节点，以及一个整型变量_size，代表链表的大小。

//定义单链表类
class LinkList
{
public://默认构造函数LinkList(){_head = new LNode(0);//创建头结点(哨兵位节点)_size = 0;}private:LNode* _head;int _size;
};

             

2.2头插法创建n个元素的线性链表

  先以头插单个元素为例：

  我们可以先创建一个新的节点来存储该元素。然后，检查链表是否为空，如果为空，则新节点就是链表的第一个节点； 否则，新节点将插入到当前头节点的后面。插入完成后，_size（代表链表元素个数的变量）加1。

void push_front(const int& val)
{//创建一个插入的新节点，将要插入的值val赋值给它LNode* newnode = new LNode(val);LNode* cur = _head->next;//保存原来第一个结点//进行头插操作_head->next = newnode;_head->next->next = cur;//连接原来的第一个节点_size++;
}

  加上n循环即可实现头插法创建n个元素的线性链表

//头插法创建n个元素
void push_front_n()
{cout << "请输入要插入的元素个数:";int n;cin >> n;cout << endl;cout << "输入要插入的元素:";while (n){int tmp;cin >> tmp;push_front(tmp);n--;}
}

             

2.3一个带头节点的链表存放一组整数，设计一个算法删除值等于x的所有节点。

  无返回值版本

  我们先检查链表是否为空，如果为空，则输出一条错误消息并返回。如果链表非空，它开始遍历链表，检查每个节点的下一个节点是否为要删除的节点。如果是，则删除该节点并释放其内存；如果不是，则移动到下一个节点。 在遍历过程中，保持对当前节点的引用，以防止删除连续的要删除的节点时出现问题。

	//删除所有x的节点
void erase_all_x(int x)
{LNode* cur = _head;if (cur->next == nullptr)//判断是否为空链表{cout << "该链表为空不可删除\n";return;}else{while (cur && cur->next)//删除的数据有可能连续，所以最好保持当前节点{if (cur->next->data == x)//如果下一个节点为要删除节点{LNode* tmp = cur->next;//用临时指针保存要删除的节点cur->next = cur->next->next;//链表指向删除节点的下一个节点delete tmp;//删除节点中的元素tmp = nullptr;}else//如果下个节点不是删除节点，那直接指向下个节点{cur = cur->next;}}}
}

  有返回值版本

//删除所有x的节点，有删除节点返回true，无删除节点返回false
bool erase_all_x(int x)
{LNode* cur = _head;if (cur->next == nullptr){cout << "该链表为空不可删除\n";return false;}else{int count = 0;//设计一个计数器，统计是否有删除的节点while (cur && cur->next)//删除的数据有可能连续，所以最好保持当前节点{if (cur->next->data == x){count++;//有删除的节点，count++LNode* tmp = cur->next;cur->next = cur->next->next;//删除x节点delete tmp;tmp = nullptr;}else//如果下个节点不是删除节点，那直接指向下个节点{cur = cur->next;}}if (count == 0)//count==0，则没有可以删除的节点{cout << "链表中没有可以删除的元素" << endl;return false;}return true;}
}

             

2.4计算线性表中值为偶数的节点个数

  我们定义函数用于遍历链表并计算其中偶数节点的数量。首先，它检查链表是否为空，如果为空，则输出一条错误消息。如果链表非空，它开始遍历链表，检查每个节点的数据是否为偶数。如果是偶数，则计数器加1。 遍历完成后，输出链表中偶数节点的数量。

//打印链表中值为偶数的节点个数
void print_even_number()
{LNode* cur = _head->next;int count = 0;if (cur == nullptr){cout << "该链表为空，没有节点\n";}else//核心就在不断通过指针遍历寻找即可{while (cur)//遍历链表中的每一个节点{if (cur->data % 2 == 0){count++;//如果cur为偶数，计数++;}cur = cur->next;}cout << "该链表中偶数节点的个数为:" << count << endl;}
}

             

2.5一个带头节点的单链表heada存放一组整数，设计分裂heada算法，偶数放在heada中，奇数放在headb中

  我们定义该函数用于将链表中的偶数节点和奇数节点分开，使得偶数节点在heada链表中，奇数节点在headb链表中。

  函数使用两个指针cur1和cur2分别遍历heada和headb链表。在遍历过程中，如果当前节点的下一个节点是偶数节点，则保持原链表不变，移动cur1指针；

  如果当前节点的下一个节点是奇数节点，则将其从原链表中删除，并添加到headb链表的末尾，同时移动cur1和cur2指针。 最后，函数返回修改后的heada和headb链表。

//分裂链表，偶数在heada中，奇数在headb中
void divide_LinkList(LNode* heada, LNode* headb)
{LNode* cur1 = heada;LNode* cur2 = headb;while (cur1 && cur1->next)//退出循环的条件要cur1和cur1下个节点不为空{if (cur1->next->data % 2 == 0)//为偶数原链表不变{cur1 = cur1->next;//cur1直接向后移动}else//若链表为奇数，需要移动放入headb中{//交换链表节点操作LNode* tmp = cur1->next;cur1->next = cur1->next->next;//调整cur2，使其获得cur1的节点，断开cur1节点的后面节点的连接cur2->next = tmp;cur2->next->next = nullptr;//cur1和cur2各向后移动cur2 = cur2->next;}}
}

             

3.main函数和源码实现

3.1测试实现：

test_LinkList1();

test_LinkList2();

test_LinkList3();

             

3.2LinkList.h

#pragma once#include<assert.h>//定义单链表节点
typedef struct LNode
{int data;LNode* next;LNode(const int& val):data(val), next(nullptr){}}LNode;//定义单链表类
class LinkList
{
public://默认构造函数LinkList(){_head = new LNode(0);//创建头结点(哨兵位节点)_size = 0;}//拷贝构造函数 lt1(lt)LinkList(const LinkList& lt){LNode* oldcur = lt._head->next;//这个this指针是新建的链表lt1的this->_head = new LNode(0);this->_size = 0;LNode* newcur = _head;while (oldcur)//深拷贝以完成链表的赋值操作{//将旧链表中的值赋值到新链表中LNode* tmp = new LNode(oldcur->data);//向后移动新旧链表节点newcur->next = tmp;newcur = newcur->next;oldcur = oldcur->next;_size++;}}//析构函数~LinkList(){LNode* cur = _head->next;while (cur){LNode* tmp = cur;cur = cur->next;delete tmp;tmp = nullptr;}}//单链表打印void print(){LNode* cur = _head->next;if (cur == nullptr){cout << "该单链表为空\n";}else{cout << "该单链表中的元素为:";while (cur){printf("%d->", cur->data);cur = cur->next;}cout << "NULL\n";}}//单链表尾插void push_back(const int& val){LNode* newnode = new LNode(val);LNode* cur = _head;while (cur && cur->next)//找到尾结点{cur = cur->next;}cur->next = newnode;//尾插_size++;}//单链表头插void push_front(const int& val){LNode* newnode = new LNode(val);LNode* cur = _head->next;_head->next = newnode;_head->next->next = cur;_size++;}//单链表尾删void pop_back(){LNode* cur = _head->next;LNode* prev = _head;if (cur == nullptr){cout << "单链表为空不可删除\n";}else{while (cur && cur->next)//找到尾结点和前一个节点{cur = cur->next;prev = prev->next;}prev->next = nullptr;delete cur;cur = nullptr;_size--;}}//单链表头删void pop_front(){LNode* cur = _head->next;if (cur == nullptr){cout << "单链表为空不可删除\n";}else{_head->next = cur->next;delete cur;cur = nullptr;_size--;}}//头插法创建n个元素void push_front_n(){cout << "请输入要插入的元素个数:";int n;cin >> n;cout << endl;cout << "输入要插入的元素:";while (n){int tmp;cin >> tmp;push_front(tmp);//LNode* newnode = new LNode(tmp);//LNode* cur = _head->next;//if (cur == nullptr)//{//	_head->next = newnode;//}//else//{//	newnode->next = cur;//	_head->next = newnode;//}n--;//_size++;}}//删除第n个元素void erase(int n){assert(n > 0 && n <= _size);LNode* cur = _head;if (cur->next == nullptr){cout << "该链表为空不可删除\n";return;}else{LNode* tmp = cur;while (n)//找到删除节点的前一个位置{tmp = cur;cur = cur->next;n--;}tmp->next = tmp->next->next;delete cur;cur = nullptr;}}//单链表节点个数void print_size(){cout << "单链表节点个数为:" << _size << endl;}//删除所有x的节点，有删除节点返回true，无删除节点返回falsebool erase_all_x(int x){LNode* cur = _head;if (cur->next == nullptr){cout << "该链表为空不可删除\n";return false;}else{int count = 0;//设计一个计数器，统计是否有删除的节点while (cur && cur->next)//删除的数据有可能连续，所以最好保持当前节点{if (cur->next->data == x){count++;//有删除的节点，count++LNode* tmp = cur->next;cur->next = cur->next->next;//删除x节点delete tmp;tmp = nullptr;}else//如果下个节点不是删除节点，那直接指向下个节点{cur = cur->next;}}if (count == 0)//count==0，则没有可以删除的节点{cout << "链表中没有可以删除的元素" << endl;return false;}return true;}}//打印链表中值为偶数的节点个数void print_even_number(){LNode* cur = _head->next;int count = 0;if (cur == nullptr){cout << "该链表为空，没有节点\n";}else{while (cur)//遍历链表中的每一个节点{if (cur->data % 2 == 0){count++;//如果cur为偶数，计数++;}cur = cur->next;}cout << "该链表中偶数节点的个数为:" << count << endl;}}//返回当前链表的头结点LNode* get_head(){return _head;}//分裂链表，偶数在heada中，奇数在headb中void divide_LinkList(LNode* heada, LNode* headb){LNode* cur1 = heada;LNode* cur2 = headb;while (cur1 && cur1->next){if (cur1->next->data % 2 == 0)//为偶数原链表不变{cur1 = cur1->next;}else//若链表为奇数，需要移动放入headb中{//交换链表节点操作LNode* tmp = cur1->next;cur1->next = cur1->next->next;cur2->next = tmp;cur2->next->next = nullptr;//cur1和cur2各向后移动cur2 = cur2->next;}}}private:LNode* _head;int _size;
};

             

3.3test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"LinkList.h"void test_LinkList1()
{LinkList lt;//链表打印lt.print();//测试空链表删除lt.pop_front();//尾插lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print();//头插lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);lt.print();//打印链表节点lt.print_size();//尾删lt.pop_back();lt.pop_back();lt.print();//头删lt.pop_front();lt.pop_front();lt.print();lt.print_size();
}void test_LinkList2()
{//头插法创建n个元素的链表LinkList lt;lt.push_front_n();lt.print();lt.print_size();
}void test_LinkList3()
{LinkList lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.push_back(7);lt.push_back(8);lt.push_back(9);lt.push_back(10);lt.print();lt.print_size();lt.push_back(6);lt.push_back(6);lt.push_back(6);//删除第11节点的元素lt.erase(11);lt.print();//删除所有元素为6的节点cout << "是否删除成功:" << lt.erase_all_x(6) << endl;lt.print();cout << "是否删除成功:" << lt.erase_all_x(6) << endl;lt.print();//打印所有节点为偶数的个数lt.print_even_number();//拷贝构造函数LinkList lt1(lt);lt1.print();lt1.print_size();//编译器生成了默认的赋值运算符重载LinkList lt2 = lt1;lt2.print();//创建空链表LinkList lt3;lt3.print();lt1.push_back(11);lt1.push_back(14);lt1.push_back(12);lt1.push_back(13);lt1.print();//分离链表lt1，使lt1只含有偶数，lt3只含有奇数lt1.divide_LinkList(lt1.get_head(), lt3.get_head());lt1.print();lt3.print();
}int main()
{//不想输入数据就调用test_LinkList1()或test_LinkList3();//test_LinkList1();//test_LinkList2();test_LinkList3();return 0;
}