問題描述
給定兩個多項式，求解其和與差。多項式的項數為M，而最高冪次為N。（1<=M<=10，1<=N<=1000000）
輸入說明
輸入包含了兩個多項式，分為兩行給出（同行資料間以空格隔開）：
每一行為兩組資料：第一組為一個值，表示多項式的非零項數M；第二組為2*M個值，每相鄰兩個值表達一個多項式的非零系數項，分別為系數值、冪次值（其中各項按照冪次的降序排列）。但如果多項式沒有非零系數項，則僅用0（M的值）表示，后面沒有系數和冪次值出現。例如，第一行的資料為：4 1 10 2 5 3 4 4 0，那么表示多項式有4項，對應的多項式為：x^10+2x^5+3x^4+4. 又例如，第二行的資料為：4 1 8 -2 5 3 3 4 1，表示多項式有4項，對應的多項式為：x^8-2x^5+3x^3+4x。那么上述兩個多項式相加的輸出結果應為：6 1 10 1 8 3 4 3 3 4 1 4 0，對應的多項式為：x^10+x^8+3x^4+3x^3+4x+4.第一個多項式減去第二個多項式的輸出結果為：7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0，對應多項式：x^10-x^8+4x^5+3x^4-3x^3-4x+4.
輸出說明
輸出包含了兩個多項式，分為兩行給出（同行資料間以空格隔開）：
第一行是多項式相加的結果，第二行是多項式相減的結果。每一行為兩組資料：第一組為一個值，表示多項式的非零項數M；第二組為2*M個值，每相鄰兩個值表達一個多項式的非零系數項，分別為系數值、冪次值（其中各項按照冪次的降序排列）。但如果多項式沒有非零系數項，則僅用0（M的值）表示，后面沒有系數和冪次值出現。
輸入樣例
例1：
4 1 10 2 5 3 4 4 0
4 1 8 -2 5 3 3 4 1
輸出樣例
例1：
6 1 10 1 8 3 4 3 3 4 1 4 0
7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0
以下是我的代碼。我的想法是，用l3,l4分別存盤加減法的結果，加減法的演算法應該都差不多，只是改改符號而已。然而我發現，當我單獨運行加法或者減法，可以得到想要的結果。但是當我把另一部分加上去，結果卻和期望的相去甚遠。我檢查了一下，沒有發現加法減法里面有哪些會互相干擾的啊，這個問題困擾我兩天了， 望大佬賜教
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int xishu;//多項式系數
int zhishu;//多項式指數
Node* next;
}node,*LinkedList;
void show(LinkedList l)//列印鏈表的函式
{
while(l)
{
printf("%d %d ",l->xishu,l->zhishu);
l=l->next;
}
}
int main()
{
LinkedList l1,l2,l3,l4,head1,head2,head3,head4;//l1,l2用于接受輸入的鏈表，l3儲存加法結果，l4儲存減法結果
l1=head1=(LinkedList)malloc(sizeof(node));
l2=head2=(LinkedList)malloc(sizeof(node));
l3=head3=(LinkedList)malloc(sizeof(node));
l4=head4=(LinkedList)malloc(sizeof(node));
LinkedList temp=(LinkedList)malloc(sizeof(node));
printf("分配空間完成");
int M,cntplus,cntminus;//cntplus統計加法結果的項數
cntplus=cntminus=0;
scanf("%d",&M);
for(int i=1;i<=2*M;i++)
{
if(i%2)
{
l1->next=(LinkedList)malloc(sizeof(node));
l1=l1->next;
scanf("%d",&l1->xishu);
}//兩個兩個讀取，第一個讀給系數，第二個讀給指數
else
{
scanf("%d",&l1->zhishu);
}
}
l1->next=NULL;
scanf("%d",&M);
for(int i=1;i<=2*M;i++)
{
if(i%2)
{
l2->next=(LinkedList)malloc(sizeof(node));
l2=l2->next;
scanf("%d",&l2->xishu);
}
else
{
scanf("%d",&l2->zhishu);
}
}
l2->next=NULL;
l1=head1->next;l2=head2->next;
while(l1&&l2)//做加法
{
if(l1->zhishu>l2->zhishu)
{
l3->next=l1;//如果l1的指數大于l2的，那么把l1加入到結果鏈表l3中去 ，同時l1指標向后撥一個
l3=l3->next;
l1=l1->next;
}
else if(l1->zhishu<l2->zhishu)//如果l1的指數小于l2,那么把l2加入到l3 ，同時l2指標向后撥一個
{
l3->next=l2;
l3=l3->next;
l2=l2->next;
}
else if(l1->zhishu==l2->zhishu)//指數相等，可以合并
{
if(l1->xishu+l2->xishu==0)//如果合并項系數為0，那么不需要添加到l3，繼續向后
{
l1=l1->next;
l2=l2->next;
//cntplus--;
}
else//合并項系數不為零，創建節點temp，為temp賦值，將temp插入到l3中去 ，繼續向后
{
temp->xishu=l1->xishu+l2->xishu;
temp->zhishu=l1->zhishu;
l3->next=temp;
l3=l3->next;
//free(temp);
l1=l1->next;
l2=l2->next;
}
}
}
if(l1)//從while回圈中跳出來后，可能有一個鏈表還沒有遍歷完，又因為多項式是降序排列的，則只需要把那個鏈表剩下的部分添加到鏈表l3中去即可
{
while(l1)
{
l3->next=l1;
l3=l3->next;
l1=l1->next;
}
}
else if(l2)
{
while(l2)
{
l3->next=l2;
l3=l3->next;
l2=l2->next;
}
}
l3->next=NULL;
l3=head3->next;
while(l3)//把項數算出來
{
cntplus++;
l3=l3->next;
}
printf("%d ",cntplus);
l3=head3->next;
show(l3);
//下面和上述操作原理一樣，做減法
l1=head1->next;
l2=head2->next;
while(l1&&l2)//減法
{
if(l1->zhishu>l2->zhishu)
{
l4->next=l1;//如果l1的指數大于l2的，那么把l1加入到結果鏈表l4中去
l4=l4->next;
l1=l1->next;
}
else if(l1->zhishu<l2->zhishu)
{
l4->next=l2;
l4=l4->next;
l4->xishu=-l2->xishu;//和加法有點不同的是，如果是把l2直接插入l4，那么需要添加負號
l2=l2->next;
}
else if(l1->zhishu==l2->zhishu)
{
if(l1->xishu-l2->xishu==0)
{
l1=l1->next;
l2=l2->next;
}
else
{
//LinkedList temp=(LinkedList)malloc(sizeof(node));
temp->xishu=l1->xishu-l2->xishu;
temp->zhishu=l1->zhishu;
l4->next=temp;
l4=l4->next;
//free(temp);
l1=l1->next;
l2=l2->next;
}
}
}
if(l1)
{
while(l1)
{
l4->next=l1;
l4=l4->next;
l1=l1->next;
}
}
else if(l2)
{
while(l2)
{
l4->next=l2;
l4=l4->next;
l4->xishu=-l4->xishu;//同樣的，把l2加入到l3需要添加負號
l2=l2->next;
}
}
l4->next=NULL;
l4=head4->next;
while(l4)
{
cntminus++;
l4=l4->next;
}
l4=head4->next;
printf("\n%d ",cntminus);
show(l4);
free(l4);
return 0;
}
uj5u.com熱心網友回復：
僅供參考：//鏈表實作一元多項式的加法減法乘法
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
float coef; //系數
int expn; //指數
struct node *next;
}
PolyNode; //多項式節點 polynomial node
typedef PolyNode* Polynomial;
Polynomial createPolynomial() { //創建多項式
PolyNode *p, *q, *head = (PolyNode *)malloc(sizeof(PolyNode)); //頭節點
head->next = NULL;
float coef;
int expn;
printf("輸入該多項式每一項的系數和指數，每項一行，輸入0 0結束！\n");
while (scanf("%f %d", &coef, &expn) && coef) { // 默認，按指數遞減排列
if (head->next) {
p = head;
while (p->next && expn < p->next->expn)
p = p->next;
if (p->next) {
if (expn == p->next->expn) { //有相同指數的直接把系數加到原多項式
p->next->coef += coef;
if (p->next->coef > -0.000001 && p->next->coef < 0.000001) { //若是相加后系數為0，則舍棄該節點
q = p->next;
p->next = q->next;
free(q);
}
} else {
q = (PolyNode*)malloc(sizeof(PolyNode));
q->coef = coef;
q->expn = expn;
q->next = p->next;
p->next = q;
}
} else {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = coef;
p->expn = expn;
p->next = NULL;
}
} else {
head->next = (PolyNode*)malloc(sizeof(PolyNode));
head->next->coef = coef;
head->next->expn = expn;
head->next->next = NULL;
}
}
return head;
}
Polynomial multiply(Polynomial poly, float coef, int expn) { //多項式與指定單項式相乘，該單項式為 coefx^expn
PolyNode *p, *q, *Poly = (PolyNode*)malloc(sizeof(PolyNode));
p = Poly;
q = poly->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = (q->coef*coef);
p->expn = (q->expn + expn);
q = q->next;
}
p->next = NULL;
return Poly;
}
void add(Polynomial poly1, Polynomial poly2) { //把 poly2 加到 poly1 上
PolyNode *p, *q, *r;
r = poly1;
p = poly1->next; //指向第一個節點
q = poly2->next;
poly2->next = NULL;
while (p && q) {
if (p->expn > q->expn) {
r->next = p;
p = p->next;
r = r->next;
} else if (p->expn < q->expn) {
r->next = q;
q = q->next;
r = r->next;
} else {
PolyNode *t;
p->coef += q->coef;
if (!(p->coef > -0.000001 && p->coef < 0.000001)) //系數不為0
{
r->next = p;
r = r->next;
p = p->next;
} else {
t = p;
p = p->next;
free(t);
}
t = q;
q = q->next;
free(t);
}
}
if (p)
r->next = p;
if (q)
r->next = q;
}
Polynomial polySubtract(Polynomial poly1, Polynomial poly2) { //多項式減法 poly1-poly2形成一個新的多項式
//把poly2的系數取相反數，形成一個新的多項式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //構造頭節點
PolyNode *p, *q;
p = poly;
q = poly2->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = -(q->coef); //系數取反
p->expn = q->expn;
q = q->next;
}
p->next = NULL;
add(poly, poly1); //利用加法
return poly;
}
Polynomial polyAdd(Polynomial poly1, Polynomial poly2) { //多項式相加 poly1+poly2形成一個新的多項式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //和多項式的頭節點
poly->next = NULL;
PolyNode *p, *q, *r;
r = poly;
p = poly1->next;
q = poly2->next;
while (p&&q) {
if (p->expn > q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
} else if (p->expn < q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
} else {
float m = p->coef + q->coef;
if (!(m > -0.000001 && m < 0.000001)) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = m;
r->expn = p->expn;
}
q = q->next;
p = p->next;
}
}
while (p) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
}
while (q) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
}
r->next = NULL;
return poly;
}
Polynomial polyMultiply(Polynomial poly1, Polynomial poly2) { //多項式相乘
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //創建多項式和的頭節點
poly->next = NULL;
PolyNode *p;
p = poly2->next;
while (p) {
add(poly, multiply(poly1, p->coef, p->expn));
p = p->next;
}
return poly;
}
void printPoly(Polynomial poly) { //列印多項式
if (poly && poly->next) {
PolyNode *p = poly->next; //p指向第一個節點
while (p->next) {
printf("%gx^%d", p->coef, p->expn);
p = p->next;
if (p && (p->coef > 0))
printf("+");
}
if (p->expn == 0)
printf("%g", p->coef); //列印常數項
else
printf("%gx^%d", p->coef, p->expn);
printf("\n");
}
}
void freePoly(Polynomial poly) { //釋放記憶體
if (poly && poly->next) {
PolyNode *p, *q;
p = poly;
while (p) {
q = p->next;
free(p);
p = q;
}
}
poly = NULL;
}
int main() {
printf("用鏈表實作多項式的加減法\n");
Polynomial poly1, poly2, poly3;
printf("創建多項式一\n");
poly1 = createPolynomial();
printf("多項式一：\n");
printPoly(poly1);
printf("創建多項式二\n");
poly2 = createPolynomial();
printf("多項式二：\n");
printPoly(poly2);
printf("兩多項式相加，和為：\n");
poly3 = polyAdd(poly1, poly2);
printPoly(poly3);
freePoly(poly3);
printf("兩個多項式相乘，積為：\n");
poly3 = polyMultiply(poly1, poly2);
printPoly(poly3);
freePoly(poly3);
printf("兩多項式相減，差為：\n");
poly3 = polySubtract(poly1, poly2);
printPoly(poly3);
freePoly(poly1);
freePoly(poly2);
freePoly(poly3);
system("pause");
return 0;
}
uj5u.com熱心網友回復：
建議樓主把功能從main函式里獨立出去，比如加法，減法，合并分別做獨立的函式。樓主這樣寫在main函式里，會導致代碼的可讀性大大降低。先調整一下代碼吧，這樣也便于查找問題～
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int elem_type;
typedef struct poly_key {
elem_type ratio;
elem_type power;
}poly_obj, *poly_handle;
typedef struct poly_node {
poly_obj poly;
struct poly_node *next;
}polynomial_obj, *polynomial_handle;
typedef int (*pfunc)(poly_obj, poly_obj);
static polynomial_handle create_node(void)
{
polynomial_handle pnew;
pnew = (polynomial_handle)malloc(sizeof(polynomial_obj));
if (!pnew) {
fprintf(stderr, "malloc error!\n");
return NULL;
}
pnew->poly.ratio = 0;
pnew->poly.power = 0;
pnew->next = NULL;
return pnew;
}
/* Create a polynomial */
void create_polynomial_link(polynomial_handle *phead)
{
polynomial_handle p, q;
while (1) {
p = create_node();
printf("Please input two numbers(ratio and power): ");
scanf("%d%d", &p->poly.ratio, &p->poly.power);
if (p->poly.ratio == 0) /* if ratio is equal zero, then break from while.*/
break;
if (!(*phead)) {
*phead = p;
q = *phead;
continue;
}
q->next = p;
q = p;
}
free(p);
}
void show_polynomial_link(polynomial_handle phead)
{
polynomial_handle pcur;
pcur = phead;
while (pcur) {
printf("%dx^%d ", pcur->poly.ratio, pcur->poly.power);
pcur = pcur->next;
}
putchar(10);
}
int get_length_polynomial(polynomial_handle phead)
{
int cnt = 0;
polynomial_handle pcur = phead;
while (pcur) {
cnt++;
pcur = pcur->next;
}
return cnt;
}
/* flag: 0: compare by ratio, 1: compare by power*/
static int check_cond(polynomial_handle pnode, int val, int flag)
{
assert(pnode);
if (flag)
return (pnode->poly.power == val);
else
return (pnode->poly.ratio == val);
}
void delete_polynomail(polynomial_handle *phead, int val, int flag)
{
polynomial_handle pcur, prev;
pcur = prev = *phead;
while (pcur) {
if (check_cond(pcur, val, flag)) {
if (pcur == *phead) {
*phead = (*phead)->next;
free(pcur);
pcur = *phead;
continue;
}
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
} else {
prev = pcur;
pcur = pcur->next;
}
}
}
static int compare_as_ratio(poly_obj a, poly_obj b)
{
return (a.ratio - b.ratio);
}
static int compare_as_power(poly_obj a, poly_obj b)
{
return (a.power - b.power);
}
void bubble_asc_sort(polynomial_handle phead, pfunc cmp)
{
polynomial_handle p, q;
poly_obj tmp;
for (p = phead; p; p = p->next)
for (q = phead; q->next; q = q->next)
if (cmp(q->poly, q->next->poly) > 0) {
tmp = q->poly;
q->poly = q->next->poly;
q->next->poly = tmp;
}
}
/* insert node before phead */
void insert_polynomail_node(polynomial_handle *phead, poly_obj param)
{
polynomial_handle pnew;
pnew = create_node();
pnew->poly = param;
pnew->next = *phead;
*phead = pnew;
}
void destroy_polynomail_link(polynomial_handle phead)
{
polynomial_handle pcur, prev;
pcur = phead;
while (pcur) {
prev = pcur->next;
free(pcur);
pcur = prev;
}
}
int main(void)
{
int len, flag, val;
polynomial_handle phead = NULL;
poly_obj poly;
create_polynomial_link(&phead);
show_polynomial_link(phead);
printf("Add one term(ratio, power): ");
scanf("%d%d", &poly.ratio, &poly.power);
insert_polynomail_node(&phead, poly);
printf("After insert: \n");
show_polynomial_link(phead);
len = get_length_polynomial(phead);
printf("The term of polynomial is %d\n", len);
bubble_asc_sort(phead, compare_as_ratio);
printf("After sort as ratio: \n");
show_polynomial_link(phead);
bubble_asc_sort(phead, compare_as_power);
printf("After sort as power: \n");
show_polynomial_link(phead);
printf("Del terms, del ratio or power(0, 1): ");
scanf("%d", &flag);
printf("Please input a number: ");
scanf("%d", &val);
delete_polynomail(&phead, val, flag);
printf("After delete: \n");
show_polynomial_link(phead);
destroy_polynomail_link(phead);
return 0;
}
個人寫的多項式，供參考～
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/135691.html
標籤：C語言