计算机软件技术基础-课件 08ch4-DS

数据结构课程的内容4.1查找

4.1.1查找操作的相关术语

4.1.2顺序查找

4.1.3折半查找

4.1.4分块查找第4章查找与排序4.1查找学习目标：

1、掌握在顺序表上进行顺序查找的方法和算法，时间复杂度，平均查找长度。

2、掌握二分查找的方法和算法，时间复杂度，二分查找判定树和查找每个元素的查找路径及平均查找长度。4.1.1查找操作的相关术语——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录——可以唯一标识一个记录的关键字例如“学号”例如“姓名”是一种数据结构——识别若干记录的关键字查找的定义：就是根据给定的关键字值，在一个表中查找出其关键字等于给定值的数据元素。

(1)若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；

(2)若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。

（2）对查找表常用的操作有哪些？

查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。

（3）有哪些查找方法？

查找方法取决于表中数据的排列方式;讨论：（1）查找的过程是怎样的？

给定一个值K，在含有n个元素的查找表中进行搜索，寻找一个关键字值等于K的元素，如找到则输出该元素，否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字（4）如何评估查找算法的优劣？明确：查找的过程就是将给定的K值与查找表中各元素的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：AverageSearchLength）。其中：n是元素个数；Pi是查找第i个元素的查找概率（通常取等概率,即Pi=1/n）;Ci是查找第i个元素时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。

静态查找表4.1.2顺序查找（线性查找）4.1.3折半查找（二分或对分查找）4.1.4分块查找（索引顺序查找）4.1.2顺序查找（Linearsearch，又称线性查找）在顺序表上的顺序查找（又称线性查找）的基本思想：从顺序表的一端开始，用给定的关键字逐个与顺序表中各数据元素的关键字比较；若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回0或-1。

（1）顺序表的存储结构： #defineMaxSize100 //数组长度常量

typedefintKeyType; //关键字类型定义typedefstruct{ KeyTypeKey; //关键字数据项

OtherTypeOtherData;//其他数据项}ElemType; //数据元素类型定义（2）算法的实现：typedefstruct{

ElemTypeS[MaxSize];

//表容量为全部元素

intN;

//表长，即表中数据元素个数}ListType;ListType*ST；例：若将待查找的特定值myKey存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！intSearch_Seq(ListType*ST,KeyTypemyKey)

{

//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0

inti;

ST->S[0].key=myKey;

//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。(对比顺序表中的SL_Location) for(i=N;ST->S[i].key!=myKey;i--); returni;}//找不到=不成功，返回值必为i=0；//找到=成功，返回值i为所找元素的位置。技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快查找执行速度。——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入ST->S[0].Key使之结束，并返回i=0。讨论②查找效率怎样计算？——用平均查找长度ASL衡量。讨论①查不到怎么办？讨论③如何计算ASL？分析：查找第1个元素所需的比较次数为n；查找第2个元素所需的比较次数为n-1；……查找第n个元素所需的比较次数为1；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1这是查找成功的情况若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL＝（1＋n）/2

，时间效率为O(n)优点：算法简单，且对顺序结构或链表结构均适用。缺点：

ASL=O(n)太长，时间效率太低。4.1.3折半查找（又称二分查找或对分查找）

这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至左(前）半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。对顺序表结构如何编程实现折半查找算法？

——见后面的例子对单链表结构如何折半查找？

——无法实现！因全部元素的定位只能从头指针head开始如何改进？讨论④顺序查找的特点：设：待查元素mykey所在区域的下界为low，上界为high，则中间位置mid＝（low＋high）/2分三种情况(升序有序表)：1)若ST->S[mid].Key＝myKey，则查找成功；2)若ST->S[mid].Key<myKey，则在[mid+1

~high]中继续查找；3)若ST->S[mid].Key>myKey，则在区域[low~mid-1]中继续查找。思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。讨论①若关键字不在表中，怎样判定和停止？——典型标志是：当查找范围的上界high<下界low时停止查找。②运算步骤：(1)low=1,high=10,mid=5，待查范围是[1,10]；(2)若ST->S[mid].Key<myKey，说明key

[mid+1,high]，则令：low=mid+1;重算mid＝

