7-5 单链表基本操作pta

### JMU 数据结构 单链表逆置 PTA 题解 单链表的逆置可以通过多种方法实现，其中一种常见的方法是通过头插法来完成。这种方法的核心思想是在构建新链表的过程中，每次都将当前节点插入到新链表的头部，从而使得最终的新链表顺序与原链表相反。 以下是基于PTA平台可能涉及的单链表逆置操作的具体实现： #### 实现代码 ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { char data; struct Node* next; } LinkNode; // 初始化单链表 LinkNode* InitList() { LinkNode* L = (LinkNode*)malloc(sizeof(LinkNode)); L->next = NULL; return L; } // 尾插法建立单链表 void CreateListTail(LinkNode* L, int n) { LinkNode *p, *r = L; for(int i = 0; i < n; ++i){ p = (LinkNode*)malloc(sizeof(LinkNode)); scanf(" %c", &p->data); p->next = NULL; r->next = p; r = p; } } // 输出单链表 void PrintList(LinkNode* L) { LinkNode* p = L->next; while(p != NULL){ printf("%c ", p->data); p = p->next; } printf("\n"); } // 获取单链表长度 int GetLength(LinkNode* L) { int length = 0; LinkNode* p = L->next; while(p != NULL){ length++; p = p->next; } return length; } // 判断单链表是否为空 bool IsEmpty(LinkNode* L) { return L->next == NULL ? true : false; } // 查找指定位置的元素 char FindKthElement(LinkNode* L, int k) { LinkNode* p = L->next; int index = 1; while(p && index < k){ p = p->next; index++; } if(index == k && p) return p->data; else{ printf("Index out of range.\n"); exit(1); } } // 插入元素 void InsertElement(LinkNode* L, int pos, char value) { LinkNode* p = L; int index = 0; while(p && index < pos - 1){ p = p->next; index++; } if(!p || index >= pos - 1){ LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode)); newNode->data = value; newNode->next = p->next; p->next = newNode; }else{ printf("Invalid position to insert.\n"); exit(1); } } // 删除指定位置的元素 void DeleteElement(LinkNode* L, int pos) { LinkNode* p = L; int index = 0; while(p->next && index < pos - 1){ p = p->next; index++; } if(p->next){ LinkNode* q = p->next; p->next = q->next; free(q); }else{ printf("Invalid position to delete.\n"); exit(1); } } // 单链表逆置 void ReverseList(LinkNode* L) { LinkNode* prev = NULL; LinkNode* current = L->next; LinkNode* next_node = NULL; L->next = NULL; // 头结点指向NULL while(current != NULL){ next_node = current->next; current->next = prev; prev = current; current = next_node; } L->next = prev; // 新链表头指针赋给L->next } // 主函数演示 int main(){ int n; LinkNode* L = InitList(); printf("Enter the number of elements and then the characters:\n"); scanf("%d", &n); CreateListTail(L, n); printf("Original List: "); PrintList(L); ReverseList(L); printf("Reversed List: "); PrintList(L); return 0; } ``` 上述代码实现了单链表的基本功能，并提供了`ReverseList`函数用于执行链表的逆置操作[^3]。此函数利用迭代方式逐步调整每个节点的`next`指针方向，从而使整个链表反转。 #### 解决方案说明 - **初始化**：创建一个带头结点的空链表。 - **尾插法建表**：按照输入数据逐个插入到链表尾部。 - **打印链表**：遍历并输出链表中的所有元素。 - **获取长度**：统计链表中有效节点的数量。 - **判断是否为空**：检查链表是否有任何实际数据节点。 - **查找特定位置元素**：定位到目标索引处的节点并返回其值。 - **插入/删除元素**：分别支持在任意位置插入或删除节点的操作。 - **逆置链表**：通过改变各节点之间的连接关系实现整体倒序排列。 ####

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的基本操作包括插入、删除和查找等操作。 1. 插入操作：在单链表中插入一个新节点，可以在表头或者表尾插入，也可以在指定位置插入。具体步骤如下： - 在表头插入：创建一个新节点，将新节点的指针指向原来的表头节点，然后将新节点设置为新的表头节点。 - 在表尾插入：创建一个新节点，将新节点的指针指向空，然后将原来的表尾节点的指针指向新节点。 - 在指定位置插入：创建一个新节点，将新节点的指针指向插入位置的下一个节点，然后将插入位置的前一个节点的指针指向新节点。 2. 删除操作：从单链表中删除一个节点，可以删除表头、表尾或者指定位置的节点。具体步骤如下： - 删除表头：将表头节点的指针指向下一个节点，然后释放原来的表头节点。 - 删除表尾：找到倒数第二个节点，将其指针指向空，然后释放原来的表尾节点。 - 删除指定位置：找到要删除节点的前一个节点，将其指针指向要删除节点的下一个节点，然后释放要删除的节点。 3. 查找操作：在单链表中查找指定元素的节点，可以从表头开始遍历整个链表，直到找到目标节点或者遍历到链表末尾。具体步骤如下： - 从表头开始，依次访问每个节点，比较节点的数据元素与目标元素是否相等。 - 如果相等，则找到目标节点；如果不相等，则继续访问下一个节点，直到链表末尾。