main.c

有用户在键盘输入两个多项式

/*------两个多项式相加-------*/
/*作者：陆鹏超  日期：07.9.26*/

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


/*------自定义结构-----------*/
struct polynode
{
    int coef;   /*系数*/
    int exp;    /*指数*/
    struct polynode *next;   /*指向下一项的指针*/
};

typedef struct polynode polypointer;
typedef polypointer *PolyPointer;

/*-------声明部分------------*/
PolyPointer PADD( PolyPointer, PolyPointer );
int compare( int, int );
PolyPointer CREAT( void );
void PRINTLIST( PolyPointer );
void EMPTY_the_list( PolyPointer head );
int REVERSE_order( PolyPointer head );

/*-------主函数--------------*/
int main()
{
    /*定义指针并初始化*/
    PolyPointer head_a, head_b, head_c;
    head_a = NULL;
    head_b = NULL;
    head_c = NULL;

    /*打印说明*/
    printf( "这个程序帮助你计算两个多项式相加的和。\n"
            "请按以下格式输入：\n"
            "  2    3    -2   2    4    1    6    0      0\n"
            "( 系数 指数 系数 指数           常数 指数零 系数零--一组输入结束 )\n"
            "  2    4    -4   3    6    1    7    0      0\n"
            "( 系数 指数 系数 指数           常数 指数零 系数零--另一组输入结束 )\n"
            "请按指数降序输入\n" );

    head_a = CREAT( );         /*录入多项式a*/
    REVERSE_order( head_a );   /*防止用户不按要求输入，排列多项式*/

    head_b = CREAT( );         /*录入多项式b*/
    REVERSE_order( head_b );   /*防止用户不按要求输入，排列多项式*/

    head_c = PADD( head_a, head_b );    /*调用多项式相加函数*/

    PRINTLIST( head_c );       /*打印结果   */

    EMPTY_the_list( head_a );           /*清空临时使用的链表*/
    EMPTY_the_list( head_b );
    EMPTY_the_list( head_c );

	return 0;
}/*主函数结束*/


/*---------compare------------------*/
/*-----比较两个节点的指数大小-------*/
/*p = q返回0，p > q返回1，p < q返回2*/
int compare( int exp_a, int exp_b )
{
    if( exp_a == exp_b )
    {
        return 0;
    }
    if( exp_a > exp_b )
    {
        return 1;
    }
    else
        return 2;
}

/*--------------------------------attach----------------------------------------------------*/
/*创建一个新节点，系数coef = c,指数exp = e,并把它链入d指定的节点之后，并返回这个新的节点指针*/
PolyPointer attach( int c, int e, PolyPointer d )
{
    PolyPointer x = NULL;    /*定义指针并初始化*/

    x = ( struct polynode * )malloc( sizeof( struct polynode ) );    /*分配空间*/

    if( x == NULL )    /*内存不足处理*/
    {
        printf("内存不足\n");
        return x;
    }

    x->coef = c;      /*数据录入及指针处理*/
    x->exp = e;
    d->next = x;
    x->next = NULL;

    return x;
}

