哈尔滨工业大学（威海）数据结构实验

#include <stdio.h> #include <stdlib.h> typedef struct PCB{ int num; int start;//基址 int lenth;//长度 struct PCB *next; }PCB; typedef struct Space{ int type;//0为空，1为被占 int start; int length; struct Space *prev; struct Space *next; }Space; PCB *head1 = NULL,*head2 = NULL,*head3 = NULL; int m,n;//定义开辟的空间，基址和长度 Space *head = NULL; int findArea(int length) { int min=10000;//最小剩余量 Space *p = head; Space *flag; do { if((p->length - length)<min&&(p->length - length)>=0&&p->type==0) { min = p->length - length; flag = p; } p = p->next; }while(p!=NULL); if(min<=2&&min>=0)//产生碎片 { flag->type = 1; } if(min>2)//分裂原来空间 { Space *s = (Space *)malloc(sizeof(Space));//更新后的空白区 s->length = min; s->start = flag->start+length; s->prev = flag; s->type = 0; s->next = flag->next; flag->length = length; flag->type = 1; flag->next = s; } return flag->start; } //创建进程 void creat() { int num; //int start;//基址 int lenth;//长度 PCB *q = head1; printf("请输入进程id和长度\n"); scanf("%d %d",&num,&lenth); PCB *p=(PCB *)malloc(sizeof(PCB)); p->num = num; p->start = findArea(lenth); p->lenth = lenth; p->next = NULL; if(head1 == NULL) { head1 = p; } else { while(q->next != NULL) { q = q->next; } q->next = p; } } void show() { int a; scanf("%d",&a); PCB *p1,*p2,*p3; if(a==1) { printf("就绪态："); p1 = head1; p2 = head2; p3 = head3; while(p1!=NULL) { printf("%d(%d,%d); ",p1->num,p1->start,p1->lenth); p1 = p1->next; } printf("\n"); printf("执行态："); while(p2!=NULL) { printf("%d(%d,%d); ",p2->num,p2->start,p2->lenth); p2 = p2->next; } printf("\n"); printf("阻塞态："); while(p3!=NULL) { printf("%d(%d,%d); ",p3->num,p3->start,p3->lenth); p3 = p3->next; } printf("\n"); } if(a==2) { Space *p = head; printf("空闲区有：\n"); while(p!=NULL) { if(p->type==0) { printf("(%d,%d)\n",p->start,p->length); } p = p->next; } } } void run() { if(head2!=NULL) { printf("正在有其他进程运行\n"); } else { PCB *q = head1; head1 = head1->next; q->next = NULL; head2 = q; } } void block() { PCB *q = head2;//取运行态 head2 = NULL; PCB *p=head3;//加入到阻塞态 if(head3 == NULL) { head3 = q; } else { while(p->next != NULL) { p = p->next; } p->next = q; } if(head1!=NULL)//如果就绪态不空 { run(); } } void success() { PCB *q = head2;//取运行态 Space *p = head; while(p!=NULL) { if(p->start==q->start)//查找运行态的空间 { break; } p = p->next; } //3块 if(p->prev!=NULL&&p->next!=NULL) { if(p->prev->type==1&&p->next->type==1)//1.上占下占 { p->type = 0; } if(p->prev->type==1&&p->next->type==0)//2.上占下空 { p->prev->next = p->next; p->next->start = p->start; p->next->length = p->length+p->next->length; p->next->prev = p->prev; free(p); } if(p->prev->type==0&&p->next->type==1)//3.上空下占 { p->prev->length = p->prev->length+p->length; p->prev->next = p->next; p->next->prev = p->prev; free(p); } if(p->prev->type==0&&p->next->type==0&&p->next->next!=NULL)//4.上空下空 下下存在 { p->prev->length = p->prev->length+p->length+p->next->length; p->prev->next = p->next->next; p->next->next->prev = p->prev; free(p); free(p->next); } if(p->prev->type==0&&p->next->type==0&&p->next->next==NULL)//5.上空下空 下下不存在 { p->prev->length = p->prev->length+p->length+p->next->length; p->prev->next = NULL; free(p); free(p->next); } } //2块 if(p->next==NULL&&p->prev!=NULL)//1.p为尾 { if(p->prev->type==1)//上占 { p->type = 0; } if(p->prev->type==0)//上空 { p->prev->length = p->prev->length+p->length; p->prev->next = NULL; } } if(p->prev==NULL&&p->next!=NULL)//2.p为头 { if(p->next->type==1)//下占 { p->type = 0; } if(p->next->type==0)//下空 { p->next->length = p->length+p->next->length; p->next->prev = NULL; p->next->start = p->start; head = p->next; free(p); } } head2 = NULL; if(head1!=NULL)//如果就绪态不空 { run(); } } void week() { PCB *q = head3;//取阻塞态 head3 = head3->next; PCB *p=head1;//加入到就绪态 if(head1 == NULL) { head1 = q; } else { while(p->next != NULL) { p = p->next; } p->next = q; } } void timeSlice() { PCB *q = head1; PCB *p = head2;//取运行态 head2 = NULL; if(head1 == NULL)//将运行态添加到就绪态 { head1 = p; } if(head1!=NULL) { while(q->next != NULL) { q = q->next; } q->next = p; } if(head1!=NULL)//如果就绪态不空 { run(); } } int main() { int flag = 1; char a; printf("请输入开辟的内存空间的基址和长度\n"); scanf("%d %d",&m,&n); head=(Space *)malloc(sizeof(Space)); head->start = m; head->length = n; head->prev = NULL; head->next = NULL; head->type = 0;//0为空，1 为占用 printf("1.创建:c+进程id+长度\n"); printf("2.终止:e 结束正在运行的进程\n"); printf("3.时间片到:t:将运行的进程装入就绪队列尾部,将下一个自动调度过来.\n"); printf("4.阻塞:b 将正在执行的程序阻塞,即插入阻塞队列尾部.\n"); printf("5.唤醒:w 将阻塞队列中的一个进程调度到就绪队列上,即阻塞队列头到就绪队列尾\n"); printf("6.查看:随时查看队列的情况:s 1/2（s 1:查看的是三个进程队列的情况，s 2:查看的是剩余内存的情况）\n\n"); while(flag == 1) { printf("请输入操作指令\n"); scanf(" %c",&a); switch(a) { case 'c': creat(); break; case 'r': run(); break; case 'b': block(); break; case 's': show(); break; case 'e'://运行完成 success(); break; case 'w': week(); break; case 't'://时间片倒 timeSlice(); break; case 'q':