操作系統任務調度問題。操作系統任務分為系統任務和用戶任務兩種。其中，系統任務的優先級 < 50，用戶任務的優先級 >= 50且 <= 255。優先級大於255的為非法任務，應予以剔除。現有一任務隊列task[]，長度為n，task中的元素值表示任務的優先級，數值越小，優先級越高。函數scheduler實現如下功能，將task[] 中的任務按照系統任務、用戶任務依次存放到 system_task[] 數組和 user_task[] 數組中（數組中元素的值是任務在task[] 數組中的下標），並且優先級高的任務排在前面，優先級相同的任務按照入隊順序排列（即先入隊的任務排在前面），數組元素為-1表示結束。
例如：task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99} system_task[] = {0, 3, 1, 7, -1} user_task[] = {4, 8, 2, 6, -1}
函數接口 void scheduler(int task[], int n, int system_task[], int user_task[])
此題有多種解法，一種是是在task數組中查找最小、次最小直到最小的數的下標，一次放入system_task和user_task數組。但此中解法控制點稍微多了些，一不小心，就在某個邏輯處出錯。還有一種解法是依次從task數組中取數，按照插入排序的方法插入到system_task和user_task數組，此解法非常明了，而且相當邏輯上也相當容易控制。最後一種解法就是把task數組的數放入拷貝到一個結構體數組裡，對這個結構體數組進行排序，然後從排好的結構體數組中依次取最小數的下標放入對應的system_task和user_task數組中。
下面是插入法的代碼：
view plaincopy to clipboardprint?void main()
{
int task[] = {0, 300, 400, 1, 80, 300, 170, 40, 99};
int n = sizeof(task)/sizeof(int);
int *system_task = new int [n + 1];
int *user_task = new int [n + 1];
scheduler(task, n, system_task, user_task);
taskprint( system_task, user_task, n + 1);
}
void scheduler(int task[], int n, int system_task[], int user_task[])
{
int syscount = 0;
int usercount = 0;
for(int i = 0; i < n; i++)
{
int current = task[i];
if(current >= 0 && current < 50)
{
system_task[syscount++] = i;
for(int j = syscount - 2; j >= 0 && syscount <= n + 1; j-- )
{
if(task[system_task[j]] > current)
{
system_task[j+1] = system_task[j];
}
else
break;
}
system_task[j+1] = i;
}
else if(current >= 50 && current <= 255)
{
user_task[usercount++] = i;
for(int j = usercount -2; j >= 0 && usercount <= n + 1; j--)
{
if(task[user_task[j]] > current)
{
user_task[j + 1] = user_task[j];
}
else
break;
}
user_task[j + 1] = i;
}
}
system_task[syscount] = -1;
user_task[usercount] = -1;
}
void taskprint(int system_task[], int user_task[], int n)
{
for(int i = 0; i < n; i++)
{
if(system_task[i] != -1)
cout << system_task[i] << endl;
else
break;
}
for(i = 0 ; i < n; i++)
{
if(user_task[i] != -1)
cout << user_task[i] << endl;
else
break;
}
}
作者“rein07的專欄”
