前言

本篇文章介紹線性表的應(yīng)用，分別使用順序表和單鏈表實現(xiàn)有序表的合并，最后介紹如何使用單鏈表實現(xiàn)兩個稀疏多項式的相加和相乘。

一、有序表的合并

已知線性表La和Lb的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將La和Lb合并為一個新的線性表Lc，且Lc中的數(shù)據(jù)元素仍按值非遞減有序排序。
非遞減指可以有相同的值出現(xiàn)在同一個線性表中
$La=(a,b,c)$
$Lb=(c,d,e,f)$
$La$和$Lb$合并后
$Lc=(a,b,c,c,d,e,f)$

1.1 順序表實現(xiàn)

算法步驟

1. 創(chuàng)建一個空表Lc
2. 依次從La或Lb中摘取元素值較小的結(jié)點插入到Lc表后，直至其中一個表變?yōu)榭諡橹?/li>
3. 繼續(xù)將La或Lb其中一個表的剩余結(jié)點插圖到Lc表的最后

代碼實現(xiàn)如下

//定義返回值狀態(tài)碼
#define SUCCESS 1
#define ERROR   0//這里假設(shè)元素的數(shù)據(jù)類型為char
typedef char ElemType;//定義一個線性表
struct SeqList {int MAXNUM;			//線性表中最大元素的個數(shù)int n;				//線性表中實際的元素個數(shù)，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)); //為合并的新表分配一個數(shù)組空間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 單鏈表實現(xiàn)

為了方便使用，選擇帶頭結(jié)點的單鏈表

算法步驟

1. pa和pb指針分別指向La和Lb的首元結(jié)點
2. pc指向La的頭結(jié)點，用La的頭結(jié)點作為Lc的頭結(jié)點
3. 依次從La或Lb中摘取元素值較小的結(jié)點插入到Lc表后，直至其中一個表變?yōu)榭諡橹?/li>
4. 繼續(xù)將La或Lb其中一個表的剩余結(jié)點插圖到Lc表的最后

代碼實現(xiàn)如下

//假設(shè)數(shù)據(jù)元素類型為char
typedef char ElemType;//定義結(jié)點類型
struct Node;				  	
typedef struct Node* PNode;   //假設(shè)作為結(jié)點指針類型
struct Node {ElemType data;   //數(shù)據(jù)域PNode next;		//指針域
};typedef struct Node* LinkList;  //假設(shè)作為單鏈表類型//合并兩個有序表
//帶頭結(jié)點
void mergeList_link(LinkList* La, LinkList* Lb, LinkList* Lc)
{PNode pa = (*La)->next;PNode pb = (*Lb)->next;PNode pc = *La;*Lc = *La;      //用La的頭結(jié)點作為Lc的頭結(jié)點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的頭結(jié)點*Lb = NULL;
}

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

假設(shè)有兩個多項式
$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}+?+p_m{x}^{e_m}$
利用線性表P表示，則
$線性表P=((p_1,e_1),(p_2,e_2),?,(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))$
假設(shè)使用順序表實現(xiàn)多項式的相加

算法步驟

1. 創(chuàng)建一個新數(shù)組c
2. 分別從頭遍歷比較a和b的每一項
   指數(shù)相同，對應(yīng)系數(shù)相加，若其和為零，則比較兩個表的下一項，若其和不為零，則在c中增加一個新項
   指數(shù)不相同，則將指數(shù)比較小的項復(fù)制到c中
3. 一個多項式遍歷完畢時，將另一個剩余項依次復(fù)制到c中

那么，數(shù)組c的大小如何確定？由于無法確定數(shù)組c的大小，所以這里不使用順序表實現(xiàn)，而是用單鏈表實現(xiàn)。
定義多項式的結(jié)點及其結(jié)構(gòu)

//定義多項式結(jié)點
struct PolyNode
{float coef; //系數(shù)int   expn; //指數(shù)struct PolyNode* next;
};
//定義多項式結(jié)點指針類型
typedef struct PolyNode* PPolyNode;
//定義多項式類型
typedef struct PolyNode* PolyLinkList;

2.1 稀疏多項式的相加

算法步驟：

1. 指針p1和p2初始化，分別指向Pa和Pb的首元結(jié)點
2. p3指向和多項式的當前結(jié)點，初值為Pa的頭結(jié)點
3. 當指針p1和p2均為到達表尾時，則循環(huán)比較p1和p2所指結(jié)點的指數(shù)值
4. p1->expn 與 p2->expn分3種情況：
   當p1->expn == p2->expn是，則將兩個結(jié)點中的系數(shù)相加
   若和不為零，則修改p1所指結(jié)點的系數(shù)值，同時刪除p2所指結(jié)點
   若和為零，則刪除p1和p2所指結(jié)點
   當p1->expn < p2->expn時，則取p1所指結(jié)點插入到和多項式鏈表中
   當p1->expn > p2->expn時，則取p2所指結(jié)點插入到和多項式鏈表中
