数据结构电子教案搜索结构.ppt

《数据结构电子教案搜索结构.ppt》由会员分享，可在线阅读，更多相关《数据结构电子教案搜索结构.ppt（37页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 1第七章 搜索结构数据结构电子教案数据结构电子教案2 2第七章第七章 搜索结构搜索结构3 3搜索搜索(Search)(Search)的概念的概念静态搜索表静态搜索表n所谓所谓搜索搜索，就是在数据集合中寻找满足某种，就是在数据集合中寻找满足某种条件的数据对象。条件的数据对象。n搜索的结果通常有两种可能：搜索的结果通常有两种可能：搜索成功搜索成功，即找到满足条件的数据对象。，即找到满足条件的数据对象。这时，作为结果，可报告该对象在这时，作为结果，可报告该对象在结构中结构中的的位置位置, 还可给出该对象中的具体信息。还可给出该对象中的具体信息。搜索不成功搜索不成功，或搜索失败。作为结果，应，或搜

2、索失败。作为结果，应报告一些信息报告一些信息, 如失败标志、位置如失败标志、位置等。等。4 4n通常称用于搜索的数据集合为通常称用于搜索的数据集合为搜索结构搜索结构，它，它是由同一数据类型的对象是由同一数据类型的对象(或记录或记录)组成。组成。n在每个对象中有若干属性，其中有一个属性，在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为其值可唯一地标识这个对象。称为关键码关键码。使用基于关键码的搜索，搜索结果应是唯一使用基于关键码的搜索，搜索结果应是唯一的的。但在实际应用时，搜索条件是多方面的，。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可以使

3、用基于属性的搜索方法，但搜索结果可能不唯一。可能不唯一。n实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。u静态环境静态环境，搜索结构在插入和删除等操作，搜索结构在插入和删除等操作的前后不发生改变。的前后不发生改变。 静态搜索表静态搜索表 5 5u动态环境动态环境，为保持较高的搜索效率，为保持较高的搜索效率, , 搜索搜索结构在执行插入和删除等操作的前后将自结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。动进行调整，结构可能发生变化。 动态搜索表动态搜索表n在静态搜索表中，数据元素存放于数组中，在静态搜索表中，数据元素存放于数组中，利用数组元素的下标作为数据元素的存放

4、地利用数组元素的下标作为数据元素的存放地址。搜索算法根据给定值址。搜索算法根据给定值 k，在数组中进行，在数组中进行搜索。直到找到搜索。直到找到 k 在数组中的存放位置或可在数组中的存放位置或可确定在数组中找不到确定在数组中找不到 k 为止。为止。 静态搜索表静态搜索表6 6数据表与搜索表的类定义数据表与搜索表的类定义 #include #include using namespace std;template class dataList; / 前视定义template class dataNode / 数据表中结点类的定义 friend class dataList; / 声明友元类pri

5、vate:7 7 K key;/ 关键码域 E other; / 其他域，视问题而定public: dataNode ( ) / 构造函数 K getKey( ) const return key; / 读取关键码 void setKey (const K x) key = x; / 修改关键码; template class dataList / 数据表类定义protected:8 8 dataNode *Element;/ 数据表存储数组 int ArraySize, CurrentSize;/ 数组长度和元素个数public: dataList (int sz) : ArraySize(

6、sz), CurrentSize(0) Element = new dataNodesz; assert (Element != NULL); dataList (dataList& R); / 复制构造函数 virtual dataList( ) delete Element; / 析构函数 9 9 virtual int Length( ) const return CurrentSize; virtual K getKey (const int i) const / 提取第 i（0 开始）元素值 assert (i = 0 & i = 0 & i CurrentSize); Elemen

7、ti.key = x; 1010 virtual bool Insert (const dataNode& e1); / 插入 virtual bool Remove (const K x, E& e1); / 删除 void output( ) const;/ 输出void input( );/ 输入 ;template bool dataList:Insert (const dataNode& e1) / 在dataList的尾部插入新元素, 若插入失败函数返/ 回false, 否则返回true.11 11 if (CurrentSize = ArraySize) return false

