天天看點
傳回

單連結清單(Singly Linked List)

單連結清單(Singly Linked List)

1. 單連結清單的概念

1.1 單連結清單的定義

  • 單連結清單是線性表的鍊式存儲表示。

1.2 單連結清單的結點結構

  • 單連結清單的結點包括兩個部分：資料域和指針域。

    (1)資料域(data)，用于存儲該結點的資料元素，資料元素類型由應用問題決定。

    (2)指針域(link)，用于存放一個指針，該指針指向下一個結點的開始存儲位址。

  • 單連結清單的結點結構示意圖：
    單連結清單(Singly Linked List)

1.3 單連結清單中各結點的連結方式

  • 單連結清單由一系列結點(連結清單中每一個元素稱為結點)組成，結點可以在運作時動态生成。
  • 單連結清單是一種實體存儲單元上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的。
  • 為了表示每個資料元素與其直接後繼資料元素之間的邏輯關系，對資料元素來說，除了存儲其本身的資訊之外，還需存儲一個訓示其直接後繼的資訊(即直接後繼的存儲位置)。由這兩部分資訊組成一個“結點”，表示線性表中一個資料元素。
  • 單連結清單要找一個數，必須要從表頭開始找起，十分麻煩。
  • 單連結清單(帶附加頭結點的)中各結點的連結方式示意圖：
    單連結清單(Singly Linked List)

2. 單連結清單的實作

2.1 靜态連結清單

  • 靜态連結清單：連結清單中所有結點的資料記憶體中的分布都是在編譯時就确定好，程式運作後不能進行改動。
  • 靜态連結清單的實作——例1 
    #include <iostream>

using namespace std;

template <class T>
struct LinkNodeSimple
{
    T data;                  //資料域(data)，用于存儲該結點的資料元素，資料元素類型由應用問題決定。
    LinkNodeSimple<T> *link; //指針域(link)，用于存放一個指針，該指針指向下一個結點的開始存儲位址。
};

int main()
{
    LinkNodeSimple<int> node1, node2, node3, *head;
    node1.data = ; 
    node2.data = ; 
    node3.data = ;
    head = &node1;       //将node1變量結構的開始位址作為一個結點賦給頭指針head
    node1.link = &node2; //将node2變量結構的開始位址作為一個結點賦給node1變量結構的link指針成員
    node2.link = &node3; //将node3變量結構的開始位址作為一個結點賦給node2變量結構的link指針成員
    node3.link = NULL;   //将node3變量結構的link指針成員賦為空，即表示該結點是個尾結點

    //列印連結清單每一個結點的data值
    int count = ;
    LinkNodeSimple<int> *p;
    p = head;//将p指針指向頭結點head
    while(NULL != p)
    {
        cout<<"#"<<count<<" num = "<<p->data<<endl;
        p = p->link;//将p指針指向下一個結點
        count++;
    }

    system("pause");
    return ;
}
  • 靜态連結清單的實作——例2 
    #include <iostream>


#include <string>

using namespace std;

template <class T1, class T2>
struct LinkNode
{
    T1 data1;                  //資料域(data)，用于存儲該結點的資料元素，資料元素類型由應用問題決定。
    T2 data2;                  //資料域(data)，用于存儲該結點的資料元素，資料元素類型由應用問題決定。
    LinkNode<T1, T2> *link; //指針域(link)，用于存放一個指針，該指針指向下一個結點的開始存儲位址。
};

int main()
{
    LinkNode<int, string> node1, node2, node3, *head;
    node1.data1 = ; node1.data2 = "one";
    node2.data1 = ; node2.data2 = "two";
    node3.data1 = ; node3.data2 = "three";
    head = &node1;       //将node1變量結構的開始位址作為一個結點賦給頭指針head
    node1.link = &node2; //将node2變量結構的開始位址作為一個結點賦給node1變量結構的link指針成員
    node2.link = &node3; //将node3變量結構的開始位址作為一個結點賦給node2變量結構的link指針成員
    node3.link = NULL;   //将node3變量結構的link指針成員賦為空，即表示該結點是個尾結點

    //列印連結清單每一個結點的data值
    int count = ;
    LinkNode<int, string> *p;
    p = head;//将p指針指向頭結點head
    while(NULL != p)
    {
        cout<<"#"<<count<<" num = "<<p->data1<<", name = "<<p->data2<<endl;
        p = p->link;//将p指針指向下一個結點
        count++;
    }

    system("pause");
    return ;
}

2.2 動态連結清單

  • 動态連結清單：連結清單結構也可以是動态地配置設定存儲的，即在需要時才開辟結點的存儲空間。

  • 動态連結清單的實作：

    (1)連結清單的結點結構定義：LinkNode.h

    #ifndef LINK_NODE_H_


#define LINK_NODE_H_



#include <iostream>


#include <string>


#include <strstream>


using namespace std;

template <class T>
struct LinkNode         //連結清單結點類的定義
{
    T data;             //資料域
    LinkNode<T> *link;  //指針域——後繼指針
    //僅初始化指針成員的構造函數
    LinkNode(LinkNode<T>* ptr = NULL){ link = ptr; }
    //初始化資料與指針成員的構造函數
    LinkNode(const T& value, LinkNode<T>* ptr = NULL){ data = value; link = ptr; }
};


