尝试按降序排序结构数组

Question

作为我正在尝试做的事情的序言 - 我正在尝试制定最短作业优先（SJF），即 C 语言中的操作系统算法。

为了处理按突发时间排序，我正在推动所有准备好的进程放在一个堆栈中，然后按降序对该堆栈进行排序。例如，如果堆栈看起来像 3,5,1,2，顶部有“2”，我尝试将其排序为：5,3,2,1，顶部有“1”。因此，当我开始使用 pop 时，我将按照我需要的顺序获取元素。

但我要展示的代码的问题是，它将 1,1,5,3 排序为 5,1,1,3。最后一个进程“3”永远不会被排序。

排序代码：

void sortByBurst() {
    int size = top;
    struct fcfs temp;
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < (size - 1 - i); j++) {
            if (stack[j].burst < stack[j + 1].burst) {
                temp = stack[j];
                stack[j] = stack[j + 1];
                stack[j + 1] = temp;
            }
        }
    }
}

如果您想查看我在哪里处理其余逻辑，即决定要推送什么 - 这就是 for 循环：

for (i = 0; i < numOfProc; i++) {
        if (first_process == 1 && p[i].arrival <= current_time && p[i].completed == 0) {
            min_index = i;
        } else if (first_process == 0 && last_index != -1) {
            for (int k = 0; k < numOfProc; k++) {
                if (p[k].completed == 0 && p[k].arrival <= p[last_index].max_slot && p[k].inQ != 1) {
                    push(p[k]);

                    p[k].inQ = 1;
                    critical_case = 1;
                } else if (p[k].completed == 0 && p[k].arrival > finalp[last_index].max_slot && p[k].inQ != 1) {
                    min_index = k;
                }
            }

            if (critical_case == 1) {
                sortByBurst();
                struct fcfs compare = pop();
                for (int l = 0; l < numOfProc; l++) {
                    if (compare.pid == p[l].pid) {
                        min_index = l;
                        break;
                    }
                }
            }
            break;
        }

    }

我正在测试代码的输入是：

 1. Process 1 | 2 (Arrival) | 1 (Burst)
 2. Process 2 | 1 (Arrival) | 5 (Burst)
 3. Process 3 | 4 (Arrival) | 1 (Burst)
 4. Process 4 | 0 (Arrival) | 6 (Burst)
 5. Process 5 | 2 (Arrival) | 3 (Burst)

所需输出：

 1. Process 4 | 0 (Arrival) | 6 (Burst)
 2. Process 1 | 2 (Arrival) | 1 (Burst)
 3. Process 3 | 4 (Arrival) | 1 (Burst)
 4. Process 5 | 2 (Arrival) | 3 (Burst)
 5. Process 2 | 1 (Arrival) | 5 (Burst)

我得到的输出：

 1. Process 4 | 0 (Arrival) | 6 (Burst)
 2. Process 5 | 2 (Arrival) | 3 (Burst)
 3. Process 3 | 4 (Arrival) | 1 (Burst)
 4. Process 1 | 2 (Arrival) | 1 (Burst)
 5. Process 2 | 1 (Arrival) | 5 (Burst)

如您所见，进程 5 应该位于列表中的第四位。但因为在 Stack 中，即使排序后它仍然位于顶部，因此该算法无法正常工作。请看看我在这里做错了什么。

完整代码：

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

struct fcfs {
    int pid, arrival, burst, min_slot, max_slot, wait_time, completed, inQ;
};

struct fcfs stack[10];
int top = -1;

void push(struct fcfs process);

struct fcfs pop();

void sortByBurst();

void pline(int x);

