变量

命名

  1. 变量名可以以数字开头吗？

    • 不可以。C语言的变量名不能以数字开头。

  2. 变量名可以以符号（如 #、*、_）开头吗？

    • 可以。变量名可以包含下划线 _，但不能包含其他符号（如 #、* 等）。

  3. 给出一个无效的C变量名例子，并解释为什么无效：

    • 例子：1stVariable。原因：变量名不能以数字开头。

数据类型

  1. 列举至少三种C语言的数据类型：

    • int（整型）
    • float（浮点型）
    • char（字符型）

  2. 每种数据类型在你计算机中需要多少内存？

    • int：通常为4字节（32位系统），8字节（64位系统）
    • float：通常为4字节
    • char：通常为1字节

  3. 哪些数据类型可以互相替代？为什么？

    • int 和 float 在某些情况下可以互相替代，但要注意精度和内存大小的不同。例如，可以将float转换为int，但会丢失小数部分。

  4. 是否有任何使用上的限制？

    • 是的，int 转换为 float 时，精度可能会丢失，反之亦然。

  5. 使用替代数据类型时是否需要做特别的处理？

    • 是的，通常需要强制类型转换（casting）来进行转换。

  6. 我们为数据类型使用的名字（如 int、float）可以作为变量名吗？

    • 不可以。int 和 float 等关键字是保留字，不能用作变量名。

赋值

  1. 如何将值 3.14 赋给名为 pi 的变量？

    float pi = 3.14;

  2. 可以将 int 类型赋值给 double 吗？

    • 可以，编译器会自动将 int 类型转换为 double 类型。

  3. 反过来可以吗？（将 double 赋值给 int）

    • 不建议这样做，因为可能会丢失小数部分。可以通过强制类型转换来实现，但这可能导致数据丢失。
    int x = (int)3.14; // x 将变为 3

引用

  1. 新手常犯的一个错误是反转赋值语句。假设你想将变量 pi 中存储的值赋给另一个变量 pi2：

    • 正确的赋值语句是：
    pi2 = pi;

  2. 如果反过来写：

    pi = pi2;
    • 这不是一个有效的C语句。反转赋值会导致逻辑错误（将 pi2 的值赋给 pi，而不是相反）。

  3. 如果你想将常量值（如 3.1415）赋给 pi2：

    • 正确的赋值语句是：
    pi2 = 3.1415;

  4. 反转赋值是否有效？

    • 如果反过来写，即 3.1415 = pi2;，则是无效的C语句，因为常量值不能作为左侧的赋值目标。

简单输入输出

字符串操作

  1. 编写一个程序，提示用户输入一个字符串（设置一个最大长度），并打印出它的反向字符串。

    #include <stdio.h>
#include <string.h>

int main() {
    char str[100];
    printf("请输入一个字符串：");
    fgets(str, sizeof(str), stdin);
    int len = strlen(str);
    for (int i = len - 1; i >= 0; i--) {
        printf("%c", str[i]);
    }
    return 0;
}

  2. 编写一个程序，提示用户输入一句话（设置一个最大长度），并打印出每个单词占一行。

    #include <stdio.h>
#include <string.h>

int main() {
    char str[100];
    printf("请输入一句话：");
    fgets(str, sizeof(str), stdin);
    char *word = strtok(str, " \n");
    while (word != NULL) {
        printf("%s\n", word);
        word = strtok(NULL, " \n");
    }
    return 0;
}

循环

  1. 编写一个函数，输出一个高度和宽度为 n 的直角三角形（右对齐），例如当 n=3 时输出：

    *
**
***

  2. 编写一个函数，输出一个高度为 2n-1 和宽度为 n 的倒三角形，例如当 n=4 时输出：

    *
**
***
****
***
**
*

  3. 编写一个函数，输出一个高度为 n 和宽度为 2n-1 的正三角形，例如当 n=6 时输出：

        *
   ***
  *****
 *******
*********