#endif /* LINK_NODE_H_ */
    (2)單連結清單的類定義及其操作的實作(帶附加頭結點)：LinkedList1.h 
    #ifndef LINKED_LIST1_H_


#define LINKED_LIST1_H_



#include "LinkNode.h"


template <class T>
class LinkedList//帶附加頭結點
{
public:
    LinkedList();                               //構造函數
    LinkedList(const LinkedList<T>& L);         //拷貝構造函數
    ~LinkedList();                              //析構函數
public:
    int Length()const;                          //計算連結清單的結點總數(除附加頭結點)
    LinkNode<T>* Search(const T& x)const;       //搜尋資料值為x的結點并傳回
    LinkNode<T>* Locate(int i)const;            //擷取第i個結點并傳回
    bool GetData(int i, T& x)const;             //擷取第i個結點的資料值儲存至x，并傳回擷取成功與否
    bool SetData(int i, const T& x);            //修改第i個結點的資料值為x
    bool Insert(int i, const T& x);             //在第i個結點後插入資料值為x的新結點
    bool Remove(int i, T& x);                   //删除第i個結點，并将被删結點的資料值儲存至x
    bool IsEmpty()const;                        //判斷表是否為空
    bool IsFull()const;                         //判斷表是否為滿
    void Sort();                                //表排序——冒泡排序
    void InputFront(const T& endTag);           //前插法建立連結清單
    void InputRear(const T& endTag);            //後插法建立連結清單
    void Output()const;                         //輸出所有結點的資料值
    void Reverse();                             //連結清單逆置
    void MakeEmpty();                           //清空連結清單(保留附加頭結點)
    LinkedList<T>& operator=(const LinkedList<T>& L);   //連結清單間指派操作——重載等号運算符
public:
    LinkNode<T>* GetHead()const;                //傳回附加頭結點的位址
    T get_value(string& s_value);               //傳回輸入的結點資料值
public:
    static bool IsNumber(const string& s_num);  //判斷輸入的字元串每個字元是否都是數值0~9
    static T StrToTtype(const string& s_num);   //類型轉換——将string型轉為模闆類型T
private:
    LinkNode<T> *first; //連結清單的頭結點
};

//構造函數
template<class T>
LinkedList<T>::LinkedList()
: first(new LinkNode<T>)
{
    cout << "$ 執行構造函數" << endl;
}

//拷貝構造函數
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)
{
    cout << "$ 執行拷貝構造函數" << endl;
    LinkNode<T> *srcptr = L.GetHead();
    LinkNode<T> *destptr = first = new LinkNode<T>;
    while (NULL != srcptr->link)
    {
        srcptr = srcptr->link;
        destptr->link = new LinkNode<T>(srcptr->data);
        destptr = destptr->link;
    }
}

//析構函數
template<class T>
LinkedList<T>::~LinkedList()
{
    cout << "$ 執行析構函數" << endl;
    MakeEmpty();
}

//計算連結清單的結點總數(除附加頭結點)
template<class T>
int LinkedList<T>::Length()const
{
    int count = ;
    LinkNode<T> *curNode = first->link;
    while (NULL != curNode)
    {
        curNode = curNode->link;
        count++;
    }
    return count;
}

//搜尋資料值為x的結點并傳回
template<class T>
LinkNode<T>* LinkedList<T>::Search(const T& x)const
{
    LinkNode<T> *curNode = first->link;
    while ((NULL != curNode) && (x != curNode->data))
    {
        curNode = curNode->link;
    }
    return curNode;
}

//擷取第i個結點并傳回
template<class T>
LinkNode<T>* LinkedList<T>::Locate(int i)const
{
    if (i < )
    {
        return NULL;
    }
    if ( == i)
    {
        return first;
    }
    int location = ;
    LinkNode<T> *curNode = first->link;
    while ((location < i) && (NULL != curNode))
    {
        curNode = curNode->link;
        location++;
    }
    return curNode;
}

//擷取第i個結點的資料值儲存至x，并傳回擷取成功與否
template<class T>
bool LinkedList<T>::GetData(int i, T& x)const
{
    LinkNode<T> *curNode = Locate(i);
    if ((NULL == curNode) || (first == curNode))
    {
        return false;
    }
    x = curNode->data;
    return true;
}

//修改第i個結點的資料值為x
template<class T>
bool LinkedList<T>::SetData(int i, const T& x)
{
    LinkNode<T> *curNode = Locate(i);
    if ((NULL == curNode) || (first == curNode))
    {
        return false;
    }
    curNode->data = x;
    return true;
}

//在第i個結點後插入資料值為x的新結點
template<class T>
bool LinkedList<T>::Insert(int i, const T& x)
{
    LinkNode<T> *curNode = Locate(i);
    if (NULL == curNode)
    {
        return false;
    }
    LinkNode<T> *newNode = new LinkNode<T>(x);
    if (NULL == newNode)
    {
        cout << "* 存儲配置設定錯誤" << endl;
        return false;
    }
    newNode->link = curNode->link;
    curNode->link = newNode;
    return true;
}

