2021 廣工 Anyview 資料結構第 3 章

/**********
【題目】試以順序表L的L.rcd[L.length+1]作為監視哨，
改寫教材3.2節中給出的升序直接插入排序算法。
順序表的類型RcdSqList定義如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]閑置
   int length;
} RcdSqList;
**********/
void InsertSort(RcdSqList &L)
{
    int i, j;
    for (i=1; i<L.length; i++) {
        if (L.rcd[i+1].key<L.rcd[i].key) {
            L.rcd[0] = L.rcd[i+1];
            j = i+1;                
            while (L.rcd[0].key<L.rcd[j-1].key) {
                L.rcd[j] = L.rcd[j-1];
                j--;
            }    
            L.rcd[j] = L.rcd[0];
        }    
    }   
}
           

/**********
【題目】如下所述，改寫教材1.3.2節例1-10的冒泡排序算法：
将算法中用以起控制作用的布爾變量change改為一個整型
變量，訓示每一趟排序中進行交換的最後一個記錄的位置，
并以它作為下一趟起泡排序循環終止的控制值。
順序表的類型RcdSqList定義如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]閑置
   int length;
} RcdSqList;
**********/
void BubbleSort(RcdSqList &L)
/* 元素比較和交換必須調用如下定義的比較函數和交換函數：*/
/* Status LT(RedType a, RedType b);   比較："<"        */
/* Status GT(RedType a, RedType b);   比較：">"        */
/* void Swap(RedType &a, RedType &b); 交換             */
{
    int change = 0, i, j, n = L.length;
    for (i = n; i > 1; i--) {
        if (change) {
            i = change;
            change = 0;
        }    
        for (j = 1; j < i; j++) {
            if (GT(L.rcd[j], L.rcd[j+1])) {
                Swap(L.rcd[j], L.rcd[j+1]);
                change = j;
            }   
        }
        if (change == 0) break;
    }
}
           

/**********
【題目】已知記錄序列L.rcd[1..L.length]中的關鍵
字各不相同，可按如下所述實作計數排序：另設數組
c[1..n]，對每個記錄a[i]， 統計序列中關鍵字比它
小的記錄個數存于c[i]，則c[i]=0的記錄必為關鍵字
最小的記錄，然後依c[i]值的大小對序列中記錄進行
重新排列。試編寫算法實作上述排序方法。
順序表的類型RcdSqList定義如下：
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]閑置
   int     length;
} RcdSqList;
**********/
void CountSort(RcdSqList &L)
/* 采用順序表存儲結構，在函數内自行定義計數數組c */
{ 
    int c['z'], index = 0, i = 1;
    for (i = 0; i < 'z'; i++) c[i] = 0;
    for (i = 1; i < L.length+1; i++) c[L.rcd[i].key]++;
    for (i = 1; i < 'z'; i++) {
        if (index == L.length) break;
        if (c[i] > 0) {
            L.rcd[++index].key = i;
            c[i]--;
            i--;
        }        
    } 
}