时间截止2022.12.21 24点

一元稀疏多项式简单计算器1）问题描述设计一个一元稀疏多项式简单计算器。2）基本要求一元稀疏多项式简单计算器的基本功能是：a.输入并建立多项式；b.输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci,ei，分别是第i项的系数和指数，序列按指数降序排列；c.多项式a和b相加，建立多项式a+b；d.多项式a和b相减，建立多项式a-b；e.计算多项式在x处的值；3）测试数据a.
（2x+5x^8-3.1x^11）+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7)
；b.
(6x^-3-x+4.4x^2-1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=-7.8x^15-1.2x^9-x+12x^-3
c.
(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(x^5+x^2+x+1)
；d.
(x+x^3)+(-x-x^3)=0
；e.
(x+x^2+x^3)+0=(x^3+x^2+x)
；4）实现提示用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。

一元稀疏多项式计算器

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDataType;

typedef struct List
{
    SLDataType data;//存系数
    SLDataType val;//存指数
    struct List* next;
}LS, LN;

LS* ListInit();//链表初始化（实际建立哨兵位头节点）

void ListPushBack(LS* Phead, SLDataType x, SLDataType y);//尾插构建链表

void PrintPloy(LS* Phead);//输出多项式

void AddPloy(LS* Pheada, LS* Pheadb, LS* AddPhead);//A+B

void SubPloy(LS* Pheada, LS* Pheadb, LS* SubPhead);//A-B

void MulPloy(LS* Pheada, LS* Pheadb, LS* MulPhead);//A*B

void DerPloy(LS* Pheada, LS* DerPhead);//A的导数

//创建结点
LS* BuyNode(SLDataType x, SLDataType y)
{
    LS* newnode = (LS*)malloc(sizeof(LS));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;//存系数
    newnode->val = y;//存指数
    newnode->next = NULL;
    return newnode;
}

//初始化建立哨兵位头节点
LS* ListInit()
{
    LS* Phead = BuyNode(0, 0);
    Phead->next = Phead;
    return Phead;
}
//尾插构建链表
void ListPushBack(LS* Phead, SLDataType x, SLDataType y)
{
    assert(Phead);
    LS* newnode = BuyNode(x, y);
    //单向循环，因此找尾部
    LS* tail = Phead->next;
    while (tail->next != Phead)
    {
        tail = tail->next;
    }
    tail->next = newnode;
    newnode->next = Phead;
}
//输出打印多项式
void PrintPloy(LS* Phead)
{
    int count = 1;
    LS* tail = Phead->next;
    assert(Phead);
    while (tail != Phead)
    {
        if (tail->data == 0)//系数为0
        {
            tail = tail->next;
            continue;
        }
        if (tail->val == 0 )//指数为0
        {
            printf("%d", tail->data);
        }
        if (tail->data > 0 && tail->val > 0)//系数大于0输出
        {
            if (count != 1)
                printf(" + ");
            if (tail->val == 1)//指数为1时输出
            {
                if (tail->data == 1.0)
                    printf("X");//系数为1时输出
                else
                    printf("%dX", tail->data);
            }
            else//指数大于1的时候输出
            {
                if (tail->data == 1.0)
                    printf("X^%d", tail->val);
                else
                    printf("%dX^%d", tail->data, tail->val);
            }
        }
        if (tail->data < 0 && tail->val > 0)//系数小于0输出
        {
            if (count != 1)
                printf(" - ");
            if (tail->val == 1)//指数为1时输出
            {
                if (tail->data == 1.0)
                    printf("X");//系数为1时输出
                else
                    printf("%dX", tail->data * (-1));
            }
            else//指数大于1的时候输出
            {
                if (tail->data == 1.0)
                    printf("X^%d", tail->val);
                else
                    printf("%dX^%d", tail->data * (-1), tail->val);
            }
        }
        count = 0;
        tail = tail->next;
    }
}



int cmp(SLDataType a, SLDataType b)
{
    if (a > b)
        return 1;
    else if (a == b)
        return 0;
    else
        return -1;
}
//将运算后的结果插入
void Insert(LS* AddPhead, SLDataType x, SLDataType y)//x是指数，y是系数
{
    LS* cur = AddPhead;
    assert(AddPhead);
    while (cur->next != AddPhead && cmp(cur->next->val, x) < 0)
    {
        cur = cur->next;
    }
    if (cur->next != AddPhead && cmp(cur->next->val, x) == 0)
    {
        cur->next->data += y;
    }
    else
    {
        LS* newnode = (LS*)malloc(sizeof(LS));
        if (newnode == NULL)
        {
            printf("malloc fail\n");
            exit(-1);
        }
        newnode->data = y;
        newnode->val = x;
        newnode->next = cur->next;
        cur->next = newnode;
    }
}
//实现A+B
void AddPloy(LS* Pheada, LS* Pheadb, LS* AddPhead)
{
    LS* str = Pheadb->next;
    LS* cur = Pheadb->next;
    assert(Pheada && Pheadb && AddPhead);
    for (cur = Pheada->next; cur != Pheada; cur = cur->next)
    {
        Insert(AddPhead, cur->val, cur->data);
    }
    for (str = Pheadb->next; str != Pheadb; str = str->next)
    {
        Insert(AddPhead, str->val, str->data);
    }
}

//A-B
void SubPloy(LS* Pheada, LS* Pheadb, LS* SubPhead)
{
    LS* str = Pheadb->next;
    LS* cur = Pheada->next;
    assert(Pheada && Pheadb && SubPhead);
    for (cur = Pheada->next; cur != Pheada; cur = cur->next)//将A插入
    {
        Insert(SubPhead, cur->val, cur->data);
    }
    for (str = Pheadb->next; str != Pheadb; str = str->next)//将B插入
    {
        str->data = -(str->data);//将B的系数变为负值
        Insert(SubPhead, str->val, str->data);
        str->data = -(str->data);//将B的系数变为原值
    }
}
//A*B
void MulPloy(LS* Pheada, LS* Pheadb, LS* MulPhead)
{
    int a = 0, b = 0;
    LS* cur = Pheada->next;
    LS* str = Pheadb->next;
    LS* prev = Pheada;
    assert(Pheada && Pheadb && MulPhead);
    for (cur = Pheada->next; cur != Pheada; cur = cur->next)
    {
        for (str = Pheadb->next; str != Pheadb; str = str->next)
        {
            a = (cur->data) * (str->data);//系数相乘
            b = (cur->val) + (str->val);//指数相加
            Insert(MulPhead, b, a);//将运算后的结果插入
        }
    }
}
//A的导数
void DerPloy(LS* Pheada, LS* DerPhead)
{
    LS* cur = Pheada->next;
    assert(Pheada);
    for (cur = Pheada->next; cur != Pheada; cur = cur->next)
    {
        if (cur->val == 0)//判断指数是否为0
        {
            cur->data = 0;
        }
        else
        {
            cur->data *= cur->val;//系数与指数相乘
            cur->val = cur->val - 1;
        }
        Insert(DerPhead, cur->val, cur->data);//将结果插入
    }
}

int main()
{
    LS* Pa = ListInit();//存放A多项式
    LS* Pb = ListInit();//存放B多项式
    LS* Add = ListInit();//存放A+B多项式
    LS* Sub = ListInit();//存放A-B多项式
    LS* Mul = ListInit();//存放A*B多项式
    LS* Der = ListInit();//存放A的导数
    size_t n = 0, m = 0;
    int a = 0, b = 0, c = 0, d = 0;
    printf("A多项式的项数：");
    scanf("%d", &n);//A的项数
    for (size_t i = 1; i <= n; i++)
    {
        printf("A多项式的第%d项系数和指数：", i);
        scanf("%d %d", &a, &b);
        ListPushBack(Pa, a, b);
    }
    printf("A多项式的输出：");
    PrintPloy(Pa);
    printf("\n");
    printf("B多项式的项数：");
    scanf("%d", &m);
    for (size_t i = 1; i <= m; i++)
    {
        printf("B多项式的第%d项系数和指数：", i);
        scanf("%d %d", &c, &d);
        ListPushBack(Pb, c, d);
    }
    printf("B多项式的输出：");
    PrintPloy(Pb);
    printf("\n");
    AddPloy(Pa, Pb, Add);
    printf("多项式A+B的输出：");
    PrintPloy(Add);
    printf("\n");
    printf("多项式A-B的输出：");
    SubPloy(Pa, Pb, Sub);
    PrintPloy(Sub);
    printf("\n");
    printf("多项式A*B的输出：");
    MulPloy(Pa, Pb, Mul);
    PrintPloy(Mul);
    printf("\n");
    printf("多项式A的导数输出：");
    DerPloy(Pa, Der);
    PrintPloy(Der);
    printf("\n");
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX_TERMS 100 // 最大多项式项数

// 多项式的一项
typedef struct
{
  float coef; // 系数
  int expon;  // 指数
} polynomialTerm;

// 多项式结构体
typedef struct polynomial
{
  int n;                           // 多项式的项数
  polynomialTerm terms[MAX_TERMS]; // 多项式的各项
} polynomial;

// 创建一个空的多项式
polynomial createPolynomial()
{
  polynomial p;
  p.n = 0;
  return p;
}

// 向多项式中添加一项
void addTerm(polynomial *p, float coef, int expon)
{
  int i;
  // 查找适当的位置
  for (i = 0; i < p->n && p->terms[i].expon > expon; i++)
    ;
  // 把更高次项向后移动一位
  int j;
  for (j = p->n; j > i; j--)
    p->terms[j] = p->terms[j - 1];
  // 插入新项
  p->terms[i].coef = coef;
  p->terms[i].expon = expon;
  p->n++;
}

// 从多项式中删除一项
void removeTerm(polynomial *p, int expon)
{
  int i;
  // 查找要删除的项
  for (i = 0; i < p->n && p->terms[i].expon != expon; i++)
    ;
  // 删除项
  int j;
  for (j = i; j < p->n - 1; j++)
    p->terms[j] = p->terms[j + 1];
  p->n--;
}

// 输出多项式
void printPolynomial(polynomial p)
{
  int i;
  printf("%d", p.n);
  for (i = 0; i < p.n; i++)
    printf(", %f, %d", p.terms[i].coef, p.terms[i].expon);
  printf("\n");
}

// 计算多项式在 x 处的值
float evaluatePolynomial(polynomial p, float x)
{
  int i;
  float result = 0;
  for (i = 0; i < p.n; i++)
    result += p.terms[i].coef * pow(x, p.terms[i].expon);
  return result;
}

// 多项式相加
polynomial addPolynomials(polynomial a, polynomial b)
{
  polynomial result = createPolynomial();

  int i = 0, j = 0;
  while (i < a.n && j < b.n)
  {
    if (a.terms[i].expon == b.terms[j].expon)
    {
      addTerm(&result, a.terms[i].coef + b.terms[j].coef,
              a.terms[i].expon);
      i++;
      j++;
    }
    else if (a.terms[i].expon > b.terms[j].expon)
    {
      addTerm(&result, a.terms[i].coef, a.terms[i].expon);
      i++;
    }
    else
    {
      addTerm(&result, b.terms[j].coef, b.terms[j].expon);
      j++;
    }
  }
  // 将剩余项加入结果
  while (i < a.n)
  {
    addTerm(&result, a.terms[i].coef, a.terms[i].expon);
    i++;
  }
  while (j < b.n)
  {
    addTerm(&result, b.terms[j].coef, b.terms[j].expon);
    j++;
  }

  return result;
}

// 多项式相减
polynomial subtractPolynomials(polynomial a, polynomial b)
{
  polynomial result = createPolynomial();

  int i = 0, j = 0;
  while (i < a.n && j < b.n)
  {
    if (a.terms[i].expon == b.terms[j].expon)
    {
      addTerm(&result, a.terms[i].coef - b.terms[j].coef,
              a.terms[i].expon);
      i++;
      j++;
    }
    else if (a.terms[i].expon > b.terms[j].expon)
    {
      addTerm(&result, a.terms[i].coef, a.terms[i].expon);
      i++;
    }
    else
    {
      addTerm(&result, -b.terms[j].coef, b.terms[j].expon);
      j++;
    }
  }
  // 将剩余项加入结果
  while (i < a.n)
  {
    addTerm(&result, a.terms[i].coef, a.terms[i].expon);
    i++;
  }
  while (j < b.n)
  {
    addTerm(&result, -b.terms[j].coef, b.terms[j].expon);
    j++;
  }

  return result;
}

int main()
{
  // 创建多项式
  polynomial a = createPolynomial();
  addTerm(&a, 2, 1);
  addTerm(&a, 5, 8);
  addTerm(&a, -3.1, 11);

  polynomial b = createPolynomial();
  addTerm(&b, 7, 0);
  addTerm(&b, -5, 8);
  addTerm(&b, 11, 9);

  // 输出多项式
  printf("a = ");
  printPolynomial(a);
  printf("b = ");
  printPolynomial(b);

  // 多项式相加
  polynomial c = addPolynomials(a, b);
  printf("a + b = ");
  printPolynomial(c);

  // 多项式相减
  polynomial d = subtractPolynomials(a, b);
  printf("a - b = ");
  printPolynomial(d);

  // 计算多项式在 x 处的值
  float x = 2.0;
  printf("a(%f) = %f\n", x, evaluatePolynomial(a, x));
  printf("b(%f) = %f\n", x, evaluatePolynomial(b, x));
  printf("c(%f) = %f\n", x, evaluatePolynomial(c, x));
  printf("d(%f) = %f\n", x, evaluatePolynomial(d, x));

  return 0;
}