第 6 章(2)━━顺序表的排序和查找.ppt

《第 6 章(2)━━顺序表的排序和查找.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、C++程序设计第6章(2)━━顺序表的排序和查找1主要内容查找与排序常用查找方法━━顺序查找常用查找方法━━折半查找（二分法查找）插入排序法━━直接插入、折半插入选择排序法冒泡排序法索引排序与查找2查找与排序查找：指在一组数据元素中寻找满足条件的数据元素，并进一步给出其具体信息。常用查找方法：①顺序查找②折半查找排序：指将一组数据元素从无序序列调整为有序序列。从小到大的排序称为升序，从大到小的排序称为降序。①关键字：若待排序的数据元素含有多个成员数据项，可根据排序需要选择其中的一个成员数据项作为依据进行排序，称以该成员数据项为关键字的排序。也可选择其中的若干个关键字为依据进行排序，先按主关

2、键字进行排序，而主关键字相同的数据元素之间，再按次关键字进行排序……。②稳定排序：指当两个数据元素关键字相同时，原来排在前的仍然排在前。常用排序方法：①插入排序②选择排序③冒泡排序3常用查找方法━━顺序查找顺序查找方法：指从第一个数据元素开始，依次顺序查找下去，直到找到要找的元素为止，或者一直找到最后一个元素也未找到。顺序查找函数模板：（保存在头文件“search.h”中）templateintsequentSearch(TsL[],intn,Tk)//在数组sL[n]中查找数据k{for(inti=0;i

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（查找成功例）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//在数组