一元稀疏多项式计算器

一元稀疏多项式计算器的课程设计（数据结构）~

//头文件#include#include#include//定义多项式的项typedef struct Polynomial{ float coef; int expn; struct Polynomial *next;}*Polyn,Polynomial;void Insert(Polyn p,Polyn h){ if(p->coef==0) free(p);//系数为0的话释放结点 else { Polyn q1,q2; q1=h; q2=h->next; while(q2&&p->expnexpn) {//查找插入位置 q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn) {//将指数相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef) {//系数为0的话释放结点 q1->next=q2->next; free(q2); } } else {//指数为新时将结点插入 p->next=q2; q1->next=p; } }}Polyn CreatePolyn(Polyn head,int m){ //建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;icoef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;}void DestroyPolyn(Polyn p){ //销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next) { free(q1); q1=q2; q2=q2->next; }}void PrintPolyn(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q) { //若多项式为空，输出0 putchar('0'); printf("
"); return; } while(q) { if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1) {//系数非1或-1的普通情况 printf("%g",q->coef); if(q->expn==1) putchar('X'); else if(q->expn) printf("X^%d",q->expn); } else { if(q->coef==1) { if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf("X^%d",q->expn); } if(q->coef==-1) { if(!q->expn) printf("-1"); else if(q->expn==1) printf("-X"); else printf("-X^%d",q->expn); } } q=q->next; flag++; } printf("
");}int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn) return 1; else if(!a||a->expnexpn) return -1; else return 0; } else if(!a&&b) return -1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空}Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb) { qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)){ case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;}Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式a-b，返回其头指针 Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) { //将pb的系数取反 p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1; return pd;}int ValuePolyn(Polyn head,int x){ //输入x值，计算并返回多项式的值 Polyn p; int i; int sum=0,t; for(p=head->next;p;p=p->next) { t=1; for(i=p->expn;i!=0;) { if(icoef*t; } return sum;}Polyn Derivative(Polyn head){ //求解并建立导函数多项式，并返回其头指针 Polyn q=head->next,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hd->next=NULL; while(q) { if(q->expn!=0) { //该项不是常数项时 p2=(Polyn)malloc(sizeof(struct Polynomial)); p2->coef=q->coef*q->expn; p2->expn=q->expn-1; p2->next=p1->next;//连接结点 p1->next=p2; p1=p2; } q=q->next; } return hd;}Polyn MultiplyPolyn(Polyn pa,Polyn pb){ //求解并建立多项式a*b，返回其头指针 Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf;}void main(){ int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; printf(" 欢迎使用多项式操作程序

"); printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);//建立多项式a printf("请输入b的项数:"); scanf("%d",&n); pb=CreatePolyn(pb,n);//建立多项式b //输出菜单 printf(" *******************************************************
"); printf(" * 多项式操作程序 *
"); printf(" * *
"); printf(" * A:输出多项式 B:输出多项式b *
"); printf(" * *
"); printf(" * C:输出a的导数 D:输出b的导数 *
"); printf(" * *
"); printf(" * E:代入x的值计算a F:代入x的值计算b *
"); printf(" * *
"); printf(" * G:输出a+b H:输出a-b *
"); printf(" * *
"); printf(" * I:输出a*b J:退出程序 *
"); printf(" * *
"); printf(" *******************************************************
"); while(a) { printf("
请选择操作："); scanf(" %c",&flag);//空格符号一定要注意 switch(flag) { case'A': case'a': { printf("
多项式a="); PrintPolyn(pa); break; } case'B': case'b': { printf("
多项式b="); PrintPolyn(pb); break; } case'C': case'c': { pc=Derivative(pa); printf("
多项式a的导函数为：a'="); PrintPolyn(pc); break; } case'D': case'd': { pc=Derivative(pb); printf("
多项式b的导函数为：b'="); PrintPolyn(pc); break; } case'E': case'e': { printf("输入x的值：x="); scanf("%d",&x); printf("
x=%d时，a=%d
",x,ValuePolyn(pa,x)); break; } case'F': case'f': { printf("输入x的值：x="); scanf("%d",&x); printf("
x=%d时，b=%d
",x,ValuePolyn(pb,x)); break; } case'G': case'g': { pc=AddPolyn(pa,pb); printf("
a+b="); PrintPolyn(pc); break; } case'H': case'h': { pc=SubtractPolyn(pa,pb); printf("
a-b="); PrintPolyn(pc); break; } case'I': case'i': { pc=MultiplyPolyn(pa,pb); printf("
a*b="); PrintPolyn(pc); break; } case'J': case'j': { printf("
感谢使用此程序！
"); DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; } default: printf("
您的选择错误，请重新选择!
"); } }}把楼上的回答用代码格式重新排版了一下，方便阅读

