讲义

课后作业

2024/4/4

# 第十八课

# 1. 综合单链表操作

假设有一个学生信息单链表，每个结点包含学生的学号、姓名和成绩。编写一个程序，实现以下操作：

  1. 插入学生信息：在单链表中插入一个新的学生信息结点，按学号从小到大的顺序插入。

  2. 删除学生信息：删除指定学号的学生信息结点。

  3. 查找学生信息：根据学号查找学生信息结点。

  4. 修改学生信息：根据学号修改学生的姓名和成绩。

  5. 显示所有学生信息：遍历并打印所有学生信息结点的学号、姓名和成绩。

链表节点定义如下：

struct Student {
    int id;        // 学号
    string name;   // 姓名
    float score;   // 成绩
    Student *next; // 指向下一个结点的指针
};

插入学生信息示例：

// 具体插入方法自定义
insertStudentInfo(head, 101, "张三", 85.5);
insertStudentInfo(head, 103, "李四", 90.0);
insertStudentInfo(head, 102, "王五", 78.5);

删除学生信息示例：

// 具体删除方法自定义
deleteStudentInfo(head, 103);

修改学生信息示例：

// 具体修改方法自定义
modifyStudentInfo(head, 101, "张小三", 88.0);

示例输出：

所有学生信息：
学号    姓名    成绩
101     张三    85.5
102     王五    78.5
103     李四    90

删除学号为 103 的学生信息后：
学号    姓名    成绩
101     张三    85.5
102     王五    78.5

修改学号为 101 的学生信息后：
学号    姓名    成绩
101     张小三  88
102     王五    78.5
  • ✅
  • 历史解析
    • 整体题解思路正确，本题主要考查单链表操作，没有问题💯

# 2. 综合双向链表操作

假设有一个双向链表，存储了学生的学号、姓名和成绩。编写一个程序，实现以下操作：

  1. 插入学生信息：按学号从小到大的顺序插入一个新的学生信息结点。

  2. 删除学生信息：根据学号删除指定的学生信息结点。

  3. 查找学生信息：根据学号查找学生信息结点。

  4. 修改学生信息：根据学号修改学生的姓名和成绩。

  5. 显示所有学生信息：遍历并打印所有学生信息结点的学号、姓名和成绩。

注意点

  1. 数据结构定义：

    • 单链表中的结点结构只包含一个指向后继结点的指针，而双向链表中的结点结构包含指向前趋结点和后继结点的指针

  2. 插入操作：

    • 单链表的插入操作需要在当前结点之后插入新结点，并且只需要将新结点的 next 指针指向当前结点的后继结点即可
    • 双向链表的插入操作不仅需要将新结点的 next 指针指向当前结点的后继结点，还需要将当前结点的后继结点的前趋指针指向新结点，并且需要考虑头结点的情况

  3. 删除操作：

    • 单链表的删除操作只需找到要删除结点的前驱结点，然后将其 next 指针指向要删除结点的后继结点，然后释放要删除结点的内存
    • 双向链表的删除操作需要同时处理前趋和后继指针，将要删除结点的前趋结点的后继指针指向要删除结点的后继结点，同时将要删除结点的后继结点的前趋指针指向要删除结点的前趋结点，然后释放要删除结点的内存

  4. 其他操作：

    • 双向链表的其他操作需要考虑前趋指针的存在，例如查找、修改等操作都需要同时考虑前趋和后继指针

链表节点定义如下：

struct node {
    int id;         // 学号
    string name;    // 姓名
    float score;    // 成绩
    node *pre, *next;  // 前趋和后继指针
};

插入学生信息示例：

// 具体插入方法自定义
insertStudentInfo(head, 101, "张三", 85.5);
insertStudentInfo(head, 103, "李四", 90.0);
insertStudentInfo(head, 102, "王五", 78.5);

删除学生信息示例：

// 具体删除方法自定义
deleteStudentInfo(head, 103);

修改学生信息示例：

// 具体修改方法自定义
modifyStudentInfo(head, 101, "张小三", 88.0);

示例输出：

所有学生信息：
学号    姓名    成绩
101     张三    85.5
102     王五    78.5
103     李四    90

删除学号为 103 的学生信息后：
学号    姓名    成绩
101     张三    85.5
102     王五    78.5

修改学号为 101 的学生信息后：
学号    姓名    成绩
101     张小三  88
102     王五    78.5
  • ✅
  • 历史解析
    • 整体题解思路正确，本题主要考查双向链表操作，没有问题💯

# 3. 综合单向循环链表操作

假设有一个循环单向链表，每个结点包含一个整数数据域和一个指向下一个结点的指针。现在需要完成以下操作：

  1. 插入结点：在循环单向链表中插入一个新结点，使得插入后链表仍然保持有序（升序排列）。

  2. 删除结点：根据给定的值，删除循环单向链表中的所有含有该值的结点。

  3. 查找结点：根据给定的值，在循环单向链表中查找并返回第一个含有该值的结点的指针，如果不存在则返回 nullptr。

  4. 反转链表：反转循环单向链表的顺序。

