帶頭結(jié)點(diǎn)的鏈表

1、鏈表和順序表

鏈表是很常見的數(shù)據(jù)結(jié)構(gòu)，鏈表總是會(huì)和線性順序表來(lái)比較。

1.1、順序表

  • 具有隨機(jī)存儲(chǔ)的特性，給定位置就能通過(guò)計(jì)算找到數(shù)據(jù)所在位置，因?yàn)樵诜峙浯鎯?chǔ)空間的時(shí)候，是連續(xù)分配的，所以讀取很快。
  • 因?yàn)槭孪纫_辟一塊空間，過(guò)大會(huì)造成空間浪費(fèi)，過(guò)小會(huì)溢出，所以在存儲(chǔ)位置長(zhǎng)度的數(shù)據(jù)時(shí)，表現(xiàn)不是很好。
  • 在插入和刪除元素時(shí)，涉及到元素的移動(dòng)，最壞情況下要移動(dòng)表里所有元素，效率不高。

1.2、鏈表

  • 通過(guò)指向下一結(jié)點(diǎn)的指針，來(lái)找到下一個(gè)元素，每個(gè)節(jié)點(diǎn)要存儲(chǔ)數(shù)據(jù)信息和指向下一結(jié)點(diǎn)的指針，從空間利用率上來(lái)說(shuō)，不如順序表。
  • 不具有隨機(jī)存儲(chǔ)的特點(diǎn)，例如想找到下標(biāo)為5的元素，順序表可以直接訪問(wèn)，而鏈表必須逐個(gè)調(diào)整，最后才能找到這個(gè)元素。
  • 插入、刪除效率高，相較于順序表的移動(dòng)元素，鏈表只需調(diào)整指針指向的元素。

1.3、比較

  • 對(duì)于隨機(jī)讀取次數(shù)多，且對(duì)插入、刪除需求小的時(shí)候，可以用順序表來(lái)存儲(chǔ)，更合理。
  • 對(duì)于插入、刪除需求頻繁的時(shí)候，可以用鏈表來(lái)存儲(chǔ)，更合理。
  • 如果內(nèi)存中碎片多，此時(shí)可能無(wú)法開辟一塊連續(xù)的大空間，從而無(wú)法創(chuàng)建順序表，此時(shí)可以使用鏈表。

2、單鏈表

2.1、兩種類型

有許多種鏈表，單鏈表就是很常見的一種鏈表類型。即只能從前向后遍歷，無(wú)法從后向前遍歷。其中單鏈表又有帶頭和不帶頭之分，聽起來(lái)怎么有點(diǎn)嚇人……

  • 不帶頭鏈表中第一個(gè)結(jié)點(diǎn)就是我們所存儲(chǔ)的元素的結(jié)點(diǎn)。
  • 帶頭鏈表中第一個(gè)結(jié)點(diǎn)存儲(chǔ)的元素為空，這個(gè)就是所謂的頭，第二個(gè)結(jié)點(diǎn)才是我們存儲(chǔ)的元素。

2.2、比較

  • 不帶頭鏈表在第一個(gè)結(jié)點(diǎn)之前插入和刪除第一個(gè)結(jié)點(diǎn)的時(shí)候，會(huì)出現(xiàn)特殊情況，使得操作不方便。
  • 帶頭鏈表，因?yàn)榈谝粋€(gè)有效的結(jié)點(diǎn)實(shí)際上是第二結(jié)點(diǎn)，所以避免了上述的情況。

3、基于C++的代碼

3.1、給出類的基本構(gòu)造

#include <iostream>
using namespace std;
template<class T>
class Node
{
private:
    Node* link;
    T element;
public:
    Node* getLink(){return link;}
    T getElement(){return element;}
    void setElement(T x){element = x;}
    void setLink(Node<T>* x){link = x;}
};
template<class T>
class SingleList
{
public:
    SingleList() { first = new Node<T>; first->setLink(NULL); length = 0; };
    ~SingleList();
    bool isEmpty() const;
    int Length() const;
    bool Find(int i, T& x)const;
    Node<T>* Find(int i)const;
    int Search(T x)const;
    bool Insert(int i, T x);
    bool Delete(int i);
    bool Update(int i, T x);
    void Clear();
    void Output(ostream& out)const;

private:
    Node<T>*first;
    int length;
};
  • Node類是結(jié)點(diǎn)類
  • isEmpty返回bool類型，判斷表是否為空
  • Length返回表長(zhǎng)度
  • Find(int i, T& x)，找到第i個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)內(nèi)的值放在x中保存
  • Find(int i) 找到第i個(gè)結(jié)點(diǎn)并返回
  • Search找到指定元素，并返回其位置
  • Insert向指定位置插入元素
  • Delete刪除指定位置元素
  • Update更新指定位置元素
  • Clear清除表
  • Output輸出表中元素

3.2、類的實(shí)現(xiàn)

template<class T>
void SingleList<T>::Output(ostream& out) const
{
        if (length==0)
    {
        out<<"The SingeList is null";
        return;
    }
    Node<T>*p = first->getLink();
    while (p != NULL)
    {
        out << p->getElement() << " ";
        p = p->getLink();
    }
    out << endl;
}

template<class T>
void SingleList<T>::Clear()
{
    Node<T>*p = first->getLink();
    while (p != NULL)
    {
        Node<T>* q = p;
        p = p->getLink();
        delete q;
    }
    length = 0;
}

