《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS08-查找》由会员分享，可在线阅读，更多相关《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS08-查找（76页珍藏版）》请在金锄头文库上搜索。
1、基本概念 线性表的查找 树表的查找 散列(Hash)技术,第八章 查找,8.1查找的基本概念,查找（Searching）的定义是：给定一个关键字值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。,查找表的数据结构表示 若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。 若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找,平均查
2、找长度 ASL（Average Search Length）定义为 ：,ASL=,其中： 1、n是结点的个数； 2、Pi是查找第i个结点的概率。若不特别声明 ，认为每个结点的查找概率相等，即 pl = p2 = pn = 1/n 3、ci是找到第i个结点所需进行的比较次数。,顺序查找(Sequential Search) 基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。,8.2线性表的查找,基于顺序结构的顺序查找算法,类型说明 typedef struct
3、KeyType key； /* KeyType由用户定义 */ InfoType otherinfo； /* 此类型依赖于应用 */ NodeType； typedef NodeType Seqlistn+1； /*多出0号单元用作监视哨*/,具体算法 int SeqSearch(Seqlist R，KeyType K) /*在顺序表R1n中顺序查找关键字为K的结点， 成功时返回找到的结点位置，失败时返回0*/ int i； R0.key=K； /*设置监视哨*/ for(i=n；Ri.key!=K;i-)； /*从表后往前找*/ return i； /*若i为0，表示查找失败，否则Ri为要找
4、的结点*/ /*SeqSearch*/,算法分析,生成林成功时的顺序查找的平均查找长度： ASL= =pi =np1+(n-1)p2+2pn-1+pn （式8.2） 在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为 (n+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。,顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。 顺序查找的缺点 查找效率低。,二分查找又称折半查找，它是一种效率较高的查找方法。 二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存
5、储结构。不妨设有序表是递增有序的。,二分查找,二分查找的基本思想是： （1）首先确定该区间的中点位置： mid = （2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。,二分查找算法 int BinSearch(SeqList R，KeyType K) int low=1，high=n，mid； while(lowK) high=mid-1; else low=mid+1； return 0； ,例：设算法的输入实例中有序的关键字序列为： 05，13，19，21，37，56，64，75，80，88，92查找的关键字K=21,第一步
6、：05，13，19，21，37，56，64， 75，80，88，92,第二步：05，13，19，21，37，56，64， 75，80，88，92,第三步：05，13，19，21，37，56，64， 75，80，88，92 此时Rmid.keyK，return mid4。,二分查找判定树 二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。,二分查找判定树的组成,圆结点即树中的内部结点。树中圆结点内的数字表示该结点
7、在有序表中的位置。 外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。 当查找时找到外部节点时，表示查找的值没有在该有序表中,二分查找的平均查找长度,二分查找成功时的平均查找长度为： ASLbnlg(n+1)-1 二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：,二分查找的优点和缺点,虽然二分查找的效率高，但是要将表按关键字排序。 二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。,分块查找,分块查找表存储结构 分块查找表由“分块有序“的线性表和索引表组成。,分块
8、查找的基本思想 ： 首先查找索引表 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。 然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。,查找关键字等于给定值K=24的结点 (见P199),因为索引表小，不妨用顺序查找方法查找索引表。即首先将K依次和索引表中各关键字比较，直到找到第1个关键宇大小等于K的结点，由于K48，所以关键字为24的结点若存在的话，则必定在第二块中；然后，由ID2.addr找到第二块的起始地址7，从该地址开始在R712中进行顺序查找，直到R11.key=K为止。,算法分析,分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查
9、找长度之和。 以二分查找来确定块，分块查找成功时的平均查找长度 ASLblk=ASLbn+ASLsqlg(b+1)-1+(s+1)/2lg(n/s+1)+s/2 以顺序查找确定块，分块查找成功时的平均查找长度 ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s),分块查找的优点 在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。 因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。,8.3 树表的查找,1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tr
10、ee)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值； （3）左、右子树本身又各是一棵二叉排序树。,二叉排序树的特点 （1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键字是惟一的。 （3） 按中序遍历该树所得到的中序序列是一个递增有序序列。,二叉排序树的存储结构,typedef int KeyType； typedef struct node KeyType key；
11、 InfoType otherinfo； struct node *lchild，*rchild； BSTNode； typedef BSTNode *BSTree；,二叉排序树插入新结点的过程 在二叉排序树中插入新结点，要保证插入后仍满足BST性质。其插入过程是： 1)若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根； 2)若二叉排序树T不为空，则将key和根的关键字比较： (a)若二者相等，则说明树中已有此关键字key，无须插入。 (b)若keyTkey，则将它插入根的右子树中。,二叉排序树插入新结点的算法 void InsertBST(BSTree *Tptr，Ke
12、yType key) BSTNode *f，*p=*TPtr； while(p) if(p-key=key) return； f=p； p=(keykey)?p-lchild：p-rchild； ,p=(BSTNode *)malloc(sizeof(BSTNode)； p-key=key； p-lchild=p-rchild=NULL； if(*TPtr=NULL) *Tptr=p； else if(keykey) f-lchild=p； else f-rchild=p； ,二叉排序树的生成 是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。,
13、BSTree CreateBST(void) BSTree T=NULL； KeyType key； scanf(“d“，&key)； while(key) InsertBST(&T，key)； scanf(“d“，&key)； return T； ,生成二叉排序树的算法 见右边,输入实例(5，3，7，2，4，8)，根据生成二叉排序树算法生成二叉排序树的过程,二叉排序树的删除,从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足BST性质。 删除操作的一般步骤 1) 进行查找 查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NUL
14、L)。若树中找不到被删结点则返回，否则被删结点是*p。,2) 删去*p。 删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。 删除*p结点的三种情况 1)*p是叶子(即它的孩子数为0) 无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。 2)*p只有一个孩子*child 只需将*child和*p的双亲直接连接后，即可删去*p。,3)*p有两个孩子 先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它
15、无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。,二叉排序树删除算法,void DelBSTNode(BSTree *Tptr，KeyType key) BSTNode *parent=NUll，*p=*Tptr，*q，*child； while(p) if(p-key=key) break； parent=p； p=(keykey)?p-lchild：p-rchild； if(!p) return； q=p； if(q-lchild&q-rchild) for(parent=q，p=q-rchild； p-lchild；,parent=p，p=p=-lchild)； child=(p-lchild)?p-lchild：p-rchild； if(!parent) *Tptr=child； else if(p=parent-lchild) parent-lchild=child； else parent-rchild=child； if(p!=q) q-key=p-key； free(p)； ,二叉排序树上的查找,在二叉排序树上进
