데이터 구조 응용

/*----------------------------------------------------------------------------------
	    ：
	      《    》          。
	             。

	          (   )      。           。        
	     ，             ，                ，    
	       。            ，              ，     
	    。


	  ：
	        ，       ，                 。  ，   
	    ，                     。  ，            
	   。   ，             。          ，         
	   。                 。。

	-------------------------------------------------------------------------------*/






/*---------------------------------------------------------------------------------
	addpolyn.c
	      

	edited by Seed,2011

	-------------------------------------------------------------------------------*/




#include<stdio.h>
#include"addpolyn.h"


int main(void)
{

	Polynomial Pa, Pb ;
	int m ;
	

	printf("       A     :  ") ;  //     A
	scanf("%d",&m) ;
	CreatPolyn(&Pa,m) ;


	PrintPolyn(Pa) ;


	printf("       B     :  ") ;  //     B
	scanf("%d",&m) ;
	CreatPolyn(&Pb,m) ;


	PrintPolyn(Pb) ;


	AddPolyn(&Pa, &Pb) ;   //  A B

	PrintPolyn(Pa) ;

	Destroy(&Pa) ;

	return 0 ;
}


/*------------------------------------------------------------------
	File : addpolyn.h
	Fuction :          

	edited by Seed , 2011
	----------------------------------------------------------------*/


#ifndef ADDPOLYN_H_
#define ADDPOLYN_H_




/*-----------------------------------------------------------
	      

	---------------------------------------------------------*/

typedef struct
{
	float coef ;
	int expn ;
} term, ElemType ;


typedef struct LNode
{
	ElemType data ;
	struct LNode *next ;
} LNode ,*Link, *Position ;


typedef struct
{
	Link head , tail ;
	int len ;
} LinkList ;


typedef LinkList Polynomial ;




/*---------------------------------------------------------
	     、           


	-------------------------------------------------------*/



typedef int Status ;

#define OK 1 
#define ERROR 0
#define TRUE 1
#define FALSE 0



Link  GetHead(Polynomial *P) ;

Status InitList(Polynomial *P) ;

Status SetCurElem(Link *p,ElemType e) ;

Status LocateElem(Polynomial *P,ElemType e,Position *q,int (*compare)(ElemType,ElemType) ) ;

Status MakeNode(Link *p,ElemType e) ;

Status InsFirst(Link h,Link s) ;

int cmp(term a,term b) ;

void CreatPolyn(Polynomial *P ,int m) ;

Link NextPos(Polynomial *P, Link l) ;

ElemType GetCurElem(Link p)  ;

void FreeNode(Link P) ;

Status ListEmpty(LinkList L) ;

Status Append(LinkList *L,Link s) ;

void AddPolyn(Polynomial *Pa, Polynomial *Pb) ;

void Destroy(Polynomial *P) ;

void PrintPolyn(Polynomial P) ;




#endif  






/*------------------------------------------------------------------
	File : polyn.h
	Fuction :        

	edited by Seed , 2011
	----------------------------------------------------------------*/



#include"addpolyn.h"
#include<stdio.h>
#include<stdlib.h>



Link GetHead(Polynomial *P)
{
	return (P->head) ;
}  //GetHead


