#c

指针与链表专题

从内存管理到数据结构的进阶之路

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 指针基础知识

1.1 指针的概念和定义

  • 指针(Pointer)的定义：
    • 指针是存储内存地址的变量
    • 通过指针可以间接访问其他变量的值
    • 指针类型决定了它能指向的数据类型
    • 指针是C++中最强大的特性之一
  • 指针的基本特点：
    • 地址存储：指针变量存储的是内存地址
    • 类型安全：不同类型的指针不能随意转换
    • 间接访问：通过解引用操作符*访问目标值
    • 动态性：可以在运行时改变指向的目标
  • 指针的声明和初始化：
    int* ptr;           // 声明整型指针
int x = 10;
ptr = &x;           // 取地址操作符&
int* ptr2 = &x;     // 声明时初始化
  • 指针的基本操作：
    int value = *ptr;   // 解引用，获取指向的值
*ptr = 20;          // 通过指针修改值
ptr++;              // 指针算术运算
  • 空指针：
    int* nullPtr = nullptr;  // C++11推荐
int* nullPtr2 = NULL;    // C风格
返回目录 信息学 指针与链表专题 魅客科创中心

1.2 指针的类型和大小

  • 指针类型系统：

    int* intPtr;        // 整型指针
char* charPtr;      // 字符指针
double* doublePtr;  // 双精度指针
void* voidPtr;      // 通用指针
int** ptrPtr;       // 指针的指针

  • 指针大小：

    • 在64位系统中，所有指针都占8字节
    • 在32位系统中，所有指针都占4字节
    • 指针大小与指向的数据类型无关
      cout << sizeof(int*) << endl;    // 8 (64位)
cout << sizeof(char*) << endl;   // 8 (64位)
cout << sizeof(double*) << endl; // 8 (64位)

  • 指针的类型安全：

    int x = 10;
int* intPtr = &x;    // 正确
char* charPtr = &x;  // 编译错误
void* voidPtr = &x;  // 正确，但需要类型转换

  • 指针算术运算：

    int arr[5] = {1, 2, 3, 4, 5};
int* ptr = arr;
ptr++;      // 移动到下一个元素
ptr += 2;   // 移动两个元素位置
返回目录 信息学 指针与链表专题 魅客科创中心

1.3 new与delete操作符

  • new操作符：
    • 用于动态分配内存返回指向分配内存的指针
    • 可以分配单个对象或数组
    • 自动调用构造函数（对于类类型）
      // 分配单个对象
int* ptr = new int(42);        // 初始化为42
double* dPtr = new double(3.14);

// 分配数组
int* arr = new int[10];        // 10个int的数组
char* str = new char[100];     // 100个char的数组
  • delete操作符：
    • 用于释放new分配的内存
    • 必须与new配对使用
    • 释放单个对象用delete
    • 释放数组用delete[]
      delete ptr;                    // 释放单个对象
delete[] arr;                  // 释放数组
delete[] str;                  // 释放字符数组
返回目录 信息学 指针与链表专题 魅客科创中心

1.4 指针的常见用途

  • 动态内存分配：
    int* singleValue = new int(42);    // 单个值
delete singleValue;                // 释放内存

int* dynamicArray = new int[10];  // 动态数组
delete[] dynamicArray;             // 释放内存
  • 函数参数传递：
    void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调用
int x = 5, y = 10;
swap(&x, &y);
返回目录 信息学 指针与链表专题 魅客科创中心

1.4.1 指针的常见用途

  • 函数返回指针：
    int* findMax(int* arr, int size) {
    int* maxPtr = arr;
    for (int i = 1; i < size; i++) {
        if (arr[i] > *maxPtr) {
            maxPtr = &arr[i];
        }
    }
    return maxPtr;
}
  • 函数指针：
    int (*funcPtr)(int, int);  // 函数指针
funcPtr = &max;             // 指向max函数
int result = funcPtr(5, 3); // 调用函数

  • 指针数组：

    int* ptrArray[5];      // 指针数组
int values[5] = {1, 2, 3, 4, 5};

for (int i = 0; i < 5; i++) {
    ptrArray[i] = &values[i];
}

  • 数组指针：

    int (*arrayPtr)[5];    // 指向数组的指针
int arr[5] = {1, 2, 3, 4, 5};
arrayPtr = &arr;
返回目录 信息学 指针与链表专题 魅客科创中心

1.5 多级指针

多级指针：

int x = 10;
int* ptr = &x;
int** ptrPtr = &ptr;
int*** ptrPtrPtr = &ptrPtr;

cout << ***ptrPtrPtr << endl; // 输出10
返回目录 信息学 指针与链表专题 魅客科创中心

1.6 指针使用注意事项

  • *运算符的歧义性：

    • 声明中的*：表示指针类型修饰符
    • 表达式中的*：表示解引用操作符
    • 重载的*：类中可以重载解引用运算符
    • 优先级问题：注意*与其他运算符的优先级关系

  • 声明时*的结合规则：

    int* p1, p2;    // p1是int*，p2是int
int *p1, *p2;   // p1和p2都是int*
int* p1 = nullptr, *p2 = nullptr;  // 推荐写法

// 复杂声明的解析
int* arr[10];      // 指针数组：10个int*元素的数组
int (*arr)[10];    // 数组指针：指向10个int元素的数组的指针
int** ptr;         // 指针的指针
  • 指针声明的最佳实践：
    // 推荐：每个指针单独声明
