[已解决]一元多项式相加问题（C语言实现数据结构）

lemon3 · 发表于 2018-12-18 12:51:49

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

遇到了一元多项式的题目，要求用链表实现，给定代码如下，现在我不知道怎么写multiplication这部分，请大佬指点！！！
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{ int coef, exp;
struct node  *next;
} NODE;

void multiplication( NODE *, NODE * , NODE * );
void input( NODE * );
void output( NODE * );

/*void multiplication(NODE *, NODE *, NODE * )
{

}*/

void input( NODE * head )
{ int flag, sign, sum, x;
char c;

NODE * p = head;

while ( (c=getchar()) !='\n' )
{
      if ( c == '<' )
      { sum = 0;
         sign = 1;
         flag = 1;
      }
      else if ( c =='-' )
         sign = -1;
      else if( c >='0'&& c <='9' )
      { sum = sum*10 + c - '0';
      }
      else if ( c == ',' )
      { if ( flag == 1 )
         { x = sign * sum;
            sum = 0;
            flag = 2;
            sign = 1;
         }
      }
      else if ( c == '>' )
      { p->next = ( NODE * ) malloc( sizeof(NODE) );
         p->next->coef = x;
         p->next->exp  = sign * sum;
         p = p->next;
         p->next = NULL;
         flag = 0;
      }
}
}

void output( NODE * head )
{
while ( head->next != NULL )
{ head = head->next;
      printf("<%d,%d>,", head->coef, head->exp );
}
printf("\n");
}

int main()
{ NODE * head1, * head2, * head3;

head1 = ( NODE * ) malloc( sizeof(NODE) );
input( head1 );

head2 = ( NODE * ) malloc( sizeof(NODE) );
input( head2 );

head3 = ( NODE * ) malloc( sizeof(NODE) );
head3->next = NULL;
multiplication( head1, head2, head3 );

output( head3 );

return 0;
}

最佳答案

月排行榜 / 总排行榜

Croper

2018-12-22 10:24:02

本帖最后由 Croper 于 2018-12-22 10:30 编辑

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int coef, exp;
struct node *next;
} NODE;
NODE * multiplication(NODE *, NODE *);
void input(NODE *);
void output(NODE *);
NODE* Link(NODE* p,int i) //输入头节点，返回第i个节点,i从0算起
{
for (int j = 0; j <= i; j++)
{
p = p->next;
if (p == NULL) return NULL;
}
return p;
}
int Length(NODE* p) //输入头节点，返回长度，
{
int j=0;
while (p->next != NULL)
{
j++;
p = p->next;
}
return j;
}
void Append(NODE*& p, int coef0, int exp0) //为一个节点添加后继并重新将指针指向后继,
{
p->next = (NODE*)malloc(sizeof(NODE));
p = p->next;
p->coef = coef0;
p->exp = exp0;
p->next=NULL;
}
void DeleteLinklist(NODE* head) //删除链表
{
NODE *pPre;
while (head != NULL)
{
pPre = head;
head = head->next;
delete pPre;
}
}
NODE * multiplication(NODE *p1, NODE *p2) //乘法运算
{
NODE* ans,*p3;
NODE* Temp1,* Temp2;
p3 = new NODE; //新建链表p3
ans = p3; //ans指向p3的头节点，用于返回
int len = Length(p1) + Length(p2)-1; //p3的最高次项=两链表最高次项相加
for (int i = 0; i < len; i++) //依次填充p3的每一项
{
Append(p3, 0, i);
for (int j = 0; j <= i; j++)
{
Temp1 = Link(p1,j);
Temp2 = Link(p2, i - j);
if ((Temp1!=NULL)&&(Temp2!=NULL)) p3->coef += (Temp1->coef*Temp2->coef);
}
}
return ans;
}
void input(NODE * p) //输入头节点，读取并储存于链表中
{
int a, b;
int i = 0;
rewind(stdin);
while(scanf_s("<%d,%d>,", &a, &b)) //读取一项，并将值暂时储存于a和b中
{
for (i; i < b; i++) Append(p, 0, i); //延长链表，直到指数=b
Append(p, a, b); //赋值
i++;
}
}
void output(NODE * head)
{
bool b = false; //储存是否已产生有效输出
while (head->next != NULL)
{
head = head->next;
if (head->coef != 0)
{
b = true; //如果任意一项系数不为0，即产生了有效输出
printf("<%d,%d>,", head->coef, head->exp);
}
}
if (!b) printf("<0,0>,"); //如果没有产生有效输出，说明这是个0多项式，输出<0,0>
printf("\n");
}
int main()
{
int i;
NODE * head1, *head2, *head3;
head1 = (NODE *)malloc(sizeof(NODE));
input(head1);
head2 = (NODE *)malloc(sizeof(NODE));
input(head2);
head3 = multiplication(head1, head2);
output(head3);
DeleteLinklist(head1);
DeleteLinklist(head2);
DeleteLinklist(head3);
return 0;
}

