題目
設(shè)計(jì)函數(shù)分別求兩個(gè)一元多項(xiàng)式的乘積與和。
輸入格式:
輸入分2行，每行分別先給出多項(xiàng)式非零項(xiàng)的個(gè)數(shù)，再以指數(shù)遞降方式輸入一個(gè)多項(xiàng)式非零項(xiàng)系數(shù)和指數(shù)（絕對(duì)值均為不超過1000的整數(shù)）。數(shù)字間以空格分隔。
輸出格式:
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項(xiàng)式以及和多項(xiàng)式非零項(xiàng)的系數(shù)和指數(shù)。數(shù)字間以空格分隔，但結(jié)尾不能有多余空格。零多項(xiàng)式應(yīng)輸出0 0。
輸入樣例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
輸出樣例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
題目不算難，但是我實(shí)力不夠，踩了不少坑，包括將得到的乘法多項(xiàng)式按照降序插入結(jié)果多項(xiàng)式時(shí)，一直因?yàn)榭罩羔樚幚淼貌缓枚鴮?dǎo)致失??；合并同類項(xiàng)忘記判斷合并后的系數(shù)是否為0。
甚至一開始算加法多項(xiàng)式時(shí)，我將list1和list2的節(jié)點(diǎn)直接插入到結(jié)果多項(xiàng)式中，破壞了鏈表的結(jié)構(gòu)，導(dǎo)致求乘法多項(xiàng)式一直得不到想要的數(shù)據(jù)。
刷提前理清思路真的很重要，以后再也不會(huì)一上來就直接寫代碼了。
1、加法多項(xiàng)式
題目給出的輸入已經(jīng)按照降冪順序排列好，相加時(shí)不需要考慮順序的問題，同時(shí)加法也不需要考慮同類項(xiàng)合并，但加法需要考慮系數(shù)互為相反數(shù)的項(xiàng)相加為0的情況。
運(yùn)算思路：
分別令p和q指向list1和list2（即兩個(gè)多項(xiàng)式）的第一項(xiàng)數(shù)據(jù)
當(dāng)p的指數(shù)大于q的指數(shù)，將節(jié)點(diǎn)p復(fù)制給新節(jié)點(diǎn)newNode，將newNode移動(dòng)到result的末尾，p往后移動(dòng)，q不動(dòng)
當(dāng)p的指數(shù)小于q的指數(shù)，將節(jié)點(diǎn)q復(fù)制給新節(jié)點(diǎn)newNode，將newNode移動(dòng)到result的末尾，q往后移動(dòng)，p不動(dòng)
當(dāng)p的指數(shù)等于q的指數(shù)，若p和q的系數(shù)相加不為0，則復(fù)制到結(jié)果多項(xiàng)式，為0則舍棄。之后p和q都要向后移動(dòng)
如果p或q還有剩余的節(jié)點(diǎn)，直接接到結(jié)果多項(xiàng)式的末尾
如果給出的輸入，所以項(xiàng)全部抵消了，或本身給出的輸入就是零多項(xiàng)式，此時(shí)結(jié)果多項(xiàng)式為空表，輸出0 0
2、乘法多項(xiàng)式
乘法不用考慮相乘系數(shù)為0的情況，但需要考慮順序和同類項(xiàng)合并的問題。
用二重循環(huán)得到多項(xiàng)式相乘的所有結(jié)果
將每個(gè)結(jié)果節(jié)點(diǎn)newNode插入到結(jié)果多項(xiàng)式中合適的位置（按照指數(shù)降序排列）文章來源：http://www.zghlxwxcb.cn/news/detail-728647.html
- 先找到正確的插入位置，從結(jié)果多項(xiàng)式開頭按順序查找，找到第一個(gè)小于等于自己系數(shù)的項(xiàng)
- 如果小于，直接插入
- 如果等于，則要合并同類項(xiàng)，要記得判斷合并后的系數(shù)是否為0，是則刪除這個(gè)項(xiàng)
動(dòng)圖來源文章來源地址http://www.zghlxwxcb.cn/news/detail-728647.html
代碼
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int coefficient; //系數(shù)
int exponent; //指數(shù)
struct Node *next;
} Node, *LinkList;
void initList(LinkList *head)
{
if ((*head = (LinkList)malloc(sizeof(Node))) == NULL)
exit(-1);
(*head)->next = NULL;
}
void creatList(LinkList head)
{
LinkList p, tail = head;
int count;
scanf("%d", &count);
while (count-- > 0)
{
p = (LinkList)malloc(sizeof(Node));
scanf("%d%d", &p->coefficient, &p->exponent);
tail->next = p;
tail = p;
}
tail->next = NULL;
}
void printList(LinkList head)
{
LinkList p = head->next;
while (p)
{
if (p == head->next)
printf("%d %d", p->coefficient, p->exponent);
else
printf(" %d %d", p->coefficient, p->exponent);
p = p->next;
}
}
void addition(LinkList list1, LinkList list2)
{
LinkList result, p = list1->next, q = list2->next, tail, newNode;
initList(&result);
tail = result;
while (p && q)
{
int coefficient1, coefficient2, exponent1, exponent2;
newNode = (LinkList)malloc(sizeof(Node));
// 當(dāng)p的指數(shù)大于q的指數(shù)，將節(jié)點(diǎn)p復(fù)制給newNode，將newNode移動(dòng)到result的末尾，p往后移動(dòng)，q不動(dòng)
if (p->exponent > q->exponent)
{
newNode->coefficient = p->coefficient;
newNode->exponent = p->exponent;
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
p = p->next;
}
else if (p->exponent < q->exponent)
{
// 當(dāng)p的指數(shù)小于q的指數(shù)，將節(jié)點(diǎn)q復(fù)制給newNode，將newNode移動(dòng)到result的末尾，q往后移動(dòng)，p不動(dòng)
newNode->coefficient = q->coefficient;
newNode->exponent = q->exponent;
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
q = q->next;
}
else
{
// 當(dāng)p和q的指數(shù)相等，直接將兩個(gè)的系數(shù)相加。如果相加后的系數(shù)為0，則將p，q直接移動(dòng)到下一位
if (p->coefficient + q->coefficient == 0)
{
p = p->next;
q = q->next;
free(newNode);
}
else
{
newNode->coefficient = p->coefficient + q->coefficient;
newNode->exponent = p->exponent;
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
p = p->next;
q = q->next;
}
}
}
// 如果p或q還有剩余節(jié)點(diǎn)，直接接到result的末尾
if (!p)
{
tail->next = q;
}
if (!q)
{
tail->next = p;
}
if (!result->next)
{
free(result);
printf("0 0");
}
else
{
printList(result);
}
}
void multiplication(LinkList list1, LinkList list2)
{
LinkList result, p = list1->next, q , tail, newNode;
initList(&result);
tail = result;
while (p)
{
q = list2->next;
while (q)
{
// 創(chuàng)建新建的newNode
newNode = (LinkList)malloc(sizeof(Node));
newNode->coefficient = p->coefficient * q->coefficient;
newNode->exponent = p->exponent + q->exponent;
newNode->next = NULL;
LinkList temp = result;
// 找到合適的插入位置
while (temp->next && newNode->exponent < temp->next->exponent)
{
temp = temp->next;
}
// 插入或者合并同類項(xiàng)
if (temp->next == NULL || newNode->exponent > temp->next->exponent)
{
newNode->next = temp->next;
temp->next = newNode;
}
else if (newNode->exponent == temp->next->exponent)
{
temp->next->coefficient += newNode->coefficient;
// 如果合并同類項(xiàng)后系數(shù)為0，得刪除這個(gè)節(jié)點(diǎn)
if(!temp->next->coefficient){
LinkList deleteNode=temp->next;
temp->next=deleteNode->next;
free(deleteNode);
}
free(newNode);
}
q = q->next;
}
p = p->next;
}
if (!result->next)
{
free(result);
printf("0 0");
}
else
{
printList(result);
}
}
int main()
{
LinkList list1, list2;
initList(&list1);
initList(&list2);
creatList(list1);
creatList(list2);
multiplication(list1, list2);
printf("\n");
addition(list1, list2);
return 0;
}
到了這里，關(guān)于PTA 習(xí)題3.6 一元多項(xiàng)式的乘法與加法運(yùn)算的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