注意点
  • 区别：

  1. 结尾指针：

    • 单向循环链表的最后一个节点的指针域指向第一个节点，形成一个闭环。
    • 单链表的最后一个节点的指针域通常为空，指向 nullptr。

  2. 遍历终止条件：

    • 在单向循环链表中，遍历链表时的终止条件通常是判断当前节点是否等于头节点，因为循环链表的尾节点指向头节点。
    • 在单链表中，遍历链表时的终止条件通常是判断当前节点是否为空，因为最后一个节点的指针域为空。
  • 操作点：

  1. 插入操作：

    • 在单向循环链表中插入节点时，需要考虑头节点和尾节点的特殊情况，确保链表的循环性。
    • 在单链表中插入节点时，只需要考虑头节点和尾节点的特殊情况，不需要考虑链表的循环性。

  2. 删除操作：

    • 在单向循环链表中删除节点时，同样需要考虑头节点和尾节点的特殊情况，并保证链表的循环性。
    • 在单链表中删除节点时，只需考虑节点的前驱节点和后继节点。

  3. 遍历操作：

    • 在遍历单向循环链表时，需要注意循环条件，通常使用 do-while 循环，并在循环体内判断当前节点是否等于头节点。
    • 在遍历单链表时，通常使用 while 循环，并在循环条件中判断当前节点是否为空。

  4. 其他操作：

    • 其他操作（如查找、反转、合并等）在单向循环链表和单链表中大体上是相似的，只是在处理尾节点时需要额外注意单向循环链表的特殊性。

链表节点定义如下：

struct Node {
    int data;
    Node* next;
};

插入结点示例：

// 具体插入方法自定义
insertNodeSorted(head, 2);
insertNodeSorted(head, 3);
insertNodeSorted(head, 5);
insertNodeSorted(head, 8);
insertNodeSorted(head, 10);

删除结点示例：

// 具体删除方法自定义
deleteNodesWithValue(head, 5);

查找结点示例：

// 具体查找方法自定义
Node* foundNode = findNodeWithValue(head, 8);
if (foundNode != nullptr) {
    cout << "存在值为8的节点" << endl;
} else {
    cout << "没有找到值为8的节点" << endl;
}

反转链表示例：

// 具体反转方法自定义
reverseLinkedList(head);

示例输出：

原节点列表:2 3 5 8 10
删除值为5的节点后:2 3 8 10
找到值为8的节点
反向节点列表:10 8 3 2
  • ✅
  • 历史解析
    • 整体题解思路正确，本题主要考查单向循环链表操作，没有问题💯

# 4. 综合双向循环链表操作

假设有一个双向循环链表，每个结点包含一个整数数据域。编写一个程序，实现以下操作：

  1. 插入结点：在双向循环链表的指定位置（索引 i）插入一个新的结点。

  2. 删除结点：删除双向循环链表中的指定位置（索引 i）的结点。

  3. 反转链表：将双向循环链表反转，即首尾相连的双向链表的方向完全颠倒。

注意点
  • 双向链表

  1. 结构：

    • 双向链表中的每个结点包含两个指针：一个指向前一个结点，一个指向后一个结点。
    • 最后一个结点的后向指针指向空（nullptr），第一个结点的前向指针也指向空（nullptr）。

  2. 操作注意点：

    • 插入和删除结点时，需要更新前向和后向指针，确保链表的连接不会断裂。
    • 在双向链表中，可以从头部或尾部开始遍历链表，因为每个结点都有前向和后向指针。
  • 双向循环链表

  1. 结构：

    • 双向循环链表中，最后一个结点的后向指针指向第一个结点，第一个结点的前向指针指向最后一个结点，形成一个循环。
    • 每个结点包含一个指向前一个结点和一个指向后一个结点的指针。

  2. 操作注意点：

    • 插入和删除结点时，需要特别注意头结点和尾结点的处理，因为它们之间存在循环连接。
    • 在遍历双向循环链表时，要小心处理循环的情况，避免陷入死循环。
  • 操作点：

  1. 插入操作：

    • 在双向链表中，插入操作需要同时更新前向和后向指针，以保持链表的正确连接。
    • 在双向循环链表中，插入操作除了更新指针外，还要确保头尾结点的连接形成循环。

  2. 删除操作：

    • 在双向链表中，删除操作需要断开被删除结点的前向和后向指针，并更新相邻结点的指针。
    • 在双向循环链表中，删除操作同样需要断开被删除结点的前向和后向指针，并更新相邻结点的指针，同时要确保头尾结点的连接不会断裂。

  3. 遍历操作：

    • 在双向链表和双向循环链表中，遍历操作需要小心处理循环的情况，避免陷入死循环。
    • 对于双向循环链表，要注意循环结束条件，通常可以选择以头结点为起点进行遍历，直到再次遍历到头结点。

链表节点定义如下：

struct Node {
    int data;    // 数据域
    Node* prev;  // 指向前一个结点的指针
    Node* next;  // 指向后一个结点的指针
};

插入结点示例：

// 具体插入方法自定义
insertNode(head, 0, 10); // 在头部插入结点
insertNode(head, 1, 20); // 在索引为1的位置插入结点
insertNode(head, 1, 30); // 在索引为1的位置插入结点

删除结点示例：

// 具体删除方法自定义
deleteNode(head, 1); // 删除索引为1的结点

反转链表示例：

// 具体反转方法自定义
reverseList(head);

示例输出：

双向循环链表：10 30 20
删除索引为1的结点后：10 20
反转链表后：20 10
  • ✅
  • 历史解析
    • 整体题解思路正确，本题主要考查双向循环链表操作，没有问题💯
上次更新: 2024-10-19 10:01:51

阶段复习