#include<iostream>
#include<iomanip>
using namespace std;
typedef struct Track
{
int track;
int priority;
struct Track *next;
}*TrackList;
void BuildTrackList(TrackList &p,int count)//建立磁盘访问序列
{
p = (TrackList)malloc(sizeof(TrackList));
TrackList q=p;
cout<<"请输入磁道的访问序列:";
for(int i = 0;i<count;i++)
{
q->next = (TrackList)malloc(sizeof(TrackList));
cin>>q->next->track;
q->next->priority = 0;
q = q->next;
}
q->next = NULL;
}
int CalculatePriority(TrackList &p,int diskHead)//计算优先数
{
if(p->track >= diskHead)
return p->priority = p->track-diskHead;
else
return p->priority = diskHead - p->track;
}
void SetPriority(TrackList &p,int diskHead)//设置每一个优先数
{
TrackList q = p->next;
while(q != NULL)
{
if(q->priority >= 0)
CalculatePriority(q,diskHead);
q = q->next;
}
}
int FindMinPriority(TrackList &p,int &diskHead)//找出最小的优先数并修改为-1,返回新的diskHead
{
TrackList q = p->next->next;
TrackList min = p->next;
while(q != NULL)
{
if((min->priority > q->priority && min->priority>=0 && q->priority>=0)||(min->priority < q->priority && min->priority<0 && q->priority>=0))
min=q;
q = q->next;
}
cout<<setw(3)<<setiosflags(ios::right)<<min->track<<" "<<setw(3)<<setiosflags(ios::right)<<min->priority<<endl;
int i = min->priority;
min->priority = -1;
diskHead = min->track;
return i;
}
void SSTF(TrackList p,int count,int diskHead)//
{
int i=0;
int sumTime=0;
int flag = count;
cout<<" "<<"磁道"<<" "<<"寻道时间"<<endl;
while( flag != 0)
{
i++;
SetPriority(p,diskHead);
cout<<"第"<<i<<"次访问:";
sumTime = sumTime + FindMinPriority(p,diskHead);
flag--;
}
cout<<"平均寻道时间为:"<<(float)sumTime/(float)count<<endl;
}
TrackList FindBehind(TrackList p,TrackList target)
{//找出节点的前驱
while(p->next != target)//要注意p的初始值
{
p = p->next;
}
return p;
}
void Ordering(TrackList &p)
{//对序列排序(从小到大)
TrackList q = p->next;
TrackList tail = NULL,max = p->next;
while(q->next != NULL)
{
q = q->next;
}
tail = q;
q = p->next->next;
while(tail != p->next)
{
while(q != tail->next)
{
if(max->track < q->track)
{
max = q;
}
q = q->next;
}
int t = max->track;
max->track = tail->track;
tail->track = t;
max = p->next;
q = p->next->next;
tail = FindBehind(p,tail);
}
}
void FCFS(TrackList p,int diskHead, int count)
{
int i=0;
int sumTime=0;
p = p->next;
cout<<" "<<"磁道"<<" "<<"寻道时间"<<endl;
while(p != NULL)
{
cout<<"第"<<++i<<"次访问:";
cout<<setw(3)<<setiosflags(ios::right)<<p->track<<" "<<setw(3)<<setiosflags(ios::right)<<CalculatePriority(p,diskHead)<<endl;
diskHead = p->track;
sumTime += p->priority;
p = p->next;
}
cout<<"平均寻道时间为:"<<(float)sumTime/(float)count<<endl;
}
TrackList FindDiskHead(TrackList p,int diskHead)
{//找出磁道数大于等于diskhead的位置,或者不存在则为最后一各节点
TrackList q = p->next;
while(1)
{
if(q->track >= diskHead||q->next == NULL)
return q;
q = q->next;
}
}
void SCANAndFSCAN(TrackList p,int diskHead,int count,int choose)
{//choose为选择算法为1时是scan算法,为其它数时是fscan
int i=0;
TrackList flag = FindDiskHead(p,diskHead);
TrackList q = flag;
int sumTime=0;
cout<<" "<<"磁道"<<" "<<"寻道时间"<<endl;
while(q != NULL)
{
cout<<"第"<<++i<<"次访问:";
cout<<setw(3)<<setiosflags(ios::right)<<q->track<<" "<<setw(3)<<setiosflags(ios::right)<<CalculatePriority(q,diskHead)<<endl;
diskHead = q->track;
sumTime += q->priority;
q = q->next;
}
if(choose == 1)
{
q = FindBehind(p,flag);
while(q != p)
{
cout<<"第"<<++i<<"次访问:";
cout<<setw(3)<<setiosflags(ios::right)<<q->track<<" "<<setw(3)<<setiosflags(ios::right)<<CalculatePriority(q,diskHead)<<endl;
diskHead = q->track;
sumTime += q->priority;
q = FindBehind(p,q);
}
}
else
{
q = p->next;
while(q != flag)
{
cout<<"第"<<++i<<"次访问:";
cout<<setw(3)<<setiosflags(ios::right)<<q->track<<" "<<setw(3)<<setiosflags(ios::right)<<CalculatePriority(q,diskHead)<<endl;
diskHead = q->track;
sumTime += q->priority;
q = q->next;
}
}
cout<<"平均寻道时间为:"<<(float)sumTime/(float)count<<endl;
}
int main()
{
int choose=1;
int count = 0;
int diskHead;
TrackList p;
cout<<"请输入磁头的位置:";
cin>>diskHead;
cout<<"请输入要访问的次数:";
cin>>count;
BuildTrackList(p,count);
cout<<"FCFS:"<<endl;
FCFS(p,diskHead,count);
Ordering(p);
cout<<"SSTF:"<<endl;
SSTF(p,count,diskHead);
cout<<"SCAN"<<endl;
SCANAndFSCAN(p,diskHead,count,choose);
cout<<"FSCAN:"<<endl;
choose = 0;
SCANAndFSCAN(p,diskHead,count,choose);
return 0;
}
评论0