數據結構-線性表的應用

前言

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

一、有序表的合并

已知線性表La和Lb的數據元素按值非遞減有序排列，現要求將La和Lb合并為一個新的線性表Lc，且Lc中的數據元素仍按值非遞減有序排序。
非遞減指可以有相同的值出現在同一個線性表中
$L a = (a, b, c)$
$L b = (c, d, e, f)$
$L a$ 和 $L b$ 合并后
$L c = (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 <= 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 單鏈表實現

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

算法步驟

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+3x+9x^8+5x^{17}$
$f_2(x)=8x+22x^7-9x^8$
多項式的通項公式為
$P_n(x)=p_1x^{e_1}+p_2x^{e_2}+\cdots+p_mx^{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))$
假設使用順序表實現多項式的相加

算法步驟

創建一個新數組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;}
}