当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

河南中医药大学:《数据结构与算法(C#语言描述)》PPT教学课件_第8章 查找 8.1 查找的基本概念 8.2 线性表的查找 8.3 树表的查找 8.4 哈希表查找

资源类别:文库,文档格式:PPT,文档页数:65,文件大小:1.18MB,团购合买
8.1 查找的基本概念 8.2 线性表的查找 8.3 树表的查找 8.4 哈希表查找
点击下载完整版文档(PPT)

第8章查找 8.1查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则 白若千个数据项组成,并假设每个记录都有一个能唯一标识该 记录的关键字。 在这种条件下查找的定义是:给定一个值k,在含有n个记 录的表中找出关键字等于k的记录。若找到查找成功,返回该 记录的信息或该记录在表中的位置;否则查找失败,返回相关 的指示信息

8.1 查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则 由若干个数据项组成,并假设每个记录都有一个能唯一标识该 记录的关键字。 在这种条件下,查找的定义是:给定一个值k,在含有n个记 录的表中找出关键字等于k的记录。若找到查找成功,返回该 记录的信息或该记录在表中的位置;否则查找失败,返回相关 的指示信息。 第8章 查 找

查找有内查找和外查找之分。若整个查找过程都在内 存进行,则称之为内查找; 反之,若查找过程中需要访问外存,则称之为外查找

查找有内查找和外查找之分。若整个查找过程都在内 存进行,则称之为内查找; 反之,若查找过程中需要访问外存,则称之为外查找

采用何种查找方法? (1)使用哪种数据结构来表示“表”,即表中记录是按 何种方式组织的。 (2)表中关键字的次序。是对无序集合查找还是对有 序集台查找? 若在查找的同时对表做修改运算(如插入和删除), 则相应的表称之为动态查找表,否则称之为静态查找表

采用何种查找方法? (1)使用哪种数据结构来表示“表” ,即表中记录是按 何种方式组织的。 (2)表中关键字的次序。是对无序集合查找还是对有 序集合查找? 若在查找的同时对表做修改运算(如插入和删除), 则相应的表称之为动态查找表,否则称之为静态查找表

由于查找运算的主要运算是关键字的比较所以通常把查找 过程中对关键字需要执行的平均比较次数(也称为平均查找长 度)作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL( Average search length)定义为: ASL=∑PC 其中,n是查找表中记录的个数。P是查找第个记录的概率, 般地,均认为每个记录的查找概率相等,即=lMm(1n) c是找到第论个记录所需进行的比较次数 平均查找长度分为成功情况下的平均查找长度和不成功 情况下的平均查找长度

由于查找运算的主要运算是关键字的比较,所以通常把查找 过程中对关键字需要执行的平均比较次数(也称为平均查找长 度)作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL(Average Search Length)定义为: =  = n i i i ASL p c 1 其中,n是查找表中记录的个数。pi是查找第i个记录的概率, 一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n), ci是找到第i个记录所需进行的比较次数。 平均查找长度分为成功情况下的平均查找长度和不成功 情况下的平均查找长度

8.2性表的查找 在表的组织方式中线性表是最简单的一种。三种在线性表 上进行查找的方法: (1)顺序查找 (2)二分查找 (3)分块查找 因为不考虑在查找的同时对表做修改故上述三种查找操作 都是在静态查找表上实现的

8.2 线性表的查找 在表的组织方式中,线性表是最简单的一种。三种在线性表 上进行查找的方法: (1)顺序查找 (2) 二分查找 (3)分块查找 因为不考虑在查找的同时对表做修改,故上述三种查找操作 都是在静态查找表上实现的

定义被查找的顺序表中每个记录的类型如下: struct RecType ∥记录类型 public int key;/存放关键字,假设关鍵字为int类型 public string data;/存放其他数据,假设为 Istring类型 定义一个顺序表查找类 SqlistSearch class如下 class salistsearchClass const int MaxSize=100; 顺序表中最多元素个数 public ectype r; 顺序表 public int length; 存放顺序表的长度 public ldxTypell I; /索引表 BTNode ra /拆半查找判定树根结点 string sstr /用于返回结果 public sqlistsearchClasso/构造函数,用于查找顺序表的初始化 i rnew BTNodeo; R=new RecType MaxSize]; I=new IdxType MaxSize]; length=0 /顺序表的基本运算算法和查找算法

