6.二叉树的基本概念，堆结构的模拟实现，堆排序和topk问题

2024-04-07 01:44
文章标签 二叉树 实现 问题 模拟 基本概念 结构 堆排序 topk

本文主要是介绍6.二叉树的基本概念，堆结构的模拟实现，堆排序和topk问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.树概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

  • 有一个特殊的结点，称为根结点，根节点没有前驱结点

  • 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

  • 因此，树是递归定义的。

image-20220831203634111

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

image-20220831203756267

1.2 树的相关概念

image-20220831204334161

注：以下概念都是通过树的特征和人类的亲缘关系形成的

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的度为6（也就是有6个子树）

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点（也就是末尾节点，叶子节点）

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为堂兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

// （了解内容）
// 节点的结构体
typedef int DataType;
struct Node
{// 第一个孩子结点struct Node*  firstChild1; // 指向其下一个兄弟结点struct Node*  pNextBrother; DataType  data; // 结点中的数据域
}

image-20220831214712310

1.4 树在实际中的运用（表示文件系统的目录树结构）

image-20220831215053961

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合：

  1. 或者为空

  2. 由一个根节点加上两棵称为左子树和右子树的二叉树组成

image-20220831215812421

从上图可以看出：

  1. 二叉树不存在度大于2的结点

  2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

image-20220831215844070

2.2特殊的二叉树：

  1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 (2^k - 1)，则它就是满二叉树。

  2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

简单解释：前k-1层是满的，第k层无论满不满，但是要求从左到右连续，就是完全二叉树

完全二叉树节点数量的范围：[2^(k-1), 2^k - 1]

image-20220831221800268

**2.3 **二叉树的性质

  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.

  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.

  • 注：2^0 + 2^1 + 2^2 +………… 2^(h-1) = 2^h-1
  1. 对任何一棵二叉树, 如果度为0的叶子结点个数为n0 , 度为2的分支结点个数为n2,则有 n0＝n2 ＋1.

image-20220902003141665

  1. 若规定根节点的层数为1，具有n个结点的满二叉树的深度为h，且 h=log(n+1),(注：log是以2为底，n+1为对数)

  2. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

  • 若i>0，i位置节点的双亲序号为(i-1)/2；若i=0，i为根节点编号，无双亲节点；注：双亲序号就是父结点
  • 若2i+1<n，左孩子序号：2i+1; 若2i+1>=n否则无左孩子
  • 若2i+2<n，右孩子序号：2i+2；若2i+2>=n否则无右孩子

  • 若child > 0，i位置节点的双亲序号：parent = (child-1)/2；child=0，child为根节点编号，无双亲节点.

  • 若2*parent+1<n，左孩子序号：child = 2*parent+1，2*parent+1>=n,则无左孩子

  • 若2*parent+2<n，右孩子序号：child = 2*parent+2，2*parent+2>=n,则无右孩子

假设：i为0，自己可以进行相应的计算

image-20240406155945455

关于二叉树性质的练习题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）   答案是B
A 不存在这样的二叉树
B 200                     //n0 = n2 + 1；
C 198
D 199

2.下列数据结构中，不适合采用顺序存储结构的是（ ）   答案是A
A 非完全二叉树
B 堆
C 队列
D 栈

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）   答案是A
A n
B n+1
C n-1
D n/2// 注：节点的度：一个节点含有的子树的个数称为该节点的度；// 在二叉树中，根节点的度就是最大是2，因为对于二叉树，一个根节点最多有2个子树
  • 解题思路

已知：如果度为0的叶子结点个数为n0 , 度为2的分支结点个数为n2,则有 n0＝n2 ＋1

我们再假设度为1的分支节点的个数为n1

因此可以得出：

  • n0 + n1 + n2 = 2n, 又因为 n0 = n2 + 1

  • 所以 n0 + n1 + n0 - 1 = 2n, ==> 2n0 + n1 - 1 = 2n

  • 因为2n和2n0都为偶数，所以n1 - 1也为偶数，所以 n1 = 1,所以叶子节点的个数为n

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）    答案是B
A 11
B 10
C 8
D 12

解题思路：

完全二叉树节点数量的范围：[2^(h-1), 2^h - 1]，

可以通过代入，来排除选项：2^(h-1) <= n <= 2^h - 1

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）    答案是B
A 383
B 384
C 385
D 386

解题思路：

注：完全二叉树度为1的节点，要不是0个，要不是1个；（这是根据完全二叉树的概念得出来的）

套用第三题的结论：n0 + n1 + n2 = 767 ==> 2n0 + n1 - 1 =767

因为767为奇数，2n0为偶数，所以n1 - 1为奇数，所以n1 = 0，所以叶子结点的个数为384

