C/C++核心知识点详解

C/C++核心知识点详解

1. 变量的声明和定义有什么区别？

在C/C++中，变量的声明和定义是两个不同的概念：

• 定义：为变量分配内存空间和地址，只能在程序中出现一次
• 声明：告诉编译器变量的类型和名称，但不分配内存，可以出现多次

当我们使用extern关键字修饰变量时，表示这是一个变量的声明，实际定义在其他文件或当前文件的后面部分。

// 变量声明（不分配内存）
extern int counter;

// 变量定义（分配内存）
int counter = 0;

实际应用：在大型项目中，通常会将变量定义在一个源文件中，然后在头文件中使用extern进行声明，这样其他源文件包含该头文件后就能使用这个变量。

2. 不同类型变量与"零值"的比较方法

在编程中，不同类型的变量与"零值"的比较方法各不相同，正确的比较方式如下：

bool型变量

// bool型变量可以直接作为条件判断
if(flag) 
{
    // flag为true时执行
} 
else 
{
    // flag为false时执行
}

int型变量

// 注意：将0放在左边是一种良好的编程习惯
if(0 != flag) 
{
    // flag不等于0时执行
} 
else 
{
    // flag等于0时执行
}

指针型变量

// 将NULL放在左边可以避免误写成赋值语句
if(NULL == ptr) 
{
    // 指针为空时执行
} 
else 
{
    // 指针不为空时执行
}

float型变量

// 浮点数比较需要考虑精度问题，使用一个极小值NORM作为判断标准
if((flag >= -NORM) && (flag <= NORM)) 
{
    // 浮点数接近0时执行
}

编程技巧：在进行等值比较时，建议将常量值放在左边（如0 == x而非x == 0）。这样如果不小心将==写成=，编译器会报错（因为不能对常量赋值），避免了难以发现的逻辑错误。

3. sizeof和strlen的区别

sizeof和strlen是C/C++中常用的两个用于获取大小的工具，但它们有本质区别：

// 示例代码
char str[] = "hello";
printf("sizeof(str) = %d\n", sizeof(str));  // 输出6（包含结尾的'\0'）
printf("strlen(str) = %d\n", strlen(str));  // 输出5（不包含结尾的'\0'）

char *p = str;
printf("sizeof(p) = %d\n", sizeof(p));      // 输出4或8（指针的大小，取决于32位或64位系统）
printf("strlen(p) = %d\n", strlen(p));      // 输出5（字符串的长度）

注意事项：sizeof是操作符而非函数，这是初学者容易混淆的点。它在编译时就能确定结果，而strlen需要在运行时遍历字符串才能计算长度。

4. C语言和C++中static关键字的区别

static关键字在C和C++中都很常用，但C++中的static功能更加丰富：

C语言中的static

• 修饰局部变量：使其具有静态存储期，函数调用结束后变量不会销毁
• 修饰全局变量：将变量的作用域限制在当前文件内
• 修饰函数：将函数的作用域限制在当前文件内

C++中的static（包含C的全部功能，并增加了以下功能）

• 修饰类的成员变量：所有对象共享一个静态成员变量
• 修饰类的成员函数：不依赖于对象实例，可通过类名直接调用

// C++中static的示例
class Counter {
public:
    static int count;       // 静态成员变量声明
    static void showCount() // 静态成员函数
    {
        cout << "Count: " << count << endl;
    }
};

int Counter::count = 0;     // 静态成员变量定义

int main() {
    Counter c1, c2;
    c1.count = 10;          // 通过对象访问
    Counter::count = 20;    // 通过类名访问
    Counter::showCount();   // 输出：Count: 20
    return 0;
}

实际应用：静态成员变量常用于记录类的实例数量、共享配置等；静态成员函数常用于不需要访问对象状态的工具函数。

5. C中的malloc和C++中的new有什么区别

malloc和new都用于动态内存分配，但有以下关键区别：

// malloc示例
int *p1 = (int*)malloc(sizeof(int));
*p1 = 10;
free(p1);

// new示例
int *p2 = new int;
*p2 = 10;
delete p2;

// 对象分配对比
class Test {
public:
    Test() { cout << "构造函数" << endl; }
    ~Test() { cout << "析构函数" << endl; }
};

