C++에서 연결 목록을 사용하여 두 개의 다항식 추가.

<시간/>

이 개념을 더 잘 이해하기 위해 먼저 필요한 모든 기본 내용을 살펴보겠습니다.

연결 목록 각 요소를 목록의 노드에 개체로 저장하는 데이터 구조입니다. 모든 메모에는 두 부분으로 된 데이터 han과 다음 노드에 대한 링크가 포함되어 있습니다.

다항식 변수와 계수로 구성된 수학적 표현입니다. 예를 들어 x^2 - 4x + 7

다항식 연결 목록에서 , 다항식의 계수와 지수는 목록의 데이터 노드로 정의됩니다.

연결 목록으로 저장된 두 개의 다항식을 추가합니다. 동일한 검정력을 갖는 변수의 계수를 추가해야 합니다. 연결 리스트 노드에는 3개의 멤버가 포함되며 계수 값은 다음 노드로 연결됩니다.

다항식을 저장하는 데 사용되는 연결 목록은 다음과 같습니다. -

다항식 :4x⁷ + 12x² + 45

C++에서 연결 목록을 사용하여 두 개의 다항식 추가.

이것이 다항식을 나타내는 연결 리스트의 모습입니다.

연결 목록으로 표현되는 두 개의 다항식을 추가합니다. 노드의 지수 값에서 값을 확인합니다. 동일한 지수 값에 대해 계수를 추가합니다.

예,

Input :
p1= 13x⁸ + 7x⁵ + 32x² + 54
p2= 3x¹² + 17x⁵ + 3x³ + 98

Output : 3x¹²+ 13x⁸ + 24x⁵+ 3x3 + 32x² + 152

설명 − 모든 거듭제곱에 대해 동일한 지수 값을 갖는 지수의 계수를 확인하고 추가합니다. 최종 다항식을 반환합니다.

알고리즘

입력 - 연결 리스트로 표현되는 다항식 p1 및 p2.

Step 1: loop around all values of linked list and follow step 2& 3.
Step 2: if the value of a node’s exponent. is greater copy this node to result node and head towards the next node.
Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result.
Step 4: Print the resultant node.

예시

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int coeff;
   int pow;
   struct Node *next;
};
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->pow = y;
      *temp = r;
      r->next = (struct Node*)malloc(sizeof(struct Node));
      r = r->next;
      r->next = NULL;
   } else {
      r->coeff = x;
      r->pow = y;
      r->next = (struct Node*)malloc(sizeof(struct Node));
      r = r->next;
      r->next = NULL;
   }
}
void polyadd(struct Node *p1, struct Node *p2, struct Node *result){
   while(p1->next && p2->next){
      if(p1->pow > p2->pow){
         result->pow = p1->pow;
         result->coeff = p1->coeff;
         p1 = p1->next;
      }
      else if(p1->pow < p2->pow){
         result->pow = p2->pow;
         result->coeff = p2->coeff;
         p2 = p2->next;
      } else {
         result->pow = p1->pow;
         result->coeff = p1->coeff+p2->coeff;
         p1 = p1->next;
         p2 = p2->next;
      }
      result->next = (struct Node *)malloc(sizeof(struct Node));
      result = result->next;
      result->next = NULL;
   }
   while(p1->next || p2->next){
      if(p1->next){
         result->pow = p1->pow;
         result->coeff = p1->coeff;
         p1 = p1->next;
      }
      if(p2->next){
         result->pow = p2->pow;
         result->coeff = p2->coeff;
         p2 = p2->next;
      }
      result->next = (struct Node *)malloc(sizeof(struct Node));
      result = result->next;
      result->next = NULL;
   }
}
void printpoly(struct Node *node){
   while(node->next != NULL){
      printf("%dx^%d", node->coeff, node->pow);
      node = node->next;
      if(node->next != NULL)
         printf(" + ");
   }
}
int main(){
   struct Node *p1 = NULL, *p2 = NULL, *result = NULL;
   create_node(41,7,&p1);
   create_node(12,5,&p1);
   create_node(65,0,&p1);
   create_node(21,5,&p2);
   create_node(15,2,&p2);
   printf("polynomial 1: ");
   printpoly(p1);
   printf("\npolynomial 2: ");
   printpoly(p2);
   result = (struct Node *)malloc(sizeof(struct Node));
   polyadd(p1, p2, result);
   printf("\npolynomial after adding p1 and p2 : ");
   printpoly(result);
   return 0;
}

출력

polynomial 1: 41x^7 + 12x^5 + 65x^0
polynomial 2: 21x^5 + 15x^2
polynomial after adding p1 and p2 : 41x^7 + 33x^5 + 15x^2 + 65x^0