【数据结构C/C++】单向链表的增删改查

「爱情、让人受尽委屈。」 2024-02-24 02:54 50阅读 0赞

#### 文章目录 ####

*  C
 *  C++
 *  408考研各数据结构C/C++代码（Continually updating）

单向链表是比较常用的数据结构，最近再面试手撕算法的时候偶尔有遇到，所以就花了一点时间简单的写了一下C/C++版本的单向链表的代码。  
这里我推荐使用C++版本，因为C++版本我特地优化了一下，提供了用户输入的功能，当然两个语言差异不大，注释可以直接看C版本的，比较容易理解。  
对于这种比较容易理解的数据机构我就不会再次附上我对这个结构的理解了，  
直接show u my code。

## C ##

#include <stdio.h>
    #include <stdlib.h>
    
    // 定义链表节点结构
    struct Node {
        
        int data;
        struct Node* next;
    };
    
    // 初始化链表
    struct Node* initializeList() {
        
        return NULL; // 返回一个空链表
    }
    
    // 在链表尾部插入节点
    struct Node* insertAtEnd(struct Node* head, int data) {
        
        //先申请并开辟空间
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->next = NULL;
    
        if (head == NULL) {
        
            return newNode; // 如果链表为空，新节点成为链表头
        }
    
        struct Node* current = head;
        while (current->next != NULL) {
        
            current = current->next; // 移动到链表末尾
        }
    
        current->next = newNode;
        return head;
    }
    
    // 在链表头部插入节点
    struct Node* insertAtBeginning(struct Node* head, int data) {
        
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->next = head;
        return newNode; // 新节点成为链表头
    }
    
    // 删除节点
    struct Node* deleteNode(struct Node* head, int data) {
        
        if (head == NULL) {
        
            return NULL; // 空链表，无需删除
        }
        //要删除的数据就是链表头节点
        if (head->data == data) {
        
            struct Node* temp = head;
            head = head->next;
            free(temp);
            return head; // 删除链表头节点
        }
        //要删除的数据不是链表头节点 从链表头下一个结点开始寻找要删除的数据
        struct Node* current = head;
        while (current->next != NULL && current->next->data != data) {
        
            current = current->next;
        }
        //停止时存在条件1：没有找到要删除的 2：cur-next-data是要删除的数据
        if (current->next != NULL) {
        
            struct Node* temp = current->next; //temp就是要删除的数据
            current->next = current->next->next;
            free(temp); // 删除中间或末尾节点
        }
    
        return head;
    }
    
    // 查找节点
    struct Node* searchNode(struct Node* head, int data) {
        
        struct Node* current = head;
        while (current != NULL) {
        
            if (current->data == data) {
        
                return current; // 找到匹配的节点
            }
            current = current->next;
        }
        return NULL; // 未找到匹配的节点
    }
    
    // 修改节点的数据
    void modifyNode(struct Node* head, int oldData, int newData) {
        
        struct Node* nodeToModify = searchNode(head, oldData);
        if (nodeToModify != NULL) {
        
            nodeToModify->data = newData; // 修改节点的数据
        }
    }
    
    // 打印链表
    void printList(struct Node* head) {
        
        struct Node* current = head;
        while (current != NULL) {
        
            printf("%d -> ", current->data);
            current = current->next;
        }
        printf("NULL\n");
    }
    
    // 释放链表内存
    void freeList(struct Node* head) {
        
        struct Node* current = head;
        while (current != NULL) {
        
            struct Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
    
    int main() {
        
        struct Node* list = initializeList();
    
        list = insertAtEnd(list, 10);
        list = insertAtEnd(list, 20);
        list = insertAtBeginning(list, 5);
    
        printf("Original List: ");
        printList(list);
    
        modifyNode(list, 20, 25);
        printf("Modified List: ");
        printList(list);
    
        list = deleteNode(list, 10);
        printf("List after deleting 10: ");
        printList(list);
    
        struct Node* foundNode = searchNode(list, 5);
        if (foundNode != NULL) {
        
            printf("Found node with data 5\n");
        } else {
        
            printf("Node with data 5 not found\n");
        }
    
        freeList(list); // 释放链表内存
    
        return 0;
    }

## C++ ##

#include <iostream>
    
    class Node {
        
    public:
        int data;
        Node* next;
    
        Node(int val) : data(val), next(nullptr) {
        }
    };
    
    class LinkedList {
        
    public:
        Node* head;
    
        LinkedList() : head(nullptr) {
        }
    
        // 插入节点到链表尾部
        void insertAtEnd(int val) {
        
            Node* newNode = new Node(val);
            if (head == nullptr) {
        
                head = newNode;
            } else {
        
                Node* current = head;
                while (current->next != nullptr) {
        
                    current = current->next;
                }
                current->next = newNode;
            }
        }
    
        // 删除节点
        void deleteNode(int val) {
        
            if (head == nullptr) {
        
                return; // 空链表，无需删除
            }
    
            if (head->data == val) {
        
                Node* temp = head;
                head = head->next;
                delete temp;
                return;
            }
    
            Node* current = head;
            while (current->next != nullptr && current->next->data != val) {
        
                current = current->next;
            }
    
            if (current->next != nullptr) {
        
                Node* temp = current->next;
                current->next = current->next->next;
                delete temp;
            }
        }
    
        // 查找节点
        Node* searchNode(int val) {
        
            Node* current = head;
            while (current != nullptr) {
        
                if (current->data == val) {
        
                    return current; // 找到匹配的节点
                }
                current = current->next;
            }
            return nullptr; // 未找到匹配的节点
        }
    
        // 修改节点的数据
        void modifyNode(int oldVal, int newVal) {
        
            Node* nodeToModify = searchNode(oldVal);
            if (nodeToModify != nullptr) {
        
                nodeToModify->data = newVal; // 修改节点的数据
            }
        }
    
        // 打印链表
        void printList() {
        
            Node* current = head;
            while (current != nullptr) {
        
                std::cout << current->data << " -> ";
                current = current->next;
            }
            std::cout << "nullptr" << std::endl;
        }
    
        // 释放链表内存
        ~LinkedList() {
        
            Node* current = head;
            while (current != nullptr) {
        
                Node* temp = current;
                current = current->next;
                delete temp;
            }
        }
    };
    
    int main() {
        
        LinkedList list;
        int choice, data, oldData, newData;
    
        while (true) {
        
            std::cout << "\nMenu:\n";
            std::cout << "1. Insert at the end\n";
            std::cout << "2. Delete node\n";
            std::cout << "3. Search node\n";
            std::cout << "4. Modify node\n";
            std::cout << "5. Print list\n";
            std::cout << "6. Exit\n";
            std::cout << "Enter your choice: ";
            std::cin >> choice;
    
            switch (choice) {
        
                case 1:
                    std::cout << "Enter data to insert: ";
                    std::cin >> data;
                    list.insertAtEnd(data);
                    break;
                case 2:
                    std::cout << "Enter data to delete: ";
                    std::cin >> data;
                    list.deleteNode(data);
                    break;
                case 3:
                    std::cout << "Enter data to search: ";
                    std::cin >> data;
                    if (list.searchNode(data) != nullptr) {
        
                        std::cout << "Found node with data " << data << std::endl;
                    } else {
        
                        std::cout << "Node with data " << data << " not found" << std::endl;
                    }
                    break;
                case 4:
                    std::cout << "Enter data to modify: ";
                    std::cin >> oldData;
                    std::cout << "Enter new data: ";
                    std::cin >> newData;
                    list.modifyNode(oldData, newData);
                    break;
                case 5:
                    std::cout << "List: ";
                    list.printList();
                    break;
                case 6:
                    return 0;
                default:
                    std::cout << "Invalid choice! Please try again." << std::endl;
            }
        }
    
        return 0;
    }

## 408考研各数据结构C/C++代码（Continually updating） ##

[ 408考研各数据结构C/C++代码（Continually updating）][408_C_C_Continually updating]  
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。  
目前我比较熟悉的数据结构如下：  
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。  
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。

[408_C_C_Continually updating]: https://blog.csdn.net/Zhangsama1/article/details/133676491?spm=1001.2014.3001.5502