pta程序设计类实验辅助教学平台答案单链表的建立

单链表是一种常用的数据结构之一，其可以非常方便地实现对数据的增删改查操作。在程序设计中，单链表具有非常广泛的应用，特别是在集合管理和动态存储上，它被用来构造各种重要的数据结构，如队列、栈、哈希表等。

一、单链表的概念和特征

单链表是一种非常基础的线性表结构，它由一系列的节点组成，在每个节点上都存储着一个数据元素和指向下一个节点的指针。这种指针就是链表中的连接关系，通过它，可以便捷地遍历整个链表，进行各种操作。

具体来说，链表中每个节点的定义如下：

```

struct Node {

int data; // 存储的数据

Node *next; // 指向下一个节点的指针

};

```

其中，data代表着节点所存储的数据，而next则是指向下一个节点的指针。可以看到，这里结构体中next是一个指针类型，声明变量时使用的是*。这是为了让编译器在编译代码时区分开普通的变量和指针类型的变量。

相比于数组这种顺序存储的数据结构，链表的最大优势在于它可以动态地分配内存空间，而不受固定大小的限制。当添加新节点时，只需要在内存中申请一个空间，并将新节点插入到链表中。这样可以避免数组插入和删除时产生的复杂度，提高程序的效率。

二、单链表的操作

链表中有很多可以对其进行的操作，常见的包括插入、删除、查找和遍历。下面分别对这些操作进行介绍。

1、插入操作

插入操作是链表中最常见的一种操作，通过它可以在链表中添加新的节点。具体实现方式由于情况的复杂度可能有所不同，在此介绍两种比较典型的情况。

首先是在链表的末尾插入一个新的节点，此时只要将新节点的指针赋值为空，然后将原链表的最后一个节点的next指针指向新节点即可，如下所示：

```

Node *node1 = new Node; // 创建一个新的节点

node1->data = 1; // 给节点的成员变量赋值

node1->next = NULL;

Node *node2 = new Node;

node2->data = 2;

node2->next = NULL;

Node *head = node1; // 定义头节点指针，初始值为node1

node1->next = node2; // node1的next指向node2

```

再来看一下在链表的中间位置插入节点的情况。在这种情况下，需要考虑一下插入的位置和插入的方法。一般常用的方法是先找到需要插入位置的前一个节点，然后将该节点的next指针赋值为新节点的地址，同时新节点的next指针也指向原先该节点指向的下一个节点，如下所示：

```

Node *node1 = new Node; // 创建三个节点，这里初始化节点的数值仅做说明，实际情况可以根据需要自行修改

node1->data = 1;

node1->next = NULL;

Node *node2 = new Node;

node2->data = 2;

node2->next = NULL;

Node *node3 = new Node;

node3->data = 3;

node3->next = NULL;

Node *curr_node = node1; // 指针初始化，初始值为node1，其中，curr_node为当前节点的指针，prev_node为前一个节点的指针

Node *prev_node = NULL;

while (curr_node != NULL) { // 在目的节点的位置插入新节点

if (curr_node->data >= 2) {

node2->next = curr_node;

prev_node->next = node2;

break;

}

prev_node = curr_node;

curr_node = curr_node->next;

}

```

2、删除操作

链表的删除操作和插入操作类似，也可以通过遍历来寻找需要删除的节点，并将该节点的指针从链表中断开，释放该节点所占用的内存空间。实现过程和插入操作类似，这里略作介绍。

首先，需要找到需要删除的节点的前一个节点的指针，然后将该节点从链表中删除。具体实现过程如下：

```

Node *prev_node = NULL;

Node *curr_node = head;

while (curr_node != NULL) {

if (curr_node->data == target_data) { // 这里target_data表示需要删除的节点的值

if (prev_node == NULL) { // 如果删除的节点是头节点

head = curr_node->next;

} else {

prev_node->next = curr_node->next;

}

delete curr_node; // 释放节点所占空间，避免内存泄漏

return true;

}

prev_node = curr_node;

curr_node = curr_node->next;

}

return false; // 如果循环完毕之后仍然没有找到要删除的节点，返回false

```

这段代码中，需要注意的是如果删除的是头节点，那么需要将head指针重新指向删除节点的下一个节点，否则链表中将出现断链的情况。因此，在进行链表的删除操作前需要仔细考虑各种情况。

3、查找操作

链表的查找操作一般包括按节点值的查找和按节点位置的查找。这里介绍按节点值查找的方法，按照类似遍历的方式，顺序查找整个链表，找到对应值的节点即可。具体实现过程如下：

```

Node *curr_node = head; // 指针初始化，从头节点开始遍历

while (curr_node != NULL) {

if (curr_node->data == target_data) { // 如果当前节点的值等于目标值

return curr_node; // 返回当前节点的指针

}

curr_node = curr_node->next; // 指针后移

}

return NULL; // 如果循环完整个链表没有找到符合条件的节点，返回NULL指针

```

按照类似的方式，查找节点的位置也是可以实现的，这里不再赘述。