8、; ElementCurrentSize = e1;/ 插入在尾端 CurrentSize+; return true;template bool dataList:Remove (const K x, E& e1) / 在dataList中删除关键码为x的元素, 通过e1返回。/ 用尾元素填补被删除元素。 if (CurrentSize = 0) return false; int i; for (i = 0; i CurrentSize & Elementi.key != x; i+); / 在表中顺序寻找1212 if (i = CurrentSize) return false; /

9、未找到 e1 = Elementi.other; / 找到,保存被删元素的值 Elementi = ElementCurrentSize-1; / 填补 CurrentSize-; return true;template void dataList:output( ) const cout 数组中的元素为： endl; for (int i = 0; i CurrentSize; i+) cout Elementi.key ; cout endl;1313 cout 元素个数 : CurrentSize endl;template void dataList:input( ) cout Cu

10、rrentSize;cout 输入数组元素的关键码: n; for (int i = 0; i CurrentSize; i+) cout 元素 i + 1 Elementi.key; 1414n顺序搜索主要用于在顺序搜索主要用于在线性表线性表中搜索。中搜索。n设若表中有设若表中有 CurrentSize 个元素，则顺序搜个元素，则顺序搜索从表的先端开始，顺序用各元素的关键码索从表的先端开始，顺序用各元素的关键码与给定值与给定值 x 进行比较进行比较n若找到与其值相等的元素，则搜索成功，给若找到与其值相等的元素，则搜索成功，给出该元素在表中的位置。出该元素在表中的位置。n若整个表都已检测完仍未

11、找到关键码与若整个表都已检测完仍未找到关键码与 x 相相等的元素，则搜索失败。给出等的元素，则搜索失败。给出失败信息失败信息 ( 这这里用里用 -1 表示表示 )。顺序搜索（顺序搜索（Sequential SearchSequential Search） 1515n一般的顺序搜索算法在第二章已经讨论过，本一般的顺序搜索算法在第二章已经讨论过，本章介绍一种使用章介绍一种使用“监视哨监视哨”的顺序搜索方法。的顺序搜索方法。n设在设在数据表数据表 dataList 中顺序搜索关键码与给中顺序搜索关键码与给定值定值 x 相等的数据元素，要求数据元素在表中相等的数据元素，要求数据元素在表中从下标从下标

12、0 开始存放开始存放, 下标为下标为 CurrentSize 的元的元素作为控制搜索过程自动结束的素作为控制搜索过程自动结束的“监视哨监视哨”使使用。用。n若搜索成功，则函数返回该元素在表中序号若搜索成功，则函数返回该元素在表中序号 Location（下标）（下标）, 若搜索失败，则函数返回若搜索失败，则函数返回 -1。1616顺序搜索表类顺序搜索表类 const int defaultSize = 100;template class SearchList : public dataList public:SearchList(int sz = defaultSize) : dataList

13、(sz) int SeqSearch (const K x) const; / 顺序搜索int SeqSearch (const K x, int loc)const; / 递归搜索;1717使用监视哨的顺序搜索算法使用监视哨的顺序搜索算法 template int SearchList:SeqSearch (const K x) const ElementCurrentSize.setKey(x); / 监视哨 int i = 0; while (Elementi+.getKey( ) != x) ; /从前向后顺序搜索 return (i = CurrentSize ? -1 : i);c

