博客

C语言实现单链表

  • Post category:C

C语言实现单链表使用攻略

1. 定义结构体

单链表的每个节点包含两个部分：数据域和指针域。我们需要定义一个结构体来表示单链表中的节点，结构体包含两个成员变量：数据域和指针域。

// 定义单链表的节点
typedef struct ListNode {
    int data;                // 数据域
    struct ListNode* next;   // 指针域，指向下一个节点
} ListNode;

2. 创建链表

创建一个单链表需要经过以下步骤：

  1. 定义一个指向链表头的指针，初始化为 NULL。
  2. 循环读入数据，每读入一个数据创建一个新的节点，并将新节点插入链表尾部。
  3. 返回链表头指针。

代码如下：

// 创建单链表
ListNode* createList() {
    ListNode* head = NULL;      // 定义链表头指针，初始化为 NULL
    ListNode* tail = NULL;      // 定义链表尾指针，初始化为 NULL
    int data;                   // 定义读入的数据
    while (scanf("%d", &data) != EOF) {   // 循环读入数据直到输入结束
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));   // 创建新节点
        node->data = data;                                      // 设置节点数据域
        node->next = NULL;                                      // 将新节点的指针域初始化为 NULL
        if (head == NULL) {     // 如果链表为空，将头指针指向新节点
            head = node;
            tail = head;
        } else {                // 如果链表不为空，将新节点插入到尾部
            tail->next = node;
            tail = node;
        }
    }
    return head;    // 返回链表头指针
}

3. 遍历链表

遍历链表需要循环访问链表中的每个节点，输出节点的数据域。

代码如下：

// 遍历链表，输出每个节点的数据域
void traverseList(ListNode* head) {
    ListNode* node = head;  // 从链表头开始遍历
    while (node != NULL) {
        printf("%d ", node->data);  // 输出节点数据域
        node = node->next;          // 将指针移动到下一个节点
    }
    printf("\n");
}

4. 插入节点

插入节点需要先找到插入位置的前一个节点，并将新节点插入到该节点后面。

代码如下：

// 在第pos个节点后插入一个新节点，新节点数据域为data
void insertNode(ListNode* head, int pos, int data) {
    ListNode* node = head;          // 从链表头开始遍历
    int i = 0;
    while (node != NULL && i < pos - 1) {  // 找到第pos个节点的前一个节点
        node = node->next;
        i++;
    }
    if (node == NULL || i > pos - 1) {     // 如果插入位置无效，返回错误
        printf("error: invalid insert position.\n");
        return;
    }
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));   // 创建新节点
    new_node->data = data;                                      // 设置新节点数据域
    new_node->next = node->next;                                // 将新节点插入到前一个节点后面
    node->next = new_node;
}

5. 删除节点

删除节点需要先找到要删除节点的前一个节点，并将前一个节点的指针域指向要删除节点的下一个节点。

代码如下：

// 删除第pos个节点
void deleteNode(ListNode* head, int pos) {
    ListNode* node = head;          // 从链表头开始遍历
    int i = 0;
    while (node != NULL && i < pos - 1) {  // 找到第pos个节点的前一个节点
        node = node->next;
        i++;
    }
    if (node == NULL || node->next == NULL || i > pos - 1) {   // 如果删除位置无效，返回错误
        printf("error: invalid delete position.\n");
        return;
    }
    ListNode* del_node = node->next;            // 要删除的节点
    node->next = del_node->next;                // 将前一个节点的指针域指向要删除节点的下一个节点
    free(del_node);                             // 释放要删除的节点
}

6. 示例

下面给出两个示例，分别演示了如何使用上述函数来创建链表、遍历链表、插入节点和删除节点。

示例1：创建链表、遍历链表

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

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

ListNode* createList() {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    int data;
    while (scanf("%d", &data) != EOF) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->data = data;
        node->next = NULL;
        if (head == NULL) {
            head = node;
            tail = head;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void traverseList(ListNode* head) {
    ListNode* node = head;
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main() {
    ListNode* head = createList();
    traverseList(head);
    return 0;
}

输入：

1 2 3 4 5

输出：

1 2 3 4 5

示例2：创建链表、遍历链表、插入节点、删除节点

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

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

ListNode* createList() {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    int data;
    while (scanf("%d", &data) != EOF) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->data = data;
        node->next = NULL;
        if (head == NULL) {
            head = node;
            tail = head;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void traverseList(ListNode* head) {
    ListNode* node = head;
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

void insertNode(ListNode* head, int pos, int data) {
    ListNode* node = head;
    int i = 0;
    while (node != NULL && i < pos - 1) {
        node = node->next;
        i++;
    }
    if (node == NULL || i > pos - 1) {
        printf("error: invalid insert position.\n");
        return;
    }
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->next = node->next;
    node->next = new_node;
}

void deleteNode(ListNode* head, int pos) {
    ListNode* node = head;
    int i = 0;
    while (node != NULL && i < pos - 1) {
        node = node->next;
        i++;
    }
    if (node == NULL || node->next == NULL || i > pos - 1) {
        printf("error: invalid delete position.\n");
        return;
    }
    ListNode* del_node = node->next;
    node->next = del_node->next;
    free(del_node);
}

int main() {
    ListNode* head = createList();
    traverseList(head);

    insertNode(head, 3, 6);
    traverseList(head);

    deleteNode(head, 2);
    traverseList(head);

    return 0;
}

输入：

1 2 3 4 5

输出：

1 2 3 4 5
1 2 3 6 4 5
1 2 6 4 5

以上就是 C 语言实现单链表的使用攻略，可以通过这些函数来创建、遍历、插入和删除单链表中的节点。

Tags: