《第1章数据结构.ppt》由会员分享，可在线阅读，更多相关《第1章数据结构.ppt（16页珍藏版）》请在三一文库上搜索。
1、,第 1 章 数据结构,1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序,姓名 学号 成绩 班级 李红 9761059 95 机97.6,10,65,865,1.5 查找,查找:,查找也叫检索，是根据给定的某个值，在表中确定 一个关键字等于给定值的记录或数据元素. 不同的数据结构采用不同的查找方法。 关键字是数据元素中某个数据项的值，它可以标识 一个数据元素.,查找的结果：,查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。,查找速度; 占用存储空间多少 算法本身复杂程度,查找方 法评价：,基本思路： 从表中第一个元素
2、开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。,1.5 查找,1.5.1 顺序查找,用户从键盘任意输入一个整数，查找该数在数组中是否存在。,#define N 10 main() int x,i,aN=13,22,35,46,-59,62,72,86,98,987; int found=0; / 查找结果的标志，1:找到，0:未找到 printf(“输入欲查找的数据：“); scanf(“%d“, ,1.5 查找,1.5.1 顺序查找,打开某一数据文件，查找某数是否存在。,#include main() FILE *fp; in
3、t x,y,found=0; fp=fopen(“e:sundata.txt“, “r“); printf(“输入欲查找的数据：“); scanf(“%d“, ,如，e盘下sun文件夹有一数据文件data.txt,该文件中存储了若干数据： 13 22 35 46 -59 62 72 86 98 987 用户从键盘任意输入一整数，查找此数在该数据文件中是否存在。,1.5 查找,1.5.1 顺序查找,从函数的角度，实现查找功能。,#define N 10 void search(int a , int x) int i, found=0; for(i=0; iN ,改进该函数： search函数有
4、返回值，若待查找的数存在，返回该数在数组中所在的位置（自然位置），若不存在，返回0。,1.5 查找,1.5.1 顺序查找,从函数的角度，实现查找功能。,#define N 10 int search(int a , int x) int i, n, found=0; for(i=0; iN ,改进该函数： search函数有返回值，若待查找的数存在，返回该数在数组中所在的位置（自然位置），若不存在，返回0。,1.5 查找,1.5.1 顺序查找,从线性表的角度，实现查找功能。,查找该班是否有某某学生。,#define N 40 struct stu int num; char name20; c
5、har department30; LISTN;,1.5 查找,1.5.1 顺序查找,从线性表的角度，实现查找功能。,#define N 40 struct stu int num; char name20; char department30; LISTN;,int search(LIST a , char name ) int i, n, found=0; for(i=0; iN ,实际上，一般采用倒序查找： for(i=N-1; i=0 i-),基本思路： 从表中第一个元素开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。,1
6、.5 查找,1.5.1 顺序查找,查找 次数,表中第一个元素就是被查找元素，一次比较就成功。 表中最后一个元素是被查找元素(或不在表中)，与所有元素比较。 平均情况，查找一个元素，大约与表中一半元素比较。,优点：对表中数据元素的存储没有要求。 缺点：线性表很大时，平均查找长度较长，效率低。,基本思路： 从表中第一个元素开始，将给定的值与表中逐个元素的关键字比较。直到两者相等表示找到，查找成功。否则就是表中无要找的元素，查找失败。,1.5 查找,1.5.1 顺序查找,下列两种情况只能采用顺序查找： 线性表是无序表(元素排列是无序的)，无论顺序存储还是链式存储 有序线性表而采用链式存储结构,思想：
7、先确定待查找记录所在的范围，然后逐步缩小范围， 直到找到或确认找不到该记录为止。 适用条件：必须在具有顺序存储结构的有序表(表中元素按关键值升序或降序存放)中进行。,算法实现 1) 确定区间的中间位置 mid =(low + high)/2 2) 用给定值与中间位置的关键字值比较；若相等，则查找成功； 若给定值大,新查找区为后半区； 若给定值小,新查找区为前半区。 3) 对缩小的区域重复上述步,直至lowhigh时，查找失败,1.5 查找,1.5.2 二分法查找(折半查找),在含有9个数的升序线性表中查找68的过程如下图,( 08, 14, 23, 37, 46, 55, 68, 79, 91
8、 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),1.5.1 二分法查找(折半查找),mid=(low+high)/2 xLmid: low=mid+1,mid=(6+9)/2=7,mid=(1+9)/2=5,1.5 查找,经过二次比较,查找成功,在含有16个数的升序线性表中查找39和17的过程如下图,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,1.5.1 二分法查找(折半查找),mid=(low+high)/2 在后半部: low=mid
9、+1 在前半部: high=mid-1,1.5 查找,经过三次比较,查找成功,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,2 4 5 8 16 20 29 36 37 39 41 42 45 50 52 58,当highlow时，查找失败,查找17,二分法查找时间复杂度,O(log2n),二分查找(折半查找) 查找效率高 前提: 查找表中的数据元素必须有序。 算法:1) 确定区间的中间位置 mid =(left + right)/2 2) 用给定值与中间位置的关键字值比较；若相等，则查找成功； 若给定值大,新查找区为后半区； 若给定值小,新查找区为前半区。 3)对缩小的区域重复上述步骤；,二分法查找时间复杂度,O(log2n),优点: 比较次数少,查找速度快 缺点：要求事先排序,查找总结,