做影视网站怎么样不犯法,佛山市网站公司,免费crm软件下载,音乐网站开发案例目录 数据结构——查找何为查找1. 查找表2. 关键字3. 查找方法效果评价指标——平均查找长度ASL(Average Search Length) 静态查找表1.顺序查找2.二分查找二分查找判定树 3.静态查找表—索引顺序表的查找索引顺序查找表的算法原理#xff1a; 动态查找树表1. 二叉排序树2. 二叉… 目录 数据结构——查找何为查找1. 查找表2. 关键字3. 查找方法效果评价指标——平均查找长度ASL(Average Search Length) 静态查找表1.顺序查找2.二分查找二分查找判定树 3.静态查找表—索引顺序表的查找索引顺序查找表的算法原理 动态查找树表1. 二叉排序树2. 二叉树的检索算法3. 二叉排序树的插入算法4. 二叉排序树的删除算法5. 最佳二叉排序树 2.平衡二叉树平衡二叉树(AVL树)平衡二叉排序树平衡旋转技术 B-树 和B树 哈希表查找哈希表冲突现象——冲突处理1. 开放定址法2. 再哈希表法3. 链地址法4. 建立一个公共溢出区 哈希表的查找哈希表的删除操作 数据结构——查找
何为查找
1. 查找表 查找表由同一类型的数据元素(或记录)构成的集合 查找表的操作包括 查询某个特定的数据元素是否在查找表中检索某个特定的数据元素的各种属性在查找表中插入一个数据元素从查找表中删去某个数据元素。 查找表的分类 静态查找表:只允许做查询和检索操作的查找表。动态查找表:除查询和检索操作外还允许进行插入和删除操作的查找表。 2. 关键字
关键字是**数据元素或记录**中某个数据项的值用以标识识别一个数据元素或记录 若此关键字可以识别唯一的一个记录则称之谓**“主关键字”** 若此关键字能识别若干记录则称之谓**“次关键字”** 查找表的查询和检索通常是根据关键字进行的 根据给定的值在查找表中确定一个其关键字等于给定值的数据元素或记录
若查找表中存在这样一个记录数据元素则称查找成功。查找结果给出整个记录数据元素的信息或指示该记录数据元素在查找表中的位置否则称此查找不成功。查找结果给出“空记录 ”或“空指针”
3. 查找方法效果评价指标——平均查找长度ASL(Average Search Length)
查找速度平均查找长度ASL(Average Search Length)-为确定记录在表中的位置需要与给定值进行比较的次数的期望值叫查找算法的平均查找长度 静态查找表–顺序查找性能分析: 查找成功的平均查找长度查找成功的情况下平均找一个数据元素需要的比较次数称为查找成功的平均查找检索长度 A S L ( 1 2 … n ) / n ( n 1 ) / 2 ASL(12…n)/n(n1)/2 ASL(12…n)/n(n1)/2 说明假设每个数据元素查找的概率相同 查找一次的平均检索长度成功失败(*) A S L ( n 1 ) / 2 ( 1 2 … n ) / ( 2 ∗ n ) 3 ( n 1 ) / 4 ASL(n1)/2(12…n)/(2*n)3(n1)/4 ASL(n1)/2(12…n)/(2∗n)3(n1)/4 说明假设每个数据元素查找的概率相同并且查找一次成功和失败的概率也相同 静态查找表
1.顺序查找
查找方法从表的一端顺序找到表的另一端 (以线性表表示静态查找表) 存储结构无特殊要求(数组或链表都可以的)元素顺序无要求(有序、无序都可以的 ) //顺序表定义
#define max 100
typedef struct{KeyType key; ;//说明KeyType代表关键字的类型//……;
}ElemType typedef struct{ ElemType elem[max]; int length;
}SqList;
SqList L;
顺序查找
int search(SqList L, KeyTypex){ //KeyType代表关键字的类型for(int i0;iL.length;i)if(L.elem[i].keyx) return i1;//找到数据的位置 1为了方便表示第几个数据return 0;
}
//说明:返回0说明没找到若找到返回是x线性表的第几个数据元素为提高查找速度设置哨兵项查找表组织成线性表线性表的数据元素从下标为1的数组元素开始存放下标为0的数组元素作为哨兵项(说明哨兵可设在低端也可以设在高端) 查找x首先将x放在下标为0的数组元素哨兵从表尾开始比较。若在哨兵 处相等说明没找到否则找到
int srearch(SqList L,KeyTypex)//KeyType代表关键字的类型
{ int kL.length;L.elem[0].keyx;while(x!L.elem[k].key)k--;return k;
}//L.elem[0]哨兵项
//说明:返回0说明没找到若找到返回是x线性表的第几个数据元素
//说明2哨兵也可以设在线性表的表尾 静态查找表–顺序查找性能分析: 查找成功的平均查找长度查找成功的情况下平均找一个数据元素需要的比较次数称为查找成功的平均查找检索长度 A S L ( 1 2 … n ) / n ( n 1 ) / 2 ASL(12…n)/n(n1)/2 ASL(12…n)/n(n1)/2 说明假设每个数据元素查找的概率相同 查找一次的平均检索长度成功失败(*) A S L ( n 1 ) / 2 ( 1 2 … n ) / ( 2 ∗ n ) 3 ( n 1 ) / 4 ASL(n1)/2(12…n)/(2*n)3(n1)/4 ASL(n1)/2(12…n)/(2∗n)3(n1)/4 说明假设每个数据元素查找的概率相同并且查找一次成功和失败的概率也相同 2.二分查找
采用二分查找的要求查找表组织成有序线性表递增或递减且采用顺序存储结构 特点通过一次比较将查找范围缩小一半
二分查找通用模板
// 在单调递增序列a中查找x的数中最小的一个即x或x的后继
while (low high)
{int mid (low high) / 2;if (a[mid] x)high mid;elselow mid 1;
}// 在单调递增序列a中查找x的数中最大的一个即x或x的前驱
while (low high)
{int mid (low high 1) / 2;if (a[mid] x)low mid;elsehigh mid - 1;
}
二分查找算法原理
//有序递增或递减顺序存储结构
int binaryS(SqList L, KeyType x){int low0, highL.length-1, m;while(lowhigh){m(lowhigh)/2;//if(L.elem[m].keyx) return m1; //若找到返回是x线性表的第几个数据元素if(L.elem[m].keyx) highm-1; else lowm1;} return 0;
}
//说明:返回0说明没找到若找到返回是x线性表的第几个数据元素
■ 二分查找的效率高但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O ( n l o g n ) O(nlogn) O(nlogn)的时间。 ■ 二分查找只适用顺序存储结构。为保持表的有序性在顺序结构里插入和删除都必须移动大量的数据元素。因此二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 ■ 对那些查找少而又经常需要改动的线性表可采用链表作存储结构进行顺序查找。链表上无法实现二分查找。*
二分查找判定树 3.静态查找表—索引顺序表的查找
线性表分成若干块每一块中的键值存储顺序是任意的块与块之间****按键值排序即后一块中的所有记录的关键字的值均大于前一块中最大键值。
建立一个索引表该表中的每一项对应于线性表中的一块每一项由键域存放相应块的最大键值和链域存放指向本块地一个结点的指针组成。
适用条件分块有序表
索引顺序表的查找: ■ 首先对索引表采用二分查找或顺序查找方法查找以确定待查记录所在的块。 ■ 在线性表查找k若其在线性表中存在且位于第i块那么一定有第i-1块的 最大键值 k ≤ 第 i 块的最大键值 最大键值k≤第i块的最大键值 最大键值k≤第i块的最大键值。 ■ 然后在相应的块中进行顺序查找。 数据结构结构体
typedef struct{ KeyType key; //关键字域//…… ; // 其它域
}ElemType;//数据结构typedef struct{ ElemType *elem; // 数据元素存储空间基址int length; // 表的长度
}SSTable;//顺序表typedef struct{ KeyType MaxKey; //本块最大关键字int FirstLink; //本块第一个结点下标
}IndexTable;//索引表的类型
索引顺序查找表的算法原理
int Seach_Index(SSTable ST,IndexTable IT[],int b,int n,KeyType k){ int i1,j;//b 为块儿数 Maxkey为每块儿中的最大值//索引表查找while((kIT[i].MaxKey)(ib)) i;if(ib){ printf(\nNot found); return(0); }jIT[i].FirstLink; //块儿内查找while((k!ST.elem[j].key)(ST.elem[j].keyIT[i].MaxKey) (jn))j; //输出查找结果 if(k!ST.elem[j].key){j0; printf(\nNot found); }return(j);
}
■ 表长为n的线性表整个表分为b块前 b-1块中的记录数为s⎡n/b⎤第b块中的记录数小于或等于s。
■ A S L ( b 1 ) / 2 ( s 1 ) / 2 ASL(b1)/2(s1)/2 ASL(b1)/2(s1)/2 * ■ 当 s 根号n ASL最小 根号n 1 ①索引表查找可使用何方法①顺序、折半查找 ②块内查找可使用何方法 ②只能使用顺序查找 ③数据可否用链式存储 ③可以使用链式存储 对那些查找少而又经常需要改动的线性表可采用链表作存储结构进行顺序查找。链表上无法实现二分查找。* 动态查找树表
1. 二叉排序树
二叉排序树定义 二叉排序树或者是一棵空树或者是具有如下特性的二叉树 若它的左子树不空则左子树上所有结点的值均小于根结点的值若它的右子树不空则右子树上所有结点的值均大于根结点的值它的左、右子树也都分别是二叉排序树 (递归) 二叉排序树的中序遍历结果递增有序 判断一棵二叉树是否为二叉排序树看其中序遍历结果是否递增有序 因此一个无序序列可通过构建一棵二叉排序树而成为有序序列。 二叉排序树的主要作用与操作 ■ 二叉排序树主要作用检索排序 ■二叉排序树主要操作检索插入建立删除 检索 ■ 在二叉排序树中查找是否存在值为x的结点。 ■ 查找过程为 ① 若二叉排序树为空查找失败。 ②否则将x与二叉排序树的根结点关键字值比较若相等查找成功结束 否则 a若x小于根结点关键字在左子树上继续进行转① b若x大于根结点关键字在右子树上继续进行转① 二叉排序树的存储结构**(二叉链表)** //二叉链表作为二叉排序树的存储结构
typedef struct NODE{int key;//数据元素的关键字//… ;//数据元素的其他数据项 struct NODE *lc,*rc;
}BiNode,*BiTree;
2. 二叉树的检索算法
//二叉排序树的检索算法
Bitree Search(BiNode *t, int x){ BiTree p; //pt;while(p!NULL){ //没找到就是返回空指针if (xp-key) //找到就返回return p; if (x p-key) //左右搜索pp-lc;else pp-rc;
}
return p;
}//函数返回查找结果没找到为空指针 3. 二叉排序树的插入算法 向二叉排序树中插入x 先要在二叉排序树中进行查找若查找成功 按二叉排序树定义待插入数据已存在不用插入查找不成功时则插入之。 新插入结点一定是作为叶子结点添加上去的。(*) 建立一棵二叉排序树则是逐个插入结点的过程。* 同一组数据输入顺序不同所建二叉排序树不同
//int Insert(Bitree t,int x)//二叉排序树的插入算法
{ BiTree q, p, s;qNULL; pt; ;//p为正在查看的节点初始从根节点开始q为p的双亲节点根节点无双亲节点 while(p!NULL){ //查找if (xp-key) return 0;//在当前的二叉排序树中找到x直接返回不再做插入 qp;//记录上一个位置if (xp-key) pp-lc; else pp-rc;}//最后没找到的话 就是插入到 q的左孩子或右孩子处s(BiTree)malloc(sizeof(Binode)) ;//没找到x做插入先申请节点空间 s-keyx; //初始化s-lcNULL; s-rcNULL ;//存放x设为叶节点if(qNULL)ts;//若原先的二叉树是一棵空树新插入的x对应的节点s为插入后二叉树的根节点//这个很重要 要不然空树 后面插入 就报错了。。。 else if(xq-key) q-lcs; ;//插入s为q的孩子else q-rcs; return 1;
}4. 二叉排序树的删除算法
从二叉排序树中删除一个结点之后使其仍能保持二叉排序树的特性。
被删结点为叶结点由于删去叶结点后不影响整棵树的特性所以只需将被删结点的双亲结点相应指针域改为空指针。若被删结点只有右子树 pr或只有左子树 pl此时只需将pr或pl替换被删结点即可。若被删结点既有左子树 pl 又有右子树pr 可按中序遍历保持有序进行调整。
左右孩子均存在 用左子树中最大的结点q的值替换被删结点再删q 或 用右子树中最小的结点w的值替换被删结点再删w 结点q (和w)的特点是最多只有一个孩子
左子树中最大结点的特点是 左子树的根节点一直向右下 直到p-rchildNULL为真,此时p就是那个左子树中的最大结点。 右子树中最小结点的特点是右子树的根节点一直向左下直到p-lchildNULL为真,此时p就是那个右子树中的最小结点。
5. 最佳二叉排序树
二叉排序树查找过程与二分查找判定树相似 n个数据元素按照不同的输入顺序构造的二叉排序树不同其中平均查找性能最高的为最佳二叉排序树. 按照二分查找判定树的建立过程建立的二叉排序树为最佳二叉排序树。 二叉排序树的查找速度一般比顺序查找快但如果是单枝树则一样快。 注意单枝树的情况
2.平衡二叉树
平衡二叉树(AVL树)平衡二叉排序树
希望所建的二叉排序树均为平衡二叉树 (AVL树) 注意需要时刻考虑到 空树 以及 单枝树 的情况 平衡二叉树:空树或者是具有下列性质的二叉树 左、右子树都是平衡二叉树 (递归)左、右子树高度之差的绝对值不超过1树中每个结点的左、右子树高度之差的绝对值不大于1。 结点的平衡因子 B F 结点的左子树深度 − 右子树深度 结点的平衡因子BF结点的左子树深度-右子树深度 结点的平衡因子BF结点的左子树深度−右子树深度 平衡二叉树每个结点的平衡因子的绝对值不超过1
平衡旋转技术
如果在一棵AVL树中插入一个新结点就有可能造成失衡此时必须重新调整树的结构使之恢复平衡。我们称调整平衡过程为平衡旋转。 平衡旋转可以归纳为四类 LL平衡旋转–单向右旋RR平衡旋转–单向左旋LR平衡旋转–先左旋后右旋RL平衡旋转–先右旋后左旋 旋转操作特点 对不平衡的最小子树操作旋转后子树根节点平衡因子为0旋转后子树深度不变故不影响全树也不影响插入路径上所有祖先结点的平衡度 平衡树查找的时间复杂度为O(logn)
LL型—单向右旋 RR型—单向左旋
LR型—先左旋后右旋: RL型—先右旋后左旋
在平衡树上进行查找的过程和二叉排序树相同因此查找过程中和给定值进行比较的关键字的个数不超过平衡二叉树的深度。 (*)
B-树 和B树
动态查找表允许查找插入和删除操作
B-树是一种平衡的多路查找树。
哈希表查找
不同的表示方法其差别仅在于关键字和给定值进行比较的顺序不同
哈希函数是一个映象即将关键字的集合映射到某个地址集合上它的设置很灵活只要这个地址集合的大小不超出允许范围即可
哈希表构造方法
哈希表冲突现象——冲突处理
实际应用中不保证总能找到一个不产生冲突的哈希函数。一般情况下只能选择恰当的哈希函数使冲突尽可能少地产生。 冲突处理方法 开放定址法再哈希表法链地址法建立一个公共溢出区 1. 开放定址法 d i d_i di称为增量有三种取法
线性探测再散列: d i i d_i i dii平方(二次)探测再散列: d i 1 2 , − 1 2 , 2 2 , − 2 2 , 3 2 , − 3 2 , … d_i 1^2 ,-1^2, 2^2, -2^2, 3^2, -3^2 , … di12,−12,22,−22,32,−32,…随机探测再散列: d i d_i di 是一组伪随机数列 增量 d i d_i di 应具有“完备性”(*)
2. 再哈希表法
3. 链地址法 4. 建立一个公共溢出区
将发生冲突的数据元素顺序存放于一个公共的溢出区
哈希表的查找
查找过程和造表过程一致 哈希表饱和的程度装载因子 α n / m αn/m αn/m 值的大小n—数据数m—表的长度 哈希表的删除操作
开放定址法删除一个数据为保证查找工作的正常进行不能真删----加删除标志
