攻坚实验四 树种统计(注释).doc

攻坚实验四 树种统计一、 实验目的熟练掌握二叉搜索树的性质及在解决问题中的应用。二、 实验内容随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。三、 实验要求 1. 输入说明：输入第一行给出一个正整数N(N=105) ,为树的数量。随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称是不超过30个英文字母和空格组成的字符串(大小写不区分)。2输出说明：按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，精确到小数点后4位。3测试用例：序号输入输出说明129Red AlderAshAspenBasswoodAshBeechYellow BirchAshCherryCottonwoodAshCypressRed ElmGumHackberryWhite OakHickoryPecanHard MapleWhite OakSoft MapleRed OakRed OakWhite OakPoplanSassafrasSycamoreBlack WalnutWillowAsh 13.7931%Aspen 3.4483%Basswood 3.4483%Beech 3.4483%Black Walnut 3.4483%Cherry 3.4483%Cottonwood 3.4483%Cypress 3.4483%Gum 3.4483%Hackberry 3.4483%Hard Maple 3.4483%Hickory 3.4483%Pecan 3.4483%Poplan 3.4483%Red Alder 3.4483%Red Elm 3.4483%Red Oak 6.8966%Sassafras 3.4483%Soft Maple 3.4483%Sycamore 3.4483%White Oak 10.3448%Willow 3.4483%Yellow Birch 3.4483%一般情况测试21 A test for the longest stringsA test for the longest strings 100.00%边界测试：最小N,最长树种名3100000随机生成不重复的大数据百分比全部为0.0010%边界测试：最大N的树4100000随机大数据略 边界测试：最大N四、 实验分析（1）问题分析问题的关键在于需要反复查找某种输入树种并将其个数加1。如果简单的将最多N个宿儒树种存为数组，则每次查找最坏都需要线性时间复杂度O(N),于是总查找时间将达到O(N2)。二分查找可以达到O(logN)的查找效率，但前提条件是数组里的数据有序。在学习高效排序算法之前，用如冒泡排序之类的简单算法并不是很好的选择，因为时间复杂度可能达到O(N2).二叉搜索树可以比较有效地提高查找效率。如果树比较平衡，则单次插入和查找都可以达到O(logN)的复杂度，因此总体时间复杂度可能降低到O(NlogN)。当然最坏的情况下，可能形成单边倾斜的二叉搜索树，这时的效率只有O(N2)，与前两种算法持平。用二叉搜索树的另一个好处是，对其进行中序遍历就可以得到按字典序递增的输出序列。（2）实现要点树形结构仍然用一般教材中介绍的链表结构存储，结点结构体除了存储该结点的树种名称及左右子树的指针外，还需要一个计数器来存储树种的数量。五、 主要仪器及耗材计算机及VC6软件六、 实验参考代码 #include#include#include#include#define MAXN 100000#define MAXS 30#define NULL 0typedef struct TreeNode *binTree;struct TreeNodechar DataMAXS+1;int cnt;binTree left;binTree right;binTree Insert(binTree T,char *Name)int cmp;if(!T)T=(binTree)malloc(sizeof(struct TreeNode);strcpy(T-Data,Name);T-cnt=1;T-left=T-right=NULL;elsecmp=strcmp(Name,T-Data);if(cmpleft=Insert(T-left,Name);else if(cmp0)T-right=Insert(T-right,Name);elseT-cnt+;return T;void output(binTree T,int N)if(!T)return;/递归终止条件output(T-left,N);/输出左子树printf(%s%.4lf%cn,T-Data,(double)T-cnt/(double)N*100.0,%);/输出根结点的值output(T-right,N);/输出右子树int main()int N,i;char nameMAXS+1;binTree T=NULL;scanf(%dn,&N);for(i=0;ileft,N);/输出左子树printf(%s%.4lf%cn,T-Data,(double)T-cnt/(double)N*100.0,%);/输出根结点的值output(T-right,N);/输出右子树int main()int N,i;char nameMAXS+1;binTree T=NULL;scanf(%dn,&N);for(i=0;iN;i+)gets(name);T=Insert(T,name);output(T,N);return 0;七、