目录
- 前言
- 一、有序表的合并
- 1.1 顺序表实现
- 1.2 单链表实现
- 二、稀疏多项式的相加和相乘
- 2.1 稀疏多项式的相加
- 2.2 稀疏多项式的相乘
- 总结
前言
本篇文章介绍线性表的应用，分别使用顺序表和单链表实现有序表的合并，最后介绍如何使用单链表实现两个稀疏多项式的相加和相乘。
一、有序表的合并
已知线性表La和Lb的数据元素按值非递减有序排列，现要求将La和Lb合并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排序。
非递减指可以有相同的值出现在同一个线性表中
L
a
=
(
a
,
b
,
c
)
La=(a,b,c)
La=(a,b,c)
L
b
=
(
c
,
d
,
e
,
f
)
Lb=(c,d,e,f)
Lb=(c,d,e,f)
L
a
La
La和
L
b
Lb
Lb合并后
L
c
=
(
a
,
b
,
c
,
c
,
d
,
e
,
f
)
Lc=(a,b,c,c,d,e,f)
Lc=(a,b,c,c,d,e,f)
1.1 顺序表实现
算法步骤
- 创建一个空表Lc
- 依次从La或Lb中摘取元素值较小的结点插入到Lc表后，直至其中一个表变为空为止
- 继续将La或Lb其中一个表的剩余结点插图到Lc表的最后
代码实现如下
//定义返回值状态码
#define SUCCESS 1
#define ERROR 0
//这里假设元素的数据类型为char
typedef char ElemType;
//定义一个线性表
struct SeqList {
int MAXNUM; //线性表中最大元素的个数
int n; //线性表中实际的元素个数，n <= MAXNUM
ElemType* element; //存放线性表元素,element[0],element[1]...element[n-1]
};
//定义一个SeqList的指针类型
typedef struct SeqList* PSeqList;
//合并两个有序表
void mergeList_seq(PSeqList La, PSeqList Lb, PSeqList Lc)
{
ElemType* pa = La->element;
ElemType* pb = Lb->element; //指针pa和pb分别指向两个表的第一个元素
Lc->n = La->n + Lb->n;
Lc->MAXNUM = Lc->n;
Lc->element = (ElemType*)malloc(sizeof(Lc->n)); //为合并的新表分配一个数组空间
if (NULL == Lc->element)
{
printf("malloc fail!\n");
exit(ERROR);
}
ElemType* pc = Lc->element; //指针pc指向Lc表的第一个元素
ElemType* pa_last = La->element + (La->n - 1); //指针pa_last指向La表的最后一个元素
ElemType* pb_last = Lb->element + (Lb->n - 1); //指针pb_last指向Lb表的最后一个元素
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while (pa <= pa_last) *pc++ = *pa++; //Lb表到达表尾，将La表中剩余元素加入Lc
while (pb <= pb_last) *pc++ = *pb++; //La表到达表尾，将Lb表中剩余元素加入Lc
}
1.2 单链表实现
为了方便使用，选择带头结点的单链表
算法步骤
- pa和pb指针分别指向La和Lb的首元结点
- pc指向La的头结点，用La的头结点作为Lc的头结点
- 依次从La或Lb中摘取元素值较小的结点插入到Lc表后，直至其中一个表变为空为止
- 继续将La或Lb其中一个表的剩余结点插图到Lc表的最后
代码实现如下
//假设数据元素类型为char
typedef char ElemType;
//定义结点类型
struct Node;
typedef struct Node* PNode; //假设作为结点指针类型
struct Node {
ElemType data; //数据域
PNode next; //指针域
};
typedef struct Node* LinkList; //假设作为单链表类型
//合并两个有序表
//带头结点
void mergeList_link(LinkList* La, LinkList* Lb, LinkList* Lc)
{
PNode pa = (*La)->next;
PNode pb = (*Lb)->next;
PNode pc = *La;
*Lc = *La; //用La的头结点作为Lc的头结点
while (pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; //插入剩余元素
free(*Lb); //释放Lb的头结点
*Lb = NULL;
}
二、稀疏多项式的相加和相乘
假设有两个多项式
f
1
(
x
)
=
7
+
3
x
+
9
x
8
+
5
x
17
f_1(x)=7+3x+9x^8+5x^{17}
f1(x)=7+3x+9x8+5x17
f
2
(
x
)
=
8
x
+
22
x
7
−
9
x
8
f_2(x)=8x+22x^7-9x^8
f2(x)=8x+22x7−9x8
多项式的通项公式为
P
n
(
x
)
=
p
1
x
e
1
+
p
2
x
e
2
+
⋯
+
p
m
x
e
m
P_n(x)=p_1x^{e_1}+p_2x^{e_2}+\cdots+p_mx^{e_m}
Pn(x)=p1xe1+p2xe2+⋯+pmxem
利用线性表P表示，则
线性表
P
=
(
(
p
1
,
e
1
)
,
(
p
2
,
e
2
)
,
⋯
,
(
p
m
,
e
m
)
)
线性表P=((p_1,e_1),(p_2,e_2),\cdots,(p_m,e_m))
线性表P=((p1,e1),(p2,e2),⋯,(pm,em))
则
f
1
(
x
)
和
f
2
(
x
)
分别用线性表
A
和
B
表示
f_1(x)和f_2(x)分别用线性表A和B表示
f1(x)和f2(x)分别用线性表A和B表示
线性表
A
=
(
(
7
,
0
)
,
(
3
,
1
)
,
(
9
,
8
)
,
(
5
,
17
)
)
线性表A=((7,0),(3,1),(9,8),(5,17))
线性表A=((7,0),(3,1),(9,8),(5,17))
线性表
B
=
(
(
8
,
1
)
,
(
22
,
7
)
,
(
−
9
,
8
)
)
线性表B=((8,1),(22,7),(-9,8))
线性表B=((8,1),(22,7),(−9,8))
假设使用顺序表实现多项式的相加
算法步骤
- 创建一个新数组c
- 分别从头遍历比较a和b的每一项
指数相同，对应系数相加，若其和为零，则比较两个表的下一项，若其和不为零，则在c中增加一个新项
指数不相同，则将指数比较小的项复制到c中- 一个多项式遍历完毕时，将另一个剩余项依次复制到c中
那么，数组c的大小如何确定？由于无法确定数组c的大小，所以这里不使用顺序表实现，而是用单链表实现。
定义多项式的结点及其结构
//定义多项式结点
struct PolyNode
{
float coef; //系数
int expn; //指数
struct PolyNode* next;
};
//定义多项式结点指针类型
typedef struct PolyNode* PPolyNode;
//定义多项式类型
typedef struct PolyNode* PolyLinkList;
2.1 稀疏多项式的相加
算法步骤：
- 指针p1和p2初始化，分别指向Pa和Pb的首元结点
- p3指向和多项式的当前结点，初值为Pa的头结点
- 当指针p1和p2均为到达表尾时，则循环比较p1和p2所指结点的指数值
- p1->expn 与 p2->expn分3种情况：
当p1->expn == p2->expn是，则将两个结点中的系数相加
若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点
若和为零，则删除p1和p2所指结点
当p1->expn < p2->expn时，则取p1所指结点插入到和多项式链表中
当p1->expn > p2->expn时，则取p2所指结点插入到和多项式链表中- 将非空表的剩余结点插入到p3所指结点的后面
- 释放Pb的头结点
代码实现如下
void poly_add(PolyLinkList* Pa, PolyLinkList* Pb, PolyLinkList* Pc)
{
PPolyNode p1 = (*Pa)->next; //指向Pa链表的首元结点
PPolyNode p2 = (*Pb)->next; //指向Pb链表的首元结点
PPolyNode p3 = *Pa; //指向Pa的头结点，作为和多项式链表
*Pc = *Pa;
PPolyNode q = NULL; //指向要被删除的结点
while (p1 && p2)
{
if (p1->expn == p2->expn) //p1指数等于p2指数
{
float coef = p1->coef + p2->coef;
if (coef) //不为零
{
//修改p1所指结点的系数
p1->coef = coef;
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
else //为零
{
//删除p1所指结点
q = p1;
p1 = p1->next;
free(q);
q = NULL;
}
//删除p2所指结点
q = p2;
p2 = p2->next;
free(q);
q = NULL;
}
else if (p1->expn < p2->expn) //p1指数小于p2指数
{
//p1所指结点插入到和多项式链表
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
else //p1指数大于p2指数
{
//p2所指结点插入到和多项式链表
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
}
p3->next = p1 ? p1 : p2; //插入剩余数据元素
free(*Pb); //释放Pb头结点
*Pb = NULL;
}
2.2 稀疏多项式的相乘
- 指针p1和p2初始化，分别指向Pa和Pb的首元结点
- 指针p3初始化，指向Pc的头结点,初化始时，Pc只是一个空表
- 用Pa的第一项与Pb的每一项相乘，将每一项相乘结果插入到Pc中(有序)
- 从Pa的第二项开始与Pb的每一项相乘，将每一项结果插入到Pc中（插入后有序）
在Pc寻找插入位置
设coef = p1->coef * p2->coef ,expn = p1->expn + p2->expn,表示当前p1和p2所指项的相乘结果
若p3->next->expn < expn,则p3 = p3->next，直到p3->next->expn > expn，分两种情况
若存在p3->next->expn > expn, 则新建一个结点插入到p3所指结点后
若不存在p3->next->expn > expn,即p3->next == NULL时，则新建一个结点插入到p3所指结>点后
若p3->next->expn == expn,分两种情况
若p3->next->coef + coef结果为零，则删除p3->next所指结点
若p3->next->coef + coef结果不为零，则修改p3->next所指结点的系数
代码实现如下
//逐项插入法
void poly_mul(PolyLinkList* Pa, PolyLinkList* Pb, PolyLinkList* Pc)
{
PPolyNode p1 = (*Pa)->next;
PPolyNode p2 = (*Pb)->next; //p1,p2分别指向Pa和Pb的首元结点
PPolyNode p3 = *Pc; //p3分别指向Pc的头结点
PPolyNode temp = NULL; //作为一个临时的结点指针
if (p1)//将p1的第一项乘以Pb的每一项
{
while (p2)
{
PPolyNode newNode = (PPolyNode)malloc(sizeof(struct PolyNode));
if (NULL == newNode)
{
printf("malloc fail!\n");
exit(ERROR);
}
newNode->coef = p1->coef * p2->coef; //p1,p2所指结点的系数相乘
newNode->expn = p1->expn + p2->expn; //p1,p2所指结点的指数相加
newNode->next = NULL;
p3->next = newNode;
p3 = newNode;
p2 = p2->next;
}
}
//从Pa的第二项开始与Pb的每一项相乘，将每一项结果插入到Pc,直到p1到达Pa的表尾
p1 = p1->next;
while (p1)
{
p2 = (*Pb)->next;
p3 = *Pc;
while (p2)
{
//在Pc寻找插入位置
float coef = p1->coef * p2->coef;
int expn = p1->expn + p2->expn;
while (p3->next && p3->next->expn < expn)
p3 = p3->next;
if (p3->next && p3->next->expn == expn) //expn与p3->next->expn相同
{
if (p3->next->coef + coef) //和不为零
p3->next->coef += coef;
else //和为零
{
//删除p3->next所指结点
temp = p3->next;
p3->next = temp->next;
free(temp);
temp = NULL;
}
}
else //p3->next->expn > expn 或p3->next == NULL
{
//在p3->next前插入一个新结点
temp = (PPolyNode)malloc(sizeof(struct PolyNode));
if (NULL == temp)
{
printf("malloc fail!\n");
destoryPoly(Pc);
}
temp->coef = coef;
temp->expn = expn;
temp->next = p3->next;
p3->next = temp;
p3 = p3->next;
}
p2 = p2->next;
}
p1 = p1->next;
}
}
总结
完整代码:https://gitee.com/PYSpring/data-structure/tree/master
![Spring学习03-[Spring容器核心技术IOC学习进阶]](https://i-blog.csdnimg.cn/direct/10957890f11d4a2bbfd5161063c717e2.png)
