C语言数据结构_第07讲 查找

《C语言数据结构_第07讲 查找》由会员分享，可在线阅读，更多相关《C语言数据结构_第07讲 查找（60页珍藏版）》请在金锄头文库上搜索。

1、实用数据结构基础第8章 查找第 8 章 查 找知 识 点查找的基本概念静态查找的基本方法：顺序查找、二分 查找和分块查找二叉排序树查找哈希函数和解决冲突的方法难 点二叉排序树查找平衡树二叉树要 求 熟练掌握以下内容：三种基本查找方法的基本思想和算 法二叉排序树查找的基本思想和算法散列函数的常用构造方法及解决冲 突方法 了解以下内容：平衡树及平衡树的调整第 8 章 目录8-1 查找的基本概念8-2 静态查找表8-3 动态查找表8-4 哈 希 表小结实验8 查找子系统习题88-1 查找的基本概念图8-1 学生招生录取登记表学号姓名性别别入学总总分录录取专业专业20010983张张三女438计计算机

2、20010984李四男430计计算机20010985王五女445计计算机20010998张张三男458计计算机首先介绍几个有关查找的基本概念：（1）查找表由同一类型的数据元素（或记录）构 成的集合称为查找表。如图8-1的学生招生录取登记表。（2）对查找表进行的操作： 查找某个特定的数据元素是否存在； 检索某个特定数据元素的属性； 在查找表中插入一个数据元素； 在查找表中删除一个数据元素。（3）静态查找（Static Search Table）在查找过程 中仅查找某个特定元素是否存在或它的属性的，称为静态 查找。 （4）动态查找（Dynamic Search Table）在查找过程 中对查找表进

3、行插入元素或删除元素操作的，称为动态查 找。 （5）关键字（Key）数据元素（或记录）中某个数据 项的值，用它可以标识数据元素（或记录）。 （6）主关键字（Primary Key）可以唯一地标识一个 记录的关键字称为主关键字。如图8-1的“学号”。（7）次关键字（Secondary Key）可以标识若干个记 录的关键字称为次关键字。如图8-1的“姓名”，其中张三 就有两位。 （8）查找（Searching）在查找表中确定是否存在一 个数据元素的关键字等于给定值的操作，称为查找（也称 为检索）。若表中存在这样一个数据元素（或记录），则 查找成功；否则，查找失败。 （9）内查找和外查找 若整个查找

4、过程全部在内存进行，则称为内查找；若在查 找过程中还需要访问外存，则称为外查找。本书仅介绍内 查找。 （10）平均查找长度ASL 查找算法的效率，主要是看要查找的值与关键字的比较次 数，通常用平均查找长度来衡量。对一个含n个数据元素的表，查找成功时：其中：Pi为找到表中第i个数据元素的概率，且有：Ci为查找表中第i个数据元素所用到的比较次数。不 同的查找方法有不同的Ci。查找是许多程序中最消耗时间的一部分。因而，一 个好的查找方法会大大提高运行速度。静态查找表是数据元素的线性表，可以是基于数组 的顺序存储或者以链表存储。(1) 顺序存储结构定义 typedef struct ElemType

5、*elem； / 数组基址 int length； / 表长度S_TBL； (2) 链式存储结构结点定义typedef struct NODE ElemType elem； / 结点的值域 struct NODE *next； / 下一个结点指针域NodeType；8-2 静态查找表8-2-1 顺序查找顺序查找又称线性查找，是最基本的查找方法之一。 顺序查找既适用于顺序表，也适用于链表。1基本思想从表的一端开始，顺序扫描线性表，依次按给定值kx 与关键字（Key）进行比较，若相等，则查找成功，并给出 数据元素在表中的位置；若整个表查找完毕，仍未找到与 kx相同的关键字，则查找失败，给出失败信息

