数据结构-线性表的应用

前言

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

一、有序表的合并

已知线性表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 <= MAXNUMElemType* 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表中剩余元素加入Lcwhile (pb <= pb_last) *pc++ = *pb++; //La表到达表尾，将Lb表中剩余元素加入Lc
}

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;
}

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

假设有两个多项式
$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;

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;
}

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;}
}

总结

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