内容型网站,中铁建设集团有限公司招标网,网站审核备案 几天,超低价虚拟主机标题#xff1a;C语言库函数scanf#xff08;#xff09;解读
水墨不写bug #xff08;图片来源于网络#xff09;
正文开始#xff1a; Top-K问题是一类问题的统称#xff1a; 即根据对象的某一属性#xff0c;找出这个属性最突出的K个对象#xff0c;并且通常对象…标题C语言库函数scanf解读
水墨不写bug 图片来源于网络
正文开始 Top-K问题是一类问题的统称 即根据对象的某一属性找出这个属性最突出的K个对象并且通常对象的数量极大。 一构造对象 为演示方便通过代码生成一个数据量极大的数据对象生成1w个数据如果我们将问题抽象化为找出1w个数据中的最大5个数那么Top-K问题就切实可见了。 在你的编译器上输入如下代码并运行你会发现在同目录下多了一个文件data.txt
#includestdio.h
#includestdlib.hvoid CreateNDate()
{// 造数据int n 10000;srand(time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (size_t i 0; i n; i){int x rand() % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}
再打开文件人为的将5个数改写为最大并做好记录。
二建堆并解决过程 打开文件并读入数据读入并压入k个数据这时堆内已有k个数据 接下来每读入一个数据就需要堆顶部的数据进行比较
找出最大K个数这种情况需要建立小堆因为小堆的堆顶数据是这个堆里最小的最小的数与读入的数进行比较。如果读入的数比较大就将较小的堆顶交换出去如果读入的数比较小就保留堆顶的数据
找出最小K个数这种情况需要建立大堆因为大堆的堆顶数据是这个堆里最大的最大的数与读入的数进行比较。如果读入的数比较小就将较大的堆顶交换出去如果读入的数比较大就保留堆顶的数据 这样既能利用堆的高效插入和高效删除又避免了开辟大量的空间来存储变量。 #includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef int HPDatatype;typedef struct Heap
{HPDatatype* a;int size;int capacity;
}HP;
void AdgustDown(HPDatatype* a, int n, int parent);//初始化
void HPinit(HP* php);//销毁
void HPDestroy(HP* php);//插入数据
void HPpush(HP* php, HPDatatype x);//删除数据规定删除堆顶的数据
void HPpop(HP* php);//得到堆顶数据
HPDatatype HPtop(HP* php);//判空
bool HPempty(HP* php);//数据个数
int HPsize(HP* php);//初始化
void HPinit(HP* php)
{assert(php);php-capacity php-size 0;//size指向最后一个元素的下一个php-a NULL;
}//销毁
void HPDestroy(HP* php)
{assert(php);php-capacity php-size 0;free(php-a);
}//交换函数
void Swap(HPDatatype* a,HPDatatype* b)
{HPDatatype tem *a;*a *b;*b tem;
}//此处模拟实现小堆,小数上移
//参数
//要插入的数据和孩子节点的数组下标
void AdgustUp(HPDatatype* a,int child)
{//根据公式不论是左孩子还是右孩子都可以计算得到int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//插入数据
void HPpush(HP* php, HPDatatype x)
{assert(php);//如果size capacity 说明顺序表满了,或者没有一个数据if (php-size php-capacity){int Newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDatatype* tem (HPDatatype*)realloc(php-a, sizeof(HPDatatype)*Newcapacity);{if (tem NULL){perror(realloc fail!);return;}}php-a tem;php-capacity Newcapacity;}//开辟好空间后插入php-a[php-size] x;php-size;//向上调整AdgustUp(php-a,php-size-1);
}//向下调整
//参数
//顺序表数据总个数向下调整时目前双亲节点的数组下标
void AdgustDown(HPDatatype* a,int n,int parent)
{int child parent * 2 1;//目前假设左孩子小while (child n){ //如果右孩子存在并比左孩子小选择右孩子if (child 1 n a[child] a[child 1]){child;}//此时孩子表示较小的孩子if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else {break;}}
}//删除数据规定删除堆顶的数据
void HPpop(HP* php)
{assert(php);Swap(php-a[0], php-a[php-size - 1]);--php-size;AdgustDown(php-a,php-size,0);
}//得到堆顶数据
HPDatatype HPtop(HP* php)
{assert(php);return php-a[0];
}//判空
//若为空返回真否则返回假
bool HPempty(HP* php)
{assert(php);return php-size 0;
}//数据个数
int HPsize(HP* php)
{assert(php);return php-size;
}int main()
{//CreateNDate();FILE* fin fopen(data.txt, r);if (fin NULL){perror(fopen error);return;}int comp 0;HP ph;HPinit(ph);int k 0;scanf(%d, k);//刚开始push k次建堆for (int i 0; i k; i){fscanf(fin, %d, comp);HPpush(ph, comp);}//开始比较comp与堆顶数据的大小while (fscanf(fin,%d,comp) ! EOF){if (ph.a[0] comp){Swap(ph.a[0], comp);AdgustDown(ph.a,ph.size,0);}}for (int i 0; i k; i){printf(%d , ph.a[i]);}return 0;
} 注意 先调用CreateNDate()函数来创建一个数据文件标记好最大K个数后再运行上述代码来验证。 完~
未经作者同意禁止转载
