C 알고리즘 과 데이터 구조 - 선형 표 의 응용, 다항식 구 화 - ShinePans

/*---      ,     ---*/
/*---By    ---*/
/*---  : 2014-5-8 . ---*/
/*---  :---*/
//          A B,          
//1.        A B;
//2.           C;
//3.           D;
//  4    A,B,C,D;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
	float A;   //  
	int m;     //  
	struct Node *next;
}LNode, *LinkList;   //    ,           ->        


void Initialize(LNode *plist);
LinkList PolyAdd(LNode *plist1, LNode *plist2);
int Cmp(int a, int b);
void Append(LNode *pa, LNode *pb);
int ListIsEmpty(const LinkList *plist);
void EmptyTheList(LNode *plist);
void PrintList(LNode *plist);
void PolySort(LNode *plist);
int GetLength(LNode *plist);
void PolyMerge(LNode *plist);
float HornorEvaluate(LNode *plist, float x);
LinkList PolyMultiply(LNode *plist1, LNode *plist2);
int GetMaxExpn(LNode *plist);

/**
*   
*/
int main(void)
{
	LNode *p1 = (LNode*)malloc(sizeof(LNode));
	LNode *p2 = (LNode*)malloc(sizeof(LNode));
	LNode *result1 = (LNode*)malloc(sizeof(LNode));
	LNode *result2 = (LNode*)malloc(sizeof(LNode));

	Initialize(p1);
	Initialize(p2);

	PolySort(p1);     //     
	PolySort(p2);

	printf("
p1 = ");
	PrintList(p1);
	printf("
p1(value) = %f", HornorEvaluate(p1, 2));

	printf("
p2 = ");
	PrintList(p2);
	printf("
p2(value) = %f", HornorEvaluate(p2, 2));


	result1 = PolyAdd(p1, p2);
	result2 = PolyMultiply(p1, p2);
	//printf("
%d",GetLength(p1));
	//PolyMerge(p1);      //     
	//UnitePoly(p1);   //     
	//EmptyTheList(p1);

	printf("
p1 + p2 = ");
	PrintList(result1);
	printf("
p1 * p2 = ");
	PrintList(result2);
	getchar();
	getchar();
	return 0;
}





/**
*Operation:         
*Precondition:
*Postcondition:
*/
void Initialize(LNode *plist)
{
	int i, n;
	float c;
	int e;

	LNode *prev = NULL, *current = NULL;

	plist->next = NULL;
	prev = plist;

	printf("
Please input the length of the polynomial: ");
	scanf_s("%d", &n);
	plist->A = 0;
	plist->m = n; //    

	printf("Please input the coefficient and the exponent of each term: 
");
	for (i = 1; i <= n; i++)
	{
		current = (LNode*)malloc(sizeof(LNode));
		scanf_s("%2f%d", &c, &e);
		current->A = c;
		current->m = e;
		prev->next = current;
		prev = current;
		/*plist->next = current;
		plist = current;*/
	}
	current->next = NULL;

	PolySort(plist);
}



/**
*Operation:         
*Precondition:
*Postcondition:
*Notes:             （  ）            
*/
LinkList PolyAdd(LNode *plist1, LNode *plist2)
{
	LNode *pa, *pb;
	LNode *result = (LNode*)malloc(sizeof(LNode));
	int a, b;
	result->next = NULL;
	LNode *r = result;
	pa = plist1->next;
	pb = plist2->next;

	while (pa && pb)
	{
		LNode *current = (LNode*)malloc(sizeof(LNode));

		a = pa->A;
		b = pb->m;

		switch (Cmp(a, b)){
		case -1:
			current->A= pa->m;
			current->A = pa->m;
			pa = pa->next;
			break;
		case  0:
			current->A = pa->A + pb->A;
			current->m = pa->m;
			pa = pa->next;
			pb = pb->next;
			break;
		case  1:
			current->A = pb->A;
			current->m = pb->m;
			pb = pb->next;
			break;
		}
		r->next = current;
		r = r->next;  //         
		current->next = NULL;
	}

	if (!pa || !pb)
	{
		if (!pa) Append(r, pb);
		if (!pb) Append(r, pa);
	}
	//free(current);
	return result;
}

/**
*       
*/
int Cmp(int a, int b)
{
	if (a>b) return 1;
	if (a<b) return -1;
	else return 0;
}


/**
*  pb     pa 
*/
void Append(LNode *pa, LNode *pb)
{
	LNode *r = pa;
	LNode *p = pb;

	while (p)
	{
		LNode *current = (LNode*)malloc(sizeof(LNode));

		current->A= p->A;
		current->m = p->m;

		p = p->next;
		r->next = current;     //SEGIVE
		current->next = NULL;
	}

}

/**
*Operation:          
*/
int ListIsEmpty(const LinkList *plist)
{
	if (*plist == NULL)
		return 1;
	else
		return 0;
}

/**
*Operation:          
*Precondition：plist         
*Postcondition：         
*/
void EmptyTheList(LNode *plist)
{
	LNode *psave;
	while (plist != NULL)
	{
		psave = plist->next;
		free(plist);
		plist = psave;
	}
}

/**
*Operation:          
*/
void PrintList(LNode *plist)
{
	LNode *p = plist;
	p = p->next; //     
	while (p != NULL)
	{
		if (p->next != NULL)
			printf("%0.1f*x^%d + ", p->A, p->m);
		else
			printf("%0.1f*x^%d;", p->A, p->m);
		p = p->next;
	}
	printf("
");
}


/**
*Operation:              
*Precondition:       
*Postcondition:          
*/
void PolySort(LNode *plist)
{
	LNode *pa = plist->next, *pb = pa->next;
	LNode *temp = (LNode*)malloc(sizeof(LNode));
	int length = GetLength(plist);
	int i;

	for (i = 0; i<length; i++)
	{
		while (pb)
		{
			if (pa->m > pb->m)
			{
				temp->A = pa->A; temp->m = pa->m;
				pa->A = pb->A; pa->m = pb->m;
				pb->A = temp->A; pb->m = temp->m;
			}

			pa = pa->next;
			pb = pa->next;
		}

		pa = plist->next;
		pb = pa->next;         //      pa,pb        
	}

}



/**
*Operation:                 （     ）
*Precondition:       
*Postcondition:            
*/
void PolyMerge(LNode *plist)
{
	LNode *prev, *current;
	int l = GetLength(plist);
	int i;

	prev = plist->next;
	current = prev->next;

	for (i = 0; i<l; i++)
	{
		while (current)
		{
			if (prev->m == current->m)
			{
				prev->A += current->A;    // why " prev->coef += current->coef " is wrong?
				prev->next = current->next;
				free(current);
				current = prev->next;
				continue;   //! without this sentence ,the function will be wrong and report an problem
			}
			prev = prev->next;
			current = prev->next;
		}

		if (current)
		{
			prev = plist->next;
			current = prev->next;
		}

	}

}

/* //     
void UnitePoly(LNode *h)//     
{
LNode *p1,*p2,*q1,*q2,*temp;
q1=h;
p1=q1->next;
while(p1!=NULL)
{
p2=p1->next;
q2=p1;
while(p2!=NULL)
{
if(p1->expn==p2->expn)
{
p1->coef=p1->coef+p2->coef;
if(p1->coef==0)
{
temp=p2;
q2->next=p2->next;
free(temp);
temp=p1;
q1->next=p1->next;
p1=q1;
free(temp);
break;
}
else
{
temp=p2;
q2->next=p2->next;
p2=p2->next;
free(temp);
}
}
else
{
q2=p2;
p2=p2->next;
}
}
q1=p1;
p1=p1->next;
}
}
*/


/**
*     
*/
int GetLength(LNode *plist)
{
	LNode *p = plist;
	int lenght = 0;
	p = p->next;  //    
	while (p)
	{
		lenght++;
		p = p->next;
	}
	return lenght;
	//return lenght-1;   //             
}




/**
*Operation:        
*Precondition:
*Postcondition:
*/
LinkList PolyMultiply(LNode *plist1, LNode *plist2)
{
	LNode *pa, *pb;
	LNode *result = (LNode*)malloc(sizeof(LNode));
	LNode *r = result;  //    ！  result       
	pa = plist1->next; pb = plist2->next;
	while (pa)
	{
		while (pb)
		{
			LNode *current = (LNode*)malloc(sizeof(LNode));

			current->A= pa->m * pb->A;  //    
			current->m = pa->m + pb->m;  //    

			r->next = current;
			current->next = NULL;
			r = r->next;

			pb = pb->next;
		}

		pa = pa->next;
		pb = plist2->next;  //pb        
	}

	PolyMerge(result);

	return result;
}



/**
*Operation: Computing the value of the polynomia
*Precondition: Ordered Polynomial Linklist
*Postcondition: The value of the polynomial
*/
float HornorEvaluate(LNode *plist, float x)
{
	//int max = GetMaxExpn(plist) + 10;
	int n = 0;
	int i;
	float result = 0;
	//float Poly[max];   //VC6 sidn't support VLA
	float Poly[20];
	LNode *p = plist->next;

	memset(Poly, 0, sizeof(Poly));

	while (p)
	{
		if (p->m == n)
		{
			Poly[n++] = p->A;
			p = p->next;
		}
		else
			Poly[n++] = 0;
	}  //Transform linklist to array to store the polynomial

	/*for(i=0;i<n;i++)   //             
	{
	printf("[%d]:%0.2f ",i,Poly[i]);
	}
	printf("
");*/

	result = Poly[n - 1];
	for (i = n - 1; i>0; i--)        //              !
	{
		result = result*x + Poly[i - 1];
		//printf("[%d %0.2f] ",i,result);  //             
	}

	return result;
}


/**
*Operation:
*Precondition:
*Postcondition:
*/
int GetMaxExpn(LNode *plist)
{
	LNode *p = plist->next;
	int max = p->m;
	while (p)
	{
		if (p->m > max)
			max = p->m;
		p = p->next;
	}
	return max;
}