链表全操作-单向链表、双向链表和循环链表的完整操作

admin

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;

// 1. 单向链表实现
template <typename T>
class SinglyLinkedList {
private:
    // 节点结构
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    Node* head;  // 头节点
    int size;    // 链表大小

public:
    // 构造函数
    SinglyLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数
    ~SinglyLinkedList() {
        clear();
    }
    
    // 清空链表
    void clear() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
        size = 0;
    }
    
    // 获取链表大小
    int getSize() const {
        return size;
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 在头部插入
    void insertAtHead(T val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    // 在尾部插入
    void insertAtTail(T val) {
        Node* newNode = new Node(val);
        if (isEmpty()) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
        size++;
    }
    
    // 在指定位置插入
    bool insertAtPosition(int pos, T val) {
        if (pos < 0 || pos > size) {
            cout << "位置无效" << endl;
            return false;
        }
        
        if (pos == 0) {
            insertAtHead(val);
            return true;
        }
        
        Node* newNode = new Node(val);
        Node* current = head;
        
        for (int i = 0; i < pos - 1; i++) {
            current = current->next;
        }
        
        newNode->next = current->next;
        current->next = newNode;
        size++;
        return true;
    }
    
    // 删除头部节点
    bool deleteAtHead() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        Node* temp = head;
        head = head->next;
        delete temp;
        size--;
        return true;
    }
    
    // 删除尾部节点
    bool deleteAtTail() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        if (size == 1) {
            delete head;
            head = nullptr;
        } else {
            Node* current = head;
            while (current->next->next != nullptr) {
                current = current->next;
            }
            delete current->next;
            current->next = nullptr;
        }
        size--;
        return true;
    }
    
    // 删除指定值的节点
    bool deleteByValue(T val) {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        if (head->data == val) {
            return deleteAtHead();
        }
        
        Node* current = head;
        while (current->next != nullptr && current->next->data != val) {
            current = current->next;
        }
        
        if (current->next == nullptr) {
            cout << "未找到值为 " << val << " 的节点" << endl;
            return false;
        }
        
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
        size--;
        return true;
    }
    
    // 查找节点是否存在
    bool search(T val) const {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == val) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    // 修改指定值为新值
    bool modify(T oldVal, T newVal) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == oldVal) {
                current->data = newVal;
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    // 遍历链表
    void traverse() const {
        if (isEmpty()) {
            cout << "链表为空" << endl;
            return;
        }
        
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "nullptr" << endl;
    }
};

// 2. 双向链表实现
template <typename T>
class DoublyLinkedList {
private:
    // 节点结构
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(T val) : data(val), prev(nullptr), next(nullptr) {}
    };
    
    Node* head;  // 头节点
    Node* tail;  // 尾节点
    int size;    // 链表大小

public:
    // 构造函数
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // 析构函数
    ~DoublyLinkedList() {
        clear();
    }
    
    // 清空链表
    void clear() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    
    // 获取链表大小
    int getSize() const {
        return size;
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 在头部插入
    void insertAtHead(T val) {
        Node* newNode = new Node(val);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }
    
    // 在尾部插入
    void insertAtTail(T val) {
        Node* newNode = new Node(val);
        if (isEmpty()) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // 在指定位置插入
    bool insertAtPosition(int pos, T val) {
        if (pos < 0 || pos > size) {
            cout << "位置无效" << endl;
            return false;
        }
        
        if (pos == 0) {
            insertAtHead(val);
            return true;
        }
        
        if (pos == size) {
            insertAtTail(val);
            return true;
        }
        
        Node* newNode = new Node(val);
        Node* current = head;
        
        // 优化：如果位置在后半部分，从尾部开始查找
        if (pos > size / 2) {
            current = tail;
            for (int i = size - 1; i > pos; i--) {
                current = current->prev;
            }
        } else {
            for (int i = 0; i < pos; i++) {
                current = current->next;
            }
        }
        
        newNode->prev = current->prev;
        newNode->next = current;
        current->prev->next = newNode;
        current->prev = newNode;
        size++;
        return true;
    }
    
    // 删除头部节点
    bool deleteAtHead() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        Node* temp = head;
        if (size == 1) {
            head = nullptr;
            tail = nullptr;
        } else {
            head = head->next;
            head->prev = nullptr;
        }
        delete temp;
        size--;
        return true;
    }
    
    // 删除尾部节点
    bool deleteAtTail() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        Node* temp = tail;
        if (size == 1) {
            head = nullptr;
            tail = nullptr;
        } else {
            tail = tail->prev;
            tail->next = nullptr;
        }
        delete temp;
        size--;
        return true;
    }
    
    // 删除指定值的节点
    bool deleteByValue(T val) {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        // 检查头节点
        if (head->data == val) {
            return deleteAtHead();
        }
        
        // 检查尾节点
        if (tail->data == val) {
            return deleteAtTail();
        }
        
        Node* current = head->next;
        while (current != nullptr && current->data != val) {
            current = current->next;
        }
        
        if (current == nullptr) {
            cout << "未找到值为 " << val << " 的节点" << endl;
            return false;
        }
        
        current->prev->next = current->next;
        current->next->prev = current->prev;
        delete current;
        size--;
        return true;
    }
    
    // 查找节点是否存在
    bool search(T val) const {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == val) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    // 修改指定值为新值
    bool modify(T oldVal, T newVal) {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == oldVal) {
                current->data = newVal;
                return true;
            }
            current = current->next;
        }
        return false;
    }
    
    // 正向遍历链表
    void traverseForward() const {
        if (isEmpty()) {
            cout << "链表为空" << endl;
            return;
        }
        
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " <-> ";
            current = current->next;
        }
        cout << "nullptr" << endl;
    }
    
    // 反向遍历链表
    void traverseBackward() const {
        if (isEmpty()) {
            cout << "链表为空" << endl;
            return;
        }
        
        Node* current = tail;
        while (current != nullptr) {
            cout << current->data << " <-> ";
            current = current->prev;
        }
        cout << "nullptr" << endl;
    }
};