程序流程

  1. 编写一个程序，使控制从 main 函数传递到四个不同的函数，并进行四次调用。

  2. 在 main 中创建一个 while 循环，将函数调用放入其中。在循环开始时询问用户输入。如果用户按下 Q，结束 while 循环。

  3. 接下来，添加条件语句，当用户输入数字时，调用不同的函数，例如输入 1 调用 function1，输入 2 调用 function2，以此类推。

  4. 让 function1 调用 function a，然后 function a 调用 function b，最后 function b 调用 function c。

  5. 绘制程序流程图，用箭头表示控制的流向。

函数

  1. 编写一个函数来检查一个整数是否为负数；函数声明应为 bool is_positive(int i);。

  2. 编写一个函数，用于将浮动点数提高到整数的幂。例如：

float a = raise_to_power(2, 3);    // a 得到 8
float b = raise_to_power(9, 2);    // b 得到 81
float raise_to_power(float f, int power);    // 这是你的声明

数学

  1. 编写一个函数，用于计算一个数是否为质数。如果是质数，返回 1；如果不是质数，返回 0。

  2. 编写一个函数，用于确定小于 n 的质数数量。

  3. 编写一个函数，通过牛顿法求平方根。

  4. 编写函数来计算三角函数。

  5. 尝试编写一个随机数生成器。

  6. 编写一个函数，找出 2 到 100 之间的质数。

递归

归并排序

  1. 编写一个 C 程序，生成一个指定长度 n 的随机整数数组，并使用归并排序算法递归地排序它。

归并排序算法是递归算法。

  • 排序一个单元素数组很容易。

  • 排序两个单元素数组，需要归并操作。归并操作将两个已排序的数组作为列表进行比较，比较列表的头部元素，选择较小的元素加入到已排序的列表中，并将该列表的头部元素移除。直到其中一个列表耗尽，然后将另一个列表直接复制到已排序列表的末尾。

  • 递归发生在，将两个单元素数组归并成一个两元素排序数组，再与另一个两元素排序数组进行归并。最终得到一个排序的 4 元素数组，同样的方法适用于其他 4 元素的排序数组。

  • 归并排序的基本方法是检查待排序列表的大小，如果大于 1，则将数组分为两部分，递归调用归并排序对这两部分进行排序。之后，在一个大小相等的临时空间中归并这两部分，最后将最终排序的数组复制回原始数组。

二叉堆

2. 二叉堆：

二叉最大堆或最小堆是一个有序结构，其中某些节点比其他节点大（例如，父节点与两个子节点）。一个二叉堆可以存储在数组中，其中：

  • 给定一个位置 i（父节点），i2 是左子节点，i2+1 是右子节点。

  • (C数组从位置0开始，但0 * 2 = 0，0 * 2 + 1 = 1，这不正确，所以可以将堆从位置 1 开始，或者在父子节点计算中加 1，在子父节点计算中减去 1)。

尝试用铅笔和纸模拟这个过程，使用 10 个随机未排序的数字，将它们逐一插入到一个大小为 10 的 "堆排序" 数组中。
向堆中插入时，将元素添加到末尾并与父节点交换，直到父节点大于当前节点。
删除堆顶元素时，将末尾元素移到堆顶，并下沉（或与较大的子节点交换）直到没有子节点比它大。

尝试在纸上处理数字 10、4、6、3、5、11，结果为 11、5、10、3、4、6。

练习：现在尝试删除 11、5、10、3、4、6 中的每个顶部元素，使用“末尾到顶部”和“下沉”（或与较大的子节点交换）方法，将这些元素按降序排列。

优先队列允许元素按优先级插入，并根据优先级提取元素。如果元素有配对结构，一部分是关键字，另一部分是数据，则这种机制非常有用；否则，它只是用于排序的机制。
练习：使用上述“插入-后退/挑战父节点”和“删除-前端/末尾-前端/推迟-更大的子节点”技术，实现堆排序或优先队列。

Dijkstra 算法

