大学计算机查找的概念在给定的查找表中找出满足某种条件的结点；若存在这样的结点，则查找成功；否则，查找失败。查找表：是一组待查数据元素的集合。
性能衡量指标：平均查找长度（与关键字进行比较的平均次数） 两种基本形式：静态查找和动态查找基本形式查找表是记录的集合，元素之间是
一种完全松散的关系；查找表结构灵活，可用多种方式来存储。存储结构的不同决定了查找方法的不同。查找表的组织四种基本存储结构基本查找方
法顺序查找从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，查找成功；若扫描完整个表，仍没有找
到相应的记录，则查找失败。折半查找折半查找又称为二分查找，要求查找表中的所有记录按关键字有序(升序或降序) 。查找时，先和查找表最
中间位置的元素进行比较，确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。
分块查找分块查找又称索引顺序查找，是顺序比较和折半查找方法的综合。将查找表分成若干块。块间有序，块内无序。即第i+1块的所有记录关
键字均大于(或小于)第i块记录的关键字；在查找表的基础上附加一个索引表，索引表按关键字有序。先确定待查记录所在块（顺序或折半），再
在块内查找(顺序查找)。二叉排序树查找将给定的K值与二叉排序树根结点的关键字进行比较： 若相等： 则查找成功；若给定的K值小于二叉
排序树根结点的关键字：继续在该结点的左子树上进行查找；查找失败，插入该节点（仍是二叉排序树）。若给定的K值大于二叉排序树根结点的关
键字：继续在该结点的右子树上进行查找。查找失败，插入该节点（仍是二叉排序树）。散列表查找设计一种记录存储地址和它关键字之间的确定对
应关系，根据该关系构造查找表（散列表）；查找时，直接定位元素的存储位置。顺序查找特点：n个元素，所需空间n+1;元素存于a[1]-
--------------a[n];a[0]为监视哨，为查找失败标志；查找时，从后向前比较； int p ; a[0]=ke
y ; / 设置监视哨兵,失败返回0 /for (p=9; a[p]!=key; p--);return(p) ; 查找3
8，结果为3；查找-10，结果为0；head特点：链式存储从前向后比较。 p=head;While(p!=NULL&&p->dat
a!=key)p=p->next;return(p) ; head查找23phead查找-10P:NULL不失一般性，设查找每个记
录成功的概率相等，即Pi=1/n；若表长为10亿，ASL约为5亿。折半查找（1）首先确定整个查找区间的中间位置; mid= (le
ft+right )/2（2）用待查关键字值与中间位置的关键字值进行比较:若相等，则查找成功；若大于，则确定查找范围为后半区域 [
mid+1,right]；若小于，则确定查找范围为前半区域 [left,mid-1] 。（3）对确定的缩小区域重复（1）、（2）步
骤；算法步骤查找关键字值为87的数据元素leftrightmid87>72缩小查找范围为右半部分mid+1至right查找关键字值
为87的数据元素rightmid（2）leftrightmid（1）查找时每经过一次比较，查找范围就缩小一半。一般情况下，表长为
n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。若表长为10亿，ASL约为29。分块查找查找表分成若干块；块
内可无序也可有序，块间有序。例中，21个元素，每块6个，分4块（最后一块一般不满）为查找表建立索引表每块一个索引项块最大关键字有序
两种组织方式有序列 12,23,5,6,7,29,43,57,87,36,40,90,120,95,112,93,95,219,2
23,567,350分两步：①对索引表进行二分查找或顺序查找，确定待查记录在哪一块；②在已确定的块中用顺序法进行查找。算法步骤（1
）先选取各块中的最大关键字构成一个索引表；（2）查找有序列 12,23,5,6,7,29,43,57,87,36,40,90,12
0,95,112,93,95,219,223,567,350查找112散列表查找哈希函数：确定记录关键字与记录存储地址之间对应关系
的函数。哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并记录存入该地址，采用此方法构造的表叫哈希表，也叫散列表。
散列表的构造哈希函数设定灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。两个关键字的哈希地址相等，或空间已被占
用，称为冲突。散列表查找过程例如，有关键字序列： 67 81 52 73 44 91 27
36 20 39。存储空间大小：13地址计算规则：L=K MOD 13； 冲突解决机制：线性探测散列表查找时比较次数
查找成功的 ASL=17/10=1.7设 n 个记录的序列为 { R1 , R2 , R3 , . . . , Rn }相应的关键
字序列为 { K1 , K2 , K3 , . . . , Kn }若一个排列 p1 , p2 , p3 , . . . , pn
，使得相应的关键字满足非递减关系。排序的概念排序的分类常见内部排序方法稳定排序算法不稳定排序算法将关键字的插入到已排序序列的适当
位置完成排序。插入排序直接插入排序初始，令第 1 个元素作为初始有序表；依次插入第 2 , 3 , …, k 个元素，构造新的有序
表；直至最后一个元素；直接插入排序算法主要应用比较和移动两种操作。算法步骤例如，有待排序列：37，26，30，56，78，28，3
7。初始： 有序序列{37}待排序列{26，30，56，78，28，37}第1趟：有序序列{26，37}待排序列{30，56，78
，28，37}第2趟：有序序列{26，30，37}待排序列{56，78，28，37}第3趟：有序序列{26，30，37，56}待排
序列{78，28，37}第3趟：有序序列{26，30，37，56}待排序列{78，28，37}第4趟：有序序列{26，30，37，
56，78}待排序列{28，37}第5趟：有序序列{26，28，30，37，56，78}待排序列{37}第6趟：有序序列{26，2
8，30，37，37，56，78}待排序列{}稳定排序算法不稳定排序算法将比较关键字大小，交换位置完成排序交换排序冒泡排序首先将第
一个元素与第二个元素比较大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；直至比较第 n-1 个元素
与第 n 个元素的大小，若为逆序，则交换；第1趟排序：结果：关键字最大的记录被交换至最后一个元素位置上。算法步骤重复以上步骤，直到
有序。例如，有序列 23，14，78，65，26，98，73，18，14，冒泡排序。第1趟：①②③④⑤⑥⑦⑧第2趟：第3趟：第4趟
：第5趟：第6趟：第7趟：第8趟：序列有序故时间复杂度：T(n)=O(n2) 空间复杂度：S(n)=O(1)时间复杂度◆
最好情况（正序）：比较次数：n-1；移动次数：0；◆ 最坏情况（逆序）：不稳定排序算法不稳定排序算法从待排序列中选出极值，存
入特定位置。选择排序简单选择排序第 1 趟：从 1—n 个记录中选择关键字最小的记录，并和第 1 个记录交换。第 2 趟：从 2
—n 个记录中选择关键字最小的记录，并和第 2 个记录交换。第n-1趟：从 n-1—n 个记录中选择关键字最小的记录，并和第 n-1 个记录交换。算法步骤以序列 23，14，78，65，26，98，73，18，14为例。第1趟：第2趟：第3趟：第4趟：第5趟：第6趟：第7趟：第8趟：对n个记录进行排序的趟数为n-1趟,进行第i趟排序时，关键字的比较次数为n-i，则：时间复杂度是：T(n)=O(n2), 空间复杂度是：S(n)=O(1) |
|
