数据结构及其应用之数据结构讲义Part1

1、数据结构及其应用（用面向对象方法与C描述）8/19/20221第一章 概述研究对象：信息的表示方法、数据的组织方法、操作算法设计意义地位：数据结构算法程序 程序设计的基础 系统软件的核心发展过程：数值计算 非数值计算 建立数学模型 客体及其关系的表示 设计数值计算方法 数据的组织 操作算法的设计 非数值计算应用的发展，促进了数据结构 的研究和发展以及其体系的完善。8/19/20222基本术语数 据：描述客观事物的且能由计算机处理的数 值、字符等符号数据元素：数据的基本单位，在计算机程序中通常 作为一个整体进行考虑和处理（记录、 结点、表目、元素）数 据 项：数据元素的某一属性。数据元素可以由

2、若干数据项组成，数据项可以由若干 更小的款项（组合项、原子项）组成。 数据项又称域、字段关 键 码：能起唯一标识（数据元素）作用的数据项数据结构：一组同类的数据元素、其间的关系及其上的 一组操作所构成的整体，称为一个数据结构8/19/20223数据结构的描述方式逻辑结构：是对数据元素之间逻辑关系（抛开具体的关系含义以及存储方式等）的描述，它可以用一个数据元素的集合和定义在此集合上的几个关系来表示。通常可用图形表示，圆圈表示数据元素，箭头表示关系：物理结构：数据结构在计算机中的具体表示和实现， 又称存储结构E iE i+1数据元素数据元素关系8/19/20224数据结构的分类按逻辑结构分类： 纯

3、集合型结构:数据元素之间除了“同属于一个集合”这一 关系外，别无其他关系 线性结构：数据元素之间存在“一个跟着一个”的序列关系 树型结构：数据元素之间存在“每个元素只能跟着一个元素 但可以有多个元素跟着它”的层次关系 图状结构：任意两个数据元素之间都可能存在关系按存储结构分类： 顺序存储结构 链式存储结构 索引存贮结构8/19/20225基本操作：任一数据结构均有一组相应的基本操作， 有时操作不同，用途迥异（如栈和队列） 常用的基本操作有插入、 删除、查找、 更新、排序等算 法：算法是为了解决给定的问题而规定的一个 有限长的操作步骤序列，则重于解决问题 的方法和步骤。当算法由计算机语言表示 时

4、称为程序（代码）算法设计目标：可维护性 可靠性（正确性、健壮行） 可读性 高效率（时间、空间）8/19/20226第二章 线性表2。1 线性表的逻辑结构 定义：由相同种类的数据元素组成的一个有穷序列称为一个线性表。“一个跟着一个” 符号表示法：L（e1,e2,en） 图形表示法：e2ene18/19/20227其中： ei -表示线性表 L 的第 i 个数据元素 n -表示线性表 L 的表长（n=0） n=0 时的线性表称为空表 ei-1 称为 ei 的前驱，ei+1 称为 ei 的后继线性表的基本操作：（1）初始化（置空表）可由构造函数实现（2）求表长（ Length ）（3）查找或定位（

5、Find ）（4）插入（ Insert ）（5）删除（ Remove ）（6）排序（ Sort ）（7）判空（ IsEmpty）8/19/202282.2 线性表的顺序存储结构 要实现在计算机内表示一个数据结构，要解决两种信息的存贮问题：数据元素本身的存贮数据元素之间关系的存贮定义：利用内存物理结构上的邻接特点，实现线性表 的“一个跟着一个”这一序列关系的存贮方式， 称为线性表的顺序存贮结构，其上的线性表称 为顺序表。顺序表的类定义：利用数组作为顺序表的存储结构， 它被封装在类的私有域中8/19/20229template class SeqList Public: SeqList(int M

6、axSize=defaultSize); SeqList( ) delete data; int Length( ) const return last+1; int Find(Type & x) const; int Insert(Type & x,int i); int Remove(Type & x); int IsEmpty( ) return last = = - 1; int Isfull( ) return last = =MaxSize 1 ; Type & Get( int i ) return i last ? NULL : datai; Private: Type * d

