yiyuanduoxiangshi.rar_一元多项式相加

#include<malloc.h> #include<stdio.h> #include<math.h> // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE // 抽象数据类型Polynomial的实现 typedef struct // 项的表示,多项式的项作为LinkList的数据元素 { float coef; // 系数 int expn; // 指数 }term,ElemType; // 两个类型名:term用于本ADT,ElemType为LinkList的数据对象名 // 带头结点的线性链表类型 typedef struct LNode // 结点类型 { ElemType data; LNode *next; }*Link,*Position; struct LinkList // 链表类型 { Link head,tail; // 分别指向线性链表中的头结点和最后一个结点 int len; // 指示线性链表中数据元素的个数 }; typedef LinkList polynomial; //具有实用意义的线性链表的24个基本操作 Status MakeNode(Link &p,ElemType e) { // 分配由p指向的值为e的结点，并返回OK；若分配失败。则返回ERROR p=(Link)malloc(sizeof(LNode)); if(!p) return ERROR; p->data=e; return OK; } void FreeNode(Link &p) { // 释放p所指结点 free(p); p=NULL; } Status InitList(LinkList &L) { // 构造一个空的线性链表 Link p; p=(Link)malloc(sizeof(LNode)); // 生成头结点 if(p) { p->next=NULL; L.head=L.tail=p; L.len=0; return OK; } else return ERROR; } Status ClearList(LinkList &L) { // 将线性链表L重置为空表，并释放原链表的结点空间 Link p,q; if(L.head!=L.tail)// 不是空表 { p=q=L.head->next; L.head->next=NULL; while(p!=L.tail) { p=q->next; free(q); q=p; } free(q); L.tail=L.head; L.len=0; } return OK; } Status DestroyList(LinkList &L) { // 销毁线性链表L，L不再存在 ClearList(L); // 清空链表 FreeNode(L.head); L.tail=NULL; L.len=0; return OK; } Status InsFirst(LinkList &L,Link h,Link s) // 形参增加L,因为需修改L { // h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前 s->next=h->next; h->next=s; if(h==L.tail) // h指向尾结点 L.tail=h->next; // 修改尾指针 L.len++; return OK; } Status DelFirst(LinkList &L,Link h,Link &q) // 形参增加L,因为需修改L { // h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。 // 若链表为空(h指向尾结点)，q=NULL，返回FALSE q=h->next; if(q) // 链表非空 { h->next=q->next; if(!h->next) // 删除尾结点 L.tail=h; // 修改尾指针 L.len--; return OK; } else return FALSE; // 链表空 } Status Append(LinkList &L,Link s) { // 将指针s(s->data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的 // 一串结点链接在线性链表L的最后一个结点之后,并改变链表L的尾指针指向新 // 的尾结点 int i=1; L.tail->next=s; while(s->next) { s=s->next; i++; } L.tail=s; L.len+=i; return OK; } Position PriorPos(LinkList L,Link p) { // 已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置 // 若无前驱，则返回NULL Link q; q=L.head->next; if(q==p) // 无前驱 return NULL; else { while(q->next!=p) // q不是p的直接前驱 q=q->next; return q; } } Status Remove(LinkList &L,Link &q) { // 删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点 Link p=L.head; if(L.len==0) // 空表 { q=NULL; return FALSE; } while(p->next!=L.tail) p=p->next; q=L.tail; p->next=NULL; L.tail=p; L.len--; return OK; } Status InsBefore(LinkList &L,Link &p,Link s) { // 已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前， // 并修改指针p指向新插入的结点 Link q; q=PriorPos(L,p); // q是p的前驱 if(!q) // p无前驱 q=L.head; s->next=p; q->next=s; p=s; L.len++; return OK; } Status InsAfter(LinkList &L,Link &p,Link s) { // 已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后， // 并修改指针p指向新插入的结点 if(p==L.tail) // 修改尾指针 L.tail=s; s->next=p->next; p->next=s; p=s; L.len++; return OK; } Status SetCurElem(Link p,ElemType e) { // 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值 p->data=e; return OK; } ElemType GetCurElem(Link p) { // 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 return p->data; } Status ListEmpty(LinkList L) { // 若线性链表L为空表，则返回TRUE，否则返回FALSE if(L.len) return FALSE; else return TRUE; } int ListLength(LinkList L) { // 返回线性链表L中元素个数 return L.len; } Position GetHead(LinkList L) { // 返回线性链表L中头结点的位置 return L.head; } Position GetLast(LinkList L) { // 返回线性链表L中最后一个结点的位置 return L.tail; } Position NextPos(Link p) { // 已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置 // 若无后继，则返回NULL return p->next; } Status LocatePos(LinkList L,int i,Link &p) { // 返回p指示线性链表L中第i个结点的位置，并返回OK，i值不合法时返回ERROR // i=0为头结点 int j; if(i<0||i>L.len) return ERROR; else { p=L.head; for(j=1;j<=i;j++) p=p->next; return OK; } } Position LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType)) { // 返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置， // 若不存在这样的元素，则返回NULL Link p=L.head; do p=p->next; while(p&&!(compare(p->data,e))); // 没到表尾且没找到满足关系的元素 return p; } Status ListTraverse(LinkList L,void(*visit)(ElemType)) { // 依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 Link p=L.head->next; int j; for(j=1;j<=L.len;j++) { visit(p->data); p=p->next; } printf("\n"); return OK; } Status OrderInsert(LinkList &L,ElemType e,int (*comp)(ElemType,ElemType)) { // 已知L为有序线性链表，将元素e按非降序插入在L中。（用于一元多项式） Link o,p,q; q=L.head; p=q->next; while(p!=NULL&&comp(p->data,e)<0) // p不是表尾且元素值小于e { q=p; p=p->next; } o=(Link)malloc(sizeof(LNode)); // 生成结点 o->data=e; // 赋值 q->next=o; // 插入 o->next=p; L.len++; // 表长加1 if(!p) // 插在表尾 L.tail=o; // 修改尾结点 return OK; } Status LocateElem(LinkList L,ElemType e,Position &q,int(*compare)(ElemType,ElemType)) { // 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中 // 第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数 // compare()取值>0的元素的前驱的位置。并返回FALSE。（用于一元多项式） Link p=L.head,pp; do { pp=p; p=p->next; }while(p&&(compare(p->data,e)<0)); // 没到表尾且p->data.expn<e.expn if(!p||compare(p->data,e)>0) // 到表尾或compare(p->data,e)>0 { q=pp; return FALSE; } else // 找到 { q=p; return TRUE; } } #define DestroyPolyn DestroyList #define PolynLength ListLength Status OrderInsertMerge(LinkList &L,ElemType e,int(* compare)(term,term)) { // 按有序判定函数compare()的约定，将值为e的结点插入或合并到升序链表L的适当位置 Position q,s; if(LocateElem(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 OK; } else // 生成该指数项并插入链表 if(MakeNode(s,e)) // 生成结点成功 { InsFirst(L,q,s); return OK; } else // 生成结点失败 return ERROR; } int cmp(term a,term b) // CreatPolyn()的实参 { // 依a的指数值<、=或>b的指数值，分别返回-1、0或+1 if(a.expn==b.expn) return 0;