/*
* 文件名: 1_3.c(選做題)
* 實(shí)驗(yàn)環(huán)境: Turbo C 2.0
* 完成時(shí)間: 2003年2月22日
*--------------------------------------------------------------------
* 改進(jìn)說(shuō)明: 可以實(shí)現(xiàn)多個(gè)多項(xiàng)式的加法、減法、乘法，并且比書中算法更加
* 合理. 例如: 連加a+b+c+d,連減a-b-c-d,連乘a*b*c*d.
*/

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

#define TRUE                        1
#define FALSE                       0
#define POSITIVE                    1
#define NEGATIVE                   -1

typedef int status;
typedef struct NodeType 
{
    float fCoeff;
    int iExpon;
    struct NodeType *next;
} NodeType, *LinkType;
typedef LinkType polynomial;
typedef polynomial *PolyPointer;

status MakePolyBuff(PolyPointer *, const int);
status MakeNode(polynomial *, const float, const int);
void AppNodeToList(polynomial *, polynomial);   /* 在鏈表尾追加結(jié)點(diǎn) */
status CreatePolyn(PolyPointer, int);
status ProcStrError(const char[]); /* 檢查輸入的數(shù)據(jù) */
void SortPolyn(PolyPointer, int); /* 根據(jù)iExpon域?qū)︽湵磉M(jìn)行升序排序 */
void DestroyBuff(PolyPointer, const int);
void DestroyPolyn(polynomial);
int PolynLength(const polynomial); /* 求鏈表的長(zhǎng)度 */
void AddProcess(PolyPointer, const int, PolyPointer, const int);
void SubstractProcess(PolyPointer, const int, PolyPointer);
void MultiplyProcess(PolyPointer, const int, PolyPointer);
void PrintPolyn(const polynomial);
void MergePolynCoeff(PolyPointer, int); /* 在有序鏈表中,合并同類項(xiàng) */

int main(void)
{
    int iCounter, 
        iPolyNum; /* 多項(xiàng)式鏈表緩沖區(qū)中鏈表的個(gè)數(shù) */
    PolyPointer PolyBuff = NULL;   /* 用戶輸入的多項(xiàng)式鏈表緩沖區(qū) */
    polynomial PolyAddRes = NULL,  /* 存放連加結(jié)果鏈表 */
               PolySubRes = NULL,  /* 存放連減結(jié)果鏈表 */
               PolyMulRes = NULL;  /* 存放連乘結(jié)果鏈表 */
    char strNum[10];

    do
    {
        printf("請(qǐng)輸入需要構(gòu)造多項(xiàng)式的個(gè)數(shù),至少2個(gè): ");
        gets(strNum); 
        iPolyNum = atoi(strNum);
    } while (iPolyNum < 2);

    MakePolyBuff(&PolyBuff, iPolyNum);
    CreatePolyn(PolyBuff, iPolyNum);
    SortPolyn(PolyBuff, iPolyNum);
    MergePolynCoeff(PolyBuff, iPolyNum);
    printf("\n打印用戶輸入并整合后的多項(xiàng)式:\n");
    for (iCounter = 0; iCounter < iPolyNum; iCounter++)
    {
        printf("第%d個(gè)項(xiàng)式:\n", iCounter + 1);
        PrintPolyn(*(PolyBuff + iCounter));
    }

    AddProcess(PolyBuff, iPolyNum, &PolyAddRes, POSITIVE);
    printf("\n----------------連加結(jié)果-----------------\n");
    PrintPolyn(PolyAddRes);

    SubstractProcess(PolyBuff, iPolyNum, &PolySubRes);
    printf("\n----------------連減結(jié)果-----------------\n");
    PrintPolyn(PolySubRes);

    MultiplyProcess(PolyBuff, iPolyNum, &PolyMulRes);
    printf("\n----------------連乘結(jié)果-----------------\n");
    PrintPolyn(PolyMulRes);

    printf("\n運(yùn)行完畢!\n");
    /* 回收資源 */
    DestroyBuff(PolyBuff, iPolyNum);
    DestroyPolyn(PolyAddRes);
    DestroyPolyn(PolySubRes);
    DestroyPolyn(PolyMulRes);

    getch();
    return 0;
}

