創建結點型別

我們用鏈表存盤一個多項式，那么該鏈表的每一個結點就代表多項式的某一項，所以我們的每一個結點必須包含三個資訊：多項式的系數、多項式的指數以及指向下一個結點的指標，

typedef int SLTDataType;//指數、系數型別

typedef struct SListNode
{
	SLTDataType coef;//系數
	SLTDataType expon;//指數
	struct SListNode* next;//用于存放下一個結點的地址
}SListNode;

列印多項式

傳入一個指向多項式鏈表的指標，遍歷該鏈表依次列印鏈表內容，（一次列印一個結點）

//列印多項式
void SListPrint(SListNode* head)
{
	SListNode* cur = head;
	if (cur)
	{
		printf("%dx^%d", cur->coef, cur->expon);//列印第一項
		cur = cur->next;
	}
	while (cur)
	{
		printf("%+dx^%d", cur->coef, cur->expon);
		cur = cur->next;
	}
	printf("\n");
}

注：需將第一項拿出來單獨列印，因為我們不希望第一項系數的正號被列印出來（若第一項系數為正），

尾插

將一個項尾插到一個多項式的后面，我們需要申請一個新結點，將要求的系數和指數賦值給這個新結點，并將新結點的指標域置空，然后尾插到目標多項式的后面，

//創建一個新結點，回傳新結點地址
SListNode* BuySLTNode(SLTDataType coef, SLTDataType expon)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));//向新結點申請空間
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->coef = coef;//系數賦值
	node->expon = expon;//指數賦值
	node->next = NULL;//將新結點的指標域置空
	return node;//回傳新結點地址
}
//尾插
void SListPushBack(SListNode** pHead, SLTDataType coef, SLTDataType expon)
{
	SListNode* newnode = BuySLTNode(coef, expon);//申請一個新結點
	if (*pHead == NULL)//判斷是否為空表
	{
		*pHead = newnode;//頭指標直接指向新結點
	}
	else
	{
		SListNode* tail = *pHead;//接收頭指標
		while (tail->next != NULL)//若某結點的指標域為NULL，說明它是最后一個結點
		{
			tail = tail->next;指標指向下一個結點
		}
		tail->next = newnode;//讓最后一個結點的指標域指向新結點
	}
}

注：若原多項式為空，即鏈表為空，直接讓原鏈表指標指向新申請的結點即可，

選擇排序

輸入的多項式可能并不是有序的，這時我們需要將多項式按指數降序排列（或按指數升序排列），以簡化后續多項式的相加操作，這里我們選用選擇排序演算法，

//選擇排序
SListNode* InsertSortList(SListNode* head)
{
	if (head == NULL || head->next == NULL)//若鏈表為慷訓鏈表只有一個結點，則不需排序
		return head;

	SListNode* sortHead = head;//記錄排序后鏈表的第一個結點
	SListNode* cur = head->next;//從待排鏈表的第二個結點開始排序
	sortHead->next = NULL;//默認鏈表的第一個結點有序，設定其指標域為空
	while (cur)
	{
		SListNode* next = cur->next;//記錄當前正在排序的結點的下一個結點
		SListNode* c = sortHead;//記錄當前遍歷到的有序鏈表的結點位置
		SListNode* p = NULL;//記錄c的前一個結點位置
		while (c)
		{
			if (cur->expon > c->expon)//待插入結點的指數大于當前遍歷到的有序鏈表的結點的指數
			{
				break;
			}
			else//待插入結點與有序鏈表中的下一個結點比較
			{
				p = c;
				c = c->next;
			}
		}
		if (p == NULL)//將待插入結點插入到有序鏈表的第一個位置
		{
			cur->next = sortHead;
			sortHead = cur;
		}
		else//將待插入結點插入到p和c之間
		{
			cur->next = c;
			p->next = cur;
		}
		cur = next;//插入下一個待插入結點
	}
	return sortHead;//回傳排列好的鏈表
}

多項式相加

