当前位置：首页 > article >正文

C语言：创建带头结点的动态链表：解析与实现

article 2025/2/1 14:43:22

创建带头结点的动态链表：解析与实现

在本博客中，我们将逐步解析一个C语言程序，该程序用于创建一个带头结点的动态链表。链表用于存储从键盘输入的学生高考总分，以任意负数作为输入结束标志。最终，程序返回链表的头指针，并在主函数中调用该功能。

代码目标

创建一个带头结点的动态链表。
从键盘输入一批学生的高考总分（以负数作为结束标志）。
返回链表的头指针。
在主函数中调用该功能并打印头指针。

代码实现

数据结构定义

struct node 
{
    int data;           // 存储学生高考总分
    struct node * next; // 指向下一个节点的指针
};
typedef struct node NODE; // 为struct node定义别名NODE

定义了一个结构体node，用于表示链表的节点。
每个节点包含两个成员：
- data：存储学生高考总分。
- next：指向下一个节点的指针。
使用typedef为struct node定义了别名NODE，方便后续代码中使用。

创建链表的函数

NODE *create()
{
    NODE *head, *p, *q; // 末节点指针p，新节点指针q
    int t;
    head = malloc(sizeof(NODE)); // 分配头结点内存
    p = head;                   // 初始化p为头结点

    while (1)
    {
        printf("输入整数（负数为结束）：");
        scanf("%d", &t); // 从键盘输入一个整数
        if (t < 0)
            break; // 如果输入为负数，结束输入

        q = malloc(sizeof(NODE)); // 分配新节点内存
        q->data = t;              // 将输入的整数存储到新节点的数据域
        p->next = q;              // 将新节点链接到链表末尾
        p = q;                    // 将p移动到新节点
    }
    p->next = NULL; // 将链表末尾的next指针设置为NULL
    return head;    // 返回头指针
}

头结点初始化：
- 使用malloc为头结点分配内存。
- 将p初始化为头结点，p用于跟踪链表的末尾。
循环输入数据：
- 使用while (1)循环不断从键盘输入数据。
- 如果输入的数为负数，使用break退出循环。
- 否则，为新节点分配内存，存储输入的数据，并将新节点链接到链表末尾。
链表结束：
- 将链表末尾节点的next指针设置为NULL，表示链表结束。
返回头指针：
- 返回头结点的指针head，作为链表的入口。

主函数

c复制

int main(void)
{
    NODE *h;
    h = create(); // 调用create函数创建链表
    printf("头指针%p\n", h); // 打印链表的头指针
    return 0;
}

在主函数中调用create函数，创建链表并获取头指针。
打印链表的头指针地址。

代码问题与修正

虽然代码实现了基本功能，但存在一些问题和潜在的改进点：

问题1：错误的链表链接

c复制

p->next = q->next;

这行代码是错误的，应该改为：

c复制

p->next = q;

原因：q->next在新节点q分配内存后未初始化，直接赋值会导致未定义行为。

修正后的代码

NODE *create()
{
    NODE *head, *p, *q; // 末节点指针p，新节点指针q
    int t;
    head = malloc(sizeof(NODE)); // 分配头结点内存
    p = head;                   // 初始化p为头结点

    while (1)
    {
        printf("输入整数（负数为结束）：");
        scanf("%d", &t); // 从键盘输入一个整数
        if (t < 0)
            break; // 如果输入为负数，结束输入

        q = malloc(sizeof(NODE)); // 分配新节点内存
        q->data = t;              // 将输入的整数存储到新节点的数据域
        p->next = q;              // 将新节点链接到链表末尾
        p = q;                    // 将p移动到新节点
    }
    p->next = NULL; // 将链表末尾的next指针设置为NULL
    return head;    // 返回头指针
}

问题2：未释放内存

在实际应用中，链表使用完毕后应释放分配的内存，避免内存泄漏。
可以在主函数中添加链表的遍历和释放操作。

完整的改进代码

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

struct node 
{
    int data;
    struct node * next;
};
typedef struct node NODE;

NODE *create()
{
    NODE *head, *p, *q; // 末节点指针p，新节点指针q
    int t;
    head = malloc(sizeof(NODE)); // 分配头结点内存
    p = head;                   // 初始化p为头结点

    while (1)
    {
        printf("输入整数（负数为结束）：");
        scanf("%d", &t); // 从键盘输入一个整数
        if (t < 0)
            break; // 如果输入为负数，结束输入

        q = malloc(sizeof(NODE)); // 分配新节点内存
        q->data = t;              // 将输入的整数存储到新节点的数据域
        p->next = q;              // 将新节点链接到链表末尾
        p = q;                    // 将p移动到新节点
    }
    p->next = NULL; // 将链表末尾的next指针设置为NULL
    return head;    // 返回头指针
}

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

int main(void)
{
    NODE *h;
    h = create(); // 调用create函数创建链表
    printf("头指针%p\n", h); // 打印链表的头指针

    // 释放链表内存
    free_list(h);
    return 0;
}