C++实现链表操作：创建、删除、插入与排序

"C++中链表操作实例分析，涵盖了链表的基本概念、单向链表的图示、创建链表的函数以及链表的一些基本操作，如创建、删除、插入、输出和排序等。" 在C++中，链表是一种非连续存储的数据结构，与数组不同，它通过指针链接各个元素。链表允许动态地添加或删除节点，因为它们不需要预先分配固定数量的空间。链表由一系列节点组成，每个节点包含实际数据和一个指针，用于指向下一个节点。链表的起点是头指针，它指向链表的第一个节点，而最后一个节点的指针通常设为NULL，表示链表的结束。 单向链表是最简单的链表形式，只支持从头到尾的遍历。在图示中，空链表只有一个头指针head，指向NULL；非空链表则由多个节点p1, p2, ..., pn组成，每个节点的next指针指向其后的节点，直到最后一个节点的next指针为NULL。 创建单向链表的函数通常从头节点开始，然后逐个添加新的节点。以下是一个简单的创建n个节点的链表的函数示例： ```cpp #include "stdlib.h" #include "stdio.h" // 定义链表节点结构体 struct student { int num; // 学号 float score; // 分数 struct student* next; // 指向下一节点的指针 }; // 创建n个节点的链表 struct student* Create() { struct student* head; // 头节点 struct student* p1 = NULL; // 新节点的地址 struct student* p2 = NULL; // 最后一个节点的地址 n = 0; // 初始化节点总数为0 // 开辟头节点 p1 = (struct student*)malloc(LEN); if (p1 == NULL) { // 节点开辟失败处理 printf("\nCann’t create it, try it again in a moment!\n"); exit(1); // 结束程序 } p2 = p1; // 循环创建n-1个节点 for (int i = 1; i < n; i++) { p1->next = (struct student*)malloc(LEN); if (p1->next == NULL) { // 节点开辟失败处理 printf("\nCann’t create it, try it again in a moment!\n"); exit(1); } p1 = p1->next; p1->num = i; // 假设用i作为学号填充 p1->score = 0.0; // 初始化分数为0 p2 = p1; } p1->next = NULL; // 设置最后一个节点的next为NULL return head; } ``` 除了创建链表，链表的其他常见操作包括： 1. **删除节点**：根据给定的节点或节点值，找到并删除相应节点。 2. **插入节点**：可以在链表的开头、结尾或指定位置插入新节点。 3. **输出链表**：遍历链表并打印节点信息。 4. **排序链表**：可以通过选择排序、插入排序、冒泡排序等方法对链表中的元素进行排序。 5. **反序链表**：将链表的顺序反转，使原来的第一个节点变为最后一个，最后一个变为第一个。 这些操作都需要通过指针来遍历和修改链表结构。链表因其灵活性在许多算法和数据结构实现中都有广泛的应用，例如在搜索、排序、图形算法等场景。理解和熟练掌握链表的操作对于提升编程能力至关重要。