数据结构-线性表的应用

前言

本篇文章介绍线性表的应用，分别使用顺序表和单链表实现有序表的合并，最后介绍如何使用单链表实现两个稀疏多项式的相加和相乘。

一、有序表的合并

已知线性表La和Lb的数据元素按值非递减有序排列，现要求将La和Lb合并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排序。
非递减指可以有相同的值出现在同一个线性表中
$La=(a,b,c)$
$Lb=(c,d,e,f)$
$La$和$Lb$合并后
$Lc=(a,b,c,c,d,e,f)$

1.1 顺序表实现

算法步骤

1. 创建一个空表Lc
2. 依次从La或Lb中摘取元素值较小的结点插入到Lc表后，直至其中一个表变为空为止
3. 继续将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
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

1.2 单链表实现

为了方便使用，选择带头结点的单链表

算法步骤

1. pa和pb指针分别指向La和Lb的首元结点
2. pc指向La的头结点，用La的头结点作为Lc的头结点
3. 依次从La或Lb中摘取元素值较小的结点插入到Lc表后，直至其中一个表变为空为止
4. 继续将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;
}
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

二、稀疏多项式的相加和相乘

假设有两个多项式
$f_1(x)=7+3x+9x^8+5x^{17}$
$f_2(x)=8x+22x^7-9x^8$
多项式的通项公式为
$P_n(x)=p_1{x}^{e_1}+p_2{x}^{e_2}+\cdots +p_m{x}^{e_m}$
利用线性表P表示，则
$线性表P=((p_1,e_1),(p_2,e_2),\cdots ,(p_m,e_m))$
则$f_1(x)和f_2(x)分别用线性表A和B表示$
$线性表A=((7,0),(3,1),(9,8),(5,17))$
$线性表B=((8,1),(22,7),(-9,8))$
假设使用顺序表实现多项式的相加

算法步骤

1. 创建一个新数组c
2. 分别从头遍历比较a和b的每一项
   指数相同，对应系数相加，若其和为零，则比较两个表的下一项，若其和不为零，则在c中增加一个新项
   指数不相同，则将指数比较小的项复制到c中
3. 一个多项式遍历完毕时，将另一个剩余项依次复制到c中

那么，数组c的大小如何确定？由于无法确定数组c的大小，所以这里不使用顺序表实现，而是用单链表实现。
定义多项式的结点及其结构

//定义多项式结点
struct PolyNode
{
	float coef; //系数
	int   expn; //指数
	struct PolyNode* next;
};
//定义多项式结点指针类型
typedef struct PolyNode* PPolyNode;
//定义多项式类型
typedef struct PolyNode* PolyLinkList;
1
2
3
4
5
6
7
8
9
10
11

2.1 稀疏多项式的相加

算法步骤：

1. 指针p1和p2初始化，分别指向Pa和Pb的首元结点
2. p3指向和多项式的当前结点，初值为Pa的头结点
3. 当指针p1和p2均为到达表尾时，则循环比较p1和p2所指结点的指数值
4. p1->expn 与 p2->expn分3种情况：
   当p1->expn == p2->expn是，则将两个结点中的系数相加
   若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点
   若和为零，则删除p1和p2所指结点
   当p1->expn < p2->expn时，则取p1所指结点插入到和多项式链表中
   当p1->expn > p2->expn时，则取p2所指结点插入到和多项式链表中
5. 将非空表的剩余结点插入到p3所指结点的后面
6. 释放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;
}
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
56
57
58

2.2 稀疏多项式的相乘

1. 指针p1和p2初始化，分别指向Pa和Pb的首元结点
2. 指针p3初始化，指向Pc的头结点,初化始时，Pc只是一个空表
3. 用Pa的第一项与Pb的每一项相乘，将每一项相乘结果插入到Pc中(有序)
4. 从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;
	}
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

总结

完整代码:https://gitee.com/PYSpring/data-structure/tree/master