iT邦幫忙

1

資料結構 鏈結串列(Linked List)

  • 分享至 

  • xImage
  •  

目錄:資料結構系列文章

單向鏈結串列(Singly Linked List)

用c++實作

#include <iostream>
using namespace std;

template <typename T>
class SinglyLinkedList; // 為了將class SinglyLinkedList設成class ListNode的friend,必須先宣告

template <typename T>
class ListNode
{
public:
    ListNode(T x) : value(x), next(0) {} // 使用c++的成員初始化串列,將value初始化為x,next初始化為0
private:
    T value;
    ListNode<T> *next;
    friend class SinglyLinkedList<T>; // 將class SinglyLinkedList宣告為friend,讓class SinglyLinkedList可以存取ListNode的private成員
};

template <typename T>
class SinglyLinkedList
{
public:
    SinglyLinkedList() : head(0), size(0) {}
    ~SinglyLinkedList()
    {
        ListNode<T> *current = head;
        while (current != 0)
        {
            ListNode<T> *NextNode = current->next;
            delete current;
            current = NextNode;
        }
        head = 0; // 當指標被delete後, 將其指向NULL, 可以避免不必要bug
    }
    void PrintList() // 印出list中的所有資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *current = head;
            while (current != 0) // 節點的traversal(走訪),從head節點走到最後一個節點
            {
                cout << current->value << " ";
                current = current->next;
            }
            cout << endl;
        }
    }
    void PushFront(T data) // 在list的最前端塞入資料
    {
        ListNode<T> *NewNode = new ListNode<T>(data);
        if (head == 0)
        {
            head = NewNode;
        }
        else
        {
            NewNode->next = head;
            head = NewNode;
        }
        ++size;
    }
    void PopFront() // 移除list中的第一個資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *NextNode = head->next;
            delete head;
            head = NextNode;
        }
        --size;
    }
    void PushBack(T data) // 在list的最後端塞入資料
    {
        if (head == 0)
        {
            PushFront(data);
        }
        else
        {
            ListNode<T> *NewNode = new ListNode<T>(data);
            ListNode<T> *current = head;
            while (current->next != 0)
            {
                current = current->next;
            }
            current->next = NewNode;
            ++size;
        }
    }
    void PopBack() // 移除list中的最後一個資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *current = head;
            while (current->next->next != 0)
            {
                current = current->next;
            }
            delete current->next;
            current->next = 0; // 這邊因為是最後一個節點,所以delete掉後一定要把它指向NULL,不然PrintList中會產生無窮迴圈
            --size;
        }
    }
    void DeleteData(T data) // 刪除list中的T data資料
    {
        ListNode<T> *previous = 0, *current = head;
        while (current != 0 && current->value != data) // 如果current為null或current的資料為我們所要刪除的就停止traversal
        {
            previous = current;
            current = current->next;
        }
        if (current == 0) // current為null代表list為空或是list中不存在我們想要刪除的資料
        {
            cout << "There is no " << data << " in list." << endl;
        }
        else if (current == head) // 如果我們想要刪除的資料是第一個節點
        {
            head = current->next;
            delete current;
            current = 0;
            --size;
        }
        else // 想要刪除的資料不是第一個節點
        {
            previous->next = current->next;
            delete current;
            current = 0;
            --size;
        }
    }
    void Clear() // 清除list中所有資料
    {
        int i = 0;
        while (head != 0)
        {
            ListNode<T> *current = head;
            head = head->next;
            delete current;
            current = 0;
        }
        size = 0;
    }
    void Reverse() // 把整串list反轉
    {
        if (head != 0 && head->next != 0) // 如果list為空或是只有1個節點,那就不須做任何動作
        {
            ListNode<T> *previous = 0, *current = head;
            while (current != 0) // 從最前面的Null節點traversal到最後一個節點
            {
                ListNode<T> *NextNode = current->next; // 用變數紀錄原本的下一個節點
                current->next = previous;              // 把節點反過來指
                previous = current;
                current = NextNode;
            }
            head = previous;
        }
    }
    int getSize() // 回傳list資料個數
    {
        return size;
    }
    T getHead() // 回傳第一個資料
    {
        if (isEmpty())
        {
            cout << "List is empty." << endl;
            return 0;
        }
        else
        {
            return head->value;
        }
    }
    bool isEmpty() // 回傳list是否為空
    {
        return head == 0;
    }