#include
#include
#include
#define N 40
typedef struct node{
int x,z;
struct node *next;
}*pnode;
int isnum(char c)
{
if(c>='0'&&c<='9') return 1;
else return 0;
}
pnode create(char *c,int i,int j)
{
if(j<i) return NULL;
int a=0,b=0,flag=0;
//处理系数。
if(!isnum(c[i])) a=1;
else
while(isnum(c[i])&&i<=j)
{
a=a*10+c[i]-'0';
i++;
}
//跳过系数与指数间非数字字符。
while(!isnum(c[i])&&i<=j)
{
flag=1;
i++;
}
//处理指数。
if(i>j&&flag==1) b=1;
else
{
if(c[i-1]=='-'&&c[i-2]=='^') flag=2;//指数是负数情况记录。
while(isnum(c[i])&&i<=j)
{
b=b*10+c[i]-'0';
i++;
}
}
if(flag==2) b=-b;//指数是负数情况处理。
pnode p;
p=(pnode)malloc(sizeof(node));
p->x=a;
p->z=b;
return p;
}//创建一个结点，表示多项式的一项。把"12X^3"这样字符串转化成一个只有系数、指数、后继的结构体。
pnode create_duo(char *c,int m)
{
if(c[m]=='\0') return NULL;
int i,j;
pnode p,q;
i=m;
if(c[i]=='+'||c[i]=='-')i++;
j=i;
while(c[j]!='\0'&&c[j]!='+'&&(c[j]!='-'||c[j-1]=='^'))
{
j++;
}//移动到多项式字符串的从下标m起第一项末。
if(c[i]!='0')
{
p=create(c,i,j-1);
if(i>0&&c[i-1]=='-') p->x=-(p->x);
q=create_duo(c,j);
p->next=q;
return p;
}
else
return create_duo(c,j); //系数为0项，不建立，跳过。
}//把一元多项式的字符串用链式存储。
pnode plus(pnode p,pnode q)
{
pnode P,H,t,m,n;
m=p;
n=q;
H=P=(pnode)malloc(sizeof(node));
while(m!=NULL&&n!=NULL)
{
t=(pnode)malloc(sizeof(node));
if(m->z>n->z)
{
t->x=m->x;
t->z=m->z;
m=m->next;
}
else
if(m->z==n->z)
{
if(m->x==-(n->x))
{
m=m->next;
n=n->next;
continue;
}//指数相同，系数相反，情况处理。
t->x=m->x+n->x;
t->z=n->z;
m=m->next;
n=n->next;
}
else
{
t->x=n->x;
t->z=n->z;
n=n->next;
}
P->next=t;
P=P->next;
}
while(m!=NULL)
{
t=(pnode)malloc(sizeof(node));
t->x=m->x;
t->z=m->z;
m=m->next;
P->next=t;
P=P->next;
}
while(n!=NULL)
{
t=(pnode)malloc(sizeof(node));
t->x=n->x;
t->z=n->z;
n=n->next;
P->next=t;
P=P->next;
}
P->next=NULL;
P=H;
H=H->next;
free(P);
return H;
}//两个一元多项式的相加。
pnode minus(pnode p,pnode q)
{
if(q==NULL) return p;
pnode t,h,g,q1;
t=q;
h=(pnode)malloc(sizeof(node));
h->x=-(t->x);
h->z=t->z;
t=t->next;
q1=h;
g=h;
while(t!=NULL)
{
h=(pnode)malloc(sizeof(node));
h->x=-(t->x);
h->z=t->z;
g->next=h;
g=g->next;
t=t->next;
}
g->next=NULL;
if(p==NULL) return q1;
return (plus(p,q1));
}//两个一元多项式的差。
pnode chen(pnode p,pnode q)
{
pnode k,h,t,g;
k=p;
t=(pnode)malloc(sizeof(node));
h=t;
h->x=(k->x)*(q->x);
h->z=k->z+q->z;
k=k->next;
g=h;
while(k!=NULL)
{
h=(pnode)malloc(sizeof(node));
h->x=(k->x)*(q->x);
h->z=k->z+q->z;
g->next=h;
g=g->next;
k=k->next;
}
g->next=NULL;
return t;
}//多项式中的一项与另一个多项式的乘。
pnode chenduo(pnode p1,pnode p2)
{
void free_pnode(pnode p);//释放一个链表空间。
if(p1==NULL||p2==NULL) return NULL;
pnode m,n,t,g;
n=p2;
t=NULL;
while(n!=NULL)
{
m=chen(p1,n);
g=plus(t,m);
free_pnode(m);
free_pnode(t);
t=g;
n=n->next;
}
return t;
}//两个多项式的乘。
void print(pnode p)
{
if(p==NULL)
{
cout<<"0"<<endl;
return;
}
while(p!=NULL)
{
if(p->x==-1&&p->z!=0)cout<<"-";
else if(p->x!=1||p->z==0)
coutx;
if(p->z)
{
cout<<"X";
if(p->z!=1)
coutz;
}
p=p->next;
if(p!=NULL&&p->x>0) cout<<"+";
}
cout<<endl;
}//输出链式存储多项式。
void main()
{
cout<<"****************************************************************************"<<endl;
cout<<"***********************一元多项式的计算(和差积)*****************************"<<endl;
cout<<"****************************************************************************"<<endl;
char ch1[N];//="30X^45-X-9";
char ch2[N];//="-4X^3-2X+1";
int n=1;
pnode p1,p2;
cout<<"输入第一个多项式(行式如.22X^31+X^22+X-1):
";
cin>>ch1;
p1=create_duo(ch1,0);
cout<<"输入第二个多项式(行式如.22X^31+X^24+X-1):
";
cin>>ch2;
p2=create_duo(ch2,0);
cout<<"多项式p1：";
print(p1);
cout<<"多项式p2：";
print(p2);
cout<<"******************************************"<<endl;
cout<<"********* 用 户 选 择 ************"<<endl;
cout<<"********* ************"<<endl;
cout<<"********* 1 . 两 多 项 式 和 ************"<<endl;
cout<<"********* ************"<<endl;
cout<<"********* 2 . 两 多 项 式 差 ************"<<endl;
cout<<"********* ************"<<endl;
cout<<"********* 3 . 两 多 项 式 积 ************"<<endl;
cout<<"********* ************"<<endl;
cout<<"********* 0 . 退 出 ************"<<endl;
cout<<"********* ************"<<endl;
cout<<"******************************************"<<endl;
while(n)
{ cout<<"请输入你的选择：";
cin>>n;
switch(n)
{
case 1:
cout<<"两多项式和(p1+p2)为：";
print(plus(p1,p2));
break;
case 2:
cout<<"两多项式差(p1-p2)为：";
print(minus(p1,p2));
break;
case 3:
cout<<"两多项式积(p1*p2)为：";
print(chenduo(p1,p2));
break;
default: cout<<" 错误选择！ "<<endl;
}
}
}

