时间片轮转法 没有队列、节点
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> struct PCB //PCB数据结构 { int name; struct PCB* next; //链接指针 int arrival; //到达时间 int remaining; //剩余时间 char signal; //状态信号 int gantt[1000]; //记录甘特图横线位置 }InitList[100]; struct PCB* curr = NULL; //当前运行程序指针 struct PCB* first = NULL; //首址 struct PCB* last = NULL; //为了简便计算，加了尾址，减少计算负担 int Time = -1 ; //时间 int Traversal; //遍历用的变量 int num = 5; //进程数 int num2; //备用进程数 int Flow = 0; //流向图判断变量 init() { //初始化 printf("____________________初始化程序___________________________\n\n"); printf("是否输出循环图（需要递归，可能会消耗更多资源）:"); scanf("%d", &Flow); MeiKaiErDu: printf("自动生成数据（1）；手动生成数据（2）；使用测试数据（3）："); int flag; //判断指标 scanf("%d", &flag); switch (flag) { case 1: //自动生成数据 printf("请输入进程数："); scanf("%d", &num); //输入进程数 num2 = num; //初始化备用进程数 srand((unsigned)time(NULL)); for (int i = 0; i < num2; i++) { input(i, rand() % num2, (rand() % (num2 - 1) + 1)); } break; case 2: //手动输入数据 printf("请输入进程数："); scanf("%d", &num); //输入进程数 num2 = num; //初始化备用进程数 for (int i = 0; i < num2; i++) { printf("请输入进程%d的到达时间和服务时间（空格隔开）：", i + 1); int TempArr, TempRem; scanf("%d%d", &TempArr, &TempRem); input(i, TempArr, TempRem); } break; case 3: //使用测试数据 num2 = num = 5; input(0, 0, 3); input(1, 2, 6); input(2, 4, 4); input(3, 6, 5); input(4, 8, 2); break; default: //梅开二度 printf("请输入正确的选择！\n"); goto MeiKaiErDu; } } void BubbleSort() //冒泡排序算法对进程抵达时间先后排序 { int i, j, n = num2; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - 1 - i; j++) { if (InitList[j].arrival > InitList[j + 1].arrival) { InitList[n] = InitList[j + 1]; InitList[j + 1] = InitList[j]; InitList[j] = InitList[n]; } } } printf("排序\n"); for (int i = 0; i < num2; i++) { printf("进程名：%d\t到达时间：%d\t服务时间：%d\n", InitList[i].name, InitList[i].arrival, InitList[i].remaining); } } input(int i, int arr, int rem) { //输入数据 InitList[i].name = i + 1; InitList[i].arrival = arr; InitList[i].next = NULL; InitList[i].remaining = rem; InitList[i].signal = '0'; memset(InitList[i].gantt, 0, sizeof(InitList[i].gantt)); //将甘特图数据置0 printf("进程名：%d\t到达时间：%d\t服务时间：%d\n", InitList[i].name, InitList[i].arrival, InitList[i].remaining); } output(struct PCB* temp, int time) { printf(" 刚刚运行的进程名：%d\t到达时间：%d\t剩余服务时间：%d\n", temp->name, temp->arrival, temp->remaining); } struct PCB* check(int time) { //检查函数，检查当前时间有没有程序到达 while (Traversal < num2 - 1) { Traversal++; if (InitList[Traversal].arrival == time) return &InitList[Traversal]; } return NULL; } PrintGantt() { //甘特图输出函数 printf("\nGanttChat"); for (int i = 0; i < Time; i++) printf("__"); printf("\n\n"); for (int i = 0; i < num2; i++) { printf("%d:\t|", InitList[i].name); for (int k = 0; k < Time; k++) { if (InitList[i].gantt[k]) printf("%c%c", 0xa8, 0x80); else printf(" "); } printf("\n"); } } Print(struct PCB* quit, struct PCB* temp) { //流向图输出函数 printf("->%d(%d)", temp->name, temp->remaining); if (temp == quit) return; else Print(quit, temp->next); } struct PCB* Seek(struct PCB* NeedSeek, struct PCB* temp) { //递归函数，返回next为NeedSeek的PCB if (temp->next == NeedSeek) return temp; else Seek(NeedSeek, temp->next); } void Run() { //主程序 printf("\n_______________________RUN______________________________\n"); for (; Time < 1000; ) { Time++; printf("\n\n --------<<< 当前时间：%d >>>---------\n\n", Time); Traversal = -1; //每一个时间片开始，都要将Traveral重置为-1.然后Check函数++就会成为0 struct PCB* temp; //temp：用以保存要插入的进程的暂留地址 last = curr; //保留上一个curr以方便插入数据 if (curr == NULL) printf(" 刚刚无程序运行\n", Time); else { curr = curr->next; //当前指针下移 curr->remaining--; output(curr, Time); //运行（输出） curr->gantt[Time - 1] = 1; //记录，该进程这个时间的甘特图是为1的 } while ((temp = check(Time)) != NULL) { //新进程插入 if (curr == NULL) { curr = first = temp; temp->next = temp; last = temp; } else { if (last->signal == 'C') last = Seek(curr, curr); //当last指向的是一个已结束的进程时，调用Seek以正统递归的方式找到在队列里的next是curr的真正PCB last->next = temp; temp->next = curr; last = temp; } } if (curr != NULL) { if (curr->remaining == 0) { //进程完成判断 curr->signal = 'C'; if (curr->next == curr) { //当curr.next指向是它自己的时候，说明队列中只有它自己一个进程了 printf(" 进程%d退出！\n 队列空！\n", curr->name); curr = NULL; //推出该仅存的进程则队列为空 } else { if (last->signal == 'C') last = Seek(curr, curr); //当last指向的是一个已结束的进程时，调用Seek以正统递归的方式找到在队列里的next是curr的真正PCB last->next = curr->next; printf(" 进程%d退出！\n", curr->name); } num--; //未结束的进程减1 if (num == 0) { printf("\n*************************结束*******************************\n"); break; //当所有进程完成时，结束主程序的循环 } } } if (curr != NULL && Flow == 1) { printf(" 当前循环队列：%d(%d)", curr->next->name, curr->next->remaining); Print(curr->next, curr->next->next); printf("\n"); } } } int main() { int con = 0; do { Time = -1; init(); BubbleSort(); Run(); PrintGantt(); printf("\n输入0以退出，输入其他数字继续:"); scanf("%d", &con); printf("\n\n"); } while (con); }