C++本科生导师制广义表代码实现，包含插入，删除，查询，输出功能

下面是一个基于指针的广义表实现，包含了插入、删除、查询和输出功能。

#include <iostream>
using namespace std;

// 广义表节点
template <typename T>
class GLNode {
public:
    T data;
    GLNode<T> *sublist; // 子表
    GLNode<T> *next; // 同层下一个节点
    GLNode() : sublist(nullptr), next(nullptr) {}
    GLNode(T d) : data(d), sublist(nullptr), next(nullptr) {}
};

// 广义表
template <typename T>
class GList {
public:
    GList() : head(nullptr) {}
    GList(const GList<T> &gl);
    ~GList() { destroy(head); }
    void insert(int i, const GList<T> &gl);
    void remove(int i);
    GLNode<T> *find(T d);
    void print();
private:
    GLNode<T> *head;
    GLNode<T> *copy(GLNode<T> *p);
    void destroy(GLNode<T> *p);
};

// 拷贝构造函数
template <typename T>
GList<T>::GList(const GList<T> &gl) {
    head = copy(gl.head);
}

// 拷贝广义表
template <typename T>
GLNode<T> *GList<T>::copy(GLNode<T> *p) {
    if (!p) return nullptr;
    GLNode<T> *q = new GLNode<T>(p->data);
    q->sublist = copy(p->sublist);
    q->next = copy(p->next);
    return q;
}

// 销毁广义表
template <typename T>
void GList<T>::destroy(GLNode<T> *p) {
    if (!p) return;
    destroy(p->sublist);
    destroy(p->next);
    delete p;
}

// 插入广义表
template <typename T>
void GList<T>::insert(int i, const GList<T> &gl) {
    GLNode<T> *p = head, *q = gl.head;
    if (!q) return;
    if (i == 1) {
        GLNode<T> *r = new GLNode<T>;
        r->sublist = copy(q);
        r->next = head;
        head = r;
        return;
    }
    for (int j = 2; p && j < i; j++) {
        p = p->next;
    }
    if (p) {
        GLNode<T> *r = new GLNode<T>;
        r->sublist = copy(q);
        r->next = p->next;
        p->next = r;
    }
}

// 删除广义表
template <typename T>
void GList<T>::remove(int i) {
    GLNode<T> *p = head, *q;
    if (i == 1) {
        head = head->next;
        delete p;
        return;
    }
    for (int j = 2; p && j < i; j++) {
        p = p->next;
    }
    if (p && p->next) {
        q = p->next;
        p->next = q->next;
        destroy(q);
    }
}

// 查找节点
template <typename T>
GLNode<T> *GList<T>::find(T d) {
    GLNode<T> *p = head, *q;
    while (p) {
        if (p->data == d) {
            return p;
        }
        if (q = find(p->sublist, d)) {
            return q;
        }
        p = p->next;
    }
    return nullptr;
}

// 查找子表中的节点
template <typename T>
GLNode<T> *GList<T>::find(GLNode<T> *p, T d) {
    if (!p) return nullptr;
    GLNode<T> *q;
    if (p->data == d) {
        return p;
    }
    if (q = find(p->sublist, d)) {
        return q;
    }
    return find(p->next, d);
}

// 输出广义表
template <typename T>
void GList<T>::print() {
    GLNode<T> *p = head;
    while (p) {
        if (p->sublist) {
            cout << '(';
            GList<T>(p->sublist).print();
            cout << ')';
        } else {
            cout << p->data;
        }
        if (p->next) {
            cout << ',';
        }
        p = p->next;
    }
}

int main() {
    GList<int> gl;
    gl.insert(1, GList<int>{1, 2, 3});
    gl.insert(2, GList<int>{4, 5});
    gl.insert(1, GList<int>{6, 7});
    gl.print(); // (6,7,(1,2,3),(4,5))
    gl.remove(2);
    gl.print(); // (6,(1,2,3),(4,5))
    return 0;
}

使用示例：

int main() {
    GList<int> gl;
    gl.insert(1, GList<int>{1, 2, 3});
    gl.insert(2, GList<int>{4, 5});
    gl.insert(1, GList<int>{6, 7});
    gl.print(); // (6,7,(1,2,3),(4,5))
    gl.remove(2);
    gl.print(); // (6,(1,2,3),(4,5))
    return 0;
}