第二节 链表
当教授链表这个知识点时，需要详细地解释链表的概念、种类、基本操作以及与数组的区别。下面详细展开讲解链表的每个知识点：
- 链表的概念：
链表是一种线性数据结构，由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，指针域指向下一个节点，通过这种指针关系连接起来。
- 链表的种类：
主要有单向链表、双向链表和循环链表。
单向链表：每个节点只有一个指针域，指向下一个节点。
双向链表：每个节点有两个指针域，分别指向前一个节点和后一个节点。
循环链表：最后一个节点的指针域指向第一个节点，形成一个循环。
链表的基本操作：
创建链表：动态分配内存空间创建节点，构建节点之间的指针关系。
插入节点：在链表的指定位置插入一个新节点，需要调整指针关系。
删除节点：从链表中删除指定位置的节点，需要调整指针关系，并释放节点的内存空间。
查找节点：遍历链表，按照顺序查找或根据条件查找目标节点。与数组的区别：
链表的长度可以动态增长，而数组的长度固定。
在链表中插入或删除节点的操作效率高，而在数组中这些操作可能涉及到大量的数据移动。
链表不需要连续的内存空间，而数组需要。
详细展开讲解示例：
单向链表：
从头节点开始，每个节点包含数据和指向下一个节点的指针。
插入节点时，需要修改前一个节点的指针指向新节点，以及新节点的指针指向后一个节点。
删除节点时，修改前一个节点的指针指向后一个节点，然后释放被删除节点的内存空间。
双向链表：
每个节点包含指向前一个节点和后一个节点的指针。
插入节点时，需要修改前一个节点和后一个节点的指针指向新节点。
删除节点时，需要修改前一个节点和后一个节点的指针指向，然后释放被删除节点的内存空间。
循环链表：
最后一个节点的指针指向第一个节点，形成一个循环。
插入和删除节点时，需要特别注意边界条件，以防止死循环或指针错误。
通过这些详细的讲解，学生可以更好地理解链表的结构、操作和应用场景，并能够编写简单的链表代码来解决问题。
单向链表应用示例：存储学生信息
单向链表可以用来存储学生信息，每个节点代表一个学生，包含学生的姓名、学号等信息。
#include <iostream>
#include <string>
using namespace std;
struct Student {
string name;
int id;
Student* next;
};
int main() {
// 创建链表节点
Student* head = nullptr;
head = new Student;
head->name = "Alice";
head->id = 1001;
head->next = nullptr;
// 添加新节点
Student* newNode = new Student;
newNode->name = "Bob";
newNode->id = 1002;
newNode->next = nullptr;
head->next = newNode;
// 遍历链表
Student* current = head;
while (current != nullptr) {
cout << "姓名: " << current->name << ", 学号: " << current->id << endl;
current = current->next;
}
// 释放内存
while (head != nullptr) {
Student* temp = head;
head = head->next;
delete temp;
}
return 0;
}
C++指针概念
指针是 C++
中一个非常重要的概念，它是一种特殊的变量类型，用于存储内存地址。通过指针，我们可以直接访问和操作内存中的数据，而不是通过变量名来操作。
指针的概念：指针是一个变量，其值为另一个变量的内存地址。 指针存储的是内存地址，而不是实际的值。 指针可以指向任何类型的数据，包括基本数据类型、数组、结构体、函数等。指针的基本操作：
取址运算符 &：用于获取变量的地址。 间接访问运算符 *：用于访问指针所指向的内存地址中存储的值。 指针赋值：将变量的地址赋给指针。 空指针：指向空地址的指针，表示不指向任何有效的内存地址。 指针运算：指针可以进行算术运算，如加法、减法等，以移动指针指向的内存位置。指针的应用：
动态内存分配：通过 new 关键字分配动态内存，并返回指向该内存的指针。 数组和字符串操作：指针可以用于遍历数组和操作字符串。 函数参数传递：可以通过指针在函数之间传递参数，实现对变量的直接修改。 动态数据结构：如链表、树等数据结构的实现常常需要用到指针。 实现复杂数据结构：如图、图形、链表、树等复杂数据结构通常需要使用指针来建立节点之间的连接。#include <iostream> using namespace std; int main() { int num = 10; // 定义一个整数变量 int* ptr; // 声明一个整型指针 ptr = # // 将变量 num 的地址赋给指针 ptr cout << "变量 num 的值为: " << num << endl; cout << "变量 num 的地址为: " << &num << endl; cout << "指针 ptr 存储的地址为: " << ptr << endl; cout << "通过指针 ptr 访问 num 的值为: " << *ptr << endl; return 0; }
C++结构体自定义数据类型
在 C++ 中，struct
关键字用于定义一个结构体（structure），结构体是一种用户自定义的数据类型，用于组合多个不同类型的数据成员。结构体可以包含各种类型的数据，包括整数、浮点数、字符、字符串、指针等。在给定的例子中，定义了一个名为 Student 的结构体，其中包含了三个数据成员：
string name：用于存储学生的姓名，类型为 string。 int id：用于存储学生的学号，类型为 int。 Student* next：用于指向下一个学生的指针，类型为 Student*，表示该成员存储的是指向 Student 结构体的指针。这个结构体的定义描述了一个学生的基本信息以及指向下一个学生的指针，可以用于构建链表数据结构，其中每个节点表示一个学生，通过 next
指针连接起来，形成一个链表。
双向链表应用示例：实现浏览器的前进后退功能
双向链表可以用来实现浏览器的前进后退功能，每个节点代表一个网页，包含指向前一个网页和后一个网页的指针。
#include <iostream>
#include <string>
using namespace std;
struct WebPage {
string url;
WebPage* prev;
WebPage* next;
};
int main() {
// 创建链表节点
WebPage* current = nullptr;
current = new WebPage;
current->url = "www.google.com";
current->prev = nullptr;
// 添加新节点
WebPage* newPage = new WebPage;
newPage->url = "www.example.com";
newPage->prev = current;
newPage->next = nullptr;
current->next = newPage;
// 后退到前一个网页
if (current->prev != nullptr) {
current = current->prev;
cout << "当前网页: " << current->url << endl;
}
// 前进到下一个网页
if (current->next != nullptr) {
current = current->next;
cout << "当前网页: " << current->url << endl;
}
// 释放内存
delete newPage;
delete current;
return 0;
}
## 循环链表应用示例：实现游戏中的循环列表
循环链表可以用于实现游戏中的循环列表，比如玩家的回合顺序，最后一个节点的指针指向第一个节点，形成一个循环。include
using namespace std;
struct Player {
string name;
Player* next;};
int main() {
// 创建循环链表
Player* head = nullptr;
head = new Player;
head->name = "Player1";
head->next = nullptr;
Player* second = new Player;
second->name = "Player2";
second->next = nullptr;
head->next = second;
Player* third = new Player;
third->name = "Player3";
third->next = nullptr;
second->next = third;
third->next = head; // 最后一个节点指向头节点，形成循环
// 遍历循环链表
Player* current = head;
do {
cout << "当前玩家: " << current->name << endl;
current = current->next;
} while (current != head);
// 释放内存
delete head;
delete second;
delete third;
return 0;}
## 将前面成绩管理系统，温度记录，电影票售卖系统使用链表
#### 成绩管理系统使用链表改写include
include
using namespace std;
struct Student {
string name;
int score;
Student* next;};
int main() {
Student* head = nullptr;
Student* current = nullptr;
// 添加学生成绩
for (int i = 0; i < 5; ++i) {
Student* newStudent = new Student;
cout << "请输入第 " << i + 1 << " 个学生的姓名和成绩: ";
cin >> newStudent->name >> newStudent->score;
newStudent->next = nullptr;
if (head == nullptr) {
head = newStudent;
current = head;
} else {
current->next = newStudent;
current = newStudent;
}
}
// 显示学生成绩
cout << "学生成绩列表：" << endl;
current = head;
while (current != nullptr) {
cout << "姓名: " << current->name << ", 成绩: " << current->score << endl;
current = current->next;
}
// 释放内存
current = head;
while (current != nullptr) {
Student* temp = current;
current = current->next;
delete temp;
}
return 0;}
温度记录器使用链表改写：
#include <iostream>
using namespace std;
struct Temperature {
int temp;
Temperature* next;
};
int main() {
const int DAYS = 7;
Temperature* head = nullptr;
Temperature* current = nullptr;
// 输入每天的温度
for (int i = 0; i < DAYS; ++i) {
Temperature* newTemp = new Temperature;
cout << "请输入第 " << i + 1 << " 天的温度: ";
cin >> newTemp->temp;
newTemp->next = nullptr;
if (head == nullptr) {
head = newTemp;
current = head;
} else {
current->next = newTemp;
current = newTemp;
}
}
// 显示每天的温度
cout << "一周内的温度记录：" << endl;
current = head;
while (current != nullptr) {
cout << current->temp << " ";
current = current->next;
}
cout << endl;
// 释放内存
current = head;
while (current != nullptr) {
Temperature* temp = current;
current = current->next;
delete temp;
}
return 0;
}
电影票售卖系统使用链表改写：
#include <iostream>
#include <string>
using namespace std;
struct Movie {
string name;
int ticketSales;
Movie* next;
};
int main() {
const int NUM_MOVIES = 3;
Movie* head = nullptr;
Movie* current = nullptr;
// 输入每部电影的售票数量
for (int i = 0; i < NUM_MOVIES; ++i) {
Movie* newMovie = new Movie;
cout << "请输入电影 " << i + 1 << " 的名称和售票数量: ";
cin >> newMovie->name >> newMovie->ticketSales;
newMovie->next = nullptr;
if (head == nullptr) {
head = newMovie;
current = head;
} else {
current->next = newMovie;
current = newMovie;
}
}
// 统计总票数和最畅销电影
int totalSales = 0;
string bestMovieName;
int maxSales = 0;
current = head;
while (current != nullptr) {
totalSales += current->ticketSales;
if (current->ticketSales > maxSales) {
maxSales = current->ticketSales;
bestMovieName = current->name;
}
current = current->next;
}
// 显示统计结果
cout << "总售票数量为: " << totalSales << endl;
cout << "最畅销电影是: " << bestMovieName << endl;
// 释放内存
current = head;
while (current != nullptr) {
Movie* temp = current;
current = current->next;
delete temp;
}
return 0;
}这些示例展示了如何使用链表数据结构来重新实现之前的成绩管理系统、温度记录器和电影票售卖系统。通过链表，我们可以动态地添加、删除和管理数据，使代码更加灵活和易于扩展。
