搜索引擎优化的主题,网站seo优化,自己做网站怎么维护,江阴网站建设推广要查询信息#xff0c;涉及两个问题#xff1a;
在哪里查#xff1f;——查找表
怎么查#xff1f;——查找方法
一.查找
1.查找表的定义#xff1a;
查找表是由同类型的数据元素构成的集合
2.对查找表的基本操作#xff1a; 1#xff09;查询某个数据元素是否在查…要查询信息涉及两个问题
在哪里查——查找表
怎么查——查找方法
一.查找
1.查找表的定义
查找表是由同类型的数据元素构成的集合
2.对查找表的基本操作 1查询某个数据元素是否在查找表中 2检索某个数据元素的各种属性 3在查找表中插入一个数据元素 4从查找表中删除某个元素 3.查找表的分类
静态查找表
仅作查询和检索操作的查找表
动态查找表
可以进行“插入”和“删除”操作
4.关键字
关键字是数据元素中某个数据项的值用以标识一个数据元素。
主关键字若关键字能标识唯一的一个数据元素
次关键字若关键字能标识若干个数据元素
5.查找
根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素。
6.查找方法评价 算法本身的时间复杂度临时变量占用存储空间的多少平均查找长度ASLAverage Search Length 对于含有n个记录的表
其中为查找表中第i个元素的概率
为找到表中第i个元素所需要比较的次数 7. 顺序表的查找
7.1 基本思想
从表中指定位置的记录开始沿着某个方向将记录的关键字与给定值相比较若某个记录的关键字与给定值相同则查找成功。
反之若找完整个顺序表都没有与给定关键字值相同的记录则查找失败。
7.2 顺序查找的性能分析 查找第n个元素1次 查找第n-1个元素2次 ... 查找第1个元素n次 查找第i个元素n1-i次 查找失败n1次 空间复杂度 需要一个辅助空间R[0] 时间复杂度 等概率情况下 平均情况 优点算法简单适用面广 缺点平均查找长度较大 8.折半查找
8.1 基本思想
查找过程每次将待查记录所在区间缩小一半。
适用条件采用顺序存储的有序表
8.2 伪代码
设表长为nlow、high和mid分别指向待查元素所在区间的上界、下界和中点k为给定值。 初始时令low0highn-1mid(highlow)/2。 让k与mid指向的记录比较 若kr[mid].key 查找成功若kr[mid].key 则highmid-1若kr[mid].key 则lowmid1 重复上述操作直至lowhigh为止查找失败。 int biserach(int r[],int n,int k){int low0,highn-1,mid0;while(lowhigh){mid(lowhigh)/2;if(r[mid]k){break;}else if(r[mid]k){highmid-1;}else{lowmid1;}}if(lowhigh){return -1;}else{return mid;}
}
8.3 算法性能分析 判定树描述查找过程的二叉树 有n个结点的判定树的层次数为 折半查找在查找过程中进行的比较次数最多不超过其判定树的深度。 折半查找的ASL
设表长为,,即判定树为深度为h的满二叉树
设表中每个记录的查找概率相等 8.4 折半查找的特点
1查找效率高
2平均查找性能和最坏性能相当接近
3要求查找表为有序表
4只适用于顺序存储结构 9.索引表查找
9.1 索引表的构建
数据分块
按关键字分成若干块达到分块有序。
建索引项
每一个块建立一个索引项每个索引项包含最大关键字项块的起始地址。
组成索引表
所有索引项组成索引表 9.2 索引表的查找
索引表内查找确定关键字所在区块。
查找表内查找查找表的某个块内查找 9.3 索引表查找的代码实现
typedef struct{int key;int link;
}SD;
typedef struct{int key;float info;
}JD;
int block_search(JD r[],SD nd[],int b,int k,int n){//n个记录分成b块int i0,j;while(knd[i].keyib){i;}if(ib){coutnot foundendl;return -1;}else{//在块内顺序查找jnd[i].link;while(jnk!r[j].key){j;}if(k!r[j].key){coutnot foundendl;return -1;}else{return j;}}
}
9.4 分块查找方法评价 若将表长为n的表平均分成b块每块含有s个记录并设表中每个记录的查找概率相等。
则有 1用顺序查找确定所在块 2)用折半查找确定所在块 10.查找方法比较
顺序查找折半查找索引查找ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储、单链表顺序存储顺序存储、单链表
11.哈希表查找
ASL1的查找算法。
如果可以确定关键字与存储位置的对应关系就有可能让ASL1.
11.1 哈希查找的基本定义
哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系
哈希查找又叫散列查找利用哈希函数进行查找的过程。
哈希函数是一种映射即从关键字空间到存储地址空间的一种映射。
哈希函数可以写成 11.2 冲突
哈希函数通常是一种压缩映射所以冲突不可避免。
冲突发生后应该有处理冲突的方法。
1直接定址法线性函数
例如H(key)key-1948 直接定址法所得地址集合与关键字集合大小相等不会发生冲突。 (2)数字分析法
对关键字进行分析取关键字的若干位或其组合作为哈希地址。
适用于关键字位数比哈希地址位数大且可能出现的关键字事先知道的情况。
3平方取中法
取关键字平方后的中间几位作为哈希地址
为什么要取关键字的平方值
扩大差别 均衡贡献
4折叠法
将关键字分割为位数相同的几部分然后取这几部分的叠加和舍去进位作哈希地址。
适用于关键字位数很多且每一位上数字分布大致均匀的情况
例如 关键字为 04 4220 5864 哈希地址位数为4
移位叠加 间界叠加
5 8 6 4 5 8 6 4
4 2 2 0 0 2 2 4
0 0 0 4 0 0 0 4
---------------------------------------------------------------------------
5除留余数法
H(key)key MOD p,pm,m为hash表长。
p选取不好容易产生同义词通常选取一个质数。 6伪随机数法
取关键字的随机函数作哈希地址值即H(key)random(key)
适用于关键字长度不等的情况。 11.3 选取哈希函数需要考虑的因素 1计算哈希函数所需的时间 2关键字长度 3哈希表长度 4关键字分布情况 5记录的查找频率 11.4 冲突处理
为出现哈希地址冲突的关键字寻找下一个新的哈希地址。
1开放定址法
当冲突发生时形成一个探查序列沿着此序列逐个地址探查直到找到一颗空位置将发生冲突的记录放入该地址中即
m 哈希表表长di 增量序列。 增量序列分类
线性探测再散列 di1,2,3,...,m-1
平方探测再散列
伪随机探测再散列 di伪随机数序列 例 2再哈希法
构造若干个哈希函数当发生冲突时计算下一个哈希地址。
3链地址法
将所有关键字为同义词的记录存储在一个单链表中并用一位数组存放头指针。
4公共溢出区法
假设某哈希函数的值域为[o,m-1]
向量HashTable[0,m-1]为基本表每个分量存放一个记录另设一个向量OverTable[0,v]为溢出表。将与基本表中的关键字发生冲突的所有记录都填入溢出表中。 11.5 例题分析
已知一组关键字19142316820842755111079
哈希函数为H(key)key MOD 13 哈希表长为16设每个记录的查找概率相等。
1线性探测再散列处理冲突
012345678910111213141514168275519208479231110
1 1 1 2 1 1 3 4 3 1 3 9
ASL30/122.5
2链地址法处理冲突
ASL6*14*21*31*4/121.75
11.6 哈希查找分析
哈希查找过程仍然是一个给定值与关键字进行比较的过程
评价哈希查找仍要用ASL
哈希查找过程与给定值进行关键字比较的次数取决于 哈希函数处理冲突的方法哈希表的装载因子 k:表中填入的记录数
L:哈希表长度 二.排序 1.内部排序的方法
内部排序的过程是一个逐步扩大有序区记录的过程 2.排序分为
稳定排序不稳定排序
3.直接插入排序稳定
3.1 基本思想
先将序列中第一个记录看成是一个有序子序列然后从第二个记录开始逐个进行插入直至整个序列有序。整个排序过程为n-1躺插入。
3.2 具体例子
i1 49 38 65 97 76 13 27
i2 38 49 65 97 76 13 27
i3 38 49 65 97 76 13 27
i4 38 49 65 97 76 13 27
i5 38 49 65 76 97 13 27
i6 13 38 49 65 97 76 27
i7 13 27 38 49 65 76 97
3.3 代码实现
void insert_select(int r[],int n){int i,j,temp;for(i1;in;i){tempr[i];ji-1;while(tempr[j]){r[j1]r[j];--j;}r[j1]temp;}
}
3.4 算法评价
时间复杂度 空间复杂度 4.折半插入排序稳定
4.1 基本思想
用折半查找方法确定插入位置的排序
4.2 算法分析
时间复杂度 空间复杂度 5.希尔排序缩小增量法非稳定
5.1 基本思想
希尔排序是对插入排序的改进。
(1) 插入排序对几乎已排好序的数据操作时效率很高可以达到线性排序的效率。
(2) 插入排序在每次往前插入时只能将数据移动一位效率比较低。
先将整个待排元素序列分割成若干个子序列由相隔某个“增量”的元素组成的。分别进行直接插入排序然后依次缩减增量再进行排序待整个序列中的元素基本有序增量足够小时再对全体元素进行一次直接插入排序。
局部有序不能提高直接插入排序算法的时间性能
5.2 代码实现
void shell_sort(int r[],int n){int din/2,i,j,temp;while(di1){for(idi;in;i){ji-di;tempr[i];while(tempr[j]j0){r[jdi]r[j];j-di;}r[jdi]temp;}di/2;}
}
5.3 性能分析
时间复杂度 空间复杂度
S(1)
6.冒泡排序稳定
6.1 基本思想
两两比较相邻记录的关键码如果反序则交换直到没有反序的记录为止。
6.2 对冒泡排序的改进
1设变量exchange记载记录交换的位置。则一趟排序后exchange记载的一定是这一趟排序中记录的最后一次交换的位置。且从此位置以后的记录均已有序。
2设bound位置的记录是无序区的最后一个记录则每趟冒泡排序的范围是r[0]~r[bound]。
在一趟排序后从exchange位置之后的记录一定是有序的所以boundexchange。
3令exchange初值为0在以后的排序中只要有记录交换exchange的值就会大于0。则当exchange0时冒泡排序结束。
6.3 代码实现
void buble_sort(int r[],int n){int exchangen-1,bound,i,temp;while(exchange){boundexchange;exchange0;for(i0;ibound;i){if(r[i]r[i1]){tempr[i];r[i]r[i1];r[i1]temp;exchangei;}}}}
6.4 性能分析
时间复杂度 空间复杂度 7.快速排序
7.1 基本思想
通过一趟排序将待排记录分隔成独立的两部分。其中一部分记录的关键码均比另一部分的关键码小则可分别对这两部分记录继续进行排序以达到整个序列有序。
首先选取一个轴值。通过一趟排序将待排序记录分割成独立的两部分。前一部分记录的关键码均小于或等于轴值后一部分记录的关键码均大于或等于轴值。然后分别对这两部分重复上述方法。
7.2 如何实现划分
设待划分的序列是r[s]~r[t]。设参数ij分别指向子序列左右两端的下标s和t。令r[s]为轴值。 j从后向前扫描直到r[j]r[i]将r[j]移动到r[i]的位置使关键码小的记录移动到前面。i从前向后扫描直到r[i]r[j]将r[i]移动到r[j]的位置使关键码大的记录移动到后面。重复上述过程直到ij。 7.3 递归出口 若待排序序列中只有一个记录则显然有序否则进行一次划分后再分别对所得的两个子序列进行快速排序。
7.4 代码实现
int get_partition(int first,int end,int r[]){int ifirst,jend,temp;while(ij){while(r[i]r[j]ij){--j;}if(ij){tempr[j];r[j]r[i];r[i]temp;i;}while(r[i]r[j]ij){i;}if(ij){tempr[j];r[j]r[i];r[i]temp;--j;}}return i;
}
void quick_sort(int r[],int first,int end){if(firstend){int posget_partition(first, end, r);quick_sort(r, first, pos-1);quick_sort(r, pos1, end);}
}
7.5 性能分析
时间复杂度与选取的轴值有关。
最好情况为每次均选取到中间值作为轴值最坏情况为每次都选取到最大或最小元素最为轴值。
平均时间复杂度
最坏时间复杂度
采用“三者取中”来确定轴值即第一个元素最后一个元素最中间的元素中的中间值作为划分元。
空间复杂度
8.选择排序
8.1 基本思想 每趟排序在当前待排序序列中选出关键码最小的记录添加到有序序列中。
8.2 代码实现
void select_sort(int r[],int n){int min,i,j,temp;for(i0;in-1;i){mini;for(ji1;jn;j){if(r[j]r[min]){minj;}}if(min!i){tempr[min];r[min]r[i];r[i]temp;}}
}
8.3 性能分析
时间复杂度: 9.归并排序稳定
速度仅慢于快速排序适用于分段有序的数列为稳定排序算法。
9.1 基本思想分治
1只包含一个元素的子表是有序表
2将有序的子表合并
3得到最终表
4) 需要一个辅助的临时数组 9.2 代码实现
void merge_sort_recursive(int r[],int reg[],int start,int end){if(startend){return;}int mid(startend)/2;merge_sort_recursive(r, reg, start, mid);merge_sort_recursive(r, reg, mid1, end);//通过上述操作已经获得了两个有序的子序列//合并int istart,jmid1,kstart;while(imidjend){if(r[i]r[j]){reg[k]r[i];}else{reg[k]r[j];}}while(imid){reg[k]r[i];}while(jend){reg[k]r[j];}for(istart;iend;i){r[i]reg[i];}
}
void merge_sort(int r[],int n){int reg[MAX_SIZE];//辅助数组merge_sort_recursive(r, reg, 0, n-1);
}9.3 性能分析
时间复杂度
空间复杂度O(n) 10.排序方法比较
10.1 排序方法选择主要考虑
1待排序记录的数量
2关键字的分布情况
3对排序稳定性的要求
10.2 时间特性 时间复杂度为快速、归并 时间复杂度为插入、冒泡、选择 待排序记录基本有序时插入和冒泡可以达到O(n) 选择、归并排序的时间特性不随关键字的分布而改变。 稳定排序插入、冒泡、归并 不稳定快速、选择、希尔