定义被查找的顺序表中每个记录的类型如下: struct RecType //记录类型 { public int key; //存放关键字,假设关键字为int类型 public string data; //存放其他数据,假设为string类型 }; 定义一个顺序表查找类SqListSearchClass如下 : class SqListSearchClass { const int MaxSize=100; //顺序表中最多元素个数 public RecType[] R; //顺序表 public int length; //存放顺序表的长度 public IdxType[] I; //索引表 BTNode r; //拆半查找判定树根结点 string sstr; //用于返回结果 public SqListSearchClass() //构造函数,用于查找顺序表的初始化 { r=new BTNode(); R=new RecType[MaxSize]; I=new IdxType[MaxSize]; length=0; } //顺序表的基本运算算法和查找算法 }

82.1顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是:从表的一端开始顺序扫描顺序表 依次将扫描到的元素关键字和给定值相比较,若当前扫描 到的元素关键字与k相等,则查找成功;着扫描结束后,仍 未找到关键字等于k的元素,则查找失败

8.2.1 顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是:从表的一端开始顺序扫描顺序表, 依次将扫描到的元素关键字和给定值k相比较,若当前扫描 到的元素关键字与k相等,则查找成功;若扫描结束后,仍 未找到关键字等于k的元素,则查找失败

顺序查找的算法如下 public int SeqSearch(int k) /顺序查找算法 int i=0 while(i=length) 未找到返回0 return 0; else return i+l /找到后返回其逻辑序号计+1

顺序查找的算法如下 : public int SeqSearch(int k) //顺序查找算法 { int i=0; while (i=length) //未找到返回0 return 0; else return i+1; //找到后返回其逻辑序号i+1 }

从顺序查找过程可以看到(不考虑越界比较n),c取 决于所查记录在表中的位置。如查找表中第1个记录R[0时, 仅需比较一次;而查找表中最后一个记录Rm-1时,需比较n 次,即c-。因此成功时的顺序查找的平均查找长度为: ASL=∑PC=-∑i=-x2(n+ n+ L n n 2 查找成功时的平均比较次数约为表长的一半。 思考题:不成功时的平均查找长度是多少?

从顺序查找过程可以看到(不考虑越界比较i<n),ci取 决于所查记录在表中的位置。如查找表中第1个记录R[0]时, 仅需比较一次;而查找表中最后一个记录R[n-1]时,需比较n 次,即ci=i。因此,成功时的顺序查找的平均查找长度为: 2 1 2 1 1 ( 1) 1 1 + = + =  =  =  = = n n n n i i n c i p sq ASL n i n i 查找成功时的平均比较次数约为表长的一半 。 思考题:不成功时的平均查找长度是多少?

8.2,2折半查找 折半查找也称为二分查找,要求线性表中的节点必须己按 关键字值的递增或递减顺序排列。 思路:首先用要查找的关键字与中间位置的节点的关键 字相比较,这个中间节点把线性表分成了两个子表,若比较结 果相等则查找完成;若不相等,再根据k与该中间节点关键字的 比较大小确定下一步查找哪个子表,这样递归进行下去,直到 找到满足条件的节点或者该线性表中没有这样的节点

8.2.2 折半查找 折半查找也称为二分查找,要求线性表中的节点必须己按 关键字值的递增或递减顺序排列。 思路:首先用要查找的关键字k与中间位置的节点的关键 字相比较,这个中间节点把线性表分成了两个子表,若比较结 果相等则查找完成;若不相等,再根据k与该中间节点关键字的 比较大小确定下一步查找哪个子表,这样递归进行下去,直到 找到满足条件的节点或者该线性表中没有这样的节点

点击下载完整版文档(PPT)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共65页,可试读20页,点击继续阅读 ↓↓
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有