单链表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;
}