数据结构：(单链表应用)多项式表示及多项式相加(2019.2.25和2.26)

/*
问题：求两个多项式的和
要求：利用链表存储多项式各项的系数和指数，再实现对两个多项式的求和 
*/ 

/*
2019.2.25  7:00-8:10
2019.2.26  6:40-7:15 
           7:25-8:00
*/

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

#define  MAX    20 

typedef struct node{
	float coef;
	int exp;
}PolyArray[MAX];    //结构体数组，用来输入多项式的数据
//关于这个结构的一个解释 https://blog.****.net/hhhhhyyyyy8/article/details/80923585
 
typedef struct pnode{
	float coef;
	int exp;
	struct pnode *next;   //pnode *next;错误 
}PolyNode;         //一个结构体结点PolyNode来代表多项式中的每一项 


void createPoly(PolyNode **pa, PolyArray a, int n);  //用多项式数组创建多项式链表 
void printPoly(PolyNode *head);  //输出多项式
void initPoly(PolyNode **pa);   //初始化链表，构造一个头结点为c做准备 
void addPoly(PolyNode *a, PolyNode *b, PolyNode *c);  //多项式相加

 
void addPoly(PolyNode *a, PolyNode *b, PolyNode *c){
/*
1.对于某一项如果a有，b没有，把a中的这个节点插入c中
2.对于某一项如果b有，a没有，把b中的这个节点插入c中 
3.对于某一项如果a和b都有，则将系数相加。如果相加后的和为0，则跳过 
*/

	
	PolyNode *pa = a->next;   //指向第一个有效结点 
	PolyNode *pb = b->next;
	PolyNode *pc = c;    //*pc = c->next;  如果这样写的话，则c为空，就跟这个头结点没有半毛钱关系了
	PolyNode *p;     //开辟新结点 
	float sum = 0;
	
	//printf("*\n");
	while(pa!=NULL && pb!=NULL){
		//printf("**\n");
		if(pa->exp > pb->exp){
			//本来想的是把a、b中的结点直接链接到c中，结果发现不行 
			p = (PolyNode *)malloc(sizeof(PolyNode));
			p->coef = pb->coef; 
			p->exp = pb->exp;
			p->next = NULL;
			
			pc->next = p;
			pc = p; 
			
			pb = pb->next;   //因为a没有变化，b已经遍历了一个元素，所以b要往后走一个 
			
		}else if(pa->exp < pb->exp){
			//printf("***\n");
			p = (PolyNode *)malloc(sizeof(PolyNode));
			p->coef = pa->coef; 
			p->exp = pa->exp;
			p->next = NULL;
			//printf("****\n");
			pc->next = p;
			pc = p; 
			
			pa = pa->next;   //因为a没有变化，b已经遍历了一个元素，所以b要往后走一个
			//printf("*****\n"); 
			//printPoly(c);
		}else{
			sum = pa->coef + pb->coef;
			
			if(sum){
				p = (PolyNode *)malloc(sizeof(PolyNode));
				p->coef = sum; 
				p->exp = pa->exp;
				p->next = NULL;
			
				pc->next = p;
				pc = p; 
							
			}
			pa = pa->next;   //因为a没有变化，b已经遍历了一个元素，所以b要往后走一个 
			pb = pb->next;
						
		}
	}
	
/*这段是自己理解的，答案有一个更精妙的写法	
	while(pa!=NULL){
		p = (PolyNode *)malloc(sizeof(PolyNode));
		p->coef = pa->coef; 
		p->exp = pa->exp;
		p->next = NULL;
			
		pc->next = p;
		pc = p; 
			
		pa = pa->next;   //因为a没有变化，b已经遍历了一个元素，所以b要往后走一个 		
	}
	
	while(pb!=NULL){
		p = (PolyNode *)malloc(sizeof(PolyNode));
		p->coef = pb->coef; 
		p->exp = pb->exp;
		p->next = NULL;
			
		pc->next = p;
		pc = p; 
			
		pb = pb->next;   //因为a没有变化，b已经遍历了一个元素，所以b要往后走一个 		
		
	}
*/

//这段是答案的  
//这就是所谓的代码优化，因为pa和pb中只有一个为0 
	if(pb!=NULL){
		pa = pb;
	} 
	
	while(pa!=NULL){
		p = (PolyNode *)malloc(sizeof(PolyNode));
		p->coef = pa->coef; 
		p->exp = pa->exp;
		p->next = NULL;
			
		pc->next = p;
		pc = p; 
			
		pa = pa->next;   //因为a没有变化，b已经遍历了一个元素，所以b要往后走一个 		
	}

} 


void initPoly(PolyNode **pa){
	//这一段是我自己加的，答案上没有 
	if(*pa != NULL){   //if(*pa == NULL){  写错了 
		return ;
	}
	
	*pa = (PolyNode *)malloc(sizeof(PolyNode));
	(*pa)->next = NULL;
} 



//输出多项式
/*
//答案只是把这个项输出来了 
void printPoly(PolyNode *head){
	PolyNode *p;
	
	p = head->next;  //p指向第一个有效结点
	while(p != NULL){
		printf("%.1fx^%d  ", p->coef, p->exp);
		p = p->next;
	} 
	printf("\n");
} 
*/

//自己想写成一个真正多项式的样子，即把加减号也输出 
void printPoly(PolyNode *head){
	PolyNode *p;
	
	p = head->next;  //p指向第一个有效结点
	while(p != NULL){
		if(p->coef > 0 && p != head->next){
			printf("+%.1fx^%d", p->coef, p->exp);
		}else{
			printf("%.1fx^%d", p->coef, p->exp);	
		} 
		
		p = p->next;
	} 
	printf("\n");
} 



//用多项式数组创建多项式链表 
void createPoly(PolyNode **pa, PolyArray a, int n){
	PolyNode *head;
	PolyNode *p,*q;  //p指向新结点，q始终指向链表末端 
	int i;
	
	//创建头结点 
	head = (PolyNode *)malloc(sizeof(PolyNode));
	head->next = NULL;
	
	//构造链表
	q = head;
	
	for(i = 0; i < n; i++){
		p = (PolyNode *)malloc(sizeof(PolyNode));
		p->coef = a[i].coef;
		p->exp = a[i].exp;
		
		q->next = p;
		q = p;
	}
	q->next = NULL;
	
	*pa = head;	
}
 
void main(void){
	PolyNode *pa = NULL;
	PolyNode *pb = NULL;
	PolyNode *pc = NULL;
	PolyArray a = {{7, 0}, {3, 1}, {9, 8}, {5, 16}};
	PolyArray b = {{8, 1}, {22, 7}, {-9, 8}};
	
	createPoly(&pa, a, 4);  //这种形式的话，是将构造好的链表在函数内部传给pa 
	//pa = createPoly(a, 4); 这种形式的话，是在编写函数时将构造好的链表传出来 
	createPoly(&pb, b, 3);
	initPoly(&pc);
	
	printf("多项式a为："); 
	printPoly(pa);
	printf("多项式b为："); 
	printPoly(pb);
	printf("多项式c为："); 
	printPoly(pc);
	
	addPoly(pa, pb, pc);
	printf("相加后多项式c为："); 
	printPoly(pc);
	
}