7、ata; / 用数组存放线性表顺序存贮结构 int Maxsize; / 数组大小，但顺序表的长度为 last+1 int last; / last 为表中最后元素的下标，last=-1 时表示空表8/19/202210上述顺序表定义中的数据成员 Maxsize 是为判断顺序表是否为满而设，last 是为便于判断顺序表是否为空、求表长、置空表而设：last=Maxsize 1表示顺序表已满，此时再进行插入操作会导致上溢错误；last=-1 表示顺序表为空表，此时再进行删除操作会导致下溢错误；last+1 代表顺序表的表长；将 last 赋值为 1 可实现置空表操作。由上可知：合理地设置数据成员

8、可大大简化算法的设计及提高算法的效率。顺序表不仅仅包含存放其数据元素的数组，它还应包括一些有用的数据成员，以及相应的操作，它们是一个整体：8/19/202211顺序表之整体概念： data01lastMaxsizelast数组下标 数组变量操作算法Maxsize-1初始化操作插入操作删除操作查找操作排序操作 . . . . . . . . . . . . .8/19/202212顺序表的基本操作（算法）（1）顺序表初始化操作算法template Seqlist:Seqlist(int sz)/构造函数，通过指定参数 sz 定义数组的长度，并将 last 置为 1/即置空表if(sz0)Maxs

9、ize=sz;last=-1; / last+1=0 , 表明表中无元素，空表data=new TypeMaxsize;8/19/202213（2）顺序表查找操作template int Seqlist:Find(Type & x) const/查找 x 在表中位置，若查找成功，函数返回 x 的位置/否则返回1int i=0;while(ilast) return 1;else return i;8/19/202214（3）顺序表插入操作 为了把新元素 x 插入到 i 处，必须把从 i 到 last 的所有元素成块向后移动一个元素位置，以空出第 i 个位置供 x 插入：x231先移动后面元素0

10、i-1ii+1last. . . . . . . . . . . . . .8/19/202215template int Seqlist:Insert(Type & x,int i)/将 x 插入表中 i 处，若成功返回 1 ，否则返回 0if (ilast+1|last=Maxsize-1) return 0;elselast+;for(int j=last;ji;j-) dataj=dataj-1;datai=x;return 1;8/19/202216（4）顺序表删除操作为了删除第 i 个元素，必须把从 i1 到 last 的所有元素向前移动一个元素位置，把第 i 个元素覆盖掉：12.

11、 . .0i-1ii+1last-1last1. . . . . . . . . . .8/19/202217template int Seqlist:Remove(Type & x)/将 x 从表中删除。若 x 在表中并成功删除则返回 1，/否则返回 0int i=Find(x);if (i=0)last-;for (int j=i;j=last;j+) dataj=dataj+1;return 1;return 0;8/19/202218顺序存储结构的优缺点优点：（1）算法简单、可读性好、开发代价低缺点：（1）插入、删除操作时需要移动大量元素， 效率较低；（2）最大表长难以估计，太大了浪费

12、空间， 太小了容易溢出。8/19/202219顺序表应用举例当将两个顺序表作集合考虑时的“并”与“交”操作算法template void Union(Seqlist & LA,Seqlist & LB)/ 合并顺序表 LA 与 LB ，重复元素只留一个，结果在 LA 中。 int n=LA.Length();int m=LB.Length();for (int i=0;i=m-1;i+)Type x=LB.Get(i); / 从顺序表 LB 中取一元素int k=LA.Find(x); / 在顺序表 LA 中查找该元素if (k=-1) / 未找到 LA.Insert( x ,n); / 将该

