数据结构课件第二章线性表2

1、 链表游标链表游标（iterator）是一种用于遍历链表的全部元）是一种用于遍历链表的全部元素的对象。从素的对象。从first出发，很容易遍历链表的全部元素，出发，很容易遍历链表的全部元素，为什么还需要游标呢？为什么还需要游标呢？ 设链表设链表L的元素都是整型数，考虑下列操作：的元素都是整型数，考虑下列操作：(1) 打印打印L中的所有元素。中的所有元素。(2) 计算计算L中所有元素的最大值、最小值和平均值。中所有元素的最大值、最小值和平均值。(3) 计算计算L中所有元素的和与积。中所有元素的和与积。(4) 求求L中满足谓词中满足谓词P(x)的元素（例如，的元素（例如，P(x)为：为：x是是某个

2、整数的平方）。某个整数的平方）。(5) 求求L中的元素中的元素x，使得对于某个函数，使得对于某个函数f，f(x)达到最达到最大值。大值。(6) 所有这些操作都需要遍历链表中的全部元素，而且所有这些操作都需要遍历链表中的全部元素，而且必须作为链表类的成员函数实现。如果链表基于模板必须作为链表类的成员函数实现。如果链表基于模板定义，这些操作都将是定义，这些操作都将是List的成员函数。这将的成员函数。这将导致以下问题：导致以下问题：(1)模板类模板类List的全部操作最好独立于的全部操作最好独立于Type的的实例化类型。然而，对某些实例化类型有意义的实例化类型。然而，对某些实例化类型有意义的操作对

3、另外一些实例化类型却是无意义的。（如：操作对另外一些实例化类型却是无意义的。（如：int/rectangle）(2)List的操作太多，导致类的定义很不紧凑，的操作太多，导致类的定义很不紧凑，难以理解，影响软件质量。难以理解，影响软件质量。(3)即使可由用户将新的成员函数加入类中，用户还即使可由用户将新的成员函数加入类中，用户还需要掌握链表结构，而掌握复杂的结构将增加用需要掌握链表结构，而掌握复杂的结构将增加用户的负担。户的负担。这启发我们将遍历（这启发我们将遍历（traversal）移到）移到List定义之外。定义之外。进一步观察，以上操作都不改动链表内容，但需进一步观察，以上操作都不改动链

4、表内容，但需要访问要访问List和和ListNode的私有数据成员。的私有数据成员。为此，我们不是将这些操作都声明为为此，我们不是将这些操作都声明为List和和ListNode的友元，而是定义第三个类的友元，而是定义第三个类ListIterator。ListIterator处理遍历链表的细节并对外提处理遍历链表的细节并对外提供链表中元素的值。供链表中元素的值。enum Boolean FALSE, TRUE;template class List;template class ListIterator;template class ListNode /结点定义结点定义friend class

5、List;friend class ListIterator;private: Type data; ListNode *link;下面是新的链表和链表游标定义下面是新的链表和链表游标定义: :template class List /链表定义链表定义friend class ListIterator;public: List( ) first = 0; / 表处理操作表处理操作 private: ListNode *first;template class ListIterator /游标定义游标定义public: ListIterator(const List& a): list(a),

6、current(a.first) ; / 与链表a关联，指向a的第一个结点 Boolean NotNull( ); Boolean NextNotNull( ); Type* First( ); Type* Next( );private: const List& list;/ 引用一个已有链表 ListNode* current;/ 指向表list中的结点;下面是下面是ListIterator的成员函数定义的成员函数定义： template Boolean ListIterator:NotNull( ) / 检查当前结点是否非空 if (current) return TRUE; else

