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

#define MAX_PROCESS 10  // 最大进程数

// 进程状态枚举
typedef enum {
    READY,      // 就绪态
    RUNNING,    // 运行态
    FINISHED    // 完成态
} ProcessState;

// 进程控制块 PCB
typedef struct PCB {
    char name[20];          // 进程名
    int priority;           // 优先数（数值越大优先级越高）
    int needTime;           // 需要运行的时间
    int runTime;            // 已运行时间
    ProcessState state;     // 进程状态
    struct PCB *next;       // 指向下一个进程的指针
} PCB;

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

// 创建新进程
PCB* createProcess(char *name, int priority, int needTime) {
    PCB *p = (PCB*)malloc(sizeof(PCB));
    strcpy(p->name, name);
    p->priority = priority;
    p->needTime = needTime;
    p->runTime = 0;
    p->state = READY;
    p->next = NULL;
    return p;
}

// 按优先数降序插入就绪队列（优先数高的在前）
void insertByPriority(PCB *newProcess) {
    if (readyQueue == NULL) {
        readyQueue = newProcess;
        return;
    }
    
    // 如果新进程优先级比队首还高
    if (newProcess->priority > readyQueue->priority) {
        newProcess->next = readyQueue;
        readyQueue = newProcess;
        return;
    }
    
    // 找到合适位置插入
    PCB *current = readyQueue;
    while (current->next != NULL && current->next->priority >= newProcess->priority) {
        current = current->next;
    }
    newProcess->next = current->next;
    current->next = newProcess;
}

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

// 显示当前所有进程状态
void displayProcesses() {
    printf("\n========== 当前进程状态 ==========\n");
    
    // 显示运行态进程
    if (runningProcess != NULL) {
        printf("[运行态] 进程名: %s | 优先数: %d | 还需时间: %d | 已运行: %d\n",
               runningProcess->name, runningProcess->priority,
               runningProcess->needTime - runningProcess->runTime,
               runningProcess->runTime);
    }
    
    // 显示就绪队列
    printf("\n【就绪队列】\n");
    if (readyQueue == NULL) {
        printf("  (空)\n");
    } else {
        PCB *p = readyQueue;
        int count = 1;
        while (p != NULL) {
            printf("  [%d] 进程名: %s | 优先数: %d | 还需时间: %d | 状态: 就绪\n",
                   count++, p->name, p->priority,
                   p->needTime - p->runTime);
            p = p->next;
        }
    }
    printf("==================================\n");
}

// 调度算法（动态优先数：每运行一次优先数-1）
void schedule() {
    int time = 0;
    
    printf("\n********** 开始进程调度 **********\n");
    
    while (readyQueue != NULL || runningProcess != NULL) {
        printf("\n>>> 时间片 %d <<<\n", time++);
        
        // 如果当前没有运行进程，从就绪队列取一个
        if (runningProcess == NULL) {
            runningProcess = getHighestPriority();
            if (runningProcess != NULL) {
                runningProcess->state = RUNNING;
                printf("调度进程 [%s] 进入运行态\n", runningProcess->name);
            }
        }
        
        // 运行当前进程一个时间片
        if (runningProcess != NULL) {
            runningProcess->runTime++;
            printf("进程 [%s] 运行中... (已运行: %d/%d)\n", 
                   runningProcess->name, 
                   runningProcess->runTime, 
                   runningProcess->needTime);
            
            // 检查是否完成
            if (runningProcess->runTime >= runningProcess->needTime) {
                runningProcess->state = FINISHED;
                printf("✓ 进程 [%s] 运行完成！\n", runningProcess->name);
                free(runningProcess);
                runningProcess = NULL;
            } else {
                // 动态优先数调整：优先数减1
                runningProcess->priority--;
                printf("进程 [%s] 优先数降为 %d\n", 
                       runningProcess->name, runningProcess->priority);
                
                // 时间片用完，放回就绪队列
                runningProcess->state = READY;
                PCB *temp = runningProcess;
                runningProcess = NULL;
                insertByPriority(temp);
            }
        }
        
        displayProcesses();
    }
    
    printf("\n********** 所有进程调度完成 **********\n");
}

int main() {
    int n, i;
    char name[20];
    int priority, needTime;
    
    printf("===== 最高优先数优先调度算法 =====\n");
    printf("请输入进程数量: ");
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        printf("\n--- 输入第 %d 个进程信息 ---\n", i + 1);
        printf("进程名: ");
        scanf("%s", name);
        printf("优先数(数值越大优先级越高): ");
        scanf("%d", &priority);
        printf("需要运行时间: ");
        scanf("%d", &needTime);
        
        PCB *p = createProcess(name, priority, needTime);
        insertByPriority(p);
    }
    
    printf("\n初始就绪队列:");
    displayProcesses();
    
    // 开始调度
    schedule();
    
    return 0;
}