int* ptr1;
int* ptr2;

// 避免：一行声明多个指针
int* ptr1, ptr2;  // 容易误解

// 推荐：使用typedef或using简化复杂声明
using IntPtr = int*;
IntPtr ptr1, ptr2;  // 两个都是指针

// 推荐：使用auto简化声明
auto ptr = &variable;
返回目录 信息学 指针与链表专题 魅客科创中心

1.7 指针的陷阱

  • *运算符的优先级陷阱：
    int arr[5] = {1, 2, 3, 4, 5};
int* ptr = arr;

// 错误：*ptr++ 等价于 *(ptr++)
int value1 = *ptr++;  // 先取*ptr的值，然后ptr++

// 正确：(*ptr)++
(*ptr)++;            // 先解引用，然后递增指向的值

// 括号的重要性
int value2 = *(ptr + 1);  // 访问下一个元素
int value3 = *ptr + 1;    // 当前元素的值加1
返回目录 信息学 指针与链表专题 魅客科创中心

2. 指针与数组

2.1 数组名的指针特性

  • 数组名与指针的关系：
    • 数组名在大多数情况下被当作指向首元素的指针
    • 数组名不是指针，但可以隐式转换为指针
    • sizeof(数组名)返回整个数组的大小
    • sizeof(指针)返回指针的大小
  • 数组与指针的区别：
    • 数组是固定大小的内存块
    • 指针是可以改变指向的变量
    • 数组不能被重新赋值
    • 指针可以进行算术运算和重新赋值
  • 数组名的使用示例：
    int arr[5] = {1, 2, 3, 4, 5};
int* ptr = arr;        // 数组名隐式转换为指针

cout << arr[0] << endl;    // 1
cout << ptr[0] << endl;    // 1
cout << *(arr + 1) << endl; // 2
cout << *(ptr + 1) << endl; // 2
  • 重要区别：
    int arr[5];
int* ptr;
sizeof(arr);  // 20 (5 * sizeof(int))
sizeof(ptr);  // 8 (指针大小)
ptr = arr;    // 正确
arr = ptr;    // 错误！数组不能重新赋值
返回目录 信息学 指针与链表专题 魅客科创中心

2.2 指针访问数组元素

  • 指针算术运算：
    int arr[5] = {10, 20, 30, 40, 50};
int* ptr = arr;

cout << *ptr << endl;      // 10 (arr[0])
cout << *(ptr + 1) << endl; // 20 (arr[1])
cout << *(ptr + 2) << endl; // 30 (arr[2])

ptr++;                     // 指向下一个元素
cout << *ptr << endl;      // 20

  • 指针与下标的等价性：

    int arr[5] = {1, 2, 3, 4, 5};
int* ptr = arr;

// 以下表达式等价：
arr[i]        == *(arr + i)        == *(ptr + i)        == ptr[i]
&arr[i]       == arr + i           == ptr + i

  • 指针遍历数组：

    int arr[5] = {1, 2, 3, 4, 5};
int* ptr = arr;
int* end = arr + 5;  // 指向数组末尾

for (; ptr < end; ptr++) {
    cout << *ptr << " ";
}
返回目录 信息学 指针与链表专题 魅客科创中心

2.2.1 指针访问数组元素

  • 多维数组与指针：
    int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

int (*rowPtr)[4] = matrix;  // 指向包含4个元素的数组
cout << rowPtr[1][2] << endl; // 7
cout << *(*(rowPtr + 1) + 2) << endl; // 7
  • 动态数组：
    int size;
cin >> size;
int* dynamicArr = new int[size];

for (int i = 0; i < size; i++) {
    dynamicArr[i] = i * 2;
}

delete[] dynamicArr;
返回目录 信息学 指针与链表专题 魅客科创中心

2.3 数组作为函数参数

  • 数组参数传递：
    // 三种等价的函数声明
void printArray(int arr[], int size);
void printArray(int* arr, int size);
void printArray(int arr[10], int size);  // 10被忽略

void printArray(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
}
  • 返回数组指针：
    int* createArray(int size) {
    int* arr = new int[size];
    for (int i = 0; i < size; i++) {
        arr[i] = i;
    }
    return arr;  // 返回动态数组指针
}

// 使用
int* myArray = createArray(5);
delete[] myArray;  // 记得释放内存
返回目录 信息学 指针与链表专题 魅客科创中心

2.4 二维数组作为函数参数

二维数组参数：

// 第二维不可以省略
void printMatrix(int matrix[][4], int rows);
void printMatrix(int (*matrix)[4], int rows);

void printMatrix(int (*matrix)[4], int rows) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < 4; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}
返回目录 信息学 指针与链表专题 魅客科创中心

3. 字符指针

3.1 字符串的基础概念

  • C风格字符串：
    • 以空字符'\0'结尾的字符数组
    • 字符指针指向字符串的首字符
    • 字符串字面量存储在只读内存区域
    • 可以通过字符指针访问和操作字符串
  • 字符串的存储方式：
    • 字符串字面量："Hello"存储在常量区
    • 字符数组：char str[] = "Hello"存储在栈区
    • 动态分配：new char[size]存储在堆区
  • 字符指针的声明：
    char* str1 = "Hello";      // 指向字符串字面量