status MakePolyBuff(PolyPointer *polyBuffHead, const int iPolyNum)
{    
    int iCounter;

    *polyBuffHead = (PolyPointer)
            malloc(sizeof(polynomial) * iPolyNum);
    if (!(*polyBuffHead))
    {
        printf("錯(cuò)誤,內(nèi)存溢出!\n");
        return FALSE;
    }
    for (iCounter = 0; iCounter < iPolyNum; iCounter++)
        *(*polyBuffHead + iCounter) = NULL;

    return TRUE;
}

status CreatePolyn(PolyPointer PolyBuff, int iPolyNum)
{
    int iCounter, iExpon;
    float fCoeff;
    char strNum[100], strTemp[64], *cpCurr, *cpCurrNum;
    polynomial pNewNode = NULL, pInsPos = NULL;

    printf("\n請(qǐng)輸入構(gòu)造多項(xiàng)式的系數(shù)和指數(shù)...\n");
    printf("輸入一個(gè)多項(xiàng)式的方式為: 系數(shù), 指數(shù); ... ; 系數(shù), 指數(shù);\n例如: 3, 4; 5, 6; 7, 8;\n");
    for (iCounter = 0; iCounter < iPolyNum; iCounter++)
    {
        printf("\n請(qǐng)輸入第%d個(gè)多項(xiàng)式:\n", iCounter + 1);
        gets(strNum);
        if(!ProcStrError(strNum)) return FALSE;
        cpCurr = cpCurrNum = strNum; 
        while (*cpCurr != '\0')
        {
            if (*cpCurr == ',')
            {
                strncpy(strTemp, cpCurrNum, cpCurr - cpCurrNum);
                strTemp[cpCurr - cpCurrNum] = '\0';
                fCoeff = (float)atof(strTemp);
                cpCurrNum = cpCurr + 1;
            }
            else if (*cpCurr == ';')
            {
                strncpy(strTemp, cpCurrNum, cpCurr - cpCurrNum);
                strTemp[cpCurr - cpCurrNum] = '\0';
                iExpon = atoi(strTemp);
                MakeNode(&pNewNode, fCoeff, iExpon);
                AppNodeToList(PolyBuff + iCounter, pNewNode);
                cpCurrNum = cpCurr + 1;
            }
            cpCurr++;
        }
    }

    return TRUE;
}

status MakeNode(LinkType *pp, const float coeff, const int expon)
{
    if (!(*pp = (LinkType)malloc(sizeof(NodeType) * 1))) 
    {
        printf("Error, the memory is overflow!\n");
        return FALSE;
    }
    (*pp)->fCoeff = coeff;
    (*pp)->iExpon = expon;
    (*pp)->next = NULL;

    return TRUE;
}

void AppNodeToList(polynomial *pHead, polynomial pNewNode)
{
    static polynomial pCurrNode;

    if (!(*pHead))
        (*pHead) = pCurrNode = pNewNode;
    else
    {
        pCurrNode->next = pNewNode;
        pCurrNode = pCurrNode->next;
    }
}

void SortPolyn(PolyPointer PolyBuff, int iPolyNum)
{
    int iCounter;
    polynomial pTemp, pTempCurrNode,    /* 臨時(shí)鏈表 */
               pPrevMinExp, pCurrMinExp,/* 指向最小iExpon結(jié)點(diǎn)的指針 */
               pCurrNode, pPrevNode;

    for (iCounter = 0; iCounter < iPolyNum; iCounter++)
    {
        pTemp = NULL;
        while (*(PolyBuff + iCounter) != NULL)
        {
            pPrevNode = pPrevMinExp = pCurrMinExp = 
                            *(PolyBuff + iCounter);
            pCurrNode = (*(PolyBuff + iCounter))->next;
            while (pCurrNode != NULL)
            {
                if (pCurrMinExp->iExpon > pCurrNode->iExpon)
                {
                    pPrevMinExp = pPrevNode;
                    pCurrMinExp = pCurrNode;
                }
                pPrevNode = pCurrNode;
                pCurrNode = pCurrNode->next;
            }
            /* 將系數(shù)最小的結(jié)點(diǎn)從原鏈表中取出 */
            if (pCurrMinExp == *(PolyBuff + iCounter))
                *(PolyBuff + iCounter) = pPrevMinExp->next;
            else
                pPrevMinExp->next = pCurrMinExp->next;
            /* 將系數(shù)最小的結(jié)點(diǎn)插入升序鏈表 */
            pCurrMinExp->next = NULL;
            if (!pTemp)
                pTemp = pTempCurrNode = pCurrMinExp;
            else
            {
                pTempCurrNode->next = pCurrMinExp;
                pTempCurrNode = pTempCurrNode->next;
            }
        }

        *(PolyBuff + iCounter) = pTemp;
    }
}

