数据结构知识点总结

int BinSearch (sqlist r, int k, int n ) {

low ? 1；

high ? n； find ? 0;

while ( low ≤ high and not find ) {

mid ? (low + high) / 2 ; if (k < r[mid]. key) high ? mid - 1; else if ( k > r[mid]. key ) low ? mid + 1; else {

i ? mid; find ? 1; } }

if ( not find ) i ? 0; return ( i ); }

折半查找法使用于存储结构为顺序存储且按关键字排好序的线性表。

在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。

--------------------------------------------------------------------- 排序

在已知待排序文件已基本有序的前提下，效率最高的排序方法是直接插入排序 考排序的效率和特点：

一、插入排序(Insertion Sort) 1. 基本思想：

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程：

【示例】：

[初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97]

二、选择排序 1. 基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】：

初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76]