/**********************************************/
#include <stdio.h>
#include <stdlib.h>
/***************鏈表實現的頭文件***************/
typedef struct node
{
    int zhishu;
    int xishu;
    struct node *next;
}linknode;
typedef linknode *linklist;
/**********************************************/
/*  函數功能：      創建鏈表
    函數入口參數：  head   空鏈表的頭結點
    函數返回值：    已經建好的鏈表的頭結點
*/
linklist creat_list(linklist head)
{
    linklist x;
    linklist p;
    head=(linklist)malloc(sizeof(linknode));/*為頭結點申請空間*/

        head->next=NULL;
        head->zhishu=0;
        head->xishu=0;  /*頭結點全部信息置空 */
        p=head;      /*指針指向頭結點 */

        while(1)
        {
            x=(linklist)malloc(sizeof(linknode));
            printf("\n Input xi shu and zhi shu:");
            scanf("%d %d",&(x->xishu),&(x->zhishu)); /*輸入系數與指數，且系數與指數之間一空格鍵隔開 */
            if(x->xishu==0)
            {                                        /*系數與指數均可為負數*/
                printf(" ******* First list is ok!*******\n\n");
                break;  /*當系數為0時輸入完成，退出循環*/
            }
            x->next=NULL; /*鏈接數據*/
            p->next=x;
            p=x;
        }
            


    return head;   /*返回頭結點*/
}
/**********************************************/
/*函數功能：    打印出鏈表各節點的值
  函數入口參數：鏈表的頭結點
  函數返回值：  無
*/
void print_list(linklist head)
{
    linklist p;
    p=head->next;
    printf("                      ");
    while(p!=NULL)
    {
        printf("(%d)X^%d",p->xishu,p->zhishu);
        if(p->next!=NULL)
            printf("+");
        p=p->next;
    }
   printf("\n");
}
/*********************************************/
/*函數功能：       釋放函數所占空間
   函數入口參數：   要釋放鏈表的頭結點
   函數返回值：     無?
  */
void free_list(linklist head)
{
    linklist p;
    while(head!=NULL)
    {
        p=head;
        head=head->next;
        free(p);
    }
}
/**********************************************/
/*函數功能：實現兩個多項式的相加
  函數入口參數：待相加的兩個多項式所在鏈表的頭結點
  函數返回值:   兩多項式之和的鏈表的頭結點
*/
linklist jiafa(linklist head1,linklist head2)
{
    linklist p1,p2,s;
    linklist p3,head3;
    head3=(linklist)malloc(sizeof(linknode));
    p3=head3;
    p1=head1->next;
    p2=head2->next;

    while(p1 && p2)
    {
        s=(linklist)malloc(sizeof(linknode));
        if(p1->zhishu>p2->zhishu)
        {

           s->zhishu=p1->zhishu;
           s->xishu=p1->xishu;
           p1=p1->next;
        }
        else if(p1->zhishu==p2->zhishu)
        {
            s->zhishu=p1->zhishu;
            s->xishu=p1->xishu+p2->xishu;
            p1=p1->next;
            p2=p2->next;
        }
        else
        {
           s->zhishu=p2->zhishu;
           s->xishu=p2->xishu;
           p2=p2->next;
        }
        p3->next=s;
        p3=s;

    }
    p3->next=NULL;        /*處理尾部*/
    if(p1)
        p3->next=p1;
    if(p2)
        p3->next=p2;

    return  head3;
}
/*****************************************************/
linklist jianfa(linklist head1,linklist head2)
{
    linklist p2;
    p2=head2->next;
    while(p2)
    {
        p2->xishu=(-1)*p2->xishu;
        p2=p2->next;
    }
    return jiafa(head1,head2);
}
/***********************************************/
void main()
{
    int choose;
    linklist  head1,head2,head3;
    head1=NULL;
    head2=NULL;
    head3=NULL;

      /*表頭提示*/

    printf("*******************************************\n");
    printf("The xishu and zhishu are integer type!\n"); /*指數和系數都為整數類型*/
    printf("The linklist input end by xishu == 0!\n"); /* 鏈表輸入時，當系數為0時輸入結束 */
    printf("The zhishu of polynomial is form high to low!\n"); /*程序輸出時指數由高到低排列 */
    printf("*******************************************\n");

    while(1)
    {
        printf("\n\n*******************************************\n");
        printf("1.jiafa!\n");
        printf("2.jianfa!\n");
        printf("0.Exit the system!\n");
        printf("Please choose:");
        scanf("%d",&choose);

        if(choose!=0&&(choose==1||choose==2))
        {
            head1=creat_list(head1); /*創建鏈表*/
            head2=creat_list(head2);

            if(head1!=NULL && head2!=NULL) /*運行的條件是兩鏈表都不為空*/
            {
                 printf("The first polynomial:\n");
                 print_list(head1);   /*輸出第一個鏈表*/
                 printf("The second polymial:\n");
                 print_list(head2);     /*輸出第二個鏈表 */
                 printf("The result is:\n");

                 switch(choose)
                 {
                    case 1:
                        head3=jiafa(head1,head2);
                        break;
                    case 2:
                        head3=jianfa(head1,head2);
                        break;
                    default:
                        break;
                 }

                print_list(head3);          /* 輸出結果 */
                printf("That is over!\n");
                
                free_list(head1); /* 釋放掉空間 */
                free_list(head2);
                free_list(head3);

             }

        if(head1==NULL && head2==NULL)      /*當兩個鏈表為空時，顯示為空 */
            printf("The list is empty!!\n");
        }
        if(choose==0)
            break;
     }
    getch();
}