單鏈表（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
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類