char str2[] = "World";     // 字符数组
char* str3 = new char[20]; // 动态分配
  • 字符串操作：
    char* str = "Hello";
cout << str << endl;        // 输出整个字符串
cout << *str << endl;       // 输出第一个字符'H'
cout << *(str + 1) << endl; // 输出第二个字符'e'
返回目录 信息学 指针与链表专题 魅客科创中心

3.2 字符指针与字符数组

字符指针 vs 字符数组：

// 字符指针
char* ptr = "Hello";
ptr = "World";     // 正确，可以重新指向
// ptr[0] = 'h';   // 错误！字符串字面量不可修改

// 字符数组
char arr[] = "Hello";
// arr = "World";  // 错误！数组不能重新赋值
arr[0] = 'h';      // 正确，可以修改数组内容

字符串遍历：

char* str = "Programming";

// 使用下标
for (int i = 0; str[i] != '\0'; i++) {
    cout << str[i];
}

// 使用指针
char* ptr = str;
while (*ptr != '\0') {
    cout << *ptr;
    ptr++;
}

// 使用指针算术
for (char* p = str; *p; p++) {
    cout << *p;
}
返回目录 信息学 指针与链表专题 魅客科创中心

4. 结构体指针

4.1 结构体基础与指针

  • 结构体指针的定义：
    • 指向结构体变量的指针
    • 通过指针访问结构体成员
    • 支持动态分配结构体内存
    • 常用于链表、树等数据结构
  • 结构体定义：
    struct Student {
    string name;
    int age;
    double score;
};
  • 结构体指针声明：
    Student s1 = {"张三", 18, 95.5};
Student* ptr = &s1;           // 指向结构体的指针
Student* dynamicPtr = new Student();  // 动态分配
  • 成员访问方式：
    // 通过结构体变量访问
cout << s1.name << endl;

// 通过指针访问（两种方式）
cout << (*ptr).name << endl;  // 解引用后访问
cout << ptr->name << endl;    // 箭头操作符
返回目录 信息学 指针与链表专题 魅客科创中心

4.2 结构体指针的操作

  • 结构体指针的基本操作：
    struct Point {
    int x;
    int y;
};

Point p1 = {10, 20};
Point* ptr = &p1;

// 访问成员
cout << ptr->x << endl;    // 10
cout << ptr->y << endl;    // 20

// 修改成员
ptr->x = 30;
ptr->y = 40;

// 指针算术
Point* ptr2 = ptr + 1;  // 指向下一个Point
  • 动态分配结构体：
    // 分配单个结构体
Student* stu = new Student();
stu->name = "李四";
stu->age = 19;
stu->score = 88.5;

delete stu;

// 分配结构体数组
Student* stuArray = new Student[3];
stuArray[0].name = "王五";
stuArray[1].name = "赵六";

delete[] stuArray;
返回目录 信息学 指针与链表专题 魅客科创中心

4.2.2 结构体指针的操作

  • 结构体指针作为函数参数：
    void printStudent(const Student* stu) {
    cout << "姓名: " << stu->name << endl;
    cout << "年龄: " << stu->age << endl;
    cout << "成绩: " << stu->score << endl;
}

void updateStudent(Student* stu, double newScore) {
    stu->score = newScore;
}
  • 结构体指针数组：
    Student s1 = {"张三", 18, 95.5};
Student s2 = {"李四", 19, 88.5};
Student s3 = {"王五", 20, 92.0};

Student* stuArray[3] = {&s1, &s2, &s3};

for (int i = 0; i < 3; i++) {
    cout << stuArray[i]->name << endl;
}
返回目录 信息学 指针与链表专题 魅客科创中心

4.2.3 结构体指针的操作

  • 嵌套结构体指针：
    struct Address {
    string city;
    string street;
};

struct Person {
    string name;
    Address* address;  // 指向另一个结构体
};

Address addr = {"北京", "中关村"};
Person person = {"张三", &addr};

cout << person.name << endl;
cout << person.address->city << endl;
cout << person.address->street << endl;
  • 自引用结构体：
    struct Node {
    int data;
    Node* next;  // 指向同类型结构体的指针
};

Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}
返回目录 信息学 指针与链表专题 魅客科创中心

5. 单向链表

5.1 单向链表的概念

  • 单向链表的定义：
    • 由一系列节点组成的线性数据结构
    • 每个节点包含数据域和指向下一个节点的指针
    • 最后一个节点的指针域为nullptr
    • 只能从头到尾单向遍历
  • 单向链表的特点：
    • 动态大小：可以在运行时动态增长或缩小
    • 插入效率：在已知位置插入的时间复杂度为
    • 内存利用率：按需分配内存，无空间浪费
    • 访问限制：不能随机访问，只能顺序访问
  • 链表节点结构：
    struct ListNode {
    int data;           // 数据域
    ListNode* next;     // 指针域
};
  • 链表的基本操作：
    • 创建：动态分配节点内存
    • 插入：在指定位置插入新节点
    • 删除：删除指定位置的节点
    • 查找：遍历链表查找特定值
    • 遍历：访问链表中的所有节点
返回目录 信息学 指针与链表专题 魅客科创中心

5.2 链表与数组的对比

  • 插入/删除：链表，数组
  • 随机访问：链表，数组
  • 内存空间：链表需要额外指针空间