void main() {

    int i, numOfProc, j;
    int counter = 0;
    int current_time = 0;
    int completed = 0;
    struct fcfs p[10], finalp[10];
    int first_process = 1;
    int prevMaxSlot = 0;
    int last_index = -1;
    int critical_case = 0;

    printf("Enter total number of Processes \n");
    scanf("%d", &numOfProc);

    for (i = 0; i < numOfProc; i++) {
        printf("Enter Arrival Time & Burst Time for Process %d: \n", i + 1);
        scanf("%d %d", &p[i].arrival, &p[i].burst);
        p[i].pid = i + 1;
        p[i].wait_time = 0;
        p[i].completed = 0;
        p[i].inQ = 0;
    }

    int prev = 0;

    while (completed != numOfProc) {

        int min_index = -1;
        for (i = 0; i < numOfProc; i++) {
            if (first_process == 1 && p[i].arrival <= current_time && p[i].completed == 0) {
                min_index = i;
            } else if (first_process == 0 && last_index != -1) {
                for (int k = 0; k < numOfProc; k++) {
                    if (p[k].completed == 0 && p[k].arrival <= p[last_index].max_slot && p[k].inQ != 1) {
                        push(p[k]);

                        p[k].inQ = 1;
                        critical_case = 1;
                    } else if (p[k].completed == 0 && p[k].arrival > finalp[last_index].max_slot && p[k].inQ != 1) {
                        min_index = k;
                    }
                }

                if (critical_case == 1) {
                    sortByBurst();
                    struct fcfs compare = pop();
                    for (int l = 0; l < numOfProc; l++) {
                        if (compare.pid == p[l].pid) {
                            min_index = l;
                            break;
                        }
                    }
                }
                break;
            }

        }

        if (min_index == -1) {
            current_time++;
        } else {
            if (p[min_index].arrival == prevMaxSlot) {
                p[min_index].min_slot = prevMaxSlot;
                p[min_index].max_slot = p[min_index].arrival + p[min_index].burst;
            } else if (p[min_index].arrival < prevMaxSlot || p[min_index].arrival == prevMaxSlot) {
                p[min_index].min_slot = prevMaxSlot;
                p[min_index].max_slot = p[min_index].min_slot + p[min_index].burst;
            } else if (p[min_index].arrival > prevMaxSlot) {
                p[min_index].min_slot = p[min_index].arrival;
                p[min_index].max_slot = p[min_index].arrival + p[min_index].burst;
            }
            p[min_index].wait_time = (first_process == 1) ? 0 : abs(p[i].min_slot - prev);
            p[min_index].completed = 1;
            prev = current_time;
            prevMaxSlot = p[min_index].max_slot;


            finalp[counter++] = p[min_index];
            first_process = 0;
            last_index = min_index;
            completed++;


        }

    }


    pline(44);
    printf("Slot\tPID\tArrival\t\tBurst\n");
    pline(44);


    for (i = 0; i < numOfProc; i++) {
        if ((finalp[i].min_slot - finalp[i - 1].max_slot) > 0 && i > 0) {
            printf("%d - %d\tNONE\tNONE\t\tNONE\n", finalp[i - 1].max_slot, finalp[i].min_slot);
        } else if ((abs(0 - finalp[i].min_slot) > 0 && i == 0)) {
            printf("0 - %d\tNONE\tNONE\t\tNONE\n", finalp[i].min_slot);
        }

        printf("%d - %d\t%d\t%d\t\t%d\n", finalp[i].min_slot, finalp[i].max_slot, finalp[i].pid, finalp[i].arrival,
               finalp[i].burst);
    }
    pline(44);

}


void pline(int x) {
    for (int i = 0; i < x; i++) {
        printf("-");
    }
    printf("\n");
}

void push(struct fcfs process) {
    if (top == 10)
        printf("\n Overflow");
    else {
        top = top + 1;
        stack[top] = process;
    }
}


struct fcfs pop() {
    struct fcfs process;
    if (top == -1)
        printf("Underflow");
    else {
        process = stack[top];
        top = top - 1;
    }

    return process;

}

void sortByBurst() {
    int size = top + 1;
    struct fcfs temp;
    for (int i = 1; i < size - 1; i++) {
        for (int j = 0; j < (size - 1 - i); j++) {
            if (stack[j].burst < stack[j + 1].burst) {
                temp = stack[j];
                stack[j] = stack[j + 1];
                stack[j + 1] = temp;
            }

        }
    }
}

Answer 1

问题是Top＆amp; i = 1;

在排序功能中，int size = top + 1，并用i = 0修复了for循环。

非常感谢所有贡献的人。