数据结构：线性表（番外）

静态链表：

有时可以借助一维数组来表示线性链表

//------线性表的静态单链表存储结构-------
#define MAXSIZE 1000
typedef struct
{
	ElemType data;
	int cur;
}component,Slinklist[MAXSIZE]

数组的一个分量表示一个结点，同时用游标（cur）代替指针指示结点在数组中的位置。在线性表的删除和插入操作时不需要移动元素，仅需要修改游标。

多项式计算：

简单的我们可以想到，用一维数组表示一个多项式，用数组的下标表示多项式中每一项的指数，用数组中每个位置上的值表示对应的系数。
但是这样存在一个问题：形如S(x) = 1 + 3x10000 – 2x20000这样的多项式，指数项的值非常大，但非零项却非常少，导致一维数组浪费的空间很大。

为此我们可以用单链表来实现。在单链表中每个结点有两个数据项（系数项和指数项）。

typedef struct {      // 项的表示
    float  coef;          // 系数
    int   expn;           // 指数
} term, ElemType;


//多项式相加
void AddPolyn (Polynomial  &Pa, Polynomial  &Pb)

{
	//多项式加法：Pa = Pa + Pb，利用两个多项式的结点构成“和多项式”。
	ha = GetHead (Pa);		//ha和hb分别指向Pa和Pb的头结点
	hb = GetHead (Pb);
	qa = NextPos (Pa, ha);		//qa和qb分别指向Pa和Pb中当前结点
	qb = NextPos (Pb, hb);
	while (qa && qb) 
	{		//qa和qb均非空
		a = GetCurElem (qa);	//a和b为两表中当前比较元素
		b = GetCurElem (qb);
		switch (*cmp(a, b))
		{
			case -1:		//多项式PA中当前结点的指数值小
				ha = qa;
				qa = NextPos (Pa, qa);
				break;
			case 0:		//两者的指数值相等
				sum = a.coef + b.coef;
				if (sum != 0.0)
				{  		//修改多项式PA中
                                                                                 //当前结点的系数值
					SetCurElem (qa, sum);
					ha = qa;
				}
				else
				{		//删除多项式PA中当前结点
					DelFirst (ha, qa);
					FreeNode (qa);
				}
				DelFirst (hb, qb);
				FreeNode (qb);
				qb = NextPos (Pb, hb);
				qa = NextPos (Pa, ha);
				break;
			case 1:		//多项式PB中当前结点的指数值小
				DelFirst (hb, qb);
				InsFirst (ha, qb);
				qb = NextPos (Pb, hb);
				ha = NextPos (Pa, ha);
				break;
		} //switch
	} //while
	if (!ListEmpty (pb)) Append (Pa, qb);	//链接Pb中剩余结点
	FreeNode (hb);		//释放Pb的头结点

} //AddPoly