77范文网 - 专业文章范例文档资料分享平台

数据结构实验指导书(4)

来源:网络收集 时间:2019-03-10 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

}

template

BiNode * BiTree :: Creat( ) { Cin>>ch;

if (ch = =’#’) return NULL; //建立一棵空树 else{

root = new BiNode; //生成一个结点 root ->data = ch;

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)在线全文阅读。

数据结构实验指导书(4).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/511413.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: