《数据结构c语言版 抽象数据类型polynomial一元多项式的实现文库》由会员分享，可在线阅读，更多相关《数据结构c语言版 抽象数据类型polynomial一元多项式的实现文库（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构 C 语言版 抽象数据类型 Polynomial 一元多项式的实现文库.txt 生活是过出来的， 不是想出来的。放得下的是曾经，放不下的是记忆。无论我在哪里，我离你都只有一转身的 距离。/* 数据结构 C 语言版 抽象数据类型 Polynomial 一元多项式的实现 P42-43 编译环境：Dev-C+ 4.9.9.2 日期：2011 年 2 月 10 日 */#include #include #include / 抽象数据类型 Polynomial 一元多项式的实现 typedef struct / 项的表示,多项式的项作为 LinkList 的数据元素 float coef; /
2、 系数 int expn;/ 指数 term, ElemType; / 两个类型名:term 用于本 ADT,ElemType 为 LinkList 的数据对象名 typedef struct LNode / 结点类型 ElemType data; struct LNode *next; LNode,*Link,*Position;typedef struct _LinkList / 链表类型 Link head,tail; / 分别指向线性链表中的头结点和最后一个结点 int len;/ 指示当前线性链表中数据元素的个数 LinkList;typedef LinkList polynomia
3、l; #define DestroyPolyn DestroyList #define PolynLength ListLength / 已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点的直接前驱的位置 / 若无前驱，则返回 NULL Position PriorPos(LinkList L,Link p) Link q; q=L.head-next;if(q=p) / 无前驱 return NULL; else while(q-next!=p) / q 不是 p 的直接前驱 q=q-next; return q; / 若升序链表 L 中存在与 e 满足判定函数 compare()
4、取值为 0 的元素，则 q 指示 L 中 / 第一个值为 e 的结点的位置，并返回 1；否则 q 指示第一个与 e 满足判定函数 / compare()取值0 的元素的前驱的位置。并返回 0。 （用于一元多项式） int LocateElemP(LinkList L,ElemType e,Position *q, int(*compare)(ElemType,ElemType) Link p=L.head,pp; do pp=p; p=p-next; while(p return 0; else / 找到 *q=p; return 1; / h 指向 L 的一个结点，把 h 当做头结点，删除链
5、表中的第一个结点并以 q 返回。 / 若链表为空(h 指向尾结点)，q=NULL，返回 0 int DelFirst(LinkList *L,Link h,Link *q) *q=h-next; if(*q) / 链表非空 h-next=(*q)-next; if(!h-next)/ 删除尾结点 (*L).tail=h; / 修改尾指针 (*L).len-; return 1; else return 0; / 链表空 / 分配由 p 指向的值为 e 的结点，并返回 1；若分配失败。则返回 0int MakeNode(Link *p,ElemType e) *p = (Link)malloc(
6、sizeof(LNode);/动态分配一个 Link 空间if(!*p) return 0; (*p)-data = e; / 赋值return 1; / 释放 p 所指结点void FreeNode(Link *p) free(*p);/老规矩，先释放存储空间，然后置空*p=NULL; / h 指向 L 的一个结点，把 h 当做头结点，将 s 所指结点插入在第一个结点之前 / 头结点没有数据域，而第一个结点是 h-nextint InsFirst(LinkList *L,Link h,Link s) s-next = h-next; h-next=s; if(h=(*L).tail)/ 如果
7、 h 指向尾结点 (*L).tail=h-next;/ 修改尾指针 (*L).len+; return 1; / 按有序判定函数 compare()的约定，将值为 e 的结点插入或合并到升序 / 链表 L 的适当位置 int OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term) Position q,s; if(LocateElemP(*L,e, / 改变当前结点系数的值 if(!q-data.coef) / 系数为 0 / 删除多项式 L 中当前结点 s = PriorPos(*L,q); / s 为当前结点的前驱
8、 if(!s) / q 无前驱 s=(*L).head; DelFirst(L,s, FreeNode( return 1; else / 生成该指数项并插入链表 if(MakeNode( return 1; else / 生成结点失败 return 0; / 依 a 的指数值b 的指数值，分别返回-1、0 或+1 / CreatPolyn()的实参 int cmp(term a,term b) if(a.expn=b.expn) return 0; else return (a.expn-b.expn)/abs(a.expn-b.expn); / 构造一个空的线性链表int InitList
9、(LinkList *L) Link p; p=(Link)malloc(sizeof(LNode); / 生成头结点 if(p) p-next=NULL; /将头尾结点都分配好，并将其下一结点置空(*L).head=(*L).tail=p; (*L).len=0; /初始为 0return 1; else/ 分配失败返回return 0; / 算法 2.22 P42 / 输入 m 项的系数和指数，建立表示一元多项式的有序链表 P void CreatPolyn(polynomial *P,int m) Position q,s; term e; int i;InitList(P); prin
10、tf(“请依次输入%d 个系数，指数：（空格）n“,m);for(i=1;inext; / 已知 p 指向线性链表中的一个结点，返回 p 所指结点中数据元素的值ElemType GetCurElem(Link p) return p-data;/ 将指针 s(s-data 为第一个数据元素)所指(彼此以指针相链,以 NULL 结尾)的 / 一串结点链接在线性链表 L 的最后一个结点之后,并改变链表 L 的尾指针指向新 / 的尾结点 int Append(LinkList *L,Link s) int i=1;/记录 s 为头的串结点个数 (*L).tail-next=s;/尾结点指向 swhi
11、le(s-next) s=s-next; i+; (*L).tail=s; (*L).len+=i; return 1; / 若线性链表 L 为空表，则返回 1，否则返回 0int ListEmpty(LinkList L) if(L.len) return 0; else return 1; / 将线性链表 L 重置为空表（头尾结点相同为空表） ，并释放原链表的结 / 点空间，不释放头尾结点，只是置空而已 int ClearList(LinkList *L) Link p,q; if(*L).head!=(*L).tail)/ 不是空表 p=q=(*L).head-next; (*L).he
12、ad-next=NULL; while(p!=(*L).tail) p=q-next; free(q); q=p; free(q);(*L).tail=(*L).head; (*L).len=0; return 1; / 销毁线性链表 L，L 不再存在int DestroyList(LinkList *L) ClearList(L);/ 清空链表（头尾结点并没有释放） FreeNode(/再释放头尾结点(*L).tail=NULL; (*L).len=0; return 1; / 算法 2.23 P43 / 多项式加法:Pa=Pa+Pb,并销毁一元多项式 Pb void AddPolyn(po
13、lynomial *Pa,polynomial *Pb) Position ha,hb,qa,qb; term a,b;ha=GetHead(*Pa); hb=GetHead(*Pb); / ha 和 hb 分别指向 Pa 和 Pb 的头结点 qa=NextPos(ha); qb=NextPos(hb); / qa 和 qb 分别指向 Pa 和 Pb 中当前结点（现为第一个结点） while(!ListEmpty(*Pa) b=GetCurElem(qb); / a 和 b 为两表中当前比较元素 switch(cmp(a,b) case -1: ha=qa; / 多项式 Pa 中当前结点的指数
14、值小 qa=NextPos(ha); / ha 和 qa 均向后移一个结点 break; case 0: qa-data.coef+=qb-data.coef; / 两者的指数值相等,修改 Pa 当前结点的系数值 if(qa-data.coef=0) / 系数和为 0，则删除多项式 Pa 中当前结点 DelFirst(Pa,ha, FreeNode( else ha=qa; DelFirst(Pb,hb, FreeNode( qb=NextPos(hb); qa=NextPos(ha); break; case 1: DelFirst(Pb,hb, / 多项式 Pb 中当前结点的指数值小 In
15、sFirst(Pa,ha,qb); ha=ha-next; qb=NextPos(hb); if(!ListEmpty(*Pb) (*Pb).tail=hb; Append(Pa,qb); / 链接 Pb 中剩余结点 DestroyPolyn(Pb); / 销毁 Pb / 另一种多项式加法的算法:Pa=Pa+Pb,并销毁一元多项式 Pbvoid AddPolyn1(polynomial *Pa,polynomial *Pb) Position qb; term b; qb=GetHead(*Pb);/ qb 指向 Pb 的头结点 qb=qb-next;/ qb 指向 Pb 的第一个结点 while(qb) b=GetCurElem(qb); OrderInsertMerge(Pa,b,cmp); qb=qb-next; DestroyPolyn(Pb); / 销毁 Pb / 一元多项式系数取反 void Opposite(polynomial Pa) Position p; p=Pa.head;while(p-next) p=p-next; p-data.coef*=-1; / 多项式减法:Pa=
