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

#define MAX_REQUESTS 1000

// 请求结构体
typedef struct {
    int track;      // 磁道号
    int visited;    // 是否已经被访问
} Request;

// 访问队列结构体
typedef struct {
    Request requests[MAX_REQUESTS]; // 请求数组
    int count;                      // 请求数量
} RequestQueue;

// 磁盘调度算法枚举
typedef enum {
    FCFS,
    SSTF,
    SCAN
} DiskScheduleAlgorithm;

// 计算两个磁道之间的距离
int calc_distance(int current_track, int target_track){
    return abs(current_track - target_track);
}

// 先来先服务算法
void fcfs(RequestQueue* queue, int initial_track){
    int current_track = initial_track;  // 当前磁道号
    int total_distance = 0;             // 总距离
    printf("FCFS调度算法\n");
    for (int i = 0; i < queue->count; i++){
        int distance = calc_distance(current_track, queue->requests[i].track);
        total_distance += distance;
        printf("磁道号：%d，距离：%d\n", queue->requests[i].track, distance);
        current_track = queue->requests[i].track;
    }

    double avg_distance = (double)total_distance / queue->count;
    printf("平均寻道长度：%f\n\n", avg_distance);
}

// 最短寻道时间优先算法
void sstf(RequestQueue* queue, int initial_track){
    int current_track = initial_track;  // 当前磁道号
    int total_distance = 0;             // 总距离
    printf("SSTF调度算法\n");
    for (int i = 0; i < queue->count; i++){
        int min_distance = INT_MAX;
        int min_index = -1;
        // 找到距离当前磁道号最近的请求
        for (int j = 0; j < queue->count; j++){
            if (!queue->requests[j].visited){
                int distance = calc_distance(current_track, queue->requests[j].track);
                if (distance < min_distance){
                    min_distance = distance;
                    min_index = j;
                }
            }
        }
        total_distance += min_distance;
        printf("磁道号：%d，距离：%d\n", queue->requests[min_index].track, min_distance);
        current_track = queue->requests[min_index].track;
        queue->requests[min_index].visited = 1;
    }
    double avg_distance = (double)total_distance / queue->count;
    printf("平均寻道长度：%f\n\n", avg_distance);
}

// 扫描算法
void scan(RequestQueue* queue, int initial_track){
    int current_track = initial_track;  // 当前磁道号
    int total_distance = 0;             // 总距离
    int direction = 1;                  // 扫描方向：1表示向外，-1表示向内
    printf("SCAN调度算法\n");
    // 将请求按磁道号排序
    for (int i = 0; i < queue->count - 1; i++){
        for (int j = i + 1; j < queue->count; j++){
            if (queue->requests[i].track > queue->requests[j].track){
                Request temp = queue->requests[i];
                queue->requests[i] = queue->requests[j];
                queue->requests[j] = temp;
            }
        }
    }

    // 扫描磁盘
    for (int i = 0; i < queue->count; i++){
        if (direction == 1){
            // 向外扫描
            if (queue->requests[i].track >= current_track){
                int distance = calc_distance(current_track, queue->requests[i].track);
                total_distance += distance;
                printf("磁道号：%d，距离：%d\n", queue->requests[i].track, distance);
                current_track = queue->requests[i].track;
            }
        }
        else{
            // 向内扫描
            if (queue->requests[i].track <= current_track){
                int distance = calc_distance(current_track, queue->requests[i].track);
                total_distance += distance;
                printf("磁道号：%d，距离：%d\n", queue->requests[i].track, distance);
                current_track = queue->requests[i].track;
            }
        }
    }
    double avg_distance = (double)total_distance / queue->count;
    printf("平均寻道长度：%f\n\n", avg_distance);
}

// 主函数
int main(){
    RequestQueue queue;             // 访问队列
    DiskScheduleAlgorithm algorithm; // 调度算法
    int initial_track;              // 初始磁道号
    printf("请输入访盘序列（以空格分隔，以-1结束）：\n");// 从键盘输入访盘序列
    queue.count = 0;
    while (1){
        int track;
        scanf("%d", &track);
        if (track == -1)
            break;
        queue.requests[queue.count].track = track;
        queue.requests[queue.count].visited = 0;
        queue.count++;
    }

    // 从键盘输入初始移动方向
    printf("请输入初始移动方向（1表示向外，-1表示向内）：\n");
    scanf("%d", &initial_track);

    // 选择调度算法
    printf("请选择调度算法（1.FCFS 2.SSTF 3.SCAN）：\n");
    scanf("%d", &algorithm);

    // 调用相应的调度算法
    switch (algorithm){
    case FCFS:
        fcfs(&queue, initial_track);
        break;
    case SSTF:
        sstf(&queue, initial_track);
        break;
    case SCAN:
        scan(&queue, initial_track);
        break;
    default:
        printf("无效的选择\n");
        break;
    }
    return 0;
}