返回目录 信息学 指针与链表专题 魅客科创中心

5.3 单向链表的基本操作

链表节点定义：

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};
  • 创建新节点：
    Node* createNode(int data) {
    return new Node(data);
}

  • 头部插入：

    Node* insertFront(Node* head, int data) {
    Node* newNode = createNode(data);
    newNode->next = head;
    return newNode;  // 返回新的头节点
}

  • 尾部插入：

    Node* insertBack(Node* head, int data) {
    Node* newNode = createNode(data);        
    Node* current = head;
    while (current->next) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}
返回目录 信息学 指针与链表专题 魅客科创中心

5.3.2 单向链表的基本操作

  • 查找节点：
    Node* findNode(Node* head, int data) {
    Node* current = head;
    while (current) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return nullptr;  // 未找到
}
  • 获取链表长度：
    int getLength(Node* head) {
    int count = 0;
    Node* current = head;
    while (current) {
        count++;
        current = current->next;
    }
    return count;
}
返回目录 信息学 指针与链表专题 魅客科创中心

5.3.3 单向链表基本操作

  • 指定位置插入：
    Node* insertAt(Node* head, int index, int data) {
    if (index < 0) {
        return head;  // 无效索引
    }
    
    if (index == 0) {
        return insertFront(head, data);
    }
    
    Node* newNode = createNode(data);
    Node* current = head;
    int currentIndex = 0;
    
    // 找到插入位置的前一个节点
    while (current && currentIndex < index - 1) {
        current = current->next;
        currentIndex++;
    }
    
    if (!current) {
        delete newNode;  // 索引越界，释放内存
        return head;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    return head;
}
  • 头部删除：
    Node* deleteFront(Node* head) {
    if (!head) {
        return nullptr;
    }
    
    Node* newHead = head->next;
    delete head;
    return newHead;
}
返回目录 信息学 指针与链表专题 魅客科创中心

5.3.4 单向链表基本操作

  • 尾部删除：
    Node* deleteBack(Node* head) {
    if (!head) {
        return nullptr;
    }
    
    if (!head->next) {
        delete head;
        return nullptr;
    }
    
    Node* current = head;
    while (current->next->next) {
        current = current->next;
    }
    
    delete current->next;
    current->next = nullptr;
    return head;
}
  • 指定位置删除：
    Node* deleteAt(Node* head, int index) {
    if (!head || index < 0) {
        return head;
    }
    
    if (index == 0) {
        return deleteFront(head);
    }
    
    Node* current = head;
    int currentIndex = 0;
    
    // 找到要删除节点的前一个节点
    while (current->next && currentIndex < index - 1) {
        current = current->next;
        currentIndex++;
    }
    
    if (!current->next) {
        return head;  // 索引越界
    }
    
    Node* temp = current->next;
    current->next = temp->next;
    delete temp;
    return head;
}
返回目录 信息学 指针与链表专题 魅客科创中心

5.3.5 单向链表基本操作

释放整个链表：

void deleteList(Node* head) {
    Node* current = head;
    while (current) {
        Node* next = current->next;
        delete current;
        current = next;
    }
}
  • 查找数据是否存在：
    bool search(Node* head, int data) {
    return findNode(head, data) != nullptr;
}
返回目录 信息学 指针与链表专题 魅客科创中心

5.4 单向链表的高级操作

  • 查找数据的位置：
    int findIndex(Node* head, int data) {
    Node* current = head;
    int index = 0;
    
    while (current) {
        if (current->data == data) {
            return index;
        }
        current = current->next;
        index++;
    }
    
    return -1;  // 未找到
}
  • 反转链表：
    Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;
    
    while (current) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    return prev;  // 新的头节点
}
返回目录 信息学 指针与链表专题 魅客科创中心

6. 双向链表

6.1 双向链表的概念

  • 双向链表的定义：
    • 每个节点包含数据域和两个指针域
    • 一个指针指向前驱节点，一个指向后继节点
    • 可以双向遍历链表
    • 插入和删除操作比单向链表更灵活
  • 双向链表的特点：
    • 双向访问：可以从任意方向遍历
    • 操作灵活：删除节点时不需要前驱节点
    • 内存开销：每个节点需要额外的指针空间
    • 实现复杂：维护两个指针的指向关系
  • 双向链表节点结构：
    struct DoublyListNode {
    int data;
    DoublyListNode* prev;  // 前驱指针
    DoublyListNode* next;  // 后继指针
};
  • 双向链表的优势：
    • 双向遍历：支持前向和后向遍历
    • 高效删除：删除节点时间复杂度
    • 灵活插入：可以在节点前后插入
    • 回溯能力：在某些算法中很有用
返回目录 信息学 指针与链表专题 魅客科创中心

6.2 双向链表的基本操作

  • 双向链表节点定义：
    struct DoublyNode {
    int data;
    DoublyNode* prev;  // 前驱指针
    DoublyNode* next;  // 后继指针
    DoublyNode(int x) : data(x), prev(nullptr), next(nullptr) {}
};
  • 创建新节点：
    DoublyNode* createDoublyNode(int data) {
    return new DoublyNode(data);
}
  • 头部插入：
    DoublyNode* insertFront(DoublyNode* head, int data) {
    DoublyNode* newNode = createDoublyNode(data);
    
    if (!head) {
        return newNode;
    }
    
    newNode->next = head;
    head->prev = newNode;
    return newNode;  // 返回新的头节点
}
返回目录 信息学 指针与链表专题 魅客科创中心