void MergePolynCoeff(PolyPointer PolyBuff, int iPolyNum)
{
    int iCounter;
    float MergeCoeffRes = 0;
    polynomial TempList, ResList = NULL, pCurrNode, pPreNode,
               pNewNode = NULL;

    for (iCounter = 0; iCounter < iPolyNum; iCounter++)
    {
        pPreNode = TempList= *(PolyBuff + iCounter);
        MergeCoeffRes = pPreNode->fCoeff;
        pCurrNode = (*(PolyBuff + iCounter))->next;
        while (pCurrNode != NULL)
        {
            while ((pCurrNode != NULL) && 
                   (pCurrNode->iExpon == pPreNode->iExpon))  
            {
                MergeCoeffRes += pCurrNode->fCoeff;
                pPreNode = pCurrNode;
                pCurrNode = pCurrNode->next;
            }

            /* 在ResList中加入新結(jié)點(diǎn) */
            if (MergeCoeffRes != 0)
            {
                MakeNode(&pNewNode, MergeCoeffRes, pPreNode->iExpon);
                AppNodeToList(&ResList, pNewNode);
                MergeCoeffRes = 0;
            }

            pPreNode = pCurrNode;
        }

        DestroyPolyn(TempList);
        *(PolyBuff + iCounter) = ResList;
        ResList = NULL;
    }

}

void AddProcess(PolyPointer polyBuff, const int iPolyNum, 
                PolyPointer pResult, const int iSign)
{
    int iCounter;
    float fCoeffRes;
    polynomial pNewNode, pCurrNode_1, pCurrNode_2, 
               pDelList = NULL, /* 下次要?jiǎng)h除的中間結(jié)果鏈表 */
               pResList = NULL; /* 中間結(jié)果鏈表 */
               
    pCurrNode_1 = *(polyBuff);
    for (iCounter = 1; iCounter < iPolyNum; iCounter++)
    {
        pCurrNode_2 = *(polyBuff + iCounter);
        while (pCurrNode_1 != NULL && pCurrNode_2 != NULL)
        {
            if (pCurrNode_1->iExpon == pCurrNode_2->iExpon)
            {
                fCoeffRes = 0;
                fCoeffRes = pCurrNode_1->fCoeff + 
                            iSign * pCurrNode_2->fCoeff;
                if (fCoeffRes != 0)
                {
                    MakeNode(&pNewNode, fCoeffRes, 
                                  pCurrNode_1->iExpon);
                    AppNodeToList(&pResList, pNewNode);
                }
                pCurrNode_1 = pCurrNode_1->next;
                pCurrNode_2 = pCurrNode_2->next;
            }
            else if (pCurrNode_1->iExpon < pCurrNode_2->iExpon)
            {
                MakeNode(&pNewNode, pCurrNode_1->fCoeff, 
                                    pCurrNode_1->iExpon);
                AppNodeToList(&pResList, pNewNode);
                pCurrNode_1 = pCurrNode_1->next;
            }
            else /* 當(dāng)pCurrNode_1->iExpon > pCurrNode_2->iExpon時(shí)候 */
            {
                MakeNode(&pNewNode, iSign * pCurrNode_2->fCoeff, 
                                    pCurrNode_2->iExpon);
                AppNodeToList(&pResList, pNewNode);
                pCurrNode_2 = pCurrNode_2->next;
            }
        }
        /* 加入余下的多項(xiàng)式 */
        while (pCurrNode_1 != NULL)
        {
            MakeNode(&pNewNode, pCurrNode_1->fCoeff, 
                                pCurrNode_1->iExpon);
            AppNodeToList(&pResList, pNewNode);
            pCurrNode_1 = pCurrNode_1->next;
        }
        while (pCurrNode_2 != NULL)
        {     
            MakeNode(&pNewNode, iSign * pCurrNode_2->fCoeff, 
                                pCurrNode_2->iExpon);
            AppNodeToList(&pResList, pNewNode);
            pCurrNode_2 = pCurrNode_2->next;
        }

        if (pDelList != NULL) DestroyPolyn(pDelList);
        pCurrNode_1 = pResList;
        pDelList = pResList;
        pResList = NULL;
    }

    *pResult = pCurrNode_1;
}

