鏈接列表多項式乘法

Question

我寫了一個程序，以單鏈表的形式乘以兩個多項式。我無法使用此代碼打印輸出。

我得到的輸出是

1st Number: 5x^2 + 4x^1 + 2x^0 
2nd Number: 5x^1 + 5x^0 
Multiplied polynomial: 

我該如何解決呢？

我的代碼：

// C++ program for multiplication of two polynomials 
// using Linked Lists 
#include<bits/stdc++.h> 
using namespace std; 

// Node structure containing power and coefficient of variable 
struct node 
{ 
    int coeff; 
    int exp; 
    struct node *next; 
}; 
void padd(float, int, node**);   
// Function to create new node 
void create_node(int x, int y, struct node **temp) 
{ 
    struct node *r,*z ; 
    z = *temp; 
    if(z == NULL) 
    { 
     r =(struct node*)malloc(sizeof(struct node)); 
     r->coeff = x; 
     r->exp = y; 
     *temp = r; 
     r->next = (struct node*)malloc(sizeof(struct node)); 
     r = r->next; 
     r->next = NULL; 
    } 
    else 
    { 
     r->coeff = x; 
     r->exp = y; 
     r->next = (struct node*)malloc(sizeof(struct node)); 
     r = r->next; 
     r->next = NULL; 
    } 
} 

// Function Multiplying two polynomial numbers 
void polymul (struct node *poly1, struct node *poly2, 
        struct node *poly) 
{ 
    struct node *y1 ; 
    float coeff1; 
    int exp1 ; 

    y1 = poly2 ; /* point to the starting of the second linked list */ 
if (poly1 == NULL && poly2 == NULL) 
     return ; 

    /* if one of the list is empty */ 
if (poly1 == NULL) 
     poly = poly2 ; 
    else 
    { 
     if (poly2 == NULL) 
      poly = poly1 ; 
     else/* if both linked lists exist */ 

     { 
      /* for each term of the first list */ 
      while (poly1 != NULL) 
      { 
       /* multiply each term of the second linked list with a 
        term of the first linked list */ 
       while (poly2 != NULL) 
       { 
        coeff1 = poly1 -> coeff * poly2 -> coeff ; 
        exp1 = poly1 -> exp + poly2 -> exp ; 
        poly2 = poly2 -> next ; 

        /* add the new term to the resultant polynomial */ 

        padd (coeff1, exp1, &poly) ; 
       } 

       poly2 = y1 ; /* reposition the pointer to the starting of 
         the second linked list */ 


       poly1 = poly1 -> next ; /* go to the next node */ 

      } 
     } 
    } 
} 

/* adds a term to the polynomial in the descending order of the exponent */ 
void padd (float coeff, int exp, struct node **s) 
{ 
    struct node *r, *temp = *s ; 

    /* if list is empty or if the node is to be inserted before the first node */ 
if (*s == NULL || exp > (*s) -> exp) 
    { 
     *s=r = (struct node*) malloc (sizeof (struct node)) ; 
     (*s) -> coeff = coeff ; 
     (*s) -> exp = exp ; 
     (*s)-> next = temp ; 
    } 
    else 
    { 
     /* traverse the entire linked list to search the position to insert a new node */ 
     while (temp != NULL) 
      { 
       if (temp -> exp == exp) 
       { 
        temp -> coeff += coeff ; 
        return ; 
       } 

       if (temp -> exp > exp && (temp -> next -> exp < exp || temp -> next == NULL)) 
        { 
         r = (struct node*)malloc (sizeof (struct node)) ; 
         r -> coeff = coeff; 
         r -> exp = exp ; 
         r -> next = temp -> next ; 
         temp -> next = r ; 
         return ; 
        } 

      temp = temp -> next ; /* go to next node */ 

      } 

     r -> next = NULL ; 
     temp -> next = r ; 
    } 
} 

// Display Linked list 
void show(struct node *node) 
{ 
while(node->next != NULL) 
    { 
    printf("%dx^%d", node->coeff, node->exp); 
    node = node->next; 
    if(node->next != NULL) 
     printf(" + "); 
    } 
} 

// Driver program 
int main() 
{ 
    struct node *poly1 = NULL, *poly2 = NULL, *poly = NULL; 

    // Create first list of 5x^2 + 4x^1 + 2x^0 
    create_node(5,2,&poly1); 
    create_node(4,1,&poly1); 
    create_node(2,0,&poly1); 

    // Create second list of 5x^1 + 5x^0 
    create_node(5,1,&poly2); 
    create_node(5,0,&poly2); 

    printf("1st Number: "); 
    show(poly1); 

    printf("\n2nd Number: "); 
    show(poly2); 

    poly = (struct node *)malloc(sizeof(struct node)); 

    // Function multiply two polynomial numbers 
    polymul(poly1, poly2, poly); 

    // Display resultant List 
    printf("\nMultiplied polynomial: "); 
    show(poly); 

return 0; 
} 

Answer 1

你應該功能polymul之前聲明你的函數padd()或者你可以在頂部，這樣編譯器知道該函數padd將polymul後遇到寫一個函數原型。

對於第二個錯誤，您應該輸入malloc函數的輸出爲struct node *，因爲malloc返回void *類型的值。