复制代码

跳转到最佳答案楼层

Croper · 发表于 2018-12-22 10:24:02

这个最佳答案由 Croper 给出，感谢 Croper 的回答。

单击隐藏图章

本帖最后由 Croper 于 2018-12-22 10:30 编辑

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int coef, exp;
struct node *next;
} NODE;
NODE * multiplication(NODE *, NODE *);
void input(NODE *);
void output(NODE *);
NODE* Link(NODE* p,int i) //输入头节点，返回第i个节点,i从0算起
{
for (int j = 0; j <= i; j++)
{
p = p->next;
if (p == NULL) return NULL;
}
return p;
}
int Length(NODE* p) //输入头节点，返回长度，
{
int j=0;
while (p->next != NULL)
{
j++;
p = p->next;
}
return j;
}
void Append(NODE*& p, int coef0, int exp0) //为一个节点添加后继并重新将指针指向后继,
{
p->next = (NODE*)malloc(sizeof(NODE));
p = p->next;
p->coef = coef0;
p->exp = exp0;
p->next=NULL;
}
void DeleteLinklist(NODE* head) //删除链表
{
NODE *pPre;
while (head != NULL)
{
pPre = head;
head = head->next;
delete pPre;
}
}
NODE * multiplication(NODE *p1, NODE *p2) //乘法运算
{
NODE* ans,*p3;
NODE* Temp1,* Temp2;
p3 = new NODE; //新建链表p3
ans = p3; //ans指向p3的头节点，用于返回
int len = Length(p1) + Length(p2)-1; //p3的最高次项=两链表最高次项相加
for (int i = 0; i < len; i++) //依次填充p3的每一项
{
Append(p3, 0, i);
for (int j = 0; j <= i; j++)
{
Temp1 = Link(p1,j);
Temp2 = Link(p2, i - j);
if ((Temp1!=NULL)&&(Temp2!=NULL)) p3->coef += (Temp1->coef*Temp2->coef);
}
}
return ans;
}
void input(NODE * p) //输入头节点，读取并储存于链表中
{
int a, b;
int i = 0;
rewind(stdin);
while(scanf_s("<%d,%d>,", &a, &b)) //读取一项，并将值暂时储存于a和b中
{
for (i; i < b; i++) Append(p, 0, i); //延长链表，直到指数=b
Append(p, a, b); //赋值
i++;
}
}
void output(NODE * head)
{
bool b = false; //储存是否已产生有效输出
while (head->next != NULL)
{
head = head->next;
if (head->coef != 0)
{
b = true; //如果任意一项系数不为0，即产生了有效输出
printf("<%d,%d>,", head->coef, head->exp);
}
}
if (!b) printf("<0,0>,"); //如果没有产生有效输出，说明这是个0多项式，输出<0,0>
printf("\n");
}
int main()
{
int i;
NODE * head1, *head2, *head3;
head1 = (NODE *)malloc(sizeof(NODE));
input(head1);
head2 = (NODE *)malloc(sizeof(NODE));
input(head2);
head3 = multiplication(head1, head2);
output(head3);
DeleteLinklist(head1);
DeleteLinklist(head2);
DeleteLinklist(head3);
return 0;
}

