实现结构：单项链表

思路：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去，减法亦然。

main.c

#include <stdio.h>
#include <malloc.h>
#include "poly.h"
#include "lArray.h"void printInfo();
void eatline();
void choose_option();void poly_exp_add(polyLinkList *ptr);void poly_exp_view(polyLinkList *ptr);void poly_exp_del(polyLinkList *ptr);void poly_addition(polyLinkList *ptr);void poly_sub(polyLinkList *ptr);int main() {printInfo();choose_option();return 0;
}void printInfo()
{printf("一元多项式的运算-----------------------\n");printf("0.添加一元表达式.\n");printf("1.查看表达式列表.\n");printf("2.删除一个表达式.\n");printf("3.一元多项式的加法.\n");printf("4.一元多项式的减法.\n");printf("6.退出.\n");printf("-------------------------------------\n");
}void choose_option()
{polyLinkList Poly_Link_List;initPolyLinkList(&Poly_Link_List);int d;do{scanf("%d",&d);eatline();switch(d){case 0://添加一元表达式poly_exp_add(&Poly_Link_List);break;case 1://查看表达式列表poly_exp_view(&Poly_Link_List);break;case 2://删除一个表达式poly_exp_del(&Poly_Link_List);break;case 3://一元多项式的加法poly_addition(&Poly_Link_List);break;case 4://一元多项式的减法poly_sub(&Poly_Link_List);break;case 6://退出break;default:break;}printf("->");}while(d != 6);
}void poly_sub(polyLinkList *ptr) {int id1;int id2;char strExp[100] = "\0";poly_exp_view(ptr);printf("\n");printf("请输入要进行减法运算的id1和id2，以\",\"隔开,并按下回车键\n");printf("例子:1,2\n");printf("->");while(scanf("%d,%d",&id1,&id2) == 2){struct polyNode * p1 = findById(ptr,id1);struct polyNode * p2 = findById(ptr,id2);if(p1 && p2){subtractPoly(p1->linkList,p2->linkList);printPolyn(p1->linkList,strExp);printf("结果:%s\n",strExp);printf("要退出请按任意键并敲下回车，不退出请继续输入表达式的id,eg:1,2\n");printf("->");strExp[0] = '\0';}else{printf("两个表达式有一个id不存在，请重新输入.\n");printf("->");}eatline();}eatline();printf("操作取消.\n");}void poly_addition(polyLinkList *ptr) {int id1;int id2;char strExp[100]="\0";poly_exp_view(ptr);printf("\n");printf("请输入要进行加法运算的id1和id2，以\",\"隔开，并按下回车键\n");printf("例子:1,2\n");printf("->");while(scanf("%d,%d",&id1,&id2) == 2){struct polyNode * p1 = findById(ptr,id1);struct polyNode * p2 = findById(ptr,id2);if(p1 && p2){addPolyn(p1->linkList,p2->linkList);printPolyn(p1->linkList,strExp);printf("结果:%s\n",strExp);printf("要退出请按任意键并敲下回车，不退出请继续输入表达式的id,eg:1,2\n");printf("->");strExp[0] = '\0';}else{printf("两个表达式有一个id不存在，请重新输入.\n");printf("->");}eatline();}eatline();printf("操作取消.\n");
}void poly_exp_del(polyLinkList *ptr) {int id;printf("请输入要删除节点的id:");if(scanf("%d",&id) == 1){polyLinkList_remove(ptr,id);}eatline();
}void poly_exp_view(polyLinkList *ptr) {struct polyNode ** pnList = findAll(ptr);int i = 0;printf("------------------------------------\n");printf("|   id   |           表达式         |\n");//36-2-(id)-(表达式) = 29char strExp[100]="\0"; //表达式空间for(;i<ptr->length;i++){printPolyn(pnList[i]->linkList,strExp);printf("|%8d|%23s  |\n",pnList[i]->id,strExp);strExp[0]='\0';}printf("------------------------------------\n");
}//表达式添加
void poly_exp_add(polyLinkList *ptr) {struct polyNode * pnode = (struct polyNode * )malloc(sizeof(struct polyNode));LinkList * linkList = (LinkList * )malloc(sizeof(LinkList));Term term;int j = 1;printf("请输入表达式的系数n和指数e并以逗号\",\"隔开,格式:n,e\n");printf("结束输入请输入任意数字并回车.\n");printf("请输入%d项:",j);;while(scanf("%d,%d",&term.n,&term.e) == 2){eatline();createPolyn(linkList,term);printf("请输入%d项:",++j);}if(j!=1)//至少输入了一项{pnode->id = ptr->length+1;pnode->linkList = linkList;polyLinkList_add(ptr,pnode);}eatline();
}void eatline()
{while(getchar() != '\n')continue;
}

poly.h

#ifndef _POLY_H_
#define _POLY_H_#include <stdbool.h>
typedef struct{int n;//系数int e;//指数
}Term;typedef struct node{Term term;struct node * next;//下一节点
}Node;typedef struct{int length;Node * head;
}LinkList;void createPolyn(LinkList * pLinkList,Term term);
void destroyPolyn(LinkList * pLinkList);
void printPolyn(LinkList * pLinkList,char * strExp);
int polynLength(LinkList * pLinkList);
void addPolyn(LinkList * pa,LinkList * pb);
void subtractPoly(LinkList * pa,LinkList * pb);
void multiplyPolyn(LinkList * pa,LinkList * pb);
int cmpTerm(Node * pa,Node *pb);
#endif

poly.c

#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "poly.h"/*** 创建一元多项式* @param pLinkList* @param term*/
void createPolyn(LinkList *pLinkList,Term term) {Node * pn = NULL;if(pLinkList->head){pn = pLinkList->head;while(pn->next)pn = pn->next;pn->next = (Node *)malloc(sizeof(Node));pn->next->term = term;}else{pn = (Node *)malloc(sizeof(Node));pLinkList->head = pn;pn->term = term;}pLinkList->length++;
}/*** 销毁一元多项式* @param pLinkList*/
void destroyPolyn(LinkList *pLinkList) {Node * pn = pLinkList->head;Node * ptemp;while(pn){ptemp = pn;pn = pn->next;free(ptemp);}
}/*** 打印表达式* @param pLinkList*/
void printPolyn(LinkList *pLinkList,char * strExp) {Node * pn = pLinkList->head;char strTemp[50];bool isFirstPlus = true;//去除表达式第一个加号while(pn){if(pn->term.e == 0){if(pn->term.n != 0){if(pn->term.n > 0){if(isFirstPlus){sprintf(strTemp,"%d",pn->term.n);}else{sprintf(strTemp,"+%d",pn->term.n);}}else if(pn->term.n < 0){sprintf(strTemp,"%d",pn->term.n);}isFirstPlus = false;strcat(strExp,strTemp);}}else{if(pn->term.n < 0){if(pn->term.e == 1)sprintf(strTemp,"%dX",pn->term.n);elsesprintf(strTemp,"%dX^%d",pn->term.n,pn->term.e);isFirstPlus = false;strcat(strExp,strTemp);}else if(pn->term.n > 0) {if(pn->term.n == 1)if(pn->term.e == 1)if(isFirstPlus)sprintf(strTemp, "X");elsesprintf(strTemp, "+X");elseif(isFirstPlus)sprintf(strTemp, "X^%d", pn->term.e);elsesprintf(strTemp, "+X^%d", pn->term.e);elseif(pn->term.e == 1)if(isFirstPlus)sprintf(strTemp, "%dX", pn->term.n);elsesprintf(strTemp, "+%dX", pn->term.n);elseif(isFirstPlus)sprintf(strTemp, "%dX^%d", pn->term.n, pn->term.e);elsesprintf(strTemp, "+%dX^%d", pn->term.n, pn->term.e);isFirstPlus = false;strcat(strExp,strTemp);}}pn = pn->next;}
}/*** 获取表达式项数* @param pLinkList* @return*/
int polynLength(LinkList *pLinkList) {if(pLinkList)return pLinkList->length;elsereturn 0;
}/*** 一元多项式的加法运算* @param pa* @param pb* @return 将pa = pa + pb,pa、pb无用的释放掉.*/
void addPolyn(LinkList *pa, LinkList *pb) {Node *na,*nb,*temp,*pre=NULL;na = pa->head;nb = pb->head;while(na && nb){if(cmpTerm(na,nb) == -1) {pre = na;na = na->next;}else if(cmpTerm(na,nb) == 0){if(na->term.n + nb->term.n != 0){na->term.n+=nb->term.n;temp = nb;nb = nb->next;pre = na;na = na->next;free(temp);}else{temp = na;na = na->next;if(!pre)//当位于第一个节点时候pa->head = na;elsepre->next = na;free(temp);temp = nb;nb = nb->next;free(temp);}}else{temp = nb->next;nb->next = na;if(!pre)pa->head = nb;elsepre->next = nb;nb = temp;}}if(nb)//如果b还有剩余节点{pre->next = nb;//链接剩余节点}
}/*** 一元多项式的减法运算* @param pa* @param pb* @return*/
void subtractPoly(LinkList * pa,LinkList * pb)
{Node *na,*nb,*temp = NULL, *pre = NULL;na = pa->head;nb = pb->head;while(na && nb){if(cmpTerm(na,nb) == -1){pre = na;na = na->next;}else if(cmpTerm(na,nb) == 0){if(na->term.n - nb->term.n != 0){na->term.n -= nb->term.n;temp = nb;nb = nb->next;free(temp);pre = na;na = na->next;}else{if(!pre)pa->head = na->next;elsepre->next = na->next;temp = na;na = na->next;free(temp);temp = nb;nb = nb->next;free(temp);}}else{nb->term.n = -nb->term.n;temp = nb->next;nb->next = na;if(!pre)pa->head = nb;elsepre->next = nb;nb = temp;}}if(nb){pre->next = nb;while(nb){nb->term.n = -nb->term.n;nb = nb->next;}}
}/*** 一元多项式的乘法运算* @param pa* @param pb* @return*/
void multiplyPolyn(LinkList * pa,LinkList * pb)
{}/*** 比较ta 和 tb 指数的大小关系，分别返回 1,0,-1* @param ta* @param tb* @return*/
int cmpTerm(Node * pa,Node *pb)
{if(pa->term.e > pb->term.e)return 1;else if(pa->term.e == pb->term.e)return 0;elsereturn -1;
}

lArray.h

#ifndef _L_ARRAY_H_
#define _L_ARRAY_H_
#include "poly.h"struct polyNode{int id;LinkList * linkList;struct polyNode * next;
};typedef struct{struct polyNode * head;int length;struct polyNode * tail;//当前链表的尾节点
}polyLinkList;void initPolyLinkList(polyLinkList * pll);
void polyLinkList_add(polyLinkList * pll,struct polyNode * pnode);
void polyLinkList_remove(polyLinkList * pll,int id);
void polyLinkList_update(polyLinkList * pll, struct polyNode * pnode);
struct polyNode * findById(polyLinkList * pll, int id);/*** 查找数组内所有节点* @param pll* @return 返回首节点指针*/
struct polyNode ** findAll(polyLinkList * pll);#endif

lArray.c

#include "lArray.h"
#include <stdlib.h>void initPolyLinkList(polyLinkList * pll)
{pll->tail = NULL;pll->length = 0;pll->head = NULL;
}void polyLinkList_add(polyLinkList * pll,struct polyNode * pnode)
{if(!pll->tail)//如果尾部指针为空，说明链表没有元素{pll->head = pnode;pll->tail = pnode;}else{pll->tail->next = pnode;pll->tail = pnode;}pll->length++;
}void polyLinkList_remove(polyLinkList * pll,int id)
{struct polyNode * node = pll->head;if(node){if(node->id == id)//首节点即是需要删除的节点{pll->head = node->next;free(node);pll->length--;}else{while(node->next){if(node->next->id == id){free(node->next);node->next = node->next->next;pll->length--;break;}node = node->next;}}}
}/*** 根据节点的id来更新* @param pll* @param pnode*/
void polyLinkList_update(polyLinkList * pll, struct polyNode * pnode)
{if(pnode){struct polyNode * node = findById(pll,pnode->id);node->linkList = pnode->linkList;}
}
struct polyNode * findById(polyLinkList * pll, int id)
{struct polyNode * node = pll->head;while(node){if(node->id == id)return node;node = node->next;}return NULL;
}/*** 查找数组内所有节点* @param pll* @return 返回首节点指针,用完记得释放*/
struct polyNode ** findAll(polyLinkList * pll)
{if(pll){if(pll->length != 0){struct polyNode ** pnArray = (struct polyNode **)malloc(sizeof(struct polyNode *)*pll->length);struct polyNode * node = pll->head;int i = 0;while(node){*(pnArray+i) = node;node = node->next;i++;}return pnArray;}}return NULL;
}

测试用例：    12X^12+12X^14+12X^17
              21X^12+243X^14+1223X^123321

进行减法操作：-9X^12-231X^14+12X^17-1223X^123321

因为时间比较紧张，所以只是实现了一元多项式的加减法运算，乘除法运算没有实现。