/*------------------------------PADD------------------------------*/
/*处理两个多项相加*/
PolyPointer PADD( PolyPointer a, PolyPointer b )
{
    PolyPointer p, q, d, c;
    int x = 0;
    int com = 0;
    p = a->next;
    q = b->next;
    c = ( struct polynode * )malloc( sizeof( struct polynode ) );    /*初始化*/
    d = c;

    while( ( p != NULL ) && ( q != NULL ) )      /*当两个多项式有一个达到式尾时跳出*/
    {
        com = compare( p->exp, q->exp );         /*比较当前两项的指数*/

        switch( com )
        {
            case 0:/*相等时系数相加*/
                   x = p->coef + q->coef;        /*系数相加*/

                   if( x != 0 )
                   {
                       d = attach( x, p->exp, d );d->next = NULL;   /*将新节点链入*/
                   }

                   p = p->next;                  /*前进一步*/
                   q = q->next;

                   break;
            case 1:/*p的指数大时，将p的此项链入结果*/
                   d = attach( p->coef, p->exp, d );d->next = NULL;   /*复制q所指节点并链入c中*/

                   p = p->next;    /*p前进一步*/

                   break;
            case 2:/*q的指数大时，将去的此项链入结果*/
                   d = attach( q->coef, q->exp, d );d->next = NULL;   /*复制q所指节点并链入c中*/

                   q = q->next;    /*q前进一步*/

                   break;
        }/*switch*/
    }/*while*/

    /*复制a的剩余部分*/
    while( p != NULL )
    {
        d = attach( p->coef, p->exp, d );d->next = NULL;
        p = p->next;
    }

    /*复制b的剩余部分*/
    while( q != NULL )
    {
        d = attach( q->coef, q->exp, d );d->next = NULL;
        q = q->next;
    }

    d->next = NULL;    /*最后的节点指向空*/

    return c;     /*返回新表头节点*/
}

/*----------------------------------CREAT------------------------------------*/
/*创建链表存放多项式*/
PolyPointer CREAT( void )
{
    int item = 0;
    PolyPointer head, q, previousPtr;

    head = NULL;
    q = NULL;
    previousPtr = NULL;

    head = ( struct polynode * )malloc( sizeof( struct polynode ) );
    head->next = NULL;                                 /*建立头指针空间    */
    previousPtr = head;

    scanf( "%d", &item );

    while( item != 0 )
    {
        q = ( struct polynode * )malloc( sizeof( struct polynode ) );   /*为新元素分配空间*/

        if( q == NULL )
        {
            printf("内存不足\n");
            return ( q );
        }

        q->coef = item;          /*读入系数，并存入*/

        scanf( "%d", &item );    /*读入指数        */

        q->exp = item;           /*存入指数        */

        q->next = NULL;          /*节点末尾指空    */

        previousPtr->next = q;   /*q链入链表       */

        previousPtr = q;         /*指向下一节点*/

        scanf( "%d", &item );

    }

    return ( head );      /*返回头指针*/
}

/*------------------打印链表----------------------*/
void PRINTLIST( PolyPointer head )
{
    PolyPointer currentPtr;
    currentPtr = head->next;

    if( currentPtr == NULL )
    {
        printf ( "The result is 0. \n" );

    }
    else
    {
        printf( "The result is: \n" );


        while( currentPtr != NULL )
        {
            printf ( "%d %d ", currentPtr->coef, currentPtr->exp );
            currentPtr = currentPtr->next;
        }

    }
}


/*------------------------------指数降序排列链表-------------------------------*/
int REVERSE_order( PolyPointer head )
{
    PolyPointer previousPtr, currentPtr, frontPtr, recordPtr;

    previousPtr = head;

    if( head->next != NULL )
    {
        currentPtr = head->next->next;
        previousPtr->next->next = NULL;

        while( currentPtr != NULL )
        {
            recordPtr = currentPtr->next;          /*记录断点信息*/
            frontPtr = head->next;                 /*从头遍历链表*/


            while( frontPtr != NULL && currentPtr->exp < frontPtr->exp )   /*到达已排表尾跳出*/
            {
                previousPtr = frontPtr;            /*逐渐从已排链表的前面向后找插入点*/
                frontPtr = frontPtr->next;
            }


            previousPtr->next = currentPtr;        /*插入*/
            currentPtr->next = frontPtr;

            currentPtr = recordPtr;                /*再次向后断点插入*/
        }
    }
    else
    {
        printf( "You input nothing.\n"
                "Close the window and retry.\n" );
    }

    return 0;
}

/*清空链表*/
/*清空临时操作建立的链表*/
void EMPTY_the_list( PolyPointer head )
{
    PolyPointer nextPtr;

    while( head != NULL )
    {
        nextPtr = head->next;      /*保存下一个节点的指针*/
        free( head );              /*释放当前节点        */
        head = nextPtr;            /*前进到下一节点      */
    }
}