数据结构实践——败者树归并模拟

2024-03-03 06:58

本文主要是介绍数据结构实践——败者树归并模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文是针对[数据结构基础系列(10):外部排序]中的实践项目。

【项目】败者树归并模拟
  编写程序,模拟改者树实现5路归并算法的过程。
  设有5个文件,其中的记录的关键字如下:
  F0:{17,21,∞} F1:{5,44,∞} F2:{10,12,∞}F3: {29,32,∞} F4: {15,56,∞}
  要求将其归并为一个有序段并输出。
  假设这些输入文件数据保存在内存中,输出结果也不必输出到文件,而是在屏幕上输出即可。

参考解答

#include <stdio.h>
#define MaxSize 20          //每个文件中最多记录
#define K 5                 //5路平衡归并
#define MAXKEY 32767        //最大关键字值∞
#define MINKEY -32768       //最小关键字值-∞
typedef int InfoType;
typedef int KeyType;
typedef struct              //记录类型
{KeyType key;            //关键字项InfoType otherinfo;     //其他数据项,具体类型在主程中定义
} RecType;
typedef struct
{RecType recs[MaxSize];int currec;
} FileType;                 //文件类型
typedef int LoserTree[K];   //败者树是完全二叉树且不含叶子
RecType b[K];               //b中存放各段中取出的当前记录
FileType F[K];              //存放文件记录的数组
void initial()
{int i;                  //5个初始文件,当前读记录号为-1F[0].recs[0].key=17;F[0].recs[1].key=21;F[0].recs[2].key=MAXKEY;F[1].recs[0].key=5;F[1].recs[1].key=44;F[1].recs[2].key=MAXKEY;F[2].recs[0].key=10;F[2].recs[1].key=12;F[2].recs[2].key=MAXKEY;F[3].recs[0].key=29;F[3].recs[1].key=32;F[3].recs[2].key=MAXKEY;F[4].recs[0].key=15;F[4].recs[1].key=56;F[4].recs[2].key=MAXKEY;for (i=0;i<K;i++)F[i].currec=-1;
}
void input(int i,int &key)  //从F[i]文件中读一个记录到b[i]中
{F[i].currec++;key=F[i].recs[F[i].currec].key;
}
void output(int q)      //输出F[q]中的当前记录
{printf("输出F[%d]的关键字%d\n",q,F[q].recs[F[q].currec].key);
}
void Adjust(LoserTree ls,int s)
//沿从叶子节点b[s]到根节点ls[0]的路径调整败者树
{int i,t;t=(s+K)/2;          //ls[t]是b[s]的双亲节点while(t>0){if(b[s].key>b[ls[t]].key){i=s;s=ls[t];    //s指示新的胜者ls[t]=i;}t=t/2;}ls[0]=s;
}
void display(LoserTree ls)  //输出败者树
{int i;printf("败者树:");for (i=0;i<K;i++)if (b[ls[i]].key==MAXKEY)printf("%d(∞) ",ls[i]);else if (b[ls[i]].key==MINKEY)printf("%d(-∞) ",ls[i]);elseprintf("%d(%d) ",ls[i],b[ls[i]].key);printf("\n");
}
void CreateLoserTree(LoserTree ls)      //建立败者树
{int i;b[K].key=MINKEY;    //b[K]置为最小关键字for (i=0;i<K;i++)ls[i]=K;        //设置ls中“败者”的初值,全部为最小关键字段号for(i=K-1;i>=0;--i) //依次从b[K-1],b[K-2],…,b[0]出发调整败者Adjust(ls,i);
}
void K_Merge(LoserTree ls)  //利用败者树ls将进行K路归并到输出
{int i,q;for(i=0;i<K;++i)        //分别从k个输入归并段读入该段当前第一个记录的关键字到binput(i,b[i].key);CreateLoserTree(ls);    //建败者树ls,选得最小关键字为b[ls[0]].keydisplay(ls);while(b[ls[0]].key!=MAXKEY){q=ls[0];            //q指示当前最小关键字所在归并段output(q);          //将编号为q的归并段中当前(关键字为b[q].key)的记录输出input(q,b[q].key);  //从编号为q的输入归并段中读人下一个记录的关键字if (b[q].key==MAXKEY)printf("从F[%d]中添加关键字∞并调整\n",q);elseprintf("从F[%d]中添加关键字%d并调整\n",q,b[q].key);Adjust(ls,q);       //调整败者树,选择新的最小关键字display(ls);}
}
int main()
{LoserTree ls;initial();K_Merge(ls);printf("\n");return 0;
}

这篇关于数据结构实践——败者树归并模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/768840

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

tomcat多实例部署的项目实践

《tomcat多实例部署的项目实践》Tomcat多实例是指在一台设备上运行多个Tomcat服务,这些Tomcat相互独立,本文主要介绍了tomcat多实例部署的项目实践,具有一定的参考价值,感兴趣的可... 目录1.创建项目目录,测试文China编程件2js.创建实例的安装目录3.准备实例的配置文件4.编辑实例的

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

springboot集成Deepseek4j的项目实践

《springboot集成Deepseek4j的项目实践》本文主要介绍了springboot集成Deepseek4j的项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录Deepseek4j快速开始Maven 依js赖基础配置基础使用示例1. 流式返回示例2. 进阶

Android App安装列表获取方法(实践方案)

《AndroidApp安装列表获取方法(实践方案)》文章介绍了Android11及以上版本获取应用列表的方案调整,包括权限配置、白名单配置和action配置三种方式,并提供了相应的Java和Kotl... 目录前言实现方案         方案概述一、 androidManifest 三种配置方式

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

Ubuntu中Nginx虚拟主机设置的项目实践

《Ubuntu中Nginx虚拟主机设置的项目实践》通过配置虚拟主机,可以在同一台服务器上运行多个独立的网站,本文主要介绍了Ubuntu中Nginx虚拟主机设置的项目实践,具有一定的参考价值,感兴趣的可... 目录简介安装 Nginx创建虚拟主机1. 创建网站目录2. 创建默认索引文件3. 配置 Nginx4

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》:本文主要介绍了如何使用CSS模拟HTML的title属性,通过鼠标悬浮显示提示文字效果,通过设置`.tipBox`和`.tipBox.tipContent`的样式,实现了提示内容的隐藏和显示,详细内容请阅读本文,希望能对你有所帮助... 效