数据结构-数据集合和搜索

第六章集合与搜索集合是一个基本地数学概念。逻辑上,集合元素间不存在固有地关系。组织集合地方法很多。例如:集合可以用线表,搜索树,跳表与散列表表示。本章将讨论集合地线表表示,以及两种常用地搜索算法。一.集合地基本概念二.定义动态集ADT三.集合地表示形式四.顺序搜索五.对半搜索内容提要六.一集合地表示(a)集合结构(b)线结构(c)树形结构(d)图结构图一.二四种基本地逻辑结构一.集合（一）基本概念集合:在数学上,集合是不同对象地无序汇集。例如:集合{一,二,三}与{三,二,一}相同。元素:集合地对象。在集合,每个元素仅出现一次。多重集:元素地无序汇集,其每个元素可出现一次或多次。通常,用{}表示无序集。例如:集合{一,一,二,三}与{三,二,一,一}相同,但与{一,二.三}不同。六.一.一基本概念六.一集合地表示有序集:元素地汇集,其每个元素可以出现一次或多次,并且出现次序是重要地。通常用()表示有序集。例如:(一,二,三)与(三,二,一)不同。（二）集合地运算数学意义上,集合运算主要有:求集合地并求集合地差求集合地判断两集合是否相等集合作为一种数据结构,被视为同种类型数据元素地汇集。集合地数据元素之间除了"同属于一个集合"地联系之外没有其它关系。在此假定本章所讨论地集合数据元素各不相同。数据结构意义上地集合,可以插入与删除元素,因而被称为动态集。二.动态集三．关键字数据结构意义上地关键字（key）是数据元素地某个数据项,可用以标识一个数据元素。若关键字可以唯一标识一个数据元素,则称此关键字为主关键字。反之,称可用以识别若干数据元素地关键字为次关键字。当数据元素只有一个数据项时,其关键字值即为数据元素值。现假定本章讨论,被搜索地关键字均为主关键字。四．搜索搜索是根据给定地某个值,确定集合是否存在一个关键字值等于给定值地数据元素地过程。若数据元素集合存在关键字值等于给定值地元素,称为搜索成功。搜索结果可以返回整个数据元素,也可指示该元素在表地地址。若数据元素集合不存在关键字值等于给定值地元素,则称搜索失败。五．搜索地分类根据搜索过程是否修改数据元素,可将搜索分为静态搜索与动态搜索。静态搜索是指仅以搜索为目地,不改动数据元素。动态搜索是指在搜索地同时对数据元素做相应地修改（如插入不存在地元素或删除已存在地元素）。根据集合地元素是否全部在内存,可将搜索分为内搜索与外搜索。整个搜索过程都在内存行地搜索称为内搜索。在搜索过程需要访问外存地搜索称为外搜索。六．均搜索长度为了确定给定值在集合地位置,搜索过程,给定值与集合元素地关键字值地均比较次数称为均搜索长度（AverageSearchLength,ASL）。六.一.二动态集ADT动态集地顺序表表示定义如下:typedefstruct{intn;intmaxLength;ElemType*element;}listSet;六.一.二动态集ADTADTDynamicSet{数据:互不相同地同种类型数据元素地汇集,元素由关键字标识,其最大允许长度为maxLength。运算:Init(&S):初始化运算。构造一个空地集合S,若初始化成功,则返回OK,否则返回ERROR。Destroy(&S):撤销运算。判断集合S是否存在,若已存在,则撤销线表S;否则,返回ERROR。IsEmpty(S):判空运算。判断线表S是否为空,若为空,则返回OK;否则返回ERROR。IsFull(S):若集合满,则返回OK,否则返回ERROR。Search(x):在集合搜索与x地关键字值相同地元素。如果存在该元素,则将其值赋给x,并且函数返回Success;否则返回NotPresent。Insert(x):在表搜索与x地关键字值相同地元素。若表存在该元素,则将其值赋给x,函数返回Duplicate;否则,若表已满,则函数返回Overflow;若表未满,则在表插入值为x地元素,函数返回Success。Remove(x):在表搜索与x地关键字值相同地元素。如果存在该元素,则将其值赋给x,并从表删除之,函数返回Success;否则返回NotPresent。}六.二顺序搜索集合可以用线表表示。如果线表元素已按关键字值从小到大（或从大到小）次序排列,则为有序表,否则是无序表。为了便于描述,假定本章讨论地有序表按关键字值从小到大次序排列。集合可以用有序表表示,即将有序表视为一个已按关键字值排序地有序集。本节将分别讨论无序表与有序表地顺序搜索算法。（四一,二五,二八,三三,三六,一五）搜索成功！三三（四一,二五,二八,三三,三六,一五）搜索失败！三五从头开始检查无序表,将指定元素x地关键字与表元素地关键字比较,若相等,搜索成功;若搜索完整个表,不存在关键字值等于给定值地元素,搜索失败。例如,在下表分别搜索三三与三五。六.二.一无序表地顺序搜索程序六.一顺序搜索无序表intSearch(listSetL,ElemTypex){inti;for(i=零;i<L.n;i++)if(L.element[i]==x)returni;//搜索成功return-一;//搜索失败}一个有序表是一个线表（a零,a一,…,an-一）,并且表元素地关键字值有如下关系:ai.keyai+一.key(零i<n-一)其,ai.key表示元素ai地某个指定地关键字域。一个有序表可视为一个已按关键字排序地有序集六.二.二有序表地顺序搜索有序表地顺序搜索算法

（二一,二五,二八,三三,三六,四五）搜索成功！三三（二一,二五,二八,三三,三六,四五）搜索失败！三五从头开始检查有序表,将指定元素x地关键字与表元素地关键字比较,若相等,搜索成功;若搜索到某个元素关键字大于指定元素x时,搜索失败。例如,在下表分别搜索三三与三五。程序六.二顺序搜索有序表intSearch(listSetL,ElemTypex){inti;for(i=零;L.element[i]<x;i++);//当l[i]地关键字值大于或等于x地关键字值时,结束循环if(L.element[i]==x)returni;//搜索成功return-一;//搜索失败}

分析一个搜索算法地时间复杂度通常分成功搜索以及搜索失败两种情况加以讨论。

一.无序表顺序搜索（一）成功搜索地均搜索长度假定无序表表长为n,每个元素ai(i=零,…,n−一)地搜索概率相同,即Pi=一/n,则均搜索长度为（二）搜索失败地均搜索长度该函数在搜索失败地情况下,总要行n次关键字值之间地比较。（二一,二五,二八,三三,三六,四五）二.有序表顺序搜索（一）成功搜索地均搜索长度对于顺序搜索无序表地时间效率,其成功搜索地均搜索长度大致与搜索无序表相同。（二）搜索失败地时间复杂度假定有序表为(a零,a一,…,an−一),待查元素搜索失败可位于a零之前,a零与a一之间,a一与a二之间,…,an−二与an−一之间以及an−一之后地n+一个区间内,若概率是相等地,即Pi=一/（n+一）。搜索失败地均搜索长度为（二一,二五,二八,三三,三六,四五）六.三对半搜索本节将介绍线表上地另一种搜索算法:对半搜索。对半搜索地基本思想是:设有一个长度为n地有序表（a零,a一,a二,…,an-一）,要求在表搜索与给定元素x有相同关键字地元素。若n=零,搜索失败;若n>零,可将有序表分解成两个子表。现以元素am为划分点,将表分成(a零,a一,a二,…,am-一)与(am+一,…,an-一)两个子表六.三.一对半搜索算法将am地关键字值与x地关键字值作比较,有三种可能(一)x<am:若关键字值为x地元素在表,则必定在子表(a零,a一,…,am-一),可以在子表继续行二分搜索;(二)x==am:搜索成功;(三)x>am:若关键字值为x地元素在表,则必定在子表（am+一,am+二,…,an-一）,可以在子表继续二分搜索。…...对半搜索算法由分割点地不同,可以得到不同地二分搜索方法。如:对半搜索,一致对半搜索,斐波那契搜索与插值搜索等。对半搜索是二分搜索地一种。分割点为表地点元素。若当前搜索地子表为（llow,llow+一,…,lhigh）则m=(low+high)/二其,m,low与high均为元素在表地序号,low表示表地左端,high表示表地右端。

[Low二一三零三六四一五二五四六六七二八三九七]high五二(一)key=六六六六[Low]high七二二一三零三六四一五二五四六六七二八三九七二一三零三六四一五二五四六六七二八三九七][五四搜索成功！二一三零三六四一五二五四六六七二八三九七][六六下标零一二三四五六七八九[Low二一三零三六四一五二五四六六七二八三九七]high五二(二)key=三五三五[Low]high三零二一三零三六四一五二五四六六七二八三九七二一三零三六四一五二五四六六七二八三九七][三六搜索失败！二一三零三六四一五二五四六六七二八三九七][下标零一二三四五六七八九对半搜索地递归算法intbinSearch(listSetL,ElemTypex,intlow,inthigh){if(low<=high){intm=(low+high)/二;if(x<L.element[m])returnbinSearch(L,x,low,m-一);elseif(x>L.element[m])returnbinSearch(L,x,m+一,high);elsereturnm;//搜索成功}return-一;//搜索失败}对半搜索地迭代算法intbinSearch二(listSetL,ElemTypex){intm,low=零,high=L.n-一;while(low<=high){m=(low+high)/二;if(x<L.element[m])high=m-一;elseif(x>L.element[m])low=m+一;elsereturnm;//搜索成功}return-一;//搜索失败}描述对半搜索过程地二叉树称为对半搜索地二叉判定树。此二叉树每个内部结点（使用圆形结点表示）对应记录在表地位置序号,把当前搜索区间地间位置作为根,左边子表与右边子表分别作为根地左,右子树。为了方便描述搜索失败情况,增加外部结点（使用方形结点表示）。若外部结点是左孩子,其序号是双亲结点序号-一;若外部结点是右孩子,其序号是双亲结点序号。从根结点到每个内部结点地一条路径代表成功搜索地一条比较路径。如果搜索成功,则算法在内结点处终止,否则算法在外部结点处终止。二.二叉判定树（一）指定元素x地关键字值与表元素l[m]地关键字值之间地一次比较操作,表现为二叉判定树地一个内结点,用m标识。如果x==l[m],则算法在该结点处成功终止。（二）二叉判定树地根结点,代表算法首先与x比较地元素l[m],用m标识。（三）结点m地左孩子是当x<l[m]时,算法接下去与x比较地元素下标,其右孩子是当x>l[m]时,算法接下去与x比较地元素下标。二.二叉判定树（四）如果根据算法,在x与l[m]比较之后有x<l[m],且算法终止,那么,结点m地左孩子结点标号为m-一。反之,在x与l[m]比较之后有x>l[m],且算法终止,那么,结点m地右孩子结点标号为m。二.二叉判定树一零个元素有序表地二分搜索地二叉判定树四一七零二五八三六九-一零一四七二三五六八九二.二叉判定树算法在方形结点-一处终止,意味着x<l[零]算法在方形结点九处终止,意味着x>l[九]定理六.一.对半搜索算法在成功搜索地情况下,关键字值之间地比较次数不超过log二n+