C语言计算链表长度的三种方法

创作时间:

作者:

@小白创作中心

C语言计算链表长度的三种方法

引用

来源

https://docs.pingcode.com/baike/1247523

在C语言中，链表是一种常用的数据结构。计算链表长度是链表操作中的基本任务之一。本文将重点介绍通过遍历链表的方法来计算链表长度。

一、遍历链表计算长度

遍历链表是一种常用且简单的方法。它的原理是从链表的头结点开始，通过一个循环逐一访问每一个结点，直到链表的末尾。每访问一个结点，计数器就加1，最终计数器的值就是链表的长度。

1.1、基本代码实现

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

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

// 函数声明
int getLength(Node* head);

int main() {
    // 创建链表
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = NULL;

    // 计算链表长度
    int length = getLength(head);
    printf("链表长度: %d\n", length);
    return 0;
}

// 计算链表长度的函数
int getLength(Node* head) {
    int length = 0;
    Node* current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

1.2、详细解释

上述代码中，首先定义了一个链表结点结构体Node，其中包含一个整型数据data和一个指向下一个结点的指针next。然后在main函数中，创建了一个简单的链表，包含两个结点。

函数getLength用于计算链表的长度。该函数接受链表的头结点作为参数，通过一个while循环遍历整个链表。在遍历过程中，每访问一个结点，计数器length加1，最终返回length的值。

二、递归计算链表长度

除了遍历链表的方法，还可以通过递归来计算链表的长度。递归方法的原理是：链表的长度等于第一个结点之后的链表长度加1。

2.1、递归代码实现

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

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

// 函数声明
int getLengthRecursively(Node* head);

int main() {
    // 创建链表
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = NULL;

    // 计算链表长度
    int length = getLengthRecursively(head);
    printf("链表长度: %d\n", length);
    return 0;
}

// 递归计算链表长度的函数
int getLengthRecursively(Node* head) {
    if (head == NULL) {
        return 0;
    } else {
        return 1 + getLengthRecursively(head->next);
    }
}

2.2、详细解释

在上面的代码中，函数getLengthRecursively是一个递归函数。它首先检查链表是否为空（即head是否为NULL）。如果链表为空，则返回0，否则返回1加上剩余链表的长度。

递归方法的优势在于代码简洁，但是它占用的栈空间较多，对于长链表可能会导致栈溢出。因此在实际应用中，需要根据具体情况选择合适的方法。

三、使用头结点存储链表长度

还有一种方法是使用头结点来存储链表的长度。每次对链表进行插入或删除操作时，更新头结点中的长度值。这种方法可以在O(1)时间内获取链表长度，但是需要在链表操作时维护长度值。

3.1、基本代码实现

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

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

typedef struct {
    Node* head;
    int length;
} LinkedList;

// 函数声明
void insertNode(LinkedList* list, int data);
int getLength(LinkedList* list);

int main() {
    // 创建链表
    LinkedList list;
    list.head = NULL;
    list.length = 0;

    // 插入结点
    insertNode(&list, 1);
    insertNode(&list, 2);

    // 计算链表长度
    int length = getLength(&list);
    printf("链表长度: %d\n", length);
    return 0;
}

// 插入结点的函数
void insertNode(LinkedList* list, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = list->head;
    list->head = newNode;
    list->length++;
}

// 获取链表长度的函数
int getLength(LinkedList* list) {
    return list->length;
}