溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
單鏈表演示圖：
單鏈表結構體：
struct Node
{
Node(const DataType& d)//節點的構造函數
:_data(d)
,_next(NULL)
{}
DataType _data; //數據
struct Node *_next; //指向下一個節點的指針
};帶頭結點和尾節點的單鏈表：
多一個Tail指針的好處就是很方便可以找到鏈表尾部，方便在尾部插入一個元素什么的。
下面我們用類來實現單鏈表：
class SList
{
friend ostream& operator<<(ostream& os, const SList& s); //輸出運算符重載(友元)
public:
SList() //構造函數
:_head(NULL)
,_tail(NULL)
{}
SList(const SList& s) //拷貝構造
:_head(NULL)
, _tail(NULL)
{
Node *cur = _head;
while (cur)
{
PushBack(cur->_data );
cur = cur->_next;
}
_tail = cur;
}
~SList() //析構函數
{
if (_head == NULL)
return;
Node *cur = _head;
if (cur != NULL)
{
Node *del = cur;
cur = cur->_next;
delete del;
}
_tail = NULL;
_head = NULL;
}
SList& operator=(SList s) //賦值運算符重載
{
swap(_head, s._head);
swap(_tail, s._tail);
return *this;
}單鏈表最基本的四個函數：
void SList::PushBack(const DataType& d) //尾插
{
Node *newNode = new Node(d); //構建一個新的節點
if (_head == NULL)
{
_head = newNode;
_tail = newNode;
}
else
{
_tail->_next = newNode;
_tail = newNode;
}
}
void SList::PushFront(const DataType& d) //頭插
{
Node *newNode = new Node(d);
if (_head == NULL)
{
_head = newNode;
_tail = newNode;
}
else
{
newNode->_next = _head;
_head = newNode;
}
}
void SList::PopBack() //尾刪
{
if (_head == NULL)
return;
else if (_head == _tail)
{
delete _tail;
_tail = NULL;
_head = NULL;
}
else
{
Node *cur = _head;
while (cur->_next != _tail)
{
cur = cur->_next;
}
delete _tail;
_tail = cur;
_tail->_next = NULL;
}
}
void SList::PopFront() //頭刪
{
if (_head == NULL)
return;
else if (_head == _tail)
{
delete _tail;
_tail = NULL;
_head = NULL;
}
else
{
Node *del = _head;
_head = _head->_next;
delete del;
}
}給一個數據，若找到該節點則返回該節點，沒找到則返回NULL
Node* SList::Find(const DataType& d)
{
Node *cur = _head;
while (cur != NULL)
{
if (cur->_data == d)
return cur;
cur = cur->_next;
}
return NULL;
}給定一個節點，在該節點后插入一個新的節點
void SList::Insert(Node* pos, const DataType& d)
{
Node *newNode = new Node(d);
if (pos == _tail) //若給定的節點是尾節點，此處可以直接調用尾插
{
_tail->_next = newNode;
_tail = newNode;
}
else
{
newNode->_next = pos->_next;
pos->_next = newNode;
}
}鏈表的逆序：此處用三個指針來實現
void SList::Reverse()
{
Node *p1 = NULL;
Node *p2 = _head;
Node *newhead = NULL;
while (p2)
{
p1 = p2;
p2 = p2->_next;
p1->_next = newhead;
newhead = p1;
}
_head = newhead;
}鏈表的排序：采用冒泡排序
void SList::Sort()
{
Node *cur = _head;
Node *end = NULL;
while (cur != end)
{
while (cur->_next != end)
{
if (cur->_data > cur->_next->_data)
{
DataType tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data = tmp;
}
cur = cur->_next;
}
end = cur;
cur = _head;
}
}刪除某個節點（給定一個數據，刪除數據與之相等的第一個節點）
void SList::Remove(const DataType& d)
{
Node *cur = _head;
while (cur != NULL)
{
if (cur->_data == d)
{
Node *del = cur->_next;
DataType tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data = tmp;
cur->_next = cur->_next->_next;
delete del;
return;
}
cur = cur->_next;
}
}刪除某些節點（給定一個數據，刪除數據與之相等的每一個節點）
void SList::RemoveAll(const DataType& d)
{
Node *cur = _head;
while (cur != NULL)
{
if (cur->_data == d)
{
Node *del = cur->_next;
DataType tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data = tmp;
cur->_next = cur->_next->_next;
delete del;
}
cur = cur->_next;
}
return;
}刪除非尾節點
void SList::EarseNotTail(Node *pos)
{
Node *del = pos;
Node *cur = _head;
while (cur->_next!=pos) //找到該節點的前一個節點
{
cur = cur->_next;
}
cur->_next = pos->_next; //讓它的_next指向要刪除節點的_next
delete del;
}找到中間節點
Node* SList::FindMinNode() //快慢指針問題
{ //兩個指針都指向頭結點
Node *cur = _head; //快的一次走兩步，慢的一次走一步
Node *fast = cur; //當快指針走到尾的時候，慢指針指向中間節點
Node *slow = cur;
while (fast)
{
fast = fast->_next->_next;
slow = slow->_next;
}
return slow;
}刪除倒數第K個節點
void SList::DelKNode(int k)
{
Node *cur = _head;
int i = k - 1;
while (i) //先讓cur指向正數第K個節點
{
cur = cur->_next;
i = i - 1;;
}
Node *p1 = _head;
Node *tmp = NULL;
while (cur->_next ) //讓一個指向頭結點的指針和cur一起走
{
tmp = p1;
p1 = p1->_next;
cur = cur->_next; //當cur指向尾節點時，那個指針指向倒第K個節點
}
Node *del = p1;
tmp->_next = p1->_next ;
delete p1;
}檢測是否帶環
//檢測是否帶環
int SList::CheckCycle(const SList& s) //快慢指針問題
{
Node *fast = _head;
Node *slow = _head;
while (slow)
{
if (slow == fast)
{
return 1;
}
fast = fast->_next->_next;
slow = slow->_next;
}
return 0;
}獲取環的入口點
Node* SList::GetCycleEoryNode()
{
Node *cur = _head;
while (cur)
{
if (cur == _tail)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}判斷是否相交
int SList::CheckCross(SList& l1, SList& l2)
{
int count1 = l1.LengthOfList(l1);
int count2 = l2.LengthOfList(l2);
if (count1 > count2)
{
Node *cur = l1._head;
while (cur)
{
if (l2._tail == cur)
return 1;
cur = cur->_next;
}
}
else
{
Node *cur = l2._head;
while (cur)
{
if (l1._tail == cur)
return 1;
cur = cur->_next;
}
}
return 0;
}合并兩個鏈表
int SList::CheckCross(SList& l1, SList& l2)
{
int count1 = l1.LengthOfList(l1);
int count2 = l2.LengthOfList(l2);
if (count1 > count2)
{
Node *cur = l1._head;
while (cur)
{
if (l2._tail == cur)
return 1;
cur = cur->_next;
}
}
else
{
Node *cur = l2._head;
while (cur)
{
if (l1._tail == cur)
return 1;
cur = cur->_next;
}
}
return 0;
}求兩個鏈表的交點
Node* SList::GetLinkCross(SList& l1, SList& l2)
{
int count1 = l1.LengthOfList(l1);
int count2 = l2.LengthOfList(l2);
Node *cur1 = l1._head;
Node *cur2 = l2._head;
if (count1 > count2)
{
Node *cur1 = l1._head;
Node *cur2 = l2._head;
while (cur2)
{
if (cur2->_next == cur1->_next )
return cur1;
else
{
cur1 = cur1->_next;
cur2 = cur2->_next;
}
}
}
else
{
Node *cur1 = l1._head;
Node *cur2 = l2._head;
while (cur1)
{
if (cur2->_next == cur1->_next)
return cur1;
else
{
cur1 = cur1->_next;
cur2 = cur2->_next;
}
}
}
return NULL;
}求鏈表長度
int SList::LengthOfList(const SList& s)
{
int length = 0;
Node *cur = _head;
while (cur)
{
length++;
cur = cur->_next;
}
return length;
}
以后會有改進版奉上，希望大家多多支持
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