只需將代碼中的代碼添加到malloc函數中即可。

r = (struct node*)malloc (sizeof (struct node)) ; 

鏈表中有一些指針問題。我已經將它們固定在ideone鏈接中。

#include<bits/stdc++.h> 

    using namespace std; 

// Node structure containing power and coefficient of variable 

    struct node 
    { 
    int coeff; 
    int exp; 
    struct node *next; 
}; 

// Function to create new node 


void create_node(int x, int y, struct node **temp) 
{ 

    struct node *r, *tmp=NULL ; 

    if(*temp == NULL) // If the list is NULL then add node at First position 
    { 
     r =(struct node*)malloc(sizeof(struct node)); 
     r->coeff = x; 
     r->exp = y; 
     r->next = NULL; 
     *temp = r; 
     /*r->next = (struct node*)malloc(sizeof(struct node)); 
     r = r->next; 
     r->next = NULL;*/ //Not needed 
    } 
    else 
    { 
     tmp = *temp; 
     while (tmp->next != NULL) { 
      tmp = tmp -> next; //Travel to the end of linked list 
     } 
     r = (struct node*)malloc(sizeof(struct node)); 
     r->coeff = x; 
     r->exp = y; 
     r->next = NULL; 
     tmp->next = r; //Add new node to the list 

    } 
} 

// Function Adding two polynomial numbers 

/* adds a term to the polynomial in the descending order of the exponent */ 

    void padd (int coeff, int exp, struct node **s) 
    { 
    struct node *r, *temp = *s ; 
    struct node *tmp = *s; 
    /* if list is empty or if the node is to be inserted before the first node 
    */ 



    if (temp == NULL || exp > (temp) -> exp) 

    { 
     r = (struct node*)malloc (sizeof (struct node)) ; 
     r -> coeff = coeff ; 
     r -> exp = exp ; 
     r -> next = temp ; 
     temp = r; 
     *s = r; 
    } 
    else 
    { 
     /* traverse the entire linked list to search the position to insert 
     a new node */ 
     while (temp != NULL) 
      { 
       if (temp -> exp == exp) 
       { 
        temp -> coeff += coeff ; 
        return; 
       } else if (temp -> exp > exp && (temp -> next -> exp < exp ||temp ->next == NULL)) 
        { 
         r = (struct node*)malloc (sizeof (struct node)) ; 
         r -> coeff = coeff; 
         r -> exp = exp ; 
         r -> next = temp -> next ; 
         temp -> next = r ; 
         return; 
        } 

       temp = temp -> next ; /* go to next node */ 

      } 

     r -> next = NULL ; 
     temp -> next = r ; 
    } 
} 

    struct node * polymul (struct node *poly1, struct node *poly2, struct node *poly3) 
    { 

    struct node *y1 ; 
    int coeff1; 
    int exp1 ; 

    struct node *poly = poly3; 
    y1 = poly2 ;   /* point to the starting of the second linked list */ 
    if (poly1 == NULL && poly2 == NULL) 
     return NULL; 

    /* if one of the list is empty */ 
    if (poly1 == NULL) { 
     poly = poly2 ; 
    } else 
    { 
     if (poly2 == NULL) 
      poly = poly1 ; 
     else /* if both linked lists exist */ 

     { 
      /* for each term of the first list */ 
      while (poly1 != NULL) 
      { 
       /* multiply each term of the second linked list with a 
        term of the first linked list */ 
       while (poly2 != NULL) 
       { 
        coeff1 = poly1 -> coeff * poly2 -> coeff ; 
        exp1 = poly1 -> exp + poly2 -> exp ; 
        poly2 = poly2 -> next ; 

        /* add the new term to the resultant polynomial */ 

        padd(coeff1, exp1, &poly) ; 
       } 

       poly2 = y1 ; /* reposition the pointer to the starting of 
           the second linked list */ 


       poly1 = poly1 -> next ; /* go to the next node */ 

      } 
     } 
    } 
    return poly; 
} 



// Display Linked list 
    void show(struct node *node) 
    { 
     while(node != NULL) // if we use node->next != NULL while will break at the last node skipping it 
     { 
      printf("%dx^%d", node->coeff, node->exp); 

      if(node->next != NULL) 
       printf(" + "); 

      node = node->next; 
     } 
    } 

// Driver program 

    int main() 
    { 
    struct node *poly1 = NULL, *poly2 = NULL, *poly = NULL; 

    // Create first list of 5x^2 + 4x^1 + 2x^0 

    create_node(5,2,&poly1); 
    create_node(4,1,&poly1); 
    create_node(2,0,&poly1); 

    // Create second list of 5x^1 + 5x^0 

    create_node(5,1,&poly2); 
    create_node(5,0,&poly2); 

    printf("1st Number: "); 
    show(poly1); 

    printf("\n2nd Number: "); 
    show(poly2); 

    poly = (struct node *)malloc(sizeof(struct node)); 

    // Function add two polynomial numbers 

    poly = polymul(poly1, poly2, poly); 

    // Display resultant List 

    printf("\nAdded polynomial: "); 
    show(poly); 

return 0; 
} 

Ideone Link