数据结构C语言版 抽象数据类型Polynomial一元多项式的实现文库.docVIP

/* 数据结构C语言版 抽象数据类型Polynomial一元多项式的实现 P42-43 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月10日 */ #include stdio.h #include malloc.h #include stdlib.h // 抽象数据类型Polynomial一元多项式的实现 typedef struct // 项的表示,多项式的项作为LinkList的数据元素 { float coef; // 系数 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 polynomial; #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()取值为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(compare(p-data,e)0)); // 没到表尾且p-data.expne.expn if(!p||compare(p-data,e)0) // 到表尾或compare(p-data,e)0 { *q=pp; return 0; } else // 找到 { *q=p; return 1; } } // h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以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；若分配失败。则返回0 int MakeNode(Link *p,ElemType e) { *p = (Link)malloc(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-next int InsFirst(LinkList *L,Link h,Link s) { s-next = h-next; h-next=s; if(h==(*L).tail) // 如果h指向尾结点 (*L).tail=