#include<stdio.h>
#include<stdlib.h>
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;//系数
int expon;//指数
Polynomial link;//后继指针
};
void display();//交互界面
void testIO();//多项式输入输出测试
void calculate();//多项式计算
void Attach(int c, int e, Polynomial *pRear);//向多项式链表中插入结点
Polynomial ReadPoly();//读取多项式链表
Polynomial Add(Polynomial P1, Polynomial P2);//多项式相加
Polynomial daoshu(Polynomial P1, Polynomial P2);//导数
Polynomial Mult(Polynomial P1, Polynomial P2);//多项式相乘
Polynomial Combin(Polynomial P);//合并同类项
Polynomial Rev(Polynomial P);//多项式每一项系数取相反数
void PrintDown(Polynomial P, int flag);//降幂输出
int main()
{ int option;
while (1)
{ system("cls"); display();
scanf("%d", &option); getchar(); fflush(stdin);
switch (option) {
case 1: testIO(); break;//多项式输入输出测试
case 2: calculate(); break;//多项式计算
case 3: return 0;//退出程序
default: printf("输入有误,请重新输入\n");
system("pause"); break;
}
}
}
//交互界面
void display() {
printf("**************一元多项式计算器**************\n");
printf("1.多项式输入输出测试\n");
printf("2.多项式计算\n");
printf("3.退出程序\n");
printf("请输入您的选择:");
}
//导数
Polynomial daoshu(Polynomial P1, Polynomial P2)
{ Polynomial q=p1->link,l,g,h;
g=l= (Polynomial)malloc(sizeof(struct PolyNode));
g->link=NULL;
while(q)
{if(q->expon!=0)
{h=(Polynomial)malloc(sizeof(struct PolyNode));
h->coef=q->coef*q->expon;
h->expon=q->expon-1;
h->link=l->link;
l->link=h;
l=h;
}
return(g)
}
//多项式输入输出测试
void testIO() {
printf("多项式输入输出测试:\n");
Polynomial L = ReadPoly();//读入多项式
PrintDown(L, 0);//降序输出
printf("测试完毕\n"); system("pause");
}
//多项式计算
void calculate() {
Polynomial P1, P2, Res;
char flag; int option;
printf("多项式计算:\n");
while (1) {
printf("请输入运算符号(仅支持+、-、*和导数(导数请输入!),输入#返回上一层):");
scanf("%c", &flag); getchar(); fflush(stdin);
switch (flag) {
case '+': option = 1; break;
case '-': option = 2; break;
case '*': option = 3; break;
case '!': option = 4; break;
case '#': return;
default: printf("输入有误,请重新输入\n");
system("pause"); option = -1; break;
}
if (option != -1) {
P1 = ReadPoly(); getchar(); fflush(stdin);
P2 = ReadPoly(); getchar(); fflush(stdin);
if (option == 1) { Res = Add(P1, P2);}
else if (option == 2) { Res = Add(P1, Rev(P2)); }
else if (option == 3) { Res = Mult(P1, P2); }
else if (option == 4) { Res = daoshu(P1,P2); }
PrintDown(Res, 0); system("pause");
}
}
}
//向多项式链表中插入结点(尾插法)
void Attach(int c, int e, Polynomial *pRear) {
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
if (c == 0) { return; }
else { P->coef = c; P->expon = e; }
P->link = NULL; (*pRear)->link = P; *pRear = P;
}
//读取多项式链表
Polynomial ReadPoly() {
Polynomial P, Rear, t;
int n, c, e;
printf("输入多项式的项数:");
scanf("%d", &n);
if (n <= 0) { printf("输入有误\n"); return NULL; }
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL; Rear = P;
printf("输入多项式的系数与指数:\n");
while (n--) {
scanf("%d%d", &c, &e);
Attach(c, e, &Rear);
}
t = P; P = P->link; free(t);
P = Combin(P);
return P;
}
//多项式相加
Polynomial Add(Polynomial P1, Polynomial P2)
{
Polynomial P, Rear, t;
Polynomial t1 = P1;
Polynomial t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL; Rear = P;
while (t1&&t2)
{
if (t1->expon == t2->expon)
{
if (t1->coef + t2->coef)
{
Attach(t1->coef + t2->coef, t1->expon, &Rear);
t1 = t1->link; t2 = t2->link;
}
}
else if (t1->expon > t2->expon)
{
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
else
{
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
}
while (t1)
{
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
while (t2)
{
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
Rear->link = NULL;
t = P; P = P->link; free(t);
P = Combin(P);
return P;
}
//多项式相乘
Polynomial Mult(Polynomial P1, Polynomial P2) {
Polynomial P, Rear, t1, t2, t;
int c, e;
if (!P1 || !P2)return NULL;
t1 = P1; t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL; Rear = P;
while (t2) {
Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
t2 = t2->link;
}
t1 = t1->link;
while (t1) {
t2 = P2; Rear = P;
while (t2) {
e = t1->expon + t2->expon;
c = t1->coef*t2->coef;
while (Rear->link&&Rear->link->expon > e) {
Rear = Rear->link;
}
if (Rear->link&&Rear->link->expon == e) {
if (Rear->link->coef + c) {
Rear->link->coef += c;
}
else {
t = Rear->link;
Rear->link = t->link;
free(t);
}
}
else {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c; t->expon = e;
t->link = Rear->link;
Rear->link = t; Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
t2 = P; P = P->link; free(t2);
P = Combin(P);
return P;
}
//合并同类项
Polynomial Combin(Polynomial L) {
Polynomial Head = L;
Polynomial P;
Polynomial Pr = L;
if (!L) {
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = 0; P->expon = 0; P->link = NULL;
return L;
}
P = L->link;
while (Head) {
while (P) {
if (P->expon == Head->expon) {
Head->coef = Head->coef + P->coef;
if (Head->coef == 0) { Head->expon = 0; }
Pr->link = P->link; free(P); P = Pr->link;
}
else {
Pr = Pr->link; P = Pr->link;
}
}
Head = Head->link; Pr = Head;
if (Head)P = Head->link;
}
//L = Up(L);
return L;
}
//多项式每一项系数取相反数
Polynomial Rev(Polynomial P) {
Polynomial node = P;
if (!P) { return NULL; }
while (node) {
node->coef = -(node->coef);
node = node->link;
}
return P;
}
//降幂输出
void PrintDown(Polynomial P, int flag) {
if (flag == 0) { printf("结果如下(降幂):"); }
if (!P) { printf("0\n"); return; }
if (P->link) { PrintDown(P->link, 1); }
if (P->coef >= 0 && P->link != NULL) { printf("+"); }
if (P->coef == 0 || P->expon == 0) { printf("%d", P->coef); }
else { printf("%dx^%d", P->coef, P->expon); }
if (flag == 0) { printf("\n"); }
}