private:
    ListNode<T> *head;
    int size;
};
int main()
{
    SinglyLinkedList<double> list;
    list.PrintList();
    cout << list.isEmpty() << endl;
    cout << list.getSize() << endl;
    cout << list.getHead() << endl;
    list.DeleteData(4);
    list.PushBack(1);
    cout << list.getSize() << endl;
    list.PushBack(3);
    list.PushFront(5);
    list.PushFront(7);
    list.PrintList();
    cout << list.isEmpty() << endl;
    cout << list.getSize() << endl;
    cout << list.getHead() << endl;
    list.PopBack();
    list.PushBack(9);
    list.DeleteData(5);
    list.PrintList();
    list.PushFront(11);
    list.PushFront(16);
    list.PushBack(13);
    list.PrintList();
    list.PopFront();
    list.PushBack(15);
    list.DeleteData(1);
    list.PrintList();
    list.Reverse();
    list.PrintList();
    cout << list.isEmpty() << endl;
    cout << list.getSize() << endl;
    cout << list.getHead() << endl;
    list.Clear();
    list.PrintList();
    cout << list.getHead();
    return 0;
}

output:

List is empty.
1
0
List is empty.
0
There is no 4 in list.
1
7 5 1 3 
0
4
7
7 1 9 
16 11 7 1 9 13 
11 7 9 13 15 
15 13 9 7 11 
0
5
15
List is empty.
List is empty.
0

用python實作

class ListNode:
    def __init__(self, x):
        self.value = x
        self.next = None


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def PrintList(self): # 印出list中的所有資料
        if self.head is None:
            print("List is empty.")
        else:
            current = self.head
            while current is not None: # 節點的traversal(遍歷或尋訪),從head節點走到最後一個節點
                print(current.value, end=' ')
                current = current.next
            print()

    def PushFront(self, data): # 在list的最前端塞入資料
        NewNode = ListNode(data)
        if self.head is None:
            self.head = NewNode
        else:
            NewNode.next = self.head
            self.head = NewNode
        self.size += 1

    def PopFront(self): # 移除list中的第一個資料
        TempNode = self.head
        if TempNode is None:
            print("List is empty.")
        else:
            self.head = TempNode.next
            TempNode = None
        self.size -= 1

    def PushBack(self, data): # 在list的最後端塞入資料
        if self.head is None:
            self.PushFront(data)
        else:
            TempNode = self.head
            while(TempNode.next is not None):
                TempNode = TempNode.next
            TempNode.next = ListNode(data)
            self.size += 1
        

    def PopBack(self): # 移除list中的最後一個資料
        TempNode = self.head
        if TempNode is None:
            print("List is empty.")
        else:
            while(TempNode.next.next is not None):
                TempNode = TempNode.next
            TempNode.next = None
        self.size -= 1

    def DeleteData(self, data): # 刪除list中的T data資料
        previous = None
        current = self.head
        while (current is not None and current.value != data): # 如果current為null或current的資料為我們所要刪除的就停止traversal
            previous = current
            current = current.next
        if current is None: # current為null代表list為空或是list中不存在我們想要刪除的資料
            print("There is no " + str(data) + " in list")
        elif current == self.head: # 如果我們想要刪除的資料是第一個節點
            self.head = current.next
            current = None
            self.size -= 1
        else: # 想要刪除的資料不是第一個節點
            previous.next = current.next
            current = 0
            self.size -= 1

    def Clear(self): # 清除list中所有資料
        while self.head is not None:
            current = self.head
            self.head = current.next
            current = 0
        self.size = 0

    def Reverse(self): # 把整串list反轉
        if self.head is not None and self.head.next is not None: #  如果list為空或是只有1個節點,那就不須做任何動作
            previous = None
            current = self.head
            while current: # 從最前面的Null節點traversal到最後一個節點
                NextNode = current.next #  用變數紀錄原本的下一個節點
                current.next = previous #  把節點反過來指
                previous = current
                current = NextNode
            self.head = previous

    def GetSize(self): # 回傳list資料個數
        return self.size

    def isEmpty(self): # 回傳list是否為空
        return self.head is None


