C/C++语言知识点二

1. 编程算法之“哨兵”思想

        哨兵思想是一种编程技巧，通过在数据结构的边界或特定位置放置一个特殊值（称为“哨兵”），来简化逻辑判断和提高代码效率。哨兵通常是一个标记值，用于指示某种条件或边界，从而避免额外的边界检查或条件判断。

哨兵思想的应用场合：

1. 数组或链表的遍历：在遍历数组或链表时，可以在末尾放置一个哨兵值，避免在每次循环中检查是否越界。

   // 例如，在查找数组中的某个元素时，可以将目标值作为哨兵放在数组末尾，从而简化查找逻辑。
   int find(int arr[], int n, int target) {int last = arr[n - 1]; // 保存最后一个元素arr[n - 1] = target;   // 将目标值作为哨兵int i = 0;while (arr[i] != target) {i++;}arr[n - 1] = last; // 恢复最后一个元素if (i < n - 1 || arr[n - 1] == target) {return i; // 找到目标值}return -1; // 未找到
   }

2. 循环终止条件：

   • 在循环中，哨兵可以作为终止条件，避免额外的判断。
   • 例如，在读取用户输入时，可以使用特定的哨兵值（如 -1 或 EOF）来终止循环。

     int sum = 0;
     int value;while (true) {scanf("%d", &value);if (value == -1) { // -1 作为哨兵break;}sum += value;
     }
     printf("Sum: %d\n", sum);

3. 排序算法：

   • 在某些排序算法（如插入排序）中，哨兵可以减少比较次数。
   • 例如，在插入排序中，可以将数组的第一个元素作为哨兵，避免每次比较时检查数组边界。

4. 字符串处理：

   • 在字符串处理中，哨兵可以标记字符串的结束位置。
   • 例如，C 语言中的字符串以 \0 作为哨兵，表示字符串的结束。

5. 图的遍历：在图算法中，哨兵可以标记节点的访问状态或边界。

---

2. Linux内核代码中的一个宏定义

代码：

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

分析: 

1. (TYPE *)0：将地址0强制类型转换为 TYPE 类型的指针。这里的 0 代表一个空指针，但通过类型转换，它被当作 TYPE 类型的对象来处理。

2. ((TYPE *)0)->MEMBER：通过上述转换得到的指针访问其 MEMBER 成员。这一步实际上是在访问一个不存在的地址上的成员，但由于编译器在编译时会计算成员的偏移量，所以这一步是安全的。

3. &((TYPE *)0)->MEMBER：获取 MEMBER 成员变量的地址。由于 MEMBER 是通过类型转换后的指针访问的，所以这个地址实际上是 MEMBER 在 TYPE 结构体中的偏移地址。

4. (size_t)&((TYPE *)0)->MEMBER：将上述地址转换为 size_t 类型的数据。size_t 是一个无符号整数类型，通常用于表示大小或偏移量。

总结：这个宏的作用是计算并返回 MEMBER 成员在 TYPE 结构体中的偏移量。这个偏移量是一个 size_t 类型的值，表示从结构体的起始地址到成员 MEMBER 的起始地址之间的字节数。

---

3. 64位和32位Linux系统字节对齐问题

代码分析：

#include <stdio.h>#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)typedef struct s
{union{int a;char str[10];};struct s* next;
} S;int main()
{printf("%d\n", offsetof(S, next));return 0;
}

 案例：

#include <stdio.h>#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)typedef struct s
{union{int a;char str;};struct s* next;
} S;int main()
{printf("Size of S: %zu\n", sizeof(S));printf("Offset of next: %zu\n", offsetof(S, next));return 0;
}//结果32位、四字节对齐
Size of S: 16
Offset of next: 12//结果64位、八字节对齐
Size of S: 24
Offset of next: 16

---

4. const和指针的用法

        在 C/C++ 中，const 关键字用于定义常量或指定某些数据不可修改。它可以应用于变量、指针、函数参数等，具有多种用法和含义。以下是 const 关键字的几种常见用法，特别是与指针结合时的不同含义： 

1. 定义常量：const 可以用于定义常量，常量的值在定义后不能被修改。

const int MAX_VALUE = 100;特点：
定义时必须初始化。
不能通过赋值修改常量的值。

2. const 与指针：const 与指针结合时，可以有不同的含义，具体取决于 const 的位置。

(1) 指向常量的指针： 

const int *pt;含义：pt 是一个指向 const int 的指针。指针可以指向不同的对象，但不能通过 pt 修改所指向的对象。示例：int a = 10;const int *pt = &a;// *pt = 20; // 错误：不能通过 pt 修改 aa = 20;      // 正确：可以直接修改 a

(2) 常量指针： 

int *const pt;含义：pt 是一个常量指针，指向 int 类型。指针的值（即指向的地址）不能修改，但可以通过 pt 修改所指向的对象。示例：int a = 10;int *const pt = &a;*pt = 20;     // 正确：可以通过 pt 修改 a// pt = &b;   // 错误：不能修改 pt 的值

(3) 指向常量的常量指针： 

const int *const pt;含义：pt 是一个常量指针，指向 const int 类型。指针的值（即指向的地址）不能修改，也不能通过 pt 修改所指向的对象。示例：int a = 10;const int *const pt = &a;// *pt = 20; // 错误：不能通过 pt 修改 a// pt = &b;  // 错误：不能修改 pt 的值

3. const 修饰函数参数：const 可以用于修饰函数参数，表示该参数在函数内部不能被修改。

(1) 修饰指针参数

void print(const int *arr, int size); // arr 是一个指向常量的指针，函数内部不能通过 arr 修改所指向的数据。

 示例：

void print(const int *arr, int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}
}

