C语言链表基础教程：创建、插入、删除及排序

### C语言链表初步 #### 一、链表的概念 链表是一种常见的基础数据结构，具有动态、灵活的特点。链表中的元素在内存中不必连续存放，每一个元素由一个存储数据本身的节点和一个指向下一个元素地址的指针（或引用）组成。链表通过指针将一系列零散的内存块串联起来，形成一个链式结构。 #### 二、链表的特点 1. **动态性：** 链表的长度可以动态增减，不需要像数组一样预先定义大小。 2. **灵活分配：** 内存中可以是非连续的空间，克服了数组的局限。 3. **访问效率低：** 需要从头遍历链表，才能找到特定的元素，平均查找时间为O(n)。 4. **插入、删除效率高：** 只需改变指针的指向，不需要移动元素，时间复杂度为O(1)。 #### 三、链表的类型 1. **单向链表（单链表）：** 每个节点只有一个指针域，指向下一个节点。 2. **双向链表（双链表）：** 每个节点有两个指针域，分别指向前一个节点和后一个节点。 3. **循环链表：** 尾节点的指针域指向头节点，形成一个环形结构。 #### 四、链表的基本操作 1. **创建链表：** 初始化链表，通常包含一个头指针，指向第一个节点，第一个节点称为头节点，头节点不存有效数据。 2. **插入操作：** 在链表的任意位置插入一个新的节点，需要修改相邻节点的指针域。 3. **删除操作：** 删除链表中指定的节点，修改相邻节点的指针域，释放目标节点的内存。 4. **遍历链表：** 从头节点开始，通过指针依次访问链表中的每个节点。 5. **查找节点：** 根据特定的条件（如值）在链表中查找节点。 6. **判断是否为空链表：** 检查链表是否含有任何节点，即头指针是否为NULL。 7. **销毁链表：** 释放链表所占用的内存，一般从链表尾部开始逐个删除节点。 #### 五、链表操作的C语言实现 以下是一个简单的C语言单向链表实现的例子： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { int data; struct Node* next; } Node; // 创建链表节点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if(newNode == NULL) { exit(-1); } newNode->data = data; newNode->next = NULL; return newNode; } // 在链表头部插入节点 void insertAtHead(Node** head, int data) { Node* newNode = createNode(data); newNode->next = *head; *head = newNode; } // 在链表尾部插入节点 void insertAtTail(Node** head, int data) { Node* newNode = createNode(data); if(*head == NULL) { *head = newNode; return; } Node* current = *head; while(current->next != NULL) { current = current->next; } current->next = newNode; } // 删除链表中的节点 void deleteNode(Node** head, int key) { Node* temp = *head, *prev = NULL; if (temp != NULL && temp->data == key) { *head = temp->next; free(temp); return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; free(temp); } // 快速排序链表 void quickSort(Node** head) { // 这里省略快速排序链表的实现细节 } // 判断链表是否为空 int isEmpty(Node* head) { return head == NULL; } // 打印链表 void printList(Node* node) { while(node != NULL) { printf("%d ", node->data); node = node->next; } } // 主函数 int main() { Node* head = NULL; insertAtHead(&head, 10); insertAtHead(&head, 20); insertAtTail(&head, 30); insertAtTail(&head, 40); printList(head); deleteNode(&head, 20); printf("\nAfter deleting 20:\n"); printList(head); return 0; } ``` #### 六、快速排序在链表上的实现 快速排序是一种分而治之的排序算法，在数组上效率较高，但在链表上实现时需要特殊处理指针。由于链表的节点是分散存储的，不能像数组那样随机访问，因此需要对快速排序算法进行调整，使其能够适用于链表。 #### 七、链表操作的注意事项 1. **内存管理：** 在使用链表时要注意内存的申请和释放，避免内存泄漏。 2. **指针操作：** 链表操作中对指针的修改要格外小心，错误的操作可能导致指针悬挂或内存访问违规。 3. **算法效率：** 链表的插入和删除操作效率较高，但频繁的动态内存分配和释放会影响性能。 4. **边界条件：** 在操作链表时要注意边界条件，例如对空链表的操作，或是在链表尾部进行插入。 以上知识点和代码示例为初学者提供了C语言链表的基本理解和实践操作，为学习更高级的数据结构和算法打下基础。