//删除第i個結點，并将被删結點的資料值儲存至x
template<class T>
bool LinkedList<T>::Remove(int i, T& x)
{
    LinkNode<T> *preNode = Locate(i - );
    if (NULL == preNode)
    {
        return false;
    }
    LinkNode<T> *delNode = preNode->link;
    if ((NULL == delNode) || (first == delNode))
    {
        return false;
    }
    preNode->link = delNode->link;
    x = delNode->data;
    delete delNode;
    return true;
}

//判斷表是否為空
template<class T>
bool LinkedList<T>::IsEmpty()const
{
    return (NULL == first->link) ? true : false;
}

//判斷表是否為滿
template<class T>
bool LinkedList<T>::IsFull()const
{
    return false;
}

//表排序——冒泡排序
template<class T>
void LinkedList<T>::Sort()
{
    LinkNode<T> *curNode = first->link;
    while (NULL != curNode)
    {
        LinkNode<T> *nextNode = curNode->link;
        while (NULL != nextNode)
        {
            if (curNode->data < nextNode->data)
            {
                T temp = curNode->data;
                curNode->data = nextNode->data;
                nextNode->data = temp;
            }
            nextNode = nextNode->link;
        }
        curNode = curNode->link;
    }
}

//前插法建立連結清單
//endTag是約定的輸入序列結束的标志。如果輸入序列是正整數，endTag可以是0或負數；
//如果輸入序列是字元，endTag可以是字元集中不會出現的字元，如“\0”。
template<class T>
void LinkedList<T>::InputFront(const T& endTag)
{
    MakeEmpty();
    string s_value;
    T value = get_value(s_value);
    while (endTag != value)
    {
        LinkNode<T> *newNode = new LinkNode<T>(value);  //建立新結點
        if (NULL == newNode)
        {
            cout << "* 存儲配置設定錯誤" << endl;
            break;
        }
        newNode->link = first->link;                    //新結點中指針域的指針指向連結清單的第一個結點
        first->link = newNode;                          //附加頭結點中指針域的指針指向新結點
        value = get_value(s_value);
    }
}

//後插法建立連結清單
//endTag是約定的輸入序列結束的标志。如果輸入序列是正整數，endTag可以是0或負數；
//如果輸入序列是字元，endTag可以是字元集中不會出現的字元，如“\0”。
template<class T>
void LinkedList<T>::InputRear(const T& endTag)
{
    MakeEmpty();
    LinkNode<T> *lastNode = first;                      //設定連結清單的最後一個結點為附加頭結點
    string s_value;
    T value = get_value(s_value);
    while (endTag != value)
    {
        LinkNode<T> *newNode = new LinkNode<T>(value);  //建立新結點
        if (NULL == newNode)
        {
            cout << "* 存儲配置設定錯誤" << endl;
            break;
        }
        lastNode->link = newNode;                       //最後一個結點中指針域的指針指向新結點
        lastNode = newNode;                             //設定最後一個結點為新結點
        value = get_value(s_value);
    }
}

//輸出所有結點的資料值
template<class T>
void LinkedList<T>::Output()const
{
    LinkNode<T> *curNode = first->link;
    while (NULL != curNode)
    {
        cout << "curNode->data = " << curNode->data << endl;
        curNode = curNode->link;
    }
}

//連結清單逆置
template<class T>
void LinkedList<T>::Reverse()
{
    LinkNode<T> *prevNode = NULL;
    LinkNode<T> *curNode = first->link;
    LinkNode<T> *nextNode = NULL;
    while (NULL != curNode) 
    {
        nextNode = curNode->link;
        curNode->link = prevNode;
        prevNode = curNode;
        curNode = nextNode;
    }
    first->link = prevNode;
}

//清空連結清單(保留附加頭結點)
template<class T>
void LinkedList<T>::MakeEmpty()
{
    LinkNode<T> *curNode = NULL;
    while (NULL != first->link)         //當連結清單不為空時，删去連結清單中所有結點
    {
        curNode = first->link;          //儲存被删結點
        first->link = curNode->link;    //将連結清單附加頭結點中指針域的指針指向被删結點的下一個結點
        delete curNode;                 //從連結清單上摘下被删結點
    }
}

//連結清單間指派操作——重載等号運算符
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)
{
    cout << "$ 執行指派操作函數" << endl;
    LinkNode<T> *srcptr = L.GetHead();
    LinkNode<T> *destptr = first = new LinkNode<T>;
    while (NULL != srcptr->link)
    {
        srcptr = srcptr->link;
        destptr->link = new LinkNode<T>(srcptr->data);
        destptr = destptr->link;
    }           
    return *this;
}

//傳回附加頭結點的位址
template<class T>
LinkNode<T>* LinkedList<T>::GetHead()const
{
    return first;
}

//傳回輸入的結點資料值
template <class T>
T LinkedList<T>::get_value(string& s_value)
{
    cout << "newNode->data = ";
    cin >> s_value;
    return StrToTtype(s_value);
}