答案：
1.B
2.A
3.A
4.B
5.B

3.二叉树的顺序结构及实现（也就是堆的实现）

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

image-20220831222336743

image-20220831222611021

3.2 堆的概念及结构

如果有一个集合中有N个数，把这个集合的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。

  • 当满足任何一个父亲节点的值 <= 孩子的值（则为小根堆）

image-20220831225031763

  • 当满足任何一个父亲节点的值 >= 孩子的值（则为大根堆）

image-20220831225329125

3.3 堆的实现

1.堆的结构类型的创建

// 存储的节点的结构体
typedef int HPDataType;
typedef struct Heap
{// a指向给数组在堆上开辟的空间（这个堆是指内存，而堆结构是一种数据结构）HPDataType* a;// 空间的大小int size;// 空间的容量int capacity;
}HP;

2.堆的初始化

void HeapInit(HP* php)
{// php存储的是堆对象的地址，因此不可以为空assert(php);// 将a指向的数组空间初始化为空php->a = NULL;// 大小和容量都初始化为空php->size = php->capacity = 0;
}

3.堆中插入数据，并且保持堆的形态

image-20220831231732854

// HeapPush()这个函数，是用来给堆对象插入一个节点
// 插入x继续保持堆形态
void HeapPush(HP* php, HPDataType x)
{assert(php);// 插入一个新的节点之前，需要先检查数组的容量够不够，如果不够则需要进行扩容// 检查是否需要扩容，如果需要就扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity*sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}// 将数据插入到堆的尾部php->a[php->size] = x;php->size++;// 调整数据，保持堆的形态//堆最后一个数据的下标为size-1（即孩子节点的下标）AdjustUp(php->a, php->size - 1);
}
堆向上调整的算法
void AdjustUp(HPDataType* a, int child)
{// 通过孩子节点的下标，找到其父亲节点的下标int parent = (child - 1) / 2;// while (parent >= 0); 不建议有问题// 当child > 0说明还有其父亲节点，还可以继续向上调整while (child > 0){// 当a[child] > a[parent]时，调整出来的就是大根堆// 当a[child] < a[parent]时，调整出来的就是小根堆if (a[child] < a[parent])   {// 如果孩子节点的值小于父亲节点的值，那么就将两个值进行交换Swap(&a[child], &a[parent]);// 进行迭代child = parent;parent = (child - 1) / 2;}else{break;}}
}

4.堆的打印

void HeapPrint(HP* php)
{for (int i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}

5.返回堆顶元素

// 判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);// 堆的大小如果为0，说明当前的堆结构是空的return php->size == 0;
}

HPDataType HeapTop(HP* php)
{assert(php);// 当堆结构不为空，那么才有堆顶元素可以进行返回assert(!HeapEmpty(php));return php->a[0];
}

6.删除堆顶元素

  • 删除堆顶元素的目的是为了找次大或者次小
  1. 错误的删除方法

image-20220901133523125

2.正确删除堆顶元素的方法

image-20220901140458374

// 删除堆顶元素
void HeapPop(HP* php)
{assert(php);// 堆结构不为空，才有元素可以删除assert(!HeapEmpty(php));// 第一步：把堆顶元素与堆尾元素进行交换Swap(&php->a[0], &php->a[php->size - 1]);// 第二步，删除堆尾元素php->size--;// 第三步：使用向下调整算法，维持堆结构AdjustDown(php->a, php->size, 0);
}
堆向下调整的算法
void AdjustDown(HPDataType* a, int n, int parent)
{// 根据公式算出左孩子的下标// 假设左孩子节点的值是最小值（在左右两个孩子相比较）int minChild = parent * 2 + 1;   // n为节点的个数，如果说minChild大于等于n，那么就已经调整到最下面了，不需要进行循环了while (minChild < n){// 找出左右两个孩子节点中，值最小的节点（在左右两个孩子相比较）// minChild+1 < n是为了保证右孩子节点不越界// a[minChild + 1] < a[minChild]的条件是建小堆// a[minChild + 1] > a[minChild]的条件是建大堆if (minChild+1 < n && a[minChild + 1] < a[minChild]){minChild++; //minChild++为右孩子}// 此时minChild下标对应的节点的值是最小值（在左右两个孩子相比较）// 开始向下调整if (a[minChild] > a[parent]){// 如果孩子节点的值大于父亲节点的值，那么就交换孩子节点和父亲节点的值Swap(&a[minChild], &a[parent]);// 迭代parent = minChild;minChild = parent * 2 + 1;}else{break;}}
}

7.堆的销毁

void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

堆的完整实现

  • Heap.h
