用連結清單實作一進制稀疏多項式的相加

        由于一進制多項式包含系數項和指數項，其系數為float型，指數項為int型，往往将其兩項組合成為一個結構元素類型，将多項式看成是一個有序表，則多項式定義中的各個操作均可利用有序表操作來完成。

       “建立多項式算法”操作結果：輸入m項的系數和指數，建立一進制多項式P；

       “銷毀多項式算法”初始條件：一進制多項式p已存在；

                                 操作結果：銷毀一進制多項式

        “輸出多項式算法”初始條件：一進制多項式p已存在；

                                   操作結果：列印一進制多項式p；

       “多項式加法算法”初始條件：兩個多項式的Pa,Pb已存在；

                                 操作結果：pa=pa+pb，并銷毀pb；

# include<stdio.h>
# include<malloc.h>

typedef struct{
	float coef;  //系數
	int expn;    //指數
}ElemType;

typedef struct LNode{  //結點類型
	ElemType data;
	struct LNode *next;
}*LinkList;

void MakeNode(LinkList &s,ElemType e){
	//生成結點
	s=(LinkList)malloc(sizeof(LNode));
	s->data=e;
}

void InsAfter(LinkList p,LinkList s){
	//插入結點
	s->next=p->next;p->next=s;
}

int compare(ElemType e1,ElemType e2){
	//比較
	if(e1.expn>e2.expn)
		return 1;
	else if(e1.expn<e2.expn)
		return -1;
	return 0;
}

void OrderInsert(LinkList &L,ElemType e,int(*compare)(ElemType,ElemType)){
	//有序插入
	LinkList p=L,q=p->next,s;
	while(q){
		int n=compare(e,q->data);
		if(n<0){  
			MakeNode(s,e);
			InsAfter(p,s);return;
		}
		else if(n==0)  break;
		p=p->next;q=p->next;
	}
	MakeNode(s,e);InsAfter(p,s); //最大，放在最後一個位置
}

void InitList(LinkList &L){
	//初始化
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
}

void SetCurElem(LinkList &p,ElemType e){ //設定結點
	p->data.coef=e.coef;
	p->data.expn=e.expn;
}

void CreatePolyn(LinkList &L,int m){
	InitList(L);ElemType e;e.coef=0.0;e.expn=-1;
	SetCurElem(L,e);//設定頭結點的資料元素
	for(int i=1;i<=m;i++){
		scanf("%f%d",&e.coef,&e.expn);  //輸入值
		OrderInsert(L,e,compare);
	}
}

void show(LinkList L){
	//輸出方法
	LinkList p=L->next;
	if(p){ //第一個輸出
		printf("%f^%d",p->data.coef,p->data.expn);
		p=p->next;
	}
	while(p){
		if(p->data.coef>0)
			printf("+");
		printf("%f^%d",p->data.coef,p->data.expn);
		p=p->next;
	}
	printf("/n");
}

void ListDestroy(LinkList &L){
	//銷毀
	LinkList p=L,q;
	while(p){
		q=p;
		p=p->next;
		free(q);
	}
}


void Add(LinkList &L1,LinkList &L2){
	//多項式相加
	LinkList p1=L1->next,p2=L2->next,r1=L1,q;//r1始終指向連結清單的尾部,p1和p2表示目前結點
	while(p1&&p2){
		int n=compare(p1->data,p2->data);
		switch(n){
		case -1:{r1->next=p1;r1=p1;p1=p1->next;break;} //L1中的值小，插入之
		case 1:{r1->next=p2;r1=p2;p2=p2->next;break;}   //L2中的值小，插入之
		case 0:{    //相同
			    float sum=p1->data.coef+p2->data.coef;
				if(sum==0){q=p1;p1=p1->next;free(q);} //删除L1中的
		    	else{p1->data.coef=sum;  //插入L1中的
		         	r1->next=p1;r1=p1;p1=p1->next;}
				q=p2;p2=p2->next;free(q);  //統一删除L2中的
			   }
		}
	}
		if(p1)
			r1->next=p1;  //添加L1
		else
			r1->next=p2;  //添加L2
		free(L2);L2=q=NULL;p1=p2=r1=NULL;
}

           

# include"cf.h"
void main(){
	LinkList L1,L2;
	CreatePolyn(L1,4);
	show(L1);
        CreatePolyn(L2,3);
	show(L2);
	Add(L1,L2);
	show(L1);
}
           

輸入一進制多項式L1（4），L2（3）

輸出L1+L2