7、return FALSE;template Boolean ListIterator:NextNotNull( ) / 检查当前结点的下一个结点是否非空 if (current & currentlink) return TRUE; else return FALSE;template Type* ListIterator:First( ) / 返回list第一个元素 if (list.first) return &list.firstdata; else return 0;template Type* ListIterator:Next( ) / 返回当前元素的下一个元素的指针 if (cu

8、rrent ) current = currentlink; if (current ) return ¤tdata; return 0;通过游标可以很方便地实现求整数链表所有元素之和通过游标可以很方便地实现求整数链表所有元素之和的操作，如下所示：的操作，如下所示：int sum(const List& a) ListIterator ai(a); / 游标ai 和链表a关联 if (! ai.NotNull( ) return 0; / 空表 int retvalue = *ai.First( ); / 第一个元素 while (ai.NextNotNull( )/ 若存在下一个

9、元素, 取 /其值并加入总和 retvalue += *ai.Next( ); return retvalue; 注意，函数注意，函数sum不需要访问不需要访问ListNode或或List的私有数据成员的私有数据成员。 也可以用私有变量也可以用私有变量current和上述四个公共成员函和上述四个公共成员函数扩展数扩展List，但当需要从不同角度遍历同一个但当需要从不同角度遍历同一个链表时，这种方法不如用若干个游标对象灵活。链表时，这种方法不如用若干个游标对象灵活。 fisrtpqqqp pqp pp pqfisrt【例例2-3】单链表的逆转单链表的逆转（p指向的结点插入指向的结点插入q指向的结

10、点之前）指向的结点之前）template Void List :Invert( )/ A chain x is inverted so that if x=(a1,an),/then, after execution, x=(an, , a1). ListNode *p = first, *q = null; /q trails p while (p) ListNode *s = p; / s point to current node p = plink; /p moves to next node slink = q; /link q to preceding node q=s； /q p

11、oint to the head of new linked list first = q;通过演示观察算法执行过程通过演示观察算法执行过程template void List:Concatenate(List b) / *this=(a1,., am)，b = (b1,., bn)，m, n 0, /生成新的*this = (a1,., am, b1,., bn) if (!first) first = b.first; return; else for (ListNode *p=first; plink; p=plink ; /无循环体 plink = b.first; 【例例2-4】两个

12、单链表的连接两个单链表的连接假设不存在数据成员假设不存在数据成员last，Cancatenate将两个链表连接将两个链表连接为一个，其计算时间与第一个链表的长度成线性关系为一个，其计算时间与第一个链表的长度成线性关系【例例2-5】试编写在带头结点的单链表中删除（一试编写在带头结点的单链表中删除（一个）最小值结点的算法。个）最小值结点的算法。LinkedList Delete(LinkedList L)L是带头结点的单链表，本算法删除其最小值结点。是带头结点的单链表，本算法删除其最小值结点。 p=L-link； p为工作指针为工作指针,指向待处理的结点。指向待处理的结点。 q=p； q指向最小值

13、结点，初始为第一个结点。指向最小值结点，初始为第一个结点。 while（p-link!=null） if（p-link-data-data）q=p-link; 记录最小值结点记录最小值结点 p=p-link； 指针后移。指针后移。 q-data=q-link-data； q结点与其后一结点交换值结点与其后一结点交换值 q-link=q- link-link； 从链表上删除最小值结点从链表上删除最小值结点 free(q-link)； 释放最小值结点空间释放最小值结点空间结束算法结束算法delete。通过演示观察算法执行过程通过演示观察算法执行过程 template struct LinkNode

14、 T data; / /结点数据结点数据 CircLinkNode *link; /; /结点链接指针结点链接指针 CircLinkNode (CircLinkNode *ptr=NULL): link(next) CircLinkNode (T d, CircLinkNode *next=NULL): data(d); link() ; template class CircList public: CircList ( T& x); /构造函数构造函数 CircList ( CircList & L); /复制构造函数复制构造函数 CircList ( ); /析构函数析构函数 int L

15、ength ( ) const; /求表长求表长 Bool IsEmpty ( ) return firstlink = first; /判断表空判断表空 CircListNode *getHead () const； void setHead (CircListNode *p) CircListNode Search ( const T & value ); /查找表中结点查找表中结点 CircListNode Locate ( int i ); /查找表中第查找表中第i i个结点个结点 T getData ( int i ); /返回当前结点的值返回当前结点的值 void setData(

16、 (int i, , T& x) ) void Insert ( int i, T & x ); /插入新结点插入新结点 void Remove (int i, T & x ); /删除结点删除结点private: CircListNode *first, *last;在表尾插入新结点在表尾插入新结点在表头和表尾插入新结点非常方便在表头和表尾插入新结点非常方便 #include #include “CircList.h”void Josephus (CircList js, int n, int m ) CircLinkNode *p = js.gethead( ), *pre=NULL; f

17、or ( int i=0; in-1; i+ ) /执行执行n-1次次 for ( int j=0; jlink; cout “Delete person ” link = p-link; delete p; /删去删去 p=pre-link; void main ( ) CircList clist; int n, m; cout n m; for ( int i=1; i=n; i+ ) clist.insert (i); /形成约瑟夫环形成约瑟夫环 Josephus (clist,n, m); /解决约瑟夫问题解决约瑟夫问题struct Term float coef; int exp;

18、 Term *link; Term( float c, int e, Term *next = NULL ) coef = c; exp = e; link = next; Term *InsertAfter(float c, int e); class Polynomialpublic: Polynomial () /构造函数 Polynomial (Polynomial &R) /复制构造函数 int maxOrder(); /求最大阶 Term *getHead() /取表头Private: ; AH = 1 - 10 x6 + 2x8 +7x14BH = - x4 + 10 x6 -

19、3x10 + 8x14 +4x18初始化；初始化；While ( (两个链都没处理完两个链都没处理完) ) if ( (指针指向当前节点的指数项相同指针指向当前节点的指数项相同) ) 系数相加，在系数相加，在C链中添加新的节点；链中添加新的节点； A、B链的指针均前移；链的指针均前移； else 以指数小的项的系数添入以指数小的项的系数添入C链中的新节点；链中的新节点； 指数小的相应链指针前移；指数小的相应链指针前移； While( (A链处理完链处理完) ) 顺序处理顺序处理B链；链； While( (B链处理完链处理完) ) 顺序处理顺序处理A链；链； 算法算法-10 02 13 35 4

20、2 A-10 03 12 24 B-10Cq1q2 多项式多项式 2 + 3x + 5x3 + 2x4 3 + 2x + 4x2 相加，结果为：相加，结果为：5 + 5x + 4x2 + 5x3 + 2x4 -10 02 13 35 42 A-10 03 12 24 B-10Cq1q205 -10 02 13 35 42 A-10 03 12 24 B-10Cq1q205 15 -10 02 13 35 42 A-10 03 12 24 B-10Cq1q205 15 24 算法（不附加任何新的结点）算法（不附加任何新的结点）：-10 02 13 35 42 pa-10 03 12 24 pbp

21、cppc：结果链的最后一个结点：结果链的最后一个结点p： 如果删除结点，则删除如果删除结点，则删除p指向的结点指向的结点-10 02 13 35 42 ahpa-10 03 12 24 pbpcp-10 02 13 35 42 pa-10 03 12 24 pbpcpah-10 05 13 35 42 pa12 24 pbpcp-10 02 13 35 42 pa03 12 24 pbpcpahah-10 05 13 35 42 12 24 pbpahpapc-10 05 15 35 42 24 pahpapcpb-10 05 13 35 42 24 pahpapcpb-10 05 13 35 42 24 pahpapcpb算法算法-10 05 13 35 42 24 pahpapcpb-10 05 13 35 42 24 pahpapcpb 分析：分析： 设设A有有m