C++ 定义双链表结构，包含析构函数

双链表结构体的定义如下：

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct DoublyLinkedList {
    Node *head;
    Node *tail;
} DoublyLinkedList;

其中，`Node` 结构体表示双链表中的节点，包括三个成员：`data` 表示节点的数据，`prev` 表示指向前一个节点的指针，`next` 表示指向后一个节点的指针。

`DoublyLinkedList` 结构体表示双链表，包括两个成员：`head` 表示指向双链表头部节点的指针，`tail` 表示指向双链表尾部节点的指针。

下面是一个简单的析构函数的实现，用于释放双链表中的所有节点占用的内存空间：

void destroy(DoublyLinkedList *list) {
    Node *curr = list->head;
    while (curr != NULL) {
        Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    list->head = NULL;
    list->tail = NULL;
}

相关问题

c++长整数、高精度运算双向循环链表

实现高精度运算的双向循环链表可以分为三个部分：节点结构体、链表结构体和高精度运算函数。

首先是节点结构体，可以定义如下：

struct Node {
    int val; // 当前节点的值
    Node* next; // 指向下一个节点的指针
    Node* prev; // 指向上一个节点的指针
    // 构造函数
    Node(int v = 0, Node* n = nullptr, Node* p = nullptr) : val(v), next(n), prev(p) {}
};

接下来是链表结构体，可以定义如下：

struct LinkedList {
    Node* head; // 头指针
    Node* tail; // 尾指针
    // 构造函数
    LinkedList() : head(nullptr), tail(nullptr) {}
    // 复制构造函数
    LinkedList(const LinkedList& lst) {
        head = tail = nullptr;
        Node* p = lst.head;
        while (p != nullptr) {
            push_back(p->val);
            p = p->next;
        }
    }
    // 析构函数
    ~LinkedList() {
        while (head != nullptr) {
            Node* p = head;
            head = head->next;
            delete p;
        }
    }
    // 在链表尾部插入一个节点
    void push_back(int v) {
        Node* p = new Node(v, nullptr, tail);
        if (tail != nullptr) {
            tail->next = p;
        } else {
            head = p;
        }
        tail = p;
    }
    // 在链表头部插入一个节点
    void push_front(int v) {
        Node* p = new Node(v, head, nullptr);
        if (head != nullptr) {
            head->prev = p;
        } else {
            tail = p;
        }
        head = p;
    }
};

最后是高精度运算函数，可以实现加法、减法和乘法等运算：

// 高精度加法
LinkedList add(const LinkedList& a, const LinkedList& b) {
    LinkedList res;
    int carry = 0; // 进位
    Node* p = a.tail;
    Node* q = b.tail;
    while (p != nullptr || q != nullptr) {
        int x = (p != nullptr) ? p->val : 0;
        int y = (q != nullptr) ? q->val : 0;
        int sum = x + y + carry;
        res.push_front(sum % 10);
        carry = sum / 10;
        if (p != nullptr) {
            p = p->prev;
        }
        if (q != nullptr) {
            q = q->prev;
        }
    }
    if (carry > 0) {
        res.push_front(carry);
    }
    return res;
}

// 高精度减法
LinkedList sub(const LinkedList& a, const LinkedList& b) {
    LinkedList res;
    int borrow = 0; // 借位
    Node* p = a.tail;
    Node* q = b.tail;
    while (p != nullptr || q != nullptr) {
        int x = (p != nullptr) ? p->val : 0;
        int y = (q != nullptr) ? q->val : 0;
        int diff = x - y - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_front(diff);
        if (p != nullptr) {
            p = p->prev;
        }
        if (q != nullptr) {
            q = q->prev;
        }
    }
    // 去除前导零
    while (res.head->next != nullptr && res.head->val == 0) {
        Node* p = res.head;
        res.head = res.head->next;
        res.head->prev = nullptr;
        delete p;
    }
    return res;
}

// 高精度乘法
LinkedList mul(const LinkedList& a, const LinkedList& b) {
    LinkedList res;
    int n = a.tail != nullptr ? 1 : 0;
    int m = b.tail != nullptr ? 1 : 0;
    if (n == 0 || m == 0) {
        return res;
    }
    int len = n + m - 1;
    int* c = new int[len];
    memset(c, 0, len * sizeof(int));
    Node* p = a.tail;
    for (int i = 0; p != nullptr; i++, p = p->prev) {
        Node* q = b.tail;
        for (int j = 0; q != nullptr; j++, q = q->prev) {
            c[i + j] += p->val * q->val;
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
    while (len > 0 && c[len - 1] == 0) {
        len--;
    }
    for (int i = len - 1; i >= 0; i--) {
        res.push_back(c[i]);
    }
    delete[] c;
    return res;
}

这样，我们就实现了一个可以进行高精度运算的双向循环链表。

用C++实现一个基于模板的双向循环链表并加上详细的注释

好的，以下是基于模板的双向循环链表的实现代码，注释详细：

#include <iostream>
using namespace std;

// 定义节点结构体
template<typename T>
struct Node {
    T data; // 节点中存储的数据
    Node<T>* next; // 指向下一个节点的指针
    Node<T>* prev; // 指向前一个节点的指针
};

// 定义双向循环链表类
template<typename T>
class DoublyLinkedList {
private:
    Node<T>* head; // 头节点指针
    Node<T>* tail; // 尾节点指针
    int size; // 链表大小
public:
    // 构造函数
    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }

    // 析构函数
    ~DoublyLinkedList() {
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* temp = current;
            current = current->next;
            delete temp;
        }
        size = 0;
    }

    // 获取链表大小
    int getSize() {
        return size;
    }

    // 判断链表是否为空
    bool isEmpty() {
        return size == 0;
    }

    // 在链表头部添加元素
    void addFirst(T data) {
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        if (head == nullptr) { // 如果链表为空
            head = newNode;
            tail = newNode;
            head->prev = tail;
            tail->next = head;
        } else { // 如果链表不为空
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
            head->prev = tail;
            tail->next = head;
        }
        size++;
    }

    // 在链表尾部添加元素
    void addLast(T data) {
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        if (tail == nullptr) { // 如果链表为空
            head = newNode;
            tail = newNode;
            head->prev = tail;
            tail->next = head;
        } else { // 如果链表不为空
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
            head->prev = tail;
            tail->next = head;
        }
        size++;
    }

    // 在指定位置插入元素
    void add(int index, T data) {
        if (index < 0 || index > size) {
            cout << "Index out of range." << endl;
            return;
        }
        if (index == 0) { // 在链表头部插入元素
            addFirst(data);
            return;
        }
        if (index == size) { // 在链表尾部插入元素
            addLast(data);
            return;
        }
        Node<T>* current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current->next;
        }
        Node<T>* newNode = new Node<T>;
        newNode->data = data;
        newNode->next = current->next;
        current->next->prev = newNode;
        current->next = newNode;
        newNode->prev = current;
        size++;
    }

    // 删除链表头部元素
    void removeFirst() {
        if (head == nullptr) {
            cout << "LinkedList is empty." << endl;
            return;
        }
        if (head == tail) { // 链表中只有一个节点
            delete head;
            head = nullptr;
            tail = nullptr;
        } else { // 链表中有多个节点
            Node<T>* temp = head;
            head = head->next;
            head->prev = tail;
            tail->next = head;
            delete temp;
        }
        size--;
    }

    // 删除链表尾部元素
    void removeLast() {
        if (tail == nullptr) {
            cout << "LinkedList is empty." << endl;
            return;
        }
        if (head == tail) { // 链表中只有一个节点
            delete tail;
            head = nullptr;
            tail = nullptr;
        } else { // 链表中有多个节点
            Node<T>* temp = tail;
            tail = tail->prev;
            tail->next = head;
            head->prev = tail;
            delete temp;
        }
        size--;
    }

    // 删除指定位置的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            cout << "Index out of range." << endl;
            return;
        }
        if (index == 0) { // 删除链表头部元素
            removeFirst();
            return;
        }
        if (index == size - 1) { // 删除链表尾部元素
            removeLast();
            return;
        }
        Node<T>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
    }

    // 获取指定位置的元素
    T get(int index) {
        if (index < 0 || index >= size) {
            cout << "Index out of range." << endl;
            return NULL;
        }
        Node<T>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        return current->data;
    }

    // 修改指定位置的元素
    void set(int index, T data) {
        if (index < 0 || index >= size) {
            cout << "Index out of range." << endl;
            return;
        }
        Node<T>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        current->data = data;
    }

    // 打印链表
    void printList() {
        if (head == nullptr) {
            cout << "LinkedList is empty." << endl;
            return;
        }
        Node<T>* current = head;
        while (current != tail) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << current->data << endl;
    }
};

