os.cpp

编程序实现下述磁盘调度算法

#include<stdio.h> /*库文件包含*/ 
#include<string.h> /*用于字符串操作*/ 
#include<stdlib.h> /*用于exit函数*/ 
#include <math.h>
#include <process.h>
#include <iostream.h>


typedef struct node{
	int data;//数据域
    struct node *next;//指针域
}Node; //变量名
                 //把磁盘定义为链表

void creat();//建立链表
void fcfs(Node *head,int c,int f);//声明先来先服务函数
void sstf(Node *head,int c,int f);//声明最短寻道时间优先函数
void scan(Node *head,int c,int f);//声明扫描函数
void cscan(Node *head,int c,int f);//循环扫描算法
void nstepscan(Node *head,int c,int f);//N步扫描算法
void print(Node *);     //输出链表函数
int f,c=0;
Node *head;


void	main()
 {  
    // system("color 1f");
   //system("title 多功能工具");
   // system("MODE con: COLS=74 lines=25");
///	Node *p,*q,*s,*head;
	

	int cord;
	do{ 
//	system("cls"); //清屏 
       printf("\n---------------------------------------------\n");
       printf("\n                   主菜单 \n\n"); 
	   printf(" 1  建立要访问的磁道号    2  输入从第几磁道开始\n\n");
	   printf(" 3  先来先服务算法        4  最短寻道时间算法\n\n");
	   printf(" 5  扫描算法              6  循环扫描算法 \n\n");
       printf(" 7  N步扫描算法           0  退出  \n\n");
	   printf("----------------------------------------------\n");
	   printf("请输入你的选择 1,2,3,4,5,6其中一个:\n");
	   //cord=getnumber(6);
         
           scanf("%d",&cord);
       
	   switch(cord)
	   {
	   case 1:{creat();
		   }break;
	   case 2:{
		      printf("\n开始的磁道号: ");
			  scanf("%d",&f);
		  } break;
			
	    case 3:{fcfs(head,c,f);
			}break;
		case 4:{sstf(head,c,f);
			   }break;
	    case 5:{scan(head,c,f);
		    }break;
		case 6:{cscan(head,c,f);
			   }break;
	    case 7:{nstepscan(head,c,f);
			   }break;
	
	    case 0:exit(0);
	    }
	}while(cord<=7&&cord>=0);
}


/************************************************************************** 
void print(Node *head)
输入参数： 
结构体链表
返回参数： 
空
功能： 
按顺序输出链表中的数值
***************************************************************************/
void print(Node *head)//输出链表
{
	Node *p;
	p=head->next;
	if(p==NULL)
	{
		printf("单链表为空:");
	}else 
	{
		while(p!=NULL)
		{
			printf("%4d",p->data);
			p=p->next;
		}
	}
}

/************************************************************************** 
  void creat()
输入参数： 
空
返回参数： 
空
功能： 
建立线性链表, 
***************************************************************************/
  void creat()
  {
	  int x;Node *ptr,*p;
      head=(Node *)malloc(sizeof(Node));
      head->next=NULL;p=head;
      printf("\n 输入 0 结束\n\n x=?  ");scanf("%d",&x);
      while(x!=0)
	  {
		  ptr=(Node *)malloc(sizeof(Node));
          ptr->data=x;ptr->next=NULL;
          p->next=ptr;
          p=ptr;
          printf(" x=?  ");scanf("%d",&x);
  		  c++;
	  }printf("链表中的顺序是:");
	  print(head);
  }


/************************************************************************** 
 void fcfs(Node *head,int c,int f)
输入参数： 
Node *head :要扫描的磁道的线性结构体。int c:磁道号总数  int f :开始扫描的磁道 
返回参数： 
无
功能： 
按照fcfs的原则,按链表中的顺序,读取其中的数值,并且输出结果。
链表中前面的数先读取. 
***************************************************************************/
 void fcfs(Node *head,int c,int f)//先来先服务算法确         
 {
	  
	  node *l;//中间变量
	  float num=0;//NUM是总的寻道长度
	  l=head->next;
	  for(int i=0;i<c;i++)
	  {
		  num+=abs(l->data-f);//求绝对值的函数 DATA 是位置 L是后一道,F是前一道的位置
		  f=l->data;//下一次循开始点环指向改变,具体说是前一移动了一位
		  l=l->next;//要找的点也改变为下一个
	  }
	  num=num/c;//总长度除以次数就是平均的长度
	  printf("\n先来先服务的寻道顺序是");
	  print(head);
	  printf("\n平均寻道长度%f",num);
 }