void SubstractProcess(PolyPointer polyBuff, const int iPolyNum, 
                      PolyPointer pResult)
{
    AddProcess(polyBuff, iPolyNum, pResult , NEGATIVE);
}

void MultiplyProcess(PolyPointer polyBuff, const int iPolyNum, 
                     PolyPointer pResult)
{
    int iCounter = 1, jCounter = 0, iLength; /* 緩沖區(qū)的長(zhǎng)度 */
    PolyPointer pTempBuff = NULL; /* 存放中間結(jié)果的緩沖區(qū) */
    polynomial  pCurrNode_1, pCurrNode_2, pNewNode  = NULL;

    /* 初始化 */
    pCurrNode_1 = polyBuff[0]; 
    iLength = PolynLength(polyBuff[0]);
    MakePolyBuff(&pTempBuff, iLength);
    while (TRUE)
    {   
        while (pCurrNode_1 != NULL)
        {
            pCurrNode_2 = polyBuff[iCounter];
            while (pCurrNode_2 != NULL)
            {
                MakeNode(&pNewNode, 
                         pCurrNode_1->fCoeff * pCurrNode_2->fCoeff,
                         pCurrNode_1->iExpon + pCurrNode_2->iExpon);
                AppNodeToList(&pTempBuff[jCounter], pNewNode);
                pCurrNode_2 = pCurrNode_2->next;
            }
            jCounter++;
            pCurrNode_1 = pCurrNode_1->next;
        }

        /* 回收舊的中間結(jié)果 */
        if (pResult != NULL) DestroyPolyn(*pResult);
        /* 獲得新的中間結(jié)果 */
        AddProcess(pTempBuff, iLength, pResult , POSITIVE);
        DestroyBuff(pTempBuff, iLength); /* 回收存中間結(jié)果的緩沖區(qū) */
        jCounter = 0;
        if (++iCounter >= iPolyNum)
            break;
        else 
        {
            iLength = PolynLength(*pResult);
            MakePolyBuff(&pTempBuff, iLength);
            pCurrNode_1 = *pResult;
        }
   }
}

void PrintPolyn(const polynomial polyList)
{
    polynomial pCurrNode = polyList;

    printf("多項(xiàng)式的長(zhǎng)度為: %d\n", PolynLength(polyList));
    while (pCurrNode != NULL)
    {
        printf("%.2fX^%d", pCurrNode->fCoeff, pCurrNode->iExpon);
        if (pCurrNode->next != NULL)
            if (pCurrNode->next->fCoeff > 0 ) 
                printf("+");
        pCurrNode = pCurrNode->next;
    }
    printf("\n");
}

int PolynLength(const polynomial polyList)
{
    int iLength = 0;
    polynomial pCurrNode = polyList;
   
    while (pCurrNode != NULL)
    {
        pCurrNode = pCurrNode->next;
        iLength++;
    }
    return iLength;
}

void DestroyBuff(PolyPointer polyBuff, const int iPolyNum)
{
    int iCounter;

    for (iCounter = 0; iCounter < iPolyNum; iCounter++)
        DestroyPolyn(polyBuff[iCounter]);
    free(polyBuff);
}

void DestroyPolyn(polynomial polyList)
{
    polynomial pCurrNode;

    while (polyList != NULL)
    {
        pCurrNode = polyList;
        polyList = polyList->next;
        free(pCurrNode);
    }
}

status ProcStrError(const char str[])
{
    const char *cpCurr = str;

    if (!strlen(str)) 
    {
        printf("你沒(méi)有輸入數(shù)據(jù)!\n");
        return FALSE;
    }
    while (*cpCurr != '\0')
    {
        if (!(*cpCurr == ' ' || *cpCurr == ',' || *cpCurr == ';' 
            || *cpCurr == '-')
            && ('0' > *cpCurr || *cpCurr > '9')
            || (*(cpCurr + 1) == '\0' && *cpCurr != ';'))
        {
            printf("輸入數(shù)據(jù)出錯(cuò),請(qǐng)注意正確的輸入方式!\n");
            return FALSE;
        }
        cpCurr++;
    }

    return TRUE;
}