c语言单链表实现最高响应比优先调度算法

最高响应比优先调度算法是一种非抢占式调度算法，它的目的是让优先级高、等待时间长的进程先执行。在单链表中实现最高响应比优先调度算法，可以按照以下步骤进行：

1. 定义进程结构体，包括进程ID、优先级、需要运行的时间、已经运行的时间等信息。

typedef struct process {
    int pid; // 进程ID
    int priority; // 进程优先级
    int need_time; // 进程需要运行的时间
    int run_time; // 进程已经运行的时间
    struct process *next; // 指向下一个进程的指针
} Process;

2. 定义单链表结构体，包括头指针和尾指针。

typedef struct process_list {
    Process *head; // 链表头指针
    Process *tail; // 链表尾指针
} ProcessList;

3. 定义创建进程的函数，根据输入的进程信息创建一个新的进程。

Process *create_process(int pid, int priority, int need_time) {
    Process *p = (Process *)malloc(sizeof(Process));
    p->pid = pid;
    p->priority = priority;
    p->need_time = need_time;
    p->run_time = 0;
    p->next = NULL;
    return p;
}

4. 定义插入进程的函数，将新的进程插入到单链表中。

void insert_process(ProcessList *list, Process *p) {
    if (list->head == NULL) { // 如果链表为空
        list->head = p;
        list->tail = p;
    } else { // 如果链表不为空
        list->tail->next = p;
        list->tail = p;
    }
}

5. 定义计算响应比的函数，根据进程的优先级和等待时间计算响应比。

float calculate_response_ratio(Process *p, int current_time) {
    return 1.0 + (current_time - p->run_time) / p->need_time;
}

6. 定义选择下一个要执行的进程的函数，遍历单链表，找到响应比最高的进程。

Process *choose_next_process(ProcessList *list, int current_time) {
    Process *p = list->head;
    Process *chosen_process = NULL;
    float max_response_ratio = 0;
    while (p != NULL) {
        float response_ratio = calculate_response_ratio(p, current_time);
        if (response_ratio > max_response_ratio) {
            max_response_ratio = response_ratio;
            chosen_process = p;
        }
        p = p->next;
    }
    return chosen_process;
}

7. 定义执行进程的函数，将选择的进程执行一定时间，更新进程的运行时间。

void run_process(Process *p, int time) {
    p->run_time += time;
}

8. 在主函数中，创建多个进程，插入到单链表中，按照最高响应比优先调度算法执行进程。

int main() {
    ProcessList list = {NULL, NULL};
    int current_time = 0;
    insert_process(&list, create_process(1, 3, 5));
    insert_process(&list, create_process(2, 1, 3));
    insert_process(&list, create_process(3, 2, 4));
    while (list.head != NULL) {
        Process *p = choose_next_process(&list, current_time);
        int run_time = p->need_time - p->run_time;
        run_process(p, run_time);
        current_time += run_time;
        printf("Process %d runs for %d units of time.\n", p->pid, run_time);
        if (p->run_time == p->need_time) {
            printf("Process %d is finished.\n", p->pid);
            if (p == list.head) {
                list.head = p->next;
            }
            if (p == list.tail) {
                list.tail = NULL;
            }
            free(p);
        }
    }
    return 0;
}

以上就是在C语言中实现单链表最高响应比优先调度算法的基本步骤，你可以根据实际需求进行修改和完善。