数据结构课件第六章查找.pptx

《数据结构课件第六章查找.pptx》由会员分享，可在线阅读，更多相关《数据结构课件第六章查找.pptx（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本节内容查找的基本概念和顺序查找王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM查找Windows系统的文件查找 WeGame查找LOL玩家ID王道考研/CSKAOYAN.COM查找顺序查找，折半查找 二叉排序树，二叉平衡树王道考研/CSKAOYAN.COM查找数据元素往往包含除了关键字以外的很多数据 这个数据元素也叫做是记录typedef struct Elemtype key;/关键字 其他信息数据元素(记录)查找时比较的对象如果不特别说明，记录可以看做是只含关键字ASL 相当于是查找算法的基本操作执行次数王道考研/CSKAOYAN.COM顺序查找顺序查找(线性查找)，

2、主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。int Search1(int a,int n,int key)for(int i=1;i=n;i+)/注意从1开始 if(ai=key)return i;/查找成功 return 0;/查找失败 每次循环需要对i的值进行判断int Search2(int a,int n,int key)int i=n;a0=key;/设置“哨兵”while(ai!=key)/如果不是要找的元素 i-;/从后往前找 retur

3、n i;/如果查找失败也会返回0 下标 0 1 2 3值 5 2 0下标 0 1 2 3值 1 5 2 0王道考研/CSKAOYAN.COM顺序查找的分析int Search1(int a,int n,int key)for(int i=1;i=n;i+)/注意从1开始 if(ai=key)return i;/查找成功 return 0;/查找失败 由于查找有查找成功和失败两种情况所以ASL也分为查找成功的ASL和查找失败的ASL下标 0 1 2 3值 5 2 0王道考研/CSKAOYAN.COM顺序查找的分析int Search1(int a,int n,int key)for(int i=1;i=n;i+)/注意从1开始 if(ai=key)return i;/查找成功 return 0;/查找失败 由于查找有查找成功和失败两种情况所以ASL也分为查找成功的ASL和查找失败的ASL本节内容折半查找王道考研/CSKAOYAN.COM