一元稀疏多项式计算器

Question

题目：一元稀疏多项式计算器
设计任务：
设计一个一元稀疏多项式简单计算器。
设计要求：
一元稀疏多项式简单计算器的基本功能是：
(1)输入并建立多项式——creatpolyn()；
(2)输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数升序排列 ——printpolyn()；
(3)多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn()；
(4)多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn()。

上机用的
求各位高手帮忙做个，有注释最好了。
谢谢啦！！！！
要用C语言编 不要C++

Answer 1

一元稀疏多项式计算器设计程序代码
#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");
}本回答被提问者采纳