6.2.1 双向链表基本操作

  • 尾部插入：
    DoublyNode* insertBack(DoublyNode* head, int data) {
    DoublyNode* newNode = createDoublyNode(data);
    
    if (!head) {
        return newNode;
    }
    
    // 找到尾节点
    DoublyNode* current = head;
    while (current->next) {
        current = current->next;
    }
    
    current->next = newNode;
    newNode->prev = current;
    return head;
}
  • 查找节点：
    DoublyNode* findDoublyNode(DoublyNode* head, int data) {
    DoublyNode* current = head;
    while (current) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return nullptr;  // 未找到
}
返回目录 信息学 指针与链表专题 魅客科创中心

6.2.2 双向链表基本操作

  • 获取链表长度：
    int getDoublyLength(DoublyNode* head) {
    int count = 0;
    DoublyNode* current = head;
    while (current) {
        count++;
        current = current->next;
    }
    return count;
}
  • 指定位置插入：
    DoublyNode* insertAt(DoublyNode* head, int index, int data) {
    if (index < 0) {
        return head;  // 无效索引
    }
    
    if (index == 0) {
        return insertFront(head, data);
    }
    
    DoublyNode* current = head;
    int currentIndex = 0;
    
    // 找到插入位置的节点
    while (current && currentIndex < index) {
        current = current->next;
        currentIndex++;
    }
    
    if (!current) {
        return head;  // 索引越界
    }
    
    DoublyNode* newNode = createDoublyNode(data);
    newNode->next = current;
    newNode->prev = current->prev;
    
    if (current->prev) {
        current->prev->next = newNode;
    }
    current->prev = newNode;
    
    return (index == 0) ? newNode : head;
}
返回目录 信息学 指针与链表专题 魅客科创中心

6.2.3 双向链表基本操作

  • 头部删除：
    DoublyNode* deleteFront(DoublyNode* head) {
    if (!head) {
        return nullptr;
    }
    
    DoublyNode* newHead = head->next;
    if (newHead) {
        newHead->prev = nullptr;
    }
    
    delete head;
    return newHead;
}
  • 尾部删除：
    DoublyNode* deleteBack(DoublyNode* head) {
    if (!head) {
        return nullptr;
    }
    
    if (!head->next) {
        delete head;
        return nullptr;
    }
    
    // 找到尾节点
    DoublyNode* current = head;
    while (current->next) {
        current = current->next;
    }
    
    current->prev->next = nullptr;
    delete current;
    return head;
}
返回目录 信息学 指针与链表专题 魅客科创中心

6.2.4 双向链表基本操作

  • 指定位置删除：
    DoublyNode* deleteAt(DoublyNode* head, int index) {
    if (!head || index < 0) {
        return head;
    }
    
    if (index == 0) {
        return deleteFront(head);
    }
    
    DoublyNode* current = head;
    int currentIndex = 0;
    
    // 找到要删除的节点
    while (current && currentIndex < index) {
        current = current->next;
        currentIndex++;
    }
    
    if (!current) {
        return head;  // 索引越界
    }
    
    if (current->prev) {
        current->prev->next = current->next;
    }
    if (current->next) {
        current->next->prev = current->prev;
    }
    
    delete current;
    return (index == 0) ? current->next : head;
}
  • 释放整个双向链表：
    void deleteDoublyList(DoublyNode* head) {
    DoublyNode* current = head;
    while (current) {
        DoublyNode* next = current->next;
        delete current;
        current = next;
    }
}
返回目录 信息学 指针与链表专题 魅客科创中心

6.3 双向链表的高级操作

前向遍历显示：

void displayForward(DoublyNode* head) {
    DoublyNode* current = head;
    while (current) {
        cout << current->data;
        if (current->next) {
            cout << " <-> ";
        }
        current = current->next;
    }
    cout << endl;
}

后向遍历显示：

void displayBackward(DoublyNode* head) {
    if (!head) return;
    
    // 先找到尾节点
    DoublyNode* tail = head;
    while (tail->next) {
        tail = tail->next;
    }
    
    // 从尾节点向前遍历
    DoublyNode* current = tail;
    while (current) {
        cout << current->data;
        if (current->prev) {
            cout << " <-> ";
        }
        current = current->prev;
    }
    cout << endl;
}
返回目录 信息学 指针与链表专题 魅客科创中心

7. 循环链表

7.1 循环链表的概念

  • 循环链表的定义：
    • 链表中最后一个节点的指针指向头节点
    • 形成一个环形结构，没有真正的尾节点
    • 可以从任意节点开始遍历整个链表
    • 分为循环单链表和循环双链表
  • 循环链表的特点：
    • 环形结构：首尾相连，形成闭环
    • 无限遍历：可以无限循环遍历
    • 无头无尾：没有明确的开始和结束
    • 特殊应用：适合轮转调度等场景
  • 循环链表类型：
    • 循环单链表：只有next指针，尾指向头
    • 循环双链表：prev和next指针，首尾相连
    • 循环多链表：多个指针域的循环结构
  • 循环链表的优势：
    • 均匀访问：从任意节点访问效率相同
    • 轮转操作：天然支持轮转和循环
    • 内存连续：逻辑上的连续性
    • 算法简化：某些算法实现更简单