// 3. 循环链表实现（基于单向循环链表）
template <typename T>
class CircularLinkedList {
private:
    // 节点结构
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    Node* head;  // 头节点
    int size;    // 链表大小

public:
    // 构造函数
    CircularLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数
    ~CircularLinkedList() {
        clear();
    }
    
    // 清空链表
    void clear() {
        if (isEmpty()) return;
        
        Node* current = head->next;
        while (current != head) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        delete head;
        head = nullptr;
        size = 0;
    }
    
    // 获取链表大小
    int getSize() const {
        return size;
    }
    
    // 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }
    
    // 在头部插入
    void insertAtHead(T val) {
        Node* newNode = new Node(val);
        if (isEmpty()) {
            head = newNode;
            head->next = head;  // 指向自身，形成循环
        } else {
            newNode->next = head->next;
            head->next = newNode;
            // 交换数据，保持head指针不变但新节点成为逻辑上的头
            swap(head->data, newNode->data);
        }
        size++;
    }
    
    // 在尾部插入
    void insertAtTail(T val) {
        Node* newNode = new Node(val);
        if (isEmpty()) {
            head = newNode;
            head->next = head;  // 指向自身，形成循环
        } else {
            newNode->next = head->next;
            head->next = newNode;
            head = newNode;  // 新节点成为新的尾节点（head指向尾节点）
        }
        size++;
    }
    
    // 在指定位置插入
    bool insertAtPosition(int pos, T val) {
        if (pos < 0 || pos > size) {
            cout << "位置无效" << endl;
            return false;
        }
        
        if (pos == 0) {
            insertAtHead(val);
            return true;
        }
        
        if (pos == size) {
            insertAtTail(val);
            return true;
        }
        
        Node* newNode = new Node(val);
        Node* current = head;
        
        // 移动到要插入位置的前一个节点
        for (int i = 0; i < pos; i++) {
            current = current->next;
        }
        
        newNode->next = current->next;
        current->next = newNode;
        size++;
        return true;
    }
    
    // 删除头部节点
    bool deleteAtHead() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        if (size == 1) {
            delete head;
            head = nullptr;
        } else {
            Node* temp = head->next;
            head->data = temp->data;  // 复制下一个节点的数据到当前头节点
            head->next = temp->next;  // 跳过下一个节点
            delete temp;
        }
        size--;
        return true;
    }
    
    // 删除尾部节点
    bool deleteAtTail() {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        if (size == 1) {
            delete head;
            head = nullptr;
        } else {
            // 找到尾节点的前一个节点
            Node* current = head;
            while (current->next != head) {
                current = current->next;
            }
            
            current->next = head->next;
            delete head;
            head = current;  // 前一个节点成为新的尾节点
        }
        size--;
        return true;
    }
    
    // 删除指定值的节点
    bool deleteByValue(T val) {
        if (isEmpty()) {
            cout << "链表为空，无法删除" << endl;
            return false;
        }
        
        // 特殊情况：只有一个节点
        if (size == 1) {
            if (head->data == val) {
                delete head;
                head = nullptr;
                size--;
                return true;
            } else {
                cout << "未找到值为 " << val << " 的节点" << endl;
                return false;
            }
        }
        
        Node* current = head;
        Node* prev = nullptr;
        
        // 查找要删除的节点
        do {
            prev = current;
            current = current->next;
            if (current->data == val) {
                prev->next = current->next;
                
                // 如果删除的是头节点（当前head的下一个节点）
                if (current == head->next && head->data == val) {
                    head->data = current->data;
                    head->next = current->next;
                }
                
                // 如果删除的是尾节点（head本身）
                if (current == head) {
                    head = prev;
                }
                
                delete current;
                size--;
                return true;
            }
        } while (current != head);
        
        cout << "未找到值为 " << val << " 的节点" << endl;
        return false;
    }
    
    // 查找节点是否存在
    bool search(T val) const {
        if (isEmpty()) return false;
        
        Node* current = head;
        do {
            if (current->data == val) {
                return true;
            }
            current = current->next;
        } while (current != head);
        
        return false;
    }
    
    // 修改指定值为新值
    bool modify(T oldVal, T newVal) {
        if (isEmpty()) return false;
        
        Node* current = head;
        do {
            if (current->data == oldVal) {
                current->data = newVal;
                return true;
            }
            current = current->next;
        } while (current != head);
        
        return false;
    }
    
    // 遍历链表
    void traverse() const {
        if (isEmpty()) {
            cout << "链表为空" << endl;
            return;
        }
        
        Node* current = head;
        do {
            cout << current->data << " -> ";
            current = current->next;
        } while (current != head);
        cout << "(回到头部)" << endl;
    }
};

