关键词:
本文是针对[数据结构基础系列(10):外部排序]中的实践项目。
【项目 】置换-选择算法模拟
编敲代码,模拟置换-选择算法生成初始归并段的过程。
设大文件里的记录共同拥有18个: 15 4 97 64 17 32 108 44 76 9 39 82 56 31 80 73 255 68
内存工作区能够容纳5个记录,输出产生的归并段文件。
在模拟中,输入文件数据和输出的归并段数据均直接置在内存中就可以。
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 50 //每一个文件最多记录数
#define MAXKEY 32767 //最大关键字值∞
#define W 5 //内存工作区可容纳的记录个数
typedef int LoserTree[W]; //败者树是全然二叉树且不含叶子,可採用顺序存储结构
typedef int InfoType; //定义其它数据项的类型
typedef int KeyType; //定义关键字类型为整型
typedef struct //记录类型
{
KeyType key; //关键字项
InfoType otherinfo; //其它数据项,详细类型在主程中定义
} RecType;
typedef struct
{
RecType rec; //存放记录
int rnum; //所属归并段的段号
} WorkAreaType;
typedef WorkAreaType WorkArea[W]; //内存工作区,容量为W
typedef struct
{
RecType recs[MaxSize]; //存放文件里的数据项
int length; //存放文件里实际记录个数
int currec; //存放当前位置
} FileType; //文件类型
FileType Fi; //定义输入文件,为全局变量
FileType Fo; //定义输出文件,为全局变量
void initial() //输入输出文件初始化
{
int n=19,i;
KeyType a[]= {15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68,MAXKEY};
for (i=0; i<n; i++)
Fi.recs[i].key=a[i];
Fi.length=n;
Fi.currec=-1;
Fo.currec=-1;
Fo.length=0;
}
void Select_MiniMax(LoserTree ls, WorkArea wa,int q)
//从wa[q]起到败者树的根比較选择最小记录,并由q指示它所在的归并段
{
int p,s,t;
for (t=(W+q)/2,p=ls[t]; t>0; t=t/2,p=ls[t])
if ((wa[p].rnum<wa[q].rnum) || (wa[p].rnum==wa[q].rnum && wa[p].rec.key<wa[q].rec.key))
{
s=q;
q=ls[t]; //q指示新的胜者
ls[t]=s;
}
ls[0]=q;
}
void Construct_Loser(LoserTree ls,WorkArea wa)
//输入W个记录到内存工作区wa,建败者树ls,选最小的记录并由s指示其在wa中的位置
{
int i;
for(i=0; i<W; i++)
wa[i].rnum=wa[i].rec.key=ls[i]=0; //工作区初始化
for(i=W-1; i>=0; i--)
{
Fi.currec++; //从输入文件读入一个记录
wa[i].rec=Fi.recs[Fi.currec];
wa[i].rnum=1; //其段号为1
Select_MiniMax(ls,wa,i); //调整败者
}
}
void get_run(LoserTree ls,WorkArea wa,int rc,int &rmax)
//求得一个初始归并段
{
int q;
KeyType minimax; //当前最小关键字
while (wa[ls[0]].rnum==rc) //选得的当前最小记录属当前段时
{
q=ls[0]; //q指示当前最小记录在wa中的位置
minimax=wa[q].rec.key;
Fo.currec++; //将刚选得的当前最小记录写入输出文件
Fo.length++;
Fo.recs[Fo.currec]=wa[q].rec;
Fi.currec++; //从输入文件读入下一记录
wa[q].rec=Fi.recs[Fi.currec];
if (Fi.currec>=Fi.length-1) //输入文件结束,虚设记录(属rmax+1段)
{
wa[q].rnum=rmax+1;
wa[q].rec.key=MAXKEY;
}
else //输入文件非空时
{
if(wa[q].rec.key<minimax)
{
rmax=rc+1; //新读入的记录属下一段
wa[q].rnum=rmax;
}
else //新读入的记录属当前段
wa[q].rnum=rc;
}
Select_MiniMax(ls,wa,q); //选择新的当前最小记录
}
}
void Replace_Selection(LoserTree ls,WorkArea wa)
//在败者树ls和内存工作区wa上用置换-选择排序求初始归并段
{
int rc,rmax;
RecType j; //j作为一个关键字最大记录,作为一个输出段结束标志
j.key=MAXKEY;
Construct_Loser(ls,wa); //初建败者树
rc=1; //rc指示当前生成的初始归并段的段号
rmax=1; //rmax指示wa中关键字所属初始归并段的最大段号
while(rc<=rmax) //rc=rmax+1标志输入文件的置换-选择排序已完毕
{
get_run(ls,wa,rc,rmax); //求得一个初始归并段
Fo.currec++; //将段结束标志写入输出文件
Fo.recs[Fo.currec]=j;
Fo.length++;
rc=wa[ls[0]].rnum; //设置下一段的段号
}
}
int main()
{
int i=0,rno=1;
initial();
LoserTree ls;
WorkArea wa;
printf("大文件的记录为:
");
while (Fi.recs[i].key!=MAXKEY)
{
printf("%d ",Fi.recs[i].key);
i++;
}
printf("
");
Replace_Selection(ls,wa); //用置换-选择排序求初始归并段
printf("产生的归并段文件的记录例如以下:
");
printf(" 归并段%d:",rno); //输出全部的归并段
for (i=0; i<Fo.length; i++)
if (Fo.recs[i].key==MAXKEY)
{
printf("∞");
if (i<Fo.length-1)
{
rno++;
printf("
归并段%d:",rno);
}
}
else
printf("%d ",Fo.recs[i].key);
printf("
共产生%d个归并段文件
",rno);
return 0;
}
数据结构精要------直接选择和堆排序算法
上篇总结中主要实践了算法的内排序的交换排序,那么接下来我们继续实践选择排序的两种:直接选择和堆排序算法。-----直接选择排序packagecom.sort;/***直接选择排序算法*@authorweixing-yang**算法思路:*首先找出最大元素,将其与a[n... 查看详情
lru置换算法(代码片段)
LRU置换算法1、实践内容说明已知系统为一进程分配的物理块数,进程运行过程中引用的页面号,编程使用LRU算法输出置换的页号、缺页中断次数及缺页率。2.算法描述1、从内存调出一页程序或数据到磁盘的对换区,... 查看详情
fifo页面置换模拟
操作系统之模拟FIFO页面置换界面采用javaGUI制作,共有两个类一个做框架一个做算法,部分方法设成静态,方便相互调用页面序列生成方式页面序列采用1-9之间任意整数,自定义页面序列或者给定页面数随机生成快表慢表页数时... 查看详情
lru置换算法(代码片段)
LRU置换算法1、实践内容说明已知系统为一进程分配的物理块数,进程运行过程中引用的页面号,编程使用LRU算法输出置换的页号、缺页中断次数及缺页率。2.算法描述1、从内存调出一页程序或数据到磁盘的对换区,... 查看详情
页面置换算法
...据,送入磁盘的对调区。选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面改换频率,也就是说,应将今后不会再拜访或许今后较长工夫内不会再拜访的页面先调出。罕见的置换算法有以下四种。1.最... 查看详情
操作系统概念页面置换算法:分别使用fifooptlru三种置换算法来模拟页面置换的过程。
关于页面置换算法的理论知识:https://www.bilibili.com/video/BV1YE411D7nH?p=45C++代码实现(未优化)#include<iostream>#include<fstream>#include<cstring>usingnamespacestd;intframe_length;//帧个数intstring_length; 查看详情
置换-选择算法
置换-选择算法为什么要引入置换-选择排序算法实现步骤后续为什么要引入置换-选择排序我们都知道,减少初始归并段个数r可以减少归并趟数S。若总的记录个数为n,每个归并段的长度为t,则归并段的个数为r=[n/t]... 查看详情
页面置换算法
...入新的页面而内存已满时,选择内存当中哪个物理页面被置换。目标:尽可能地减少页面的换进换出次数(即缺页中断的次数)。具体来说,把未来不再使用的或短期内较少使用的页面换出,通常只能在局部性原理指导下依据过去... 查看详情
lru和fifo页面置换算法模拟实战(代码片段)
Introduction本文将介绍如何使用LRU和FIFO实现页面置换的模拟(Python实现),并使用缺页率进行算法的评价。Requirement先附上具体的要求:【实验目的】(1)了解内存分页管理策略(2)掌握调页策略(3&... 查看详情
几种置换算法
...的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰... 查看详情
页面置换算法
...个页面调出,需根据一定的算法来实现。 常见的页面置换算法有: 1.最佳置换算法(Optimal) 从内存中移除永远都不再需要的页面或者说是未来最长时间内不再被访问的页面,如果这样的页面存在,则选择最长时间 查看详情
三种页面置换算法的c++模拟(代码片段)
1#include<iostream>2usingnamespacestd;3intpage[]=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,-1;4voidFIFO();5voidOPT();6voidRLU();7boolinArray(int*a,intn,intp);8intmain(void)9FIFO();10OPT();11RLU 查看详情
页面置换算法的常见的置换算法
参考技术A最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是,总是选择在主存中停留时间最长(即最老)的一页置换,即先进入内存的页,先退出内存。理由是:最早调入内存的页,其不再被使用的可能性比刚调... 查看详情
页面置换算法之clock算法
...,如果还有新的页面要被缓冲到池中,就要设计一种页面置换的算法,将一个旧的页面替换成新的页面。一般来说我们熟悉的算法有下面几种:下面逐一介绍各种算法。2.最佳置换算法如果被替换掉的页是以后再也不会使用的,... 查看详情
置换-选择算法
置换-选择算法为什么要引入置换-选择排序算法实现步骤后续为什么要引入置换-选择排序我们都知道,减少初始归并段个数r可以减少归并趟数S。若总的记录个数为n,每个归并段的长度为t,则归并段的个数为r=[n/t]... 查看详情
操作系统页面置换算法lru和fifo
LRU(LeastRecentlyUsed)最少使用页面置换算法,顾名思义,就是替换掉最少使用的页面。FIFO(firstinfirstout,先进先出)页面置换算法,这是的最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最... 查看详情
页面置换算法
...到内存中,但此时内存已满,就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。 本文内容 算法思想:每次选择淘汰的页面将是以后永不使用,或者... 查看详情
寒假15(前n个数的随机置换的两个算法)(随机数产生)
具体实现过程见substitutionofintfrom1ton 随机数算法知识:kitty的随机数算法博客; 蒙特卡洛法:统计实验法,大量模拟求概率,用于不可解析函数,或概率分布,的模拟与计算时将所求解的问题同一定的概率模型相... 查看详情