4、遍历操作

链表的遍历操作是其中非常重要的一种，通过遍历可以将整个链表的节点全部打印出来，或者按照特定的顺序输出。基本遍历操作的基础实现如下：

```

void traverse(Node *head) { // 入参为头节点的指针

Node *curr_node = head; // 指针初始化，从头节点开始遍历

while (curr_node != NULL) { // 循环结束条件是到达了链表的尾部

cout << curr_node->data << " "; // 输出当前节点的数据

curr_node = curr_node->next; // 指针后移

}

cout << endl;

}

```

可以看到，通过遍历可以顺序输出整个链表的内容。

三、单链表的实践

接下来，我们用一个具体的例子来演示单链表的使用。假设我们需要编写一个程序，来管理一群学生的信息。每个学生有一个学号和姓名，我们希望能够按照学号的大小顺序来插入和删除节点，同时可以查找和遍历整个链表。

那么我们可以定义一个学生类信息，其中保存学号和姓名，然后在主函数中创建一个单链表，并在其中按照学号大小来插入节点。接着，通过遍历功能查看整个链表中的学生信息，如果需要删除某个学生的信息，可以通过学号来查找到对应的节点，然后删除它。

```

#include

#include

using namespace std;

class Student {

public:

int id; // 学生学号

string name; // 学生姓名

};

struct Node {

Student stu; // 存放学生信息

Node *next; // 指向下一个节点

};

Node *create_list() { // 创建链表

Node *head = NULL;

return head;

}

void insert_node(Node *head, Node *new_node) { // 在链表中按学号顺序插入节点

// step 1：先找到当前节点的前一个节点，由于当前链表按学号单调递增，因此可以进行类似二分查找的方式来查找

Node *curr_node = head;

Node *prev_node = NULL;

while (curr_node != NULL && curr_node->stu.id < new_node->stu.id) {

prev_node = curr_node;

curr_node = curr_node->next;

}

// step 2：将新节点的next指针指向curr_node，将prev_node的next指针指向new_node

new_node->next = curr_node;

if (prev_node != NULL) {

prev_node->next = new_node;

}

else {

head = new_node;

}

}

void delete_node(Node *head, int id) { // 在链表中按学号删除节点

Node *prev_node = NULL;

Node *curr_node = head;

while (curr_node != NULL && curr_node->stu.id != id) {

prev_node = curr_node;

curr_node = curr_node->next;

}

// 如果找到需要删除的节点，那么将该节点的前一个节点的next指针指向该节点的next节点

if (curr_node != NULL && curr_node->stu.id == id) {

if (prev_node != NULL) {

prev_node->next = curr_node->next;

}

else {

head = curr_node->next;

}

delete curr_node;

}

}

void traverse(Node *head) { // 遍历整个链表，输出学生信息

Node *curr_node = head;

while (curr_node != NULL) {

cout << curr_node->stu.id << " " << curr_node->stu.name << endl;

curr_node = curr_node->next;

}

}

int main() {

Node *head = create_list();

Student stu1 = {101, "Tom"};

Student stu2 = {103, "Jerry"};

Student stu3 = {102, "Mary"};

Student stu4 = {104, "Alice"};

Student stu5 = {105, "Bob"};

Node *node1 = new Node;

node1->stu = stu1;

node1->next = NULL;

Node *node2 = new Node;

node2->stu = stu2;

node2->next = NULL;

Node *node3 = new Node;

node3->stu = stu3;

node3->next = NULL;

Node *node4 = new Node;

node4->stu = stu4;

node4->next = NULL;

Node *node5 = new Node;

node5->stu = stu5;

node5->next = NULL;

insert_node(head, node1); // 依次插入学生信息

insert_node(head, node2);

insert_node(head, node3);

insert_node(head, node4);

insert_node(head, node5);

cout << "原始学生信息列表：" << endl;

traverse(head);

delete_node(head, 103); // 删除学号为103的学生信息

cout << "删除学号为103的学生之后的信息列表：" << endl;

traverse(head);

return 0;

}

```

这个程序中，我们首先定义了一个学生类（Student），其中包含了学号和姓名两个成员变量，然后定义了一个单链表（create_list函数），并在其中实现了插入（insert_node函数）、删除（delete_node函数）和遍历（traverse函数）的操作。

最后，我们通过一个主函数来运行程序，在其中依次插入学生信息，并按照学号排序，然后遍历整个学生信息链表。在找到需要删除的节点时，我们通过学号进行查找，并将对应的学生信息从链表中删除。最终，我们再次遍历整个链表，输出当前学生信息的列表。

四、总结

单链表是一种常用的数据结构之一，其最大的优势在于可以动态地分配内存空间，在进行数据的插入、删除和修改时非常方便。通过上述实践，我们可以发现单链表的实现过程其实并不难，只要掌握好链表中基本的增删改查操作，就可以应对大部分的编程场景。当然，对于更加复杂的问题，还需要通过不断的实践和学习来不断提升自己的技能水平。