返回目录 信息学 指针与链表专题 魅客科创中心

7.2 循环单链表的基本操作

  • 循环单链表节点定义：

    struct CircularNode {
    int data;
    CircularNode* next;
    CircularNode(int x) : data(x), next(nullptr) {}
};

  • 创建新节点：

    CircularNode* createCircularNode(int data) {
    return new CircularNode(data);
}
  • 插入节点（尾部插入）：
    CircularNode* insertCircular(CircularNode* tail, int data) {
    CircularNode* newNode = createCircularNode(data);
    
    if (!tail) {
        // 第一个节点，指向自己
        tail = newNode;
        tail->next = tail;
    } else {
        // 在尾部插入
        newNode->next = tail->next;  // 新节点指向头节点
        tail->next = newNode;        // 尾节点指向新节点
        tail = newNode;               // 更新尾节点
    }
    return tail;
}
返回目录 信息学 指针与链表专题 魅客科创中心

8. 经典例题解析

8.1 CSP-J 2022 链表合并

题目描述：合并两个有序链表

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }
    
    current->next = l1 ? l1 : l2;
    
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

解题思路：

  1. 创建虚拟头节点

    • 使用dummy节点简化边界处理
    • 避免单独处理头节点情况

  2. 双指针遍历

    • 两个指针分别遍历两个链表
    • 每次选择较小的节点连接

  3. 处理剩余节点

    • 一个链表遍历完后，直接连接剩余部分
    • 保持原有顺序不变

  4. 复杂度分析

    • 时间复杂度：O(m+n)
    • 空间复杂度：O(1)

关键技巧：

  • 虚拟头节点简化代码
  • 指针移动的时机选择
  • 内存管理避免泄漏
返回目录 信息学 指针与链表专题 魅客科创中心

8.2 CSP-S 2021 链表环检测

题目描述：判断链表是否有环并找出环的入口

bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast && fast->next) {
        if (slow == fast) return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return false;
}

ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    // 快慢指针找相遇点
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    
    if (!fast || !fast->next) return nullptr;
    
    // 找环的入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}

解题思路：

  1. 环检测原理

    • 快指针走两步，慢指针走一步
    • 如果有环，两指针必然相遇
    • 无环时快指针会先到达终点

  2. 找环入口

    • 相遇后，一个指针从头开始
    • 两指针同步前进，再次相遇即为入口
    • 基于数学推导的正确性

  3. 边界条件

    • 空链表或单节点链表
    • 快指针移动的安全性检查

  4. 复杂度分析

    • 时间复杂度：O(n)
    • 空间复杂度：O(1)

数学证明：

  • 设头到环入口距离为a，环长度为b
  • 相遇时快指针走了f步，慢指针走了s步
  • f = 2s，且f-s = nb（n圈）
  • 解得s = nb，即相遇点距环入口nb步
  • 从头走到入口需要a步，从相遇点走到入口也需要a步
返回目录 信息学 指针与链表专题 魅客科创中心

8.3 POJ 2367 链式基数排序

题目描述：使用链表实现基数排序

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

void radixSort(int arr[], int n) {
    const int RADIX = 10;
    Node* buckets[RADIX] = {nullptr};
    
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        maxVal = max(maxVal, arr[i]);
    }
    
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        // 分配到桶中
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % RADIX;
            Node* newNode = new Node(arr[i]);
            
            if (!buckets[digit]) {
                buckets[digit] = newNode;
            } else {
                Node* current = buckets[digit];
                while (current->next) {
                    current = current->next;
                }
                current->next = newNode;
            }
        }
        
        // 从桶中收集
        int index = 0;
        for (int i = 0; i < RADIX; i++) {
            Node* current = buckets[i];
            while (current) {
                arr[index++] = current->data;
                Node* temp = current;
                current = current->next;
                delete temp;
            }
            buckets[i] = nullptr;
        }
    }
}

解题思路：

  1. 基数排序原理

    • 按位数从低到高进行排序
    • 每一位使用稳定的排序算法
    • 链表作为桶，保持插入顺序

  2. 链表桶操作

    • 10个链表对应0-9的数字
    • 按当前位数值分配到对应桶
    • 按桶顺序收集，保持稳定性

  3. 算法步骤

    • 找最大值确定位数
    • 对每一位进行分配和收集
    • 重复直到最高位

  4. 复杂度分析

    • 时间复杂度：O(d(n+k))，d为位数，k为基数
    • 空间复杂度：O(n+k)

优化要点：

  • 使用链表保持稳定性
  • 及时释放内存避免泄漏
  • 确定合适的基数大小
返回目录 信息学 指针与链表专题 魅客科创中心

8.4 POJ 2492 链表实现并查集

题目描述：使用链表实现并查集

struct ListNode {
    int data;
    ListNode* next;
    ListNode* parent;
    int rank;
    ListNode(int x) : data(x), next(nullptr), parent(this), rank(0) {}
};

class DisjointSet {
private:
    unordered_map<int, ListNode*> nodes;
    
public:
    void makeSet(int x) {
        if (nodes.find(x) == nodes.end()) {
            nodes[x] = new ListNode(x);
        }
    }
    