// 测试函数
int main() {
    // 测试单向链表
    cout << "=== 测试单向链表 ===" << endl;
    SinglyLinkedList<int> sll;
    sll.insertAtHead(1);
    sll.insertAtTail(3);
    sll.insertAtPosition(1, 2);
    sll.traverse();  // 1 -> 2 -> 3 -> nullptr
    cout << "查找 2: " << (sll.search(2) ? "找到" : "未找到") << endl;
    sll.modify(2, 5);
    sll.traverse();  // 1 -> 5 -> 3 -> nullptr
    sll.deleteByValue(5);
    sll.traverse();  // 1 -> 3 -> nullptr
    cout << "单向链表大小: " << sll.getSize() << endl;
    
    // 测试双向链表
    cout << "\n=== 测试双向链表 ===" << endl;
    DoublyLinkedList<int> dll;
    dll.insertAtHead(1);
    dll.insertAtTail(3);
    dll.insertAtPosition(1, 2);
    dll.traverseForward();  // 1 <-> 2 <-> 3 <-> nullptr
    dll.traverseBackward(); // 3 <-> 2 <-> 1 <-> nullptr
    cout << "查找 2: " << (dll.search(2) ? "找到" : "未找到") << endl;
    dll.modify(2, 5);
    dll.traverseForward();  // 1 <-> 5 <-> 3 <-> nullptr
    dll.deleteByValue(5);
    dll.traverseForward();  // 1 <-> 3 <-> nullptr
    cout << "双向链表大小: " << dll.getSize() << endl;
    
    // 测试循环链表
    cout << "\n=== 测试循环链表 ===" << endl;
    CircularLinkedList<int> cll;
    cll.insertAtHead(1);
    cll.insertAtTail(3);
    cll.insertAtPosition(1, 2);
    cll.traverse();  // 1 -> 2 -> 3 -> (回到头部)
    cout << "查找 2: " << (cll.search(2) ? "找到" : "未找到") << endl;
    cll.modify(2, 5);
    cll.traverse();  // 1 -> 5 -> 3 -> (回到头部)
    cll.deleteByValue(5);
    cll.traverse();  // 1 -> 3 -> (回到头部)
    cout << "循环链表大小: " << cll.getSize() << endl;
    
    return 0;
}

admin

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;

// 1. 单向链表实现
// 节点结构体
typedef struct SinglyNode {
    int data;
    SinglyNode* next;
} SinglyNode;

// 创建新节点
SinglyNode* createSinglyNode(int val) {
    SinglyNode* node = new SinglyNode;  // 使用new替代malloc
    node->data = val;
    node->next = nullptr;
    return node;
}

// 初始化链表（返回头节点）
SinglyNode* initSinglyLinkedList() {
    return nullptr;  // 空链表头节点为nullptr
}

// 获取链表长度
int getSinglyListLength(SinglyNode* head) {
    int length = 0;
    SinglyNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}

// 判断链表是否为空
bool isSinglyListEmpty(SinglyNode* head) {
    return head == nullptr;
}

// 在头部插入
SinglyNode* insertSinglyAtHead(SinglyNode* head, int val) {
    SinglyNode* newNode = createSinglyNode(val);
    newNode->next = head;
    return newNode;  // 新节点成为新的头节点
}

