数据结构-查找表
- 格式：pps
- 大小：156.00 KB
- 文档页数：23
第八章查找表•8.1静态查找表•8.2动态查找表•8.3哈希表及其查找•查找表：–由同一类元素或记录构成的集合。
对数据元素间的关系未作限定。
•对查找表的操作有–查找某个“特定”的元素是否在表中。
–查找某个“特点”的元素的各种属性。
–在查找表中插入一个元素。
–在查找表中删除一个元素•静态查找表、动态查找表•关键字–数据元素中的某个数据项值。
可以表示一个数据元素，如可以唯一表示，则为主关键字（primary key）。
•查找–根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。
若找到表示查找成功，返回该元素详细信息或在查找表中的位置；负责返回NULL8.1静态查找表8.1.1顺序查找•算法8.1–int Search_Seq(SSTable ST,KeyType kval)设监视哨•例8.1在顺序查找表中查找成功和失败•平均查找长度–查找过程中先后和给定值进行比较的关键字的个数的期望值ASL＝∑P i C i∑P i＝1i＝1，2，。
nC i＝n－i＋1P i＝1/nASLss＝1/n∑（n－i＋1）=(n+1)/28.1.2折半查找•折半查找（binary Search）：二分查找。
•例8.2利用二分查找在顺序有序表中查找。
–算法8.2Int Search_Bin(SStable ST,KeyType kval)–ASLbs＝（n＋1）/nlog(n+1)-1ASL bs=(20+21*2+…+2h-1*h)Pi=1/n∑1h2i-1*i令i=t+1;S=∑1h2i-1*i=2∑1h2i-2*i=2∑h-12t-1*(t+1)=2∑0h-12t-1*t+2∑0h-12t-1=2(∑1h2t-1*t-2h-1*h+20-1*0)+∑0h-12t=2(S-2h-1*h)+2h-1S=2h*h-2h+1=(n+1)log2(n+1)-(n+1)+1==(n+1)log2(n+1)-n ASL bs=1/n*S=(n+1)/nlog2(n+1)-18.1.3分块查找•又称索引顺序查找–介于顺序查和折半查找之间。
适合于关键字分块有序typedef struct{KeyType key;int stadr;}indexItem;typedef struct{indexItem*elem;int length;}indexTable;–算法8.3Search_Idx(SSTable ST,indexTable ID,KeyT kval)–设索引长度b，顺序表长度为n，则：ASLidx=ASL(b)+ASL(n/b)≈log2(b+1)-1+(n/b+1)/28.2动态查找表•对动态查找表进行的操作有–InitDSTable（&DT）–DestroyDSTable（&DT）–SearchDSTable（DT，kval）–InsertDSTable（&DT,e）*–DeleteDSTable（&DT,kval）*–TraverseDSTable（DT）8.2.1二叉查找树•查找树、二叉查找树–通过合根结点的关键字进行比较可以将继续查找的范围缩小到某一颗子树中，具有该特性的树称查找树。
二叉排序树又称二叉查找树。
•例8.4二叉查找树的查询过程。
–算法8.4bool Search_BST(BiTree T,KeyType kval, BiTree&p,BiTree&f)•二叉查找树的插入算法–算法8.5bool Insert_BST(BiTree&T,ElemType e)•删除结点的处理方法–若是叶子结点，直接删除–只有一个孩子，则将其孩子直接挂到其双亲上。
–有两个孩子，找左孩子中最大的一个元素，代替被删除结点，最大元素肯定只有一个孩子，按2）处理删除最大元素–算法8.6bool Delete_BST(BiTree&T,KeyType kval)•二叉查找树的平均查找长度p（n）＝2（n＋1）/n*logn+C•二叉平衡（查找）树–树中每个结点的左、右子树深度之差的绝对值不大于1，这种平衡状态的二叉查找树。
实现方法：平衡旋转技术8.2.2键树•键树、数字查找树（Digital search trees）–结点不是关键字，而是关键字中的一个字符,从根到叶子结点的路径（根、叶子本身除外）才是关键字•例8.5统计正文中某些单词出现的次数算法8.7void setmatch(DLTree root,char line[])算法8.8bool Search_DLTree(DLTree rt,int j,int&k)•算法8.9双链树的创建bool Insert_DLTree(DLTree&root,KeysType K,int&n)•键树的存储（双链树）–采用孩子－兄弟的存储方法。
Const MAXKEYLEN＝16；Const LINESIZE＝80；typedef struct{char ch[MAXKEYLEN];int num;}KeysType;typedef enum{LEAF,BRANCH}NodeKind; typedef struct{char symbol;struct DLTNode*next;NodeKind kind;Union{struct DLTNode*first;int idx;}}DLTNode,*DLTree;8.3哈希表及其查找8.3.1哈希表的定义和特点•哈希表–在记录的关键字和其存储位置（数组下标）之间设定一个确定的对应关系f，关键字为kval的记录存储在f（kval）位置处•哈希表的装填系数α＝n/m–其中m为哈希表分配空间–n为填入的记录数。
实际应用：0.65～0.85•哈希函数–可以对关键字做简单的算术或逻辑运算。
例8.6：i=f1(key)=key例8.7：i=f2(key)=(关键字的第一个字母ASCII码)－(‘A’的ASCII 码)例8.8：i=f3(key)=(f2(关键字的第一个字母)+f2(关键字的最后一个字母))/2•冲突–若出现f（key1）＝f（key2）的现象称冲突。
没有冲突的哈希函数很少存在，只能尽量均匀。
称“再散列”。
在建哈希表时，不仅要设定哈希函数，还要设定处理冲突的方法•哈希表的严格定义：–根据设定的哈希函数和处理冲突的方法为一组记录建立的一种存储结构，哈希函数又称散列函数。
构建哈希表又称散列技术8.3.2构造哈希函数的方法•除留余数法Hash（key）＝key mod p（p<=m）其中p为不大于m且最接近m的最大素数。
如m=1000 p=997•平方取中法–对一个关键字平方，取中间几位，中间几位和每位数字都有关系，不易冲突•折叠法–将关键字分割成位数相同的几部分（最后一部分可以不同），然后几部分相加舍进位作为哈希地址。
–有移位叠加、间界叠加8.3.3处理冲突的方法•开放定址法–从哈希地址Hash(key)求得一个地址序列H1、H2…H k,0<=k<=m-1,即H1－H k-1都不空，直到H k为空为止。
若哈希表未满，必能找到k<m，使Hk空。
H i=(Hash(key)+d i)mod m i=1,2,...,k k<=m-1d i为递增序列,有三种取法a)di＝1,2,...,m-1b)di=12，-12，22，－22...，k2，－k2（k<=m/2）c)di＝伪随机序列–例8.9设一组关键字(07,15,20,31,48,53,64,76,82,99)试构建哈希表取m＝11，p=11,Hash（key）＝key mod11•链地址法–将所有关键字为同义词（即具有相同的哈希函数值）的记录存贮在同一线性链表中，而哈希表中下标为i的分量存储哈希函数值为i的链表的头指针8.3.4哈希函数的查找及其性能分析•开放定址法的存储结构inthashsize[]={997,...}typedef struct{ElemType*elem;//记录存储基址int count;//记录数int sizeindex;//哈希表容量}HashTable;const SUCCESS＝1；const UNSUCCESS＝0；const DUPLICATE＝-1；–算法8.10Status SearchHash(HashTable H,KeyType kval,int &p,int&c)–算法8.11Status InsertHash(HashTable&H,ElemType e)•链地址法存储结构：typedef struct{ElemType data;LHNode*next;//记录数}LHNode,*LHNodeptr;typedef struct{LHNodeptr*elem;int count;//记录数int sizeindex;//哈希表容量}LHashTable;Status SearchHash(LHashTable H,KeyType kval,LHNodeptr &p,int&c){//若查到，p指向该结点；//若查不到，p返回最后一个结点待插入p=H.elem[Hash(kval)];while(p&&p->data.key!=kval){q=p;p=p->next;c++;}//q紧随pif(p)return SUCCESS;else{p=q;return UNSUCCESS;}}Status InsertHash(HashTable&H,ElemType e) {c=0;if(SearchHash(H,e.key,p,c)==SUCCESS) return DUPLICATE;else if(c<hashsize[H.sizeindex]/2){s＝new LHNode;s->data=e;p->next=s;H.count++;return OK;}//ifelse recreateHashTable(H);//重建哈希表}•线形探测散列、二次探测散列、链地址法构建哈希函数比较（07，15，20，31，48，53，64，76，82，99）m=11n=10p=11α＝0.91关键字07152031485364768299ASL 线形1112234424 2.4二次1112234222 2.0链地址法1112234111 1.7 *1121111113 1.3* 表示m=13 p=13α＝0.77•查找成功时平均查找长度：ASL sl（α）≈(1+1/(1-α))/2ASL sr（α）≈-1/αln(1-α)ASL sc（α）≈1+α/2•查找不成功时平均查找长度ASLul（α）≈(1+1/(1-α)2)/2ASLsr（α）≈1/(1-α)ASLsc（α）≈α+e-α8.3.5哈希表的应用举例•C语言中编译程序使用的符号表，操作有–对给定的名字查是否已在表中。
