C语言线性链表实现一元多项式

main.cpp

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#include <stdio.h>#include "Polynomial.h"int main(){polynomail a, b, c;CreatePolyn(a, 2);CreatePolyn(b, 2);AssignPolyn(c, AddPolyn(a, b));AssignPolyn(c, SubtractPolyn(a, b));AssignPolyn(c, MutiplyPolyn(a, b));PrintPolyn(c);return 0;}

Polynomial.h

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#ifndef POLYNOMIAL_H#define POLYNOMIAL_H#include "Linked_List.h"typedef LinkList polynomail;void AssignPolyn(polynomail& x, polynomail y){x.head = y.head;x.tail = y.tail;x.len = y.len;}void CopyPolyn(polynomail& x, polynomail y){ClearList_L(x);int i = 1;for (Link py = NextPos(y, GetHead_L(y)); py != y.tail; py = NextPos(y, py)){ListInsert_L(x, i++, py->data);}}//-------基本操作的函数原型说明--------void CreatePolyn(polynomail& P, int m);void DestroyPolyn(polynomail& P);void PrintPolyn(polynomail P);int PolynLength(polynomail P);polynomail AddPolyn(polynomail Pa, polynomail Pb);polynomail SubtractPolyn(polynomail Pa, polynomail Pb);polynomail MutiplyPolyn(polynomail Pa, polynomail Pb);//-------基本操作的算法描述------------//输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid CreatePolyn(polynomail& P, int m){InitList_L(P);CreateList_L(P, m);}//销毁一元多项式void DestroyPolyn(polynomail& P){}//打印输出一元多项式void PrintPolyn(polynomail P){if (ListEmpty_L(P)){printf("00");}else{Link p = P.head;while(p->next != P.tail){(*visit)(p->next->data);if (p->next->next != P.tail){printf(" + ");}p = p->next;}}}//返回一元多项式P中的项数int PolynLength(polynomail P){return ListLength_L(P);}//完成多项式相加运算，即：Pa = Pa + Pb，并销毁一元多项式Pbpolynomail AddPolyn(polynomail Pa, polynomail Pb){polynomail Pc;InitList_L(Pc);Link ha, hb, hc, qa, qb, qc, temp;ElemType a, b, sum;ha = GetHead_L(Pa);hb = GetHead_L(Pb);hc = GetHead_L(Pc);qa = NextPos(Pa, ha);qb = NextPos(Pb, hb);qc = hc;while (qa!= Pa.tail && qb != Pb.tail){a = GetCurElem_L(qa);b = GetCurElem_L(qb);switch(compare(a, b)){//插入a中元素到ccase -1:MakeNode_L(temp, qa->data);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qa = NextPos(Pa, qa);FreeNode_L(temp);break;//插入sum到ccase 0:sum.coef = a.coef + b.coef;sum.expn = a.expn;if (sum.coef != 0.0f){MakeNode_L(temp, sum);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);FreeNode_L(temp);}qa = NextPos(Pa, qa);qb = NextPos(Pb, qb);break;//插入b中元素到ccase 1:MakeNode_L(temp, qb->data);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qb = NextPos(Pb, qb);FreeNode_L(temp);break;}}if (qa != Pa.tail){while(qa != Pb.tail){MakeNode_L(temp, qa->data);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qa = NextPos(Pa, qa);FreeNode_L(temp);}}else if (qb != Pb.tail){while(qb != Pb.tail){MakeNode_L(temp, qb->data);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qb = NextPos(Pb, qb);FreeNode_L(temp);}}return Pc;}//完成多项式相减运算，即：Pa = Pa - Pb，并销毁一元多项式Pbpolynomail SubtractPolyn(polynomail Pa, polynomail Pb){polynomail Pc;InitList_L(Pc);Link ha, hb, hc, qa, qb, qc, temp;ElemType a, b, sum;ha = GetHead_L(Pa);hb = GetHead_L(Pb);hc = GetHead_L(Pc);qa = NextPos(Pa, ha);qb = NextPos(Pb, hb);qc = hc;while (qa!= Pa.tail && qb != Pb.tail){a = GetCurElem_L(qa);b = GetCurElem_L(qb);switch(compare(a, b)){//插入a中元素到ccase -1:MakeNode_L(temp, qa->data);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qa = NextPos(Pa, qa);FreeNode_L(temp);break;//插入sum到ccase 0:sum.coef = a.coef - b.coef;sum.expn = a.expn;if (sum.coef != 0.0f){MakeNode_L(temp, sum);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);FreeNode_L(temp);}qa = NextPos(Pa, qa);qb = NextPos(Pb, qb);break;//插入b中元素到ccase 1:MakeNode_L(temp, getOpposite(qb->data));ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qb = NextPos(Pb, qb);FreeNode_L(temp);break;}}if (qa != Pa.tail){while(qa != Pb.tail){MakeNode_L(temp, qa->data);ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qa = NextPos(Pa, qa);FreeNode_L(temp);}}else if (qb != Pb.tail){while(qb != Pb.tail){MakeNode_L(temp, getOpposite(qb->data));ListInsert_L(Pc, qc, temp);qc = NextPos(Pc, qc);qb = NextPos(Pb, qb);FreeNode_L(temp);}}return Pc;}//完成多项式相乘运算，即：Pa = Pa * Pb，并销毁一元多项式Pbpolynomail MutiplyPolyn(polynomail Pa, polynomail Pb){polynomail Pc, tempPolyn;InitList_L(Pc);InitList_L(tempPolyn);Link ha, hb, qa, qb, htemp, temp, qtemp;ElemType a, b, sum;ha = GetHead_L(Pa);hb = GetHead_L(Pb);htemp = GetHead_L(tempPolyn);qa = NextPos(Pa, ha);while (qa != Pa.tail){qtemp = htemp;a = GetCurElem_L(qa);qb = NextPos(Pb, hb);while(qb != Pb.tail){b = GetCurElem_L(qb);sum.coef = a.coef * b.coef;sum.expn = a.expn + b.expn;MakeNode_L(temp, sum);ListInsert_L(tempPolyn, qtemp, temp);qtemp = NextPos(tempPolyn, qtemp);qb = NextPos(Pb, qb);FreeNode_L(temp);}qa = NextPos(Pa, qa);//PrintPolyn(AddPolyn(Pc, tempPolyn));CopyPolyn(Pc, AddPolyn(Pc, tempPolyn));ClearList_L(tempPolyn);}return Pc;}#endif