void free_pnode(pnode p)
{
pnode t;
while(p!=NULL)
{
t=p;
p=p->next;
free(t);
}
}
采纳吧，100%能用，我测试过了

一元稀疏多项式计算器设计程序代码
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#define maxlen 10
#define large 999

typedef struct Linklistomial{
float coef;
int expn;
struct Linklistomial *next;
}Linklistomial,*Linklist;

void Insert(Linklist p,Linklist h){
if(p->coef==0) free(p);//系数为0的话释放结点
else
{
Linklist q1,q2;
q1=h;
q2=h->next;
while(q2&&p->expn<q2->expn) { //查找插入位置
q1=q2;
q2=q2->next;
}
if(q2&&p->expn==q2->expn) { //将指数相同相合并
q2->coef+=p->coef;
free(p);
if(!q2->coef) {//系数为0的话释放结点
q1->next=q2->next;
free(q2);
}
}
else { //指数为新时将结点插入
p->next=q2;
q1->next=p; }
}
}

Linklist CreateLinklist(Linklist head,int m){
//建立一个头指针为head、项数为m的一元多项式
int i;
Linklist p;
p=head=(Linklist)malloc(sizeof(struct Linklistomial));
head->next=NULL;
for(i=0;i<m;i++) {
p=(Linklist)malloc(sizeof(struct Linklistomial));//建立新结点以接收数据
printf("请输入第%d项的系数与指数:",i+1);
scanf("%f %d",&p->coef,&p->expn);
Insert(p,head); //调用Insert函数插入结点
}
return head;
}

