《编程珠玑》中的问题用C实现——1
问题描述:一顺序文件中至多存在10000000个记录,每条记录都是一个7位整数,请对此文件中数据进行排序。
要求:1.程序可使用内存只有1MB。2.程序运行时间尽可能的短。
补充说明:每个记录都是一个7位正整数,并且没有其他的关联数据,每个整数至多只能出现一次。
实现纲要:
在现实中,位图和位向量很常见,我们可以使用一个20位的字符串来表示一个小型的小于20的非负整数集合。例如:我们可以将集合{1,2,3,5,8,13}存储在下面这个字符串中:01110100100001000000.集合中代表数字 的各个位设置为1,而其他的位全部都设为0.
在现实问题中,每个整数的7个十进制数字表示了一个小于千万的数字。我们将使用一个具有一千万位的字符串表示该文件,在该字符串中,当且公当整数i在该文件中时,第i个位才打开(设为1)。
实现代码:
1.位操作头文件:bit.h
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#ifndef BIT_H
#define BIT_H
#define BIT_SIZE 10000000
#define BIT_UNIT int
unsigned int GetBitUnitSize(void);
unsigned int GetBitArraySize(void);
void InitBitArray(BIT_UNIT *p);
void SetBitValue(BIT_UNIT *p, unsigned int bit, short val);
unsigned short GetBitValue(BIT_UNIT *p, unsigned int bit);
void PrintArrayList(BIT_UNIT *p);
BIT_UNIT SetIndexBitValue(unsigned short index);
#endif
2.位操作c文件:bit.c
#include "bit.h"
unsigned int GetBitUnitSize(void)
{
return sizeof(BIT_UNIT) * 8;
}
unsigned int GetBitArraySize(void)
{
return BIT_SIZE / GetBitUnitSize();
}
void InitBitArray(BIT_UNIT *p)
{
int array_size = GetBitArraySize();
int unit_size = GetBitUnitSize();
int i = 0;
for (i = 0; i < array_size; i++)
*(p + i) = *(p + i) << unit_size;
}
void SetBitValue(BIT_UNIT *p, unsigned int bit, short val)
{
if (bit >= BIT_SIZE) return;
unsigned int array_size = GetBitArraySize();
unsigned short unit_size = GetBitUnitSize();
unsigned int unit_index = bit / unit_size;
unsigned short bit_index = bit % unit_size;
if (bit_index == 0) {
unit_index--;
bit_index = unit_size;
}
相关文档:
编译,编译程序读取源程序(字符流),对之进行词法和语法的分析,将高级语言指令转换为功能等效的汇编代码,再由汇编程序转换为机器语言,并且按照操作系统对可执行文件格式的要求链接生成可执行程序。
C源程序头文件-->预编译处理(cpp)-->编译程序本身-->优化程序-->汇编程序-->链接程序--> ......
1.区别(主要的):指针需要增加一次额外的提取操作
编译器为每个变量分配一个地址(左值)。这个地址编译时可知,而且该变量在运行时一直保存于这个地址。相反,存储于变量中的值(它的右值)只有在运行时才可知。如果需要用到变量中存储的值,编译器就发出指令从地址读入变量值并将它存于寄存器中。
  ......
C/C++中Static的作用详述
1.先来介绍它的第一条也是最重要的一条:隐藏。
当我们同时编译多个文件时,所有未加static前缀的全局变量和函数都具有全局可见性。为理解这句话,我举例来说明。我们要同时编译两个源文件,一个是a.c,另一个是main.c.
下面是a.c的内容:
char a = 'A'; // global variable
void ......
VC中下面几个结构体大小分别是多少呢
struct MyStruct
{
double m4;
char m1;
int m3;
};
struct MyStruct {
char m1;
double m4;
int m3;
};
#pragma pack(push)   ......
一、 函数参数传递机制的基本理论 函数参数传递机制问题在本质上是调用函数(过程)和被调用函数(过程)在调用发生时进行通信的方法问题。基本的参数传递机制有两种:值传递和引用传递。以下讨论称调用其他函数的函数为主调函数,被调用的函数为被调函数。 值传递(passl-by-value)过程中,被调函数的形式参 ......