Test *t1 = (Test*)malloc(sizeof(Test)); // 不调用构造函数
free(t1);                               // 不调用析构函数

Test *t2 = new Test;                    // 调用构造函数
delete t2;                              // 调用析构函数

注意事项：malloc和free必须配对使用，new和delete必须配对使用，不能交叉使用，否则会导致内存泄漏或程序崩溃。

6. 如何编写一个"标准"的宏MIN

宏定义是C/C++中常用的代码复用方式，但需要注意其副作用：

// 标准的MIN宏定义
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

上面的宏定义看似正确，但在某些情况下会产生副作用：

int x = 5;
int *p = &x;
// 下面的调用会导致p指针自增两次！
int result = MIN(++*p, 10);
// 展开后相当于: ((++*p) <= (10) ? (++*p) : (10))

改进版本：使用临时变量避免副作用

#define MIN(a, b) ({ \
    typeof(a) _a = (a); \
    typeof(b) _b = (b); \
    _a <= _b ? _a : _b; \
})

最佳实践：在C++中，应尽量使用内联函数代替宏定义，更加类型安全且没有副作用：

template<typename T>
inline T min(T a, T b) {
    return a <= b ? a : b;
}

7. 指针可以是volatile吗？

是的，指针可以被volatile修饰。volatile关键字告诉编译器，变量的值可能会在程序的控制之外被改变（如硬件、中断服务程序等），因此编译器不应对这类变量的访问进行优化。

指针被volatile修饰有两种情况：

1. 指针本身是volatile（指针地址可能被外部修改）
2. 指针指向的内容是volatile（指针指向的内容可能被外部修改）

// 指针本身是volatile
int *volatile p;  

// 指针指向的内容是volatile
volatile int *p;  

// 指针本身和指向的内容都是volatile
volatile int *volatile p;

实际应用场景：

• 内存映射的硬件寄存器
• 多线程共享的变量
• 中断服务程序修改的变量

// 中断服务程序修改buffer指针的例子
volatile char *buffer;

// 中断服务程序
void interrupt_handler() {
    buffer = new_buffer_location;  // 修改指针值
}

8. 数组名a和&a的区别

在C/C++中，数组名和数组的地址有微妙但重要的区别：

• 数组名a：表示数组首元素的地址，类型为元素类型*
• 数组的地址&a：表示整个数组的地址，类型为数组类型*

虽然它们的数值可能相同，但类型不同，这会影响指针运算：

#include <stdio.h>
void main(void) {
    int a[5] = {1, 2, 3, 4, 5};
    int *ptr1 = (int *)(&a + 1);  // &a是数组的地址，+1后指向数组后面的位置
    int *ptr2 = (int *)(a + 1);   // a是首元素地址，+1后指向第二个元素
    
    printf("%d, %d\n", *(a + 1), *(ptr1 - 1));  // 输出：2, 5
    printf("%d\n", *ptr2);                       // 输出：2
}

解析：

• *(a + 1)：数组第二个元素，值为2
• *(ptr1 - 1)：ptr1指向数组后面的位置，-1后指向数组最后一个元素，值为5
• *ptr2：指向数组第二个元素，值为2

指针运算的关键：指针加1，实际上是加上指针所指向类型的大小。

9. C/C++程序编译的内存分配情况

C/C++程序在内存中被分为5个区域：

1. 代码区（Text Segment）

• 存放程序的机器码
• 只读，防止程序意外修改指令
• 可共享，多个程序可共用一份代码

2. 数据区（Data Segment）

• 存放已初始化的全局变量和静态变量
• 程序启动时分配，程序结束时释放
• 分为只读数据区和读写数据区

3. BSS区（Block Started by Symbol）

• 存放未初始化的全局变量和静态变量
• 程序启动时被初始化为0
• 程序结束时释放

4. 堆区（Heap）

• 动态分配的内存（malloc/new）
• 由程序员手动管理（申请/释放）
• 从低地址向高地址增长
• 容易产生内存泄漏和碎片化

5. 栈区（Stack）

• 存放函数参数、局部变量等
• 由编译器自动管理
• 从高地址向低地址增长
• 容量有限但管理高效

