链表的基本操作

（一）实验类型：设计性

（二）实验目的：

      1. 掌握线性表的链式存贮结构及基本操作，深入了解链表的基本特性，以便在实际问题背景下灵活运用它们。

      2. 巩固该存贮结构的构造方法，深入理解和灵活掌握链表的插入、删除等操作。

（三）实验内容：

1. 建立线性表的链式存储结构。

2. 完成链表操作：建立，初始化，增加，插入，删除。

 

#include <iostream>// 链表节点结构
struct ListNode {int val;                // 节点存储的值ListNode* next;         // 指向下一个节点的指针
};// 初始化链表
void initList(ListNode*& head) {head = nullptr;
}// 在链表尾部添加节点
void appendNode(ListNode*& head, int value) {ListNode* newNode = new ListNode;      // 创建新节点//创建新的空间newNode->val = value;newNode->next = nullptr;if (head == nullptr) {head = newNode;                     // 如果链表为空，直接将新节点作为头节点}else {ListNode* tmp = head;while (tmp->next != nullptr) {tmp = tmp->next;                 // 遍历链表，找到尾部节点}tmp->next = newNode;                 // 将新节点连接到尾部节点的next指针上}
}// 在指定位置插入节点
void insertNode(ListNode*& head, int value, int pos) {if (pos <= 0) {ListNode* newNode = new ListNode;  // 创建新节点newNode->val = value;newNode->next = head;               // 将新节点连接到头节点之前head = newNode;                     // 将新节点作为头节点}else {ListNode* tmp = head;int count = 1;while (tmp != nullptr && count < pos)//tmp != nullptr是因为我们插入是必须要左右两边都有数据才能叫插入，//不然就只能添加，不可以直接填在一个很远的空间里，不然就浪费空间了{tmp = tmp->next;                 // 遍历链表，找到指定位置的前一个节点count++;}if (tmp != nullptr)//必须是在tmp不为空时，才能算成插入。//再次判断是因为我们只选取count遍历到pos的位置的这种情况，而不是空的链表的情况。{ListNode* newNode = new ListNode;  // 创建新节点newNode->val = value;newNode->next = tmp->next;         // 将新节点连接到当前节点的next指针上//这是链接步骤的代码，把数据插入//至于next是因为我们是要插入在数据的中间，也就是tmp的next的位置tmp->next = newNode;//这个是指向新的插入数据的步骤，方便下一次数据的插入。}else {std::cout << "插入位置超过链表长度！" << std::endl;}}
}// 删除指定位置的节点
void deleteNode(ListNode*& head, int pos) {if (head == nullptr) {std::cout << "链表为空，无法删除节点！" << std::endl;return;}if (pos <= 0) {ListNode* tmp = head;head = head->next;          // 删除头节点delete tmp;}else {ListNode* tmp = head;int count = 1;while (tmp->next != nullptr && count < pos) {tmp = tmp->next;        // 遍历链表，找到指定位置的前一个节点count++;}if (tmp->next != nullptr) {ListNode* delNode = tmp->next;//先指向当前数据tmp->next = delNode->next;//直接将当前数据跳到下一个，前面已经链接好的数据不会丢失因为都在同一个位置//我们不过是把当前数据覆盖成下一个罢了delete delNode;}else {std::cout << "删除位置超过链表长度！" << std::endl;}}
}// 打印链表
void printList(ListNode* head) {ListNode* tmp = head;while (tmp != nullptr) {std::cout << tmp->val << " ";tmp = tmp->next;}std::cout << std::endl;
}int main() {ListNode* myList;initList(myList);// 在链表尾部增加节点appendNode(myList, 1);appendNode(myList, 2);appendNode(myList, 3);printList(myList);  // 输出：1 2 3// 在指定位置插入节点insertNode(myList, 4, 2);printList(myList);  // 输出：1 4 2 3// 删除节点deleteNode(myList, 2);printList(myList);  // 输出：1 2 3return 0;
}