//判斷輸入的字元串每個字元是否都是數值0~9
template <class T>
bool LinkedList<T>::IsNumber(const string& s_num)
{
    for (size_t i = ; i < s_num.size(); i++)
    {
        if ((s_num[i] < '0') || (s_num[i] > '9'))
        {
            return false;
        }
    }
    return true;
}

//類型轉換——将string型轉為模闆類型T
template <class T>
T LinkedList<T>::StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}


#endif /* LINKED_LIST1_H_ */
    (3)單連結清單的類定義及其操作的實作(不帶附加頭結點)：LinkedList2.h 
    #ifndef LINKED_LIST2_H_


#define LINKED_LIST2_H_



#include "LinkNode.h"


template <class T>
class LinkedList//不帶附加頭結點
{
public:
    LinkedList();                               //構造函數
    LinkedList(const LinkedList<T>& L);         //拷貝構造函數
    ~LinkedList();                              //析構函數
public:
    int Length()const;                          //計算連結清單的結點總數
    LinkNode<T>* Search(const T& x)const;       //搜尋資料值為x的結點并傳回
    LinkNode<T>* Locate(int i)const;            //擷取第i個結點并傳回
    bool GetData(int i, T& x)const;             //擷取第i個結點的資料值儲存至x，并傳回擷取成功與否
    bool SetData(int i, const T& x);            //修改第i個結點的資料值為x
    bool Insert(int i, const T& x);             //在第i個結點後插入資料值為x的新結點
    bool Remove(int i, T& x);                   //删除第i個結點，并将被删結點的資料值儲存至x
    bool IsEmpty()const;                        //判斷表是否為空
    bool IsFull()const;                         //判斷表是否為滿
    void Sort();                                //表排序——冒泡排序
    void InputFront(const T& endTag);           //前插法建立連結清單
    void InputRear(const T& endTag);            //後插法建立連結清單
    void Output()const;                         //輸出所有結點的資料值
    void Reverse();                             //連結清單逆置
    void MakeEmpty();                           //清空連結清單
    LinkedList<T>& operator=(const LinkedList<T>& L);   //連結清單間指派操作——重載等号運算符
public:
    LinkNode<T>* GetHead()const;                //傳回頭結點的位址
    T get_value(string& s_value);               //傳回輸入的結點資料值
public:
    static bool IsNumber(const string& s_num);  //判斷輸入的字元串每個字元是否都是數值0~9
    static T StrToTtype(const string& s_num);   //類型轉換——将string型轉為模闆類型T
private:
    LinkNode<T> *first; //連結清單的頭結點
};

//構造函數
template<class T>
LinkedList<T>::LinkedList()
: first(NULL)
{
    cout << "$ 執行構造函數" << endl;
}

//拷貝構造函數
template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)
{
    cout << "$ 執行拷貝構造函數" << endl;
    LinkNode<T> *srcptr = L.GetHead();
    LinkNode<T> *destptr = first = NULL;
    if (NULL != srcptr)
    {
        destptr = first = new LinkNode<T>(srcptr->data);
        while (NULL != srcptr->link)
        {
            srcptr = srcptr->link;
            destptr->link = new LinkNode<T>(srcptr->data);
            destptr = destptr->link;
        }
    }
}

//析構函數
template<class T>
LinkedList<T>::~LinkedList()
{
    cout << "$ 執行析構函數" << endl;
    MakeEmpty();
}

//計算連結清單的結點總數
template<class T>
int LinkedList<T>::Length()const
{
    int count = ;
    LinkNode<T> *curNode = first;
    while (NULL != curNode)
    {
        curNode = curNode->link;
        count++;
    }
    return count;
}

//搜尋資料值為x的結點并傳回
template<class T>
LinkNode<T>* LinkedList<T>::Search(const T& x)const
{
    LinkNode<T> *curNode = first;
    while ((NULL != curNode) && (x != curNode->data))
    {
        curNode = curNode->link;
    }
    return curNode;
}

//擷取第i個結點并傳回
template<class T>
LinkNode<T>* LinkedList<T>::Locate(int i)const
{
    if (i <= )
    {
        return NULL;
    }
    int location = ;
    LinkNode<T> *curNode = first;
    while ((location < i) && (NULL != curNode))
    {
        curNode = curNode->link;
        location++;
    }
    return curNode;
}

//擷取第i個結點的資料值儲存至x，并傳回擷取成功與否
template<class T>
bool LinkedList<T>::GetData(int i, T& x)const
{
    LinkNode<T> *curNode = Locate(i);
    if (NULL == curNode)
    {
        return false;
    }
    x = curNode->data;
    return true;
}

//修改第i個結點的資料值為x
template<class T>
bool LinkedList<T>::SetData(int i, const T& x)
{
    LinkNode<T> *curNode = Locate(i);
    if (NULL == curNode) 
    {
        return false;
    }
    curNode->data = x;
    return true;
}