Linked_List.h

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#ifndef LINKED_LIST_H#define LINKED_LIST_H#include "ADT_Polynomail.h"#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0;#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef struct LNode{ElemType data;struct LNode * next;}*Link, *Position;typedef struct{Link head, tail;int len;}LinkList;Status MakeNode_L(Link& p, ElemType e);Status FreeNode_L(Link& p);Status InitList_L(LinkList& L);Status DestroyList_L(LinkList& L);void CreateList_L(LinkList& L, int n);Status ClearList_L(LinkList& L);Status InsFirst_L(Link& h, Link s);Status DelFirst_L(Link& h, Link& q);Status Append_L(LinkList& L, Link s);Status Remove_L(LinkList& L, Link& q);Status InsBefore_L(LinkList& L, Link& p, Link s);Status InsAfter_L(Link& p, Link& s);Status DelBefore_L(LinkList& L, Link& p, Link s);Status DelAfter_L(Link& p, Link& s);Status SetCurElem_L(Link& p, ElemType e);ElemType GetCurElem_L(Link p);Status ListEmpty_L(LinkList L);int ListLength_L(LinkList L);Position GetHead_L(LinkList L);Position GetLast_L(LinkList L);Position PriorPos(LinkList L, Link p);Position NextPos(LinkList L, Link p);Status LocatePos(LinkList L, int i, Link& p);Position LocateElem_L(LinkList L, ElemType e);Status ListInsert_L(LinkList& L, int i, ElemType e);Status ListInsert_L(LinkList& L, Link& p, Link s);Status ListDelete_L(LinkList& L, int i, ElemType& e);Status ListDelete_L(LinkList& L, Link& p);void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc);void union_L(LinkList& La, LinkList& Lb);Status ListTraverse_L(LinkList L);//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERRORStatus MakeNode_L(Link& p, ElemType e){//!优先级高于=if (!(p = (Link)malloc(sizeof(LNode)))){return ERROR;}AssignElemType(p->data, e);p->next = NULL;return OK;}//释放p所指结点Status FreeNode_L(Link& p){free(p);//p->next = NULL;return OK;}//构造一个空的线性链表LStatus InitList_L(LinkList& L){L.len = 0;MakeNode_L(L.head, getDefaultNULL());MakeNode_L(L.tail, getDefaultNULL());L.head->next = L.tail;L.tail->next = NULL;return OK;}//销毁线性链表LStatus DestroyList_L(LinkList& L){ClearList_L(L);FreeNode_L(L.head);FreeNode_L(L.tail);return OK;}//void CreateList_L(LinkList& L, int n){ElemType e;for (int i = 1; i <= n; i++){input(e);ListInsert_L(L, i, e);}}//将线性链表L重置为空表，并释放原链表的结点空间Status ClearList_L(LinkList& L){Link p = L.head->next, temp;while(p != L.tail){temp = p;p = p->next;FreeNode_L(temp);}L.head->next = L.tail;L.len = 0;return OK;}//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前Status InsFirst_L(Link& h, Link s){InsAfter_L(h, s);return OK;}//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回Status DelFirst_L(Link& h, Link& q){DelAfter_L(h, q);return OK;}//将指针s所指(彼此以指针相连)的一串结点链接在线性链表L的最后一个结点之后，//并改变链表L的尾指针指向新的尾结点Status Append_L(LinkList& L, Link s){Link p = PriorPos(L, L.tail);p->next = s;L.len++;//如果不只一个插入一个元素，执行while循环while (s->next != NULL && s->next->next != NULL){s = s->next;L.len++;}s->next = L.tail;return OK;}//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点Status Remove_L(LinkList& L, Link& q){Link temp = PriorPos(L, L.tail);q = temp;L.tail = q;FreeNode_L(temp);return OK;}//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，//并修改指针p指向新插入的结点Status InsBefore_L(LinkList& L, Link& p, Link s){Link temp = PriorPos(L, p);temp->next = s;s->next = p;return OK;}//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，//并修改指针p指向新插入的结点Status InsAfter_L(Link& p, Link& s){s->next = p->next;p->next = s;return OK;}Status DelBefore_L(LinkList& L, Link& p, Link& s){Link temp = PriorPos(L, p);s = p;temp->next = p->next;FreeNode_L(p);return OK;}//删除sStatus DelAfter_L(Link& p, Link& s){p->next = s->next;s->next = NULL;return OK;}//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值Status SetCurElem_L(Link& p, ElemType e){AssignElemType(p->data, e);return OK;}//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值ElemType GetCurElem_L(Link p){return p->data;}//若线性链表为空表，则返回TRUE；否则返回FALSEStatus ListEmpty_L(LinkList L){return L.head->next == L.tail ? TRUE : FALSE;}//返回线性表L中元素个数int ListLength_L(LinkList L){return L.len;}//返回线性链表L中最后一个结点的位置Position GetHead_L(LinkList L){return L.head;}//返回线性链表L中最后一个结点的位置Position GetLast_L(LinkList L){return L.tail;}//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，//若无前驱，则返回NULLPosition PriorPos(LinkList L, Link p){Link temp;temp = L.head;while(temp->next && temp->next != p){temp = temp->next;}return temp;}//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，//若无后继，则返回NULLPosition NextPos(LinkList L, Link p){return p->next;}//返回p所指线性链表L中第i个结点的位置并返回OK；i值不合法时返回ERRORStatus LocatePos(LinkList L, int i, Link& p){p = L.head;int j = 0;while(p && j < i){p = p->next;++j;}if (!p){return ERROR;}return OK;}//返回线性链表L中第1个与e满足函数compare()判定关系的元素和位置，//若不存在这样的元素则返回NULLPosition LocateElem_L(LinkList L, ElemType e){for (Link p = L.head; p != L.tail; p = p->next){if (compare(e, p->data)){return p;}}return NULL;}Status ListInsert_L(LinkList& L, int i, ElemType e){Link h, s;//找出要插入位置的前一个结点hif (!LocatePos(L, i - 1, h)){return ERROR;}if (!MakeNode_L(s, e)){return ERROR;}InsAfter_L(h, s);++L.len;return OK;}Status ListInsert_L(LinkList& L, Link& p, Link s){Link temp;MakeNode_L(temp, s->data);InsAfter_L(p, temp);++L.len;return OK;}Status ListDelete_L(LinkList& L, int i, ElemType& e){Link h, s;if (!LocatePos(L, i - 1, h)){return ERROR;}if (!LocatePos(L, i, s)){return ERROR;}e = s->data;DelAfter_L(h, s);FreeNode_L(s);--L.len;return OK;}Status ListDelete_L(LinkList& L, Link& p){Link h = PriorPos(L, p);DelAfter_L(h, p);FreeNode_L(p);--L.len;return OK;}//为Lc重新分配所有结点空间void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc){Link ha, hb, pa, pb, q;ElemType a, b;ha = GetHead_L(La);hb = GetHead_L(Lb);pa = NextPos(La, ha);pb = NextPos(Lb, hb);while(pa != La.tail && pb != Lb.tail){a = GetCurElem_L(pa);b = GetCurElem_L(pb);if (compare(a, b) <= 0){q = PriorPos(La, pa);DelAfter_L(q, pa);Append_L(Lc, pa);pa = NextPos(La, ha);}else{q = PriorPos(Lb, pb);DelAfter_L(q, pb);Append_L(Lc, pb);pb = NextPos(Lb, hb);}}if (pa != La.tail){Append_L(Lc, pa);}else{Append_L(Lc, pb);}FreeNode_L(ha);FreeNode_L(hb);}//一次对L的每个元素调用函数visit()，一旦visit()失败，则操作失败Status ListTraverse_L(LinkList L){Link p = L.head;if (ListEmpty_L(L)){return ERROR;}while(p->next != L.tail){(*visit)(p->next->data);p = p->next;}return OK;}#endif

ADT_Polynomial.h

/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#ifndef ADT_POLYNOMIAL_H#define ADT_POLYNOMIAL_Htypedef struct{float coef; //系数int expn; //指数}term, ElemType;ElemType getDefaultNULL(){ElemType DefaultNULL;DefaultNULL.coef = 0.0f;DefaultNULL.expn = -1;return DefaultNULL;}int compare(ElemType x, ElemType y){if (x.expn > y.expn) return 1;else if (x.expn < y.expn) return -1;else return 0;}void input(ElemType& x){scanf_s("%f%d", &x.coef, &x.expn);}void visit(ElemType x){if (x.expn){printf("(%f * X^%d)", x.coef, x.expn);}else{printf("%f", x.coef);}}void AssignElemType(ElemType& x, ElemType y){x.coef = y.coef;x.expn = y.expn;}ElemType getOpposite(ElemType x){ElemType y;y.coef = -x.coef;y.expn = x.expn;return y;}#endif