#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>// 节点的结构体
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;// 打印堆元素
void HeapPrint(HP* php);// 初始化堆
void HeapInit(HP* php);// 销毁堆
void HeapDestroy(HP* php);// 向堆插入元素
void HeapPush(HP* php, HPDataType x);// 删除堆顶元素
void HeapPop(HP* php);// 返回堆顶元素
HPDataType HeapTop(HP* php);// 判断堆是否为空
bool HeapEmpty(HP* php);// 返回堆元素的个数
int HeapSize(HP* php);
  • Heap.h
#include "Heap.h"// 打印堆元素
void HeapPrint(HP* php)
{for (int i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}// 初始化堆
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}// 销毁堆
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}// 交换堆元素的值
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 堆元素向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 插入x继续保持堆形态（堆插入一个元素）
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}// 堆元素向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1;while (minChild < n){// 找出小的那个孩子if (minChild + 1 < n && a[minChild + 1] > a[minChild]){minChild++;}if (a[minChild] > a[parent]){Swap(&a[minChild], &a[parent]);parent = minChild;minChild = parent * 2 + 1;}else{break;}}
}// 删除堆顶元素 -- 找次大或者次小
// O(logN)
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}// 返回堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}// 判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}
  • main.c
#define _CRT_SECURE_NO_WARNINGS#include "Heap.h"int main()
{//int a[] = { 15, 18, 19, 25, 28, 34, 65, 49, 27, 37 };int a[] = { 65, 100, 70, 32, 50, 60 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); ++i){HeapPush(&hp, a[i]);}HeapPush(&hp, 10);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);HeapPop(&hp);HeapPrint(&hp);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}return 0;
}

3.4 堆的应用

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  • 建堆

    • 升序：建大堆

    • 降序：建小堆

  • 利用堆删除思想来进行排序

1.向上调整建堆

image-20220901155243838

// 堆元素向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 向上调整建堆
void HeapSort(int* a, int n)
{// 建堆 -- 向上调整建堆 - 时间复杂度为O(N*logN)for (int i = 1; i < n; ++i){// 从下标为1的元素开始，向上调整，最后数组a[]就是一个堆结构的数组AdjustUp(a, i);}	
}int main()
{//int a[] = { 65, 100, 60, 32, 50, 70 };int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };HeapSort(a, sizeof(a) / sizeof(int));for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}printf("\n");return 0;
}
向上调整建堆的时间复杂度

image-20220901181233899

2.向下调整建堆

image-20220901161055530

// 堆元素向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1;while (minChild < n){// 找出小的那个孩子if (minChild + 1 < n && a[minChild + 1] > a[minChild]){minChild++;}if (a[minChild] > a[parent]){Swap(&a[minChild], &a[parent]);parent = minChild;minChild = parent * 2 + 1;}else{break;}}
}/*
// 公式
已知孩子节点求父亲节点下标
parent = (child - 1)/2
已知父亲节点求孩子节点下标
左孩子：child = 2*parent+1
右孩子：child = 2*parent+2
*/
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 - 时间复杂度为O(N)// n-1就是数组的最后一个元素// 最后一个孩子节点的父亲节点的下标为 parent = (child - 1)/2// 因此最后一个元素的父亲节点的下标就是(n-1-1)/2for (int i = (n-1-1)/2; i >= 0; --i){AdjustDown(a, n, i);}
}int main()
{//int a[] = { 65, 100, 60, 32, 50, 70 };int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };HeapSort(a, sizeof(a) / sizeof(int));for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}printf("\n");return 0;
}
向下调整建堆的时间复杂度

image-20220901175249812

3.堆排序

建大堆来排升序
  • 升序就是将一个数组的元素按从小到大依次排列
    • 当建立好一个大堆，那么对顶元素就是最大元素（时间复杂度为O(N)）
    • 将堆顶元素与堆尾元素交换，再将新的堆顶元素（前n-1个元素）向下调整，就可以得到一个新的大堆（时间复杂度为O(1)）
  • 降序就是将一个数组的元素按从大到小依次排列

image-20220901185241892

注：再往下，就是将34和1进行交换，再将前n-1个元素建成新的堆（只需要将堆顶元素向下调整一次就可以），可以看出调整n次之后就是一个升序队列

