1. 多项式ADT
需求：多项式的数学运算
eg: P1(X) = 10X1000 + 5X14 + 1 ， P2(X) = 3X1990 - 2X1492 + 11X + 1
1.使用一个简单数组来存储这些系数。
- 数组的长度就等于最高的幂数
- 从index 0-> Max 依次存储幂数从高到低的各系数。
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.优化的方式是使用单链表来存储数据，多项式的每一项含在一个单元中，并且这些单元以次数递减的顺序排序。如图：
image.png
链表实现的类型声明
typedef struct Node* PtrToNode;
struct Node
{
int Coefficient;
int Exponent;
PtrToNode Next;
};
typedef PtrToNode Polynomail;
2. 基数排序
需求: 我们有N个整数，范围从1到M，将其进行排序。
基础方式: 桶式排序创建一个数组称之为Count，大小为M，并初始化为零。Count有M个单元，开始时他们都是空的。当Ai被读入时Count[Ai]增1。这个方法的缺点很明显，如果M足够大，数组就太大了。
优化方式: 基数排序是在上面的桶式排序的基础上优化出来的。也就是使用多趟桶式排序。具体算法就是通过最低（有效）位（对基数N所取的位）进行桶式排序，然后对次最低（有效）位进行。等等。
数列：64，8，216，512，27，729，0，1，343，125。为了使问题简化，此时操作按基是10进行，不过一般并不做这样的假设。（第一趟是根据个位来排列，第二趟是根据十位，第三趟是根据百位）
image.png
3. 多重表
需求: 一所有40000名学生和2500门课程的大学需要生成两种类型的报告。第一个报告高列出每个班的注册者，第二个报告列出每个学生注册的班级。
1. 常见的实现方法是使用二维数组。这样一个数组将有1亿项。平均大约一个学生注册三门课程，因此实际上有意义的数据只有120000项，大约占0.1%
2. 循环表。 节省了大量空间，但是要花费时间。这里我把表结构的截图发出来。C1，C2，C3，C4为课程，S1，S2，S3，S4为学生。所有的表都各有一个表头并且都是循环的。比如，为了列出C3班的所有学生，我们从C3开始通过向右行进而遍历其表。第一个单元属于学生S1。虽然不存在明显的信息，但是可以通过跟踪该生链表直达到该表表头而确定该生的信息。一旦找到该生信息，我们就转回到C3的表并找到可以确定属于S3的另一个单元，我们继续并发现S4和S5也在该班上。
image.png