void DestroyLinklist(Linklist p){ //销毁多项式p
Linklist q1,q2;
q1=p->next; q2=q1->next;
while(q1->next) {
free(q1);
q1=q2;
q2=q2->next; }
}

void PrintLinklist(Linklist P){
Linklist q=P->next;
int flag=1; //项数计数器
if(!q) { //若多项式为空，输出0
putchar('0');
printf("\n");
return;
}
while(q)
{
if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项
if(q->coef!=1&&q->coef!=-1) { //系数非1或-1的普通情况
printf("%g",q->coef);
if(q->expn==1) putchar('X');
else if(q->expn) printf("X^%d",q->expn);
}
else {
if(q->coef==1)
{
if(!q->expn) putchar('1');
else if(q->expn==1) putchar('X');
else printf("X^%d",q->expn);
}
if(q->coef==-1)
{
if(!q->expn) printf("-1");
else if(q->expn==1) printf("-X");
else printf("-X^%d",q->expn);
}
}
q=q->next;
flag++;
}
printf("\n");
}

int compare(Linklist a,Linklist b){
if(a&&b)
{ if(!b||a->expn>b->expn) return 1;
else if(!a||a->expn<b->expn) return -1;
else return 0;
}
else if(!a&&b) return -1;//a多项式已空，但b多项式非空
else return 1;//b多项式已空，但a多项式非空
}

