很久没碰c语言,基本语法都忘了,最近看编程珠玑,想用c语言写,顺便复习一下,过了这么长时间再碰c,应该会有不同的理解。下面是第一章的有编程的习题。

##(1) 使用c库函数qsort排序random出来的99999个整数
首先我们用rand函数产生n个待排序的数,写入文件中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* random_file.c
* author: CalvinMeng
* usage: ./random_file <intput file>
*/
#include <stdio.h>
#include <stdlib.h>
int main(){
int i,n;
scanf("%d",&n);
for(i = 0 ; i < n; i++){
printf("%d\n", rand()%100000 );
}
}

然后用qsort函数对输入的数进行排序

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
/* random_file.c
* author: CalvinMeng
* usage: ./qsort <intput file>
*/
#include <stdio.h>
#include <stdlib.h>
// 规定该函数只能返回int
int intcomp(const void *x,const void *y){
return (*(int*)x) - (*(int *)y);
}
int a[100000];
int main(void){
int i ,n = 0;
while(scanf("%d",&a[n]) != EOF){
n++;
}
qsort(a,n,sizeof(int),intcomp);
for(i = 0; i < n ;i++){
printf("%d\n",a[i]);
}
return 0;
}

然后编译,调用

1
2
$ echo 99999 > input.txt
$ ./random_file < input.txt | ./qsort >output.txt

##(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
/* bitmap.c
* author: CalvinMeng
* usage: ./bitmap
*/
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define N 10000000
#define MASK 0x1F
int a[1 + N/BITSPERWORD];
void set(int i){
a[i >> SHIFT] |= (1 << (i & MASK));
}
void clear (int i){
a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i){
return a[i >> SHIFT] & (1 << (i & MASK));
}
int main(){
int indent = 16;
set(indent);
printf("%d\n",test(indent));
clear(indent);
printf("%d\n",test(indent));
}

##(3) 位图排序
首先产生1000000个随机数,这里就不严格限制必须不重复了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* random_file.c
* author: CalvinMeng
* usage: ./random_file <intput file>
*/
#include <stdio.h>
#include <stdlib.h>
#define N 10000000
int main(){
int i,n;
scanf("%d",&n);
for(i = 0 ; i < n; i++){
printf("%d\n", rand()%N );
}
}

然后将这些数进行bit排序

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
34
35
36
37
38
/* bitmap_sort.c
* author: CalvinMeng
* usage: ./bitmap_sort inputfile
*/
#include <stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define N 10000000
#define MASK 0x1F
int a[1 + N/BITSPERWORD];
void set(int i){
a[i >> SHIFT] |= (1 << (i & MASK));
}
void clear (int i){
a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i){
return a[i >> SHIFT] & (1 << (i & MASK));
}
int main(){
int number = 0;
while(scanf("%d",&number) != EOF){
set(number);
}
for (int i = 0; i < N; ++i)
{
if(test(i)){
printf("%d\n", i);
}
}
return 0;
}

然后编译,调用

1
2
$ echo 1000000 > input.txt
$ ./random_file < input.txt | ./bitmap_sort > output.txt

原书上说10秒,现在机器那么快,大概不到1秒就搞定了。

(4) 生成小于n但不重复的k个数字

噗,本来第三个题目想绕过去的,看来还是绕不过去,我一开始的想法是,例如N为10000000,K为1000000,相除为10,
那么设置random时候每次返回0-9的一个数,输出累计的数,这种方法是能够生成随机的100万的数,但随机出来的数的范围基本在500万左右。
不符合题意。下面给出答案的程序:

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
34
35
36
/* random_k.c
* author: CalvinMeng
* usage: ./random_k <intput file>
*/
#include <stdio.h>
#include <stdlib.h>
#define N 10000000
#define K 1000000
int a[N+1];
int randint(int l,int r){
if(r < l) return 0;
return l+rand() % (r-l);
}
void swap (int l, int r){
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
int main(){
int i;
for(i=0; i < N; ++i){
a[i] = i;
}
for(i = 0; i < K; ++i){
swap(i,randint(i,N-1));
printf("%d\n",a[i]);
}
return 0;
}