(2) 修饰引用参数（C++）

void print(const std::string &str); // str 是一个常量引用，函数内部不能修改 str 的值

示例：

void print(const std::string &str) {std::cout << str;
}

4. const 修饰成员函数（C++）：在 C++ 中，const 可以修饰类的成员函数，表示该函数不会修改类的成员变量。

class MyClass {
public:int getValue() const {return value;}
private:int value;
};// getValue 是一个常量成员函数，不能修改类的成员变量。

5. const 修饰返回值：const 可以用于修饰函数的返回值，表示返回值不能被修改。

const int* getPointer(); // 返回的指针指向的内容不能被修改。

6. const 修饰全局或局部变量：const 可以用于修饰全局或局部变量，表示变量的值不能被修改。

void func() {const int LOCAL_VALUE = 10;// LOCAL_VALUE = 20; // 错误：不能修改常量
}

总结：const 关键字的用法非常灵活，主要作用是保证数据的不变性。以下是一些常见的应用场景：

1. 定义常量。
2. 修饰指针，限制指针或指向数据的修改。
3. 修饰函数参数，防止参数被修改。
4. 修饰成员函数（C++），保证函数不修改对象状态。
5. 修饰返回值，限制返回值的修改。

通过合理使用 const，可以提高代码的安全性和可读性，避免意外的数据修改。

---

5. fork函数 

分析代码：

int main() {fork() || fork();
}

1. fork() 的作用：

   • fork() 创建一个新的进程（子进程），子进程是父进程的副本。
   • fork() 在父进程中返回子进程的 PID（大于 0），在子进程中返回 0。
   • 如果 fork() 失败，返回 -1。

2. 逻辑或运算符 || 的特性：

   • A || B：如果 A 为真（非零），则不会执行 B（短路特性）。
   • 如果 A 为假（零），则继续执行 B。

进程创建过程：

1. 第一次 fork()：

   • 父进程调用 fork()，创建一个子进程。
   • 父进程中，fork() 返回子进程的 PID（大于 0），因此 fork() || fork() 的值为真，短路特性生效，不会执行第二个 fork()。
   • 子进程中，fork() 返回 0，因此 fork() || fork() 的值为假，继续执行第二个 fork()。

2. 第二次 fork()：

   • 只有在第一次 fork() 创建的子进程中，才会执行第二个 fork()。
   • 子进程调用 fork()，创建另一个子进程（孙子进程）。
   • 子进程中，fork() 返回孙子进程的 PID（大于 0），因此 fork() || fork() 的值为真，短路特性生效。
   • 孙子进程中，fork() 返回 0，因此 fork() || fork() 的值为假。