复制代码

lemon3 · 发表于 2018-12-19 18:06:04

救救孩子，我想发布悬赏了为这题！！！

Croper · 发表于 2018-12-19 19:22:08

拜托先把链表的常用方法给谢了啊。。
本来想帮你写，但是发现你的链表连Append都没有。。还得别人帮你写么

lemon3 · 发表于 2018-12-20 11:03:36

Croper 发表于 2018-12-19 19:22
拜托先把链表的常用方法给谢了啊。。
本来想帮你写，但是发现你的链表连Append都没有。。还得别人帮你写么

dalao救救孩子，我现在考试有点多，这个还没时间来好好学！！！救救孩子

lemon3 · 发表于 2018-12-21 11:44:43

Croper 发表于 2018-12-19 19:22
拜托先把链表的常用方法给谢了啊。。
本来想帮你写，但是发现你的链表连Append都没有。。还得别人帮你写么

求帮忙修改！！！
不知道哪错了！！！
救救孩子！！！
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{ int coef, exp;
struct node  *next;
} NODE;

void multiplication( NODE *, NODE * , NODE * );
void input( NODE * );
void output( NODE * );
void creatlist( NODE * head2, NODE * p3 );

void creatList( NODE * head2, NODE * p3 )
{
NODE * p2 = head2->next;
while(p2->next != NULL)
{
p3 = ( NODE * )malloc(sizeof(NODE));
p3 = p3->next;
p3->coef = 0;
p3->exp = 0;
p2 = p2->next;
}
p3->next = (NODE *)malloc(sizeof(NODE));
p3->next=NULL;

}
void multiplication(NODE * head1, NODE * head2, NODE * head3 )
{
NODE * p1 = head1->next;
NODE * p2 = head2->next;
NODE * p3 = head3;
NODE * now;
NODE * temp;
void creatList(NODE * head2, NODE * p3);
while(p1->next != NULL)
{
p1=p1->next;
p2=head2->next;
p3=head3;
while(p2->next != NULL)
{
now->next = (NODE * )malloc(sizeof(NODE));
now->coef = p1->coef + p2->coef;
now->exp = p1->exp + p2->exp;
if(p3->next->exp == 0&&p3->next->coef == 0)
{
p3->next->exp = now->exp;
p3->next->coef = now->coef;
p3 = p3->next;
}
while(now->exp < p3->next->exp )
{
p3=p3->next;
}
}
}
temp = p3;
if(temp->exp == now->exp)
{
temp->coef += now->coef;
temp->exp += now->exp;
}
else
{
now->next = p3->next;
p3->next = now;
}
p2 = p2->next;
p3 = head3;
while(p3->next->next != NULL)
{
while(p3->next->coef == 0)
{
if(p3->next->next != NULL)
{
now = p3->next;
p3->next = now->next;
free(now);
}
else
{
p3 = p3->next;
}
p3->next = NULL;
if(head3->next == NULL)
{
head3->next->coef = 0;
head3->next->exp = 0;
head3->next->next = NULL;
}

}
}

void input( NODE * head )
{ int flag, sign, sum, x;
char c;

NODE * p = head;

while ( (c=getchar()) !='\n' )
{
      if ( c == '<' )
      { sum = 0;
         sign = 1;
         flag = 1;
      }
      else if ( c =='-' )
         sign = -1;
      else if( c >='0'&& c <='9' )
      { sum = sum*10 + c - '0';
      }
      else if ( c == ',' )
      { if ( flag == 1 )
         { x = sign * sum;
            sum = 0;
            flag = 2;
            sign = 1;
         }
      }
      else if ( c == '>' )
      { p->next = ( NODE * ) malloc( sizeof(NODE) );
         p->next->coef = x;
         p->next->exp  = sign * sum;
         p = p->next;
         p->next = NULL;
         flag = 0;
      }
}
}

void output( NODE * head )
{
while ( head->next != NULL )
{ head = head->next;
      printf("<%d,%d>,", head->coef, head->exp );
}
printf("\n");
}

int main()
{ NODE * head1, * head2, * head3;

head1 = ( NODE * ) malloc( sizeof(NODE) );
input( head1 );

head2 = ( NODE * ) malloc( sizeof(NODE) );
input( head2 );

head3 = ( NODE * ) malloc( sizeof(NODE) );
head3->next = NULL;
multiplication( head1, head2, head3 );

output( head3 );

return 0;
}

lemon3 · 发表于 2018-12-22 20:58:48

Croper 发表于 2018-12-22 10:24

老哥，delete在Dev上面unknown啊！！！

Croper · 发表于 2018-12-22 21:10:20

不好意思，习惯c++了，把new改malloc把delete改free吧

lemon3 · 发表于 2018-12-22 21:22:43

lemon3 · 发表于 2018-12-22 21:23:28

第三十四行是不是错了，既有地址符又有指针

lemon3 · 发表于 2018-12-22 21:26:57

给的函数不允许修改（所以你加的bool能删掉吗）

Croper · 发表于 2018-12-22 21:38:00

本帖最后由 Croper 于 2018-12-22 21:48 编辑

第三十四行是不是错了，既有地址符又有指针

没有错，传的就是指针的引用，你可以理解为这样Append 传入的指针就是实参本身而不是实参的复制，在Append里p=p->next出来之后就不需要再p=p->next了

给的函数不允许修改（所以你加的bool能删掉吗）

没看懂什么意思，output()里的bool b什么意思什么意思我已经在注释里说明白了啊

lemon3 · 发表于 2018-12-23 12:33:39

Croper 发表于 2018-12-22 21:38
没有错，传的就是指针的引用，你可以理解为这样Append 传入的指针就是实参本身而不是实参的复制，在Appen ...

是我的编译器不支持吗？到bool这儿就卡住了，编译不了

Croper · 发表于 2018-12-23 16:39:40

发一下错误信息

lemon3 · 发表于 2018-12-23 19:17:18

Croper 发表于 2018-12-23 16:39
发一下错误信息

就这样！！！！

Croper · 发表于 2018-12-23 20:09:10

忘了C里面没有bool了
开头加一段

#define true 1
#define false 0
typedef int bool;

复制代码

lemon3 · 发表于 2018-12-23 21:41:33

Croper 发表于 2018-12-23 20:09
忘了C里面没有bool了
开头加一段

结果是错的呀，返回的全是<0,0>

Croper · 发表于 2018-12-23 23:57:30

本帖最后由 Croper 于 2018-12-24 00:09 编辑

我这儿是没有问题的。。。你那是什么破编译器啊。。。。把if(!b)改成if(b==false)试试吧。。
另外自己也思考下呗，我注释都写这么清晰了，b就是储存是否产生过输出的一个flag，没有产生过输出的话就输出一个<0,0>占位，避免空输出。bool不行就改成同样的int呗，

学语言你要自己会看错误提示会调试程序啊，unknown type name "bool"就是c语言不支持bool啊,既然不支持就改其他方法啊。学语言不会自己调试不可能每个问题都来问啊，自己按步执行观察每个变量的变化，哪儿变量有意外的变化自己看啊，刚开始你扔一串东西上来，要求链表实现，结果自己就写了个头节点，其他链表的实现方法一点儿没有，我真的是看着都不想动键盘。。

lemon3 · 发表于 2018-12-24 00:01:28

嗯，我今天看了一天数据结构，慢慢有点理解了。谢谢！！！

lemon3 · 发表于 2018-12-24 00:02:37

Croper 发表于 2018-12-23 23:57
我这儿是没有问题的。。。你那是什么破编译器啊。。。。把if(!b)改成if(b==false)试试吧。。
另外自己也思 ...

嗯，我今天看了一天数据结构，慢慢有点理解了。谢谢！！！

账号		自动登录	找回密码
密码			立即注册

[已解决]一元多项式相加问题（C语言实现数据结构）

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块