從兩個待相加的多項式的表頭開始，比較兩個結點的指數大小，若相同，則將兩個結點的系數相加得到新的系數，申請一個新結點（結點的系數為新得到的系數，指數與這兩個結點的指數相同）尾插到新鏈表的后面即可，若兩個結點的指數不相同，則申請一個新結點（新結點的系數和指數與兩個結點中指數較大的結點相同）尾插到新鏈表后面即可，

//比較兩個結點的指數大小
int Compare(SLTDataType e1, SLTDataType e2)
{
	if (e1 > e2)
		return 1;
	else if (e1 < e2)
		return -1;
	else
		return 0;
}
//多項式相加
SListNode* PolyAdd(SListNode* P1, SListNode* P2)
{
	SListNode* front = NULL;//相加后的鏈表的頭指標
	while (P1&&P2)
	{
		switch (Compare(P1->expon, P2->expon))//比較指數
		{
		case 1:
			SListPushBack(&front, P1->coef, P1->expon);
			P1 = P1->next;
			break;
		case -1:
			SListPushBack(&front, P2->coef, P2->expon);
			P2 = P2->next;
			break;
		case 0:
			SLTDataType sum = P1->coef + P2->coef;
			if (sum)
				SListPushBack(&front, sum, P1->expon);
			P1 = P1->next;
			P2 = P2->next;
			break;
		}
	}
	while (P1)//將P1剩余項尾插到鏈表后面
	{
		SListPushBack(&front, P1->coef, P1->expon);
		P1 = P1->next;
	}
	while (P2)//將P2剩余項尾插到鏈表后面
	{
		SListPushBack(&front, P2->coef, P2->expon);
		P2 = P2->next;
	}
	return front;//回傳新鏈表
}

可以對照下圖進行邏輯分析：
在這里插入圖片描述
注：當兩個指數相同的結點的系數相加為0時，不必申請新結點插入新鏈表，

代碼總覽 + 結果展示

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;//指數、系數型別

typedef struct SListNode
{
	SLTDataType coef;//系數
	SLTDataType expon;//指數
	struct SListNode* next;//用于存放下一個結點的地址
}SListNode;

