数据结构：多项式链表的操作

 包括对链表的冒泡排序，归并排序，链表的释放

#include "stdio.h"typedef struct Elem
{double coeff;double exp;
}Pair;typedef struct  poly
{Pair data;struct  poly  *next;
}*pPolyList,PolyList;//比较两个数的大小，按结果返回
int cmp(double a,double b)
{if(a > b )return 1;else if(a==b)return 0;return -1;
}//初始化多项式链表，按组输入，直到输入的为两个 0 0 表示链接结束
void Init_Poly( pPolyList* ha)
{double coeff;double exp;pPolyList  pa;coeff=0;exp=0;(*ha)=(pPolyList)malloc( sizeof(struct  poly) );memset(*ha,0,sizeof(PolyList));(*ha)->next=NULL;while(1){scanf("%lf %lf",&coeff,&exp);if(coeff ==0.0 && exp==0.0)break;pa=(pPolyList)malloc(sizeof(struct poly));(pa->data).coeff=coeff;(pa->data).exp = exp;pa->next=(*ha)->next;(*ha)->next=pa;}
}//打印多项式链表
void Print_List(pPolyList ha)
{pPolyList pa;pa=ha;if(!ha || !ha->next )return;if(ha->data.coeff==0.0)pa=ha->next;printf(" \n");while(pa){printf("%0.2lfX%0.2lf  ",pa->data.coeff,pa->data.exp);pa=pa->next;}}//释放多项式链表
void FreeList(pPolyList* ha)
{pPolyList pa,t;pa=*ha;if(!pa)return;t=pa;do{t=pa;pa=pa->next;free(t);}while(pa);*ha=NULL;t=NULL;
}//将两个多项式链表（已经排序），归并排序void MergeList(pPolyList ha,pPolyList hb,pPolyList* hc)
{pPolyList pa,pb,pc;*hc=(pPolyList)malloc(sizeof(PolyList));memset((*hc),0,sizeof(PolyList));pa=ha->next;pb=hb->next;pc=*hc;while(pa && pb){if( pa->data.exp < pb->data.exp ){pc->next=pa;pa=pa->next;}else{pc->next=pb;pb=pb->next;}pc=pc->next;}pc->next=pa ? pa:pb;
}//将多项式链表按照指数的大小排序
void Sort_List(pPolyList ha)
{pPolyList t,p,middle;middle=NULL;p=ha;if(!ha || !ha->next)return;while(ha->next->next != middle){t=ha;p=t->next;while(1){if(t->next->data.exp > p->next->data.exp ){t->next=p->next;p->next=t->next->next;t->next->next=p;}else{p=p->next;}t=t->next;if( (p->next) == middle ){middle=p;break;}}}
}//两多项式相加，
void Add_Polynomial(pPolyList ha,pPolyList hb)
{pPolyList pa,pb,qa,qb,t;int flag;double sum;pa=ha;		//pa为得到的相加之后的链表的游标pb=hb;qa=ha->next;qb=hb->next;while( qa && qb )//开始的时候qa，qb分别指向ha，hb的两个链表的第一个数据元素，{//比较两个系数的大小，进行不同的操作switch( cmp(qa->data.exp,qb->data.exp) ){case -1:pa->next=qa;qa=qa->next;pa=pa->next;break;case 0:sum=qa->data.coeff+qb->data.coeff;if( 0.0 != sum){pa->next=qa;pa->next->data.coeff=sum;qa=qa->next;pa=pa->next;	//系数相同，将系数放到qa上，删除当前qb节点t=qb->next;free(qb);qb=t;		}else	//如果两个指数相同，且系数加起来为0，那么就的删除两个节点{  t=qa->next;free(qa);qa=t;t=qb->next;free(qb);qb=t;			 }break;case 1:pa->next=qb;qb=qb->next;pa=pa->next;break;}//switch}//whilepa->next=qb?qb:NULL;
}void main()
{    pPolyList hc=NULL;pPolyList ha=NULL;pPolyList hb=NULL;Init_Poly(&ha);		//初始化两个链表Init_Poly(&hb);Print_List(ha);	Print_List(hb);Sort_List(ha);		//对两个链表排序Sort_List(hb);Print_List(ha);		//打印排序后的两个多项式链表Print_List(hb);//MergeList(ha,hb,&hc);	//对两个Add_Polynomial(ha,hb);Print_List(ha);FreeList(&ha);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！