1、数据结构（数据结构（C+版）版）n 第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计第8章 查找8.1 查找的基本概念8.2 线性表的查找8.3 二叉排序树及其查找算法8.4 哈希查找数据结构（C+版）叶核亚8.1 查找的基本概念1.查找表与关键字2.查找操作与查找结果3.查找表所具有的数据结构4.查找方法5.查找算法的性能评价6.静态查找表与动态查找表7.查找技术的实现iniicpASL1数据结构（C+版）叶核亚8.2 线性表的查找l8.2.1 顺序查找l8.2.2 折半查找l
2、8.2.3 分块查找数据结构（C+版）叶核亚8.2.1 顺序查找1.顺序表的顺序查找数据结构（C+版）叶核亚顺序表的顺序查找算法实现#include#include /其中定义随机数函数void create(int table,int n);/数组中添加n个随机数void output(int table,int n);/输出数组的n个元素int search(int table,int n,int k)/查找，返回k值首次出现元素的下标 /未找到时，返回-1 int i=0;bool find=false;while(in&!find)couttablei=kdata!=k)p=p-nex
3、t;return p;设计主函数如下：#include Onelink.h /单链表类void main(void)Onelink h1(5);h1.output();/输出5个结点的单链表 int k=4;coutsearch(k)=;数据结构（C+版）叶核亚3算法分析212)1(1111nnnnincpASLniinii成功nnncpASLniinii111不成功数据结构（C+版）叶核亚8.2.2 折半查找数据结构（C+版）叶核亚2折半查找算法实现#include const int N=8;void output(int table,int n);/输出数组的n个元素,略int half
4、search(int table,int k)/顺序表的折半查找算法 /查找k值,找到时返回下标,不成功时返回-1 int left=0,right=N-1,mid;bool find=false;while(left=right&!find)/子序列边界有效 mid=(left+right)/2;/子序列的中间位置 coutleft=left right=right mid=mid;couttablemid=k?n;if(k=tablemid)find=true;/查找成功 else数据结构（C+版）叶核亚8.2.3 分块查找1.分块查找算法的基本思想“块间有序、块内无序”。2.静态查找表的
5、分块查找3.动态查找表的分块查找数据结构（C+版）叶核亚2.静态查找表的分块查找u 36o 21a 00b 1c 2d 6e 10f 13i 16l 191234567n 208p 229索引表index0breakcasecharclass1234567continue8default9下标do10doubleelsefloat11121314151617for18if19关键字20intlongnew2122232425262729private30protectedpublicreturnshortstaticswitchthis28throwunsignedvirtualvoidwhi
6、le首字母下标r 2510s 27t 33v 39w 40111213C关键字主表tableautodeleteenumexternfriendinlineoperatorregistersignedsizeofstructtypedefunion31394032333435363738141516数据结构（C+版）叶核亚3动态查找表的分块查找 a d索引表index姓fname指针headNameNode姓名name电话号码telephone a10 a21 a99nullnext d10null d10 d21 d99nextIndexNodetable块BlockNode01234567
7、89nullnullnullnullnullnullnullnullindexitable数据结构（C+版）叶核亚8.3 二叉排序树及其查找算法1.二叉排序树的定义二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：n若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。n若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。n根结点的左、右子树也分别为二叉排序树。数据结构（C+版）叶核亚2二叉排序树的建立数据结构（C+版）叶核亚3.二叉排序树插入结点的递归算法#include Tree1.h /二叉树类TreeNode1*inse
8、rt(char ch,TreeNode1*p)/递归算法 /将ch插入到以p为根的子树中 if(p=NULL)p=new TreeNode1(ch);/建立叶子结点作为p的左孩子 else if(chdata)p-left=insert(ch,p-left);/将ch插入到p的左子树中 /建立的叶子结点作为p的左孩子 else p-right=insert(ch,p-right);/将ch插入到p的右子树中 /建立的叶子结点作为p的右孩子 return p;数据结构（C+版）叶核亚建立二叉排序树的算法 void create(Tree1&t1,char str)/以str字符串建立二叉排序树
9、t1.root=NULL;int i=0;cout建立二叉排序树：;while(stri!=0)coutstri;t1.root=insert(stri,t1.root);i+;coutn;数据结构（C+版）叶核亚4.二叉排序树的查找TreeNode1*search(Tree1&t1,char ch)/查找结点，非递归算法 TreeNode1*p=t1.root,*find=NULL;coutSearch ch:;while(p!=NULL&find=NULL)coutdatadata)find=p;else if(chdata)p=p-left;else p=p-right;数据结构（C+版
10、）叶核亚8.4 哈希查找1.哈希函数与哈希表2.哈希查找技术的设计思想设计一个好的哈希函数，尽可能地减少冲突。因为冲突是不可避免的，发生冲突时，使用一种解决冲突的有效方法。3.设计哈希函数4.解决冲突的方法线性开放寻址法拉链法数据结构（C+版）叶核亚采用拉链法的哈希表结构 n设哈希函数hash(k)=k%10n关键字序列：n9，4，12，3，1，14，74，6，16，96 0data next 1 12 3 4 6 1234567 8 9 974 1696 14table哈希基表哈希链表同义词冲突同义词冲突数据结构（C+版）叶核亚拉链法的哈希表类 1.声明拉链法的哈希表类下面声明拉链法的哈希表类HashTable，其中成员变量table数组作为哈希基表，元素类型是单链表的结点类OnelinkNode，size是table数组的存储单元个数。文件名为HashTable.h。#include Onelink.h /单链表类class HashTable /拉链法的哈希表类 public:OnelinkNode*table;/指向哈希基表数组的指针 int size;/哈希基表的数组容量 HashTable(int n);/构造函数，分配哈希基表的存储单元 HashTable();/析构函数 int hash(int k);/哈希函数数据结构（C+版）叶核亚
