單連結清單c++實作

#include <iostream>

using namespace std;

class node {
public:
    char data;
    node *next = nullptr;

    node() { next = nullptr; };

    node(char data) : data(data) { next = nullptr; }

};

class linklist {
private:
    int size = 0;//長度
    node *head;//頭節點

public:
    linklist() {
        size = 0;
        head = nullptr;
    }

//（1）	create(): 建立一個空的單連結清單；
    bool create() {
        if (head == nullptr) {//判斷是否建立過表
            head = new node;
            return true;
        }
        return false;
    }

//（2）	insert(i,x): 在單連結清單第i個位置上插入一個元素x；
    bool insert(int i, char x) {
        if (i < 0 || i > size) {//判斷下标合法性
            cout << "下标不合法" << endl;
            return false;
        }
        //node *node1 = new node(x);
        node node1(x);
        if (i == 0) {//如果插在第一個
            node1.next = head->next;
            head->next = &node1;
            //
            size++;
            cout << "插在第一個" << endl;
            return true;
        }
        node *temp = head->next;
        if (i == size) {//如果插在結尾
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = &node1;
            size++;
            cout << "插在結尾" << endl;
            return true;
        }
        //插在一般位置
        for (int j = 0; j < i - 1; j++) {
            temp = temp->next;
        }
        node1.next = temp->next;
        temp->next = &node1;
        size++;
        cout << "插在一般" << endl;

        return true;
    }

//（3）	traverse(): 按序通路單連結清單的每一個資料元素；
    void traverse() {
        if (head == nullptr) {//判斷是否建表
            cout << "未建立表" << endl;
        } else if (size == 0) {//判斷是否有資料
            cout << "表中無資料" << endl;
        } else {
            node *temp = head->next;
            while (temp != nullptr) {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }

//（4）	length(): 求單連結清單長度；
    int length() {
        return size;
    }

//（5）	empty(): 判斷單連結清單是否為空；
    bool empty() {
        return size == 0;
    }

//（6）	visit(i): 傳回單連結清單第i個位置的元素；
    char visit(int i) {
        if (i < 0 || i >= size) {//判斷下标合法性
            cout << "下标不合法" << endl;
            return 0;
        }
        node *temp = head->next;
        for (int j = 0; j < i; j++) {
            temp = temp->next;
        }
        cout << temp->data << endl;
    }

//（7）	search(x): 搜尋某個元素x在單連結清單中是否出現，并傳回x的位置；
    int search(char x) {
        if (head == nullptr) {//判斷是否建表
            cout << "未建立表" << endl;
            return -1;
        } else if (size == 0) {//判斷是否有資料
            cout << "表中無資料" << endl;
            return -1;
        } else {
            int count = 0;//計數器
            int flag = 0;//記錄是否找到，找到置為1
            node *temp = head->next;
            while (temp != nullptr) {
                if (temp->data == x) {
                    flag = 1;
                    break;
                }
                count++;
            }
            if (flag) {//為真代表找到
                return count;
            } else {
                return -1;
            }
        }

    }

//（8）	clear(): 删除單連結清單中的所有資料元素；
    void clear() {
        if (head != nullptr) {
            head->next = nullptr;
            size = 0;
        }
    }

//（9）	remove(i): 删除單連結清單的第i個元素；
    char remove(int i) {
        if (i < 0 || i >= size) {//判斷下标合法性
            cout << "下标不合法" << endl;
            return false;
        }
        if (i == 0) {//如果删除第一個

            head->next = head->next->next;
            size--;
            return true;
        }
        node *temp = head->next;
        if (i == size - 1) {//如果删除結尾
            while (temp->next->next != nullptr) {
                temp = temp->next;
            }
            temp->next = nullptr;
            size--;
            return true;
        }
        //删除一般位置
        for (int j = 0; j < i - 1; j++) {
            temp = temp->next;
        }
        temp->next = temp->next->next;
        size--;
        return true;

    }

//（10）	eraseXY(x, y): 删除單連結清單中元素值在x到y（假設x<=y）之間的所有元素；
    bool eraseXY(int x, int y) {
        if (x < 0 || y >= size || y < x) {//判斷下标合法性
            cout << "下标不合法" << endl;
            return false;
        }
        if (x == 0) {//如果删除第一個
            if (y == size - 1) {//如果y是最後一個
                size = 0;
                head->next = nullptr;
                return true;
            }
            node *temp = head->next;
            for (int j = 0; j < y - 1; j++) {
                temp = temp->next;
            }
            head->next = temp->next->next;
            size = size - (y - x + 1);
            return true;
        }

        if (y == size - 1) {//如果删除結尾
            node *temp = head->next;
            for (int j = 0; j < x - 1; j++) {
                temp = temp->next;
            }
            temp->next = nullptr;
            size = size - (y - x + 1);
            return true;
        }
        //删除一般位置
        node *temp1 = head->next;
        node *temp2 = head->next;
        for (int j = 0; j < x - 1; j++) {
            temp1 = temp1->next;
        }
        for (int j = 0; j < y - 1; j++) {
            temp2 = temp2->next;
        }
        temp1->next = temp2->next->next;
        size = size - (y - x + 1);
        return true;


    }

//（11）	reverse(): 實作單連結清單的逆置。
    void reverse() {
        if (head == nullptr) {//判斷是否建表
            cout << "未建立表" << endl;
        } else if (size == 0) {//判斷是否有資料
            cout << "表中無資料" << endl;
        } else {
            node *p = head->next;
            node *t = head->next;
            head->next = nullptr;
            while (p != nullptr) {
                p->next = head->next;
                head->next = p;
                t = t->next;
                p = t;
            }


        }

    }
};

int main() {
    linklist l;
    l.create();
    l.insert(0, 'b');
    l.insert(1, 'c');
    l.insert(2, 'd');
    l.insert(3, 'e');
    l.traverse();
    cout << l.length() << endl;
    cout << l.empty() << endl;
    cout << l.visit(2) << endl;
    cout << l.search('b') << endl;
    l.reverse();
    l.traverse();
    l.insert(3, 'a');
    l.reverse();
    l.traverse();
    l.remove(2);
    l.eraseXY(1, 2);
    l.clear();
    cout << l.empty() << endl;

    return 0;
}