笔记：数据结构（链表）

链表基本操作分解链表是一种动态数据结构它通过指针将一组零散的内存块串联起来。链表的基本操作包括初始化、插入、删除、查找、遍历和销毁等。以下是链表的基本操作分解以单链表为例。1.链表的定义typedef struct Node { int data; // 数据域存储元素的值 struct Node *next; // 指针域指向下一个结点 } Node; typedef struct { Node *head; // 头指针指向链表的第一个结点 } LinkedList;2.链表的初始化初始化链表将头指针置为NULL表示链表为空。void InitList(LinkedList *L) { L-head NULL; // 头指针初始化为NULL }3.链表的插入操作1在链表头部插入元素void InsertAtHead(LinkedList *L, int e) { Node *newNode (Node*)malloc(sizeof(Node)); // 创建新结点 if (!newNode) { printf(Memory allocation failed.\n); return; } newNode-data e; // 设置新结点的数据域 newNode-next L-head; // 新结点的指针域指向原头结点 L-head newNode; // 更新头指针 }2在链表尾部插入元素void InsertAtTail(LinkedList *L, int e) { Node *newNode (Node*)malloc(sizeof(Node)); // 创建新结点 if (!newNode) { printf(Memory allocation failed.\n); return; } newNode-data e; // 设置新结点的数据域 newNode-next NULL; // 新结点的指针域置为NULL if (L-head NULL) { // 如果链表为空新结点为头结点 L-head newNode; } else { Node *p L-head; while (p-next ! NULL) { // 找到链表的最后一个结点 p p-next; } p-next newNode; // 将新结点插入链表尾部 } }3在链表的第i个位置插入元素void InsertAtPosition(LinkedList *L, int i, int e) { if (i 1) { printf(Invalid position.\n); return; } Node *newNode (Node*)malloc(sizeof(Node)); // 创建新结点 if (!newNode) { printf(Memory allocation failed.\n); return; } newNode-data e; // 设置新结点的数据域 if (i 1) { // 如果插入位置是第一个结点 newNode-next L-head; L-head newNode; return; } Node *p L-head; for (int j 1; j i - 1 p ! NULL; j) { // 找到第 i-1 个结点 p p-next; } if (p NULL) { // 如果插入位置超出链表长度 printf(Invalid position.\n); free(newNode); return; } newNode-next p-next; // 将新结点插入第 i 个位置 p-next newNode; }4.链表的删除操作1删除链表的第i个位置的元素void DeleteAtPosition(LinkedList *L, int i) { if (i 1 || L-head NULL) { printf(Invalid position or list is empty.\n); return; } if (i 1) { // 如果删除的是第一个结点 Node *temp L-head; L-head L-head-next; free(temp); return; } Node *p L-head; for (int j 1; j i - 1 p ! NULL; j) { // 找到第 i-1 个结点 p p-next; } if (p NULL || p-next NULL) { // 如果删除位置超出链表长度 printf(Invalid position.\n); return; } Node *temp p-next; // 临时指针指向要删除的结点 p-next temp-next; // 将第 i-1 个结点的指针域指向第 i1 个结点 free(temp); // 释放删除结点的内存 }2删除链表中值为e的第一个元素void DeleteByValue(LinkedList *L, int e) { if (L-head NULL) { printf(List is empty.\n); return; } if (L-head-data e) { // 如果删除的是第一个结点 Node *temp L-head; L-head L-head-next; free(temp); return; } Node *p L-head; while (p-next ! NULL p-next-data ! e) { // 找到值为 e 的结点的前驱结点 p p-next; } if (p-next NULL) { // 如果未找到值为 e 的结点 printf(Element not found.\n); return; } Node *temp p-next; // 临时指针指向要删除的结点 p-next temp-next; // 将前驱结点的指针域指向删除结点的下一个结点 free(temp); // 释放删除结点的内存 }5.链表的查找操作查找链表中值为e的第一个结点并返回其位置。int LocateElem(LinkedList *L, int e) { Node *p L-head; int pos 1; while (p ! NULL) { // 遍历链表 if (p-data e) { // 找到值为 e 的结点 return pos; // 返回结点的位置 } p p-next; pos; } return -1; // 未找到返回 -1 }6.链表的遍历操作遍历链表并打印所有元素。void PrintList(LinkedList *L) { Node *p L-head; if (p NULL) { printf(List is empty.\n); return; } printf(List: ); while (p ! NULL) { // 遍历链表 printf(%d , p-data); // 打印结点的值 p p-next; } printf(\n); }7.链表的销毁操作释放链表中所有结点的内存。void DestroyList(LinkedList *L) { Node *p L-head; while (p ! NULL) { // 遍历链表 Node *temp p; // 临时指针指向当前结点 p p-next; // 指针指向下一个结点 free(temp); // 释放当前结点的内存 } L-head NULL; // 头指针置为NULL printf(List destroyed.\n); }8.示例代码int main() { LinkedList L; InitList(L); // 初始化链表 InsertAtHead(L, 10); // 在头部插入10 InsertAtTail(L, 20); // 在尾部插入20 InsertAtPosition(L, 2, 15); // 在第2个位置插入15 PrintList(L); // 输出: List: 10 15 20 DeleteAtPosition(L, 2); // 删除第2个位置的元素 PrintList(L); // 输出: List: 10 20 DeleteByValue(L, 20); // 删除值为20的元素 PrintList(L); // 输出: List: 10 int pos LocateElem(L, 10); // 查找值为10的元素 printf(Element 10 is at position: %d\n, pos); // 输出: Element 10 is at position: 1 DestroyList(L); // 销毁链表 return 0; }9.总结链表的基本操作包括初始化、插入、删除、查找、遍历和销毁。链表的优点是插入和删除操作高效缺点是访问元素需要遍历链表。通过掌握链表的基本操作可以更好地理解链表的实现原理和应用场景。