C语言深入探索之单链表与typedef的用法

介绍

在数据结构中，链表是一种非常基础且重要的数据结构。C语言中使用指针和结构体可以非常方便的实现链表的基本操作。此外，typedef是C语言中类型定义的关键字，可以为已有的数据类型重新定义名称，增加代码的可读性。

本篇文章将着重讲解使用C语言实现单链表的基本操作，并结合typedef给链表节点和链表本身定义更易于理解的名称。

单链表的基本操作

单链表是一种链式存储结构，它通过每个节点上的指针链接起来构成一个链表。在C语言中，用结构体表示链表节点，用指针实现链表节点的链接。

链表节点结构体

在C语言中，链表节点可以使用结构体来表示。链表节点通常包含两个元素，一个是值(value)，另一个是指向下一个节点的指针(next)。

struct ListNode {
    int value;
    struct ListNode *next;
};

链表的基本操作

链表的基本操作包括插入节点、删除节点和遍历链表。

插入节点

需要插入一个节点时，只需要将新节点的next指针指向当前节点的下一个节点，再将当前节点的next指针指向新节点即可。

void insertNode(struct ListNode *currentNode, struct ListNode *newNode) {
    newNode->next = currentNode->next;
    currentNode->next = newNode;
}

删除节点

删除节点时，只需要找到要删除的节点的前一个节点，将其next指针指向要删除节点的后一个节点即可。

void deleteNode(struct ListNode *currentNode) {
    struct ListNode *temp = currentNode->next;
    currentNode->next = currentNode->next->next;
    free(temp);
}

遍历链表

遍历链表时，只需要从头节点开始，依次访问每个节点的值即可。

void traverseList(struct ListNode *head) {
    struct ListNode *currentNode = head->next;
    while (currentNode != NULL) {
        printf("%d ", currentNode->value);
        currentNode = currentNode->next;
    }
}

示例说明

以下示例演示了如何使用链表实现逆序输出一个整数数组。

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

struct ListNode {
    int value;
    struct ListNode *next;
};

void insertNode(struct ListNode *currentNode, struct ListNode *newNode) {
    newNode->next = currentNode->next;
    currentNode->next = newNode;
}

void deleteNode(struct ListNode *currentNode) {
    struct ListNode *temp = currentNode->next;
    currentNode->next = currentNode->next->next;
    free(temp);
}

void traverseList(struct ListNode *head) {
    struct ListNode *currentNode = head->next;
    while (currentNode != NULL) {
        printf("%d ", currentNode->value);
        currentNode = currentNode->next;
    }
}

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    struct ListNode *head = (struct ListNode *) malloc(sizeof(struct ListNode));
    struct ListNode *currentNode = head;
    int i;
    for (i = 0; i < 5; i++) {
        struct ListNode *newNode = (struct ListNode *) malloc(sizeof(struct ListNode));
        newNode->value = array[i];
        insertNode(currentNode, newNode);
        currentNode = newNode;
    }
    traverseList(head);

    struct ListNode *p = head->next;
    head->next = NULL;
    while (p != NULL) {
        struct ListNode *temp = p;
        p = p->next;
        insertNode(head, temp);
    }
    traverseList(head);
}

输出结果为:

5 4 3 2 1 
1 2 3 4 5 

typedef的用法

typedef是C语言中类型定义的关键字，可以为已有的数据类型重新定义名称，增加代码的可读性。

为链表节点定义名称

在调用链表操作时，经常需要使用struct ListNode类型的变量。为了增加代码的可读性，我们可以使用typedef重新定义一个更加易于理解的名称list_node_t。

typedef struct ListNode list_node_t;

在定义链表节点的变量时，可以使用新定义的名称。

list_node_t *head = (list_node_t *) malloc(sizeof(list_node_t));

为链表本身定义名称

在调用链表操作时，也经常需要使用struct ListNode类型的指针变量。为了增加代码的可读性，我们可以使用typedef重新定义一个更加易于理解的名称list_t。

typedef struct ListNode *list_t;

在定义链表变量时，可以使用新定义的名称。

list_t head = (list_t) malloc (sizeof(struct ListNode));

示例说明

以下示例演示了如何使用typedef为链表节点和链表本身定义新名称。

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

typedef struct ListNode {
    int value;
    struct ListNode *next;
} list_node_t;

typedef struct ListNode *list_t;

void insertNode(list_t head, list_node_t *newNode) {
    newNode->next = head->next;
    head->next = newNode;
}

void deleteNode(list_t head, list_node_t *currentNode) {
    list_node_t *temp = currentNode->next;
    currentNode->next = currentNode->next->next;
    free(temp);
}

void traverseList(list_t head) {
    list_node_t *currentNode = head->next;
    while (currentNode != NULL) {
        printf("%d ", currentNode->value);
        currentNode = currentNode->next;
    }
}

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    list_t head = (list_t) malloc(sizeof(list_node_t));
    list_node_t *currentNode = head;
    int i;
    for (i = 0; i < 5; i++) {
        list_node_t *newNode = (list_node_t *) malloc(sizeof(list_node_t));
        newNode->value = array[i];
        insertNode(head, newNode);
        currentNode = newNode;
    }
    traverseList(head);

    list_node_t *p = head->next;
    head->next = NULL;
    while (p != NULL) {
        list_node_t *temp = p;
        p = p->next;
        insertNode(head, temp);
    }
    traverseList(head);
}

输出结果与前面的示例相同。