调用5的部分函数
typedef struct LNode { ElemType data; LNode *next; }*Link,*Position; struct LinkList { Link head, tail;//分别指向线性链表中的头结点和最后一个结点 int len;//指示线性链表中数据元素的个数 }; void MakeNode(Link &p, ElemType &e) { //分配由p指向的值为e的结点。若分配失败，则退出 p = (Link)malloc(sizeof(LNode)); if (!p) { exit(ERROR); } p->data = e; } void FreeNode(Link &p) { //释放p所指结点 free(p); p = NULL; } void InitList(LinkList &L) { //构造一个空的线性链表L Link p; p = (Link)malloc(sizeof(LNode));//生成头结点 if (p) { p->next = NULL; L.head = L.tail = p; L.len = 0; } else { exit(ERROR); } } void 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; } } } void DestroyList(LinkList &L) { //销毁线性表 ClearList(L); FreeNode(L.head); L.tail = NULL; L.len = 0; } void InsFirst(LinkList &L, Link h, Link s) { //h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前 //h = L.head->next; s->next = h->next; h->next = s; if (h == L.tail)//h指向尾结点 { L.tail = h->next;//修改尾指针 } L.len++; } Status DelFirst(LinkList &L, Link h, Link &q) { //h指向L的一个结点，把h当做头结点，删除链表中的第一个结点，并以q返回 //若链表为空(h指向尾结点)，q=NULL，返回FALSE //h = L.head; q = h->next; if (q)//链表非空 { h->next = q->next; if (!h->next)//删除尾结点 { L.tail = h;//修改尾指针 } L.len--; return OK; } else { return FALSE;//链表空 } } void 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; } Position PriorPos(LinkList L, Link p) { //已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置。若无前驱，则返回NULL Link q; q = L.head->next; if (p == q)//无前驱 { 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; //Link n; if (L.len == 0)//空表 { q = NULL; return FALSE; } while (p->next != NULL) { //n = p; p = p->next; } q = L.tail; //n->next = NULL; p->next = NULL; //L.tail = n; L.tail = p; L.len--; return OK; } void 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++; } void 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++; } void SetCurElem(Link p, ElemType e) { //已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值 p->data = e; } ElemType GetCurElem(Link p) { //已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 return p->data; } Status ListEmpty(LinkList L) { //判断表空 if (L.len) return FALSE; else return TRUE; } int ListLength(LinkList 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指向线性链表中的一个结点，返回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) { p = L.head; } else if (i<0 || i>L.len) { return ERROR; } else { p = L.head->next; for (j = 1; j < i; j++) { p = p->next; } return OK; } } Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { //返回线性链表中第1个与e满足函数compare()判定关系的元素的位置 //若不存在这样的元素，则返回NULL Link p = L.head; do { p = p->next; } while (p && !(compare)(p->data,e));//没找到表尾且没找到满足关系的元素 return p; } void ListTraverse(LinkList L, void(*visit)(ElemType)) { //依次对L的每个数据元素调用函数visit() Link p = L.head->next; int j; for (j = 1; j <= L.len; j++) { visit(p -> data); p = p->next; } printf("\n"); } void 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++; if (!p)//插在表尾 L.tail = o; } 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<e if (!p || compare(p->data, e))//到表尾或compare(p->data,e)>0 { q = pp; return FALSE; } else//找到 { q = p; return TRUE; } } Status ListInsert_L(LinkList &L, int i, ElemType e) { //在带头结点的单链线性表的第i个元素之前插入e Link h, s; if (LocatePos(L, i - 1, h)) return ERROR;//i值不合法 MakeNode(s, e);//结点分配失败则退出 InsFirst(L, h, s);//对于从第i个结点开始的链表，第i-1个结点是它的头结点 return OK; } void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int(*compare)(ElemType, ElemType)) { //已知单链线性表La和Lb的元素按值非递减排列。 //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列 Link ha, hb, pa, pb, q; ElemType a, b; InitList(Lc);//存储空间分配失败则退出 ha = GetHead(La);//ha，hb分别指向La和Lb的头结点 hb = GetHead(Lb); pa = NextPos(ha);//pa和pb分别指向La和Lb的首元结点 pb = NextPos(hb); while (pa && pb)//La和Lb非空 { a = GetCurElem(pa);//a和b为两表中当前比较元素（第i个元素） b = GetCurElem(pb); if (compare(a, b) <= 0)//a<=b { DelFirst(La, ha, q);//移去La的首元结点并以q返回 q->next = NULL;//将q的next域赋值NULL，以便调用Append() Append(Lc, q);//将q结点接在Lc的尾部 pa = NextPos(ha);//pa指向La新的首元结点 } else//a>b { DelFirst(Lb, hb, q);//移去Lb的首元结点并以q返回 q->next = NULL;//将q的next域赋值NULL，以便调用Append() Append(Lc, q);//将q结点接在Lc的尾部 pb = NextPos(hb);//pb指向Lb新的首元结点 } } if (pa)//La非空 { Append(Lc, pa);//链接La中剩余结点 } else//Lb非空 { Append(Lc, pb);//链接Lb中剩余结点 } free(ha);//销毁La和Lb La.head = La.tail = NULL; La.len = 0; free(hb); Lb.head = Lb.tail = NULL; Lb.len = 0; } int diff(ElemType c1, ElemType c2) { return c1 - c2; } //一元多项式的表示及相加 typedef struct//项的表示，多项式的项座位LinkList的数据元素 { float coef;//系数 int expn;//指数 }term,ElemType;//两个类型名称，term用于本ADT，ElemType为LinkList的数据对象名 typedef LinkList polynomial; #define DestroyPolyn DestroyList #define PolynLength ListLength void 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); } } else//生成该指数项并插入链表 { MakeNode(s, e);//生成结点 InsFirst(L, q, s); } } int cmp(term a, term b)//CreatPolyn()的实参 { //依a的指数值<、=或>b的指数值，分别返回-1，0或1 if (a.expn == b.expn) return 0; else return (a.expn - b.expn) / abs(a.expn - b.expn); } void CreatPolyn(polynomial &P, int m) { //输入m项的系数和指数，建立表示一元多项式的有序链表P Position q, s; term e; int i; InitList(P); printf("请依次输入%d个系数，指数：\n", m); for (i = 1; i <= m; ++i) { //依次输入m个非零项（可按任意顺序） scanf("%f,%d", &e.coef, &e.expn); if (!LocateElem(P, e, q, cmp))//当前链表中不存在该指数项，cmp是实参 { MakeNode(s, e); InsFirst(P, q, s);//生成结点并插入链表 } } } void PrintPolun(polynomial P) { //打印输出一元多项式P Link q; q = P.head->next;//q指向第一个结点 printf("系数 指数\n"); while (q) { printf("%f %d\n", q->data.coef, q->data.expn); q = q->next; } } void AddPolyn(polynomial &Pa, polynomial &Pb) { //多项式假发：Pa=Pa+Pb,并销毁一元多项式Pb Position ha, hb, qa, qb; term a, b; ha = GetHead(Pa);//ha和hb分别指向Pa和Pb的头结点 hb = GetHead(Pb); qa = NextPos(ha);//qa和qb分别指向Pa和Pb中当前结点（现为第1个结点） qb = NextPos(hb); while (!ListEmpty(Pa) && !ListEmpty(Pb)) { //Pa和Pb均非空且ha没指向尾结点(qa!=0) a = GetCurElem(qa);//a和b为两表中当前比较元素 b = GetCurElem(qb); switch (cmp(a,b)) { case -1:ha = qa;//多项式pa中当前结点的指数值小 qa = NextPos(ha);//ha和qa均向后移1个结点 break; case 0:qa->data.coef += qb->data.coef;//两者指数值相等，修改Pa当前结点的系数值 if (qa->data.coef == 0)//删除多项式Pa中当前结点 { DelFirst(Pa, ha, qa); FreeNode(qa); } else { ha = qa; } DelFirst(Pb, hb, qb); FreeNode(qb); qb = NextPos(hb); qa = NextPos(ha); break; case 1:DelFirst(Pb, hb, qb);//多项式Pb中当前结点的指数值小 InsFirst(Pa, ha, qb); ha = ha->next; qb = NextPos(hb); } } if (!ListEmpty(Pb)) { Pb.tail = hb; Append(Pa, qb);//链接Pb中剩余结点 } DestroyPolyn(Pb);//销毁Pb } void AddPolyn1(polynomial &Pa, polynomial &Pb) { //另一种多项式加法的算法：Pa=Pa+Pb，并销毁一元多项式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) { //一元多项式Pa系数取反 Position p; p = Pa.head; while (p->next) { p = p->next; p->data.coef *= -1; } } void SubtractPolyn(polynomial &Pa, polynomial &Pb) { //多项式剪发：Pa=Pa-Pb,并销毁一元多项式Pb Opposite(Pb); AddPolyn(Pa, Pb); } void SubtractPolyn(polynomial &Pa, polynomial &Pb) { //多项式乘法：Pa=Pa*Pb，并销毁一元多项式Pb polynomial Pc; Position qa, qb; term a, b, c; InitList(Pc); qa = GetHead(Pa); qa = qa->next; while (qa) { a = GetCurElem(qa); qb = GetHead(Pb); qb = qb->next; while (qb) { b = GetCurElem(qb); c.coef = a.coef*b.coef; c.expn = a.expn + b.expn; OrderInsertMerge(Pc, c, cmp); qb = qb->next; } qa = qa->next; } DestroyPolyn(Pb);//销毁Pb ClearList(Pa);//将Pa重置为空表 Pa.head = Pc.head; Pa.tail = Pc.tail; Pa.len = Pc.len; }