数据结构第二次作业

#include <assert.h>
#include <iostream>
#include <memory>
 
using namespace std;
 
struct List {
    struct LNode {
        int data;
        struct LNode *next;
    };
    LNode *head_ptr;
 
    List() { head_ptr = nullptr; }
 
    ~List() {
        if (head_ptr == nullptr) {
            return;
        }
        LNode *current = head_ptr;
        do {
            LNode *tmp = current;
            current = current->next;
            free(tmp);
        } while (current != head_ptr);
    }
 
    void insert(int value) {
        LNode *node = static_cast<LNode *>(malloc(sizeof(LNode)));
        assert(node != nullptr);
        node->data = value;
        if (head_ptr == nullptr) {
            head_ptr = node;
            node->next = head_ptr;
            return;
        }
        LNode *tail = head_ptr;
        // 采用尾插法使得顺序输出
        while (tail->next != head_ptr) {
            tail = tail->next;
        }
        tail->next = node;
        node->next = head_ptr;
    }
 
    void erase_ifeq(int value) {
        if (head_ptr == nullptr) {
            return;
        }
        // Start from the 2ne node
        LNode *current = head_ptr->next;
        LNode *prev = head_ptr;
 
        while (current != head_ptr) {
            if (current->data != value) {
                prev = current;
                current = current->next;
                continue;
            }
            prev->next = current->next;
            free(current);
            current = prev->next; // Move to next node
        }
        if (current->data != value) {
            return;
        }
        if (current->next = current) { // Only one remain
            free(head_ptr);
            head_ptr = nullptr;
            return;
        }
        head_ptr = prev->next = current->next;
        free(current);
    }
 
    void print() {
        if (head_ptr == nullptr) {
            cout << "empty!" << endl;
            return;
        }
        LNode *current = head_ptr;
        do {
            cout << current->data << " ";
            current = current->next;
        } while (current != head_ptr);
        cout << endl;
    }
};
 
int main() {
    List list;
    list.print();
    list.insert(1);
    list.insert(1);
    list.insert(1);
    list.insert(1);
    list.print();
    list.insert(2);
    list.print();
    list.erase_ifeq(1);
    list.print();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_SIZE = 30;
 
void erase_n_from(int table[MAX_SIZE], int num, int index) {
    while (index < MAX_SIZE) {
        if (index + num >= MAX_SIZE) {
            table[index++] = 0;
            continue;
        }
        table[index++] = table[index + num];
    }
}
 
void show(int table[MAX_SIZE]) {
    for (size_t i = 0; i < MAX_SIZE; i++) {
        cout << table[i] << " ";
    }
    cout << endl;
}
 
int main() {
    int table[MAX_SIZE] = {3,   2, 5, 6,  7, 54, 3, 6, 7,  9, 99, 7,  6, 45, 4,
                           334, 5, 5, 56, 5, 5,  5, 5, 55, 5, 3,  33, 3, 3,  3};
    show(table);
    erase_n_from(table, 33, 15);
    show(table);
}

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T> class Node {
  public:
    T data;
    Node *next;
    Node *prev;
 
    Node(T value) : data(value), next(nullptr), prev(nullptr) {}
};
 
template <typename T> class DoublyCircularLinkedList {
  private:
    Node<T> *head;
 
  public:
    DoublyCircularLinkedList() : head(nullptr) {}
 
    ~DoublyCircularLinkedList() {
        if (head) {
            Node<T> *current = head;
            do {
                Node<T> *nextNode = current->next;
                delete current;
                current = nextNode;
            } while (current != head);
        }
    }
 
    void append(T value) {
        Node<T> *newNode = new Node<T>(value);
        if (!head) {
            head = newNode;
            head->next = head;
            head->prev = head;
        } else {
            Node<T> *tail = head->prev;
            tail->next = newNode;
            newNode->prev = tail;
            newNode->next = head;
            head->prev = newNode;
        }
    }
 
    void display() const {
        if (!head)
            return;
        Node<T> *current = head;
        do {
            std::cout << current->data << " ";
            current = current->next;
        } while (current != head);
        std::cout << std::endl;
    }
 
    void reverse() {
        if (!head)
            return;
        Node<T> *current = head;
        do {
            swap(current->next,current->prev);
            current = current->prev;
        } while (current != head);
        head = head->next;
    }
};
 
int main() {
    DoublyCircularLinkedList<int> list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
 
    std::cout << "Original list: ";
    list.display();
 
    list.reverse();
 
    std::cout << "Reversed list: ";
    list.display();
 
    return 0;
}