Data_Structure/作業/unit2/DS2/DS2_usingLinkedlist.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

typedef struct node {
    int coef;
    int exp;
    struct node* rlink;
    struct node* llink;
} node;
node *head, *tail, *current, *prev, *temp;

void init_f() {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    head->rlink = tail;
    tail->llink = head;
}

void read_poly(char str[] ){
	int argCount ;
	while (1) {

    	node* newNode = (node*)malloc(sizeof(node));
    	
        argCount = sscanf(str, "%dx^%d%s", &newNode->coef, &newNode->exp, str);
        
        if (argCount >= 2) {  // <20><><EFBFBD>\Ū<><C5AA><EFBFBD>Y<EFBFBD>ƩM<C6A9><4D><EFBFBD><EFBFBD>
        
            newNode->llink = tail->llink;  
		    newNode->rlink = tail;         
		    tail->llink->rlink = newNode;  
		    tail->llink = newNode;

            if (argCount == 2) {
				break ;
			}
				
        } else {
        	if(!isdigit(newNode->coef)){
        		newNode->exp = 0;
        		
				newNode->llink = tail->llink;  
			    newNode->rlink = tail;         
			    tail->llink->rlink = newNode;  
			    tail->llink = newNode;
			    
			    break ;
			    
			}else{
//				printf("newNode->coef = %d\n",newNode->coef);
//				printf("isdigit(newNode->coef) = %d",isdigit(newNode->coef));
				
				free(newNode);
            	break ;
			}
            
        }
	}
}

void clear_node(){
	 // <20><><EFBFBD><EFBFBD><EFBFBD>O<EFBFBD><4F><EFBFBD><EFBFBD>
    current = head->rlink;
    while (current != tail) {
        temp = current;
        current = current->rlink;
        free(temp);
    }
    free(head);
    free(tail);
}


void show(int p[], int n, int mode){
	int i;
	if(mode == 0){
		printf("\n<EFBFBD><EFBFBD><EFBFBD>{<7B><>p(x)= ");
		current = head->rlink;
		while (current != tail) {
			if(abs(current->coef)>1){
				printf("%s%d", current->coef > 1? "":"\b",current->coef);
			}else if(current->coef == -1){
				printf("%s", current->exp == 0? "\b-1":"\b-");
			}
			switch(current->exp){
				case 0: 
					if(current->coef == 1 ) printf("1+");
					else printf("+");
					break;
				case 1:
					printf("x+");
					break;
				default:
					printf("x^%d+",current->exp);
			}
	        current = current->rlink;
	    }
	    printf("\b ");		
	    
	}else { /* mode==1<>A<EFBFBD><41><EFBFBD>ܩұo<D2B1><6F> */ 
		for (i = 0; i < n; i++) printf("%d<>B",p[i]);
		if (n > 0) printf("\b\b  ");
	}
	
}

