《数据结构 第3--8章 应用和部分算法题.》由会员分享，可在线阅读，更多相关《数据结构 第3--8章 应用和部分算法题.（20页珍藏版）》请在金锄头文库上搜索。
1、第三章（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： 求链表中的最大整数； 求链表的结点个数； 求所有整数的平均值。#include /定义在头文件RecurveList.h中class List;class ListNode /链表结点类friend class List;private:int data;/结点数据ListNode *link;/结点指针ListNode ( const int item ) : data(item), link(NULL) /构造函数;class List /链表类private:ListNode *first
2、, current;int Max ( ListNode *f );int Num ( ListNode *f );float Avg ( ListNode *f, int& n );public:List ( ) : first(NULL), current (NULL) /构造函数List ( ) /析构函数ListNode* NewNode ( const int item );/创建链表结点, 其值为itemvoid NewList ( const int retvalue );/建立链表, 以输入retvalue结束void PrintList ( );/输出链表所有结点数据int
3、GetMax ( ) return Max ( first ); /求链表所有数据的最大值int GetNum ( ) return Num ( first ); /求链表中数据个数float GetAvg ( ) return Avg ( first ); /求链表所有数据的平均值;ListNode* List : NewNode ( const int item ) /创建新链表结点ListNode *newnode = new ListNode (item);return newnode;void List : NewList ( const int retvalue ) /建立链表,
4、以输入retvalue结束first = NULL; int value; ListNode *q;cout value;/输入while ( value != retvalue ) /输入有效q = NewNode ( value );/建立包含value的新结点if ( first = NULL ) first = current = q;/空表时, 新结点成为链表第一个结点else current-link = q; current = q; /非空表时, 新结点链入链尾cin value;/再输入current-link = NULL;/链尾封闭void List : PrintLis
5、t ( ) /输出链表cout nThe List is : n;ListNode *p = first;while ( p != NULL ) cout data link; cout link = NULL ) return f -data;/递归结束条件int temp = Max ( f -link );/在当前结点的后继链表中求最大值if ( f -data temp ) return f -data;/如果当前结点的值还要大, 返回当前检点值else return temp;/否则返回后继链表中的最大值int List : Num ( ListNode *f ) /递归算法 : 求
6、链表中结点个数if ( f = NULL ) return 0;/空表, 返回0return 1+ Num ( f -link );/否则, 返回后继链表结点个数加1float List : 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; #in
7、clude RecurveList.h/定义在主文件中int main ( int argc, char* argv ) List test; int finished;cout finished;/输入建表结束标志数据 test.NewList ( finished );/建立链表test.PrintList ( );/打印链表cout nThe Max is : test.GetMax ( );cout nThe Num is : test.GetNum ( );cout nThe Ave is : test.GetAve () n;printf ( Hello World!n );ret
8、urn 0;第五章2应用题（1）试找出满足下列条件的二叉树 先序序列与后序序列相同 中序序列与后序序列相同 先序序列与中序序列相同 中序序列与层次遍历序列相同先序遍历二叉树的顺序是“根左子树右子树”，中序遍历“左子树根右子树”，后序遍历顺序是：“左子树右子树根，根据以上原则，本题解答如下：（） 若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（） 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树（） 若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（） 若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（2）
9、设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树（或森林）。 ABMFD(3)CEMHG (1) (2)（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10
10、，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WP
11、L2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。初态:weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112终态3算法设计题以二叉链表作为二叉树
