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

C语言---链表

news 2025/4/25 19:08:36

一、引言

二、链表的基本概念

三、链表的实现

1.结点定义

2.创建链表

3.遍历链表

4.插入结点

5.删除结点

四、总结

本文将带领大家详细了解C语言中链表的概念、原理以及如何实现链表的各种操作。通过本文的学习，相信大家会对C语言链表有一个更加清晰的认识。

一、引言

在C语言中，链表是一种常用的数据结构，它由一系列结点组成，每个结点包含数据域和指针域。链表相较于数组，具有动态扩展、插入删除操作高效等优点。本文将围绕链表的基本概念、实现及操作进行讲解。

二、链表的基本概念

结点：链表中的每个元素称为结点，每个结点包含两部分：数据域和指针域。
头指针：指向链表第一个结点的指针。
尾指针：指向链表最后一个结点的指针。
空链表：头指针为NULL的链表。

三、链表的实现

1.结点定义

首先，我们需要定义一个结点结构体：

typedef struct Node {int data;          // 数据域struct Node* next; // 指针域
} Node;

2.创建链表

创建链表的方法有很多种，这里我们以头插法为例：

Node* createList() {Node* head = (Node*)malloc(sizeof(Node)); // 创建头结点head->next = NULL;                         // 初始化头结点指针域int data;while (scanf("%d", &data) != EOF) {Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新结点newNode->data = data;                         // 设置新结点数据域newNode->next = head->next;                   // 新结点指向原链表的第一个结点head->next = newNode;                         // 头结点指向新结点}return head;
}

3.遍历链表

void traverseList(Node* head) {Node* p = head->next; // 从第一个结点开始遍历while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");
}

4.插入结点

以下是在链表中第i个位置插入新结点的操作：

void insertNode(Node* head, int i, int data) {Node* p = head;int j = 0;while (p != NULL && j < i - 1) { // 找到第i-1个结点p = p->next;j++;}if (p == NULL || j > i - 1) {printf("插入位置不合法\n");return;}Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新结点newNode->data = data;newNode->next = p->next; // 新结点指向第i个结点p->next = newNode;       // 第i-1个结点指向新结点
}

5.删除结点

以下是在链表中删除第i个结点的操作：

void deleteNode(Node* head, int i) {Node* p = head;int j = 0;while (p->next != NULL && j < i - 1) { // 找到第i-1个结点p = p->next;j++;}if (p->next == NULL || j > i - 1) {printf("删除位置不合法\n");return;}Node* q = p->next; // q指向第i个结点p->next = q->next; // 第i-1个结点指向第i+1个结点free(q);           // 释放第i个结点的内存
}