c语言建立带头结点的单链表

C语言建立带头结点的单链表

下面是一个完整的C语言实现,展示如何建立带头结点的单链表：

#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;
// 创建头结点
Node* createHeadNode() {
    Node *head = (Node*)malloc(sizeof(Node));
    if (head == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    head->next = NULL;  // 头结点的next指针初始为NULL
    return head;
}
// 在链表尾部插入节点
void insertAtTail(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    // 找到链表最后一个节点
    Node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    // 将新节点链接到链表末尾
    current->next = newNode;
}
// 打印链表
void printList(Node *head) {
    Node *current = head->next;  // 跳过头结点
    printf("链表内容: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
// 释放链表内存
void freeList(Node *head) {
    Node *current = head;
    Node *next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}
int main() {
    // 创建头结点
    Node *head = createHeadNode();
    // 插入数据
    insertAtTail(head, 10);
    insertAtTail(head, 20);
    insertAtTail(head, 30);
    insertAtTail(head, 40);
    // 打印链表
    printList(head);
    // 释放内存
    freeList(head);
    return 0;
}

代码说明

1. 节点结构定义：

   • 使用struct Node定义链表节点，包含数据域data和指向下一个节点的指针next

2. 创建头结点：

   • createHeadNode()函数动态分配内存创建头结点
   • 头结点的next指针初始化为NULL

3. 尾部插入节点：

   • insertAtTail()函数在链表尾部插入新节点
   • 首先找到链表最后一个节点，然后将新节点链接到它后面

4. 打印链表：

   
   （图片来源网络，侵删）
   • printList()函数从头结点的下一个节点开始遍历并打印数据

5. 内存释放：

   • freeList()函数释放整个链表（包括头结点）的内存

其他插入方式

除了尾部插入,还可以实现头部插入：

// 在链表头部插入节点
void insertAtHead(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = head->next;  // 新节点指向原第一个节点
    head->next = newNode;        // 头结点指向新节点
}

带头结点的单链表有以下优点：

1. 插入和删除操作不需要特殊处理头结点的情况
2. 所有节点的操作可以统一处理
3. 空链表和非空链表的处理方式一致

这个实现展示了链表的基本操作，可以根据需要扩展更多功能，如按位置插入、删除节点、查找节点等。