(low+high)/2

；.(3)若ST->S[mid].Key>

myKey，说明key

[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST->S[mid].Key=myKey，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST->S[mid]=key

（2）查找不成功：high<low

（意即被查找区间长度小于0）解：①先设定3个辅助标志:

low,high,mid，折半查找举例：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置

已知如下10个元素的有序表：

（08172544687798100115125）,请查找关键字为17

和120的数据元素。有：mid=

(low+high)/2

例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找K=17和K=120的情况描述为下图1及下图2形式。1.）查找K=172.）查找K=12012345678910123456789102.）查找K=1202.）查找K=1201234567891012345678910二分查找算法实现：intbinsearch(ListType*ST

,KeyTypek)

{intlow=1,high=n;

while(low<=high)

{intmid=(low+high)/2;//取区间中点

if(ST->S[mid].key==k)returnmid;//查找成功

elseif(ST->S[mid].key

>k)

high=mid-1;//在左子区间中查找

elselow=mid+1;//在右子区间中查找

}

return0;//查找失败

}先看一个具体的情况，假设：n=116391425781011判定树折半查找的平均查找长度12233334444讨论②二分查找的效率（ASL）为方便起见，假设表中全部n个元素＝2m-1个（判定树为满二叉树）。1次比较就查找成功的元素有1个（20），即中间值；2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处；3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处…4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处………则第m次比较时查找成功的元素会有（2m-1）个；全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1

即推导过程平均每个数据的查找长度还要除以n，所以：注：等差-等比数列（arithmeticgeometricseries）4.1.4分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。让数据分块有序，即把被查找的表分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。

该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。索引表最大关键字起始地址2212138920334244382448605874498653第1块第2块第3块224886例：2248860612特点：块间有序，块内无序查找步骤分两步进行：①对索引表使用折半查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw对索引表查找的ASL对块内查找的ASLS为每块内部的记录个数，n/s即块的数目例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5若索引表也是顺序查找，则ASL=(n/s+1)/2+(s+1)/2四、顺序查找、对半查找、分块查找的比较1）查找效率：对半查找、分块查找、顺序查找高低

二分查找－－有序表高2）要求表的结构：分块查找－－逐段有序表

顺序查找－－有序表、无序表低

顺序查找适用于顺序和链式存储3)要求的存储方式：分块查找二分查找－－只适用于顺序存储结构且有序。4.2排序

4.2.1排序的概念

4.2.2插入排序

4.2.3简单选择排序

4.2.4交换排序第4章查找与排序排序学习目标：

1、掌握插入、选择和冒泡等排序的方法，排序过程及时间复杂度。

2、掌握每一种排序方法的稳定性。4.2.1排序的概念1.什么是排序？将一个数据元素（记录）的任意序列，重新排列成一个按关键字有序的序列。

2.排序的目的是什么？3.排序算法的好坏如何衡量？时间效率——排序速度（算法执行中的数据比较次数与数据移动次数）空间效率——占内存辅助空间的大小稳定性——若两个记录A和B的关键字值相等，但排序后A、

B的先后次序保持不变，则称这种排序算法是稳定的。

——便于查找！4.什么叫内部排序？什么叫外部排序？

——若待排序记录都在内存中，称为内部排序；——若待排序记录一部分在内存，一部分在外存，则称为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

5.待排序记录在内存中怎样存储和处理？①顺序排序——排序时直接移动记录；②链表排序——排序时只移动指针；③地址排序——排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。注：大多数排序算法都是针对顺序表结构的(便于直接移动元素)6.顺序存储（顺序表）的抽象数据类型如何表示？Typedefstruct//定义每个记录（数据元素）的结构

{KeyTypekey;//定义关键字为整型类量

InfoTypeotherinfo;//定义其它数据项类型

}elemtype;//类型字Typedefstruct//定义顺序表的结构

{elemtyper[MAXSIZE];//存储顺序表的向量

intlength;//顺序表的长度

}SqList;#defineMAXSIZE20//设记录不超过20个typedefintKeyType;//定义KeyType为整型类（int型）7.内部排序的算法有哪些？——按排序的规则不同，可分为5类：插入排序交换排序（重点是快速排序*）选择排序*归并排序*基数排序三种简单排序算法4.2.2插入排序插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。如：当插入第i

