已知带表头结点单链表的类型定义如下： typedef struct node{ ElemType element; ／/结点的数据域 struct node *link; //结点的指针域 }Node; Typedef struct headerList { Node *head; int n; }HeaderList; 参照程序2.8～程序2.14，编写程序，完成带表头结点单链表的初始化、查找、插人、删除、输出、撤销等操作。（编写代码，带注释）

以下是基于您提供的类型定义，完成带表头节点单链表的基本操作（初始化、查找、插入、删除、输出、撤销）。代码包含详细的注释以便理解。 ```c #include <stdio.h> #include <stdlib.h> // 定义结点结构体 typedef struct node { int element; // 结点的数据域 (假设 ElemType 为 int 类型) struct node *link; // 指向下一个结点的指针 } Node; // 定义带头结点的单链表结构体 typedef struct headerList { Node *head; // 表头指针 int n; // 链表长度 } HeaderList; // 初始化链表 void initList(HeaderList *list) { list->head = (Node *)malloc(sizeof(Node)); // 创建头结点 if (list->head == NULL) { // 内存分配失败处理 printf("内存不足！\n"); exit(-1); } list->head->link = NULL; // 初始为空链表 list->n = 0; // 长度置为0 } // 查找值等于key的第一个元素的位置索引（从1开始），未找到返回0 int findElement(const HeaderList *list, int key) { Node *p = list->head->link; // p指向第一个实际数据结点 int index = 1; while (p != NULL) { if (p->element == key) return index; // 找到目标 p = p->link; index++; } return 0; // 未找到则返回0 } // 插入新元素x到指定位置pos处（从1开始） bool insertElement(HeaderList *list, int x, int pos) { if (pos <= 0 || pos > list->n + 1) return false; // 检查合法性 Node *newNode = (Node *)malloc(sizeof(Node)); newNode->element = x; Node *pre = list->head; // pre始终位于待插入位置之前 for (int i = 1; i < pos; ++i) pre = pre->link; newNode->link = pre->link; // 修改链接关系 pre->link = newNode; list->n++; // 更新长度 return true; } // 删除第pos个位置的元素，并返回其值；若删除失败，则返回INT_MIN作为标志值 int deleteElement(HeaderList *list, int pos) { if (pos <= 0 || pos > list->n) return INT_MIN; // 参数非法 Node *pre = list->head; // pre始终位于待删位置之前 for (int i = 1; i < pos; ++i) pre = pre->link; Node *delNode = pre->link; // delNode为目标结点 pre->link = delNode->link; // 跳过该结点 int value = delNode->element; // 获取将被删除的值 free(delNode); // 回收空间 list->n--; // 更新长度 return value; } // 输出整个链表内容 void printList(const HeaderList *list) { Node *p = list->head->link; // p指向第一个实际数据结点 printf("当前列表: "); while (p != NULL) { printf("%d ", p->element); p = p->link; } printf("\n"); } // 销毁链表并释放所有动态分配的空间 void destroyList(HeaderList *list) { Node *p = list->head; // 开始遍历 while (p != NULL) { Node *temp = p; p = p->link; free(temp); // 逐个释放结点 } list->head = NULL; list->n = 0; } // 测试函数 int main() { HeaderList myList; initList(&myList); insertElement(&myList, 5, 1); insertElement(&myList, 7, 2); insertElement(&myList, 9, 3); printList(&myList); printf("查找结果：%d\n", findElement(&myList, 7)); printf("删除第2项：%d\n", deleteElement(&myList, 2)); printList(&myList); destroyList(&myList); return 0; } ``` ### 算法解析： 1. **初始化** (`initList`)：创建一个空链表，设置`head->link=NULL`表示空表。 2. **查找** (`findElement`)：按顺序访问每个结点，检查是否匹配给定关键字 `key`。 3. **插入** (`insertElement`)：先定位前驱结点，然后调整指针以添加新的结点。 4. **删除** (`deleteElement`)：同样通过前驱结点修改连接关系，同时回收废弃结点空间。 5. **打印** (`printList`)：依次扫描每项数据并输出至控制台。 6. **销毁** (`destroyList`)：逐一释放所有已分配存储单元以防泄漏资源。 --- ####