第二十七课：数据结构入门 - 数组与链表
学习目标：
- 理解数组的基本概念和操作。
- 掌握链表的基本结构与特点。
- 学会在C++中定义和操作数组和链表。
- 了解数组和链表的基本使用场景。
学习内容：
-
数组（Array）
- 概念：数组是一种线性数据结构，用一段连续的内存空间来存储一系列相同类型的元素。
- 参数用法：
- 索引（Index）：数组中每个元素的位置，通常从0开始。
- 长度（Length）：数组中元素的数量，确定数组大小的属性。
- 代码示例：
#include <iostream> using namespace std; int main() { int arr[5] = {1, 2, 3, 4, 5}; // 声明并初始化一个整型数组 // 访问并打印数组元素 for (int i = 0; i < 5; i++) { cout << "Element at index " << i << ": " << arr[i] << endl; } return 0; } - 预计输出效果：
Element at index 0: 1 Element at index 1: 2 Element at index 2: 3 Element at index 3: 4 Element at index 4: 5 - 使用场景：数组通常用于存储固定数目的元素，适合快速地通过索引查询元素。
-
链表（LinkedList）
- 概念：链表是一种线性结构，由一系列不必在内存中连续存储的元素组成，每个元素均包含数据部分和指向下一个元素的指针。
- 参数用法：
- 节点（Node）：链表中的元素，包含数据和指向下一个节点的指针。
- 头指针（Head）：指向链表的第一个节点的指针。
- 代码示例：
#include <iostream> using namespace std; // 定义链表节点结构体 struct Node { int data; Node* next; }; // 打印链表函数 void printList(Node* n) { while (n != nullptr) { cout << n->data << " "; n = n->next; } cout << endl; } int main() { Node* head = new Node(); Node* second = new Node(); Node* third = new Node(); head->data = 1; // 赋值 head->next = second; // 指向下一个节点 second->data = 2; second->next = third; third->data = 3; third->next = nullptr; printList(head); // 打印链表 return 0; } - 预计输出效果：
1 2 3 - 使用场景：链表适合于元素数量变动较大的情况，便于插入和删除元素，但访问特定位置的元素较慢。
链表遍历与插入
-
链表的遍历
- 链表的遍历意味着按照链表的指针从头到尾访问每个节点。
- 遍历通常使用循环或递归来完成。
-
链表中的数据插入
- 链表中的数据可以在头部、尾部或任意给定节点后插入。
- 插入操作需要更改节点的指针以维护链表的结构。
链表的节点定义示例（C++）：
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr)};
遍历链表示例（C++）：
void traverseList(ListNode* head) {
ListNode* temp = head;
while(temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
链表中数据插入示例（C++）：
- 在头部插入：
ListNode* insertAtHead(ListNode* head, int x) {
ListNode* newNode = new ListNode(x);
newNode->next = head;
head = newNode;
return head;
}
- 在尾部插入：
ListNode* insertAtTail(ListNode* head, int x) {
ListNode* newNode = new ListNode(x);
if(head == nullptr) {
return newNode;
}
ListNode* temp = head;
while(temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
return head;
}
- 在给定节点后插入：
void insertAfterNode(ListNode* prevNode, int x) {
if(prevNode == nullptr) {
cout << "The given previous node cannot be null." << endl;
return;
}
ListNode* newNode = new ListNode(x);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
练习题：
- 实现一个单链表，并定义一个函数遍历此链表。
- 写出一个函数，在单链表的头部插入一个节点。
- 写出一个函数，在单链表的尾部插入一个节点。
- 写出一个函数，在单链表的某个节点后插入一个新节点。
#include <iostream>
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr)};
class SinglyLinkedList {
public:
ListNode *head;
SinglyLinkedList() : head(nullptr) // 遍历链表
void traverseList() {
ListNode *temp = head;
while (temp != nullptr) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << std::endl;
}
// 在头部插入节点
void insertAtHead(int x) {
ListNode *newNode = new ListNode(x);
newNode->next = head;
head = newNode;
}
// 在尾部插入节点
void insertAtTail(int x) {
ListNode *newNode = new ListNode(x);
if (head == nullptr) {
head = newNode;
} else {
ListNode *temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}
// 在某个节点后插入新节点
void insertAfterNode(ListNode *prevNode, int x) {
if (prevNode == nullptr) {
std::cout << "The given previous node cannot be null." << std::endl;
return;
}
ListNode *newNode = new ListNode(x);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
};
int main() {
SinglyLinkedList list;
// 在链表头部插入节点
list.insertAtHead(5);
list.insertAtHead(3);
list.insertAtHead(1);
// 在链表尾部插入节点
list.insertAtTail(7);
list.insertAtTail(9);
// 遍历链表
list.traverseList();
// 在链表中第一个节点后插入新节点
list.insertAfterNode(list.head, 2);
// 再次遍历链表
list.traverseList();
return 0;
}