Dijkstra 算法是一种使用优先队列的搜索算法。它从插入起始节点开始，优先级值为 0。其他所有节点都以较大的 N 作为优先级值插入。每个节点有一个邻接节点列表、当前距离起始节点的距离以及用于计算当前节点的前驱指针。邻接矩阵作为邻接节点列表的替代方案，需要一个 n x n 的布尔值邻接矩阵。

该算法基本上是在优先队列中遍历，移除前端节点，检查邻接节点，并更新每个邻接节点的距离，更新的距离等于前端节点的距离与邻接节点之间的距离之和。

每次更新节点后，执行“更新优先级”的操作：

当节点的距离小于父节点的距离时（在该优先队列中，父节点的距离比子节点小），节点与父节点交换。

之后，当节点的距离大于一个或多个子节点时，节点与最远的子节点交换，这样最远的子节点成为其更远兄弟的父节点，成为当前节点的父节点。

通过更新优先级，当前节点的邻接节点的反向指针被更新为当前节点。

当目标节点被移除并成为当前节点时，算法结束，可以通过追踪反向指针将路径记录到一个数组中，然后进行类似快速排序的分区操作，逆转数组顺序，得到从起始节点到目标节点的最短路径。

快速排序

3. 编写一个 C 程序，使用快速排序的分区交换算法进行递归排序。

你可以使用第 1 题中归并排序的“驱动程序”或随机数测试数据。这是“重用”的一个例子，通常鼓励使用重用。

  • 重用的优点是减少了编写、调试和测试的时间。

分区交换的概念是随机选择一个分区元素，并将所有需要排序的元素分为三个等价类：小于分区值的元素、分区元素本身和大于等于分区元素的元素。

这一过程可以在不分配比交换两个元素所需的一个临时元素空间更多的情况下完成。例如，对于整数数据，可以使用一个临时整数来交换元素。
然而，分区元素应该在原始数组空间中的位置是未知的。通常的做法是将分区元素放到待排序数组的末尾，然后设置两个指针，一个指向数组的开始位置，另一个指向分区元素的下一个位置，反复扫描左指针向右移动，右指针向左移动。

左扫描会在找到一个大于或等于分区值的元素时停止，右扫描会在找到一个小于分区值的元素时停止，然后交换这两个元素，使用临时空间。

左扫描会在达到分区元素时停止，因为这时整个数组都小于分区值。右扫描可能会达到第一个元素，如果整个数组都大于分区元素，则需要进行测试，否则扫描不会停止。外循环会在左指针和右指针交叉时退出。测试指针是否交叉以及外循环是否退出应在交换之前进行，否则右指针可能会交换一个已经被左指针扫描过的小于分区元素。

最后，一旦指针交叉，分区元素需要被放置在左右两个分区之间。
在指针交叉时，左指针可能会停在分区元素的最后一个位置，而右指针未越过倒数第二个元素。这种情况发生在所有元素都小于分区值时。

  • 如果选择将右指针与分区元素交换，那么将会出现不正确的状态，导致左数组的最后一个元素变得小于分区元素的值。

  • 如果选择将左指针与分区元素交换，那么左数组会小于分区，分区元素将与一个比它大的元素交换，或者与分区元素本身交换。

需要检查快速排序的一个特殊情况，即排序一个两个元素逆序的数组：

  • 左指针会停在第一个无序元素上，右指针从第一个无序元素开始，但外循环会因为这是最左端的元素而退出。然后，分区元素与左指针的第一个元素交换，这样两个元素就变得有序了。

  • 对于一个已排序的两个元素数组，最左边的指针会跳过第一个小于分区元素的元素，停在分区元素上。右指针从第一个元素开始并退出，因为它是第一个位置。指针交叉后，外循环退出，分区元素与自己交换，因此保持了有序状态。

在交换之后，左指针应该增加，右指针应该减少，以防止重复扫描相同的位置，因为可能会导致无限循环（尤其是在左指针退出时元素等于或大于分区元素，而右指针元素等于分区元素值的情况）。一种实现方法是，Sedgewick 使用左指针减一和右指针加一来作为初始扫描位置，并使用前增和前减操作符，例如（++i, --i）。

最后修改: 2025年01月12日 星期日 13:26