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

/*

数据结构C语言版 抽象数据类型Polynomial一元多项式的实现 P42-43

编译环境：Dev-C++ 4.9.9.2 日期：2011年2月10日 */

#include #include #include

// 抽象数据类型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.expndata,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=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,&q,compare)) // L中存在该指数项 {

q->data.coef+=e.coef; // 改变当前结点系数的值 if(!q->data.coef) // 系数为0 {

// 删除多项式L中当前结点

s = PriorPos(*L,q); // s为当前结点的前驱 if(!s) // q无前驱 s=(*L).head; DelFirst(L,s,&q); FreeNode(&q); }

return 1; }

else // 生成该指数项并插入链表

if(MakeNode(&s,e)) // 生成结点成功 {

InsFirst(L,q,s); 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(LinkList *L) {

Link p;

p=(Link)malloc(sizeof(LNode)); // 生成头结点 if(p) {

p->next=NULL;

//将头尾结点都分配好，并将其下一结点置空 (*L).head=(*L).tail=p; (*L).len=0; //初始为0 return 1; }

else // 分配失败返回 return 0;