{ int i;
i=space[S].next;
while (i) { cout< void main() { SLList space; ElemType A[]={1,2,3,4}, B[]={2,4,6,8,10}; int S; difference(space,S,4,5,A,B); SLListOutput(space,S); } 2.3.2 循环链表 循环链表(circular linked list)的最后一个结点的指针域指向头结点，整个链表形成一个环。从表中任一结点出发均可找到表中其它结点。循环链表的操作和线性链表基本一致，差别是最后结点的不是next==NULL,而是next等于头指针。 L a b c L [习题2.33③]将线性链表分割为3个循环链表。 void SplitLList(LList L, LList &A, LList &B,LList &C) { LList p,q; A=new LNode; A->next=A; B=new LNode; B->next=B; C=new LNode; C->next=C; p=L->next; while (p) { q=p; p=p->next; if (q->data>='a' && q->data<='z' ||q->data>='A' && q->data<='Z') { q->next=A->next; A->next=q;} else if (q->data>='0' && q->data<='9') { q->next=B->next; B->next=q;} else { q->next=C->next; C->next=q;} } delete L; } 2.3.3 双向链表 双向链表(double linked list)的结点中有两个指针域，分别指向直接后继和直接前趋。在C语言中描述如下： typedef struct DLNode { ElemType data; DLNode *prior,*next; } *DLList; 双向循环链表，如图2.14(c)所示，链表中存有两个环，图2.14(b)所示为只有一个表头结点的空表。 L a b 第15页 在双向链表中，若d为指向表中某一结点的指针，则有 d->next->prior==d->prior->next==d 这个表示式恰当地反映了这种结构的特性。 在双向链表中，有些操作如:ListLength、GetElem、LocateElem等仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入、删除时不同，在双向链表中需同时修改两个方向上的指针，它们的算法分别如算法2.18和2.19所示。 //取双向循环链表的元素的位置指针 DLList ListGetElem(DLList L,int i) { DLList p; int j; p=L; j=0; while (p->next!=L && j // 在双向循环链表中插入第i个结点(参见算法2.18) bool ListInsert(DLList &L, int i,ElemType e) { DLList p,s; p=ListGetElem(L,i-1); if (!p) return false; s=new DLNode; s->data=e; s->next=p->next; p->next->prior=s; p->next=s; s->prior=p; return true; } void ListInsertLast(DLList &L, ElemType e) { DLList s; s=new DLNode; s->data=e; s->prior=L->prior; L->prior->next=s; s->next=L; L->prior=s; } void ListInsertFirst(DLList &L, ElemType e) { DLList s; s=new DLNode; s->data=e; s->next=L->next; L->next->prior=s; s->prior=L; L->next=s; } // 算法 2.19 在双向循环链表中删除元素 bool ListDelete(DLList &L,int i,ElemType &e){ DLList p; p=ListGetElem(L,i); if (!p) return false; e=p->data; p->prior->next=p->next; 第16页 p->next->prior=p->prior; delete p; return true; } //建立双向循环链表 void ListCreate(DLList &L, ElemType a[ ],int n){ int i; L=new DLNode; L->prior=L; L->next=L; for (i=n; i>=1; i--) ListInsertFirst(L,a[i-1]); } //遍历双向循环链表 void ListTraverse(DLList L,void visit(ElemType)) { DLList p; p=L->next; while (p!=L) { visit(p->data); p=p->next; } } [习题2.38] 按访问频度降序排序。 struct ElemType { char name[6+1]; char tele[7+1]; int freq; }; void visit(ElemType e) { cout< void ListCreate(DLList &L,char fn[]) { //建立双向循环链表 ElemType e; ifstream ft; L=new DLNode; L->prior=L; L->next=L; ft.open(fn,ios::nocreate); if (!ft) return; while (!ft.eof()) { ft>>e.name>>e.tele; e.freq=0; ListInsertFirst(L,e); } ft.close(); } DLList ListVisit(DLList &L, char name[7]) { DLList p,q; p=L->next; while (p!=L && strcmp(p->data.name,name)) p=p->next; if (p==L) return NULL; p->data.freq++; q=p; while (q->prior!=L && q->prior->data.freq ElemType e=q->data; q->data=p->data; p->data=e; return q; // 算法2 将p前移，将p插在q->prior与q之间,有可能q==p if (p==q) return p; p->prior->next=p->next; p->next->prior=p->prior; DLList r=q->prior; r->next=p; p->prior=r; p->next=q; q->prior=p; return p; } 第17页 在链表中，结点之间的关系用指针来表示，则数据元素在线性表中的位序概念已淡化，而元素在链表中的位置所代替。因此可从实际应用的角度出发重新定义线性链表及其基本操作。 typedef struct LNode { ElemType data; LNode *next; } *Link,*position; typedef struct { Link head,tail; int len; } LinkList; 基本操作见课本第37-38页。 2.4 一元多项式的表示及相加 本节内容是线性表的一个应用例子。 一元多项式 pn(x)可按升幂写成： ?(p0,p1,p2,?,pn) pn(x)?p0?p1x?p2x2???pnxn 它由n+1个系数唯一确定。它可用一个线性表P来表示： P每一项的指数i隐含在其系数P的序号里。 对于稀疏多项式，如：S(x)系数和指数。 一元n次多项式若只写出系数非0的项，则可写成 其中， ?1?3x10000?2x20000，若储存全部系数则严重浪费内存空间，而应该只存储非零项的 pn(x)?p1xe1?p2xe2???pmxem pi是指数为 ei的项的非零系数，且满足：0 ?e1?e2???em?n，可用线性表 ?(p1,e1),(p2,e2),?,(pm,em)?表示多项式pn(x)。 抽象数据类型一元多项式的定义如下： ADT Polynomial { 数据对象：D={ai|ai∈TermSet,i=1..m} TermSet中的每个元素包含一个表示系数的实数和表示指数的整数。 数据关系：R1={ [例2.4]抽象数据类型Polynomial的实现。基本操作的函数原型说明见课本第42-43页。 [例]一元多项的加法。加法运算规则：两个多项式中所有指数相同的项，对应系数相加，若和不为零，则构成和多项式中的一项；若和为零，则和多项式中没有此项。所有指数不相同的项均复制到“和多项式”中。同时参考课本算法2.23. #include \struct ElemType { float coef; int exp; //coefficient, exponent }; void visit(ElemType e) { cout<<\ #include \ void AddPolynomial(LList &A, LList &B) 第18页
