}
template
BiNode
if (ch = =’#’) return NULL; //建立一棵空树 else{
root = new BiNode
root ->lchild = Creat( ); //递归建立左子树 root ->rchile = Creat( ); //递归建立右子树 } }
实 验 三 散列表的建立
题目:散列表的建立
1.实验目的
(1)掌握散列查找的基本思想; (2)掌握闭散列表的构造方法; (3)掌握线性探测处理冲突的方法; (4)掌握散列技术的查找性能。 2.实验内容
(1)对于给定的一组整数和散列函数,采用线性探测法处理冲突构造散列表; (2)设计查找算法,验证查找性能。 3.实现提示
假设散列表长为m,散列函数为除留余数法,即H(key)=key%p,m和p在主函数中由用户从键盘输入,待散列的数据也由用户从键盘输入,算法如下:
闭散列表构造算法
int CreatHash(int ht[ ], int m) {
for (i=0; i 16 cin>>k; while (k! =’#’) // #作为结束标志 { j =k % p; if (ht[ j ] = = 0) ht[ j ] =k; //没有发生冲突,直接存入 else{ i = (j+1) % m; while (ht[ i ]!=0 && i!=j) { if (ht[ i ] = = 0){ ht[ i ] =k; //发生冲突,向后探测若干次后存入 break; } else i= (i+1) % m; //向后探测一个位置 } if (i = = j)throw“溢出”; } cin>>k; } } 假设在已建立的散列表中进行静态查找,在查找过程中设置计数器count统计元素的比较次数,查找算法如下: 闭散列表的查找算法 HashSearch int HashSearch ( int ht[ ], int m, int k) { j =k %p; count =0; i =j; while (ht[ i ]!=0) { if ( ++count && ht[ i ] = = k) { //发生冲突,比较若干次查找成功 cout<<“查找成功,比较次数为:”< i= (i+1) % m; //向后探测一个位置 if (i = = j)break; } cout<<“查找不成功,比较次数为:”< 17 2.2设计性实验 实 验 一 统计候选人得票 题目:统计候选人得票 1.问题描述 设有n个候选人参加选举,统计每个人最后的得票情况。 2.基本要求 (1)以数组作为存储结构; (2)设计统计得票算法,将最后的得票情况统计并输出。 3.设计思想 可以将每个候选人设计为一个结构类型,包括名字和得票数,将n个候选人组成一个结构数组,其存储结构定义如下: const int n=10; //假设有10个人参加选举 struct Person { char *name; int count; }Leader[n]; 可以从键盘依次输入选举情况,每次输入一个人的名字,将输入的名字与结构数组 Leader进行比较,将对应候选人的得票数加1。 4.算法描述 选票统计算法 void Election(Person Leader[ ],int n) { cin>>name; while(name!=“#”) { for(i=0;i if(strcmp(Leader[i].name,name) = = 0) Leader[i].count ++; cin>>name; } 18 for(i=0;i cout< 思考题 将该问题用C++中的类实现。 实 验 二 汉诺塔问题 题目:汉诺塔问题 1.问题描述 汉诺塔问题来自一个古老的传说:在世界刚被创建的时候有一座钻石宝塔(塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔B和塔C)。从世界创始之日起,婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去,其间借助于塔B的帮助。每次只能移动一个碟子,任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时,世界末日也就到了。 2.基本要求 (1)设计数据结构,表示三座宝塔和n个盘子; (2)输出每一次移动盘子的情况; (3)分析算法的时间性能。 3.设计思想 对于汉诺塔问题的求解,可以通过以下三个步骤实现: (1)将塔A上的n-1个碟子借助塔C先移到塔B上。 (2)把塔A上剩下的一个碟子移到塔C上。 (3)将n-1个碟子从塔B借助于塔A移到塔C上。 显然,这是一个递归求解的过程,当n=3时的求解过程如图所示。 三座宝塔(塔A、塔B、塔C)分别用三个字符A,B,C来表示,n个盘子用从1开始的连续自然数编号。具体算法如下: c)把塔A上剩下的一个碟子移到塔C上(d)把n-1个碟子从塔B移到塔C 图 汉诺塔求解示意图 19 汉诺塔算法Hanoi void Hanoi( int n, char A, char B, char C) { if (n = = 1) cout<<“A→C”; //将碟子从A移到C上 else { Hanoi (n-1,A,C,B); cout<<“A→C”; Hanoi (n-1,B,A,C); } } 实 验 三 求无向连通图的生成树 题目:求无向连通图的生成树 1.问题描述 求无向连通图的一棵生成树。 2.基本要求 (1)采用邻接矩阵存储; (2)求深度优先生成树; (3)输出该生成树的每一条边。 3.设计思想 在一个连通无向图G=(V,E)中,如果从任一个顶点开始进行深度优先遍历,必定将边集E分成两个集合T和B,其中T是遍历过程中经历的边的集合,B是剩余的边的集合。显然,边集T和图G中所有顶点一起构成连通图G的一棵生成树。因此,修改7.4.1节中邻接矩阵类MGraph的深度优先遍历算法,输出遍历所经过的边,算法如下: 深度优先生成树算法DFSTraverse template void MGraph :: DFSTraverse ( int v) { visited [v] =1; for ( j=0; j if (arc[ v ][ j ] = = 1 && visited[ j ] = = 0) { cout<<“(”< 20 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据结构实验指导书(4)在线全文阅读。
相关推荐: