burt

原创 作者：飞阳
转载请注明出处：http://hi.baidu.com/burtcn/blog
不足之处请指正，谢谢

#include <stdio.h>
#include <stdlib.h>
#define alloc(type) (type*)malloc(sizeof(type))

//进程结构体
struct process{    
        char name[10];
        int starttime;
        int runtime;
        struct process *next;
} *pHead;

//函数声明
void create();
void insert();
int getCount(int starttime);
void delProcess(process *prev);
process* SJF(int count);

void create(){    
        pHead=alloc(process);
        pHead->next=NULL;
        char num;    
        printf("请输入进程数目:");
        scanf("%d",&num);
        printf("下面输入进程信息\n输入格式:进程名 开始时间 运行时间\n");
        for(int i=0;i<num;i++){
            printf("%d:",i+1);
            insert();    
        }
}

void insert(){    
        //输入进程信息
        process *item=alloc(process);    
        scanf("%s %d %d",item->name,&(item->starttime),&(item->runtime));
        item->next=NULL;
        //插入到合适的位置，按输入时间排序
        process *p,*q;
        p=pHead;
        q=p->next;    
        while(q!=NULL&&q->starttime<=item->starttime){
            p=q;
            q=p->next;
        }
        item->next=q;
        p->next=item;    
}

int getCount(int starttime){
        //返回小于指定时间的进程数目    
        process *pos;
        pos=pHead->next;
        int count=0;
        while(pos!=NULL&&pos->starttime<=starttime){
            count++;
            pos=pos->next;
        }
        return count;
}

void delProcess(process *prev){
        //删除指定节点进程    
        if(prev==NULL||prev->next==NULL) return;
        process *p,*q;
        p=prev;
        q=prev->next;
        p->next=q->next;
        q->next=NULL;
        free(q);
}

process* SJF(int count){
        //返回指定时间之前，下次调用的进程
        process *minpos=NULL,*p=pHead,*q;
        int mintime=0;    
        q=p->next;
        for(int i=0;i<count;i++){
            if(i==0){
                mintime=q->runtime;
                minpos=p;
            }else{            
                if(mintime>q->runtime){
                    mintime=q->runtime;
                    minpos=p;
                }
            }
            p=q;
            q=p->next;
        }
        return minpos;
}

void run(){

        int time=0;
        int count=0;
        process *p,*q;

        while(true){
            if(pHead->next==NULL) break;        
            count=getCount(time);
            if(count==0) time++;
            else{                
                if(count==1)
                    p=pHead;
                else
                    p=SJF(count);
                q=p->next;            
                printf("进程名:%s\t",q->name);
                printf("开始时间:%d\t",time);
                printf("响应时间:%d\t",time-q->starttime);
                time+=q->runtime;
                printf("结束时间:%d\t",time);
                printf("周转时间:%d\n",time-q->starttime);
                delProcess(p);
            }
        }    

}

void main(){
        create();
        printf("\n开始运行...\n");
        run();
        printf("运行结束...\n");
}

调试结果：
请输入进程数目:5
下面输入进程信息
输入格式:进程名 开始时间 运行时间
1:A 0 4
2:B 1 4
3:C 2 3
4:D 3 2
5:E 4 1

开始运行...
进程名:A 开始时间:0 响应时间:0 结束时间:4 周转时间:4
进程名:E 开始时间:4 响应时间:0 结束时间:5 周转时间:1
进程名:D 开始时间:5 响应时间:2 结束时间:7 周转时间:4
进程名:C 开始时间:7 响应时间:5 结束时间:10 周转时间:8
进程名:B 开始时间:10 响应时间:9 结束时间:14 周转时间:13
运行结束...
Press any key to continue