13、元素追加到 LA 中 n+;8/19/202220template void Intersection( Seqlist & LA,Seqlist & LB)/ 求顺序表 LA 与 LB 的共同元素，结果在 LA 中int n = LA.Length( );int m = LB.Length( );int i = 0;while ( i n )Type x = LA.Get( i ); / 从 LA 中取一元素int k = LB.Find( x ); / 在 LB 中查找该元素if ( k= - 1) / 未找到 LA.Remove( i ); n-; / 则从 LA 中删除该元素else

14、i +;8/19/202221多项式及其运算A(x)=a0 x + a1x +a2x +an-1x + anx =B(x)=b0 x + b1x +b2x +bn-1x +bnx =A(x)+B(x)=实际应用中，上述一元多项式中的很多系数有可能为零，即为稀疏多项式，如下式所示： aixi=0ni012n-1n012n-1n bixii=0 (ai+bi)xni=0iP (x)=1.2+51.3x +3.7x5050101P(x)=ci xi=0neic0=1.2 e0=0c1=51.3 e1=50c2=3.7 e2=1018/19/202222多项式的表示对于稀疏多项式，采用二元组表示法可以

15、大大节省存储空间：（1）将稀疏多项式的每一项用二元组表示客体的表示方法（2）用一顺序表（一维数组）来存放上述的二元组数据的组织方法c0c1cicne0e1eien系数指数. . . . . . . . . .8/19/202223多项式二元组的类定义客体的表示方法class Polynomial; / 多项式类的前视声明class term / 多项式中项（二元组）的类定义friend Polynomial; / 定义 Polynomial 类为 term 类的友元类private :float coef; / 系数int exp; / 指数8/19/202224多项式的类定义数据的表示方法c

16、lass Polynomialpublic :. . . / 成员函数声明（构造、释构、相加等函数）private :int MaxTerms ; /共享空间（顺序表）的最大项数static term termArrayMaxTerms;/存放二元组的数组，存放多个多项式的共享空间static int free ; / 共享空间中自由空间之起始下标int start , finish ; / 多项式在共享空间中的首、尾下标8/19/202225多项式的相加 A(x)=aix B(x)=bjxC(x)=A(x)+B(x)nmi=0j=0e ie jA . Start A . finishB .

17、Start B . finish free MaxTerm-18/19/202226多项式AB算法思路：（1）保留A、B两个多项式，将AB放人C中；（2）开始时 C.start = free；（3）设置两个指针 a 和 b 分别作为 A 与 B 的检测指针，开始时 分别指向 A 与 B 的首项，即： a = A . start ; b = B . start；（4）当两个指针都未超出相应多项式的最末位置时，比较它们所 指示的对应项的指数： 若指数相等，则对应项系数相加，若相加结果不为零，则在 C 中加入一个新项 若指数不等，则把指数小者拷贝到 C 中（5）当两个指针中有一个超出了相应多项式的最