Status InitList(Polynomial *P)
{

	if((P->head = P->tail = (Link) malloc(sizeof(LNode))) == NULL) //        p->head = p->tail = e ;          
	{
		printf("Can't assign room
") ;
		exit(1) ;
	}
																		//  e      ，          ,          ，														
	P->len = 0 ;															//              .

	P->head->next = NULL ;


	return OK ;

}  //InitList


Status SetCurElem(Link *p,ElemType e)
{
	if(NULL == p)
	{
		printf("Error
") ;
		return ERROR ;
	}                           
	else
	{
		
		(*p)->data = e ;

		return OK ;
	}
}  //SetCurElem



int cmp(term a,term b)
{
	if(a.expn > b.expn )
		return 1 ;
	else if(a.expn == b.expn )
		return 0 ;
	else 
		return -1 ;
} // cmp


Status LocateElem(Polynomial *P,ElemType e,Link *q,int (*compare)(ElemType,ElemType) )
{
	Link temp = (Link)malloc(sizeof(LNode)) ;		
	Link pre = (Link) malloc(sizeof(LNode)) ;
	
	ElemType t ;

	temp = P->head->next  ;
	pre = P->head ;

	while(temp != NULL)
	{
		t = temp->data ;
		
		switch((*compare)(t,e))
		{
		case 1 :
			(*q) = pre ;						
			return 1 ;
			
		case 0 :
			return 0 ;
		}                             //switch-case             

		temp = temp->next ;
		pre = pre->next ;
	}                                //while

	return -1 ;

}  //LocateElem



Status MakeNode(Link *p,ElemType e)
{	
	if(((*p) = (Link) malloc(sizeof(LNode))) != NULL)
	{
		(*p)->data = e ;
		(*p)->next = NULL ;
		return TRUE ;
	}

	return FALSE ;
}  //MakeNode



Status InsFirst(Link h,Link s)  
{
	Link temp ;
	if((temp = (Link) malloc(sizeof(LNode))) != NULL )
	{
		temp = h->next ;

		s->next = temp ;

		h->next = s ;


		return OK ;
	}

	return FALSE ;
}



void CreatPolyn(Polynomial *P ,int m)
{
	Link  h ,s = NULL;
	ElemType  e ;
	int i = 0 ;
	Link *q = (Link *) malloc(sizeof(LNode)) ;
	Link last = (Link) malloc(sizeof(LNode)) ;


	e.coef = 0.0 ;
	e.expn = -5 ;

	InitList(P) ;

    h = GetHead(P) ;




	if(!SetCurElem(&h,e))
	{
		printf("The pointer is NUUL
") ;
		exit(1) ;
	}

	for(i = 0 ; i < m ; i++)
	{
		printf("
     ：") ;
		scanf("%f",&(e.coef )) ;

		printf("
     : ") ;
		scanf("%d",&(e.expn) ) ;

		switch(LocateElem(P,e,q,cmp))
		{
		case 0 :
			break ;
			
		case 1 :
			if(MakeNode(&s,e))
			{
				if(InsFirst(*q,s))
				{
					P->len++ ;
				}
			}
			break ;

		case -1 :
			if(MakeNode(&s,e))
			{
				last = P->tail ;
				
				last->next = s ;
				
				P->tail = s ;

				P->len++ ;			
			}                //if
			break ;
		}//switch
	}  //for
		
}  //CreatPolyn


Link NextPos(Polynomial *P, Link l)
{
	Link cur = P->head ;
	
	while(cur != l && cur != NULL)
		cur = cur->next ;

	if(NULL == cur)
		return NULL ;
	else
		return l->next ;

} //NextPos


ElemType GetCurElem(Link p) 
{
	return p->data ;
} //GetCurElem

Status DelFirst(Link h, Link q)
{
	Link temp ;
	
	if(NULL == h->next )
	{
		q = NULL ;
		return ERROR ; 
	}

	temp = h->next ;
	h->next = h->next ->next ;
	q = temp ;

	return OK ;
} //DelFirst 



void FreeNode(Link P)
{
	if(NULL == P)
		;
	else
	{
		free(P) ;
		P = NULL ;
	}
} //FreeNode



Status ListEmpty(LinkList L)
{
	if(L.head == L.tail)
		return TRUE ;
	else
		return FALSE ;
} //ListEmpty

Status Append(LinkList *L,Link s)
{

	int count = 0 ;

	L->tail->next = s ;


	while(s != NULL)
	{
		s = s->next ;
		count++ ;
	}

	L->tail = s ;
	L->len += count ;

	return TRUE ;

}//Append 

void AddPolyn(Polynomial *Pa,Polynomial *Pb)
{
	Link ha ,hb ;
	Link qa, qb ;

	ElemType a ,b ;

	float sum ;

	ha = GetHead(Pa) ;
	hb = GetHead(Pb) ;

	qa = NextPos(Pa,ha) ;
	qb = NextPos(Pb,hb) ;

	

	while((qa != NULL) && (qb != NULL))
	{
		a = GetCurElem(qa) ;
		b = GetCurElem(qb) ;

		switch(cmp(a,b))
		{
		case -1 :
			ha = qa ;
			qa = NextPos(Pa,qa) ;
			break ;

		case 0 :
			sum = a.coef + b.coef ;

			a.coef = sum ;

			if(sum != 0.0)
			{
				SetCurElem(&qa,a) ;      //Status SetCurElem(Link *p,ElemType e)
				ha = qa ;
			}
			else
			{
				if(DelFirst(ha,qa))
				{
					Pa->len-- ;
				}
				FreeNode(qa) ;
			}

			DelFirst(hb,qb) ;
			FreeNode(qb) ;
			qb = NextPos(Pb,hb) ;
			qa = NextPos(Pa,ha) ;
			break ;

		case 1 :
			DelFirst(hb,qb) ;
			InsFirst(ha,qb) ;
			qb = NextPos(Pb,hb) ;
			ha = NextPos(Pa,ha) ;

			break ;
		}  //switch
	}  //while


	if(!ListEmpty(*Pb))
	{
		Append(Pa,qb) ;
	}

	FreeNode(hb) ;

}  //AddPolyn



void Destroy(Polynomial *P)
{
	Link h = P->head ;
	Link temp ;

	while(h != NULL)
	{
		temp = h ;
		h = h->next ;
		free(temp) ;
	}

} //Destroy


void PrintPolyn(Polynomial P)
{
	Link h= P.head ;

	while(h != NULL) 
	{
		printf("%.2f^%d + " ,h->data.coef ,h->data.expn ) ;
		h = h->next ;
	}

	printf("


") ;

} //PrintPolyn