数据结构:线性表(番外)

本文最后更新于 2024年6月7日 下午

静态链表:

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

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

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

多项式计算:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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

数据结构:线性表(番外)
https://siegelion.cn/2019/09/14/数据结构:线性表(番外)/
作者
siegelion
发布于
2019年9月14日
许可协议