数据结构和算法习题及答案解析

《数据结构和算法习题及答案解析》由会员分享，可在线阅读，更多相关《数据结构和算法习题及答案解析（48页珍藏版）》请在装配图网上搜索。

1、-第1章 绪论习题1简述以下概念：数据、数据元素、数据项、数据对象、数据构造、逻辑构造、存储构造、抽象数据类型。2试举一个数据构造的例子，表达其逻辑构造和存储构造两方面的含义和相互关系。3简述逻辑构造的四种根本关系并画出它们的关系图。4存储构造由哪两种根本的存储方法实现.5选择题1在数据构造中，从逻辑上可以把数据构造分成 。A动态构造和静态构造 B紧凑构造和非紧凑构造C线性构造和非线性构造 D内部构造和外部构造2与数据元素本身的形式、内容、相对位置、个数无关的是数据的 。A存储构造 B存储实现C逻辑构造 D运算实现3通常要求同一逻辑构造中的所有数据元素具有一样的特性，这意味着 。 A数据具有同

2、一特点B不仅数据元素所包含的数据项的个数要一样，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等4以下说法正确的选项是 。A数据元素是数据的最小单位B数据项是数据的根本单位C数据构造是带有构造的各数据项的集合D一些外表上很不一样的数据可以有一样的逻辑构造5以下与数据的存储构造无关的术语是。A顺序队列 B. 链表C.有序表 D. 链栈6以下数据构造中，是非线性数据构造A树 B字符串 C队 D栈6试分析下面各程序段的时间复杂度。1*=90; y=100;while(y0)if(*100)*=*-10;y-;else *+;2for (i=0; in; i+)for