    ListNode* findSet(ListNode* node) {
        if (node->parent != node) {
            node->parent = findSet(node->parent);
        }
        return node->parent;
    }
    
    int findSet(int x) {
        if (nodes.find(x) == nodes.end()) {
            makeSet(x);
        }
        return findSet(nodes[x])->data;
    }
    
    void unionSets(int x, int y) {
        makeSet(x);
        makeSet(y);
        
        ListNode* rootX = findSet(nodes[x]);
        ListNode* rootY = findSet(nodes[y]);
        
        if (rootX == rootY) return;
        
        if (rootX->rank < rootY->rank) {
            rootX->parent = rootY;
        } else if (rootX->rank > rootY->rank) {
            rootY->parent = rootX;
        } else {
            rootY->parent = rootX;
            rootX->rank++;
        }
    }
    
    bool sameSet(int x, int y) {
        return findSet(x) == findSet(y);
    }
};

解题思路：

  1. 并查集数据结构

    • 每个元素是一个链表节点
    • parent指针指向集合代表
    • rank用于优化合并操作

  2. 路径压缩优化

    • find操作时压缩路径
    • 将节点直接指向根节点
    • 递归实现路径压缩

  3. 按秩合并优化

    • rank表示树的深度
    • 将浅树合并到深树
    • 避免树深度过快增长

  4. 复杂度分析

    • 查找操作：接近O(1)
    • 合并操作：接近O(1)
    • 空间复杂度：O(n)

应用场景：

  • 连通性问题
  • 等价关系判断
  • 动态连通性维护
  • 图论算法基础
返回目录 信息学 指针与链表专题 魅客科创中心

8.5 USACO 1.3 链表实现队列

题目描述：使用链表实现队列操作

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

class LinkedListQueue {
private:
    Node* front;
    Node* rear;
    int size;
    
public:
    LinkedListQueue() : front(nullptr), rear(nullptr), size(0) {}
    ~LinkedListQueue() {
        while (!isEmpty()) {
            dequeue();
        }
    }
    
    void enqueue(int x) {
        Node* newNode = new Node(x);
        
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) {
            throw runtime_error("Queue is empty");
        }
        
        Node* temp = front;
        int value = temp->data;
        front = front->next;
        
        if (!front) {
            rear = nullptr;
        }
        
        delete temp;
        size--;
        return value;
    }
    
    int peek() const {
        if (isEmpty()) {
            throw runtime_error("Queue is empty");
        }
        return front->data;
    }
    
    bool isEmpty() const {
        return front == nullptr;
    }
    
    int getSize() const {
        return size;
    }
};

解题思路：

  1. 队列FIFO特性

    • 先进先出的数据结构
    • 入队操作在尾部进行
    • 出队操作在头部进行

  2. 双指针设计

    • front指针指向队头
    • rear指针指向队尾
    • 提高操作效率到O(1)

  3. 边界条件处理

    • 空队列的判断和处理
    • 单元素队列的特殊情况
    • 析构函数的内存清理

  4. 操作复杂度

    • 入队：O(1)
    • 出队：O(1)
    • 查看队首：O(1)
    • 空间复杂度：O(n)

设计要点：

  • 维护头尾指针避免遍历
  • 动态内存管理
  • 异常安全性考虑
  • 容量无限制的优势
返回目录 信息学 指针与链表专题 魅客科创中心

8.6 USACO 2.2 链表实现栈

题目描述：使用链表实现栈操作

struct StackNode {
    int data;
    StackNode* next;
    StackNode(int x) : data(x), next(nullptr) {}
};

class LinkedListStack {
private:
    StackNode* top;
    int size;
    
public:
    LinkedListStack() : top(nullptr), size(0) {}
    ~LinkedListStack() {
        while (!isEmpty()) {
            pop();
        }
    }
    
    void push(int x) {
        StackNode* newNode = new StackNode(x);
        newNode->next = top;
        top = newNode;
        size++;
    }
    
    int pop() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        
        StackNode* temp = top;
        int value = temp->data;
        top = top->next;
        
        delete temp;
        size--;
        return value;
    }
    
    int peek() const {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        return top->data;
    }
    
    bool isEmpty() const {
        return top == nullptr;
    }
    
    int getSize() const {
        return size;
    }
};

解题思路：

  1. 栈LIFO特性

    • 后进先出的数据结构
    • 所有操作都在栈顶进行
    • 天然适合链表实现

  2. 头节点作为栈顶

    • 链表头节点对应栈顶
    • 简化插入和删除操作
    • 避免维护尾指针

  3. 操作实现

    • push：在头部插入节点
    • pop：删除头部节点
    • peek：查看头部节点数据

  4. 复杂度分析

    • push：O(1)
    • pop：O(1)
    • peek：O(1)
    • 空间复杂度：O(n)

优势特点：

  • 动态扩容，无容量限制
  • 所有操作都是常数时间
  • 内存使用精确，无浪费
  • 实现简单直观
返回目录 信息学 指针与链表专题 魅客科创中心

8.7 CSES 1193 链表反转

题目描述：反转链表的多种方法

class Solution {
public:
    // 方法1：迭代反转
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        
        while (current) {
            ListNode* next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
    }
    
