单链表的结构有多种
这里介绍的链表有头结点、有尾节点并且尾节点指向头结点
单链表的每个结点的地址存放在其直接前驱结点的指针域中。其中第一个结点没有前驱结点，因此需要一个头指针指向第一个节点，便于我们对整个链表进行操作；这里的单链表的最后一个节点的指针域存放的是头结点的地址。
单链表不能随意存取，必要的时候我们可以通过已知结点的指针域不断遍历从而获取我们要的结点。
SList.h
/****************************************************************************************************/
/*
功能：应用C++语言实现单链表的各项操作
建立链表的节点类LinkNode，封装一个SList类将有效节点链接起来
基本的成员函数：
构造函数、拷贝构造函数、赋值运算符的重载、析构函数
**
**单链表的具体操作：
** 1：在尾部插入节点
** 2：打印单链表
** 3：链表置空
** 4：尾除尾节点
** 5：头插
** 6：删除首节点
** 7：固定位置插入一个节点
** 8：删除某一节点
** 9：查找某节点并返回这个节点的位置
** 10：计算链表节点的数目
** 11：查找某节点并删除
** 12：删除链表中所有的x
** 13：去重
** 14：合并两个链表
** 15：冒泡排序
** 16：翻转单链表
**
** By ：Lynn-Zhang
**
*/
/*****************************************************************************************************/
//****************/
typedef int DataType;
//节点类（复合形态）
//struct LinkNode
//{
// friend class SList; //将SList设为友元，便于SList类可以访问节点类的私有成员
//public:
// LinkNode(const DataType x);
//private:
// DataType _data; //节点的数据
// LinkNode* _next; //指向该节点的下一个节点
//};
//直接用struct定义LinkNode类，因为struct的成员默认为公有数据成员，所以可直接访问
struct LinkNode //节点类(建议写法)
{
LinkNode(const DataType x);
DataType _data; //节点的数据
LinkNode* _next; //指向该节点的下一个节点
};
class SList
{
public:
SList(); //构造函数
SList(const SList& s); //拷贝构造
SList &operator=(SList& s); //赋值运算符的重载
~SList();
public:
//单链表的具体操作
void Uniqe(); //去重
void Merge(SList &s); //合并
void Sort(); //冒泡
void Reverse(); //翻转
void Swap(SList& s); //交换
void PrintSList(); //打印链表
void PushBack(const DataType& x); //在尾部插入一个节点
void Clear(); //链表置空
void PopBack(); //删除尾节点
void PushFront(DataType x); //头插
void PopFront(); //删除首节点
void Insert(LinkNode* pos, DataType x);//固定位置插入一个节点
void Erase(LinkNode* pos); //删除某一节点
LinkNode* Find(DataType x); //查找节点并返回这个节点的地址
int Amount(); //计算链表节点的数目
void Remove(DataType x); //查找某节点并删除
void RemoveAll(DataType x); //删除链表中所有的x
private:
LinkNode* _head; //指向头节点
LinkNode* _tail; //指向尾节点
};
//*********************//
SList.cpp (函数实现)
//**********************/////////
#include<iostream>
using namespace std;
#include<assert.h>
#include"SList.h"
LinkNode::LinkNode(const DataType x)
:_data(x)
, _next(NULL)
{}
SList::SList() //构造函数
:_head(NULL)
, _tail(NULL)
{}
SList::SList(const SList& s) //拷贝构造
:_head(NULL)
, _tail(NULL)
{
if (s._head == NULL)
{
return;
}
LinkNode* tmp = s._head;
do{
PushBack(tmp->_data);
tmp = tmp->_next;
} while (tmp != s._head);
}
//赋值运算符的重载（传统方法）
//SList & SList::operator=(const SList& s)
//{
// if (this != &s)
// {
// _head = NULL;
// _tail = NULL;
// LinkNode* tmp = s._head;
// do{
// PushBack(tmp->_data);
// tmp = tmp->_next;
// } while (tmp != s._head);
// }
// return *this;
//}
//赋值运算符的重载（高效写法）
/*void SList::Swap(SList& s)
{
swap(_head, s._head);
swap(_tail, s._tail);
}
SList& SList::operator=(SList &s)
{
if (this != &s)
{
SList tmp(s);
Swap(tmp);
}
return *this;
}*/
SList& SList::operator=(SList &s) //赋值运算符的重载再优化(推荐写法)
{
if (this != &s)
{
swap(_head, s._head);
swap(_tail, s._tail);
}
return *this;
}
SList::~SList() //析构
{
Clear();
}
void SList::Reverse() //链表逆置（利用头插新节点的方法）
{
if (_head == NULL||_head->_next==_tail)
{
return;
}
int ret = Amount();
_tail = new LinkNode(_head->_data);
LinkNode* begin=NULL;
LinkNode* tmp = _tail;
while (--ret)
{
LinkNode* del = _head;
_head = _head->_next;
delete del; //这里不要忘记做清理工作，否则内存泄漏
begin = new LinkNode(_head->_data);
begin->_next = tmp;
_tail->_next = begin;
tmp = begin;
}
_head = begin;
}
//打印链表
void SList::PrintSList()
{
//头结点为空时，无需打印链表
if (_head==NULL)
{
cout << "This SList is Empty !" << endl;
return;
}
else
{
LinkNode* tmp = _head;
do{
cout << tmp->_data << "-->";
tmp = tmp->_next;
} while (tmp != _head);
cout << endl;
}
}
void SList::PushBack(const DataType& x) //在尾部插入一个节点
{
//如果链表为空，插入节点后只有一个节点，此时_head=_tail
if (_head == NULL)
{
_head = new LinkNode(x);
_tail = _head;
_tail->_next = _head;
}
else
{
_tail->_next = new LinkNode(x);
_tail = _tail->_next;
_tail->_next = _head;
}
}
void SList::Clear() //链表置空
{
LinkNode* begin = _head;
while (begin != _tail)
{
_head = _head->_next;
delete begin;
begin = _head;
}
_head = NULL;
_tail = NULL;
}
void SList::PopBack() //尾删
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
}
else if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = NULL;
}
else
{
LinkNode* cur = _head;
while (cur->_next != _tail)
{
cur = cur->_next;
}
delete _tail;
_tail = cur;
_tail->_next = _head;
}
}
void SList::PushFront(DataType x) //头插
{
if (_head == NULL)
{
PushBack(x);
}
else
{
LinkNode* tmp = _head;
_head = new LinkNode(x);
_head->_next = tmp;
_tail->_next = _head;
}
}
void SList::PopFront() //删除首节点
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return;
}
LinkNode* tmp = _head;
_head = _head->_next;
_tail->_next = _head;
delete tmp;
}
//固定位置插入一个节点（这个函数需和Find函数搭配使用）
//先用Find函数找到新节点需要插入的位置
//（将Find函数的返回值传给Insert函数的参数pos）,再在pos节点后面插入新节点x
void SList::Insert(LinkNode* pos, DataType x)
{
assert(pos);
if (pos==_tail)
{
PushBack(x);
}
else
{
LinkNode* tmp = new LinkNode(x);
tmp->_next = pos->_next;
pos->_next = tmp;
}
}
//删除某一节点，同样，要先找到该节点并传参给Erase函数
void SList::Erase(LinkNode* pos)
{
assert(pos);
if (pos == _tail)
{
PopBack();
}
if (pos == _head)
{
PopFront();
}
else
{
LinkNode* prev = _head;
while (prev->_next != pos)
{
prev = prev->_next;
}
prev->_next = pos->_next;
delete pos;
}
}
LinkNode* SList::Find(DataType x) //查找节点并返回这个节点的地址
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return NULL;
}
else
{
LinkNode* tmp = _head;
do{
if (tmp->_data == x)
{
return tmp;
}
tmp = tmp->_next;
} while (tmp != _head);
return NULL;
}
}
int SList::Amount() //计算链表节点的数目
{
if (_head == NULL)
{
return 0;
}
else
{
int count = 0;
LinkNode* cur = _head;
while (cur != _tail)
{
count++;
cur = cur->_next;
}
return ++count;
}
}
void SList::Remove(DataType x) //查找某节点并删除
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
}
else
{
LinkNode* tmp = Find(x);
if (tmp != NULL)
{
Erase(tmp);
}
}
}
void SList::RemoveAll(DataType x) //删除链表中所有的x
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return;
}
//如果链表不为空，设置left和right前后指针，从头至尾遍历一遍，delete节点的data为x的节点
LinkNode* left = _tail;
LinkNode* right = _head;
int count = Amount();
while (count--)
{
//当要删掉的节点是头节点时，需要注意头节点要指向它的下一个节点
//当要删掉的节点是尾节点时，需要注意尾节点要指向它的上一个节点
//当left和right指向同一块要删掉的节点时，将链表置空
if (right->_data == x)
{
if (_head == right)
{
_head = _head->_next;
}
if (_tail == right)
{
_tail =left;
}
if (right == left)
{
_head = NULL;
_tail = NULL;
return;
}
LinkNode* tmp = right;
right = right->_next;
delete tmp;
left->_next = right;
}
else
{
left = right;
right = right->_next;
}
}
}
void SList::Uniqe() //去重(针对有序链表)
{
assert(_head &&_head!= _tail);
LinkNode* left = _head;
LinkNode* right = _head->_next;
while (left != _tail)
{
while(left->_data == right->_data)
{
LinkNode* tmp = right;
right = right->_next;
left->_next = right;
delete tmp;
}
left = left->_next;
right = right->_next;
}
}
void SList::Merge(SList &s) //合并（针对有序链表）,合并后依然有序
{
// 1. _head为空
// 2. 链表s为空
if (_head == NULL)
{
_head = s._head;
_tail = s._tail;
}
if (s._head == NULL)
{
return;
}
// 3. 两个链表都不为空
LinkNode* phead = _head;
if (phead->_data <= s._head->_data)
{
phead = phead->_next;
}
else
{
_head = s._head;
s._head = s._head->_next;
}
LinkNode* cur = _head;
while (1)
{
if (phead->_data <= s._head->_data)
{
_head->_next = phead;
_head = _head->_next;
if (phead == _tail)
{
_head->_next = s._head;
_tail=s._tail;
_tail->_next = cur;
break;
}
phead = phead->_next;
}
else
{
_head->_next = s._head;
_head = _head->_next;
if (s._head ==s._tail)
{
_head->_next = phead;
_tail->_next = cur;
break;
}
s._head = s._head->_next;
}
}
_head = cur;
}
void SList::Sort() //冒泡排序
{
assert(_head);
if (_head == _tail)
{
return;
}
int size = Amount();
for (int i = 0; i < size-1 ; i++)
{
LinkNode* left = _head;
LinkNode* right = _head->_next;
for (int j = 0; j < size - i-1 ; j++)
{
if (left->_data>right->_data)
{
swap(left->_data, right->_data);
}
right = right->_next;
left = left->_next;
}
}
}
///************************
测试用例（Test.cpp）
#include"SList.h"
#include<stdlib.h>
void Test3()
{
//排序 去重 合并
cout << "list 1:" << endl;
SList list1;
/*list1.PushBack(2);
list1.PushBack(3);
list1.PushBack(2);
list1.PushBack(2);
list1.PushBack(1);
list1.PrintSList();
list1.Sort();
list1.PrintSList();
list1.Uniqe();
list1.PrintSList();*/
list1.PushBack(5);
list1.PushBack(3);
list1.PushBack(8);
list1.PushBack(2);
list1.PushBack(9);
list1.PushBack(10);
list1.PushBack(2);
list1.PushBack(2);
list1.PushBack(1);
list1.PrintSList();
list1.Sort();
list1.PrintSList();
cout << "list 2:" << endl;
SList list2;
list2.PushBack(1);
list2.PushBack(6);
list2.PushBack(4);
list2.PushBack(0);
list2.PushBack(7);
list2.PrintSList();
list2.Sort();
list2.PrintSList();
cout << "list 1:" << endl<<endl;
list1.Merge(list2);
list1.PrintSList();
}
void Test2()
{
SList list1;
list1.PushBack(1);
list1.PushBack(3);
list1.PushBack(4);
list1.PushBack(2);
list1.PushBack(6);
list1.PrintSList();
/*list1.RemoveAll(2);
list1.PrintSList();*/
SList list2 = list1;
/*list2.PushBack(2);
list2.PushBack(3);
list2.PushBack(4);
list2.PushBack(2);
list2.PushBack(2);*/
list2.PrintSList();
list2.Reverse();
list2.PrintSList();
}
void Test1()
{
//SList list1;
//list1.PushBack(1);
//list1.PushBack(2);
//list1.PushBack(3);
//list1.PushBack(4);
//list1.PushBack(5);
//list1.PrintSList();
//list1.Remove(2);
//list1.PrintSList();
//int num =list1.Amount();
//cout <<"节点个数："<< num << endl;
/*//检验Erase函数
LinkNode* del = list1.Find(2);
list1.Erase(del);
list1.PrintSList();
*/
/*//找到某节点并在其后插入新节点
LinkNode* In =list1.Find(5);
list1.Insert(In, 0);
list1.PrintSList();*/
/* //删除头结点
list1.PopFront();
list1.PrintSList();
*//////
/*//////查找节点
LinkNode* ret=list1.Find(5);
if (ret != NULL)
{
cout << "要查找的节点data是：" << ret->_data << endl;
cout << "要查找的节点adress是：" <<ret<< endl;
}
else
{
cout << "not exit !" << endl;
}*////////
//验证构造函数
//SList list2(list1);
//list2.PrintSList();
//验证赋值运算符的重载
//SList list3 = list2;
//list3.PrintSList();
//验证析构函数
//list3.Clear();
//list3.PrintSList();
//验证尾删和头插
///*list3.PopBack();
//list3.PrintSList();*/
//list3.PushFront(0);
//list3.PrintSList();
}
int main()
{
//Test1();