用链表实现多项式的乘法，怎么优化？
怎么优化可以提高处理速度？求啊。。。
[解决办法]
/*
* 实验环境: Turbo C 2.0
* 完成时间: 2003年2月22日
*--------------------------------
* 改进说明: 可以实现多个多项式的加法、减法、乘法，并且比书中算法更加
* 合理. 例如: 连加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); /* 在链表尾追加结点 */
status CreatePolyn(PolyPointer, int);
status ProcStrError(const char[]); /* 检查输入的数据 */
void SortPolyn(PolyPointer, int); /* 根据iExpon域对链表进行升序排序 */
void DestroyBuff(PolyPointer, const int);
void DestroyPolyn(polynomial);
int PolynLength(const polynomial); /* 求链表的长度 */
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); /* 在有序链表中,合并同类项 */
int main(void)
{
int iCounter,
iPolyNum; /* 多项式链表缓冲区中链表的个数 */
PolyPointer PolyBuff = NULL; /* 用户输入的多项式链表缓冲区 */
polynomial PolyAddRes = NULL, /* 存放连加结果链表 */
PolySubRes = NULL, /* 存放连减结果链表 */
PolyMulRes = NULL; /* 存放连乘结果链表 */
char strNum[10];
do
{
printf( "请输入需要构造多项式的个数,至少2个: ");
gets(strNum);
iPolyNum = atoi(strNum);
} while (iPolyNum < 2);
MakePolyBuff(&PolyBuff, iPolyNum);
CreatePolyn(PolyBuff, iPolyNum);
SortPolyn(PolyBuff, iPolyNum);
MergePolynCoeff(PolyBuff, iPolyNum);
printf( "\n打印用户输入并整合后的多项式:\n ");
for (iCounter = 0; iCounter < iPolyNum; iCounter++)
{
printf( "第%d个项式:\n ", iCounter + 1);
PrintPolyn(*(PolyBuff + iCounter));
}
AddProcess(PolyBuff, iPolyNum, &PolyAddRes, POSITIVE);
printf( "\n----------------连加结果-----------------\n ");
PrintPolyn(PolyAddRes);
SubstractProcess(PolyBuff, iPolyNum, &PolySubRes);
printf( "\n----------------连减结果-----------------\n ");
PrintPolyn(PolySubRes);
MultiplyProcess(PolyBuff, iPolyNum, &PolyMulRes);
printf( "\n----------------连乘结果-----------------\n ");
PrintPolyn(PolyMulRes);
printf( "\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( "错误,内存溢出!\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请输入构造多项式的系数和指数...\n ");
printf( "输入一个多项式的方式为: 系数, 指数; ... ; 系数, 指数;\n例如: 3, 4; 5, 6; 7, 8;\n ");
for (iCounter = 0; iCounter < iPolyNum; iCounter++)
{
printf( "\n请输入第%d个多项式:\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, /* 临时链表 */
pPrevMinExp, pCurrMinExp,/* 指向最小iExpon结点的指针 */
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;
}
/* 将系数最小的结点从原链表中取出 */
if (pCurrMinExp == *(PolyBuff + iCounter))
*(PolyBuff + iCounter) = pPrevMinExp-> next;
else
pPrevMinExp-> next = pCurrMinExp-> next;
/* 将系数最小的结点插入升序链表 */
pCurrMinExp-> next = NULL;
if (!pTemp)
pTemp = pTempCurrNode = pCurrMinExp;
else
{
pTempCurrNode-> next = pCurrMinExp;
pTempCurrNode = pTempCurrNode-> next;
}
}
*(PolyBuff + iCounter) = pTemp;
}
}
