学步园

收获

一．一定要把问题弄清楚后在进行解答。

例如磁盘文件排序我们就需要弄清楚 1 文件里存储了多少数据 2 存储数据的范围和类型 3 计算机允许使用的内存 4 在文件中是否有相同的数据出现 

二．位图的数据结构（后边的习题解答加以详述）

三．可以实现程序的时空双赢

习题选解 首先通过 第四题生成10万个不同的小于10000000数据。

1

/*
	没有内存限制，直接把数据读内存，进行qsort 
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX 100005

int num[MAX], n = 0;

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int main()
{
	freopen("data.txt", "r", stdin);
	while(scanf("%d", &num[n]) != EOF)
	{
		n++;
	}
	qsort(num, n, sizeof(num[0]), cmp); 
	for(int i = 0; i < n; i++)
	{
		printf("%d ", num[i]);
	}
	printf("\nqsort Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
	return 0;
}

2 3（详细Bitmap讲解请参看http://blog.csdn.net/dweqd/article/details/6806024
）

/*
	10万个不大于10000000 数据的Bitmap应用排序。 
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define WORD 32 // 一个int四个字节 32位 
#define SHIFT 5 // 左移5位 *32，右移5为 /32 
#define MASK 0x1f
#define MAX 10000000

int Bitmap[1 + MAX/WORD], num;
/*
	一定要熟悉位操作 m&n等价于m%(n+1) 
*/ 
void set(int i) // 把第i位置为1的操作 
{
	Bitmap[i >> SHIFT] |= (1 << (i & MASK));
}

int test(int i)// 检查第i位是否为1 
{
	return Bitmap[i >> SHIFT] & (1 << (i & MASK));
}

int main()
{
	freopen("data.txt", "r", stdin);
	memset(Bitmap, 0, sizeof(Bitmap)); // 将数组所有为置为0，进行初始化 
	while(scanf("%d", &num) != EOF) // 把相应的位置为1 
	{
		set(num);
	}
	for(int i = 0; i < MAX; i++) // 从第0位开始遍历，检查为1的位，并进行输出。 
	{
		if(test(i))
		{
			printf("%d ", i);
		}
	}
	printf("\nBitmap Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC);
	return 0;
}

运行时间比较
4

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define numSum 100000
#define maxNum 10000000
int a[maxNum];

double random()
{
	return (double)rand() / RAND_MAX;
}

int random(int m)
{
	return (int)(random() * (m-1) + 0.5);
}

int Random(int n, int m) //产生一定区间的随机数据 
{
	return (n + random(m-n) + 1);
}

void swap(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

int main()
{
	freopen("data.txt", "w", stdout);
	srand(time(NULL));
	for(int j = 0; j < maxNum; j++)
	{
		a[j] = j;
	} 
	for(int i = 0; i < numSum; i++) //后边区间生成随机数据，进行交换产生不同的随机数据 
	{
		int temp = Random(i, maxNum - 1);
		swap(a + i, a + temp);
		printf("%d ", a[i]);
	}
	return 0;
}