14、onst int Size = 10;void main (void) 1818 dataList L1 (Size);/ 定义搜索表L1 int Target; int Loc; L1.input( ); L1.output( );/ (修改教材) cout Target;/ 输入要搜索的数据 if ( (Loc = L1.SeqSearch(Target) = 0 ) cout 找到待查元素位置在： Loc + 1 endl;/ 搜索成功 else cout 没有找到待查元素！ endl; / 搜索不成功1919n设数据表中有设数据表中有 n 个元素，搜索第个元素，搜索第 i 个元素的个元

15、素的概率为概率为 pi，搜索到第，搜索到第 i 个元素所需比较次数个元素所需比较次数为为 ci，则搜索成功的平均搜索长度，则搜索成功的平均搜索长度:n在顺序搜索并设置在顺序搜索并设置“监视哨监视哨”情形：情形： ci = i +1, i = 0, 1, , n-1，因此，因此1010niiniiisuccpcpASL) 1 ( .)(110ipASL-niisucc顺序搜索的平均搜索长度顺序搜索的平均搜索长度2020n一般表中各个元素的搜索概率不同，如果按一般表中各个元素的搜索概率不同，如果按搜索的概率从高到低搜索的概率从高到低排列表中的元素，从有排列表中的元素，从有序顺序表的情况可知序顺序表

16、的情况可知，可以得到，可以得到高高的搜索效的搜索效率。率。n在等概率情形，在等概率情形，pi = 1/n, i = 1, 2, , n。搜索。搜索成功的平均成功的平均搜索长度搜索长度为：为：n在搜索不成功情形，在搜索不成功情形，ASLunsucc = n +1。.)()(1-nisuccnnnninASL021211112121n采用递归方法搜索值为采用递归方法搜索值为 x 的元素，每递归一的元素，每递归一层就向待查元素逼近一个位置，直到到达该层就向待查元素逼近一个位置，直到到达该元素。假设待查元素在第元素。假设待查元素在第 i（0 i n）个位）个位置，则算法递归深度达置，则算法递归深度达

17、i（0 i）。）。10 20 30 40 50 60i = 1搜索搜索 3010 20 30 40 50 60i = 210 20 30 40 50 60i = 3递递归归顺序搜索的递归算法顺序搜索的递归算法2222顺序搜索的递归算法顺序搜索的递归算法template int dataList:SeqSearch (const K x, int loc) const / 在数据表 Element0 n-1 中搜索其关键码与给/ 定值匹配的对象, 函数返回其表中位置。参数 loc/ 是在表中开始搜索位置 if (loc = CurrentSize) return -1; / 失败 else if

18、 (Elementloc.getKey( ) = x) / 搜索成功return loc; else return SeqSearch (x, loc+1); / 递归搜索2323template class SortedList : public dataListpublic: SortedList(int sz = 100): dataList(sz) int Search (const K x) const; / 顺序搜索 int BinarySearch (const K x) const;/ 折半搜索 int BinarySearch (const K x, int low, int

19、 high) const; / 递归折半搜索;有序顺序表有序顺序表的类定义的类定义2424基于有序顺序表的顺序搜索算法基于有序顺序表的顺序搜索算法template int SortedList:SeqSearch (const K x) const / 顺序搜索关键码为x的数据对象for (int i = 0; i x) break; / 失败return -1; 2525有序顺序表顺序搜索的时间代价有序顺序表顺序搜索的时间代价n衡量一个搜索算法的时间效率的标准是：在衡量一个搜索算法的时间效率的标准是：在搜索过程中关键码平均比较次数，也称为平搜索过程中关键码平均比较次数，也称为平均搜索长度均搜

20、索长度ASL (Average Search Length)，通常它是搜索表中元素总数通常它是搜索表中元素总数 n 的函数。的函数。n设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi , 搜索到第搜索到第 i 个个元素所需比较次数为元素所需比较次数为 ci , 则搜索成功的平均则搜索成功的平均搜索长度搜索长度:niiniiisuccpcpASL11) 1 ( .2626n在顺序搜索情形，搜索第在顺序搜索情形，搜索第 i (0i n) 个元素个元素需要比较需要比较 i 次，假定按等概率搜索各元素：次，假定按等概率搜索各元素：n这与一般顺序表情形相同。但搜索不成功时这与一般顺序表情形相同。

21、但搜索不成功时不需一直比较到表尾，只要发现下一个元素不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。的值比给定值大，就可断定搜索不成功。n设一个有设一个有 n 个表项的表，查找失败的位置有个表项的表，查找失败的位置有n + 1个，可以用个，可以用判定树判定树加以描述。加以描述。搜索成功搜索成功时停在内结点，搜索失败时停在外结点。时停在内结点，搜索失败时停在外结点。2121)(1111nnnnincpASLniiniisucc2727n例如，有序顺序表例如，有序顺序表 (10, 20, 30, 40, 50, 60)的顺序搜索的分析（使用判定树）的顺序搜索的分析（使用判

22、定树）105060203040611762succiASLi06(1)i512777unsucciASL2828n判定树判定树是一种扩充二叉树。内结点代表顺序是一种扩充二叉树。内结点代表顺序表中已有的元素，外结点代表失败结点，它表中已有的元素，外结点代表失败结点，它表示在两个相邻已有元素值之间的值。表示在两个相邻已有元素值之间的值。n假定表中所有失败位置的搜索概率相同，则假定表中所有失败位置的搜索概率相同，则搜索不成功的平均搜索长度：搜索不成功的平均搜索长度：n时间代价为时间代价为O(n)。为了加速搜索，在有序顺。为了加速搜索，在有序顺序表的情形，可以采用序表的情形，可以采用折半搜索折半搜索，

23、它也称，它也称二二分搜索分搜索，时间代价可降到，时间代价可降到O(log2n)。-1(1)011nunsucciASLinn=骣=+桫2929基于有序顺序表的折半搜索基于有序顺序表的折半搜索n设设 n 个元素存放在一个有序顺序表中。个元素存放在一个有序顺序表中。n折半搜索时折半搜索时, 先求先求位于搜索区间正中的元素的位于搜索区间正中的元素的下标下标 mid，用其关键码与给定值用其关键码与给定值 x 比较比较:u Elementmid.key = x，搜索成功；搜索成功；u Elementmid.key x，把搜索区间缩小到把搜索区间缩小到表的表的前半部分前半部分，继续折半搜索；，继续折半搜索

24、；u Elementmid.key x，把搜索区间缩小到把搜索区间缩小到表的表的后半部分后半部分，继续折半搜索。，继续折半搜索。n如果搜索区间已缩小到一个对象，仍未找到如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。想要搜索的对象，则搜索失败。3030搜索成功的例子搜索成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high63131搜索失败的例子搜索失败的例子- -1 0 1 3 4 6 8 10 1250 1 2

25、 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high53232templateint SortedList:BinarySearch (const K x, int low, int high ) const / 折半搜索递归算法 int mid = -1; / 元素序号从 0 开始 if (low = high) mid = (low + high) / 2;if (Elementmid.getKey( ) x)mid = BinarySearch (x, low, mid - 1); ret

26、urn mid;3333template int SortedList :BinarySearch (const K x) const / 折半搜索的迭代算法 int high = CurrentSize - 1, low = 0, mid; while (low = high) mid = (low + high) / 2;if (Elementmid.getKey( ) x)high = mid - 1;/ 左缩搜索区间else return mid; / 搜索成功 return -1;3434n分析有序顺序表分析有序顺序表 ( 10, 20, 30, 40, 50, 60 ) 的折的折半

27、搜索算法性能的判定树：半搜索算法性能的判定树：105030204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 3535n判定树也是判定树也是扩充二叉树扩充二叉树，搜索成功时检测指针，搜索成功时检测指针停留在树中某个内结点上。搜索不成功时检测停留在树中某个内结点上。搜索不成功时检测指针停留在某个外结点（失败结点）上。指针停留在某个外结点（失败结点）上。n下面的例子是一棵普通判定树。下面的例子是一棵普通判定树。3636折半搜索算法的性能分析折半搜索算法的性能分析n若设若设 n = 2h-1，则描述折半搜索的判定树

28、是高则描述折半搜索的判定树是高度为度为 h 的满二叉树。的满二叉树。 2h = n + 1, h = log2(n + 1)n第第 1 层结点有层结点有 1 个个, 搜索第搜索第 1 层结点要比较层结点要比较 1次次; 第第 2 层结点有层结点有 2 个个, 搜索第搜索第 2 层结点要比层结点要比较较 2 次次; , 第第 i (1ih) 层结点有层结点有 2i-1 个个, 搜搜索第索第 i 层结点要比较层结点要比较 i 次，次，。n假定每个结点的搜索概率相等，即假定每个结点的搜索概率相等，即 pi = 1/n，则搜索成功的平均搜索长度为则搜索成功的平均搜索长度为3737121)(221)( 23222112210hhhhhh=-+=+-+=+-+-22211 (1) 21)(1)log (1)1 log (1)1log (1)1hsuccASLhnnnnnnnnn可以用归纳法证明可以用归纳法证明这样，由这样，由 2h = n+1, h = log2(n+1)223222(11 -1210hsucchnASL