查找与排序技术.ppt

《查找与排序技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章查找与排序技术3.1基本的查找技术3.2基本的排序技术3.1基本的查找技术3.1.1顺序查找3.1.2有序表的对分查找3.1.3分块查找2第3章查找与排序技术3.1.1顺序查找(1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。3第3章查找与排序技术线性表在顺序存储结构下的顺序查找输入：线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在线性表中的序号k。如果在线性表中不存

2、在元素x，则输出k＝－1。PROCEDURESERCH(V，n，x，k)k＝1WHILE(k≤n)and(V(k)≠x)DOk＝k＋1IF(k＝n＋1)THENk＝－1RETURN4第3章查找与排序技术/*函数返回被查找元素x在线性表中的序号，如果在线性表中不存在元素值x，则返回－1*/intserch(v，n，x)intn；ETv[]，x；/*ET为线性表数据类型*/{intk；k＝0；while((k＜n)&&(v[k]≠x))k＝k＋1；if(k＝＝n)k＝－1；return(k)；}5第3章查找与排序技术线性表

3、在链式存储结构下的顺序查找输入：线性链表头指针HEAD以及存储空间V、NEXT；被查找的元素x。输出：被查找元素x的结点在线性链表中的存储序号k。如果在线性链表中不存在元素值为x的结点，则输出k＝－1。PROCEDURELSERCH(V，NEXT，HEAD，x，k)k＝HEADWHILE(k≠0)and(V(k)≠x)DOk＝NEXT(k)IF(k＝0)THENk＝－1RETURN6第3章查找与排序技术structnode{ETd；structnode*next；}；/*函数返回被查找元素x所在结点的存储地址，如果在线

4、性链表中不存在元素值为x的结点，则返回NULL*/structnode*lserch(head，x)structnode*head；ETx；/*ET为线性链表中值域的数据类型*/{structnodek；k＝head；while((k≠NULL)&&(k－>d≠x))k＝k－>next；return(k)；}7第3章查找与排序技术3.1.2有序表的对分查找设有序线性表的长度为n，被查元素为x。将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的

5、部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。在最坏情况下，对分查找只需比较log2n次，而顺序查找需比较n次。8第3章查找与排序技术有序线性表在顺序存储结构下的对分查找输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存在元素x，则输出k＝－1。PROCEDUREBSERCH(V，n，x，k)i＝1；j＝nWH

6、ILE(i＜＝j)DO{k＝(i＋j)/2IF(V(k)＝x)THENRETURNIF(V(k)＞x)THENj＝k－1；ELSEi＝k＋1；}IF(i＞j)THENk＝－1RETURN9第3章查找与排序技术intbserch(v，n，x)/*函数返回被查找元素x在线性表中的序号如果在线性表中不存在元素值x，则返回－1*/intn；ETx，v[]；{inti，j，k；i＝1；j＝n；while(i＜＝j){k＝(i＋j)/2；if(v[k－1]＝＝x)return(k－1)；if(v[k－1]＞x)j＝k－1；else

7、i＝k＋1；}return(－1)；}10第3章查找与排序技术3.1.3分块查找分块有序表将长度为n线性表分成m个子表，各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。分块有序表的结构可以分为两部分：(1)线性表本身采用顺序存储结构。(2)再建立一个索引表。在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。11第3章查找与排序技术structind

8、node{ETkey；/*数据域，存放子表中的最大值，其类型与线性表中元素的数据类型相同*/intk；/*指针域，指示子表中第一个元素在线性表中的序号*/}；12第3章查找与排序技术13第3章查找与排序技术(1)首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的，因此可以采用对分查找。(2)然后在相应的子