#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PROCESS 10  // 最大进程数

// 进程控制块 PCB
typedef struct PCB {
    char name[20];      // 进程名
    int priority;       // 优先数（数值越大优先级越高）
    int need_time;      // 需要运行时间
    int run_time;       // 已运行时间
    char state;         // 进程状态：'R'就绪, 'r'运行, 'F'完成
    struct PCB *next;   // 指向下一个进程的指针
} PCB;

PCB *ready = NULL;      // 就绪队列头指针
PCB *running = NULL;    // 当前运行进程

// 函数声明
void init_process();           // 初始化进程
void insert_ready(PCB *p);     // 按优先级插入就绪队列
PCB *get_highest_priority();   // 获取优先级最高的进程
void print_queue();            // 打印就绪队列
void schedule();               // 调度函数
void run_process();            // 运行进程
void destroy_process(PCB *p);  // 撤销进程

// 初始化进程信息（可手动输入或预置）
void init_process() {
    int n, i;
    PCB *p;
    printf("===== 进程调度模拟程序（最高优先数优先）=====\n\n");
    printf("请输入进程数量(最多%d个): ", MAX_PROCESS);
    scanf("%d", &n);
    
    if (n <= 0 || n > MAX_PROCESS) {
        printf("进程数量不合法！\n");
        return;
    }
    
    for (i = 0; i < n; i++) {
        p = (PCB *)malloc(sizeof(PCB));
        if (p == NULL) {
            printf("内存分配失败！\n");
            return;
        }
        
        printf("\n--- 输入第%d个进程信息 ---\n", i + 1);
        printf("进程名: ");
        scanf("%s", p->name);
        printf("优先数(数值越大优先级越高): ");
        scanf("%d", &p->priority);
        printf("需要运行时间: ");
        scanf("%d", &p->need_time);
        
        p->run_time = 0;
        p->state = 'R';  // 初始状态为就绪
        p->next = NULL;
        
        insert_ready(p);  // 插入就绪队列
    }
}

// 按优先级从高到低插入就绪队列（优先级相同则按先来先服务）
void insert_ready(PCB *p) {
    PCB *curr, *prev;
    
    if (ready == NULL) {
        // 队列为空
        ready = p;
        p->next = NULL;
        return;
    }
    
    // 找到插入位置（优先级降序）
    prev = NULL;
    curr = ready;
    while (curr != NULL && curr->priority >= p->priority) {
        prev = curr;
        curr = curr->next;
    }
    
    if (prev == NULL) {
        // 插入队首
        p->next = ready;
        ready = p;
    } else {
        // 插入中间或队尾
        p->next = curr;
        prev->next = p;
    }
}

// 取出就绪队列中优先级最高的进程
PCB *get_highest_priority() {
    PCB *p;
    if (ready == NULL) return NULL;
    
    p = ready;
    ready = ready->next;
    p->next = NULL;
    return p;
}

// 打印当前就绪队列状态
void print_queue() {
    PCB *p = ready;
    printf("\n【当前就绪队列状态】\n");
    if (p == NULL) {
        printf("  就绪队列为空\n");
        return;
    }
    
    printf("  队首 -> ");
    while (p != NULL) {
        printf("[%s|优先数:%d|需时:%d|已运行:%d|状态:%c] -> ", 
               p->name, p->priority, p->need_time, p->run_time, p->state);
        p = p->next;
    }
    printf("队尾\n");
}

// 打印当前运行进程
void print_running() {
    if (running != NULL) {
        printf("\n【当前运行进程】\n");
        printf("  [%s|优先数:%d|需时:%d|已运行:%d|状态:%c]\n", 
               running->name, running->priority, running->need_time, running->run_time, running->state);
    }
}

// 调度函数：选择优先级最高的进程投入运行
void schedule() {
    if (running != NULL) return;  // 已有运行进程
    
    running = get_highest_priority();
    if (running != NULL) {
        running->state = 'r';  // 置为运行态
    }
}

// 运行当前进程一个时间片
void run_process() {
    if (running == NULL) {
        printf("当前没有运行进程！\n");
        return;
    }
    
    printf("\n========================================\n");
    printf(">>> 正在运行进程: %s\n", running->name);
    printf(">>> 运行前: 优先数=%d, 已运行=%d, 需运行=%d\n", 
           running->priority, running->run_time, running->need_time);
    
    running->run_time++;      // 已运行时间加1
    running->priority--;      // 动态优先数：运行一次后优先级降低1
    
    printf(">>> 运行后: 优先数=%d, 已运行=%d\n", running->priority, running->run_time);
    
    // 检查进程是否完成
    if (running->run_time >= running->need_time) {
        running->state = 'F';  // 置为完成态
        printf(">>> 进程 %s 运行完毕！\n", running->name);
        destroy_process(running);
        running = NULL;
    } else {
        // 未完成，重新放回就绪队列
        running->state = 'R';
        printf(">>> 进程 %s 时间片用完，重新进入就绪队列\n", running->name);
        insert_ready(running);
        running = NULL;
    }
}

// 撤销进程（释放内存）
void destroy_process(PCB *p) {
    if (p != NULL) {
        printf(">>> 撤销进程 %s，释放资源\n", p->name);
        free(p);
    }
}

// 主函数
int main() {
    int choice;
    int step = 1;
    
    init_process();  // 初始化进程
    
    if (ready == NULL) {
        printf("没有创建任何进程，程序退出。\n");
        return 0;
    }
    
    printf("\n========================================");
    printf("\n进程初始化完成，开始调度...\n");
    print_queue();
    
    // 调度循环
    while (ready != NULL || running != NULL) {
        printf("\n========================================");
        printf("\n【第 %d 轮调度】\n", step++);
        
        schedule();          // 调度
        print_running();     // 显示运行进程
        run_process();       // 运行进程
        print_queue();       // 显示就绪队列
        
        printf("\n按回车键继续下一轮调度（输入0退出）...");
        choice = getchar();
        if (choice == '0') {
            printf("用户选择退出调度。\n");
            break;
        }
        // 清除缓冲区
        while (getchar() != '\n');
    }
    
    printf("\n========================================\n");
    printf("所有进程调度完成！\n");
    
    return 0;
}