复试笔试C语言一些要点

C语言短路求值（逻辑与、逻辑或）

逻辑或的短路

首先上代码：

1
2
3
4
5
6
7
8

#include <stdio.h>
int main() {
    int a = 1;
    printf("a = %d\n", a);
    1 || (a = 0);
    printf("a = %d\n", a);
    return 0;
}

运行结果如下：

a = 1
a = 1

逻辑或的表现形式如下：
expression1 || exexpression2

这⾥用到了逻辑或，由于逻辑或的短路，expression1为true，则后⾯的expression2（即：(a=0) ）不再求值，整个表达式的结果为true，所以a的值仍为1，没有改变。【即：一真为真】

逻辑与的短路

⾸先看如下代码：

1
2
3
4
5
6
7
8

#include <stdio.h>
int main() {
    int a = 1;
    printf("a = %d\n", a);
    0 && (a = 3);
    printf("a = %d\n", a);
    return 0;
}

运行结果如下：

a = 1
a = 1

逻辑与的表现形式如下：
expression1 && expression2

上述代码中用到了逻辑与，由于逻辑与的短路，expression1为false，则后面的expression2不再求值，整个的结果为false，所以a的值没有改变。【即：一假则假】

Eratosthenes筛选法

算法原理

解释一：
给出要筛选数值的范围$n$，找出sqrt(n)以内的素数$p_1, p_2, … , p_k$。

• 先把1删除（现今数学界1既不是质数也不是合数）
• 读取队列中当前最小的数2，然后把2的倍数删去
• 读取队列中当前最小的数3，然后把3的倍数删去
• 读取队列中当前最小的数5，然后把5的倍数删去
• 读取队列中当前最小的数7，然后把7的倍数删去
• 不断重复下去…直到需求的范围内所有的数均删除或读取
  注：此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。
  【来源：百度百科】

解释二：

1. 取最小的数$2$，并声明它是素数，同时筛去它及它的所有倍数；
2. 取未筛去的数中的最小者，声明它是素数，同时筛去它及它的所有倍数；
3. 重复步骤2，至筛中无数为止，得到所有素数。

筛法实际上是筛去合数，留下素数。

一位数组举例

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//C Language
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define SIZE 10000
int main() {
	int i; /*i表示整数和对应的下标*/
	int j; /*j表示正要处理的质数，j之前的已处理，j之后的未处理*/
	int k; /*k表示正在处理的j的倍数从2开始到j*k<SIZE*/
	int a[SIZE]; /*下标表示整数内容判断是否为质数*/
	int *p; /*控制循环*/
	for(p = a; p < a+SIZE; ++p) { /*初始化数组全是TRUE*/
		*p = TRUE;
	}
	a[0] = a[1] = FALSE; /*设置前面两个是不是质数的数的状态为FALSE，即0和1不是质数*/
	i = 2;
	while(i < SIZE) { /*找到下一个质数*/
		while(a[i++] == TRUE) {
			j = i-1;
			break;
		}
		for(k = 2; j*k < SIZE && i < SIZE; ++k) { /*处理质数的倍数*/
			a[j*k] = FALSE;
		}
	}
	for(p = a; p < a+SIZE; ++p) { /*打印出质数*/
		if(*p == TRUE) {
			printf("%8d", p-a);
		}
	}
	printf("\n");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//C++
int countPrimes(int n) {
    vector<bool> vec_flag(n, true);
    vec_flag[0] = false;
    vec_flag[1] = false;

    for(int i = 2; i < sqrt(n);i++) {
        if(vec_flag[i]){
            for(int j = i * i; j < n; j += i) {
                vec_flag[j] = false;
            }
        }
    }
    return count(vec_flag.begin(), vec_flag.end(), true);
}

关于void *

void的含义

void即“无类型”，void *则为“无类型指针”，可以指向任何数据类型

void指针的使用规范

• void指针可以指向任意类型的数据，亦即可用任意数据类型的指针对void指针赋值。例如：

  1 2 3

  int *p_int; void *p_void; p_void = p_int; /*但是不能 p_int = p_void*/

如果要将p_void赋给其他类型指针，则需要强制类型转换如：p_int = (int *)p_void;

• 在ANSIC标准中，不允许对void指针进行算术运算如p_void++或p_void += 1等，而在GNU中则允许。因为在缺省情况下，GNU认为void *与char *⼀样。sizeof(*pvoid ) == sizeof(char).
• 由于void指针可以指向任意类型的数据，亦即可用任意数据类型的指针对void指针赋值，因此还可以用void指针来作为函数形参，这样函数就可以接受任意数据类型的指针作为参数。例如：

  1 2	void *memcpy(void *dest, const void *src, size_t len); void *memset(void *buffer, int c, size_t num);