高地址  +------------------+
        |       栈区       | <-- 自动变量，函数参数
        |        ↓        |
        |                 |
        |                 |
        |        ↑        |
        |       堆区       | <-- 动态分配的内存
        +------------------+
        |      BSS区       | <-- 未初始化的全局变量、静态变量
        +------------------+
        |      数据区      | <-- 已初始化的全局变量、静态变量
        +------------------+
低地址  |      代码区      | <-- 程序指令
        +------------------+

内存分配方式：

1. 静态分配：编译时确定大小，整个程序运行期间存在（全局变量、静态变量）
2. 栈分配：函数调用时分配，返回时自动释放（局部变量）
3. 堆分配：运行时动态分配，需手动释放（malloc/new分配的内存）

10. strcpy、sprintf与memcpy的区别

这三个函数都可以用于数据复制，但适用场景和特点不同：

strcpy

• 功能：复制字符串
• 原型：char *strcpy(char *dest, const char *src);
• 特点：
  • 源和目标都必须是字符串（以’\0’结尾）
  • 复制到遇到’\0’为止
  • 不检查缓冲区大小，可能导致溢出

sprintf

• 功能：格式化字符串并输出到缓冲区
• 原型：int sprintf(char *str, const char *format, ...);
• 特点：
  • 可处理多种数据类型并转换为字符串
  • 支持格式化控制
  • 效率较低但功能强大
  • 返回写入的字符数

memcpy

• 功能：内存块复制
• 原型：void *memcpy(void *dest, const void *src, size_t n);
• 特点：
  • 按字节复制指定长度的内存
  • 可复制任何类型的数据
  • 不检查’\0’，完全按指定长度复制
  • 效率最高

// 使用示例
char src[] = "Hello World";
char dest1[20], dest2[20], dest3[20];

// 使用strcpy
strcpy(dest1, src);
printf("strcpy: %s\n", dest1);  // 输出：Hello World

// 使用sprintf
sprintf(dest2, "%s", src);
printf("sprintf: %s\n", dest2); // 输出：Hello World

// 使用memcpy
memcpy(dest3, src, strlen(src) + 1);  // +1复制结尾的'\0'
printf("memcpy: %s\n", dest3);  // 输出：Hello World

// sprintf的格式化功能
int num = 123;
sprintf(dest2, "数字: %d", num);
printf("sprintf格式化: %s\n", dest2);  // 输出：数字: 123

性能对比：memcpy > strcpy > sprintf

安全版本：现代编程中应优先使用更安全的版本：strncpy、snprintf和memcpy_s，它们会检查缓冲区大小，防止溢出。

11. 如何设置特定地址的变量值

在某些特殊场景（如嵌入式系统、驱动开发）中，需要直接操作特定内存地址：

// 设置地址为0x67a9的整型变量值为0xaa66
int *ptr;
ptr = (int *)0x67a9;  // 将地址0x67a9强制转换为int指针
*ptr = 0xaa66;        // 通过指针写入值

注意事项：

1. 这种操作在普通应用程序中可能导致段错误
2. 在嵌入式系统中常用于访问硬件寄存器
3. 不同平台的指针大小可能不同（32位系统4字节，64位系统8字节）
4. 需要考虑内存对齐问题

实际应用：

// 在嵌入式系统中设置GPIO寄存器
#define GPIO_BASE 0x40020000
#define GPIO_ODR  (GPIO_BASE + 0x14)  // 输出数据寄存器偏移量

// 设置GPIO引脚输出高电平
*(volatile uint32_t *)GPIO_ODR |= (1 << 5);  // 设置第5位为1

12. 面向对象的三大特征

面向对象编程的三大核心特征是封装、继承和多态：

1. 封装（Encapsulation）

将数据和操作数据的方法绑定在一起，对外部隐藏实现细节，只暴露必要的接口。

优点：

• 提高代码安全性
• 降低耦合度
• 便于维护和修改

class BankAccount {
private:
    double balance;  // 私有数据成员
    
public:
    // 公开的接口方法
    void deposit(double amount) {
        if (amount > 0) {
            balance += amount;
        }
    }
    
    bool withdraw(double amount) {
        if (amount > 0 && balance >= amount) {
            balance -= amount;
            return true;
        }
        return false;
    }
    
    double getBalance() const {
        return balance;
    }
};

2. 继承（Inheritance）

允许创建新类（子类）继承现有类（父类）的属性和方法。

继承的三种形式：

