第8章查找算法Word文档格式.docx
《第8章查找算法Word文档格式.docx》由会员分享，可在线阅读，更多相关《第8章查找算法Word文档格式.docx（34页珍藏版）》请在冰点文库上搜索。
否则，查找不成功。
例如，在表8-1所示的电话簿中，以姓名为关键字，查找是否有“刘胜利”的记录，即k=“刘胜利”。
最简单的查找过程是：
从查找表的第1个数据元素开始依次比较当前记录的关键字和k的值是否相等，第3个数据元素的姓名与k相同，则查找成功；
再设k=“李伟”，电话簿中所有数据元素的姓名都不等于k，则查找不成功。
2.静态查找表与动态查找表
对查找表除了进行查询和检索操作外，也可能进行其他的操作，如在查找表中插入或删除一个数据元素。
根据查找表数据是否变化，可以将查找表分为静态查找表和动态查找表：
●静态查找表（staticsearchtable）：
不需要对一个查找表进行插入、删除操作，例如，字典是一个静态查找表。
●动态查找表（dynamicsearchtable）：
需要对一个查找表进行插入、删除操作，例如，电话簿则是一个动态查找表。
3.查找方法
查找的方法一般因数据结构及存储结构的不同而变化。
如果数据元素之间不存在明显的组织规律，则不便于查找。
为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，亦即改变查找表的结构。
查找表的规模也会影响查找方法的选择。
对于数据量较小的线性表，可以采用顺序查找算法。
例如，从电话簿的第一个数据元素开始，依次将数据元素的关键字与k比较，进行查找操作。
当数据量较大时，顺序查找算法效率很低，这时可采用分块查找算法。
例如，在字典中查找单词，从头开始进行顺序查找的效率低、速度慢，没有人会真的这样查字典。
一般我们分两步查找单词：
首先确定单词首字母的起始页码，再根据单词后几个字母的顺序，就可以快速准确地定位单词，并查阅其含义。
这是因为字典是按字母顺序排列的。
总之，要根据不同的条件选择合适的查找的方法，以求快速高效地得到查找结果。
本章将讨论若干种经典的查找方法。
4.查找算法的性能评价
查找的效率直接依赖于数据结构和查找算法，衡量查找算法性能的最主要标准是平均查找长度（AverageSearchLength,ASL）。
平均查找长度是指查找过程所需进行的关键字比较次数的平均值，即有
其中，pi是要查找的数据元素的出现概率，要查找数据元素处在查找表中不同的位置i，则查找相应数据元素需进行的关键字比较次数往往是不同的，用ci表示关键字比较次数。
一般要查找的数据元素的出现概率pi很难精确确定，通常考虑等概率出现的情况，即设pi=1/n。
查找成功和查找不成功的平均查找长度ASL通常不同，分别用ASL成功和ASL不成功表示。
8.1.2C#内建数据结构中的查找操作
.NETFramework的类库中定义了许多使用方便的数据结构，我们以Array、ArrayList和List以及Hashtable和Dictionary为例介绍其中的查找操作方面的内容。
1.Array、ArrayList和List
C#中的数组都是继承自System.Array基类型。
Array类提供了许多用于排序、搜索和复制数组的方法。
System.Collections.ArrayList类和System.Collections.Generic.List（泛型）类都提供了一种使用大小可按需动态增加的数组。
给定某一数组元素的下标（Index）找到该元素的值也可以看成是一种查找操作，它的时间复杂度为O
（1）。
而找到具有特定值的某元素的过程才是一般意义下的查找操作，最基本的查找方法是：
对于给定k，从数组的一端开始，依次比较每个数据元素的关键字，直到查找成功或不成功。
Array，List和ArrayList类都提供了多种重载（overloaded）形式的IndexOf（）方法实现查找操作，Array类的IndexOf方法都是静态方法，它们分别具有下列形式：
1）publicstaticintIndexOf<
T>
（T[]array,Tvalue）;
T为数组元素的泛型类型，在调用时指明。
array为要搜索的数组；
value为要搜索的对象；
返回给定数据在数组中首次出现的位置。
如果在整个array中找到value的匹配项，则为第一个匹配项的索引；
否则为-1。
2）publicstaticintIndexOf<
（T[]array,Tvalue,intstartindex,intcount）;
返回给定数据在数组指定范围内首次出现的位置。
如果在array中从startIndex开始并且包含count个的元素的这部分元素中找到value的匹配项，则返回值为第一个匹配项的索引；
对于已按关键字的值排序好的数据结构，则提供实现更高效的二分查找（binarysearch）的BinarySearch方法：
1）publicstaticintBinarySearch<
（T[]array,Tvalue）;
Array为要搜索的已排序一维数组；
value为要搜索的对象。
返回给定数据在数组中首次出现位置。
如果找到value，则返回值为指定array中的指定value的索引。
如果找不到value，则返回值一个负数re，并且它的按位补码i=~re正好是将value插入array并保持其排序的正确位置。
即，如果value小于array中的一个元素，则返回数组中大于value的第一个元素的索引的按位补码。
如果value大于array中的所有元素，则返回最后一个元素的索引加1的按位补码。
根据返回值的规则，如果返回值re<
0，则说明数组array中没有查找的数据value；
如果re=-1，则value<
array[~re]=array[0]；
如果~re=array.Length，则array[~re-1]=array[array.Length-1]<
value；
其他情况则有array[~re-1]<
value<
array[~re]。
2）publicstaticintBinarySearch<
（T[]array,intstartindex,intcount,Tvalue）;
返回给定数据在数组指定范围内首次出现位置。
如果找不到value，返回值的含义同上所述。
2.Hashtable和Dictionary
.NETFramework的类库中定义了表示（键，值）对的集合的类Hashtable，它定义在System.Collections名字空间中。
Hashtable类提供了表示（键，值）对的集合，集合中的每个元素都是一个存储在DictionaryEntry对象中的键/值对，这些（键，值）对根据键的哈希代码进行组织。
Hashtable的元素可以直接通过键来索引，如下例中用openWith[“txt”]可以得到它的值“notepad.exe”。
在.NETFramework2.0版本的类库中新增了类似于Hashtable类的Dictionary泛型类（在System.Collections.Generic名字空间中）。
【例8.1】创建并初始化Dictionary以及打印出其值。
usingSystem;
usingSystem.Collections.Generic;
classSamplesDictionary{
publicstaticvoidMain（）{
Dictionary<
string,string>
openWith=newDictionary<
（）;
openWith.Add（"
txt"
"
notepad.exe"
）;
bmp"
paint.exe"
dib"
rtf"
wordpad.exe"
openWith["
doc"
]="
winword.exe"
;
foreach（KeyValuePair<
kvpinopenWith）{
Console.WriteLine（"
Key={0},Value={1}"
kvp.Key,kvp.Value）;
}
\nRemove（\"
doc\"
）"
openWith.Remove（"
if（!
openWith.ContainsKey（"
））{
Key\"
isnotfound."
程序运行结果如下：
Key=txt,Value=notepad.exe
Key=bmp,Value=paint.exe
Key=dib,Value=paint.exe
Key=rtf,Value=wordpad.exe
Key=doc,Value=winword.exe
Remove（"
）
Key"
isnotfound.
8.2线性表的查找
线性表的查找方法有3种：
顺序查找，折半查找和分块查找。
要根据不同的条件选择合适的查找的方法，以求快速高效地得到查找结果。
8.2.1顺序查找
顺序查找（sequentialsearch）是一种最基本的查找算法，又称为线性查找（linearsearch）。
对于给定查找条件k，从线性表的指定位置开始，依次将k与每个数据元素的关键字进行比较，直到查找成功，或到达线性表的指定边界时仍没有找到关键字等于k的数据元素，则查找不成功。
在第2章介绍线性表时，我们在顺序表和链表中都实现了顺序查找算法，它们都以方法IndexOf的某种重载形式提供。
本章将第2章中定义的顺序表SequencedList进行修改，以定义顺序查找表LinearSearchList。
1.顺序查找的基本思想
设数据元素保存在顺序表中，对于一个给定值k，顺序查找算法描述如下：
●设i=0，比较第i个数据元素的关键字是否等于k，如果相等，则查找成功，查找过程结束；
否则i++，继续比较。
●线性表中所有数据元素的关键字都不等于k，则查找不成功。
顺序表的顺序查找过程如图8.1所示。
图8.1顺序存储线性表的顺序查找过程
2.顺序查找表的定义
顺序查找表定义为LinearSearchList类，它实现顺序表的顺序查找操作及其他操作。
publicclassLinearSearchList<
whereT:
IComparable{
privateT[]items;
//存储数据元素的数组
privateintcount;
//顺序表的长度
intcapacity=0;
//顺序表的容量
publicLinearSearchList（intcapacity）{
items=newT[capacity];
//分配capacity个存储单元
count=0;
//此时顺序表长度为0
this.capacity=capacity;
}
publicLinearSearchList（）:
this（16）{}
publicvoidAdd（Tk）{//将k添加到顺序表的结尾处
if（Full）{//resizearray
Capacity=capacity*2;
//doublecapacity
}
items[count]=k;
count++;
publicboolFull{get{returncount>
=capacity;
}}//判断顺序表是否已满
publicintCount{get{returncount;
}}//返回顺序表长度
publicintCapacity{get{returncapacity;
set{
if（value>
capacity）{
capacity=value;
T[]copy=newT[capacity];
//createnewlysizedarray
Array.Copy（items,copy,count）;
//copyoverthearray
items=copy;
//assignitemstothenew,largerarray
}
顺序查找算法实现在方法IndexOf中。
//查找k值在线性表中的位置,查找成功时返回k值首次出现位置，否则返回-1
publicintIndexOf（Tk）{
intj=0;
while（j<
count&
&
!
items[j].Equals（k））
j++;
if（j>
=0&
j<
count）
returnj;
elsereturn-1;
3.单向链表中的查找操作
如果数据保存在单向链表中，对于一个给定值k，顺序查找就是从链表的第一个数据结点沿着链接的方向依次与各结点数据进行比较，直至查找成功，或表中所有数据元素的关键字都不等于k，则查找不成功。
在第二章介绍的SingleLinkedList类中增加实现顺序查找算法的IndexOf方法如下：
publicintIndexOf（Tk）{
intj=0;
SingleLinkedNode<
q=head.Next;
while（q!
=null）{
if（k.Equals（q.Item））
returnj;
q=q.Next;
j++;
return-1;
4.算法分析
同前面的章节一样，线性表中的元素下标从零开始。
设线性表中元素的个数为n，查找第i个元素的概率为pi，在等概率情况下，pi=1/n。
如果线性表中第i个元素的关键字等于k，进行i+1次比较即可找到该元素。
对于成功的查找，关键字的平均查找长度ASL成功为
每个不成功的查找，都只有在n次比较后才能确定，故关键字的平均查找长度ASL不成功为n，即
可见，在等概率条件下，查找成功的平均查找长度约为线性表长度的一半，查找不成功的平均查找长度等于线性表的长度。
所以顺序查找算法的时间复杂度为O（n）。
8.2.2折半查找
如果顺序存储结构的数据元素已经按照关键字大小排序，则可以在其上进行折半查找，又称二分查找（binarysearch）。
1.折半查找的基本思想
不失一般性，假定线性表的数据元素是按照升序排列的，对于待查找关键字值k，从线性表的中间位置开始比较，如果当前数据元素的关键字等于k，则查找成功。
否则，若k小于当前数据元素的关键字，则以后在线性表的前半部分继续查找；
反之，则在线性表的后半部分继续查找。
依同样的原理重复进行这一过程，直至获得查找成功或不成功的结果。
例如，对于如下数据序列（仅考虑数据元素的关键字）：
{1,3,14,19,23,32,55,86}
设查找k=23，left和right分别为查找范围的左边界和右边界，计算mid=（left+right）/2，即设置mid是left和right的平均数（取整），将线性表下标为mid的数据元素与k进行比较。
折半查找算法描述如下：
●初始化left=0,right=7,此时mid=3，比较k与items[mid]，如图8.2（a）所示。
●因为k>
items[mid]，故以后只需在线性表的后半部继续比较，查找范围缩小，left上移，right不变，即令left=mid+1=4，right=7，则mid=5，如图8.2（b）所示。
●再比较k与items[mid]，有k<
items[mid]，说明只需在mid的前半部继续比较，查找范围缩小。
right下移，left不变，即令left=4，right=mid-1=4，则mid=4，如图8.2（c）所示。
此时若k=items[mid]，则查找成功，mid为查找到的数据元素的序号；
否则查找不成功。
图8.2折半查找的过程
2.折半查找算法实现
在顺序查找表LinearSearchList类中增加实现折半查找算法的BinarySearch方法。
该方法的参数与返回值与Array.BinarySearch相同。
//查找k值在线性表中的位置，查找成功时返回k值首次出现位置，否则返回应插入位置的位补码
//查找范围:
从下标si开始，包含length个元素
publicintBinarySearch（Tk,intsi,intlength）{
intmid=0,left=si;
intright=left+length-1;
while（left<
=right）{
mid=（left+right）/2;
if（k.CompareTo（items[mid]）==0）returnmid;
elseif（k.CompareTo（items[mid]）<
0）
right=mid-1;
else
left=mid+1;
if（k.CompareTo（items[mid]）>
mid++;
return~mid;
【例8.2】创建顺序查找表，对其进行排序后测试折半查找算法。
usingsearch;
namespacesearchtest{
classLinearSearchListTest{
staticvoidMain（string[]args）{
intn=10;
LinearSearchList<
int>
sl=newLinearSearchList<
（n+8）;
Randomize（sl,n）;
Console.Write（"
随机排列：
"
sl.Show（true）;
排序后：
sl.Sort（）;
intk=50;
intre=sl.BinarySearch（k,0,n）;
{0}{1},{2}"
k,re,~re）;
//用0到100之间的随机整数填充线性表
staticvoidRandomize（LinearSearchList<
sl,intn）{
intk;
Randomrandom=newRandom（）;
for（inti=0;
i<
n;
i++）{
k=random.Next（100）;
sl.Add（k）;
}
LinearSearchList:
73567953797099992936
排序后：
29365356707379799999
50-3,2
3.算法分析
在长度n=8的线性表中进行折半查找的过程如图8.3所示，折半查找过程形成一棵二叉判定树。
结点中的数字表示线性表中数据元素的下标。
二叉判定树反映了折半查找过程中，进行关键字比较的数据元素次序。
当n=8时，线性表的左边界为0，即left=0，右边界为7，即right=7，第一次k与下标为mid=（0+7）/2=3的数据元素比较，若k值较小，再与下标为1的数据元素比较，否则与下标为5的数据元素比较；
依同样的方法继续查找。
设二叉判定树的高度为h，则h满足下式：
2h–1<
n≤2h+1–1
在二叉判定树中，一次成功的查找恰好走过一条从根结点到某结点的路径。
比较次数最少为1次，最多为
，平均比较次数为
。
不成功的查找路径则从根结点到叶子结点，平均比较次数也为
折半查找算法每比较一次，如果查找成功，算法结束；
否则，将查找的范围缩小一半。
而顺序查找算法在每一次比较后，仅将查找范围缩小了一个数据元素。
因此，折半查找算法的平均效率比顺序查找算法高。
顺序查找算法简单，对原始数据不要求已排序，适用于顺序存储结构和链式存储结构；
折半查找算法虽然减少了查找次数，速度较快，但条件严格，要求数据序列是顺序存储结构的并且已排序，而对数据序列进行排序也是要花费一定代价的。
图8.3折半查找过程的二叉判定树
8.2.3分块查
升级会员 