單鏈表的結構有多種
這裡介紹的鏈表有頭結點、有尾節點並且尾節點指向頭結點
單鏈表的每個結點的地址存放在其直接前驅結點的指針域中。其中第一個結點沒有前驅結點，因此需要一個頭指針指向第一個節點，便於我們對整個鏈表進行操作；這裡的單鏈表的最後一個節點的指針域存放的是頭結點的地址。
單鏈表不能隨意存取，必要的時候我們可以通過已知結點的指針域不斷遍歷從而獲取我們要的結點。
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();
Test2();
system("pause");
}
本文利用C++語言，在Windows平台 Visual Studio 2013開發環境下實現