Linklist AddLinklist(Linklist pa,Linklist pb){//求解并建立多项式a+b，返回其头指针
Linklist qa=pa->next;
Linklist qb=pb->next;
Linklist headc,hc,qc;
hc=(Linklist)malloc(sizeof(struct Linklistomial));//建立头结点
hc->next=NULL;
headc=hc;
while(qa||qb)
{
qc=(Linklist)malloc(sizeof(struct Linklistomial));
switch(compare(qa,qb)){
case 1: {
qc->coef=qa->coef;
qc->expn=qa->expn;
qa=qa->next;
break; }
case 0: {
qc->coef=qa->coef+qb->coef;
qc->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case -1: {
qc->coef=qb->coef;
qc->expn=qb->expn;
qb=qb->next;
break; }
}
if(qc->coef!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else free(qc);//当相加系数为0时，释放该结点
}
return headc;
}

int ValueLinklist(Linklist head,int x){
//输入x值，计算并返回多项式的值
Linklist p;
int i;
int sum=0,t;
for(p=head->next;p;p=p->next)
{
t=1;
for(i=p->expn;i!=0;)
{
if(i<0){t/=x;i++;}//指数小于0，进行除法
else{t*=x;i--;}//指数大于0，进行乘法
}
sum+=p->coef*t;
}
return sum;
}

void xiang()
{ int m,n,a,x;
char flag;
Linklist pa=0,pb=0,pc;
printf(" 欢迎使用多项式操作程序\n\n");
printf("请输入a的项数:");
scanf("%d",&m);
pa=CreateLinklist(pa,m);//建立多项式a
printf("请输入b的项数:");
scanf("%d",&n);
pb=CreateLinklist(pb,n);//建立多项式
//输出菜单
printf(" *******************************************************\n");
printf(" * 多项式操作程序 *\n");
printf(" * *\n");
printf(" * A:输出多项式a B:输出多项式b *\n");
printf(" * *\n");
printf(" * C: 输出a+b D:带入x的值计算a+b *\n");
printf(" * *\n");
printf(" * E:代入x的值计算a F:代入x的值计算b *\n");
printf(" * *\n");
printf(" * G: 返回主菜单 *\n");
printf(" * *\n");
printf(" *******************************************************\n");

while(a)
{
printf("\n请选择操作：");
scanf(" %c",&flag);//空格符号一定要注意
switch(flag)
{ case'A':
case'a': {
printf("\n 多项式a=");
PrintLinklist(pa);
break; }
case'B':
case'b': {
printf("\n 多项式b=");
PrintLinklist(pb);
break; }
case'C':
case'c': {
pc=AddLinklist(pa,pb);
printf("\n a+b=");
PrintLinklist(pc);
break;
}
case'D':
case'd': { pc=AddLinklist(pa,pb);
printf("输入x的值：x=");
scanf("%d",&x);
printf("\n x=%d时，a+b=%d\n",x,ValueLinklist(pc,x));
break;
}

case'E':
case'e': {
printf("输入x的值：x=");
scanf("%d",&x);
printf("\n x=%d时，a=%d\n",x,ValueLinklist(pa,x));
break;
}
case'F':
case'f': {
printf("输入x的值：x=");
scanf("%d",&x);
printf("\n x=%d时，b=%d\n",x,ValueLinklist(pb,x));
break;
}

case'G':
case'g': {
DestroyLinklist(pa);
DestroyLinklist(pb);
a=0;
break; }
default:
printf("\n 您的选择错误，请重新选择!\n");
}
}
}

typedef struct{
int a[maxlen],b[maxlen],h[maxlen];
char vexs[maxlen];
int n,arcnum;
int kind;
int edges[maxlen][maxlen];
}MGraph;

int cnull=-1;

MGraph createMG(MGraph g){
int i,j;
for(i=0;i<g.arcnum;i++)
for(j=0;j<g.arcnum;j++)
g.edges[i][j]=0;
return g;
}

MGraph create(MGraph g){
int k;
for(k=1;k<=g.arcnum;k++){
g.edges[g.a[k]][g.b[k]]=g.h[k];
g.edges[g.b[k]][g.a[k]]=g.h[k];
}
return g;
}

struct{
int vex;
int lowcost;
}closedge[maxlen];

void minispantree_prim(MGraph mg,int I){
int i,j,k,m,min;
for(j=1;j<=mg.n;j++){
if(j!=I){
closedge[j].vex=I;
closedge[j].lowcost=mg.edges[j][I];
}
}
closedge[I].lowcost=0;
for(j=1;j<mg.n;j++){
printf("最经济的架设方法是：编号");
for(i=1;i<mg.n;i++){
min=100;
k=i;
for(j=1;j<=mg.n;j++)
if(closedge[j].lowcost<min&&closedge[j].vex!=0&&closedge[j].lowcost!=0)
{
min=closedge[j].lowcost;k=j;
}

printf("(%d,%d)",closedge[k].vex,k); //打印边
closedge[k].lowcost=0; //将顶点k加入U

for(m=1;m<=mg.n;m++){ //重新调整closedge数组
if(mg.edges[k][m]<closedge[m].lowcost&&m!=k){
closedge[m].lowcost=mg.edges[k][m];closedge[m].vex=k;
}
}
}
}
printf("的城市相连");
}
void shu()
{printf(" 利用普里姆算法求图的最小生成树\n");
MGraph g;
int i,j,k,h;
printf("请输入城市（顶点数）网络（边）数:");scanf("%d%d",&i,&j);
g.n=i;g.arcnum=j;
for(i=0;i<g.n;i++){
printf("第%d座城市的名称:",i+1);scanf("%s",&g.vexs[i]);
}
for(k=1;k<=g.arcnum;k++){
label:
printf("第%d条网络的两座城市的编号:",k);
scanf("%d %d",&i,&j);g.a[k]=i;g.b[k]=j;
while(i<1||i>g.n||j<1||j>g.n){
printf("编号超出范围,重新输入");
goto label;
}
printf("\t该网络（边）的权值:");scanf("%d",&h);
g.h[k]=h;
}

g=createMG(g);
g=create(g);
printf("\n");
minispantree_prim(g,1);
printf("\n 输入任何键返回主菜单!");
}

void menu(){
printf(" welcome to our system\n");
printf(" **************************************************\n");
printf(" * 1.一元多项式加法器 *\n");
printf(" * 2.n个城市之间最经济的网络架设方法 *\n");
printf(" * 3.exit *\n");
printf(" **************************************************\n");
}

int main(){
int choice;
menu();
printf(" please make your choice:");
scanf("%d",&choice);
while(choice!=3)
{
switch(choice){
case 1:system("cls");xiang();getch();break;
case 2:system("cls");shu();getch();getch();break;
default:printf(" please chooose the right choice!");getch();getch();break;
}
system("cls");
menu();
printf(" please make your choice:");
scanf("%d",&choice);
}
printf(" 谢谢使用该程序!\n");
}

---

一元稀疏多项式计算器视频