本文共 5726 字，大约阅读时间需要 19 分钟。
完美的数据结构大作业之选。
C语言+链表 实现。
不用提前知道多项式项数，可以自动排序，可以合并同类项，可以进行加法、乘法运算。
//#include//#include #include"stdafx.h"#include #include //#define ERROR 0;//#define OVERFLOW 0;typedef struct Polyn { int expn, coef; Polyn* next;}*P;P CreatePolyn(Polyn *P); // 创建节点Polyn* SelectSort(Polyn *Pa); // 选择排序Polyn* MergePolyn(Polyn *Pa); //合并同类项void PrintPolyn(Polyn *P); // 打印多项式int cmp(int a, int b); // 比较函数P AddPolyn(P Pa, P Pb); // 多项式相加P MultiPolyn(P Pa, P Pb); // 多项式相乘/*------------------------Dome---------------------------------*/int main(){ P Pa, Pb, Pc, Pd; Pa = (Polyn *)malloc(sizeof(Polyn)); Pb = (Polyn *)malloc(sizeof(Polyn)); Pa = CreatePolyn(Pa); Pb = CreatePolyn(Pb); Pd = MultiPolyn(Pa, Pb); Pc = AddPolyn(Pa, Pb); system("pause"); return 0;}/*-----------------------打印多项式------------------------------*/void PrintPolyn(Polyn* P){ Polyn* q = P->next; //若多项式为空 printf("\n"); while (q->next != NULL) { if (q->coef>0) printf("%d*x^%d+", q->coef, q->expn); else if (q->coef < 0) { printf("(%d)*x^%d+", q->coef, q->expn); } else printf(""); q = q->next; } if (q->coef>0) printf("%d*x^%d", q->coef, q->expn); else printf("(%d)*x^%d", q->coef, q->expn);}/*-----------------------合并同类项------------------------------*/Polyn* MergePolyn(Polyn *Pa) { P p, pBefore, del; pBefore = Pa->next; p = pBefore->next; while (p) { if (p->expn == pBefore->expn) { del = p; pBefore->coef = pBefore->coef + p->coef; p = p->next; pBefore->next = p; free(del); } else pBefore = p; p = p->next; } //PrintPolyn(Pa); return Pa;}/*-----------------------创建节点--------------------------------*/P CreatePolyn(Polyn *P){ Polyn *previous, *current, *head; head = (Polyn *)malloc(sizeof(Polyn)); if (!head) exit(0); head->coef = 0; head->expn = -1; head->next = NULL; previous = head; int coef, expn; printf("\n请输入系数和指数（输入为(0,0)时结束）:\n"); scanf_s("%d%d", &coef, &expn); for (; (coef != 0) || (expn != 0);) { if (coef != 0) { current = (Polyn *)malloc(sizeof(Polyn)); current->coef = coef; current->expn = expn; current->next = NULL; previous->next = current; previous = current; current = previous->next; scanf_s("%d%d", &coef, &expn); } else scanf_s("%d%d", &coef, &expn); } P = SelectSort(head); P = MergePolyn(head); PrintPolyn(P); return P;}/*------------------------选择排序-------------------------------*/Polyn* SelectSort(Polyn *head){ Polyn *pfirst = NULL; //有序链表表头指针 Polyn *ptail = NULL; //有序链表表尾指针 Polyn *pmin = NULL; //存储最小节点 Polyn *pminBefore = NULL; //存储最小节点的前驱节点 Polyn *p = NULL; //当前比较节点 //pfirst = NULL; while (head != NULL) /*在链表中找键值最小的节点。*/ { /* 注意：这里for语句就是体现选择排序思想的地方 */ for (p = head, pmin = head; p->next != NULL; p = p->next) /*循环遍历链表中的节点，找出此时最小的节点。*/ { if (p->next->expn < pmin->expn) /*找到一个比当前min小的节点。*/ { pminBefore = p; /*保存找到节点的前驱节点：显然p->next的前驱节点是p。*/ pmin = p->next; /*保存键值更小的节点。*/ } } /*上面for语句结束后，就要做两件事；一是把它放入有序链表中；二是根据相应的条件判断，安排它离开原来的链表。 第一件事*/ if (pfirst == NULL) /* 如果有序链表目前还是一个空链表 */ { pfirst = pmin; /* 第一次找到键值最小的节点。 */ ptail = pmin; /* 注意：尾指针让它指向最后的一个节点。 */ } else /* 有序链表中已经有节点 */ { ptail->next = pmin; /* 把刚找到的最小节点放到最后，即让尾指针的next指向它。*/ ptail = pmin; /* 尾指针也要指向它。 */ } /*第二件事*/ if (pmin == head) /* 如果找到的最小节点就是第一个节点 */ { head = head->next; /* 显然让head指向原head->next,即第二个节点，就OK */ } else /*如果不是第一个节点*/ { pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/ } } if (pfirst != NULL) /*循环结束得到有序链表first */ { ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */ } head = pfirst; //PrintPolyn(head); return head;} /*-----------------------比较函数-------------------------------*/int cmp(int a, int b){ if (a < b) return 1; else if (a = b) return 0; else return -1;}//cmp /*-----------------------多项式相加-----------------------------*/P AddPolyn(P Pa, P Pb){ Polyn *qa = Pa->next; Polyn *qb = Pb->next; Polyn *headc, *hc, *qc; hc = (Polyn*)malloc(sizeof(Polyn)); hc->next = NULL; headc = hc; while (qa != NULL || qb != NULL) { qc = (Polyn*)malloc(sizeof(Polyn)); qc->next = NULL; if (qa && qb) { switch (cmp(qa->expn, qb->expn)) { case 1: { qc->coef = qa->coef; qc->expn = qa->expn; qa = qa->next; break; } case 0: { qc->coef = qa->coef + qb->coef; qc->expn = qa->expn; qa = qa->next; qb = qb->next; break; } case -1: { qc->coef = qb->coef; qc->expn = qb->expn; qb = qb->next; break; } }//switch } else if(qb != NULL) { qc->coef = qb->coef; qc->expn = qb->expn; qb = qb->next; } else{ qc->coef = qa->coef; qc->expn = qa->expn; qa = qa->next; } if (qc->coef != 0) { qc->next = hc->next; hc->next = qc; hc = qc; } else free(qc); } printf("\n多项式相加结果：\n"); PrintPolyn(headc); return headc;}//AddPolyn/*------------------------多项式乘法------------------------------*/P MultiPolyn(P Pa, P Pb) { P qa, qb; qa = Pa->next; qb = Pb->next; P qc, hc, headc; hc = (Polyn *)malloc(sizeof(Polyn)); hc->next = NULL; headc = hc; while (qa) { while (qb) { qc = (Polyn*)malloc(sizeof(Polyn)); qc->next = NULL; qc->coef = qa->coef * qb->coef; qc->expn = qa->expn + qb->expn; hc->next = qc; hc = qc; qc = qc->next; qb = qb->next; } qb = Pb->next; qa = qa->next; } headc = SelectSort(headc); headc = MergePolyn(headc); printf("\n多项式相乘结果：\n"); PrintPolyn(headc); return headc;}
vs环境可直接运行。非vs编程软件，注意根据情况改动头文件和int main中的 system（“pause”）；。
转载地址：http://pqdxi.baihongyu.com/