数据结构

单向链表的基本概念

单向链表（Singly Linked List） 是一种线性数据结构，其中每个元素（称为节点）包含两个部分：

  1. 数据域 (Data) ：存储实际的数据。
  2. 指针域 (Pointer/Link) ：指向下一个节点的引用。对于单向链表来说，这个指针通常称为“next”。

单向链表的基本操作

  1. 插入：在链表中添加一个新的节点。

    • 在头部插入
    • 在尾部插入
    • 在指定位置插入
  2. 删除：从链表中移除一个节点。
  3. 查找：找到链表中的某个节点。
  4. 遍历：访问链表中的所有节点。

单向链表的实现步骤

  1. 定义节点结构体 (Node)。
  2. 创建链表类或结构体，并定义头指针 (head)。
  3. 实现插入、删除、查找和遍历操作。

下面是一个完整的C语言代码示例，展示了如何实现单向链表：

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构体
typedef struct Node {
    int data;          // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 创建一个新的节点
Node* create_node(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// 在链表头部插入节点
void insert_at_head(Node** head, int data) {
    Node* new_node = create_node(data);
    new_node->next = *head;
    *head = new_node;
}

// 在链表尾部插入节点
void insert_at_tail(Node** head, int data) {
    Node* new_node = create_node(data);
    if (*head == NULL) {
        // 如果链表为空，新节点就是头节点
        *head = new_node;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
}

// 删除指定数据的节点
void delete_node(Node** head, int key) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = *head;
    // 如果头节点就是要删除的节点
    if (temp->data == key) {
        *head = temp->next;  // 将头指针指向下一个节点
        free(temp);
        return;
    }
    // 找到要删除的节点
    Node* prev = NULL;
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("未找到指定数据\n");
        return;
    }
    // 删除节点
    prev->next = temp->next;
    free(temp);
}

// 查找指定数据的节点
Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 遍历链表并打印每个节点的数据
void display(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 释放整个链表的内存
void free_list(Node** head) {
    Node* current = *head;
    Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

int main() {
    Node* head = NULL;  // 初始化头指针为NULL

    // 插入节点
    insert_at_head(&head, 30);
    insert_at_tail(&head, 40);
    insert_at_head(&head, 20);
    insert_at_tail(&head, 50);

    printf("链表内容: ");
    display(head);  // 输出: 20 -> 30 -> 40 -> 50 -> NULL

    // 删除节点
    delete_node(&head, 30);
    printf("删除节点30后链表内容: ");
    display(head);  // 输出: 20 -> 40 -> 50 -> NULL

    // 查找节点
    Node* found = search(head, 40);
    if (found) {
        printf("找到节点: %d\n", found->data);  // 输出: 找到节点: 40
    } else {
        printf("未找到节点\n");
    }

    // 释放链表内存
    free_list(&head);

    return 0;
}

代码解释

  1. 定义节点结构体:

    typedef struct Node {
    int data;          // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

  2. 创建一个新的节点:

    Node* create_node(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

  3. 在链表头部插入节点:

    void insert_at_head(Node** head, int data) {
    Node* new_node = create_node(data);
    new_node->next = *head;
    *head = new_node;
}

  4. 在链表尾部插入节点:

    void insert_at_tail(Node** head, int data) {
    Node* new_node = create_node(data);
    if (*head == NULL) {
        // 如果链表为空，新节点就是头节点
        *head = new_node;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
}

  5. 删除指定数据的节点:

    void delete_node(Node** head, int key) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = *head;
    // 如果头节点就是要删除的节点
    if (temp->data == key) {
        *head = temp->next;  // 将头指针指向下一个节点
        free(temp);
        return;
    }
    // 找到要删除的节点
    Node* prev = NULL;
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("未找到指定数据\n");
        return;
    }
    // 删除节点
    prev->next = temp->next;
    free(temp);
}

  6. 查找指定数据的节点:

    Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

  7. 遍历链表并打印每个节点的数据:

    void display(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

  8. 释放整个链表的内存:

    void free_list(Node** head) {
    Node* current = *head;
    Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

发表评论