1. 多項式ADT

需求：多項式的數(shù)學(xué)運算

eg: P₁(X) = 10X¹⁰⁰⁰ + 5X¹⁴ + 1 ， P₂(X) = 3X¹⁹⁹⁰ - 2X¹⁴⁹² + 11X + 1

1.使用一個簡單數(shù)組來存儲這些系數(shù)。

• 數(shù)組的長度就等于最高的冪數(shù)
• 從index 0-> Max 依次存儲冪數(shù)從高到低的各系數(shù)。

typedef struct 
{
    int CoeffArray[MaxDegree + 1];
    int HighPower;  
} * Polynomial;

void ZeroPolynomial(Polynomial Poly)
{
    int i;
    for( i = 0; i <= MaxDegree; i ++)
        Poly -> CoeffArray[i] = 0;
    Poly -> HighPower = 0;
}

//相加
void AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum) 
{
    int i;
    ZeroPolynomial(PolySum);
    PolySum -> HighPower = Max(Poly1 -> HighPower, Poly2 -> HighPower);
    for( i = PolySum -> HighPower; i >= 0; i--)
        PolySum -> CoeffArray[i] = Poly1 -> CoeffArray[i] + Poly2 -> CoeffArray[i];
}

//相乘
void MultPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd)
{
    int i,j;
    ZeroPolynomial(PolyProd);
    PolyProd -> HighPower = Poly1 -> HighPower + Poly2 -> HighPower;

    if (PolyProd -> HighPower > MaxDegree)
        Error("Exceeded array size");
    else 
        for(i = 0; i <= Poly1 -> HighPower; i++) 
            for(j = 0; j <= Poly2 -> HighPower; j++)
                PolyProd -> CoeffArray[i + j] += Poly1 -> CoeffArray[i] * Poly2 -> CoeffArray[j];
}

2.優(yōu)化的方式是使用單鏈表來存儲數(shù)據(jù)，多項式的每一項含在一個單元中，并且這些單元以次數(shù)遞減的順序排序。如圖：

image.png

鏈表實現(xiàn)的類型聲明

typedef struct Node* PtrToNode;

struct Node
{
    int Coefficient;
    int Exponent;
    PtrToNode Next;
};

typedef PtrToNode Polynomail;

2. 基數(shù)排序

需求: 我們有N個整數(shù)，范圍從1到M，將其進行排序。

基礎(chǔ)方式: 桶式排序創(chuàng)建一個數(shù)組稱之為Count，大小為M，并初始化為零。Count有M個單元，開始時他們都是空的。當A_i被讀入時Count[A_i]增1。這個方法的缺點很明顯，如果M足夠大，數(shù)組就太大了。

優(yōu)化方式: 基數(shù)排序是在上面的桶式排序的基礎(chǔ)上優(yōu)化出來的。也就是使用多趟桶式排序。具體算法就是通過最低（有效）位（對基數(shù)N所取的位）進行桶式排序，然后對次最低（有效）位進行。等等。

數(shù)列：64，8，216，512，27，729，0，1，343，125。為了使問題簡化，此時操作按基是10進行，不過一般并不做這樣的假設(shè)。（第一趟是根據(jù)個位來排列，第二趟是根據(jù)十位，第三趟是根據(jù)百位）

image.png

3. 多重表

需求: 一所有40000名學(xué)生和2500門課程的大學(xué)需要生成兩種類型的報告。第一個報告高列出每個班的注冊者，第二個報告列出每個學(xué)生注冊的班級。

1. 常見的實現(xiàn)方法是使用二維數(shù)組。這樣一個數(shù)組將有1億項。平均大約一個學(xué)生注冊三門課程，因此實際上有意義的數(shù)據(jù)只有120000項，大約占0.1%

2. 循環(huán)表。 節(jié)省了大量空間，但是要花費時間。這里我把表結(jié)構(gòu)的截圖發(fā)出來。C1，C2，C3，C4為課程，S1，S2，S3，S4為學(xué)生。所有的表都各有一個表頭并且都是循環(huán)的。比如，為了列出C3班的所有學(xué)生，我們從C3開始通過向右行進而遍歷其表。第一個單元屬于學(xué)生S1。雖然不存在明顯的信息，但是可以通過跟蹤該生鏈表直達到該表表頭而確定該生的信息。一旦找到該生信息，我們就轉(zhuǎn)回到C3的表并找到可以確定屬于S3的另一個單元，我們繼續(xù)并發(fā)現(xiàn)S4和S5也在該班上。

image.png