• 实现继承：子类继承父类的实现代码
• 接口继承：子类仅继承方法声明，需自行实现（如C++的纯虚函数）
• 可视继承：子类继承父类的界面和实现（主要用于GUI编程）

// 基类
class Animal {
protected:
    string name;
    
public:
    Animal(string n) : name(n) {}
    virtual void makeSound() {
        cout << "动物发出声音" << endl;
    }
};

// 派生类
class Dog : public Animal {
public:
    Dog(string n) : Animal(n) {}
    void makeSound() override {
        cout << name << "汪汪叫" << endl;
    }
};

3. 多态（Polymorphism）

允许不同类的对象对同一消息做出不同的响应。

多态的两种形式：

• 编译时多态（静态多态）：通过函数重载和运算符重载实现
• 运行时多态（动态多态）：通过虚函数和继承实现

// 运行时多态示例
Animal *animal1 = new Animal("动物");
Animal *animal2 = new Dog("小狗");

animal1->makeSound();  // 输出：动物发出声音
animal2->makeSound();  // 输出：小狗汪汪叫

// 编译时多态示例（函数重载）
class Calculator {
public:
    int add(int a, int b) {
        return a + b;
    }
    
    double add(double a, double b) {
        return a + b;
    }
};

面向对象编程的优势：

• 更接近人类思维方式
• 代码复用性高
• 易于维护和扩展
• 提高开发效率

13. C++的空类有哪些成员函数

C++编译器会为空类自动生成六个默认成员函数：

1. 默认构造函数：创建对象时调用
2. 默认析构函数：销毁对象时调用
3. 拷贝构造函数：用一个对象初始化另一个对象时调用
4. 拷贝赋值运算符：将一个对象赋值给另一个已存在的对象时调用
5. 取址运算符：获取对象地址时调用
6. 取址运算符const版本：获取const对象地址时调用

class Empty {};

// 等价于以下定义
class Empty {
public:
    // 默认构造函数
    Empty() {}
    
    // 默认析构函数
    ~Empty() {}
    
    // 拷贝构造函数
    Empty(const Empty& other) {}
    
    // 拷贝赋值运算符
    Empty& operator=(const Empty& other) { return *this; }
    
    // 取址运算符
    Empty* operator&() { return this; }
    
    // 取址运算符const版本
    const Empty* operator&() const { return this; }
};

注意事项：

1. 这些函数只有在被使用时才会被编译器生成
2. C++11后还会生成移动构造函数和移动赋值运算符
3. 如果自定义了其中任何一个函数，编译器就不会生成对应的默认版本

14. 拷贝构造函数和赋值运算符的区别

拷贝构造函数和赋值运算符都用于对象复制，但有重要区别：

拷贝构造函数

• 调用时机：创建新对象时
• 函数原型：ClassName(const ClassName& other);
• 特点：
  • 创建一个新对象
  • 不需要检查自赋值
  • 不需要释放已有资源

赋值运算符

• 调用时机：已有对象间赋值时
• 函数原型：ClassName& operator=(const ClassName& other);
• 特点：
  • 操作已存在的对象
  • 需要检查自赋值
  • 需要释放对象已有资源

class MyString {
private:
    char* data;
    
public:
    // 构造函数
    MyString(const char* str = nullptr) {
        if (str) {
            data = new char[strlen(str) + 1];
            strcpy(data, str);
        } else {
            data = new char[1];
            data[0] = '\0';
        }
    }
    
    // 析构函数
    ~MyString() {
        delete[] data;
    }
    
    // 拷贝构造函数
    MyString(const MyString& other) {
        data = new char[strlen(other.data) + 1];
        strcpy(data, other.data);
    }
    
    // 赋值运算符
    MyString& operator=(const MyString& other) {
        // 检查自赋值
        if (this == &other) {
            return *this;
        }
        
        // 释放原有资源
        delete[] data;
        
        // 分配新资源并复制
        data = new char[strlen(other.data) + 1];
        strcpy(data, other.data);
        
        return *this;
    }
};

// 使用示例
MyString s1("Hello");       // 构造函数
MyString s2 = s1;           // 拷贝构造函数
MyString s3;                // 默认构造函数
s3 = s1;                    // 赋值运算符

深拷贝与浅拷贝：

