数据结构算法题，谁能帮我写一下程序呀！感谢！

Question

一元多项式的计算。
任务：能够按照指数将序排列建立并输出多项式；能够完成两个多项式的相加、想减并将结果输入。

Answer 1

//函数功能有，求多项式的和，差，积
/*
输入函数的输入操作：1，先输入多项式的成员的个数n：（如 x+1,的n=2）;
2，输入多项式（x+1），格式如下：
coef expn
1 1
1 0
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct {
float coef;
int expn;
}Elemtype;
typedef struct node{
Elemtype data;
node *next;
}LNode,*Linklist;

Linklist creat(int n); //创建n各节点，并初始化
void print(Linklist head);//输出
Linklist Add(Linklist f1,Linklist f2); //f1+f2
Linklist sub(Linklist f1,Linklist f2); //f1-f2
Linklist mult(Linklist f1,Linklist f2); //f1*f2
Linklist turn(Linklist head); //排序，合并同类项
int len(Linklist head); //求多项式的长度
void main()
{
Linklist f1,f2,f4,f3;
printf(" Polyn + - *\n");

printf("Input polyn \nPolyn f1 input data n:");
int n;scanf("%d",&n);
f1=creat(n);

printf("Polyn f2 input data n:");
scanf("%d",&n);
f2=creat(n);

printf("\nOUT Polyn;\n");
printf("polyn1:"); print(f1);
printf("polyn2:"); print(f2);

f3=Add(f1,f2); printf("polyn Add f1+f2:"); print(f3);
f4=sub(f1,f2); printf("polyn sub f1-f2"); print(f4);

printf("polyn mult f1*f2:"); print(mult(f1,f2));
}

Linklist turn(Linklist head)
{
Linklist p, q;
if(!head->next) return head;
Elemtype temp;
for (q=head;q->next;q=q->next)
{
for (p=q->next;p;p=p->next)
{
if(p->data.expn>q->data.expn)
{
temp=p->data;p->data=q->data;q->data=temp;
}
else if(p->data.expn==q->data.expn) {
q->data.coef=q->data.coef+p->data.coef;p=p->next;
q->next=p; if(!p||!p->next) break;
}
}
if((q==NULL)||(q->next==NULL)) break;
}
return head;
}

Linklist creat(int n)
{
Linklist head,p,pf;
printf("input %d data :\n coef expn\n",n);
for(int i=0;i<n;i++)
{
pf=(Linklist)malloc(sizeof(LNode));
if(i==0)
head=p=pf;
printf("NO %d : ",i+1);
scanf("%f%d",&pf->data.coef,&pf->data.expn);
if(pf->data.coef) {p->next=pf;
p=p->next;}
}
p->next=NULL;
head=turn(head);
return head;
}

void print(Linklist head)
{
Linklist p;
p=head;
printf("\n coef expn\n");
while(p){
printf(" %6.2f %4d\n",p->data.coef,p->data.expn);
p=p->next;
}
printf("\n");
}
int len(Linklist head)
{
Linklist p;
p=head;
int n;
for(n=0;p;p=p->next,n++);
return n;
}
Linklist Add(Linklist f1,Linklist f2) //f1+f2
{
Linklist p1,p2,f;
Linklist p,pf;
p1=f1; p2=f2;
p=f=(Linklist)malloc(sizeof(LNode));f->next=NULL;
while (p1||p2)
{
pf=(Linklist)malloc(sizeof(LNode));
if(p1&&(p2==NULL))
{
pf->data=p1->data;
p1=p1->next;
}
else if(p2&&(p1==NULL)){
pf->data=p2->data;
p2=p2->next;
}
else if(p1->data.expn-p2->data.expn==0)
{
pf->data.coef=p1->data.coef+p2->data.coef;
pf->data.expn=p1->data.expn;
p1=p1->next;p2=p2->next;
}
else if(p1->data.expn>p2->data.expn)
{
pf->data=p1->data;
p1=p1->next;
}
else if(p1->data.expn<p2->data.expn){
pf->data=p2->data;
p2=p2->next;
}
if(pf->data.coef) //如果系数coef==0 则删除该项成员
{p->next=pf;
p=p->next;}
}
p->next=NULL;f=f->next; f=turn(f);
return f;
}

Linklist sub(Linklist f1,Linklist f2) //f1-f2
{
Linklist p1,p2,f;
Linklist p,pf;
p1=f1; p2=f2;
p=f=(Linklist)malloc(sizeof(LNode));f->next=NULL;
while (p1||p2)
{
pf=(Linklist)malloc(sizeof(LNode));
if(p1&&(p2==NULL))
{
pf->data=p1->data;
p1=p1->next;
}
else if(p2&&(p1==NULL)){
pf->data.expn=p2->data.expn;
pf->data.coef=-p2->data.coef;
p2=p2->next;
}
else if(p1->data.expn-p2->data.expn==0)
{
pf->data.coef=p1->data.coef-p2->data.coef;
pf->data.expn=p1->data.expn;
p1=p1->next;p2=p2->next;
}
else if(p1->data.expn>p2->data.expn)
{
pf->data=p1->data;
p1=p1->next;
}
else if(p1->data.expn<p2->data.expn){
pf->data.expn=p2->data.expn;
pf->data.coef=-(p2->data.coef);
p2=p2->next;
}
if(pf->data.coef)
{p->next=pf;
p=p->next;}
}
p->next=NULL;f=f->next; f=turn(f);
return f;
}
Linklist mult(Linklist f1,Linklist f2) //f1*f2
{
Linklist p1,p2,f;
Linklist pf;f=NULL;
for(p1=f1;p1;p1=p1->next)
{
for(p2=f2;p2;p2=p2->next)
{
pf=(Linklist)malloc(sizeof(LNode));
pf->data.expn=p1->data.expn+p2->data.expn;
pf->data.coef=p1->data.coef*p2->data.coef;
pf->next=NULL;
f=Add(f,pf);
pf=NULL;
}
}
f=turn(f);
return f;
}

Answer 2

设计一个数据结构元，将某一项的系数和指数当成属性：
typedef struct dataElem{
int coefficient;//系数
int exponent;//指数
} Elem; //代表多项式中的一项
如果你用c++的话可以用vector来存多项式，如果是c的话，就只有自己建动态链表了。
------------------------
对于任务一：
重要将动态vector中的项按照Elem.exponent的顺序排列一下，然后输出各项即可。
对于任务二：
只要将两个vector中，指数相同的项的系数部分相加/相减即可完成多项式相加减的功能。

Answer 3

typedef struct Node *PtrToNode;
struct Node {
int Coefficient;
int Exponent;
PtrToNode Next;
};
typedef PtrToNode Polynomial;
/* Nodes are sorted in decreasing order of exponents.*/
Polynomial Add( Polynomial a, Polynomial b )
{ /* return a polynomial which is the sum of a and b*/
/*use linked list with a head node */
PtrToNode front, tail;
int sum;
/* create a head node */
tail = malloc(sizeof(Node));
if ( tail ==Null)
FatalError( "The memory is full");
front = tail; front->Exponent=-1;
a=a->Next; b=b->Next;
while ( a && b )
switch ( COMPARE(a-> Exponent, b-> Exponent) ) {
case -1: Attach(b-> Coefficient, b-> Exponent, &tail);
b = b-> Next;
break;
case 0: sum = a-> Coefficient + b-> Coefficient;
if ( sum ) Attach(sum, a-> Exponent, &tail);
a = a-> Next; b = b-> Next;
break;
case 1: Attach(a-> Coefficient, a-> Exponent, &tail);
a = a-> Next;
break;
}
/* copy rest of list a and then list b */
for ( ; a; a = a-> Next ) Attach(a-> Coefficient, a-> Exponent, &tail);
for ( ; b; b = b-> Next ) Attach(b-> Coefficient, b-> Exponent, &tail);
tail->Next = NULL;
return front;
}

void Attach( int coefficient, int exponent, PtrToNode *ptr )
{ /* create a new node, attach it to the node pointed by ptr.*/
/* ptr is updated to this new node */
PtrToNode temp;
temp = malloc(sizeof(Node)); /* Do not destroy the input !!!*/
if ( temp==Null )
FatalError(“The memory is full");
temp-> Coefficient = coefficient;
temp-> Exponent = exponent;
temp-> Next = NULL;
(*ptr)->Next = temp; /* attach */
*ptr = temp; /* update */
}

Time complexity O(m + n), or O(max(m, n))
Note:
1. An algorithm with time complexity O(m*n) is NOT acceptable.
2. Using a linked list to store all the terms as in the array representation just doesn’t make sense.
该程序基于C语言编写
相减就是加上相反数，自己根据加法写下不麻烦的。