[데이터 구조 뇌 도 시리즈 02] 선형 구조

//        .cpp

//  ：
//	       ，                 ，                   ；
//	     ，                ，          ：  ，P1   ，P2   ；
//	                ，                           

#include

typedef struct PolyNode * PtrToPolyNode;
typedef struct PolyNode {
	int coef;
	int expo;
	PtrToPolyNode Next;
};
typedef PtrToPolyNode Polynomial;

//      ，  1，-1,0
int Compare(int e1, int e2) {
	if (e1 > e2) return 1;
	else if (e1 < e2) return -1;
	else return 0;
}

//                     ，                
void Attach(int coef, int expo, Polynomial * PtrRear) {
	Polynomial P;
	
	//     ，   
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->coef = coef;
	P->expo = expo;
	P->Next = NULL;

	// P                  ，         
	(*PtrRear)->Next = P;
	*PtrRear = P;
}

Polynomial PolyAdd(Polynomial P1, Polynomial P2) {
	Polynomial front, rear, tmp;
	int sum;
	//                   
	rear = (Polynomial)malloc(sizeof(struct PolyNode));
	//front            
	front = rear;
	while(P1&&P2)
		switch (Compare(P1->expo, P2->expo)) {
		case 1:
			Attach(P1->coef, P1->expo, &rear);
			P1 = P1->Next;
			break;
		case -1:
			Attach(P2->coef, P2->expo, &rear);
			P2 = P2->Next;
			break;
		case 0:
			sum = P1->coef + P2->coef;
			if (sum) Attach(sum, P1->expo, &rear);
			P1 = P1->Next;
			P2 = P2->Next;
			break;
		}
	//                            
	for (; P1; P1 = P1->Next) Attach(P1->coef, P1->expo, &rear);
	for (; P2; P2 = P2->Next) Attach(P2->coef, P2->expo, &rear);
	rear->Next = NULL;
	tmp = front;
	front = front->Next;
	free(tmp);
	return front;
}