int findRoot(int q[]) /* <20><><EFBFBD>ڡA<DAA1>ұo<D2B1>Ѧs<D1A6>Jq[]<5D>A<EFBFBD>^<5E>Ǯڪ<C7AE><DAAA>Ӽ<EFBFBD> */ 
{
	int r, c = 0, i, j, k, sum;
	int sign[2] = {1,-1};
	
	current = tail->llink;
	r = abs(current->coef);				/* <20><><EFBFBD>X<EFBFBD>̧C<CCA7><43><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Y<EFBFBD><59> */
	
	if (current->exp != 0) { /* <20>̧C<CCA7><43><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> >= 1<>A<EFBFBD>h0<68><30><EFBFBD>i<EFBFBD><69><EFBFBD><EFBFBD> */ 
		if ((i = current->exp) > 0) q[c++] = 0;	/* <20>̧C<CCA7><43><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ƴ]<5D><>i */
		current = head->rlink;
		while(current!=tail){
			current->exp -= i; /* <20>Ҧ<EFBFBD><D2A6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƴ<EFBFBD><C6B4>hi */ 
			current = current->rlink;
		}
	}
	
	
//	r = abs(p[2*p[0]]);				/* <20><><EFBFBD>X<EFBFBD>̧C<CCA7><43><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Y<EFBFBD><59> */

	for (i = 1; i <= r; i++) {		/* <20>Ҽ{<7B><><EFBFBD>㰣r<E3B0A3><72><EFBFBD>]<5D><>i<EFBFBD>A<EFBFBD><41><EFBFBD>`<60>N<EFBFBD><4E><EFBFBD>t<EFBFBD><74> */ 
		if (r%i != 0) continue;		/* <20><><EFBFBD><EFBFBD><EFBFBD>㰣r<E3B0A3><72>i<EFBFBD>N<EFBFBD><4E><EFBFBD>L<EFBFBD>A<EFBFBD>~<7E><><EFBFBD>Ҽ{<7B>U<EFBFBD>@<40><>i */ 
		
		for (j = 0; j < 2; j++) {	/* j<><6A>0<EFBFBD>A<EFBFBD>N<EFBFBD><4E><EFBFBD>Ҽ{+i<><69><EFBFBD><EFBFBD><EFBFBD>ҡFj<46><6A>1<EFBFBD>A<EFBFBD>N<EFBFBD><4E><EFBFBD>Ҽ{-i<><69><EFBFBD><EFBFBD><EFBFBD>p */
			for (sum = 0, current = head->rlink ; current!= tail ; current = current->rlink)	/* <20>p<EFBFBD><70><EFBFBD>C<EFBFBD>@<40><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>G<EFBFBD><47>(<28>Y<EFBFBD><59>*x^<5E><><EFBFBD><EFBFBD>)<29>ò֥[<5B><>sum<75><6D><EFBFBD><EFBFBD> */ 
				sum += current->coef *(int)(pow(sign[j]*i,current->exp));
			if (sum == 0) q[c++] = sign[j]*i;  /* bingo! <20>o<EFBFBD>{<7B>X<EFBFBD>G<EFBFBD><47><EFBFBD>󪺾<EFBFBD><F3AABABE>ƮڡA<DAA1>N<EFBFBD><4E><EFBFBD>g<EFBFBD>Jq<4A>}<7D>C */ 
		}
	}
	
	return c;
}


int main() {
    char str[100];
    int poly_num , *q ,c , high;
    init_f();

    printf("\n*** <20>Ѧh<D1A6><68><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ʈ<EFBFBD> ***\n\n<EFBFBD><EFBFBD><EFBFBD>J<EFBFBD>h<EFBFBD><EFBFBD><EFBFBD><EFBFBD> ==> ");
    
    if (fgets(str, sizeof(str), stdin) == NULL) {
        printf("<EFBFBD><EFBFBD><EFBFBD>J<EFBFBD><EFBFBD><EFBFBD>~<7E>I\n");
        return 1;
    }


/*	
		1x^2-100x^0
		1x^3-2x^2-1x^1+2x^0
		1x^3-7x^2+4x^1+12x^0
		1x^4+3x^3-66x^2+52x^1+120x^0
		3x^4+9x^3-198x^2+156x^1+360x^0
		1x^2-1x^1
		2x^ 3 -201 x^2+ 97 x^1 +300
		2x^12-195x^11-500x^10
		6x^4 - 1x^3 -25x^2 + 4x^1 + 4 
		1x^5-1x^3-1x^2-1x^1+1x^0
		1x^5+1x^3+1x^2+1x^1+1x^0
		1x^3+1x^0
*/ 
	
    read_poly(str);
    
    current = head->rlink;
	high= current->exp;
    
	show(q,c,0);
	
	q = (int *)malloc((high + 1) *sizeof(int)); /* p[1]<5D><><EFBFBD><EFBFBD><EFBFBD>̰<EFBFBD><CCB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ơA<C6A1>̦<EFBFBD><CCA6>ȳЫب<D0AB><D8A8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŷ<EFBFBD><C5B6><EFBFBD><EFBFBD>}<7D>C<EFBFBD>s<EFBFBD><73><EFBFBD>ҨD<D2A8>o<EFBFBD><6F><EFBFBD><EFBFBD><EFBFBD>Ʈ<EFBFBD> */ 
	
	c = findRoot(q);
	
	if (c > 0) {
		printf("\n\n<EFBFBD>ѱo<EFBFBD><EFBFBD><EFBFBD>Ʈڬ<EFBFBD><EFBFBD>G");
		show(q,c,1);  
	}
	else
		printf("\n\n<EFBFBD><EFBFBD><EFBFBD>Ʈڤ<EFBFBD><EFBFBD>s<EFBFBD>b\n");
		
    
    
	clear_node();
   

    return 0;
}