论坛 › C\C++交流 › 一元多项式相加问题（C语言实现数据结构）

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

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

遇到了一元多项式的题目，要求用链表实现，给定代码如下，现在我不知道怎么写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;
}

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

ok

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语言实现数据结构）