int main() {
    // 创建双向循环链表对象
    DoublyLinkedList<int> dll;

    // 在链表头部添加元素
    dll.addFirst(1);
    dll.addFirst(2);
    dll.addFirst(3);
    dll.printList(); // 输出： 3 2 1

    // 在链表尾部添加元素
    dll.addLast(4);
    dll.addLast(5);
    dll.addLast(6);
    dll.printList(); // 输出： 3 2 1 4 5 6

    // 在指定位置插入元素
    dll.add(2, 7);
    dll.printList(); // 输出： 3 2 7 1 4 5 6

    // 删除链表头部元素
    dll.removeFirst();
    dll.printList(); // 输出： 2 7 1 4 5 6

    // 删除链表尾部元素
    dll.removeLast();
    dll.printList(); // 输出： 2 7 1 4 5

    // 删除指定位置的元素
    dll.remove(2);
    dll.printList(); // 输出： 2 7 4 5

    // 获取指定位置的元素
    cout << dll.get(2) << endl; // 输出： 4

    // 修改指定位置的元素
    dll.set(2, 8);
    dll.printList(); // 输出： 2 7 8 5

    return 0;
}

这里实现了双向循环链表的基本操作，包括在链表头部、尾部和指定位置插入元素，删除链表头部、尾部和指定位置的元素，获取指定位置的元素和修改指定位置的元素等。在实现过程中，我们采用了模板化编程，使得该链表可以存储任意类型的数据。同时，为了更好地理解和使用该链表，我们在每个函数中都添加了详细的注释。