• 浅拷贝：仅复制指针值，导致多个对象指向同一内存
• 深拷贝：复制指针指向的内容，每个对象有独立的内存

最佳实践：当类中包含指针成员时，必须自定义拷贝构造函数和赋值运算符，实现深拷贝，避免多次释放同一内存的错误。

15. 如何设计一个不能被继承的类

在C++中，有几种方法可以创建不能被继承的类：

方法1：使用final关键字（C++11及以上）

class FinalClass final {
    // 类实现...
};

// 以下代码将编译错误
class Derived : public FinalClass {  // 错误：不能从final类继承
    // ...
};

方法2：使用私有构造函数和友元类

template <typename T>
class A {
    friend T;  // 将T声明为友元，使其能访问私有构造函数
private:
    A() {}     // 私有构造函数
    ~A() {}    // 私有析构函数
};

class B : virtual public A<B> {
public:
    B() {}
    ~B() {}
};

// 尝试从B继承的类将无法访问A的构造函数
class C : virtual public B {
public:
    C() {}     // 编译错误：无法访问A的构造函数
    ~C() {}
};

原理解析：

1. 类A的构造函数和析构函数都是私有的
2. 类B被声明为A的友元，因此可以访问A的私有成员
3. 类C继承自B，但不是A的友元，无法访问A的私有构造函数
4. 由于C++中构造子类对象必须先构造基类对象，所以C无法被实例化

方法3：使用虚拟继承和私有构造函数

class NonInheritable {
private:
    NonInheritable() {}
    friend class Access;
};

class Access : virtual NonInheritable {
public:
    Access() {}  // 可以访问NonInheritable的构造函数
};

// 任何尝试继承Access的类都会失败

实际应用：不可继承类在设计单例模式、工具类或防止继承滥用时非常有用。

16. 访问基类的私有虚函数

以下代码展示了如何通过指针操作访问基类的私有虚函数：

#include <iostream>
using namespace std;

class A {
public:
    virtual void g() {
        cout << "A::g" << endl;
    }
private:
    virtual void f() {
        cout << "A::f" << endl;
    }
};

class B : public A {
public:
    void g() override {
        cout << "B::g" << endl;
    }
    virtual void h() {
        cout << "B::h" << endl;
    }
};

typedef void(*Fun)(void);

int main() {
    B b;
    Fun pFun;
    
    for(int i = 0; i < 3; i++) {
        pFun = (Fun)*((int*)*((int*)(&b)) + i);
        pFun();
    }
    
    return 0;
}

输出结果：

B::g
A::f
B::h

代码解析：

1. &b获取对象b的地址
2. (int*)(&b)将对象地址转换为int指针
3. *((int*)(&b))获取对象的虚函数表地址
4. ((int*)*((int*)(&b)) + i)获取虚函数表中第i个函数的地址
5. (Fun)*((int*)*((int*)(&b)) + i)将函数地址转换为函数指针
6. pFun()调用该函数

虚函数表结构：

+-------------+
| B::g        | <- 虚函数表第一项
+-------------+
| A::f        | <- 私有虚函数，但仍在表中
+-------------+
| B::h        | <- 派生类新增的虚函数
+-------------+

注意事项：

• 虽然私有虚函数不能通过正常方式访问，但它们仍存在于虚函数表中
• 这种技术通常用于调试和逆向工程，不应在正常代码中使用
• 不同编译器的虚函数表实现可能有所不同

17. 类成员函数的重写、重载和隐藏的区别

在C++中，重写(Override)、重载(Overload)和隐藏(Hide)是三个容易混淆的概念：

重写(Override)

• 定义：派生类重新实现基类中的虚函数
• 条件：
  • 基类函数必须是虚函数(virtual)
  • 函数名、参数列表、返回类型必须完全相同
  • 派生类函数可以使用override关键字(C++11)明确表示意图
• 作用：实现运行时多态

class Base {
public:
    virtual void show() { cout << "Base::show()" << endl; }
};

class Derived : public Base {
public:
    void show() override { cout << "Derived::show()" << endl; }  // 重写
};

// 使用示例
Base* ptr = new Derived();
ptr->show();  // 输出：Derived::show()

重载(Overload)

• 定义：同一个类中定义多个同名但参数列表不同的函数
• 条件：
  • 函数名相同
  • 参数列表不同(类型、数量或顺序)
  • 返回类型可以相同也可以不同