//在第i個結點後插入資料值為x的新結點
template<class T>
bool LinkedList<T>::Insert(int i, const T& x)
{
    LinkNode<T> *newNode = new LinkNode<T>(x);
    if (NULL == newNode)
    {
        cout << "* 存儲配置設定錯誤" << endl;
        return false;
    }
    if ( == i)
    {
        newNode->link = first;
        first = newNode;
        return true;
    }
    LinkNode<T> *curNode = Locate(i);
    if (NULL != curNode)
    {
        newNode->link = curNode->link;
        curNode->link = newNode;
        return true;
    }
    delete newNode;
    return false;
}

//删除第i個結點，并将被删結點的資料值儲存至x
template<class T>
bool LinkedList<T>::Remove(int i, T& x)
{
    if (NULL == first)
    {
        return false;
    }
    LinkNode<T> *delNode = NULL;
    if ( == i)
    {   
        delNode = first;
        first = delNode->link;
    }
    else
    {
        LinkNode<T> *preNode = Locate(i - );
        if ((NULL == preNode) || (NULL == preNode->link))
        {
            return false;
        }
        delNode = preNode->link;
        preNode->link = delNode->link;
    }
    x = delNode->data;
    delete delNode;
    return true;
}

//判斷表是否為空
template<class T>
bool LinkedList<T>::IsEmpty()const
{
    return (NULL == first) ? true : false;
}

//判斷表是否為滿
template<class T>
bool LinkedList<T>::IsFull()const
{
    return false;
}

//表排序——冒泡排序
template<class T>
void LinkedList<T>::Sort()
{
    LinkNode<T> *curNode = first;
    while (NULL != curNode)
    {
        LinkNode<T> *nextNode = curNode->link;
        while (NULL != nextNode)
        {
            if (curNode->data < nextNode->data)
            {
                T temp = curNode->data;
                curNode->data = nextNode->data;
                nextNode->data = temp;
            }
            nextNode = nextNode->link;
        }
        curNode = curNode->link;
    }
}

//前插法建立連結清單
//endTag是約定的輸入序列結束的标志。如果輸入序列是正整數，endTag可以是0或負數；
//如果輸入序列是字元，endTag可以是字元集中不會出現的字元，如“\0”。
template<class T>
void LinkedList<T>::InputFront(const T& endTag)
{
    MakeEmpty();
    string s_value;
    T value = get_value(s_value);
    while (endTag != value)
    {
        LinkNode<T> *newNode = new LinkNode<T>(value);  //建立新結點
        if (NULL == newNode)
        {
            cout << "* 存儲配置設定錯誤" << endl;
            break;
        }
        newNode->link = first;                          //新結點中指針域的指針指向連結清單的第一個結點
        first = newNode;                                //新結點成為頭結點
        value = get_value(s_value);
    }
}

//後插法建立連結清單
//endTag是約定的輸入序列結束的标志。如果輸入序列是正整數，endTag可以是0或負數；
//如果輸入序列是字元，endTag可以是字元集中不會出現的字元，如“\0”。
template<class T>
void LinkedList<T>::InputRear(const T& endTag)
{
    MakeEmpty();
    LinkNode<T> *lastNode = first;                      //設定連結清單的最後一個結點為頭結點;
    string s_value;
    T value = get_value(s_value);
    while (endTag != value)
    {
        LinkNode<T> *newNode = new LinkNode<T>(value);  //建立新結點
        if (NULL == newNode)
        {
            cout << "* 存儲配置設定錯誤" << endl;
            break;
        }
        if(NULL == lastNode)
        {
            first = newNode;                            //當連結清單為空時，新結點成為頭結點
        }
        else
        {
            lastNode->link = newNode;                   //連結清單的最後一個結點中指針域的指針指向新結點
        }
        lastNode = newNode;                             //新結點成為連結清單的最後一個結點
        value = get_value(s_value);
    }
}

//輸出所有結點的資料值
template<class T>
void LinkedList<T>::Output()const
{
    LinkNode<T> *curNode = first;
    while (NULL != curNode)
    {
        cout << "curNode->data = " << curNode->data << endl;
        curNode = curNode->link;
    }
}

//連結清單逆置
template<class T>
void LinkedList<T>::Reverse()
{
    LinkNode<T> *prevNode = NULL;
    LinkNode<T> *curNode = first;
    LinkNode<T> *nextNode = NULL;
    while (NULL != curNode) 
    {
        nextNode = curNode->link;
        curNode->link = prevNode;
        prevNode = curNode;
        curNode = nextNode;
    }
    first = prevNode;
}

//清空連結清單
template<class T>
void LinkedList<T>::MakeEmpty()
{
    LinkNode<T> *curNode = NULL;
    while (NULL != first)               //當連結清單不為空時，删去連結清單中所有結點
    {
        curNode = first;                //儲存被删結點
        first = curNode->link;          //被删結點的下一個結點成為頭結點
        delete curNode;                 //從連結清單上摘下被删結點
    }
}