template<class T>
bool SingleList<T>::Update(int i, T x)
{
    Node<T>* p = Find(i);
    if (p == NULL) return false;
    p->setElement(x);
    return true;
}

template<class T>
bool SingleList<T>::Delete(int i)
{
    Node<T>*p;
    if (i == 0)
        p = first;
    else
    {
        p = Find(i - 1);
        if (p == NULL)return false;
    }
    //找到第i-1個(gè)結(jié)點(diǎn)
    Node<T>*q = p->getLink();//q是第i個(gè)結(jié)點(diǎn)
    p->setLink(q->getLink());//第i-1個(gè)結(jié)點(diǎn)指向第i+1個(gè)結(jié)點(diǎn)
    delete q;//刪除第i個(gè)結(jié)點(diǎn)
    length--;//減小長(zhǎng)度
    return true;

}

template<class T>
bool SingleList<T>::Insert(int i, T x)
{
    Node<T>*p;
    if (i==0)
        p = first;
    else
    {
        p = Find(i - 1);
        if (p == NULL)return false;
    }
    //以上是找到第i-1個(gè)結(jié)點(diǎn)，越界判斷在Find函數(shù)里
    Node<T>* newNode = new Node<T>;//生成新插入的結(jié)點(diǎn)
    newNode->setElement(x);//賦值
    newNode->setLink(p->getLink());//新結(jié)點(diǎn)指向原來(lái)的第i個(gè)結(jié)點(diǎn)
    p->setLink(newNode);//第i-1個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
    length++;//表長(zhǎng)度增加
    return true;
}

template<class T>
int SingleList<T>::Search(T x) const
{
    if (length == 0)//如果表里沒有元素，則直接返回
    {
        cout << "The SingleList is null!";
        return -1;
    }
    Node<T>*p = first->getLink();
    int position = 0;//位置信息
    while (p != NULL)
    {
        if (p->getElement() == x) return position;//找到元素，返回位置
        p = p->getLink();
        position++;
    }
    cout << "Don't find the element!";
    return -1;
}
template<class T>
Node<T>* SingleList<T>::Find(int i) const
{
    if (i > length - 1 || i < 0)//越界檢查
    {
        cout << "Out of Bounds!";
        return NULL;
    }
    Node<T>* p = first->getLink();//從第一個(gè)有效元素開始查找
    for (int j = 0; j < i; j++)
    {
        p = p->getLink();//逐個(gè)調(diào)整，知道指向第i個(gè)元素
    }
    return p;
}
template<class T>
bool SingleList<T>::Find(int i, T& x) const
{
    Node<T>* p = Find(i);
    if (p == NULL) return false;
    x = p->getElement();
    return true;
}

template<class T>
int SingleList<T>::Length() const
{
    return length;
}

template<class T>
bool SingleList<T>::isEmpty() const
{
    if (length == 0) return true;
    else return false;
}

template<class T>
SingleList<T>::~SingleList()
{
    Node<T>*p;
    while (first != NULL)
    {
        p = first->getLink();//找到當(dāng)前刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        delete first;//刪除當(dāng)前結(jié)點(diǎn)
        first = p;
    }
}

除了刪除和插入以外，其他的方法實(shí)現(xiàn)起來(lái)都不困難，唯一有些復(fù)雜的就是插入和刪除，要想好先后執(zhí)行的操作，從老師的PPT里找到的圖片


插入和刪除.png
  • 插入時(shí)，先將新結(jié)點(diǎn)指向原來(lái)的第i個(gè)結(jié)點(diǎn)，再讓第i-1個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)。
  • 刪除時(shí)，找到第i-1個(gè)結(jié)點(diǎn)和第i個(gè)結(jié)點(diǎn)，讓第i-1個(gè)結(jié)點(diǎn)指向第i+1個(gè)結(jié)點(diǎn)，刪除第i個(gè)結(jié)點(diǎn)。

至此整個(gè)基本的帶頭單鏈表就完成了，讓我們來(lái)測(cè)試一下吧！

4、測(cè)試

測(cè)試代碼如下

#include "SingleList.h"
#include "iostream"
using namespace std;
int main()
{
    SingleList<int> newlist;
    newlist.Insert(0, 1);
    newlist.Insert(0, 2);
    newlist.Insert(0, 3);
    newlist.Insert(0, 4);
    newlist.Insert(2, 20);
    newlist.Output(cout);
    newlist.Delete(1);
    newlist.Output(cout);
    cout<<newlist.Length()<<endl;
    cout << newlist.isEmpty() << endl;
    cout << newlist.Search(1)<<endl;
    cout << newlist.Search(5)<<endl;
    int n;
    newlist.Find(1, n);
    cout << n << endl;
    cout << newlist.Find(2)->getElement()<<endl;
    newlist.Update(2, 55);
    newlist.Output(cout);
    newlist.Clear();
    newlist.Find(0);
    cin >> n;
    return 0;
}

我們先預(yù)測(cè)一下輸出，應(yīng)該是
4 3 20 2 1
4 20 2 1
4
0
3
don't find the element!
20
2
4 20 55 1
out of bounds!
運(yùn)行程序

測(cè)試.JPG

運(yùn)行結(jié)果符合我們的預(yù)期，這樣就基本實(shí)現(xiàn)了單鏈表

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容