Lotplace

初始化

Linked List的核心概念是Node組成的串列，
因此必須先宣告Node與Head Node的初始化。

/* 實作資結(1) - Single Linked List*/
#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next = NULL;
    Node(int d){
        data = d; 
    }
};

class SingleLinkedList{
    Node *head;
    public:
    //初始化一個Single Linked List，並給予HEAD初值。
    SingleLinkedList(int data){
        head = new Node(data);
    }
};


int main(){
    SingleLinkedList list = SingleLinkedList(1);
    return 0;
}

接著實作Linked List常見的方法(顯示、新增、移除)
首先，將Linked List中所有元素印出

    //迭代List中所有元素，並且印出。
    void Show(){
        Node *tmp = head;
        cout << tmp->data;
        while(tmp->next != NULL){
            tmp = tmp->next;
            cout << "," << tmp->data;
        }
        cout << endl;
    }

將元素append到尾端

    //加入一個元素到尾端
    void Append(int data){
        Node *tmp = head;
        while(tmp->next != NULL){
            tmp = tmp->next;
        }
        tmp->next = new Node(data);
    }

Insert到指定的位置

    //插入元素至指定index的位置(HEAD從0起算)
    bool Insert(int index, int data){
        Node *tmp = new Node(data);

        //index為0表示插入在HEAD位置
        if(index == 0){
            tmp->next = head;
            head = tmp;
            return true;
        }

        int i = 0;
        Node *before_index = head;
        //要獲取index前一個node才能做insert
        while(i < index - 1){
            before_index = before_index->next;
            i++;
            if(before_index->next == NULL) break; //Linked List迭代到尾端的話強制跳出，避免記憶體存取錯誤。
        }

        //插入在尾端
        if(before_index->next == NULL){
            before_index->next = new Node(data);
            return true;
        }
        //插入在中間
        tmp->next = before_index->next;
        before_index->next = tmp;
        return true;
    }

然後實作刪除節點

    //刪除指定index的節點(HEAD從0起算)
    bool Delete(int index){
        //刪除的是HEAD
        if(index == 0){
            if(head->next == NULL) return false; //只有index的情況不能再刪了，不然會全變成NULL
            head = head->next;
        }

        int i = 0;
        Node *before_index = head;
        //要獲取index前一個node才能做delete
        while(i < index - 1){
            before_index = before_index->next;
            i++;
            if(before_index->next == NULL) break; //Linked List迭代到尾端的話強制跳出，避免記憶體存取錯誤。
        }
        
        Node *tmp = before_index->next;
        before_index->next = before_index->next->next;
        free(tmp); //釋放掉該Node佔的記憶體空間
        
        return true;
    }

最後做一些簡單的測試，完整的CODE:

/* 基本的Single Linked List練習*/
#include <iostream>
using namespace std;

struct Node{
    int data;
    Node *next = NULL;
    Node(int d){
        data = d; 
    }
};

class SingleLinkedList{
    Node *head;
    public:
    //初始化一個Single Linked List，並給予HEAD初值。
    SingleLinkedList(int data){
        head = new Node(data);
    }

    //加入一個元素到尾端
    void Append(int data){
        Node *tmp = head;
        while(tmp->next != NULL){
            tmp = tmp->next;
        }
        tmp->next = new Node(data);
    }

    //迭代List中所有元素，並且印出。
    void Show(){
        Node *tmp = head;
        cout << tmp->data;
        while(tmp->next != NULL){
            tmp = tmp->next;
            cout << "," << tmp->data;
        }
        cout << endl;
    }

    //插入元素至指定index的位置(HEAD從0起算)
    bool Insert(int index, int data){
        Node *tmp = new Node(data);

        //index為0表示插入在HEAD位置
        if(index == 0){
            tmp->next = head;
            head = tmp;
            return true;
        }

        int i = 0;
        Node *before_index = head;
        //要獲取index前一個node才能做insert
        while(i < index - 1){
            before_index = before_index->next;
            i++;
            if(before_index->next == NULL) break; //Linked List迭代到尾端的話強制跳出，避免記憶體存取錯誤。
        }

        //插入在尾端
        if(before_index->next == NULL){
            before_index->next = new Node(data);
            return true;
        }
        //插入在中間
        tmp->next = before_index->next;
        before_index->next = tmp;
        return true;
    }

    //刪除指定index的節點(HEAD從0起算)
    bool Delete(int index){
        //刪除的是HEAD
        if(index == 0){
            if(head->next == NULL) return false; //只有index的情況不能再刪了，不然會全變成NULL
            head = head->next;
        }

        int i = 0;
        Node *before_index = head;
        //要獲取index前一個node才能做delete
        while(i < index - 1){
            before_index = before_index->next;
            i++;
            if(before_index->next == NULL) break; //Linked List迭代到尾端的話強制跳出，避免記憶體存取錯誤。
        }
        
        Node *tmp = before_index->next;
        before_index->next = before_index->next->next;
        free(tmp); //釋放掉該Node佔的記憶體空間
        
        return true;
    }
};


int main(){
    SingleLinkedList list = SingleLinkedList(1);
    list.Append(3);
    list.Append(5);
    list.Insert(3,7); //插入尾端，等同於Append(7)
    list.Insert(0,0); //插入在List HEAD
    list.Insert(2,2); //插入在List中間
    list.Insert(4,4);
    list.Insert(6,6);
    list.Insert(87,87); //超過尾端，強制Append
    list.Delete(8); //刪除尾端
    list.Delete(0); //刪除HEAD
    list.Delete(1); //刪除List中間
    list.Show();
    return 0;
}

---

Filed under: c++,資結 - @ 2021 年 7 月 22 日 上午 11:10

標籤: c++, data_struct