1. 多項式ADT
需求：多項式的數(shù)學運算
eg: P1(X) = 10X1000 + 5X14 + 1 ， P2(X) = 3X1990 - 2X1492 + 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宿亡，將其進行排序常遂。
基礎方式: 桶式排序創(chuàng)建一個數(shù)組稱之為Count，大小為M挽荠，并初始化為零克胳。Count有M個單元，開始時他們都是空的圈匆。當Ai被讀入時Count[Ai]增1漠另。這個方法的缺點很明顯，如果M足夠大跃赚，數(shù)組就太大了酗钞。
優(yōu)化方式: 基數(shù)排序是在上面的桶式排序的基礎上優(yōu)化出來的。也就是使用多趟桶式排序来累。具體算法就是通過最低（有效）位（對基數(shù)N所取的位）進行桶式排序，然后對次最低（有效）位進行窘奏。等等嘹锁。
數(shù)列：64，8着裹，216领猾，512，27骇扇，729摔竿，0，1少孝，343继低，125。為了使問題簡化稍走，此時操作按基是10進行袁翁，不過一般并不做這樣的假設柴底。（第一趟是根據(jù)個位來排列，第二趟是根據(jù)十位粱胜，第三趟是根據(jù)百位）
image.png
3. 多重表
需求: 一所有40000名學生和2500門課程的大學需要生成兩種類型的報告柄驻。第一個報告高列出每個班的注冊者，第二個報告列出每個學生注冊的班級焙压。
1. 常見的實現(xiàn)方法是使用二維數(shù)組鸿脓。這樣一個數(shù)組將有1億項。平均大約一個學生注冊三門課程涯曲，因此實際上有意義的數(shù)據(jù)只有120000項野哭，大約占0.1%
2. 循環(huán)表。 節(jié)省了大量空間掀抹，但是要花費時間虐拓。這里我把表結構的截圖發(fā)出來。C1傲武，C2蓉驹，C3，C4為課程揪利，S1态兴，S2，S3疟位，S4為學生瞻润。所有的表都各有一個表頭并且都是循環(huán)的。比如甜刻，為了列出C3班的所有學生绍撞，我們從C3開始通過向右行進而遍歷其表。第一個單元屬于學生S1得院。雖然不存在明顯的信息傻铣，但是可以通過跟蹤該生鏈表直達到該表表頭而確定該生的信息。一旦找到該生信息祥绞，我們就轉回到C3的表并找到可以確定屬于S3的另一個單元非洲，我們繼續(xù)并發(fā)現(xiàn)S4和S5也在該班上。
image.png