// 在尾部插入
SinglyNode* insertSinglyAtTail(SinglyNode* head, int val) {
    SinglyNode* newNode = createSinglyNode(val);
    
    if (isSinglyListEmpty(head)) {
        return newNode;  // 空链表时新节点成为头节点
    }
    
    SinglyNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

// 在指定位置插入（pos从0开始）
SinglyNode* insertSinglyAtPosition(SinglyNode* head, int pos, int val) {
    int length = getSinglyListLength(head);
    if (pos < 0 || pos > length) {
        cout << "位置无效" << endl;
        return head;
    }
    
    if (pos == 0) {
        return insertSinglyAtHead(head, val);
    }
    
    SinglyNode* newNode = createSinglyNode(val);
    SinglyNode* current = head;
    
    for (int i = 0; i < pos - 1; i++) {
        current = current->next;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

// 删除头部节点
SinglyNode* deleteSinglyAtHead(SinglyNode* head) {
    if (isSinglyListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    SinglyNode* temp = head;
    head = head->next;
    delete temp;  // 使用delete替代free
    return head;
}

// 删除尾部节点
SinglyNode* deleteSinglyAtTail(SinglyNode* head) {
    if (isSinglyListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 只有一个节点的情况
    if (head->next == nullptr) {
        delete head;  // 使用delete替代free
        return nullptr;
    }
    
    SinglyNode* current = head;
    while (current->next->next != nullptr) {
        current = current->next;
    }
    
    delete current->next;  // 使用delete替代free
    current->next = nullptr;
    return head;
}

// 删除指定值的节点
SinglyNode* deleteSinglyByValue(SinglyNode* head, int val) {
    if (isSinglyListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 头节点就是要删除的节点
    if (head->data == val) {
        return deleteSinglyAtHead(head);
    }
    
    SinglyNode* current = head;
    while (current->next != nullptr && current->next->data != val) {
        current = current->next;
    }
    
    if (current->next == nullptr) {
        cout << "未找到值为 " << val << " 的节点" << endl;
        return head;
    }
    
    SinglyNode* temp = current->next;
    current->next = current->next->next;
    delete temp;  // 使用delete替代free
    return head;
}

// 查找节点是否存在
bool searchSinglyNode(SinglyNode* head, int val) {
    SinglyNode* current = head;
    while (current != nullptr) {
        if (current->data == val) {
            return true;
        }
        current = current->next;
    }
    return false;
}

// 修改指定值为新值
bool modifySinglyNode(SinglyNode* head, int oldVal, int newVal) {
    SinglyNode* current = head;
    while (current != nullptr) {
        if (current->data == oldVal) {
            current->data = newVal;
            return true;
        }
        current = current->next;
    }
    return false;
}

// 遍历链表
void traverseSinglyList(SinglyNode* head) {
    if (isSinglyListEmpty(head)) {
        cout << "链表为空" << endl;
        return;
    }
    
    SinglyNode* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "nullptr" << endl;
}

// 清空链表
SinglyNode* clearSinglyList(SinglyNode* head) {
    SinglyNode* current = head;
    while (current != nullptr) {
        SinglyNode* next = current->next;
        delete current;  // 使用delete替代free
        current = next;
    }
    return nullptr;  // 清空后头节点为nullptr
}

// 2. 双向链表实现
// 节点结构体
typedef struct DoublyNode {
    int data;
    DoublyNode* prev;
    DoublyNode* next;
} DoublyNode;

// 创建新节点
DoublyNode* createDoublyNode(int val) {
    DoublyNode* node = new DoublyNode;  // 使用new替代malloc
    node->data = val;
    node->prev = nullptr;
    node->next = nullptr;
    return node;
}

// 初始化链表（返回头节点）
DoublyNode* initDoublyLinkedList() {
    return nullptr;
}

// 获取链表长度
int getDoublyListLength(DoublyNode* head) {
    int length = 0;
    DoublyNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}

// 判断链表是否为空
bool isDoublyListEmpty(DoublyNode* head) {
    return head == nullptr;
}

// 获取尾节点
DoublyNode* getDoublyListTail(DoublyNode* head) {
    if (isDoublyListEmpty(head)) {
        return nullptr;
    }
    
    DoublyNode* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    return current;
}

// 在头部插入
DoublyNode* insertDoublyAtHead(DoublyNode* head, int val) {
    DoublyNode* newNode = createDoublyNode(val);
    
    if (isDoublyListEmpty(head)) {
        return newNode;
    }
    
    newNode->next = head;
    head->prev = newNode;
    return newNode;
}

// 在尾部插入
DoublyNode* insertDoublyAtTail(DoublyNode* head, int val) {
    DoublyNode* newNode = createDoublyNode(val);
    
    if (isDoublyListEmpty(head)) {
        return newNode;
    }
    
    DoublyNode* tail = getDoublyListTail(head);
    tail->next = newNode;
    newNode->prev = tail;
    return head;
}

// 在指定位置插入（pos从0开始）
DoublyNode* insertDoublyAtPosition(DoublyNode* head, int pos, int val) {
    int length = getDoublyListLength(head);
    if (pos < 0 || pos > length) {
        cout << "位置无效" << endl;
        return head;
    }
    
    if (pos == 0) {
        return insertDoublyAtHead(head, val);
    }
    
    if (pos == length) {
        return insertDoublyAtTail(head, val);
    }
    
    DoublyNode* newNode = createDoublyNode(val);
    DoublyNode* current = head;
    
    // 找到要插入位置的节点
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    
    newNode->prev = current->prev;
    newNode->next = current;
    current->prev->next = newNode;
    current->prev = newNode;
    
    return head;
}

// 删除头部节点
DoublyNode* deleteDoublyAtHead(DoublyNode* head) {
    if (isDoublyListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    DoublyNode* temp = head;
    head = head->next;
    
    if (head != nullptr) {
        head->prev = nullptr;
    }
    
    delete temp;  // 使用delete替代free
    return head;
}

// 删除尾部节点
DoublyNode* deleteDoublyAtTail(DoublyNode* head) {
    if (isDoublyListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 只有一个节点的情况
    if (head->next == nullptr) {
        delete head;  // 使用delete替代free
        return nullptr;
    }
    
    DoublyNode* tail = getDoublyListTail(head);
    tail->prev->next = nullptr;
    delete tail;  // 使用delete替代free
    
    return head;
}

// 删除指定值的节点
DoublyNode* deleteDoublyByValue(DoublyNode* head, int val) {
    if (isDoublyListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 头节点就是要删除的节点
    if (head->data == val) {
        return deleteDoublyAtHead(head);
    }
    
    DoublyNode* current = head->next;
    while (current != nullptr && current->data != val) {
        current = current->next;
    }
    
    if (current == nullptr) {
        cout << "未找到值为 " << val << " 的节点" << endl;
        return head;
    }
    
    // 尾节点的情况
    if (current->next == nullptr) {
        return deleteDoublyAtTail(head);
    }
    
    // 中间节点的情况
    current->prev->next = current->next;
    current->next->prev = current->prev;
    delete current;  // 使用delete替代free
    
    return head;
}

// 查找节点是否存在
bool searchDoublyNode(DoublyNode* head, int val) {
    DoublyNode* current = head;
    while (current != nullptr) {
        if (current->data == val) {
            return true;
        }
        current = current->next;
    }
    return false;
}

// 修改指定值为新值
bool modifyDoublyNode(DoublyNode* head, int oldVal, int newVal) {
    DoublyNode* current = head;
    while (current != nullptr) {
        if (current->data == oldVal) {
            current->data = newVal;
            return true;
        }
        current = current->next;
    }
    return false;
}

// 正向遍历链表
void traverseDoublyForward(DoublyNode* head) {
    if (isDoublyListEmpty(head)) {
        cout << "链表为空" << endl;
        return;
    }
    
    DoublyNode* current = head;
    while (current != nullptr) {
        cout << current->data << " <-> ";
        current = current->next;
    }
    cout << "nullptr" << endl;
}

// 反向遍历链表
void traverseDoublyBackward(DoublyNode* head) {
    if (isDoublyListEmpty(head)) {
        cout << "链表为空" << endl;
        return;
    }
    
    DoublyNode* current = getDoublyListTail(head);
    while (current != nullptr) {
        cout << current->data << " <-> ";
        current = current->prev;
    }
    cout << "nullptr" << endl;
}

// 清空链表
DoublyNode* clearDoublyList(DoublyNode* head) {
    DoublyNode* current = head;
    while (current != nullptr) {
        DoublyNode* next = current->next;
        delete current;  // 使用delete替代free
        current = next;
    }
    return nullptr;
}

// 3. 循环链表实现（基于单向循环链表）
// 节点结构体
typedef struct CircularNode {
    int data;
    CircularNode* next;
} CircularNode;

// 创建新节点
CircularNode* createCircularNode(int val) {
    CircularNode* node = new CircularNode;  // 使用new替代malloc
    node->data = val;
    node->next = nullptr;
    return node;
}

// 初始化链表（返回头节点）
CircularNode* initCircularLinkedList() {
    return nullptr;
}

// 获取链表长度
int getCircularListLength(CircularNode* head) {
    if (head == nullptr) {
        return 0;
    }
    
    int length = 1;  // 至少有头节点
    CircularNode* current = head->next;
    
    while (current != head) {
        length++;
        current = current->next;
    }
    
    return length;
}

// 判断链表是否为空
bool isCircularListEmpty(CircularNode* head) {
    return head == nullptr;
}

// 在头部插入
CircularNode* insertCircularAtHead(CircularNode* head, int val) {
    CircularNode* newNode = createCircularNode(val);
    
    if (isCircularListEmpty(head)) {
        head = newNode;
        head->next = head;  // 指向自身，形成循环
        return head;
    }
    
    // 新节点插入到头节点之后，然后交换数据
    newNode->next = head->next;
    head->next = newNode;
    
    // 交换数据，使新节点成为逻辑上的头节点
    int temp = head->data;
    head->data = newNode->data;
    newNode->data = temp;
    
    return head;
}

// 在尾部插入
CircularNode* insertCircularAtTail(CircularNode* head, int val) {
    CircularNode* newNode = createCircularNode(val);
    
    if (isCircularListEmpty(head)) {
        head = newNode;
        head->next = head;  // 指向自身，形成循环
        return head;
    }
    
    // 插入到头节点之后
    newNode->next = head->next;
    head->next = newNode;
    
    // 新节点成为新的尾节点（头指针指向尾节点）
    head = newNode;
    
    return head;
}

// 在指定位置插入（pos从0开始）
CircularNode* insertCircularAtPosition(CircularNode* head, int pos, int val) {
    int length = getCircularListLength(head);
    
    // 空链表且插入位置为0的情况
    if (isCircularListEmpty(head)) {
        if (pos == 0) {
            return insertCircularAtHead(head, val);
        } else {
            cout << "位置无效" << endl;
            return head;
        }
    }
    
    if (pos < 0 || pos > length) {
        cout << "位置无效" << endl;
        return head;
    }
    
    if (pos == 0) {
        return insertCircularAtHead(head, val);
    }
    
    if (pos == length) {
        return insertCircularAtTail(head, val);
    }
    
    CircularNode* newNode = createCircularNode(val);
    CircularNode* current = head;
    
    // 移动到要插入位置的前一个节点
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    
    return head;
}

// 删除头部节点
CircularNode* deleteCircularAtHead(CircularNode* head) {
    if (isCircularListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 只有一个节点的情况
    if (head->next == head) {
        delete head;  // 使用delete替代free
        return nullptr;
    }
    
    // 将下一个节点的数据复制到头节点，然后删除下一个节点
    CircularNode* temp = head->next;
    head->data = temp->data;
    head->next = temp->next;
    delete temp;  // 使用delete替代free
    
    return head;
}

// 删除尾部节点
CircularNode* deleteCircularAtTail(CircularNode* head) {
    if (isCircularListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 只有一个节点的情况
    if (head->next == head) {
        delete head;  // 使用delete替代free
        return nullptr;
    }
    
    // 找到尾节点的前一个节点
    CircularNode* current = head;
    while (current->next != head) {
        current = current->next;
    }
    
    current->next = head->next;
    delete head;  // 使用delete替代free
    head = current;  // 前一个节点成为新的尾节点
    
    return head;
}

// 删除指定值的节点
CircularNode* deleteCircularByValue(CircularNode* head, int val) {
    if (isCircularListEmpty(head)) {
        cout << "链表为空，无法删除" << endl;
        return head;
    }
    
    // 只有一个节点的情况
    if (head->next == head) {
        if (head->data == val) {
            delete head;  // 使用delete替代free
            return nullptr;
        } else {
            cout << "未找到值为 " << val << " 的节点" << endl;
            return head;
        }
    }
    
    CircularNode* current = head;
    CircularNode* prev = nullptr;
    
    // 查找要删除的节点
    do {
        prev = current;
        current = current->next;
        if (current->data == val) {
            prev->next = current->next;
            
            // 如果删除的是头节点（当前head的下一个节点）
            if (current == head->next && head->data == val) {
                head->data = current->data;
                head->next = current->next;
            }
            
            // 如果删除的是尾节点（head本身）
            if (current == head) {
                head = prev;
            }
            
            delete current;  // 使用delete替代free
            return head;
        }
    } while (current != head);
    
    cout << "未找到值为 " << val << " 的节点" << endl;
    return head;
}

// 查找节点是否存在
bool searchCircularNode(CircularNode* head, int val) {
    if (isCircularListEmpty(head)) {
        return false;
    }
    
    CircularNode* current = head;
    do {
        if (current->data == val) {
            return true;
        }
        current = current->next;
    } while (current != head);
    
    return false;
}

// 修改指定值为新值
bool modifyCircularNode(CircularNode* head, int oldVal, int newVal) {
    if (isCircularListEmpty(head)) {
        return false;
    }
    
    CircularNode* current = head;
    do {
        if (current->data == oldVal) {
            current->data = newVal;
            return true;
        }
        current = current->next;
    } while (current != head);
    
    return false;
}

// 遍历链表
void traverseCircularList(CircularNode* head) {
    if (isCircularListEmpty(head)) {
        cout << "链表为空" << endl;
        return;
    }
    
    CircularNode* current = head;
    do {
        cout << current->data << " -> ";
        current = current->next;
    } while (current != head);
    cout << "(回到头部)" << endl;
}

// 清空链表
CircularNode* clearCircularList(CircularNode* head) {
    if (isCircularListEmpty(head)) {
        return nullptr;
    }
    
    CircularNode* current = head->next;
    while (current != head) {
        CircularNode* next = current->next;
        delete current;  // 使用delete替代free
        current = next;
    }
    
    delete head;  // 使用delete替代free
    return nullptr;
}

// 测试函数
int main() {
    // 测试单向链表
    cout << "=== 测试单向链表 ===" << endl;
    SinglyNode* sll = initSinglyLinkedList();
    sll = insertSinglyAtHead(sll, 1);
    sll = insertSinglyAtTail(sll, 3);
    sll = insertSinglyAtPosition(sll, 1, 2);
    traverseSinglyList(sll);  // 1 -> 2 -> 3 -> nullptr
    cout << "查找 2: " << (searchSinglyNode(sll, 2) ? "找到" : "未找到") << endl;
    modifySinglyNode(sll, 2, 5);
    traverseSinglyList(sll);  // 1 -> 5 -> 3 -> nullptr
    sll = deleteSinglyByValue(sll, 5);
    traverseSinglyList(sll);  // 1 -> 3 -> nullptr
    cout << "单向链表长度: " << getSinglyListLength(sll) << endl;
    sll = clearSinglyList(sll);
    
    // 测试双向链表
    cout << "\n=== 测试双向链表 ===" << endl;
    DoublyNode* dll = initDoublyLinkedList();
    dll = insertDoublyAtHead(dll, 1);
    dll = insertDoublyAtTail(dll, 3);
    dll = insertDoublyAtPosition(dll, 1, 2);
    traverseDoublyForward(dll);  // 1 <-> 2 <-> 3 <-> nullptr
    traverseDoublyBackward(dll); // 3 <-> 2 <-> 1 <-> nullptr
    cout << "查找 2: " << (searchDoublyNode(dll, 2) ? "找到" : "未找到") << endl;
    modifyDoublyNode(dll, 2, 5);
    traverseDoublyForward(dll);  // 1 <-> 5 <-> 3 <-> nullptr
    dll = deleteDoublyByValue(dll, 5);
    traverseDoublyForward(dll);  // 1 <-> 3 <-> nullptr
    cout << "双向链表长度: " << getDoublyListLength(dll) << endl;
    dll = clearDoublyList(dll);
    
    // 测试循环链表
    cout << "\n=== 测试循环链表 ===" << endl;
    CircularNode* cll = initCircularLinkedList();
    cll = insertCircularAtHead(cll, 1);
    cll = insertCircularAtTail(cll, 3);
    cll = insertCircularAtPosition(cll, 1, 2);
    traverseCircularList(cll);  // 1 -> 2 -> 3 -> (回到头部)
    cout << "查找 2: " << (searchCircularNode(cll, 2) ? "找到" : "未找到") << endl;
    modifyCircularNode(cll, 2, 5);
    traverseCircularList(cll);  // 1 -> 5 -> 3 -> (回到头部)
    cll = deleteCircularByValue(cll, 5);
    traverseCircularList(cll);  // 1 -> 3 -> (回到头部)
    cout << "循环链表长度: " << getCircularListLength(cll) << endl;
    cll = clearCircularList(cll);
    
    return 0;
}

admin

[C++] 纯文本查看 复制代码

#include<iostream>
using namespace std;
#define ElemType int
  
//************************单链表的存储结构********************
typedef struct LNode
{
    ElemType data;//结点的数据域
    struct LNode* next;//结点的指针域
}LNode, * LinkList;//LinkList为指向结构体LNode的指针类型
  
//***********************单链表的基本操作函数******************
  
//单链表的初始化
void InitList(LinkList& L)
{
    //构造一个空的单链表
    L = new LNode;
    L->next = NULL;
}
//单链表的创建
void CreateList_H(LinkList& L)//前插法创建单链表
{
    //创建一个长度为n的单链表L,逆序位插入
    int n;
    LNode* p;
    cout << "请输入创建的单链表长度：" << endl;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        p = new LNode;
        cout << "请输入插入的第" << i + 1 << "个数据值" << endl;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}
  
void CreateList_R(LinkList& L)//后插法创建单链表
{
    //创建一个长度为n的单链表L,正序位插入
    int n;
    LNode* p, * r;
    r = L;//尾指针r指向头结点
    cout << "请输入创建的单链表长度：" << endl;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        p = new LNode;
        cout << "请输入插入的第" << i + 1 << "个数据值" << endl;
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}
  
//单链表的插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
    //在带头结点的单链表L的第i个结点前插入新结点
    LinkList p = L;
    LNode* s;
    int j = 0;
    while (p && j < i - 1)//p指向第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (!p || i < 1)//i大于表长+1或小于1，插入位置不合法
    {
        return false;
    }
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
  
//单链表的删除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
    //将单链表的第i个结点删除
    LinkList p = L;
    LNode* q;
    int j = 0;
    while (p->next && j < i - 1)//p指向第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (!(p->next) || i < 1)//i大于表长或小于1，删除位置不合法
    {
        return false;
    }
    q = p->next;//临时保存被删结点的地址以备释放
    p->next = q->next;
    e = q->data;//保存被删结点的数据
    delete q;//释放被删结点的空间
    return true;
}
  
//单链表的取值
bool GetElem(LinkList L, int i, ElemType& e)
{
    //获取单链表中第i个结点的数据
    LinkList p = L;
    int j = 0;
    while (p->next && j < i - 1)//p指向第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (!(p->next) || i < 1)//i大于表长或小于1，第i个结点不存在
    {
        return false;
    }
    e = p->next->data;//获取第i个结点的数据
    return true;
}
  
//单链表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
    //在单链表中查找第一个数据为e的结点
    p = L->next;//p指向首元结点
    while (p && p->data != e)
    {
        p = p->next;
    }
    if (p)
    {
        return true;
    }
    return false;
}
  
//*********************************单链表的基本功能函数******************************
  
//1、插入
void ListInsert(LinkList& L)
{
  
    ElemType e;
    int i;
    bool flag;
    cout << "请输入要插入的数据：" << endl;
    cin >> e;
    cout << "请输入要插入的位置：" << endl;
    cin >> i;
    flag = ListInsert(L, i, e);
    if (flag)
        cout << "插入成功!" << endl;
    else
        cout << "位置不对，插入失败！" << endl;
}
  
//2、删除
void ListDelete(LinkList& L)
{
    ElemType e;
    int i;
    bool flag;
    cout << "请输入要删除数据的位置：" << endl;
    cin >> i;
    flag = ListDelete(L, i, e);
    if (flag)
        cout << "删除成功，删除的数据为：" << e << endl;
    else
        cout << "位置不对，删除失败！" << endl;
}
  
//3、取值
void GetElem(LinkList L)
{
    ElemType e;
    int i;
    bool flag;
    cout << "请输入要获取数据的位置：" << endl;
    cin >> i;
    flag = GetElem(L, i, e);
    if (flag)
        cout << "获取的数据为：" << e << endl;
    else
        cout << "位置不对，获取数据失败！" << endl;
}
  
//4、查找
void LocateElem(LinkList L)
{
    ElemType e;
    LNode* p = NULL;
    bool flag;
    cout << "请输入要查找的数据：" << endl;
    cin >> e;
    flag = LocateElem(L, p, e);
    if (flag)
        cout << "查找成功，该数据的地址为：" << p << endl;
    else
        cout << "查找失败！" << endl;
}
  
//5、判空
void ListEmpty(LinkList L)
{
    if (L->next)
        cout << "链表不为空！" << endl;
    else
        cout << "链表为空！" << endl;
}
  
//6、求长
void ListLength(LinkList L)
{
    LinkList p = L->next;//p指向第一个结点
    int i = 0;
    while (p)//遍历单链表，统计结点数
    {
        i++;
        p = p->next;
    }
    cout << "链表的长度为：" << i << endl;
}
  
//7、清空
void ClearList(LinkList& L)
{
    LNode* p, * q;
    p = L->next;
    while (p)//从首元结点开始，依次删除
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;//头结点指针域置空
}
  
//8、销毁
void DestroyList(LinkList& L)
{
    LNode* p;
    while (L)//从头结点开始依次删除
    {
        p = L;
        L = L->next;
        delete p;
    }
}
  
//9、打印
void PrintList(LinkList L)
{
    LinkList p = L->next;//p指向第一个结点
    int i = 0;
    while (p)//遍历单链表
    {
        i++;
        cout << "链表第" << i << "个数据为：" << p->data << endl;
        p = p->next;
    }
}
  
//菜单
void menu()
{
    cout << "***************************************************************************" << endl;
    cout << "***********************************1、插入*********************************" << endl;
    cout << "***********************************2、删除*********************************" << endl;
    cout << "***********************************3、取值*********************************" << endl;
    cout << "***********************************4、查找*********************************" << endl;
    cout << "***********************************5、判空*********************************" << endl;
    cout << "***********************************6、求长*********************************" << endl;
    cout << "***********************************7、清空*********************************" << endl;
    cout << "***********************************8、销毁*********************************" << endl;
    cout << "***********************************9、打印*********************************" << endl;
    cout << "***********************************0、退出*********************************" << endl;
    cout << "***************************************************************************" << endl;
}
  
int main()
{
    LinkList L;
    InitList(L);
    int select;
    cout << "请先创建单链表：1、前插法！  2、后插法！" << endl;
    cin >> select;
    switch (select)
    {
    case 1://插入
        CreateList_H(L);
        system("pause");//按任意键继续
        break;
    case 2://删除
        CreateList_R(L);
        system("pause");
        break;
    default:
        cout << "输入有误,创建失败！" << endl;
        system("pause");
        break;
    }
    while (1)
    {
        system("CLS");//清屏操作
        menu();
        cout << "请输入菜单序号：" << endl;
        cin >> select;
        switch (select)
        {
        case 1://插入
            ListInsert(L);
            system("pause");//按任意键继续
            break;
        case 2://删除
            ListDelete(L);
            system("pause");
            break;
        case 3://取值
            GetElem(L);
            system("pause");
            break;
        case 4://查找
            LocateElem(L);
            system("pause");
            break;
        case 5://判断链表是否为空
            ListEmpty(L);
            system("pause");
            break;
        case 6://求单链表的长度
            ListLength(L);
            system("pause");
            break;
        case 7://清空
            ClearList(L);
            system("pause");
            break;
        case 8://销毁
            DestroyList(L);
            system("pause");
            return 0;
            break;
        case 9://打印
            PrintList(L);
            system("pause");
            break;
        case 0:
            cout << "欢迎下次使用!" << endl;//退出
            system("pause");
            return 0;
            break;
        default:
            cout << "菜单序号输入有误！" << endl;
            system("pause");
            break;
        }
    }
    system("pause");
    return 0;
}