/************************************************************************** 
sstf(Node *head,int c,int f)
输入参数： 
Node *head :要扫描的磁道的线性结构体。int c:磁道号总数  int f :开始扫描的磁道 
返回参数： 
无
功能： 
按照sstf的原则,按链表中的顺序,读取其中的数值,并且输出结果。
 根f最近的磁道先读取
***************************************************************************/
void sstf(Node *head,int c,int f)//最短寻道时间优先算法                
{
	Node *p,*q,*r,*s,*l,*m;
	l=(Node *)malloc(sizeof(Node));
	l->next=NULL;//开辟一个L名字的空间
	m=l;//赋给M,M,L指向同一个空间两个变量，建立另外的链表，用来排序
	q=head;//Q指向头节点                                  一.二组指针初始化
	p=head->next;//P下一个
	s=head;//S和Q都指向头
	r=head->next;//R和Pz指向下一个
	//两组四个指针，
	float num=0;//总的寻道长度
	//以下两重循的是寻找离出发点最近的磁道，并且在外的计算长度之和
	for(int i=0;i<c;i++)//循环C次就完成了
	{
		int min=abs(f-r->data);//可能是比F大，也可能比F是小，所以要求绝对值
		for(int j=0;j<c-i-1;j++)//还要循环C-I-1次就找到地I个元素了。
		{
			p=p->next;//第一组指针前移                               第二组指针
			q=q->next;//第一组指针前移
			if(abs(f-p->data)<min)//找到后面两个元素中哪个比较接近F
			{
    
				min=abs(f-p->data);//找到后赋给MIN
				r=p;//找到后离F第二个元素向前移动                   第一组指针
				s=q;//找到后离F第一个元素向后移动
			}
		}
		num+=abs(f-r->data);//求寻道总长度
		f=r->data;//开始所在磁道位置前移
		s->next=r->next;//开始磁道前移                            第一组指针
		r->next=NULL;//新链表的尾元素，指针域是空的
		m->next=r;//把R指为新链表的尾元素
		m=r;//用M指向新元素的表尾
		q=head;//从新开始扫描，以找到下一个元素
		p=head->next;//从新开始
		s=head;//从新开始
		r=head->next;//从新开始
	}
	//循环结束，两个表头，两条链表
	num=num/c;//平均寻找长度
	print(l);//输出新的链表
	printf("\n最短寻道时间优先顺序是");
	print(l);//输出新的链表
	printf("\n平均寻道长度%f",num);
}


/************************************************************************** 
scan(Node *head,int c,int f) 
输入参数： 
Node *head :要扫描的磁道的线性结构体。int c:磁道号总数  int f :开始扫描的磁道 
返回参数： 
无
功能： 
按照scan的原则,按链表中的顺序,读取其中的数值,并且输出结果。
每次循环完一次,重新读取链表 ,直到所有数据都读完.
***************************************************************************/
void scan(Node *head,int c,int f)//扫描算法           
{
	
	int min,max,i=0,j=0;
	float num=0;
	Node *p,*q,*r,*s,*m,*n,*x,*y; 
	r=(Node *)malloc(sizeof(Node));//存放比开始磁道小的磁道
	r->next=NULL;
	s=r;
	m=(Node *)malloc(sizeof(Node));//存放比开始磁道大的磁道
	m->next=NULL;
	n=m;
	x=(Node *)malloc(sizeof(Node));
	x->next=NULL;
	y=x;
	q=head;
	p=head->next;
	while(p->next!=NULL)
	{
		if(p->data-f>0)
		{
			q->next=p->next;
			p->next=NULL;
			n->next=p;
			n=p;
			p=q->next;
			i++;
		}
		else
		{
			q->next=p->next;
			p->next=NULL;
			s->next=p;
			s=p;
			p=q->next;
			j++;
		}

	}
	if(p->data>=f)
	{
		n->next=p;
		n=p;
		i++;
	}else
	{
		s->next=p;
		s=p;
		j++;
	}
	//print(r);
	//print(m);
	q=r;//对比开始磁道小的磁道排序
	p=r->next;
	while(q->next->next!=NULL)
	{
		q=q->next;
		p=q->next;
		max=q->data;
		while(p->next!=NULL)
		{
			if(p->data>max)
			{
				max=p->data;
                p->data=q->data;
                q->data=max;
                max=q->data;
			}
			p=p->next;
		}
		if(p->data>max)
		{
			max=p->data;
			p->data=q->data;
			q->data=max;
			max=q->data;
		}
	}
	//print(r);
	q=m;
	p=m->next;
	while(q->next->next!=NULL)
	{
		q=q->next;
		p=q->next;
		min=q->data;
		while(p->next!=NULL)
		{
			if(p->data<min)
			{
				min=p->data;
                p->data=q->data;
                q->data=min;
                min=q->data;
			}
			p=p->next;
		}
		if(p->data<min)
		{
			min=p->data;
			p->data=q->data;
			q->data=min;
			min=q->data;
		}
	}
	//print(m);
	x=m;
	p->next=r->next;
	y=x->next;
	while(y->next!=NULL)
	{
		num+=abs(f-y->data);
		f=y->data;
		y=y->next;
	}
	num+=abs(f-y->data);
	num=num/c;
	printf("\n扫描算法的顺序是");
	print(x);//输出新的链表
	printf("\n平均寻道长度%f",num);

}


/************************************************************************** 
cscan(Node *head,int c,int f) 
输入参数： 
Node *head :要扫描的磁道的线性结构体。int c:磁道号总数  int f :开始扫描的磁道 
返回参数： 
无
功能： 
按照cscan的原则,按照线性表中的顺序,读取其中的数值,并且输出结果。 
***************************************************************************/ 
void cscan(Node *head,int c,int f)//循环扫描算法    
{         



	printf("cscan:");


}


/************************************************************************** 
void nstepscan(Node *head,int c,int f) 
输入参数： 
Node *head :要扫描的磁道的线性结构体。int c:磁道号总数  int f :开始扫描的磁道 
返回参数： 
无
功能： 
按照nstepscan的原则,按照线性表中的顺序,读取其中的数值,并且输出结果。 
***************************************************************************/ 
void nstepscan(Node *head,int c,int f)//N步扫描算法             
{
	printf("nstepscan:");

}