进程树结构：

父进程
|
├─ 子进程
|   |
|   └─ 孙子进程
|
└─ 子进程

进程总数：总共创建了 3 个进程。

1. 父进程：1 个。
2. 子进程：1 个。
3. 孙子进程：1 个。

总结：

• 代码 fork() || fork() 会创建 3 个进程。
• 第一次 fork() 创建 1 个子进程。
• 第二次 fork() 在子进程中创建 1 个孙子进程。
• 父进程和子进程都会执行 fork()，但由于逻辑或运算符的短路特性，父进程不会执行第二个 fork()。

---

6. 按指针引用值传递参数 

代码分析： 下面这段代码的输出结果为：

#include <stdio.h>
void change(int *a, int &b, int c)
{c=*a;b=30;*a=20;
}int main ( )
{int a = 10, b = 20, c = 30;change(&a, b, c);printf( "%d, %d, %d, ", a, b, c);return 0;
}

1. 函数 change 的参数传递

• int *a：
  • 传递指针，函数内部可以通过指针修改 a 的值。
• int &b：
  • 传递引用（C++ 特性），函数内部可以直接修改 b 的值。
• int c：
  • 传递值，函数内部对 c 的修改不会影响外部的 c。

2. 函数 change 的逻辑 

void change(int *a, int &b, int c)
{c = *a;    // 将指针 a 指向的值赋值给 c（局部变量，不影响外部的 c）b = 30;    // 将引用 b 的值修改为 30*a = 20;   // 将指针 a 指向的值修改为 20
}

3. main 函数的逻辑

int main()
{int a = 10, b = 20, c = 30;change(&a, b, c);printf("%d, %d, %d, ", a, b, c);return 0;
}

• 调用 change 函数：
  • &a 传递 a 的地址。
  • b 传递 b 的引用。
  • c 传递 c 的值。
• change 函数执行后：
  • *a = 20 修改了 a 的值为 20。
  • b = 30 修改了 b 的值为 30。
  • c = *a 修改了局部变量 c 的值为 10，但外部的 c 不受影响。

总结：

• 指针 int *a：可以修改外部变量的值。
• 引用 int &b：可以直接修改外部变量的值。
• 值传递 int c：对局部变量的修改不影响外部变量。

最终输出结果为：20, 30, 30。

---

7. 调用几次构造函数

题目内容是：

若 MyClass 为一个类，执行 MyClass a, *p; 语句时会自动调用该类构造函数的次数是（）

选项：

• A: 2
• B: 5
• C: 4
• D: 9

解题思路：

1. MyClass a：

   • 这是一个数组，包含 4 个 MyClass 对象。
   • 每个对象在创建时都会调用构造函数，因此会调用 4 次构造函数。

2. MyClass *p：

   • 这是一个指针数组，包含 5 个 MyClass 类型的指针。
   • 指针本身是内置类型，不会调用 MyClass 的构造函数。
   • 这些指针默认初始化为 nullptr，不会创建 MyClass 对象。

3. 总结：

   • MyClass a 会调用 4 次构造函数。
   • MyClass *p 不会调用构造函数。
   • 总共调用构造函数的次数是 4 次。

---

8. 统计二进制数中1的个数

题目内容是：

要求：求下面函数的返回值：
int func(int x)
{int countx = 0;while(x){countx++;x = x&(x-1);}return countx;
} 

这个函数的返回值是 整数 x 的二进制表示中 1 的个数。以下是详细分析： 

解题思路：

1. x = x & (x - 1)：

   • 这个操作会将 x 的二进制表示中最右边的 1 置为 0。
   • 例如：
     • 如果 x = 12（二进制 1100），则 x - 1 = 11（二进制 1011）。
     • x & (x - 1) = 1100 & 1011 = 1000（二进制 1000）。
     • 下一次循环时，x = 8（二进制 1000），x - 1 = 7（二进制 0111）。
     • x & (x - 1) = 1000 & 0111 = 0000（二进制 0000）。
     • 循环结束。