18、末位置，则将另 一个多项式的剩余部分拷贝到 C 中8/19/202227Polynomial Polynomial : Add ( Polynomial B ) Polynomial C; int a = start; int b =B.start; C.start = free; float c;while ( a = finish & b : NewTerm( termArrayb.coef , termArrayb.exp); b+ ; break ; case : NewTerm( termArraya.coef , termArraya.exp); a+ ; for ( ; a =

19、finish ; a+ ) NewTerm( termArraya.coef , termArraya.exp);for ( ; b = B.finish ; b+ ) NewTerm( termArrayb.coef , termArrayb.exp);C.finish=free-1;return C ; 8/19/202228void Polynomial : NewTerm( float c , int e )/ 把一个新的项（二元组 ）追加到多项式 C(x) 中if ( free = MaxTerms )cout “Too many terms in polynomials” endl

20、 ;return ;termArray free . coef = c ;termArray free . exp = e ;free + ;8/19/202229作业： 定义多项式类的求表长、查找、插入、删除、判空表判满表、读取（第 i 个元素）等成员函数，并用这些函数实现前述的两个多项式的相加操作。提示：（1）定义查找指数相等的元素的成员函数（2）仿照前述的顺序表合并操作算法，先从多项式 B 中读取一元素，在 A 中查找有无指数相等元素：若无，则有序插入 A 中；若有，则系数相加：若和为零，则从 A 中删除相应元素；否则用新系数构造新元素，并插入 A 中相应位置8/19/202230稀疏矩

21、阵（Sparse Matrix）数值计算中的顺序表设计 000220015 011000170A=000-6000000003909100000000280000矩阵 A 是一个 6 行 7 列的稀疏矩阵，只有 8 个非零元素，其他均为零。因此用二维数组来存储稀疏矩阵的空间利用率较低，必须考虑对稀疏矩阵的压缩存储表示。8/19/202231稀疏矩阵的三元组表示法：（1）将稀疏矩阵的非零元素用三元组 表示（ 表示稀疏矩阵的 第 row 行、第 column 列的值为 value） 客体的表示方法（2）用一顺序表（一维数组）来存放上述三元组 （每一个三元组即为顺序表的一个数据元素） 并按行优先顺序

22、存放 数据的组织方法template class Tritupleprivate :int row, col;Type value;8/19/202232矩阵A的三元组表示：表下标行(row) 列(col) 值(value)0 03221 06152 11113 15174 23-65 35396 40917 52288/19/202233稀疏矩阵的类声明：template class SparseMatrixpublic: SparseMatrix(int MaxTerms=defaultSize); SparseMatrix() delete smArray; SparseMatrix C

23、ompression(smData); SparseMatrix Transpose(); SparseMatrix Add(SparseMatrix b); SparseMatrix Multiply(SparseMatrix b);private: int Rows, Cols, Terms,MaxTerms; Trituple smArrayMaxTerms;8/19/202234说明： （1）压缩前的稀疏矩阵为 Rows 行, Cols 列的矩阵 smData ，压缩后的稀疏矩阵存放在一维数组 smArray 中，其中的元素为 Trituple 类型的对象。 声明中的 Terms 对应

24、于顺序表定义中的 last， MaxTerms 对应于顺序表定义中的 Maxsize， smArray 对应于顺序表定义中的 data （2）为稀疏矩阵声明了四种操作：压缩（Compression）转置（Transpose）相加（Add）相乘（Multiply）根据实际需要还可以声明其他操作。 （3）数值计算与非数值计算的数据结构中所定义的基本操作有很大的不同8/19/202235稀疏矩阵的转置操作快速转置算法思路：（1）引入两个辅助数组 rowSize 和 rowStart rowSize i 表示稀疏矩阵第 i 列的非零元素个数rowStart i 表示稀疏矩阵第 i 列的第一个（行号最小

25、） 非零元素在转置矩阵的三元组表中的位置。显然应有： rowStart i + rowSize i = rowStart i+1 . . . . . . .共有 rowSize i 个元素8/19/202236 上述公式表示，若已知稀疏矩阵第 i 列的第一个非零元素在转置矩阵的三元组表中的位置 rowStart i , 以及稀疏矩阵第 i 列的非零元素个数 rowSize i , 就可以算出第 i+1 列非零元素在转置矩阵的三元组表中的位置 rowStart i+1 另外，根据转置矩阵的定义可知： rowStart 0 = 0因此： rowStart 1 = rowSize 0 + rowSt

26、art 0 = rowSize 0 rowStart 2 = rowSize 1 + rowStart 1 . . . . . .因此，只要预先统计得到 rowSize i ( i = 0 , 1 , 2 , . . .)就可以得到第 i + 1 列非零元素在转置矩阵的三元组表中的位置8/19/202237template SparseMatrix SparseMatrix:FastTranspos( )/ int *rowSize = new intCols; int *rowStart = new intCols;SparseMatrix b; b.Rows = Cols; b.Cols

27、= Rows; b.Terms = Terms;if (Terms 0 ) for (int i = 0; iCols; i +) rowSizei = 0;for (i=0;iTerms;i+) rowSizesmArrayi.col+;rowStart0=0;for (i=1;iCols;i+) rowStarti=rowStarti-1+rowSizei-1;for (i=0;i= 0 ) 个字符的有限序列通常可记为：S = a0 a1 a2 an-1 其中： 串名S串值引号中的内容n串长，即串中的字符个数（不包括串结束符 0 ）空串 n = 0 的串（但包含串结束符）空白串仅由若干个空

28、格字符组成的串，其长度不为零子串从非空串中连续取出的若干个字符组成的串子串的位置子串的第0个字符在原串中的位置可以认为：串是限制数据元素为字符的顺序表8/19/2022392.5.1 字符串抽象数据类型和类定义class Stringpublic: String(const String &);String(const char *const);String();String() delete ch;int Length() const return curLen；String & operator()(int pos,int len);int operator =(const String

29、& ob) const return strcmp(ch,ob.ch)=0;int operator !=(const String & ob) constreturn strcmp(ch,ob.ch)!=0;int operator ! () const return curLen=0；String & operator = (const String &);String & operator += (const String &);char & operator (int i );int Find(String pat) const;private:int curLen;char * ch

30、;8/19/202240有了上述的串类定义，就可以进行下列操作：String s1; String s2 ( “ Hello World ” );s1 = s2;String s3 ( “ ; nice to here ! ” );s1 + = s3;int len=s1.length();String s4;s4=s1(6,5);If (s1=s2)If (s1!=s2)If (! s1)Char c=s16;s16=w;8/19/202241文本编辑 计算机应用中要涉及大量的文本文件，文本文件由大量的串（行）组成，在某些文本文件（如源程序）中，串（行）长差异 很大，若每行都用等长的串来存贮

31、，则会浪费存贮空间解决的办法之一是建立一个很大的字符数组作为所有串的共享空间串值共享空间，再为每个串建立一个描述子，用于描述该串的长度以及该串在串值共享空间中的位置等信息，并将这些描述子存入一顺序表中，参见下图：8/19/202242 行表(linelist) 串值共享空间（space） MaxSize-1.free行号0 1 2 3 行长 位置行2行3行0行1. . . . . . . . .自由空间起始地址 0串值共享空间String（串）行表Seqlist（顺序表）设计行内字符插入、删除操作算法设计整行插入、删除操作算法8/19/202243第三章 链表顺序表有下列缺点：（1）插入、删除

32、操作时需要移动大量元素， 效率较低；（2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。 因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结构。 定义：用指针来表示数据元素之间关系的存储结构 称之为链式存储结构。8/19/202244定义：用由指针连接起来的一串结点来存储一个线性表 的存储结构称为线性链式存储结构，简称链表。 当每一结点中只有一个指针，并用来表示一个数 据元素到其后继元素之间的接续关系，则称这种 存储结构为单链表。注：此处的结点是指通过指针型变量动态索取到的存储空间. . .firstfirst头指针 指针域 (link) las

33、tlast 尾指针 数据元素域 (data) 空指针结点1头结点结点0结点n-1e0e1en-18/19/202245 上述的单链表表头设置了一头结点，头结点的数据域中可以为空，或者存放一些辅助数据。 设置头结点的目的是为了简化对空表的特殊处理，使得算法更简单、更有效。 对于带头结点的单链表，可以很容易地表示空链表： 头指针 头结点 first last尾指针8/19/202246用模板定义的单链表类template class List; /单链表类的前视声明template class ListNode /链表结点类的定义friend class List ; /将 List 类定义为 L

34、istNode 类的友元public:ListNode( );ListNode(const Type & item);ListNode *NextNode ( ) return link;/后继结点指针void InsertAfter (ListNode * p); /将 *p 结点插入到当前结点之后ListNode * GetNode (const Type & item ,ListNode * next); /创建一个新结点ListNode * RemoveAfter ( ); /删除后继结点private:Type data;ListNode * link;datalink8/19/20

35、2247template class List/单链表类的定义public:List( ) last=first=new ListNode (value,NULL); /构造函数，建立一个空链表List( );void MakeEmpty( );/删除所有元素结点，将链表置为空链表int Length( ) const; /求单链表表长ListNode *Find(Type value); /查找值为 value 的结点ListNode *Find(int i); /查找结点 i , 返回结点 i 的指针int Insert(Type value,int i); /将值为 value 的新结点

36、插入结点 i 之前Type *Remove(int i);/删除结点 iType Get(int i);/读取结点 i 的值private:ListNode *first, *last;/头指针，尾指针8/19/202248ListNode类（链表结点类）的成员函数的实现template void ListNode:ListNode( ):link(NULL)template void ListNode:ListNode(const Type & item)/构造函数，创建一个新结点，该结点的值为 item , 指针域为NULLdata=item;link=NULL;template List

37、Node * ListNode:GetNode(const Type & item, ListNode * next=NULL)/创建一个新结点，该结点的值为 item , 指针域为NULL,并返回/该结点的指针ListNode *newnode=new ListNode(item,next);return newnode;8/19/202249InsertAfter( ) 函数template void ListNode:InsertAfter(ListNode *p)将 p 所指的结点（*p）链接成为当前结点（*this）的后继结点p-link=link; /(1)link=p; /(2)

38、thisdatalinkdatalinkdatalinkpp-link=linklink=p(1)(2)当前结点8/19/202250RemoveAfter( )datalinkdatalinkdatalink 当前结点 要删除的结点template ListNode *ListNode:RemoveAfter()/删除当前结点 ( *this ) 的后继结点,并返回该结点的指针ListNode *tempptr=link; /(1)if (link=NULL) return NULL;link=tempptr-link; /(2)return tempptr;：(1)tempptr=link

39、(2) link=tempptr-linkthis8/19/202251List类（链表类）的成员函数的实现template void List:MakeEmpty( )/ 将当前链表置为空表ListNode *q ;while (first -link != NULL) / 循环删除头结点的后继结点，直到无后继结点为止q=first -link ; first -link=q -link ; delete q ;last=first;/ 最后让 last 指向头结点，完成置空表操作first(1) q=first-link(2) first-link=q-link(最后) last头结点8/

40、19/202252template int List:Insert(Type value,int i);/ 将值为 value 的新数据元素插入到链表中结点 i 之前ListNode *p = Find(i-1);/ 查找结点 i-1if (p=NULL) return 0;/ 结点 i-1 不存在，插入失败ListNode *newnode=GetNode(value,p-link);/ 创建新结点 / 并使新结点指向结点 i (1)if (p-link=NULL) last=newnode;/ 若结点 i 不存在，则新结点将 / 是表尾结点p-link=newnode;/ 让结点 i-1

41、指向新结点，实现插入 (2)return 1; 结点 i-1 结点 i 新结点 pnewnode(1)(2)8/19/202253template Type *List : Remove( int i )/ 删除结点 i ,若成功，则返回该结点的数据元素（地址）， / 否则返回NULLListNode *p= Find(i-1) , *q ; / 查找结点 i-1if ( p=NULL | p-link=NULL) return NULL;/ 若结点 i-1 或者 / 结点 i 不存在，则返回 NULL , 删除失败q=p-link; / (1)p-link=q-link;/ (2)Type

42、value=q-data;if (q=last) last=p;delete q;return &value;结点 i-1 结点 i 结点 i+1 p q (1)(2)8/19/202254template ListNode *List:Find( int i ) / 查找结点 i , 若找到，则返回该结点的指针，否则返回NULLif ( i -1 ) return NULL;if ( i = -1 ) return first;/ 结点 1 即为头结点ListNode *p=first-link;/ p 指向结点0int j=0;while(p!= NULL & jlink;j=j+;ret

43、urn p; 8/19/2022553.1.6 单链表的游标(Iterator)类 在实际应用中经常要对单链表进行打印、统计、检索等需要向后搜索整个链表的操作，因此设计具有光标功能的，能够记住当前位置并能得到其后继结点的游标类是有意义的。 单链表的位置概念：current 是结点 i+1的位置有了单链表结点 i+1 的位置 current ，删除结点 i+1 或在结点 i+1 前插入新结点就会简单得多，无需查找过程。current结点 i结点 i+18/19/202256单链表游标类声明Template class ListIteratorpublic:ListIterator(const L

44、ist & l):list(l),current(l.first) Boolean NotNull( ); / 检查游标结点（指针 current / 所指的结点）是否为不空Boolean NextNotNull ( ); / 检查游标结点的后继结点是 /否为不空Type * First ( );/使游标指向头结点Type * Next ( ); / 使游标指向后继结点private:const List & list;ListNode * current;/游标（指针）8/19/202257单链表游标类成员函数的定义template Boolean ListIterator:NotNull(

45、 )/ 检查游标结点（ current 所指的结点）是否为不空（注：/此处结点不空是指该结点的指针不空）。若不空，则返回真，/ 否则返回假if ( current != NULL ) return True;else return False;template Boolean ListIterator:NextNotNull( )/ 检查游标结点（游标所指的结点）的后继结点是否为不空。/ 若不空，则返回真；否则返回假if ( current != NULL & current-link != NULL ) return True;else return False;8/19/202258tem

46、plate ListNode * ListIterator:First( )/ 使游标指向头结点if ( list.first-link != NULL ）current = list.first; / 若头结点的指针 /域不空，即链表为非空表,则使游标指向头结点else current = NULL; / 否则置空游标 return current;template ListNode * ListIterator:Next( )/ 使游标指向后继结点if ( current != NULL & current-link != NULL )current=current-link;/ 若游标结

47、点及其后继结点都不空，则/ 将游标指向后继结点else current=NULL;/ 否则置空游标return current;8/19/202259游标类应用举例：int sum ( const List &l )/计算 int 型单链表 l 的累加和ListIterator li(l);/定义一个单链表对象 l 及其游标类对象 li ,并 /将游标指向单链表的头结点（由构造函数实现）if ( ! li.nextNotNull() return 0;/空链表，返回 0int retvalue=*li.First();/读取头结点的值，假定头结点的值为 0while ( li.nextNotN

48、ull() retvalue += *li.Next();/若存在后继结点，则循环累加return retvalue;课堂作业：使用游标类求 int 型单链表的最大结点。若单链表为空则返回NULL，否则返回最大结点的位置。8/19/2022603.2 循环链表（Circular List）e0e1en-1 循环链表的定义： （ P82P83）循环链表与单链表不同的是链表中表尾结点的 link 域不是NULL，而是链表头结点的指针（链表指针） firstlast表头结点firstlast空表8/19/202261循环链表（带头结点）的类定义：enum Boolean False,Truetemp

49、late class CircList;/循环链表类的前视声明template class CircListNode/循环链表结点的类定义public:CircListNode (Type d=0, CircListNode * next=NULL):data ( d ), link ( next ) /构造函数，创建一个循环 /链表结点，并初始化数据域为 d , 指针域为 NULLprivate:Type data;CircListNode * link;datalink8/19/202262template class CircListpublic:CircList ( Type value );CircList ( );int Length ( ) const;Boolean IsEmpty ( ) return first-link = first; Boolean Find ( const Type & value );Type GetData ( ) const;/读取游标结点（ *current )的数据域void Firster ( ) current=first; /将 current 指向头结点Boolean First ( );/将 curre