欢迎来到天天文库
浏览记录
ID:53197003
大小:301.50 KB
页数:33页
时间:2020-04-17
《第 6 章(2)━━顺序表的排序和查找.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库。
1、C++程序设计第6章(2)━━顺序表的排序和查找1主要内容查找与排序常用查找方法━━顺序查找常用查找方法━━折半查找(二分法查找)插入排序法━━直接插入、折半插入选择排序法冒泡排序法索引排序与查找2查找与排序查找:指在一组数据元素中寻找满足条件的数据元素,并进一步给出其具体信息。常用查找方法:①顺序查找②折半查找排序:指将一组数据元素从无序序列调整为有序序列。从小到大的排序称为升序,从大到小的排序称为降序。①关键字:若待排序的数据元素含有多个成员数据项,可根据排序需要选择其中的一个成员数据项作为依据进行排序,称以该成员数据项为关键字的排序。也可选择其中的若干个关键字为依据进行排序,先按主关
2、键字进行排序,而主关键字相同的数据元素之间,再按次关键字进行排序……。②稳定排序:指当两个数据元素关键字相同时,原来排在前的仍然排在前。常用排序方法:①插入排序②选择排序③冒泡排序3常用查找方法━━顺序查找顺序查找方法:指从第一个数据元素开始,依次顺序查找下去,直到找到要找的元素为止,或者一直找到最后一个元素也未找到。顺序查找函数模板:(保存在头文件“search.h”中)templateintsequentSearch(TsL[],intn,Tk)//在数组sL[n]中查找数据k{for(inti=0;i3、时,返回所找到元素的下标return-1;//找不到时,返回-1}4【例】(对函数sequentSearch()进行测试。)#include#include#include“search.h”voidmain(){inta[10],k;cout<<“数组中的数据为:”;for(inti=0;i<10;i++){a[i]=rand()%90+10;cout<>k;i=sequentSearch(a,10,k);if(i!=-1)cout<4、]<<“已找到,下标=”<5、h)/2③查找并缩小查找区间:若所要找的元素==mid所指的元素,则:表示已找到,查找成功,结束!若所要找的元素>mid所指的元素,则:取low=mid+1,high不变,继续查找,重复②;若所要找的元素high仍未查找到,则:表示找不到,查找失败,停止!67478889299high=9mid=(5+9)/2=7low=4+1=516374156697478889299mid=(0+9)/2=4high=9low=0012345678988(查找成功例)1637415669747888926、99mid=(0+9)/2=4high=9low=0012345678916374156mid=(0+3)/2=1high=4-1=3low=04156low=1+1=2high=3mid=(2+3)/2=256high=3low=3mid=(3+3)/2=367(查找失败例)7常用查找方法━━折半查找(二分法查找)折半查找(迭代算法)函数模板:(保存在头文件“search.h”中)templateintbinarySearch1(TsL[],intn,Tk)//在数组sL[n]中查找数据k{intlow=0,high=n-1,mid;while(low<=high)7、{mid=(low+high)/2;if(k==sL[mid])returnmid;//找到时,返回所找到元素的下标if(k//在数组
3、时,返回所找到元素的下标return-1;//找不到时,返回-1}4【例】(对函数sequentSearch()进行测试。)#include#include#include“search.h”voidmain(){inta[10],k;cout<<“数组中的数据为:”;for(inti=0;i<10;i++){a[i]=rand()%90+10;cout<>k;i=sequentSearch(a,10,k);if(i!=-1)cout<4、]<<“已找到,下标=”<5、h)/2③查找并缩小查找区间:若所要找的元素==mid所指的元素,则:表示已找到,查找成功,结束!若所要找的元素>mid所指的元素,则:取low=mid+1,high不变,继续查找,重复②;若所要找的元素high仍未查找到,则:表示找不到,查找失败,停止!67478889299high=9mid=(5+9)/2=7low=4+1=516374156697478889299mid=(0+9)/2=4high=9low=0012345678988(查找成功例)1637415669747888926、99mid=(0+9)/2=4high=9low=0012345678916374156mid=(0+3)/2=1high=4-1=3low=04156low=1+1=2high=3mid=(2+3)/2=256high=3low=3mid=(3+3)/2=367(查找失败例)7常用查找方法━━折半查找(二分法查找)折半查找(迭代算法)函数模板:(保存在头文件“search.h”中)templateintbinarySearch1(TsL[],intn,Tk)//在数组sL[n]中查找数据k{intlow=0,high=n-1,mid;while(low<=high)7、{mid=(low+high)/2;if(k==sL[mid])returnmid;//找到时,返回所找到元素的下标if(k//在数组
4、]<<“已找到,下标=”<
5、h)/2③查找并缩小查找区间:若所要找的元素==mid所指的元素,则:表示已找到,查找成功,结束!若所要找的元素>mid所指的元素,则:取low=mid+1,high不变,继续查找,重复②;若所要找的元素high仍未查找到,则:表示找不到,查找失败,停止!67478889299high=9mid=(5+9)/2=7low=4+1=516374156697478889299mid=(0+9)/2=4high=9low=0012345678988(查找成功例)163741566974788892
6、99mid=(0+9)/2=4high=9low=0012345678916374156mid=(0+3)/2=1high=4-1=3low=04156low=1+1=2high=3mid=(2+3)/2=256high=3low=3mid=(3+3)/2=367(查找失败例)7常用查找方法━━折半查找(二分法查找)折半查找(迭代算法)函数模板:(保存在头文件“search.h”中)templateintbinarySearch1(TsL[],intn,Tk)//在数组sL[n]中查找数据k{intlow=0,high=n-1,mid;while(low<=high)
7、{mid=(low+high)/2;if(k==sL[mid])returnmid;//找到时,返回所找到元素的下标if(k//在数组
此文档下载收益归作者所有