數據結構基礎(8)

鏈表簡介

數組的缺點:

1.元素插入:除了在數組的末尾插入元素之外,在數組的其他任何位置插入元素都需要進行數組元素的頻繁移動(插入位置之後的元素都需往後移動), 時間復雜度約為O(N);

2.數組的刪除:除了在數組的末尾刪除元素之外,在數組的其他任何位置刪除元素都需要進行數組元素的頻繁移動(刪除位置之後的元素都需往前移動), 時間復雜度也為O(N);

鏈表的特點:

由於在鏈表中插入/刪除元素都不需要進行數據的移位, 只需要O(1)時間完成, 因此鏈表適用於頻繁插入與刪除的情況;

但是鏈表也有缺點:鏈表不適用於需要頻繁訪問的情況, 因為如果需要查詢一個數據, 鏈表需要遍歷整個數據序列, 需要的O(n)的時間, 然而由於數組支持隨機訪問, 因此數組只需O(1)的時間便可完成數據的訪問, 因此此時數組就非常便利了!

單鏈表

單鏈表特征如圖所示:

單鏈表只需一個節點(首節點first)來指向該鏈表,有時為了操作方便，在第一個結點之前虛加一個”頭結點”(算法導論稱之為”啞節點”)，以指向頭結點的指針為鏈表的頭指針(為了實現上的方便, 我們采用了這種帶有附加頭結點的鏈表實現方案, 同時也為將來我們將該鏈表改造成循環鏈表與循環雙鏈表打下了基礎)。<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD48cD4gICAg08nT2rWlwbSx7crH0rvW1suz0PK05sihtcS94bm5LCDS8rTLzqrV0rXaIGkguPbK/b7d1KrL2CwgsdjQ68/I1dK1vbXaIGktMSC49sr9vt3UqsvYoaM8L3A+PHA+IDwvcD48cD48c3Ryb25nPrWlwbSx7b3ateO5udTsOjwvc3Ryb25nPjwvcD48cD48cHJlIGNsYXNzPQ=="brush:java;">class Node { private: Type data; //數據域:節點數據 Node *next; //指針域:下一個節點 };

但為了能夠應用於MyList類, 需要對其改造:

//鏈表節點
template 
class Node
{
    //可以將MyList類作為Node的友元
    //或者將Node類做成MyList的嵌套類, 嵌套在MyList中, 也可以完成該功能
friend class MyList;

    template 
    friend ostream &operator<<(ostream &os, const MyList &list);
private:
    //constructor說明:
    //next = NULL;    //因為這是一個新生成的節點, 因此下一個節點為空
    Node(const Type &dataValue):data(dataValue), next(NULL) {}

    Type data;  //數據域:節點數據
    Node *next; //指針域:下一個節點
};

單鏈表構造:

//鏈表
template 
class MyList
{
    template 
    friend ostream &operator<<(ostream &os, const MyList &list);
public:
    MyList();
    ~MyList();

    //將元素插入表頭
    void insertFront(const Type &data);
    //將元素插入到位置index上(index從1開始)
    void insert(const Type &data, int index);
    //刪除表中所有值為data的節點
    void remove(const Type &data);
    bool isEmpty() const;

    //鏈表反轉
    void invort();
    //將鏈表(list)鏈接到本條鏈表的末尾
    void concatenate(const MyList &list);

private:
    //指向第一個節點的指針
    Node *first;
};

//鏈表的構造
template 
MyList::MyList()
{
    //first指向一個空節點
    first = new Node(0);
    first -> next = NULL;
}
//鏈表的析構
template 
MyList::~MyList()
{
    Node *deleteNode = NULL;
    while (first != NULL)
    {
        deleteNode = first;
        first = first -> next;
        delete deleteNode;
    }
}

元素插入:

由前面的圖像可見，在單鏈表中插入結點只需要修改指針。但同時，若要在第i個結點之前插入元素，修改的是第i-1 個結點的指針。

因此,在單鏈表中第 i 個結點要進行的基本工作為:找到線性表中第i-1個結點，然後修改其指向後繼的指針。

template 
void MyList::insertFront(const Type &data)
{
    Node *newNode = new Node(data);
    newNode -> next = first -> next;
    first -> next = newNode;
}

template 
void MyList::insert(const Type &data, int index)
{
    //由於我們在表頭添加了一個空節點
    //因此如果鏈表為空, 或者在鏈表為1的位置添加元素
    //其操作與在其他位置添加元素相同

    int count = 1;
    //此時searchNode肯定不為NULL
    Node *searchNode = first;
    // 找到要插入的位置
    // 如果所給index過大(超過了鏈表的長度)
    // 則將該元素插入到鏈表表尾
    // 原因是 searchNode->next != NULL 這個條件已經不滿足了
    // 已經到達表尾
    while (count < index && searchNode->next != NULL)
    {
        ++ count;
        searchNode = searchNode->next;
    }

    // 插入鏈表
    Node *newNode = new Node(data);
    newNode->next = searchNode->next;
    searchNode->next = newNode;
}

元素的刪除:

在單鏈表中刪除第 i 個結點的基本操作為:找到線性表中第i-1個結點，修改其指向後繼的指針。

template 
void MyList::remove(const Type &data)
{
    if (isEmpty())
        return ;

    Node *previous = first;   //保存要刪除節點的前一個節點
    for (Node *searchNode = first->next;
            searchNode != NULL;
            searchNode = searchNode->next)
    {
        if (searchNode->data == data)
        {
            previous->next = searchNode->next;
            delete searchNode;
            //重新調整searchNode指針
            //繼續遍歷鏈表查看是否還有相等元素

            //如果當前searchNode已經到達了最後一個節點
            //也就是searchNode->next已經等於NULL了, 則下面這條語句不能執行
            if (previous->next == NULL)
                break;

            searchNode = previous->next;
        }
        previous = searchNode;
    }
}

//鏈表的判空
template 
bool MyList::isEmpty() const
{
    return first->next == NULL;
}