6、。2算法的实现现以顺序存储为例，数据元素从下标为1的数组单元开 始存放，0号单元留作为监测哨，用来存放待找的值kx。void SeqSearch( ) / 顺序查找 int aN,i,x,y;printf (“ntt建立整数的顺序表(以回车为间隔，以1结束)：n“);for (i=1;i=0if (i=0) printf (“没有找到n“);else printf (“已找到，在第%d的位置上n“,i); 监测哨的作用：（1）省去判定循环中下标越界的条件，从而节约比较时间 ；（2）保存查找值的副本，查找时若遇到它，则表示查找不 成功。这样在从后向前查找失败时，不必判查找表是否检 测完，从而达到

7、算法统一。3顺序查找性能分析对一个含n个数据元素的表，查找成功时：就上述算法而言，对于n个数据元素的表，给定值kx 与表中第i个元素关键字相等，即定位第i个记录时，需进 行n-i+1次关键字比较，即Ci=n-i+1。则查找成功时，顺序查找的平均查找长度为：设每个数据元素的查找概率相等，即 Pi= ，则等 概率情况下有：查找不成功时，关键字的比较次数总是n+1次。算法中的基本工作就是关键字的比较，因此，查找长 度的量级就是查找算法的时间复杂度为O(n)。顺序查找缺点是当n很大时，平均查找长度较大，效 率低；优点是对表中数据元素的存储没有要求。另外，对 于线性链表，只能进行顺序查找。8-2-2 二

8、分查找二分查找也叫折半查找，是一种效率较高的查找方法 ，但前提是表中元素必须按关键字有序（按关键字递增或 递减）排列。1二分查找的基本思路在有序表中，取中间元素作为比较对象，若给定值与 中间元素的关键字相等，则查找成功；若给定值小于中间 元素的关键字，则在中间元素的左半区继续查找；若给定 值大于中间元素的关键字，则在中间元素的右半区继续查 找。不断重复上述查找过程，直到查找成功，或所查找的 区域无数据元素，查找失败。2查找的步骤（1） low=1；high=length； / 设置初始区间（2） 当lowhigh时，返回查找失败信息 / 表空，查找失败 （3） lowhigh，mid=(low

9、+high)/2; / 取中点 （a） 若kxtbl.elemmid.key，low=mid+1；转（2）/ 查找在右半区进行（c） 若kx=tbl.elemmid.key，返回数据元素在表中位置/ 查找成功 3排序举例 【例8-1】有序表： 5，14，18，21，23，29，31，35，38 ，42，46，49，52。在表中查找值为14和22的数据元素。 查找关键字为14的过程14 查找关键字为22的过程 224算法 void BinSearch() / 二分查找 int RMAXLEN,i,k,low,mid,high,m,nn;char ch;printf(“建立递增有序的查找顺序表(以

10、回车间隔，以-1结束)：n“);for(i=0;ik) high=mid-1;else if (Rmidhigh) printf(“没有找到n“);printf(“共进行%d次比较。n“,m);if (Rmidkey= =Key) printf(“树中已有%d，不需插入n“,Key); return; f=p; p=(Keykey)?p-lchild:p-rchild;p=new BSTNode;p-key=Key;p-lchild=p-rchild=NULL;if (*T)=NULL) (*T)=p;else if (Keykey) f-lchild=p;else f-rchild=p;*3

11、二叉排序树删除操作若要在二叉排序树中删除一个结点，删除之后的二叉排 序树仍要保持二叉排序树的特性，这就需要我们从三种情况 进行考虑： （1）删除的结点是叶子结点将其父结点与该结点相连接的指针设为NULL。如图8-6 要删除结点11，则只需将其父结点9的右指针设为NULL。图8-6 删除叶子结点示意图1611252819920131625281992013（2）删除的结点只有一棵子树： 将被删除结点的子树向上提升，用子树的根结点取 代被删除结点。如图8-7要删除结点9，则用结点11取代结 点9。16112528199201316252819112013图8-7 删除的结点只有一棵子树（3）删除的

12、结点有两棵子树：（两种方法）（a）中序直接前趋法将被删除结点的中序遍历的直接前趋结点取代被删除 结点。如图8-8要删除结点20，则要将中序直接前趋结点 19取代结点20。16112528199201316252891913图8-8 中序直接前趋法删除结点有两棵子树的情况（b）中序直接后继法将被删除结点的中序遍历的直接后继结点取代被删除 结点。如图8-8要删除结点20，则要将中序直接后继结点 25取代结点20。（本书程序采用此种方法）图8-9 中序直接后继法删除结点有两棵子树的情况161125281992013162819112513二叉排序树上删除结点的算法：void DelBSTNode(B

13、STree *T,KeyType Key) BSTNode *parent=NULL,*p,*q,*child;p=*T;while(p) / 查找要删除的结点 if (p-key=Key) break;parent=p;p=(Keykey)?p-lchild:p-rchild;if (!p) printf (“没有找到要删除的结点n“); return;q=p;if (q-lchildp-lchild;parent=p,p=p-lchild);/查找右子树最左端结点child=(p-lchild)?p-lchild:p-rchild; if (!parent) *T=child; else

14、/ 若左右子树至少有一为空 if (p= =parent-lchild)parent-lchild=child;else parent-rchild=child;if (p!=q)q-key=p-key; delete(p);4二叉排序树查找过程从其定义可见，二叉排序树的查找过程为： （1）若查找树为空，查找失败。 （2）查找树非空，将给定值kx与查找树的根结点关键字比较 。 （3）若相等，查找成功，结束查找过程，否则，（a）当给kx小于根结点关键字，查找将在以左子女为根的 子树上继续进行，转（1）（b）当给kx大于根结点关键字，查找将在以右子女为根的 子树上继续进行，转（1）以二叉链表作为二

15、叉排序树的存储结构，则查找过程算法 程序描述如下： typedef struct node / 二叉排序树结点结构 KeyType key; / 数据元素字段 struct node *lchild,*rchild; / 左、右指针字段 BSTNode; / 二叉树结点类型二叉排序树查找算法：void SearchBST(BSTree T,KeyType Key) BSTNode *p=T;while(p) if (p-key=Key) printf(“已经找到n“); return; p=(Keykey)?p-lchild:p-rchild;printf(“没有找到n“);5二叉排序树的查找分析在二叉排序树上查找其关键字等于给定值结点的过程， 恰是走了一条从根结点到该结点的路程的过程。含有n 个结 点的二叉树是不唯一的，如何来进行查找分析呢？图8-10 (a) 二叉排序树 图8-10 (