做电影ppt模板下载网站,罗湖网站建设费用,中国十大室内设计师,深圳万创网怎么样1.查找的基本概念
1、查找表——由同一类型的数据元素#xff08;或记录#xff09;构成的集合称为查找表。 2、对查找表进行的操作#xff1a;
查找某个特定的数据元素是否存在#xff1b;
检索某个特定数据元素的属性#xff1b;
在查找表中插入一个数据元素#x…1.查找的基本概念
1、查找表——由同一类型的数据元素或记录构成的集合称为查找表。 2、对查找表进行的操作
查找某个特定的数据元素是否存在
检索某个特定数据元素的属性
在查找表中插入一个数据元素
在查找表中删除一个数据元素。
3、静态查找Static Search Table——在查找过程中仅查找某个特定元素是否存在或它的属性的称为静态查找。
4、动态查找Dynamic Search Table——在查找过程中对查找表进行插入元素或删除元素操作的称为动态查找。
5、关键字Key——数据元素或记录中某个数据项的值用它可以标识数据元素或记录。
6、主关键字Primary Key——可以唯一地标识一个记录的关键字称为主关键字。如上图中的“学号”。
7、次关键字Secondary Key——可以标识若干个记录的关键字称为次关键字。如上图中的“姓名”其中张三就有两位。
8、查找Searching——在查找表中确定是否存在一个数据元素的关键字等于给定值的操作称为查找也称为检索。若表中存在这样一个数据元素或记录则查找成功否则查找失败。
9、内查找和外查找 ——若整个查找过程全部在内存进行则称为内查找若在查找过程中还需要访问外存则称为外查找。
10、平均查找长度ASL 查找算法的效率主要是看要查找的值与关键字的比较次数通常用平均查找长度来衡量。
平均查找长度为确定数据元素在列表中的位置 需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。对于长度为n的列表 查找成功时的平均查找长度为 其中Pi为查找列表中第i个数据元素的概率Ci为找到列表中第i个数据元素时已经进行过的关键字比较次数。不同的查找方法有不同的Ci。由于查找算法的基本运算是关键字之间的比较操作所以可用平均查找长度来衡量查找算法的性能。 11、查找的基本方法可以分为两大类即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法而计算式查找法也称为HASH哈希查找法。
2.基于线性表的查找法
1 顺序查找法
顺序查找又称线性查找是最基本的查找方法之一。顺序查找法的特点是用所给关键字与线性表中各元素的关键字逐个比较直到成功或失败。存储结构通常为顺序结构也可为链式结构。 下面给出顺序结构有关数据类型的定义
define LIST-SIZE 20typedef struct {KeyType key; OtherType other-data; } RecordType;
typedef struct {RecordType rLIST-SIZE1; /* r0为工作单元 */int length; } RecordList; 1顺序查找的基本思想
从表的一端开始顺序扫描线性表依次按给定值k与关键字Key进行比较若相等则查找成功并给出数据元素在表中的位置若整个表查找完毕仍未找到与k相同的关键字则查找失败给出失败信息。
2算法的实现
现以顺序存储为例数据元素从下标为1的数组单元开始存放0号单元留作为监测哨用来存放待找的值k。 //设置监视哨的顺序查找法
typedef struct {RecordType rLIST-SIZE1; int length; } RecordList;
int SeqSearchRecordList l, KeyType k
/*在顺序表l中顺序查找其关键字等于k的元素 若找到 则函数值为该元素在表中的位置否则为0*/
{ l.r0.keyk; il.length; while (l.ri.key!k) i--; returni;
}其中1.r0称为监视哨可以起到防止越界的作用。
//不用监视哨的算法
int SeqSearchRecordList l, KeyType k
/*不用监视哨法 在顺序表中查找关键字等于k的元素*/
{l.r0.keyk; il.length; while (i1l.ri.key!k) i--; if (i1) returnielse return (0);
} 监测哨的作用 1省去判定循环中下标越界的条件从而节约比较时间
2保存查找值的副本查找时若遇到它则表示查找不成功。这样在从后向前查找失败时不必判查找表是否检测完从而达到算法统一。
3顺序查找性能分析
下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n那么查找第i个数据元素时需进行n-i1次比较即Cin-i1。又假设查找每个数据元素的概率相等即Pi1/n 则顺序查找算法的平均查找长度为 查找不成功时关键字的比较次数总是n1次。
算法中的基本工作就是关键字的比较因此查找长度的量级就是查找算法的时间复杂度为O(n)。
4.顺序查找的优缺点
顺序查找技术的优点是算法简单且适应面广且对表结构没有任何要求无论是顺序表还是链表无论记录是否按关键字有序均可应用。缺点是平均查找长度较大当查找规模很大时查找效率较低。另外对于线性链表只能进行顺序查找。
2.折半查找法
二分查找也叫折半查找是一种效率较高的查找方法但前提是表中元素必须按关键字有序按关键字递增或递减排列。
1二分查找的基本思路
在有序表中取中间元素作为比较对象若给定值与中间元素的关键字相等则查找成功若给定值小于中间元素的关键字则在中间元素的左半区继续查找若给定值大于中间元素的关键字则在中间元素的右半区继续查找。不断重复上述查找过程直到查找成功或所查找的区域无数据元素查找失败。 注意
1、由于关键字有序所以查找时每次和中间位置的元素比较可快速确定被查找元素在且只可能在哪半个区间内从而省去与另一半区间内元素的比较因此提高了效率。
2、查找时每次都和M下标处的元素比较若相同则查找成功。M的计算规则为M(HL)/2。
3、此算法的关键是下标的变化初始时L0H元素数量-1M(HL)/2当确定元素在左半区间内时对下标的更新规则为L不变HM-1同理若确定元素在右半区间则H不变LM1。
4、下标经过变化后若发现HL则表示关键字不在序列中查找失败。
int BinarySearch(int a[], int n, int key)
{ int l 0; int h n-1; int m; /* 根据结论3 */while (lh) /* 根据结论4 */{ m (lh)/2; /* 根据结论3 */if( key a[m]) return m; if( key a[m]) h m-1;elsel m1; }return -1; /*查找不成功返回-1 */
}下面用平均查找长度来分析折半查找算法的性能。 折半查找过程可用一个称为判定树的二叉树描述 判定树中每一结点对应表中一个记录 但结点值不是记录的关键字 而是记录 在表中的位置序号。 根结点对应当前区间的中间记录 左子树对应前一子表 右子树对应后一子表。 例如对含11个记录的有序表 其折半查找过程可如下图所示的二叉判定树表示。 二叉树结点内的数值表示有序表中记录的序号 如二叉树的根结点表示第一次折半时找到的第6个记录。 图中的虚线表示查找关键字等于13的记录的过程 需要的比较次数为4 因为关键字等于13的记录在判定树上位于第4层。 因此 记录在判定树上的“层次”恰为找到此记录时所需进行的比较次数。 假设每个记录的查找概率相同 则从图所示判定树可知 对任意长度为11的有序表进行折半查找的平均查找长度为ASL(12233334444)/1133/113。
折半查找成功时 关键字比较次数最多不超过判定树的深度。 由于判定树的叶子结点所在层次之差最多为1 故n个结点的判定树的深度与n个结点的完全二叉树的深度相等均为log2n1。 这样折半查找成功时关键字比较次数最多不超过log2n1。 相应地 折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径 因此 折半查找失败时 关键字比较次数最多也不超过判定树的深度log2n1。 为便于讨论 假定表的长度n2h-1 则相应判定树必为深度是h的满二叉树hlog2(n1)。 又假设每个记录的查找概率相等 则折半查找成功时的平均查找长度为 所以二分查找的时间复杂度为O (log2n) 。
二分查找的优点是效率高。
二分查找的缺点是
1必须按关键字排序有时排序也很费时
2只适用顺序存储结构所以进行插入、删除操作必须移动大量的结点。
二分查找适用于那种一经建立就很少改动而又经常需要查找的线性表。对于那些经常需要改动的线性表可以采用链表存储结构进行顺序查找。
3.分块查找法 分块查找法要求将列表组织成以下索引顺序结构
首先将列表分成若干个块子表。一般情况下块的长度均匀 最后一块可以不满。每块中元素任意排列即块内无序但块与块之间有序。
构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置以及每块中的最大关键字或最小关键字。索引表按关键字有序排列。 实现算法
索引表是有序的所以在索引表上既可以采用顺序查找也可以采用折半查找而每个块中的记录排列是任意的所以在块内只能采用顺序查找。
注意
1.算法引入索引表的辅助结构可以首先通过索引表确定被查找关键字所在的区间再从相应区间内查找从而有效的减少比较的次数。
2.在构建索引表时索引表存储相应块中的最大值这些最大值按有序排放在确定区间时可以使用折半查找的方法。
3.为了保证索引表有效原始序列中的元素必须“部分有序”所谓“部分有序”指的是对于第i个区间中的所有数据都应比前一个区间即第i-1个区间内所有关键字大否则会导致索引失效。
4.由于每个区间的关键字是无序的因此在区间内的查找只能使用顺序查找。
5.算法需要在一开始构建索引表并且保证原始序列“部分有序”这本身会耗费一定的时间如果原始序列中的元素不再发生变化则索引表的结构是稳定的一旦原始序列发生变化则仍需重新构造索引表并使得新序列重新“部分有序”。
#define MaxIndex 索引表的最大长度typedef struct{ elemtype key;int link;}IdxType;在这种结构下查找过程要分为两步首先查找索引表。因为索引表是有序表所以可采用二分查找或顺序查找以确定给定值所在的块。因为块中的记录可以是任意排列的所以再在已确定的块中进行顺序查找。
//分块查找
int IdxSerch(SeqList A[], IdxType index[], int b, KeyType k, int n)
{ //分块查找关键字为k的记录索引表为index[0..b-1] int low0, highb-1, mid, i; int sn/b; //每块记录个数while(lowhigh) { mid(lowhigh)/2;if(index[mid].key k) low mid1else highmid-1; }if(lowb) { //在顺序表中顺序查找for(iindex[low].link;iindex[low].links-1 in; i)if(A[i].keyk) return i;}return -1;
}索引顺序查找的平均查找长度 查找“索引”的平均查找长度 查找“顺序表”的平均查找长度 分块查找的平均查找长度由两部分构成 即查找索引表时的平均查找长度为LB以及在相应块内进行顺序查找的平均查找长度为LW。 假定将长度为n的表分成b块且每块含s个元素则bn/s。又假定表中每个元素的查找概率相等则每个索引项的查找概率为1/b块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块则有 3.动态查找
动态查找表特点表结构本身是在查找过程中动态生成的即对于给定值key若表中存在关键字等于key的记录则查找成功否则插入关键字为key的元素。
1.二叉排序树
二叉排序树(二叉搜索树、二叉查找树) 或者是一棵空树或是一棵有如下特性的非空二叉树
若它的左子树非空则左子树上所有结点的关键字均小于根结点的关键字若它的右子树非空则右子树上所有结点的关键字均大于等于根结点的关键字。
左、右子树本身又各是一棵二叉排序树。
结论二叉排序树中序遍历得到的必是一个有序序列。 #define NULL 0
typedef struct Node /* 树中结点定义*/
{ int key; /* 关键字*/struct Node * pLeft; /* 指向左子树的指针 */struct Node * pRight; /* 指向右子树的指针 */
}Node;二叉排序树的搜索
若二叉排序树为空则查找不成功否则
1若给定值等于根结点的关键字则查找成功
2若给定值小于根结点的关键字则继续在左子树上进行查找
3若给定值大于根结点的关键字则继续在右子树上进行查找。
/*查找成功返回值为1查找失败返回0*/
int SearchBST(Node * pRoot,int key)
{ /* 结点为空则表示搜索到叶子结点仍没找到返回0 */if(pRoot NULL) return 0;if(key pRoot-key)return 1; /*查找成功返回1*//*若key小于当前结点的关键字则继续在左子树中搜索*/else if(key pRoot-key) SearchBST(pRoot-pLeft, key); else /*否则继续在右子树中查找*/SearchBST(pRoot-pRight,key)
} 二叉排序树的插入及创建
根据动态查找表的定义“插入”操作在查找不成功时才进行
若二叉排序树为空树则新插入的结点为新的根结点否则新插入的结点必为一个新的叶子结点其插入位置由查找过程得到。
输入4、2、3、5、8、0、1 //改进二叉排序树搜索算法
int SearchBST(Node * pRoot, int key, Node** pKeyNode, Node ** pParentNode)
{ *pKeyNode pRoot;while(*pKeyNode){ if(key (* pKeyNode)-key){ *pParentNode *pKeyNode;*pKeyNode (*pKeyNode)-pRight; }else if(key (*pKeyNode)-key){ *pParentNode *pKeyNode; *pKeyNode (*pKeyNode)-pLeft; }else { return 1;}} *pKeyNode *pParentNode; return 0;
}pParentNodepRoot的父结点初始时pRoot指向根结点其父结点为NULL; pKeyNode : 查找成功时返回关键字所在结点的指针不成功时返回查找路径上不为空的最后一个结点当pKeyNode返回NULL时表示此时二叉排序树为一颗空树; 查找成功返回1查找失败返回0 //二叉排序树插入算法
int InsertBST(Node ** pRoot, int key)
{ Node * pNewNode; /*定义存放新的关键字的结点*/Node* pKeyNode * pParentNodeNULL/*如果该关键字已在树中则插入失败*/
if(SearchBST(*pRoot, key, pKeyNode, pParentNode)) return 0;/*若不在树中则首先为新结点分配空间*/Node * pNewNode (Node*)malloc(sizeof(Node));pNewNode-key key; /*为新结点赋初值*/pNewNode-pLeft pNewNode-pRight NULL;/*若树为空树则新结点为插入后的根结点*/if(pKeyNode NULL) (*pRoot) pNewNode;/*比结点关键字小插入到左孩子*/else if(key pKeyNode-key) pKeyNode-pLeft pNewNode;else pKeyNode-pRight pNewNode;return 1;
}key被插入关键字;
pRoot插入后新的二叉排序树的根结点指针; 插入成功返回1插入失败返回0。
二叉排序树的删除算法
和插入相反删除在查找成功之后进行并且要求在删除二叉排序树上某个结点之后仍然保持二叉排序树的特性。
1被删除的结点是叶子
其双亲结点中相应指针域的值改为“空”
2被删除的结点只有左子树或者只有右子树
其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。
3被删除的结点既有左子树也有右子树。
以其前驱替代之然后再删除该前驱结点 方法1: 首先找到p结点在中序序列中的直接前驱s结点然后将p的左子树改为f的左子树而将p的右子树改为s的右子树f-lchildp-lchilds-rchild p-rchild free(p)
方法2: 首先找到p结点在中序序列中的直接前驱s结点然后用s结点的值替代p结点的值再将s结点删除原s结点的左子树改为s的双亲结点q的右子树p-datas-dataq-rchild s-lchildfree(s)
int DeleteBST(Node * pRoot,int key)
{ Node * pParentNode NULL;Node * pNode pRoot;Node * pKeyNode;Node ** pTempNode;if(SearchBST(pRoot,key,pKeyNode,pParentNode)){ if(pParentNode NULL) pTempNode pRoot;else if(pKeyNode pParentNode-pLeft) pTempNode pParentNode-pLeft;else pTempNode pParentNode-pRight;if (pKeyNode-pLeft NULL){ *pTempNode pKeyNode-pRight;free(pKeyNode);}else if(pKeyNode-pRight NULL){ *pTempNode pKeyNode-pLeft; free(pKeyNode); }else{ pNode pKeyNode-pLeft; pTempNode pKeyNode-pLeft;while (pNode-pRight ! NULL) { pTempNode pNode-pRight;pNode pNode-pRight;}pKeyNode-key pNode-key;*pTempNode pNode-pLeft; free(pNode);}return 1;}return 0;
}查找性能的分析
对于每一棵特定的二叉排序树均可按照平均查找长度的定义来求它的 ASL 值显然由值相同的 n 个关键字构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同甚至可能差别很大。
时间复杂度
分析在二叉排序树上进行查找的过程中根结点为待查结点时给定值同树中结点的比较次数仅为一次待查结点位于最后一层时比较的次数为树的深度。
普通情况下对二叉排序树进行查找的时间复杂度为O( log2n ) 最差情况下(二叉排序树为一棵单支树)其时间复杂度为O(n)。
为使得由任何初始序列构成的二叉排序树的平均查找长度是对数级的所以可使得构造的二叉排序树是一个平衡二叉树。
2.平衡二叉排序树
平衡二叉排序树又称为AV树。一棵平衡二叉排序树或者是空树或者是具有下列性质的二叉排序树
① 左子树与右子树的高度之差的绝对值小于等于1
② 左子树和右子树也是平衡二叉排序树。引入平衡二叉排序树的目的是为了提高查找效率 其平均查找长度为O(log2n)。
在下面的描述中需要用到结点的平衡因子balance factor这一概念其定义为结点的左子树深度与右子树深度之差。
显然对一棵平衡二叉排序树而言 其所有结点的平衡因子只能是-1、 0或1。当我们在一个平衡二叉排序树上插入一个结点时有可能导致失衡即出现绝对值大于1的平衡因子如2、-2。图中给出了一棵平衡二叉排序树和一棵失去平衡的二叉排序树。 失衡调整 4.哈希法
哈希法又称散列法、杂凑法或关键字地址计算法等相应的表称为哈希表。 这种方法的基本思想是首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H使得pH(k)H称为哈希函数。创建哈希表时把关键字为k的元素直接存入地址为H(k)的单元以后当查找关键字为k的元素时再利用哈希函数计算出该元素的存储位置pH(k)从而达到按关键字直接存取元素的目的。
当关键字集合很大时关键字值不同的元素可能会映象到哈希表的同一地址上即 k1≠k2但 Hk1Hk2这种现象称为冲突此时称k1和k2为同义词。实际中冲突是不可避免的 只能通过改进哈希函数的性能来减少冲突。
1.构造方法
1. 数字分析法
例如有80个记录关键字为8位十进制整数d1d2d3…d7d8如哈希表长取100则哈希表的地址空间为 00~99。假设经过分析各关键字中d4和d7的取值分布较均匀 则哈希函数为H(key)H(d1d2d3…d7d8)d4d7。例如 H(81346532)43H(81301367)06。 相反 假设经过分析 各关键字中 d1和d8的取值分布极不均匀d1 都等于5d8 都等于2此时如果哈希函数为H(key)H(d1d2d3…d7d8)d1d8 则所有关键字的地址码都是52显然不可取。 2. 平方取中法 当无法确定关键字中哪几位分布较均匀时 可以先求出关键字的平方值然后按需要取平方值的中间几位作为哈希地址。这是因为平方后中间几位和关键字中每一位都相关故不同关键字会以较高的概率产生不同的哈希地址。
3. 分段叠加法
这种方法是按哈希表地址位数将关键字分成位数相等的几部分最后一部分可以较短 然后将这几部分相加 舍弃最高进位后的结果就是该关键字的哈希地址。 具体 方法有折叠法与移位法。 移位法是将分割后的每部分低位对齐相加 折叠法是从一端向另一端沿分割界来回折叠奇数段为正序 偶数段为倒序 然后将各段相加。 例如 key12360324711202065, 哈希表长度为1000 则应把关键字分成3位一段 在此舍去最低的两位65 分别进行移位叠加和折叠叠加 求得哈希地址为105和907。
4. 除留余数法 假设哈希表长为m p为小于等于m的最大素数 则哈希函数为Hkk%p 其中%为模p取余运算。
例如已知待散列元素为18756043549046表长m10 p7 则有
H(18)18 % 74 H(75)75 % 75 H(60)60 % 74
H(43)43 % 71 H(54)54 % 75 H(90)90 % 76 H(46)46 % 74
此时冲突较多。 为减少冲突 可取较大的m值和p值 如mp13 结果如下
H(18)18 % 135 H(75)75 % 1310 H(60)60 % 138
H(43)43 % 134 H(54)54 % 132 H(90)90 % 1312 H(46)46 % 137 5. 伪随机数法
采用一个伪随机函数作哈希函数即H(key)random(key)。
在实际应用中 应根据具体情况 灵活采用不同的方法 并用实际数据测试它的性能以便做出正确判定。 通常应考虑以下五个因素
计算哈希函数所需的时间简单。
关键字的长度。
哈希表的大小。
关键字的分布情况。
记录查找的频率。
2.处理冲突的方法 1. 开放定址法
这种方法也称再散列法其基本思想是当关键字key的哈希地址p Hkey出现冲突时以p为基础产生另一个哈希地址p1如果p1仍然冲突再以p为基础产生另一个哈希地址p2……直到找出一个不冲突的哈希地址pi将相应元素存入其中。这种方法有一个通用的再散列函数形式 其中Hkey为哈希函数 m 为表长 di称为增量序列。 增量序列的取值方式不同相应的再散列方式也不同。主要有以下三种
线性探测再散列di123…: m-1
这种方法的特点是 冲突发生时顺序查看表中下一单元 直到找出一个空单元或查遍全表。
二次探测再散列 di12-12 22-22…k2-k2 (k≤m/2)
这种方法的特点是冲突发生时在表的左右进行跳跃式探测 比较灵活。
伪随机探测再散列di伪随机数序列。
具体实现时应建立一个伪随机数发生器并给定一个随机数做起点。 2. 再哈希法
这种方法是同时构造多个不同的哈希函数 HiRH1key i12 … k
当哈希地址HiRH1key发生冲突时再计算HiRH2key……直到冲突不再产生。这种方法不易产生聚集但增加了计算时间。 3. 链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表并将单链表的头指针存在哈希表的第i个单元中 因而查找、插入和删除主要在同义词链中进行。 链地址法适用于经常进行插入和删除的情况。 4. 建立公共溢出区
这种方法的基本思想是将哈希表分为基本表和溢出表两部分凡是与基本表发生冲突的元素一律填入溢出表。
3.哈希表的查找过程
哈希表的查找过程与哈希表的创建过程是一致的。 当查找关键字为K的元素时 首先计算p0hashK。如果单元p0为空 则所查元素不存在 如果单元p0中元素的关键字为K则找到所查元素否则重复下述解决冲突的过程 按解决冲突的方法找出下一个哈希地址pi 如果单元pi为空则所查元素不存在如果单元pi中元素的关键字为K则找到所查元素。
//以线性探测再散列为例
define m 哈希表长度
define NULLKEY 代表空记录的关键字值
typedef int KeyType;
typedef struct{KeyType key; } RecordType ;
typedef RecordType HashTablem ; int HashSearch( HashTable ht, KeyType K)
{p0hash(K); if (htp0.keyNULLKEY) return (-1); else if (htp0.keyK) return (p0); else /* 用线性探测再散列解决冲突 */{ for (i1; im-1; i) { pi(p0i) % m; if (htpi .keyNULLKEY) return (-1); else if (htpi.keyK) return (pi); } return (-1); }
} 4.哈希法性能分析
由于冲突的存在哈希法仍需进行关键字比较 因此仍需用平均查找长度来评价哈希法的查找性能。哈希法中影响关键字比较次数的因素有三个哈希函数、 处理冲突的方法以及哈希表的装填因子。
哈希表的装填因子α的定义如下 α可描述哈希表的装满程度。 显然α越小 发生冲突的可能性越小 而α越大 发生冲突的可能性也越大。 假定哈希函数是均匀的 则影响平均查找长度的因素只剩下两个 处理冲突的方法以及α。以下按处理冲突的不同方法分别列出相应的平均查找长度。
线性探测再散列 伪随机探测再散列、 二次探测 链址法 从以上讨论可知哈希表的平均查找长度是装填因子α的函数而与待散列元素数目n无关。因此 论元素数目n有多大都能通过调整α使哈希表的平均查找长度较小。
手工计算等概率情况下查找成功的平均查找长度规则如下 手工计算等概率情况下查找不成功的平均查找长度规则如下
