單鏈表（C++實現）

来源:http://www.cnblogs.com/Lynn-Zhang/archive/2016/04/15/5396637.html
-Advertisement-
Play Games

單鏈表的結構有多種 這裡介紹的鏈表有頭結點、有尾節點並且尾節點指向頭結點 單鏈表的每個結點的地址存放在其直接前驅結點的指針域中。其中第一個結點沒有前驅結點，因此需要一個頭指針指向第一個節點，便於我們對整個鏈表進行操作；這裡的單鏈表的最後一個節點的指針域存放的是頭結點的地址。 單鏈表不能隨意存取，必要 ...


單鏈表的結構有多種

這裡介紹的鏈表有頭結點、有尾節點並且尾節點指向頭結點

wKioL1btPpKSlsBmAAAKFtUh58k849.png

 

單鏈表的每個結點的地址存放在其直接前驅結點的指針域中。其中第一個結點沒有前驅結點，因此需要一個頭指針指向第一個節點，便於我們對整個鏈表進行操作；這裡的單鏈表的最後一個節點的指針域存放的是頭結點的地址。

單鏈表不能隨意存取，必要的時候我們可以通過已知結點的指針域不斷遍歷從而獲取我們要的結點。

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開發環境下實現

　


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • atitit.userService 用戶系統設計 v6 q413
    atitit.userService 用戶系統設計 v6 q413 1. 新特性1 2. Admin login1 3. 用戶註冊登錄2 3.1. <!-- 會員註冊使用 --> 商家註冊2 3.2. <!-- 會員登錄使用 -->3 3.3. <!-- 會員退出登錄 -->3 3.4. <!-- ...
  • Atitit.獲取某個服務 網路鄰居列表 解決方案
    Atitit.獲取某個服務 網路鄰居列表 解決方案 原理，帶入某個ip掃描從0 255 很快，多線程幾秒就可以出來。 使用CountDownLatch來join線程.. 返回 [{ "ip":"192.168.2.114", "url":"http://@ip@:8080/cms/list_deta ...
  • 關於設計模式的定義，什麼是設計模式？
    我是在前年的時候開始深入接觸C#的，所以，為什麼說是深入呢，大學裡面學過C#，但是，大學的學習你們是懂。剛進公司的三個多月，一直都是在熟悉C#的語法，後來我的頭就讓我做一個計算器的例子（基本上大家都做過這個例子），然後就直接做了，結果可想而知，運行時可以運行，但是只有一個class，頭看了之後，就讓 ...
  • volatile雙重鎖實現單例
    雙重鎖實現單例時遭到質疑，既是：雙重鎖也無法保證單例模式！ 果然，答案又是對方對的，汗顏！ 原因是：指令會重排序，普通的變數僅僅會保證該方法在執行時，所有依賴的賦值結果是正確的，但不會保證執行順序！ 為什麼會重排序：指令重排序是指cpu採用了允許將多條指令不按照程式的順序分開發送各相應電路單元處理， ...
  • StarUML安裝與Win7不相容解決
    最近在學習建模工具（StarUML）發現 其他功能一切正常 但是無法顯示代碼導出功能， 正常界面如下： 我的安裝確沒有導出功能缺少C++，C# ,Java等導出功能 解決辦法： 到StarUML安裝目錄下 找到需要導入語言文件夾， 例如c#對應文件夾staruml-csharp 打開文件夾 找到un ...
  • 裝飾模式
    裝飾模式是為已有功能動態的添加更多功能的一種方式。 當系統需要新功能的時候，是向舊的類中添加新的代碼，而這些新的代碼通常裝飾了原有類的核心職責或者主要行為， 這些新的邏輯增加了主類的複雜度，但是它們僅僅是滿足一些只在某這特定情況下才會執行的特殊行為的需要，且先後執行順序不確定。 這樣，每個要裝飾的功 ...
  • Redis實現關註關係
    最近使用關係型資料庫實現了用戶之間的關註，於是思考換一種思路，使用Redis實現用戶之間的關註關係。 綜合考慮了一下Redis的幾種數據結構後，覺得可以用集合實現一下。 假設“我”的ID是1，“別人”的ID是2。 一、添加關註 添加關註分為兩步：1、將對方id添加到自己的關註列表中；2、將自己的id ...
  • java併發：線程同步機制之計數器&Exechanger
    第一節 CountDownLatch （1）初識CountDownLatch （2）詳述CountDownLatch CountDownLatch是通過一個計數器來實現的，計數器的初始值為線程的數量。每當一個線程完成了自己的任務後，計數器的值就會減1，當計數器值到達0時，它表示所有的線程已經完成了任 ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類