5. 將非空表的剩余結(jié)點插入到p3所指結(jié)點的后面
6. 釋放Pb的頭結(jié)點

代碼實現(xiàn)如下

void poly_add(PolyLinkList* Pa, PolyLinkList* Pb, PolyLinkList* Pc)
{PPolyNode p1 = (*Pa)->next;    //指向Pa鏈表的首元結(jié)點PPolyNode p2 = (*Pb)->next;    //指向Pb鏈表的首元結(jié)點PPolyNode p3 = *Pa;			  //指向Pa的頭結(jié)點，作為和多項式鏈表	*Pc = *Pa;PPolyNode q = NULL;		     //指向要被刪除的結(jié)點		while (p1 && p2){if (p1->expn == p2->expn)		//p1指數(shù)等于p2指數(shù){float coef = p1->coef + p2->coef;if (coef)		//不為零{//修改p1所指結(jié)點的系數(shù)p1->coef = coef;p3->next = p1;p3 = p1;p1 = p1->next;}else          //為零{//刪除p1所指結(jié)點q = p1;p1 = p1->next;free(q);q = NULL;}//刪除p2所指結(jié)點q = p2;p2 = p2->next;free(q);q = NULL;}  else if (p1->expn < p2->expn)		//p1指數(shù)小于p2指數(shù){//p1所指結(jié)點插入到和多項式鏈表p3->next = p1;p3 = p1;p1 = p1->next;}else                              //p1指數(shù)大于p2指數(shù){//p2所指結(jié)點插入到和多項式鏈表p3->next = p2;p3 = p2;p2 = p2->next;}}p3->next = p1 ? p1 : p2;	//插入剩余數(shù)據(jù)元素free(*Pb);		//釋放Pb頭結(jié)點*Pb = NULL;
}

2.2 稀疏多項式的相乘

1. 指針p1和p2初始化，分別指向Pa和Pb的首元結(jié)點
2. 指針p3初始化，指向Pc的頭結(jié)點,初化始時，Pc只是一個空表
3. 用Pa的第一項與Pb的每一項相乘，將每一項相乘結(jié)果插入到Pc中(有序)
4. 從Pa的第二項開始與Pb的每一項相乘，將每一項結(jié)果插入到Pc中（插入后有序）
   在Pc尋找插入位置
   設(shè)coef = p1->coef * p2->coef ,expn = p1->expn + p2->expn,表示當前p1和p2所指項的相乘結(jié)果
   若p3->next->expn < expn,則p3 = p3->next，直到p3->next->expn > expn，分兩種情況
   若存在p3->next->expn > expn, 則新建一個結(jié)點插入到p3所指結(jié)點后
   若不存在p3->next->expn > expn,即p3->next == NULL時，則新建一個結(jié)點插入到p3所指結(jié)>點后
   若p3->next->expn == expn,分兩種情況
   若p3->next->coef + coef結(jié)果為零，則刪除p3->next所指結(jié)點
   若p3->next->coef + coef結(jié)果不為零，則修改p3->next所指結(jié)點的系數(shù)

代碼實現(xiàn)如下

//逐項插入法
void poly_mul(PolyLinkList* Pa, PolyLinkList* Pb, PolyLinkList* Pc)
{PPolyNode p1 = (*Pa)->next;PPolyNode p2 = (*Pb)->next;   //p1,p2分別指向Pa和Pb的首元結(jié)點PPolyNode p3 = *Pc;			  //p3分別指向Pc的頭結(jié)點	PPolyNode temp = NULL;		  //作為一個臨時的結(jié)點指針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所指結(jié)點的系數(shù)相乘newNode->expn = p1->expn + p2->expn; //p1,p2所指結(jié)點的指數(shù)相加newNode->next = NULL;p3->next = newNode;p3 = newNode;p2 = p2->next;}}//從Pa的第二項開始與Pb的每一項相乘，將每一項結(jié)果插入到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所指結(jié)點temp = p3->next;p3->next = temp->next;free(temp);temp = NULL;}}else   //p3->next->expn > expn 或p3->next == NULL{//在p3->next前插入一個新結(jié)點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;}
}

總結(jié)

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