3、 (j=0; jm; j+)aij=0;3s=0;for i=0; in; i+)for(j=0; jn; j+)s+=Bij;sum=s;4i=1; while(i=n) i=i*3;5*=0;for(i=1; in; i+)for (j=1; j1y=0;while(*(y+1)* (y+1) y+;1O12Om*n3On24Olog3n5因为*+共执行了n-1+n-2+1= n(n-1)/2，所以执行时间为On26O()第2章 线性表1选择题1一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。A110 B108C100 D1202在n个结点的顺序表中，算法

4、的时间复杂度是O(1)的操作是 。A第i个结点1in和求第i个结点的直接前驱2in B在第i个结点后插入一个新结点1inC删除第i个结点1inD将n个结点从小到大排序3向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为 。A8 B63.5C63 D74存储的存储构造所占存储空间 。A分两局部，一局部存放结点值，另一局部存放表示结点间关系的指针B只有一局部，存放结点值C只有一局部，存储表示结点间关系的指针D分两局部，一局部存放结点值，另一局部存放结点所占单元数5线性表假设采用链式存储构造时，要求内存中可用存储单元的地址 。A必须是连续的 B局部地址必须是连续

5、的C一定是不连续的 D连续或不连续都可以6线性表在 情况下适用于使用链式构造实现。A需经常修改中的结点值 需不断对进展删除插入 C中含有大量的结点 中结点构造复杂7单链表的存储密度 。A大于1 B等于1 C小于1 D不能确定8将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。An B2n-1 C2n Dn-19在一个长度为n的顺序表中，在第i个元素1in+1之前插入一个新元素时须向后移动 个元素。An-i Bn-i+1 Cn-i-1 Di(10) 线性表L=(a1，a2,an)，以下说法正确的选项是 。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素

6、的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。(11) 假设指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是 。AO(1) BO(n) CO(n2) DO(nlog2n)(12) 以下说法错误的选项是 。A求表长、定位这两种运算在采用顺序存储构造时实现的效率不比采用链式存储构造时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储构造优于顺序存储构造(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为 。As-ne*t=p+1;p-ne*

7、t=s;B(*p).ne*t=s;(*s).ne*t=(*p).ne*t;Cs-ne*t=p-ne*t;p-ne*t=s-ne*t;Ds-ne*t=p-ne*t;p-ne*t=s; (14) 在双向链表存储构造中，删除p所指的结点时须修改指针 。Ap-ne*t-prior=p-prior;p-prior-ne*t=p-ne*t;Bp-ne*t=p-ne*t-ne*t;p-ne*t-prior=p;Cp-prior-ne*t=p;p-prior=p-prior-prior;Dp-prior=p-ne*t-ne*t;p-ne*t=p-prior-prior;(15) 在双向循环链表中，在p指针所指

8、的结点后插入q所指向的新结点，其修改指针的操作是 。Ap-ne*t=q; q-prior=p;p-ne*t-prior=q;q-ne*t=q;Bp-ne*t=q;p-ne*t-prior=q;q-prior=p;q-ne*t=p-ne*t;Cq-prior=p;q-ne*t=p-ne*t;p-ne*t-prior=q;p-ne*t=q;Dq-prior=p;q-ne*t=p-ne*t;p-ne*t=q;p-ne*t-prior=q;2算法设计题1将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。void

9、MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)pa=La-ne*t; pb=Lb-ne*t; Lc=pc=La; /用La的头结点作为Lc的头结点 while(pa & pb) if(pa-datadata) pc-ne*t=pa;pc=pa;pa=pa-ne*t; else if(pa-datapb-data) pc-ne*t=pb; pc=pb; pb=pb-ne*t; else / 相等时取La的元素，删除Lb的元素 pc-ne*t=pa;pc=pa;pa=pa-ne*t; q=pb-ne*t;delete pb ;pb =q; p

10、c-ne*t=papa:pb; /插入剩余段 delete Lb; /释放Lb的头结点 2将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa = La-ne*t; pb = Lb-ne*t; / 初始化 Lc=pc=La; /用La的头结点作为Lc的头结点 Lc-ne*t = NULL; while ( pa | pb ) if ( !pa ) q = pb; pb = pb-ne*t; e

11、lse if ( !pb ) q = pa; pa = pa-ne*t; else if (pa-data data ) q = pa; pa = pa-ne*t; else q = pb; pb = pb-ne*t; q-ne*t = Lc-ne*t; Lc-ne*t = q; / 插入 delete Lb; /释放Lb的头结点 3两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。void Mi*(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa=la-ne*t;pb=lb-ne*t;设工作指针pa和pb

12、；Lc=pc=La; /用La的头结点作为Lc的头结点while(pa&pb) if(pa-data=pb-data)交集并入结果表中。 pc-ne*t=pa;pc=pa;pa=pa-ne*t; u=pb;pb=pb-ne*t; delete u;elseif(pa-datadata) u=pa;pa=pa-ne*t; deleteu;else u=pb; pb=pb-ne*t; delete u;while(pa) u=pa; pa=pa-ne*t; delete u; 释放结点空间while(pb) u=pb; pb=pb-ne*t; delete u;释放结点空间pc-ne*t=null

13、;置链表尾标记。delete Lb; 注： 本算法中也可对B表不作释放空间的处理4两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集即仅由在A中出现而不在B中出现的元素所构成的集合，并以同样的形式存储，同时返回该集合的元素个数。void DifferenceLinkedList A，B，*nA和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0p=A-ne*t；p和q分别是链表A和B的工作指针。 q=B-ne*t； pre=A；pre为A中p所指结点的前驱结点的指针。whilep!

14、=null & q!=nullifp-datadatapre=p；p=p-ne*t；*n+； A链表中当前结点指针后移。elseifp-dataq-dataq=q-ne*t；B链表中当前结点指针后移。else pre-ne*t=p-ne*t；处理A，B中元素值一样的结点，应删除。 u=p； p=p-ne*t；delete u； 删除结点5设计算法将一个带头结点的单链表A分解为两个具有一样构造的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点链表A的元素类型为整型，要求B、C表利用A表的结点。6设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTy

15、pe Ma* (LinkList L )if(L-ne*t=NULL) return NULL;pma*=L-ne*t; /假定第一个结点中数据具有最大值p=L-ne*t-ne*t;while(p != NULL )/如果下一个结点存在if(p-data pma*-data) pma*=p;p=p-ne*t;return pma*-data;7设计一个算法，通过遍历一趟，将链表中所有结点的方向逆转，仍利用原表的存储空间。void inverse(LinkList &L) / 逆置带头结点的单链表 L p=L-ne*t; L-ne*t=NULL; while ( p) q=p-ne*t; / q

16、指向*p的后继 p-ne*t=L-ne*t; L-ne*t=p; / *p插入在头结点之后 p = q; 8设计一个算法，删除递增有序链表中值大于mink且小于ma*k的所有元素mink和ma*k是给定的两个参数，其值可以和表中的元素一样，也可以不同 。void delete(LinkList &L, int mink, int ma*k) p=L-ne*t; /首元结点 while (p & p-datane*t; /查找第一个值mink的结点 if (p) while (p & p-datane*t; / 查找第一个值 ma*k 的结点 q=pre-ne*t; pre-ne*t=p; /

17、修改指针 while (q!=p) s=q-ne*t; delete q; q=s; / 释放结点空间 /if9p指向双向循环链表中的一个结点，其结点构造为data、prior、ne*t三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。知道双向循环链表中的一个结点，与前驱交换涉及到四个结点p结点，前驱结点，前驱的前驱结点，后继结点六条链。void E*changeLinkedList pp是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。q=p-llink； q-llink-rlink=p；p的前驱的前驱之后继为p p-llink=q-llink；p的前

18、驱指向其前驱的前驱。 q-rlink=p-rlink；p的前驱的后继为p的后继。 q-llink=p；p与其前驱交换 p-rlink-llink=q；p的后继的前驱指向原p的前驱 p-rlink=q；p的后继指向其原来的前驱算法e*change完毕。10长度为n的线性表A采用顺序存储构造，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。题目分析 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动删第i个元素，第i+1至第n个元素要依次前移。此题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头

19、尾两个指针i=1，j=n，从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。void DeleteElemType A ，int nA是有n个元素的一维数组，本算法删除A中所有值为item的元素。i=1；j=n；设置数组低、高端指针下标。whileij whileij & Ai!=itemi+；假设值不为item，左移指针。ifijwhileij & Aj=itemj-；假设右端元素值为item，指针左移ifidata;top=top-link； Btop=top-link;*=top-link； C*=top;top=top-link； D*=t

20、op-link；5设有一个递归算法如下 int fact(int n) /n大于等于0 if(n=0) return 1; else return n*fact(n-1); 则计算fact(n)需要调用该函数的次数为。An+1Bn-1C nD n+26栈在中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有7为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑构造应该是。A队列 B栈 C 线性表 D有序表8设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S

21、，一个元素出栈后即进入Q，假设6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是。A2 B3 C4 D 69在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为。 Atop不变 Btop=0 Ctop- Dtop+10设计一个判别表达式中左，右括号是否配对出现的算法，采用数据构造最正确。A线性表的顺序存储构造B队列C. 线性表的链式存储构造 D. 栈11用方式存储的队列，在进展删除运算时。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改12循环队列存储在数组A0.m中

22、，则入队时的操作为。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 13最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front14栈和队列的共同点是。A. 都是先进先出 B. 都是先进后出C. 只允许在端点处插入和删除元素 D. 没有共同点15一个递归算法必须包括。A. 递归局部B. 终止条件和递归局部C. 迭代局部D. 终止

23、条件和迭代局部2回文是指正读反读均一样的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)根据提示，算法可设计为：/以下为顺序栈的存储构造定义*define StackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判断t字符向量是否为回文，假设是，返回1，否则返回0SeqStack s

24、;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量长度for ( i=0; ilen/2; i+)/将一半字符入栈Push( &s, ti);while( !EmptyStack( &s)/ 每弹出一个字符与相应字符比较temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等则返回0else i+;return 1 ; / 比较完毕均相等则返回 13设从键盘输入一整数的序列：a1, a2, a3，an，试编写算法实现：用栈构造存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

25、算法应对异常情况入栈满等给出相应的信息。*define ma*size 栈空间容量void InOutS(int sma*size) /s是元素为整数的栈，本算法进展入栈和退栈操作。 int top=0; /top为栈顶指针，定义top=0时为栈空。for(i=1; i=n; i+) /n个整数序列作处理。 scanf(%d,&*); /从键盘读入整数序列。if(*!=-1) / 读入的整数不等于-1时入栈。if(top=ma*size-1)printf(栈满n);e*it(0);else s+top=*; /*入栈。else /读入的整数等于-1时退栈。 if(top=0)printf(栈空

26、n);e*it(0); else printf(出栈元素是%dn,stop-)； /算法完毕。4从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入完毕，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。 题目分析逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进展相应运算，结果再压入OPND栈。这个过程一直进展到读出表达式完毕符$，这时OPND栈中只有一个数，就是结果。float

27、e*pr( )/从键盘输入逆波兰表达式，以$表示输入完毕，本算法求逆波兰式表达式的值。float OPND30; / OPND是操作数栈。init(OPND); /两栈初始化。float num=0.0; /数字初始化。 scanf (%c,&*);/*是字符型变量。while(*!=$) switch case0=*=0&*=0&*j)printf(序列非法n)；e*it(0); i+; /不管Ai是I或O，指针i均后移。if(j!=k) printf(序列非法n)；return(false);else printf(序列合法n)；return(true); /算法完毕。 算法讨论在入栈出栈

28、序列即由I和O组成的字符串的任一位置，入栈次数I的个数都必须大于等于出栈次数即O的个数，否则视作非法序列，立即给出信息，退出算法。整个序列即读到字符数组中字符串的完毕标记0，入栈次数必须等于出栈次数题目中要求栈的初态和终态都为空，否则视为非法序列。(6假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。算法如下：/先定义链队构造:typedef struct queuenodeDatatype data;struct queuenode *ne*t;QueueNode; /以上是结点类型的定义typedef s

29、tructqueuenode *rear;LinkQueue; /只设一个指向队尾元素的指针(1)置空队void InitQueue( LinkQueue *Q) /置空队：就是使头结点成为队尾元素QueueNode *s;Q-rear = Q-rear-ne*t;/将队尾指针指向头结点while (Q-rear!=Q-rear-ne*t)/当队列非空，将队中元素逐个出队s=Q-rear-ne*t;Q-rear-ne*t=s-ne*t;free(s);/回收结点空间(2)判队空int EmptyQueue( LinkQueue *Q) /判队空/当头结点的ne*t指针指向自己时为空队retur

30、n Q-rear-ne*t-ne*t=Q-rear-ne*t;(3)入队void EnQueue( LinkQueue *Q, Datatype *) /入队/也就是在尾结点处插入元素QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申请新结点p-data=*; p-ne*t=Q-rear-ne*t;/初始化新结点并链入Q-rear-ne*t=p;Q-rear=p;/将尾指针移至新结点(4)出队Datatype DeQueue( LinkQueue *Q)/出队,把头结点之后的元素摘下Datatype t;QueueNode *p;if

31、(EmptyQueue( Q )Error(Queue underflow);p=Q-rear-ne*t-ne*t; /p指向将要摘下的结点*=p-data; /保存结点中数据if (p=Q-rear)/当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点Q-rear = Q-rear-ne*t; Q-rear-ne*t=p-ne*t;elseQ-rear-ne*t-ne*t=p-ne*t;/摘下结点pfree(p);/释放被删结点return *;7假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag= 0和tag = 1来区别在队头指针(front)和队尾指针(r

32、ear)相等时，队列状态为空还是满。试编写与此构造相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义*include template classQueue /循环队列的类定义public: Queue (int=10 ); Queue ( ) delete Q;void EnQueue (Type& item );Type DeQueue ();TypeGetFront ( );void MakeEmpty ( ) front = rear = tag = 0;/置空队列intIsEmpty ( )const return front = rear & tag

33、= 0;/判队列空否intIsFull ( )const return front = rear & tag = 1;/判队列满否private:intrear, front, tag;/队尾指针、队头指针和队满标志Type *Q;/存放队列元素的数组intm;/队列最大可容纳元素个数构造函数template Queue: Queue ( intsz ) : rear (0),front (0), tag(0), m (sz) /建立一个最大具有m个元素的空队列。Q =new Typem;/创立队列空间assert ( Q != 0 );/断言:动态存储分配成功与否插入函数template v

34、oidQueue :EnQueue ( Type &item) assert ( ! IsFull ( ) );/判队列是否不满，满则出错处理rear = ( rear + 1 ) % m;/队尾位置进1, 队尾指针指示实际队尾位置Qrear = item;/进队列tag = 1;/标志改1，表示队列不空删除函数template Type Queue :DeQueue ( ) assert ( ! IsEmpty ( ) );/判断队列是否不空，空则出错处理front =( front + 1 ) % m;/队头位置进1, 队头指针指示实际队头的前一位置tag = 0;/标志改0, 表示栈不满

35、return Qfront;/返回原队头元素的值读取队头元素函数template Type Queue :GetFront ( ) assert ( ! IsEmpty ( ) );/判断队列是否不空，空则出错处理return Q(front + 1) % m;/返回队头元素的值(8如果允许在循环队列的两端都可以进展插入和删除操作。要求： 写出循环队列的类型定义； 写出从队尾删除和从队头插入的算法。题目分析 用一维数组 v0.M-1实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队

36、空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向开展，队尾端入队向下标大的方向开展。1*define M队列可能到达的最大长度typedefstruct elemtp dataM;int front,rear; cycqueue;2elemtp delqueue ( cycqueue Q) /Q是如上定义的循环队列，本算法实现从队尾删除，假设删除成功，返回被删除元素，否则给出出错信息。 if (Q.front=Q.rear) printf(队列空); e*it(0); Q.rear=(Q.rear-1+M)%M; /修改队尾指针。return(Q.data(Q.rea

37、r+1+M)%M); /返回出队元素。/从队尾删除算法完毕void enqueue (cycqueue Q, elemtp *)/ Q是顺序存储的循环队列，本算法实现从队头插入元素*。if (Q.rear=(Q.front-1+M)%M) printf(队满; e*it(0);) Q.dataQ.front=*; /* 入队列Q.front=(Q.front-1+M)%M; /修改队头指针。/ 完毕从队头插入算法。9Ackermann函数定义如下: 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。 写出计算Ack(m,n)的非递归算法。int Ack(int

38、m,n) if (m=0) return(n+1);elseif(m!=0&n=0) return(Ack(m-1,1);elsereturn(Ack(m-1,Ack(m,m-1); /算法完毕1Ack(2,1)的计算过程 Ack(2,1)=Ack(1,Ack(2,0) /因m0,n0而得 =Ack(1,Ack(1,1) /因m0,n=0而得 =Ack(1,Ack(0,Ack(1,0) / 因m0,n0而得 = Ack(1,Ack(0,Ack(0,1) / 因m0,n=0而得 =Ack(1,Ack(0,2) / 因m=0而得 =Ack(1,3) / 因m=0而得 =Ack(0,Ack(1,2)

39、 /因m0,n0而得 = Ack(0,Ack(0,Ack(1,1) /因m0,n0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0) /因m0,n0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1) /因m0,n=0而得 = Ack(0,Ack(0,Ack(0,2) /因m=0而得 = Ack(0,Ack(0,3) /因m=0而得 = Ack(0,4) /因n=0而得 =5 /因n=0而得2int Ackerman( int m, int n) int akmMN;int i,j;for(j=0;jN;j+) akm0j;=j+1;for(i=1;im;i+) akmi

40、0=akmi-11;for(j=1;jN;j+) akmij=akmi-1akmij-1; return(akmmn); /算法完毕10f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现以下运算的递归算法：求链表中的最大整数；求链表的结点个数； 求所有整数的平均值。*include /定义在头文件RecurveList.h中class List;classListNode /链表结点类friend classList;private:intdata;/结点数据ListNode *link;/结点指针ListNode ( const intitem ) : data(item), li

41、nk(NULL) /构造函数;class List /链表类private:ListNode *first, current;intMa*(ListNode *f);int Num(ListNode *f);floatAvg (ListNode *f,int&n);public:List ( ) :first(NULL), current (NULL) /构造函数List() /析构函数ListNode* NewNode ( const intitem );/创立链表结点, 其值为itemvoidNewList ( const intretvalue );/建立链表, 以输入retvalue完

42、毕voidPrintList ( );/输出链表所有结点数据intGetMa* ( ) return Ma* ( first ); /求链表所有数据的最大值int GetNum ( ) returnNum ( first ); /求链表中数据个数float GetAvg ( ) return Avg ( first ); /求链表所有数据的平均值;ListNode* List:NewNode ( const int item ) /创立新链表结点ListNode *newnode = new ListNode (item);returnnewnode;voidList:NewList(cons

43、t int retvalue)/建立链表, 以输入retvalue完毕first=NULL;intvalue;ListNode *q;coutvalue;/输入while( value != retvalue)/输入有效q=NewNode(value);/建立包含value的新结点if ( first = NULL ) first = current = q;/空表时, 新结点成为链表第一个结点else current-link= q;current = q; /非空表时, 新结点链入链尾cin value;/再输入current-link = NULL;/链尾封闭voidList:Print

44、List()/输出链表coutnThe List is:n;ListNode *p = first;while(p!=NULL)coutdatalink;cout link=NULL)returnf-data;/递归完毕条件inttemp=Ma*(f-link);/在当前结点的后继链表中求最大值if(f-datatemp)returnf-data;/如果当前结点的值还要大, 返回当前检点值else returntemp;/否则返回后继链表中的最大值intList :Num ( ListNode *f ) /递归算法:求链表中结点个数if ( f = NULL ) return 0;/空表, 返回0return 1+ Num ( f -link );/否则, 返回后继链表结点个数加1floatList :Avg ( ListNode *f, int&n)/递归算法 : 求链表中所有元素的平均值if ( f -link = NULL ) /链表中只有一个结点, 递归完毕条件n = 1; return( float ) (f-data ); else float Sum =Avg (f-link, n) * n;n+;return ( f-data+Sum ) / n; *include Recur