用线性表实现一元多项式的加法

65 阅读 0 评论 43 点赞

我是靠谱客的博主无语大碗，最近开发中收集的这篇文章主要介绍用线性表实现一元多项式的加法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

struct monomial {//单项式
int exponent;//指数
float coefficient;//系数
};

struct node {
   monomial m;
   struct node *next;
};
typedef struct node *polynomial;
void initpolynomial(polynomial &p, int count) { //初始化链表
   polynomial rear, t;
   rear = p = (polynomial)malloc(sizeof(node)); //j建立一个带有头结点的空链表，即初始化
   p->next = NULL;

for (int i = 0; i < count; i++) {

       t = (polynomial)malloc(sizeof(node)); //为新节点分配存储单元
       cin >> t->m.coefficient;
       cin >> t->m.exponent;
       t->next = NULL;
       rear->next = t;
       rear = t;
   }
}

void initpolynomial(polynomial p) { //打印多项式
   if (p->next == NULL) {
       printf("0n");
   }//判断是否为空链表

node *thenode = p->next;

   while (thenode != NULL) {
       printf("+%fx^%d", thenode->m.coefficient, thenode->m.exponent);
       thenode = thenode->next;
   }

printf("n");
}

void freepolynomial (polynomial p) {
node *thenode;

   while (p->next != NULL) {
       thenode = p->next;
       free(thenode);
   }

   free(p);//释放完内存后，指向链表的指针值也要置空
}//链表内存要一个一个释放
polynomial addpolynomial(polynomial p1, polynomial p2) {
   polynomial result = (polynomial)malloc(sizeof(node));
   node *idx1 = p1->next; //首元节点
   node *idx2 = p2->next;
   node *idx = result;

   while (idx1 != NULL or idx2 != NULL) {
       if (idx1 == NULL) { //把其中一个多项式是空的情况先列出来
           while (idx2 != NULL) {
               idx->next = (node *)malloc(sizeof(node));
               idx = idx->next;
               idx->next = NULL;
               idx->m.exponent = idx2->m.exponent;
               idx->m.coefficient = idx2->m.coefficient;
               idx2 = idx2->next;
           }

           break;
       } else if (idx2 == NULL) {
           while (idx1 != NULL) {
               idx->next = (node *)malloc(sizeof(node));
               idx = idx->next;
               idx->next = NULL;
               idx->m.exponent = idx1->m.exponent;
               idx->m.coefficient = idx1->m.coefficient;
               idx = idx->next;
           }

           break;
       } else {
           if (idx1->m.exponent > idx2->m.exponent) {

               idx->next = (node *)malloc(sizeof(node));
               idx = idx->next;
               idx->next = NULL;
               idx->m.exponent = idx2->m.exponent;
               idx->m.coefficient = idx2->m.coefficient;
               idx2 = idx2->next;
           } else if (idx1->m.exponent < idx2->m.exponent) {
               idx->next = (node *)malloc(sizeof(node));
               idx = idx->next;
               idx->next = NULL;
               idx->m.exponent = idx1->m.exponent;
               idx->m.coefficient = idx1->m.coefficient;
               idx1 = idx1->next;
           } else {
               idx->next = (node *)malloc(sizeof(node));
               idx = idx->next;
               idx->next = NULL;
               idx->m.exponent = idx1->m.exponent;
               idx->m.coefficient = idx1->m.coefficient + idx2->m.coefficient;
               idx1 = idx1->next;
               idx2 = idx2->next;
           }
       }
   }

return result;
}

int main() {
   polynomial p1, p2;
   int m, n;
   cout << "请输入第一个多项式的项数：";
   cin >> m;
   cout << "请输入第二个多项式的项数：";
   cin >> n;
   initpolynomial(p1, m);
   initpolynomial(p2, n);
   initpolynomial(addpolynomial(p1, p2));
   freepolynomial (p1);
   freepolynomial(p2);
}