• 作用：实现编译时多态

class Calculator {
public:
    int add(int a, int b) { return a + b; }                 // 原函数
    double add(double a, double b) { return a + b; }        // 重载
    int add(int a, int b, int c) { return a + b + c; }      // 重载
};

// 使用示例
Calculator calc;
cout << calc.add(1, 2) << endl;       // 调用第一个add
cout << calc.add(1.5, 2.5) << endl;   // 调用第二个add
cout << calc.add(1, 2, 3) << endl;    // 调用第三个add

隐藏(Hide)

• 定义：派生类定义了与基类同名的函数，但不满足重写条件
• 情况：
  • 基类函数不是虚函数
  • 函数名相同但参数列表不同
  • 函数名相同但基类函数是虚函数，派生类函数参数列表不同
• 作用：派生类函数会隐藏基类的所有同名函数，不论参数如何

class Base {
public:
    void display() { cout << "Base::display()" << endl; }
    void display(int x) { cout << "Base::display(int)" << endl; }
};

class Derived : public Base {
public:
    void display() { cout << "Derived::display()" << endl; }  // 隐藏基类的所有display函数
};

// 使用示例
Derived d;
d.display();     // 输出：Derived::display()
d.display(5);    // 错误：Derived类中没有接受int参数的display函数
d.Base::display(5);  // 正确：通过作用域解析运算符访问被隐藏的函数

总结对比：

• 重写：不同类中，虚函数，参数相同，运行时多态
• 重载：同一类中，同名函数，参数不同，编译时多态
• 隐藏：不同类中，同名函数，不满足重写条件，派生类对象无法直接访问基类被隐藏的函数

18. 多态实现的原理

C++多态的实现主要依靠虚函数表(vtable)和虚函数指针(vptr)机制：

虚函数表机制

1. 虚函数表创建：编译器为每个包含虚函数的类创建一个虚函数表(vtable)
2. 虚函数指针：编译器在每个对象的内存布局开头插入一个隐藏的指针(vptr)
3. 构造函数中的操作：对象构造时，vptr被初始化为指向该类的vtable
4. 虚函数调用：通过对象的vptr找到vtable，再从表中找到对应的函数地址

内存布局示例

类A的对象内存布局:          类A的虚函数表:
+----------------+          +----------------+
| vptr           |--------->| A::virtualFunc1|
+----------------+          +----------------+
| 成员变量1      |          | A::virtualFunc2|
+----------------+          +----------------+
| 成员变量2      |
+----------------+

类B(继承自A)的对象内存布局:  类B的虚函数表:
+----------------+          +----------------+
| vptr           |--------->| B::virtualFunc1|
+----------------+          +----------------+
| A的成员变量1   |          | A::virtualFunc2|
+----------------+          +----------------+
| A的成员变量2   |          | B::virtualFunc3|
+----------------+          +----------------+
| B的成员变量1   |
+----------------+

代码示例

#include <iostream>
using namespace std;

class Base {
public:
    virtual void func1() { cout << "Base::func1()" << endl; }
    virtual void func2() { cout << "Base::func2()" << endl; }
    void func3() { cout << "Base::func3()" << endl; }  // 非虚函数
};

class Derived : public Base {
public:
    void func1() override { cout << "Derived::func1()" << endl; }  // 重写
    // func2未重写，继承Base::func2
    void func3() { cout << "Derived::func3()" << endl; }  // 隐藏
    virtual void func4() { cout << "Derived::func4()" << endl; }  // 新增虚函数
};

int main() {
    Base* ptr = new Derived();
    ptr->func1();  // 输出：Derived::func1() - 多态调用
    ptr->func2();  // 输出：Base::func2() - 未重写，调用基类版本
    ptr->func3();  // 输出：Base::func3() - 非虚函数，静态绑定
    // ptr->func4();  // 错误：Base类没有func4函数
    
    delete ptr;
    return 0;
}

多态的关键点：

1. 基类指针或引用指向派生类对象
2. 通过该指针或引用调用虚函数
3. 在运行时根据对象的实际类型决定调用哪个函数

注意事项：