//連結清單間指派操作——重載等号運算符
template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)
{
    cout << "$ 執行指派操作函數" << endl;
    LinkNode<T> *srcptr = L.GetHead();
    LinkNode<T> *destptr = first = NULL;
    if (NULL != srcptr)
    {
        destptr = first = new LinkNode<T>(srcptr->data);
        while (NULL != srcptr->link)
        {
            srcptr = srcptr->link;
            destptr->link = new LinkNode<T>(srcptr->data);
            destptr = destptr->link;
        }
    }
    return *this;
}

//傳回頭結點的位址
template<class T>
LinkNode<T>* LinkedList<T>::GetHead()const
{
    return first;
}

//傳回輸入的結點資料值
template <class T>
T LinkedList<T>::get_value(string& s_value)
{
    cout << "newNode->data = ";
    cin >> s_value;
    return StrToTtype(s_value);
}

//判斷輸入的字元串每個字元是否都是數值0~9
template <class T>
bool LinkedList<T>::IsNumber(const string& s_num)
{
    for (size_t i = ; i < s_num.size(); i++)
    {
        if ((s_num[i] < '0') || (s_num[i] > '9'))
        {
            return false;
        }
    }
    return true;
}

//類型轉換——将string型轉為模闆類型T
template <class T>
T LinkedList<T>::StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}


#endif /* LINKED_LIST2_H_ */
    (4)主函數(main函數)的實作：main.cpp 
    #include "LinkedList1.h"    //帶附加頭結點

//#include "LinkedList2.h"  //不帶附加頭結點


#define EXIT 0              //退出


#define CONSTRUCT_COPY 1    //拷貝構造連結清單


#define LENGTH 2            //計算連結清單的結點總數


#define SEARCH 3            //搜尋資料值為x的結點并傳回


#define LOCATE 4            //擷取第i個結點并傳回


#define GETDATA 5           //擷取第i個結點的資料值儲存至x，并傳回擷取成功與否


#define SETDATA 6           //修改第i個結點的資料值為x


#define INSERT 7            //在第i個結點後插入資料值為x的新結點


#define REMOVE 8            //删除第i個結點，并将被删結點的資料值儲存至x


#define ISEMPTY 9           //判斷表是否為空


#define ISFULL 10           //判斷表是否為滿


#define SORT 11             //表排序——冒泡排序


#define INPUTFRONT 12       //前插法建立連結清單


#define INPUTREAR 13        //後插法建立連結清單


#define OUTPUT 14           //輸出所有結點的資料值


#define REVERSE 15          //連結清單逆置


#define MAKEEMPTY 16        //清空連結清單


#define OPERATOR_COPY 17    //連結清單間指派操作——重載等号運算符


#define GETHEAD 18          //傳回頭結點的位址


void print_description()
{
    cout << "------------------------------>單連結清單<------------------------------" << endl;
    cout << "功能選項說明：" << endl;
    cout << "#0： 退出" << endl;
    cout << "#1： 拷貝構造連結清單" << endl;
    cout << "#2： 計算連結清單的結點總數" << endl;
    cout << "#3： 搜尋資料值為x的結點并傳回" << endl;
    cout << "#4： 擷取第i個結點并傳回" << endl;
    cout << "#5： 擷取第i個結點的資料值儲存至x，并傳回擷取成功與否" << endl;
    cout << "#6： 修改第i個結點的資料值為x" << endl;
    cout << "#7： 在第i個結點後插入資料值為x的新結點" << endl;
    cout << "#8： 删除第i個結點，并将被删結點的資料值儲存至x" << endl;
    cout << "#9： 判斷表是否為空" << endl;
    cout << "#10：判斷表是否為滿" << endl;
    cout << "#11：表排序——冒泡排序" << endl;
    cout << "#12：前插法建立連結清單" << endl;
    cout << "#13：後插法建立連結清單" << endl;
    cout << "#14：輸出所有結點的資料值" << endl;
    cout << "#15：連結清單逆置" << endl;
    cout << "#16：清空連結清單" << endl;
    cout << "#17：連結清單間指派操作——重載等号運算符" << endl;
    cout << "#18：傳回頭結點的位址" << endl;
    cout << "--------------------------------------------------------------------" << endl;
}

//輸入結點編号
template <class T>
int get_item()
{
    cout << "> 請輸入結點編号，item = ";
    string s_item;
    cin >> s_item;
    while (false == LinkedList<T>::IsNumber(s_item))
    {
        cout << "* 輸入有誤，請重新輸入：";
        cin >> s_item;
    }
    return atoi(s_item.c_str());
}

//輸入資料值
template <class T>
T get_data()
{
    cout << "> 請輸入資料值，data = ";
    string s_data;
    cin >> s_data;
    return LinkedList<T>::StrToTtype(s_data);
}

//輸入結束标志位
template <class T>
T get_endtag()
{
    cout << "請輸入結束标志值，endTag = ";
    string s_endTag;
    cin >> s_endTag;
    return LinkedList<T>::StrToTtype(s_endTag);
}

//構造單連結清單
template <class T>
LinkedList<T>* construct_linkedlist()
{
    cout << "\n==> 建立單連結清單" << endl;
    LinkedList<T> *linkedList = new LinkedList<T>;
    return linkedList;
}