2. countx++：

   • 每次循环将 countx 加 1，表示找到了一个 1

 示例 1：

int x = 12; // 二进制 1100
int result = func(x);分析
第一次循环：x = 1100，x & (x - 1) = 1000，countx = 1。
第二次循环：x = 1000，x & (x - 1) = 0000，countx = 2。
循环结束，返回 2。

示例 2：

int x = 7; // 二进制 0111
int result = func(x);分析：
第一次循环：x = 0111，x & (x - 1) = 0110，countx = 1。
第二次循环：x = 0110，x & (x - 1) = 0100，countx = 2。
第三次循环：x = 0100，x & (x - 1) = 0000，countx = 3。
循环结束，返回 3。

---

9. 编写代码：判断一个数是不是2的N次方

方法 1：利用二进制特性

2 的 N 次方的二进制表示中，只有一个 1，其余位都是 0。例如：

• 1（2⁰）：0001
• 2（2¹）：0010
• 4（2²）：0100
• 8（2³）：1000

因此，判断一个数是否是 2 的 N 次方，可以检查它的二进制表示是否只有一个 1。

#include <stdio.h>int isPowerOfTwo(int x) {// 如果 x 是 2 的 N 次方，则 x & (x - 1) == 0return x > 0 && (x & (x - 1)) == 0;
}int main() {int x;printf("Enter a number: ");scanf("%d", &x);if (isPowerOfTwo(x)) {printf("%d is a power of two.\n", x);} else {printf("%d is not a power of two.\n", x);}return 0;
}

解释：

• x > 0：确保 x 是正整数。
• (x & (x - 1)) == 0：如果 x 是 2 的 N 次方，则 x & (x - 1) 的结果为 0。

 

方法 2：循环除以 2

通过循环将 x 反复除以 2，如果最终结果为 1，则 x 是 2 的 N 次方。

#include <stdio.h>int isPowerOfTwo(int x) {if (x <= 0) {return 0; // 非正整数不可能是 2 的 N 次方}while (x > 1) {if (x % 2 != 0) {return 0; // 如果不能被 2 整除，则不是 2 的 N 次方}x /= 2;}return 1; // 最终结果为 1，是 2 的 N 次方
}int main() {int x;printf("Enter a number: ");scanf("%d", &x);if (isPowerOfTwo(x)) {printf("%d is a power of two.\n", x);} else {printf("%d is not a power of two.\n", x);}return 0;
}

解释：

• 如果 x 能被 2 整除，则继续除以 2，直到 x 变为 1。
• 如果在过程中 x 不能被 2 整除，则不是 2 的 N 次方。

 

方法 3：利用对数

如果 log₂(x) 是整数，则 x 是 2 的 N 次方。

#include <stdio.h>
#include <math.h>int isPowerOfTwo(int x) {if (x <= 0) {return 0; // 非正整数不可能是 2 的 N 次方}double log2x = log2(x);return log2x == (int)log2x; // 判断 log2x 是否为整数
}int main() {int x;printf("Enter a number: ");scanf("%d", &x);if (isPowerOfTwo(x)) {printf("%d is a power of two.\n", x);} else {printf("%d is not a power of two.\n", x);}return 0;
}

解释：

• 计算 log₂(x)，如果结果是整数，则 x 是 2 的 N 次方。

总结：

• 推荐方法：方法 1（利用二进制特性），效率最高，代码简洁。
• 其他方法：方法 2 和方法 3 也可以实现，但效率较低。

 

#include <stdio.h>#define ISPOWER_OF_TWO(x) ((x&(x-1))==0)int main(void)
{int n;printf("Please enter a number, n = ");scanf("%d", &n);if(ISPOWER_OF_TWO(n))printf("n is the power of two\n");elseprintf("n is not the power of two\n");return 0;
}

#include <stdio.h>#define ISPOWER_OF_TWO(x) ((x > 0) && ((x & (x - 1)) == 0))int main(void)
{int n;printf("Please enter a number, n = ");scanf("%d", &n);if(ISPOWER_OF_TWO(n))printf("n is the power of two\n");elseprintf("n is not the power of two\n");return 0;
}