数据结构 一元多项式

[c]代码库

//头文件
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//定义多项式的项
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->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;
		}
	}
}

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

void PrintPolyn(Polyn P){
	Polyn 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");
}


void PrintfPolyn(Polyn P){
	Polyn q=P->next; 
    int flag=1;//项数计数器
    if(!q)
	{ //若多项式为空，输出0
        putchar('0'); 
        printf("\n");
        return;
	}   
    while(q)
	{
		printf("%g,",q->coef);
        printf("%d,",q->expn);
        q=q->next; 
		flag++;
	}
}

int compare(Polyn a,Polyn 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多项式非空
}

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;
}



void main()
{
    int m,n,a,x;
	char flag;
    Polyn pa=0,pb=0,pc;

    printf("请输入a的项数:");
    scanf("%d",&m);
    pa=CreatPolyn(pa,m);//建立多项式a
    printf("请输入b的项数:");
    scanf("%d",&n);
    pb=CreatPolyn(pb,n);//建立多项式b

    //输出菜单
    printf("   *******************************\n");
	printf("   *       A:输出多项式a         *\n");
	printf("   *       B:输出多项式b         *\n");
	printf("   *       C:输出多项式整数序列a *\n");
	printf("   *       D:输出多项式整数序列b *\n");
	printf("   *       E:输出a+b             *\n");
	printf("   *       F:输出a-b             *\n");
    printf("   *******************************\n");

	while(a)
	{
        printf("\n请选择操作：");
        scanf(" %c",&flag);//空格符号一定要注意
		switch(flag)
		{

		    case'A':
				{
			        printf("\n       多项式a=");
			        PrintPolyn(pa);
			break;
				}
		case'B':
				{
				    printf("\n       多项式b=");
				    PrintPolyn(pb);
				    break;
				}
        case'C':
				{
				    printf("\n       多项式整数序列a=");
					printf("%d,",m);
				    PrintfPolyn(pa);
				    break;
				}
		case'D':
				{
				    printf("\n       多项式整数序列b=");
				    printf("%d,",n);
				    PrintfPolyn(pb);
				    break;
				}
		    case'E':
				{
				pc=AddPolyn(pa,pb);
                    printf("\n       a+b=");
				PrintPolyn(pc);
				    break;
				}
            case'F':
				{
				pc=SubtractPolyn(pa,pb);
                    printf("\n       a-b=");
				PrintPolyn(pc);
				break;
				}
            default:
				printf("\n    选择错误，请重新选择!\n");
		}
	}
}