// 堆元素向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1;while (minChild < n){// 找出小的那个孩子if (minChild + 1 < n && a[minChild + 1] > a[minChild]){minChild++;}if (a[minChild] > a[parent]){Swap(&a[minChild], &a[parent]);parent = minChild;minChild = parent * 2 + 1;}else{break;}}
}// 堆排序函数（排升序）
void HeapSort(int* a, int n)
{// 大思路：选择排序，依次选数，从后往前排（先找出最大的数，再找次大的数）// 升序 -- 大堆// 降序 -- 小堆	// 第一步建立大堆// 注：堆最后一个元素的下标为n-1for (int i = (n-1-1)/2; i >= 0; --i){// 建堆 -- 向下调整建堆 - O(N)// a指向存放堆元素的空间// n是堆元素的个数// i是最后一个元素的父亲节点的下标AdjustDown(a, n, i);}// 第二步// 选数->时间复杂度为O(N*logN)int i = 1;while (i < n){// 2.1 交换堆顶元素和堆尾元素Swap(&a[0], &a[n - i]);// 向下调整的时间复杂度为O(logN)；（调整的元素个数为n-i）// 将堆顶元素向下调整AdjustDown(a, n - i, 0);++i;}
}int main()
{//int a[] = { 65, 100, 60, 32, 50, 70 };int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };HeapSort(a, sizeof(a) / sizeof(int));for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}printf("\n");return 0;
}

4. TOP-K问题

  • 求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
  1. 用数据集合中前K个元素来建堆

  • 前k个最大的元素，则建小堆

  • 前k个最小的元素，则建大堆

  1. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
  • 前k个最大的元素，则建小堆；
    • 如果与对顶元素比较，大于堆顶元素，则替换堆顶元素，最终这个堆的k个元素就是前k个最大元素

image-20220901205509832

topk的程序

#define _CRT_SECURE_NO_WARNINGS#include "Heap.h"void CreateDataFile(const char* filename, int N)
{FILE* fin = fopen(filename, "w");if (fin == NULL){perror("fopen fail");return;}srand(time(0));for (int i = 0; i < N; ++i){// rand()的范围是0~32767// 格式化打印到文件中fprintf(fin, "%d\n", rand() % 1000000);}fclose(fin);
}void PrintTopK(const char* filename, int k)
{assert(filename);FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}// 创建一个堆元素空间，这个空间可以存放k个堆元素int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail");return;}// 如何读取前K个数据for (int i = 0; i < k; ++i){// 从fout这个文件流里面读取数据，放入到指定的变量minHeap[i]中fscanf(fout, "%d", &minHeap[i]);}// 建k个数小堆for (int j = (k - 2) / 2; j >= 0; --j){AdjustDown(minHeap, k, j);}// 继续读取后N-Kint val = 0;while (fscanf(fout, "%d", &val) != EOF){// 将后N-K个数据与堆顶元素进行比较，如果大于堆顶元素，那么与对顶元素进行交换// 再将堆顶元素向下调整，维持堆结构if (val > minHeap[0]){minHeap[0] = val;AdjustDown(minHeap, k, 0);}}// 此时minHeap指向的堆空间的k个元素就是前k个最大元素for (int i = 0; i < k; ++i){printf("%d ", minHeap[i]);}free(minHeap);fclose(fout);
}int main()
{const char* filename = "Data.txt";int N = 10000;int K = 10;// 先创建一个文件，并在文件中放入数据// CreateDataFile(filename, N);// 打印文件的前topk个数据PrintTopK(filename, K);return 0;
}

fscanf()的用法

在C语言中，fscanf() 函数用于从指定的文件流中读取格式化的数据，就像 scanf() 函数用于从标准输入流（键盘）中读取输入一样。它的原型如下：

int fscanf(FILE *stream, const char *format, ...);
  • stream 是一个指向已打开文件的指针，用于指定要从中读取数据的文件流。
  • format 是一个格式化字符串，用于指定要读取的数据的格式。
  • ... 表示可变数量的参数，用于存储从文件中读取的数据。

fscanf() 函数按照格式字符串 format 中指定的格式从文件流 stream 中读取数据，并将其存储到指定的变量中。函数返回成功读取并转换的参数个数，如果读取失败或到达文件末尾，则返回 EOF（-1）。

以下是一个示例代码，演示了如何使用 fscanf() 函数从文件中读取格式化的数据：

#include <stdio.h>int main() {FILE *fp;int num1, num2;float num3;fp = fopen("data.txt", "r");if (fp == NULL) {perror("Error opening file");return -1;}// 从文件中读取整数和浮点数fscanf(fp, "%d %d %f", &num1, &num2, &num3);printf("Read numbers: %d, %d, %.2f\n", num1, num2, num3);fclose(fp);return 0;
}

在这个示例中，程序打开名为 data.txt 的文件，并使用 fscanf() 函数从文件中读取格式化的数据。第一个 %d 表示读取一个整数，第二个 %d 表示读取另一个整数，第三个 %f 表示读取一个浮点数。读取到的数据分别存储到变量 num1、num2 和 num3 中，并打印到屏幕上。最后，关闭文件流。

这篇关于6.二叉树的基本概念，堆结构的模拟实现，堆排序和topk问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/881347。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2