//列印多項式
void SListPrint(SListNode* head)
{
	SListNode* cur = head;
	if (cur)
	{
		printf("%dx^%d", cur->coef, cur->expon);//列印第一項
		cur = cur->next;
	}
	while (cur)
	{
		printf("%+dx^%d", cur->coef, cur->expon);
		cur = cur->next;
	}
	printf("\n");
}
//創建一個新結點，回傳新結點地址
SListNode* BuySLTNode(SLTDataType coef, SLTDataType expon)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));//向新結點申請空間
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->coef = coef;//系數賦值
	node->expon = expon;//指數賦值
	node->next = NULL;//將新結點的指標域置空
	return node;//回傳新結點地址
}
//尾插
void SListPushBack(SListNode** pHead, SLTDataType coef, SLTDataType expon)
{
	SListNode* newnode = BuySLTNode(coef, expon);//申請一個新結點
	if (*pHead == NULL)//判斷是否為空表
	{
		*pHead = newnode;//頭指標直接指向新結點
	}
	else
	{
		SListNode* tail = *pHead;//接收頭指標
		while (tail->next != NULL)//若某結點的指標域為NULL，說明它是最后一個結點
		{
			tail = tail->next;指標指向下一個結點
		}
		tail->next = newnode;//讓最后一個結點的指標域指向新結點
	}
}
//選擇排序
SListNode* InsertSortList(SListNode* head)
{
	if (head == NULL || head->next == NULL)//若鏈表為慷訓鏈表只有一個結點，則不需排序
		return head;

	SListNode* sortHead = head;//記錄排序后鏈表的第一個結點
	SListNode* cur = head->next;//從待排鏈表的第二個結點開始排序
	sortHead->next = NULL;//默認鏈表的第一個結點有序，設定其指標域為空
	while (cur)
	{
		SListNode* next = cur->next;//記錄當前正在排序的結點的下一個結點
		SListNode* c = sortHead;//記錄當前遍歷到的有序鏈表的結點位置
		SListNode* p = NULL;//記錄c的前一個結點位置
		while (c)
		{
			if (cur->expon > c->expon)//待插入結點的指數大于當前遍歷到的有序鏈表的結點的指數
			{
				break;
			}
			else//待插入結點與有序鏈表中的下一個結點比較
			{
				p = c;
				c = c->next;
			}
		}
		if (p == NULL)//將待插入結點插入到有序鏈表的第一個位置
		{
			cur->next = sortHead;
			sortHead = cur;
		}
		else//將待插入結點插入到p和c之間
		{
			cur->next = c;
			p->next = cur;
		}
		cur = next;//插入下一個待插入結點
	}
	return sortHead;//回傳排列好的鏈表
}
//比較兩個結點的指數大小
int Compare(SLTDataType e1, SLTDataType e2)
{
	if (e1 > e2)
		return 1;
	else if (e1 < e2)
		return -1;
	else
		return 0;
}
//多項式相加
SListNode* PolyAdd(SListNode* P1, SListNode* P2)
{
	SListNode* front = NULL;//相加后的鏈表的頭指標
	while (P1&&P2)
	{
		switch (Compare(P1->expon, P2->expon))//比較指數
		{
		case 1:
			SListPushBack(&front, P1->coef, P1->expon);
			P1 = P1->next;
			break;
		case -1:
			SListPushBack(&front, P2->coef, P2->expon);
			P2 = P2->next;
			break;
		case 0:
			SLTDataType sum = P1->coef + P2->coef;
			if (sum)
				SListPushBack(&front, sum, P1->expon);
			P1 = P1->next;
			P2 = P2->next;
			break;
		}
	}
	while (P1)//將P1剩余項尾插到鏈表后面
	{
		SListPushBack(&front, P1->coef, P1->expon);
		P1 = P1->next;
	}
	while (P2)//將P2剩余項尾插到鏈表后面
	{
		SListPushBack(&front, P2->coef, P2->expon);
		P2 = P2->next;
	}
	return front;//回傳新鏈表
}

int main()
{
	SListNode* P1 = NULL;//存放第一個運算式資料的鏈表
	SListNode* P2 = NULL;//存放第二個運算式資料的鏈表
	SLTDataType coef, expon;
	//1.輸入兩個多項式
	int count = 0;
	printf("請輸入第一個多項式的項數:>");
	scanf("%d", &count);
	printf("請輸入第一個多項式:>");
	int i = 0;
	for (i = 0; i < count; i++)
	{
		scanf("%dx^%d", &coef, &expon);
		SListPushBack(&P1, coef, expon);
	}
	printf("請輸入第二個多項式的項數:>");
	scanf("%d", &count);
	printf("請輸入第二個多項式:>");
	for (i = 0; i < count; i++)
	{
		scanf("%dx^%d", &coef, &expon);
		SListPushBack(&P2, coef, expon);
	}
	//2.分別將兩個多項式按指數降序排列
	SListNode* SortP1 = InsertSortList(P1);//按指數排序第一個多項式
	SListNode* SortP2 = InsertSortList(P2);//按指數排序第二個多項式
	printf("第一個多項式按指數降序排列為:>");
	SListPrint(SortP1);
	printf("第二個多項式按指數降序排列為:>");
	SListPrint(SortP2);
	//3.將兩個多項式相加
	SListNode* PolyAddHead = PolyAdd(SortP1, SortP2);//將兩個多項式相加
	printf("將兩個多項式相加之后的結果為:>");
	SListPrint(PolyAddHead);
	return 0;
}

在這里插入圖片描述
注意：多項式輸入時，每一項的輸入格式需相同，均為：系數x^指數，

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279850.html

標籤：其他

上一篇：資料結構秘籍之鏈表

下一篇：深度決議〔程式員之所以高薪的真實原因〕，加班、禿頂只是冰山一角而已......

多項式加法運算（鏈表實作）

文章目錄

創建結點型別

列印多項式

尾插

選擇排序

多項式相加

代碼總覽 + 結果展示