本文共 4501 字,大约阅读时间需要 15 分钟。
值期末考试之际,汇总查找的相关内容
关键字:可以标识一个记录的数据项
查找:
查找表:
静态查找表:
顺序表,顺序查找
线性链表,顺序查找
有序的顺序表,折半查找
斐波那契查找法,插值查找法
索引顺序表/分块表,分块查找
动态查找表:
哈希(Hash)表
平均查找长度:查找一个记录时比较关键字次数的平均值
元素类型为记录(结构)------包含关键字和名称
#define maxsize 100typedef struct node{ keytype key; char name[6];}ElemType;typedef struct{ ElemType elem[maxsize+1];//maxsize+1个记录,elem[0]为监视哨 int length;}SSTable;SSTable ST1,ST2;
算法1:不使用监视哨
int sequsearch(SSTable ST,keytype k){ int i=ST.length; //从第n个记录开始查找 while(i>=1&&k!=ST.elem[i].key)i--;//继续扫描 if(i) printf("success\n"); //查找成功! else printf("fail\n"); //查找失败! return i; //返回记录的下标i,没找到就返回0了}
算法2:使用监视哨elem[0]
int sequsearch(SSTable ST,keytype k){ int i=ST.length; //从第n个记录开始查找 ST.elem[0].key=k; //将k填入0位置 while(k!=ST.elem[i].key)i--; //继续扫描 return i; //返回记录的下标i}
分析:
查找成功
ASL=(n+1)/2
查找失败
使用监视哨elem[0],为n+1
不使用监视哨elem[0],为n
ASL=3(n+1)/4
折半查找(binary search,对半查找,二分查找)–一种分治的思想
算法1:
int binsearch(SSTable ST,keytype k){ int low,mid,high; low=1; high=ST.length; while(low<=high){ mid=(low+high)/2; if(k
算法2:
int binsearch(SSTable ST,keytype k){ int low,mid,high; low=1;high=ST.length; while(low<=high){ mid=(low+high)/2; if(k
判定树:描述折半查找的二叉树
若n=2k-1,则判定树为满二叉树,其深度为k=log2(n+1)
假定Pi=1/n,比较关键字的次数:
最少 C=1
最多 C=log2(n+1)
ASL=(n+1)/nlog2(n+1)-1
条件:分块表“按块有序”,索引表“按key有序”
n个记录分为b块,每块的记录数s=n/b
查找方法与ASL
顺序查找、折半查找
ASL(1)=(b+1)/2
在某一块中顺序查找
ASL(2)=(s+1)/2
ASL=(b+1)/2+(s+1)/2=(b+s)/2+1=1/2(n/s+s)+1
最加分块:s=根号n
ASLmin=根号n+1=O(根号n)
定义:二叉树中的任一结点大于其非空左子树的所有结点,而小于其非空右子树的所有结点,则称这颗二叉树为二叉排序树。
对于一颗二叉排序树进行中序遍历,所得的结点序列一定是递增有序的。
struct node{ struct { int key; //关键字 }data; struct node *lchild,*rchild; //左右子树的指针}*root,*t;
(递归实现插入元素)
struct node *intree(struct node *t,ElemType x){ if(t==NULL){ //如果为空,那么新开一个结点 t=(struct node *)malloc(sizeof(struct node)) t->data=x; //生成并插入结点x t->lchild=t->rchild=NULL; //为叶子结点 } else if(x.keydata.key) t->lchild=intree(t->lchild,x); //插入到左子树 else t->rchild=intree(t->rchild,x); //插入到右子树 return t;}
(返回值 失败:NULL 成功:非NULL,结点指针)
struct node *search_tr(struct node*t,keytype k){ if(t==NULL) return NULL; //查找失败 else if(k==k->data.key) return t; //查找成功 else if(kdata.key) return search_tr(t->lchild,k);//查左子树 else return search_tr(t->rchild,k); //查右子树}
struct node *search_tree(struct node*t,keytype k){ while(t!=NULL) if(k==t->data.key) return t; //查找成功 else if(kdata.key) t=t->lchild; //查左子树 else t=t->rchild; //查右子树 return t; //查找失败}
在二叉排序树中删除一个结点时,必须将因删除节点而断开的二叉链表重新连接起来,同时确保二叉排序树的性质不会失去。
- 删除叶结点
- 被删及结点缺左子树(或右子树)
- 被删结点左右子树都存在
分析:
最好情况(满二叉树)
ASL=(n+1)/nlog2(n+1)-1=O(log2n)
最坏情况(单枝树)
ASL=(n+1)/2
平均值
ASL=O(log2n)
结点的平衡因子:结点的左右子树的深度之差。
AVL树:任何结点的平衡因子的绝对值小于等于1的二叉树
AVL树的存储结构:
typedef int DataType;typedef struct node{ DataType data; int balance; struct node *leftChild,*rightChild;}AVLNode;typedef AVLNode * AVLTree;
平衡化旋转
如果在一棵平衡的二叉搜索树中插入一个新结点,造成了不平衡,此时必须调整树的结构,使之平衡化。
平衡化旋转的两类:
静态查找表和动态查找表查找方法的不足:
无法根据关键字的值,估计数据元素可能在的位置
存储数据元素时,利用一个Hash函数根据数据元素的关键字计算出该数据元素的存储位置,查找时,也是根据给定的数据元素的关键字计算出该数据元素可能存储位置,这样一来,存储和查找的效率相当高。
哈希表也称为散列表,其数据元素的存储一般是不连续的,通过Hash函数计算出的地址称为哈希地址或散列地址。
Hash函数实现的是将一组关键字映像到一个有限的地址区间上,理想的情况是关键字得到不同的地址。
设K1和K2是关键字,若K1不等于K2是H(K1)=H(k2),则称K1和K2为同义词,他们发生了冲突。
要考虑的两个问题:
取关键字过着关键字的某个线性函数值为哈希地址
设哈希表的表长为m,哈希地址为key除以p所得的余数
p<=m,p为接近m的质数(素数)eg:m=130,p=127
或者不包含小于20的质因子的合数
解决冲突的方法:线性探测再散列(哈希)
H(k)=取k2的中间某几位数字
eg:K=21 K2=0441 取中间两位,H(K)=44
将关键字分成位数相同的几部分,然后取这几部分的叠加和作为哈希地址
边界折叠法
eg: k=056439725 H(k)=650+439+725=1814
位移折叠法
k=056439527 056+439+527=1022 H(k)=022
设哈希表中可能出现的关键字都是事先知道的,则可以取关键字的若干分布均匀的位组成哈希地址
eg:k=9020067 H(k)=206
H(k)=random(key)
random(key)为产生伪随机数的函数
eg:H(k)=取k2的中间2位数*40/99
再用线性探测再散列法解决冲突
将关键字为同义词的所有记录存入同一个链表中(表尾插入)。
eg:设H(k)=k的首字母再字母表中序号
将发生冲突的所有记录都存入一个公共溢出区
eg:设H(k)=k的首字母再字母表中的序号
发生冲突时,再使用下一个哈希函数计算哈希地址
哈希表的平均查找长度依赖于哈希表的装填因子
你说的,乐观一点
给生活加点甜
转载地址:http://sdzwb.baihongyu.com/