    // 方法2：递归反转
    ListNode* reverseListRecursive(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* newHead = reverseListRecursive(head->next);
        head->next->next = head;
        head->next = nullptr;
        
        return newHead;
    }
    
    // 方法3：头插法反转
    ListNode* reverseListInsert(ListNode* head) {
        ListNode dummy(0);
        dummy.next = nullptr;
        
        while (head) {
            ListNode* next = head->next;
            head->next = dummy.next;
            dummy.next = head;
            head = next;
        }
        
        return dummy.next;
    }
};

解题思路：

  1. 迭代法（三指针）

    • 使用prev、current、next三个指针
    • 逐个反转指针方向
    • 时间复杂度O(n)，空间复杂度O(1)

  2. 递归法

    • 递归到链表末尾
    • 反转时从后向前处理
    • 时间复杂度O(n)，空间复杂度O(n)

  3. 头插法

    • 创建虚拟头节点
    • 使用头插法构建新链表
    • 时间复杂度O(n)，空间复杂度O(1)

  4. 方法比较

    • 迭代法：空间效率最高
    • 递归法：代码简洁但栈空间消耗大
    • 头插法：思路清晰，易于理解

选择建议：

  • 面试推荐迭代法（空间最优）
  • 代码简洁选递归法
  • 教学演示选头插法
返回目录 信息学 指针与链表专题 魅客科创中心

8.8 CSES 1195 链表排序

题目描述：链表排序（归并排序）

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        // 找到中间节点
        ListNode* mid = findMiddle(head);
        ListNode* right = mid->next;
        mid->next = nullptr;
        
        // 递归排序
        ListNode* left = sortList(head);
        right = sortList(right);
        
        // 合并有序链表
        return merge(left, right);
    }
    
private:
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        
        current->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

解题思路：

  1. 归并排序选择

    • 链表不适合快速排序（随机访问困难）
    • 归并排序天然适合链表
    • 稳定排序，时间复杂度优秀

  2. 找中点技巧

    • 快慢指针找到链表中点
    • fast从head->next开始避免偶数长度问题
    • 断开链表分成两部分

  3. 递归排序

    • 递归排序左右两部分
    • 基线条件：空链表或单节点
    • 递归深度O(log n)

  4. 合并有序链表

    • 类似合并两个有序数组
    • 使用虚拟头节点简化操作
    • 保持稳定性

  5. 复杂度分析

    • 时间复杂度：O(n log n)
    • 空间复杂度：O(log n)递归栈

优化要点：

  • 快慢指针找中点的技巧
  • 虚拟头节点简化合并
  • 递归深度的控制
返回目录 信息学 指针与链表专题 魅客科创中心

9. 练习题推荐

9.1 基础练习题

指针基础：

  • HDU 2020 绝对值排序（指针数组）
  • HDU 2031 进制转换（指针参数）
  • POJ 2388 指针排序练习
  • CSES 1069 指针基础操作

数组与指针：

  • HDU 2014 青年歌手大奖赛（数组指针）
  • HDU 2041 超级楼梯（指针遍历）
  • POJ 2387 指针数组应用
  • CSES 1072 二维数组指针

字符指针：

  • HDU 2021 发工资（字符串处理）
  • HDU 2022 海选女主角（字符数组）
  • POJ 3981 字符串替换
  • CSES 1073 字符串指针操作

结构体指针：

  • HDU 2023 求平均成绩（结构体数组）
  • HDU 2024 C语言合法标识符（结构体指针）
  • POJ 2386 结构体链表基础
  • CSES 1074 结构体排序
返回目录 信息学 指针与链表专题 魅客科创中心

9.1 链表基础

单向链表：

  • HDU 2032 杨辉三角（链表构建）
  • HDU 2033 人见人爱A+B（链表操作）
  • POJ 2388 链表排序
  • CSES 1075 链表基础操作

双向链表：

  • HDU 2034 人见人爱A-B（双向链表）
  • HDU 2035 人见人爱A^B（链表遍历）
  • POJ 2389 双向链表应用
  • CSES 1076 链表插入删除
返回目录 信息学 指针与链表专题 魅客科创中心

9.2 进阶练习题

链表算法：

  • HDU 2042 不容易系列（链表递归）
  • HDU 2043 密码（链表应用）
  • POJ 2299 链表归并排序
  • CSES 1193 链表反转

复杂链表操作：

  • HDU 2044 一只小蜜蜂（链表DP）
  • HDU 2045 不容易系列之（链表递推）
  • POJ 2492 并查集链表实现
  • CSES 1195 链表排序
**循环链表**： - **HDU 2046** 骨牌铺方格（循环链表） - **HDU 2047** 阿牛的EOF牛肉串（循环链表） - **POJ 2367** 约瑟夫环问题 - **CSES 1196** 循环链表应用

高级数据结构：

  • HDU 2048 神、上帝以及老天爷（概率链表）
  • HDU 2049 不容易系列之（链表组合）
  • POJ 2418 字典树链表实现
  • CSES 1197 高级链表操作
返回目录 信息学 指针与链表专题 魅客科创中心
指针与链表专题

#c

这个讲义使用了Awesome Marp主题的蓝色风格。 内容针对竞赛选手设计，注重基础概念和实际应用。

封底页： - 感谢学生的参与 - 提供联系方式或其他资源 - 鼓励学生继续学习和实践