(i

2)个对象时,前面的V[1],V[2],…,V[i-1]已经排好序。这时,用V[i]的关键码与V[i-1],V[i-2],…的关键码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。简言之，边插入边排序，保证子序列中随时都是排好序的。插入排序的具体实现算法：

1)直接插入排序 2)折半插入排序

直接插入排序新元素插入到哪里？例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出简单插入排序的中间过程序列。 【13】,6,3,31,9,27,5,11第1趟【6,13】,3,31,9,27,5,11第2趟 【3,6,13】,31,9,27,5,11第3趟 【3,6,13，31】,9,27,5,11第4趟 【3,6,9,13，31】,27,5,11第5趟 【3,6,9,13，27,31】,5,11第6趟 【3,5,6,9,13，27,31】,11第7趟 【3,5,6,9,11，13，27,31】

在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。最简单的排序法！排好序的子序列！直接插入排序voidInsertSort(SqList*L)//对顺序表L作直接插入排序{inti,j;for(i=2;i<=L->length;i++){//复制为哨兵

L->r[0].key=L->r[i].key; j=i-1; while(L->r[0].key<L->r[j].key) {L->r[j+1]=L->r[j]; //记录后移

j--; }//此时，满足L->r[0].key>=L->r[j].key L->r[j+1]=L->r[0]; //插入正确的位置

}}说明：哨兵L->r[0]的作用：保存记录L->r[i]的副本；监视下标j是否越界，自动控制循环结束例2：关键字序列T=（21，25，49，25*，16，08），

请写出简单插入排序的具体实现过程。*表示后一个25i=121254925*16080123456暂存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或暂存单元（Temp）。则程序执行过程为：21254925*21初态：164925*25211608完成!时间效率：O(n2)——因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下还要加上移动元素的次数。空间效率：O（1）——因为仅占用1个缓冲单元算法的稳定性：稳定——因为25*排序后仍然在25的后面。

若设待排序的对象个数为n，则算法需要进行n-1次插入。最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较1次，移动2次对象。因此，总的关键码比较次数为n-1，对象移动次数为2(n-1)。直接插入排序的算法分析需要进行插入的元素需要两次移动1.搬移到暂存单元2.从暂存单元插入到序列中

最坏情况下，第i趟插入时，第i个对象必须与前面(i-1)+1个对象都做关键码比较，并且每做1次比较就要做1次数据移动。则总的关键码比较次数KCN

(KeyComparisonNumber)和对象移动次数EMN

(ElementMoveNumber)分别为直接插入排序小结：1.若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键码比较次数和对象移动次数约为n2/4。因此，简单插入排序的时间复杂度为O(n2)。2.

简单插入排序是一种稳定的排序方法。*折半插入排序(BinaryInsertsort)基本思想是:设在顺序表中有一个对象序列V[1],V[2],

…,V[n-1]。其中,V[1],

V[1],…,V[i-1]

是已经排好序的对象。在插入V[i]

时,利用折半搜索法寻找V[i]的插入位置。用折半插入排序所进行的排序码比较次数与待排序记录序列的初始排列无关，仅依赖于记录个数。在插入第i个记录时，需要经过

log2i

+1次比较，才能确定它应插入的位置。n个记录折半插入排序所需的比较次数为：记录移动次数O(n2)

，时间复杂度仍为O(n2)折半插入排序是一个稳定的排序方法。4.2.3简单选择排序选择排序的基本思想是：每一趟在后面n-i+1个待排记录中选取关键字最小的记录作为有序序列中的第i个记录。思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。优点：实现简单缺点：每趟只能确定一个元素，表长为n时需要n-1趟例：关键字序列T=（21，25，49，25*，16，08），请给出简单选择排序（前小后大）的具体实现过程。原始序列：

21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,

49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49最小值08与r[1]交换位置4.2.4交换排序（冒泡排序）

每趟不断将待排序列中相邻元素两两比较，使大数沉底，小数上冒，并按“前小后大”（或“前大后小”）规则交换。

每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。例：关键字序列T=(21，25，49，25*，16，08），请写出冒泡排序（前小后大）的