//析構單連結清單
template <class T>
void destory_linkedlist(LinkedList<T>* linkedList)
{
    cout << "\n==> 釋放單連結清單在堆中申請的空間，并将指向該空間的指針變量置為空" << endl;
    delete linkedList;
    linkedList = NULL;
}

//拷貝構造連結清單
template <class T>
void construct_copy(LinkedList<T>* linkedList)
{
    cout << "$ 執行拷貝構造連結清單函數" << endl;
    LinkedList<T> cpy_linkedlist = *linkedList;
    cpy_linkedlist.Output();
}

//計算連結清單的結點總數
template <class T>
void length(LinkedList<T>* linkedList)
{
    cout << "$ 執行計算連結清單的結點總數函數，Length = " << linkedList->Length() << endl;
}

//搜尋資料值為x的結點并傳回
template <class T>
void search(LinkedList<T>* linkedList)
{
    cout << "$ 執行搜尋資料值為x的結點并傳回函數" << endl;
    T data = get_data<T>();
    LinkNode<T> *node = linkedList->Search(data);
    if (NULL == node)
    {
        cout << "* 搜尋失敗" << endl;
        return;
    }
    cout << "* 搜尋成功，data = " << node->data << endl;
}   

//擷取第i個結點并傳回
template <class T>
void locate(LinkedList<T>* linkedList)
{
    cout << "$ 執行擷取第i個結點并傳回函數" << endl;
    int n_item = get_item<T>();
    LinkNode<T> *node = linkedList->Locate(n_item);
    if ((NULL == node) || (linkedList->GetHead() == node))
    {
        cout << "* 擷取失敗" << endl;
        return;
    }
    cout << "* 擷取成功，item = " << n_item << "，data = " << node->data << endl;
}

//擷取第i個結點的資料值儲存至x，并傳回擷取成功與否
template <class T>
void getdata(LinkedList<T>* linkedList)
{
    cout << "$ 執行擷取第i個結點的資料值儲存至x并傳回擷取成功與否函數" << endl;
    T data;
    int n_item = get_item<T>();
    if (false == linkedList->GetData(n_item, data))
    {
        cout << "* 擷取失敗" << endl;
        return;
    }
    cout << "* 擷取成功，item = " << n_item << "，data = " << data << endl;
}

//修改第i個結點的資料值為x
template <class T>
void setdata(LinkedList<T>* linkedList)
{
    cout << "$ 執行修改第i個結點的資料值為x函數" << endl;
    int n_item = get_item<T>();
    T data = get_data<T>();
    if (false == linkedList->SetData(n_item, data))
    {
        cout << "* 修改失敗" << endl;
        return;
    }
    cout << "* 修改成功，item = " << n_item << "，data = " << data << endl;
}

//在第i個結點後插入資料值為x的新結點
template <class T>
void insert(LinkedList<T>* linkedList)
{
    cout << "$ 執行在第i個結點後插入資料值為x的新結點函數" << endl;
    int n_item = get_item<T>();
    T data = get_data<T>();
    if (false == linkedList->Insert(n_item, data))
    {
        cout << "* 插入失敗" << endl;
        return;
    }
    cout << "* 插入成功，item+1 = " << n_item+ << "，data = " << data << endl;
}

//删除第i個結點，并将被删結點的資料值儲存至x
template <class T>
void remove(LinkedList<T>* linkedList)
{
    cout << "$ 執行删除第i個結點并将被删結點的資料值儲存至x函數" << endl;
    T data;
    int n_item = get_item<T>();
    if (false == linkedList->Remove(n_item, data))
    {
        cout << "* 删除失敗" << endl;
        return;
    }
    cout << "* 删除成功，item = " << n_item << "，data = " << data << endl;
}

//判斷表是否為空
template <class T>
void isempty(LinkedList<T>* linkedList)
{
    cout << "$ 執行判斷表是否為空函數，IsEmpty = " << linkedList->IsEmpty() << endl;
}

//判斷表是否為滿
template <class T>
void isfull(LinkedList<T>* linkedList)
{
    cout << "$ 執行判斷表是否為滿函數，IsFull = " << linkedList->IsFull() << endl;
}

//表排序——冒泡排序
template <class T>
void sort(LinkedList<T>* linkedList)
{
    cout << "$ 執行表排序——冒泡排序函數" << endl;
    linkedList->Sort();
}

//前插法建立連結清單
template <class T>
void inputfront(LinkedList<T>* linkedList)
{
    cout << "$ 執行前插法建立連結清單函數" << endl;
    T endTag = get_endtag<T>();
    linkedList->InputFront(endTag);
}

//後插法建立連結清單
template <class T>
void inputrear(LinkedList<T>* linkedList)
{
    cout << "$ 執行後插法建立連結清單函數" << endl;
    T endTag = get_endtag<T>();
    linkedList->InputRear(endTag);
}

//輸出所有結點的資料值
template <class T>
void output(LinkedList<T>* linkedList)
{
    cout << "$ 執行輸出所有結點的資料值函數" << endl; 
    linkedList->Output();
}