def main():
    list = SinglyLinkedList()
    list.PrintList()
    print(list.isEmpty())
    print(list.GetSize())
    list.DeleteData(4)
    list.PushBack(1)
    print(list.GetSize())
    list.PushBack(3)
    list.PushFront(5)
    list.PushFront(7)
    list.PrintList()
    print(list.isEmpty())
    print(list.GetSize())
    list.PopBack()
    list.PushBack(9)
    list.DeleteData(5)
    list.PrintList()
    list.PushFront(11)
    list.PushFront(16)
    list.PushBack(13)
    list.PrintList()
    list.PopFront()
    list.PushBack(15)
    list.DeleteData(1)
    list.PrintList()
    list.Reverse()
    list.PrintList()
    print(list.isEmpty())
    print(list.GetSize())
    list.Clear()
    list.PrintList()


if __name__ == '__main__': # 檔案被import時,不執行main()函式
    main()

output:

List is empty.
1
0
There is no 4 in list.
1
7 5 1 3 
0
4
7 1 9 
16 11 7 1 9 13 
11 7 9 13 15 
15 13 9 7 11 
0
5
List is empty.

下一篇:資料結構 堆疊(Stack)


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
marlin12
iT邦研究生 5 級 ‧ 2019-07-15 23:25:47

C++和python作比較,你覺得它們的優點和缺點在那裏?
你比較喜歡用那個程式語言?原因在那裏?

Citrus iT邦新手 5 級 ‧ 2019-07-16 14:01:16 檢舉

c++跟python如果要比較最大的不同就是速度了
如果有在打online judge就會知道
python不適合online judge跟競賽
因為那種都會有限制時間
如果實際去打就會知道python執行時間太久
譬如一個題目 用差不多的寫法
c++執行只要0.7秒但python卻要3秒
但時間限制是2秒
我目前是資工系大一升大二,學校的課程現在主要是資料結構與演算法
這些的課程作業都打c++
不過平常自己有空時都會去寫些別的程式像是網頁程式或是別的東西
這時就會寫python了
你可以參考我的文章
https://ithelp.ithome.com.tw/tags/articles/it%27s%20django%20%E7%94%A8python%E8%BF%85%E9%80%9F%E6%89%93%E9%80%A0web%E6%87%89%E7%94%A8%21%E5%AD%B8%E7%BF%92%E7%B4%80%E9%8C%84

marlin12 iT邦研究生 5 級 ‧ 2019-07-16 22:04:31 檢舉

謝謝你的回覆!
看你在這裏的文章,好像你主要是用python的django來打造網頁吧!
其實python還被廣泛應用在機器學習(Machine Learning)資料分柝(Data analysis)的領域上。
我是較為喜歡強型別(strongly typed)的程式語言,因為可以避開很多弱型別(weakly typed)程式語言的陷阱。
因為python越趨流行,看來無可避免也要用上它。因此,我也嘗試去認識它。
全面分析Python的優點和缺點

Citrus iT邦新手 5 級 ‧ 2019-07-16 22:47:11 檢舉

是的,另外我喜歡python的原因是因為python比起c/c++更容易實作出不同的東西,所以除了本科系的c++,空閒時間我也常常拿來寫python

我要留言

立即登入留言