• 构造函数不能是虚函数，但析构函数通常应该是虚函数
• 虚函数机制会增加对象大小(vptr的大小)和函数调用开销
• 虚函数表在程序启动时创建，位于只读数据段
• 多重继承时虚函数表结构更复杂

19. 链表和数组的区别

链表和数组是两种基本的数据结构，各有优缺点：

存储结构

• 数组：连续内存空间，固定大小
• 链表：非连续内存空间，动态大小，每个节点包含数据和指向下一节点的指针

内存分配

• 数组：编译时静态分配或运行时动态分配，但大小固定
• 链表：运行时动态分配，可以根据需要增长或缩小

访问元素

• 数组：O(1)时间复杂度，通过索引直接访问
• 链表：O(n)时间复杂度，需要从头节点遍历

插入和删除

• 数组：O(n)时间复杂度，需要移动元素
• 链表：O(1)时间复杂度(如果已知位置)，只需修改指针

内存利用

• 数组：可能存在空间浪费(预分配)或不足(需要扩容)
• 链表：按需分配，但每个节点需要额外的指针空间

缓存局部性

• 数组：连续存储，缓存命中率高，对CPU友好
• 链表：随机存储，缓存命中率低

代码示例

// 数组示例
int arr[5] = {1, 2, 3, 4, 5};
cout << arr[2] << endl;  // 直接访问：O(1)

// 在索引2处插入值6
for(int i = 4; i >= 2; i--) {
    arr[i+1] = arr[i];  // 移动元素：O(n)
}
arr[2] = 6;

// 链表示例
struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

// 在已知节点后插入：O(1)
void insertAfter(Node* prevNode, int data) {
    if (prevNode == nullptr) return;
    
    Node* newNode = new Node(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// 查找值为3的节点：O(n)
Node* findNode(Node* head, int value) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) return current;
        current = current->next;
    }
    return nullptr;
}

选择建议：

• 需要频繁随机访问元素时，选择数组
• 需要频繁插入删除元素时，选择链表
• 不确定元素数量且需要动态调整大小时，选择链表
• 对内存要求严格且元素数量固定时，选择数组

20. 如何反转单链表

反转单链表是一个经典的编程问题，有两种常见的解法：循环法和递归法。

循环法

// 循环法反转单链表
ListNode* reverseList(ListNode* head) {
    // 空链表或只有一个节点的情况
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    ListNode* prev = nullptr;    // 前一个节点
    ListNode* curr = head;       // 当前节点
    ListNode* next = nullptr;    // 下一个节点
    
    while (curr != nullptr) {
        next = curr->next;       // 保存下一个节点
        curr->next = prev;       // 反转指针
        prev = curr;             // 移动prev指针
        curr = next;             // 移动curr指针
    }
    
    return prev;  // 新的头节点
}

循环法步骤：

1. 初始化三个指针：prev(前一个节点)、curr(当前节点)、next(下一个节点)
2. 遍历链表，对于每个节点：
   • 保存下一个节点(next = curr->next)
   • 反转当前节点的指针(curr->next = prev)
   • 移动prev和curr指针(prev = curr, curr = next)
3. 返回新的头节点(prev)

递归法

// 递归法反转单链表
ListNode* reverseList(ListNode* head, ListNode* prev = nullptr) {
    // 基本情况：空链表
    if (head == nullptr) {
        return prev;
    }
    
    // 保存下一个节点
    ListNode* next = head->next;
    
    // 反转当前节点的指针
    head->next = prev;
    
    // 递归处理剩余链表
    return reverseList(next, head);
}

递归法步骤：

1. 基本情况：如果当前节点为空，返回prev作为新的头节点
2. 保存当前节点的下一个节点
3. 反转当前节点的指针，使其指向前一个节点
4. 递归调用函数处理剩余链表，将当前节点作为下一次递归的prev参数

复杂度分析：

• 时间复杂度：O(n)，需要遍历整个链表一次
• 空间复杂度：
  • 循环法：O(1)，只使用了常数额外空间
  • 递归法：O(n)，递归调用栈的空间

注意事项：

• 处理空链表和只有一个节点的特殊情况
• 保存必要的指针，避免丢失链表节点
• 确保正确更新头节点
• 递归法在链表很长时可能导致栈溢出

应用场景：

• 链表逆序遍历
• 某些算法需要从尾到头处理链表
• 检测回文链表