//連結清單逆置
template <class T>
void reverse(LinkedList<T>* linkedList)
{
    cout << "$ 執行連結清單逆置函數" << endl;
    linkedList->Reverse();
}

//清空連結清單
template <class T>
void make_empty(LinkedList<T>* linkedList)
{
    cout << "$ 執行清空連結清單函數" << endl; 
    linkedList->MakeEmpty();
}

//連結清單間指派操作——重載等号運算符
template <class T>
void operator_copy(LinkedList<T>* linkedList)
{
    cout << "$ 執行連結清單間指派操作——重載等号運算符函數" << endl; 
    LinkedList<T> cpy_linkedlist;
    cpy_linkedlist = *linkedList;//或cpy_linkedlist.operator=(*linkedList);
    cpy_linkedlist.Output();
}

//傳回頭結點的位址
template <class T>
void gethead(LinkedList<T>* linkedList)
{       
    LinkNode<T> *head = linkedList->GetHead();
    cout << "$ 執行傳回頭結點的位址函數，&first = " << &head << endl;
}

//單連結清單操作選擇
template <class T>
void select_operation(LinkedList<T>* linkedList)
{
    if (NULL == linkedList)
    {
        cout << "* 沒有構造單連結清單，請先構造單連結清單。" << endl;
        return;
    }

    string s_operation;
    while (s_operation != "0")
    {
        cout << "\n==> 請輸入功能選項編号(按\"0\"退出程式)：";
        cin >> s_operation;
        while (false == LinkedList<T>::IsNumber(s_operation))
        {
            cout << "* 輸入有誤，請重新輸入：";
            cin >> s_operation;
        }
        int n_operation = atoi(s_operation.c_str());
        switch (n_operation)
        {
            case EXIT://退出
            {
                cout << "$ 退出程式" << endl;
                break;
            }
            case CONSTRUCT_COPY://拷貝構造連結清單
            {
                construct_copy(linkedList);
                break;
            }
            case LENGTH://計算連結清單的結點總數
            {
                length(linkedList);
                break;
            }
            case SEARCH://搜尋資料值為x的結點并傳回
            {
                search(linkedList);
                break;
            }
            case LOCATE://擷取第i個結點并傳回
            {
                locate(linkedList);
                break;
            }
            case GETDATA://擷取第i個結點的資料值儲存至x，并傳回擷取成功與否
            {
                getdata(linkedList);
                break;
            }
            case SETDATA://修改第i個結點的資料值為x
            {
                setdata(linkedList);
                break;
            }
            case INSERT://在第i個結點後插入資料值為x的新結點
            {
                insert(linkedList);
                break;
            }
            case REMOVE://删除第i個結點，并将被删結點的資料值儲存至x
            {
                remove(linkedList);
                break;
            }
            case ISEMPTY://判斷表是否為空
            {
                isempty(linkedList);
                break;
            }
            case ISFULL://判斷表是否為滿
            {
                isfull(linkedList);
                break;
            }
            case SORT://表排序——冒泡排序
            {
                sort(linkedList);
                break;
            }
            case INPUTFRONT://前插法建立連結清單
            {
                inputfront(linkedList);
                break;
            }
            case INPUTREAR://後插法建立連結清單
            {
                inputrear(linkedList);
                break;
            }
            case OUTPUT://輸出所有結點的資料值
            {
                output(linkedList);
                break;
            }
            case REVERSE://連結清單逆置
            {
                reverse(linkedList);
                break;
            }
            case MAKEEMPTY://清空連結清單
            {
                make_empty(linkedList);
                break;
            }
            case OPERATOR_COPY://連結清單間指派操作——重載等号運算符
            {
                operator_copy(linkedList);
                break;
            }
            case GETHEAD://傳回頭結點的位址
            {
                gethead(linkedList);
                break;
            }
            default:
            {
                cout << "* 請輸入正确的功能選項編号" << endl;
                break;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    print_description();
    LinkedList<int> *linkedList = construct_linkedlist<int>();
    select_operation(linkedList);
    destory_linkedlist(linkedList);
    system("pause");
    return ;
}

3. 單連結清單的優缺點

3.1 優點

  • 沒有空間限制，存儲元素的個數無上限，基本隻與記憶體空間大小有關。
  • 插入和删除元素速率高。

3.2 缺點

  • 占用額外的空間以存儲指針(浪費空間)。
  • 随機存取元素速率低。
  • 單連結清單要找一個數，必須要從表頭開始找起，十分麻煩。

3.3 單連結清單的适用情況

  • 适用于需要進行大量增加和删除元素操作而對通路元素無要求的，及預先無法确定表的大小的程式。

參考文獻：

[1]《資料結構(用面向對象方法與C++語言描述)(第2版)》殷人昆——第二章

[2]《C/C++常用算法手冊》秦姣華、向旭宇——第二章

[3] 百度搜尋關鍵字：單連結清單的優缺點

C++資料結構 資料結構 單連結清單 靜态連結清單 動态連結清單 單連結清單的優缺點
上一篇: windbg 常用指令~*
下一篇: 一起玩轉算法：保證圖可完全周遊

繼續閱讀