排序与查找
第3章排序与查找
在计算机科学中，排序(sorting)是研究得最多的问题之一，许多书籍都深入讨论了这个问题。本章仅仅是一个介绍，重点放在C语言的实际应用上。
排序
程序员可以使用的基本排序算法有5种：
·插入排序(insertionsort．)
·交换排序(exchangesOrt)
·选择排序(selectionsort)
·归并排序(mergesort)
·分布排序(distributionsort)
为了形象地解释每种排序算法是怎样工作的，让我们来看一看怎样用这些方法对桌上一付乱序的牌进行排序。牌既要按花色排序(依次为梅花、方块、红桃和黑心)，还要按点数排序(从2到A)。
插入排序的过程为：从一堆牌的上面开始拿牌，每次拿一张牌，按排序原则把牌放到手中正确的位置。桌上的牌拿完后，手中的牌也就排好序了。
交换排序的过程为：
(1)先拿两张牌放到手中。如果左边的牌要排在右边的牌的后面，就交换这两张牌的位置。
(2)然后拿下一张牌，并比较最右边两张牌，如果有必要就交换这两张牌的位置。
(3)重复第(2)步，直到把所有的牌都拿到手中。
(4)如果不再需要交换手中任何两张牌的位置，就说明牌已经排好序了；否则，把手中的牌放到桌上，重复(1)至(4)步，直到手中的牌排好序。
选择排序的过程为：在桌上的牌中找出最小的一张牌，拿在手中；重复这种操作，直到把所有牌都拿在手中。
归并排序的过程为：把桌上的牌分为52堆，每堆为一张牌。因为每堆牌都是有序的(记住，此时每堆中只有一张牌)，所以如果把相邻的两堆牌合并为一堆，并对每堆牌进行排序，就可以得到26堆已排好序的牌，此时每一堆中有两张牌。重复这种合并操作，就可以依次得到13堆牌(每一堆中有4张牌)，7堆牌(有6堆是8张牌，还有一堆是4张牌)，最后将得到52张的一堆牌。
分布排序(也被称作radix sort，即基数排序)的过程为：先将牌按点数分成13堆，然后将这13堆牌按点数顺序叠在一起；再将牌按花色分成4堆，然后将这4堆牌按花色顺序叠在一起，牌就排好序了。
在选用排序算法时，你还需要了解以下几个术语：
(1)自然的(natural)
如果某种排序算法对有序的数据排序速度较快(工作量变小)，对无序的数据排序速度却较慢(工作变量大)，我们就称这种排序算法是自然的。如果数据已接近有序，就需要考虑选用自然的排序算法。
(2)稳定的(stable)
如果某种排序算法能保持它认为相等的数据的前后顺序，我们就称这种排序
算法是稳定的。
例如，现有以下名单：
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用稳定的排序算法按姓对上述名单进行排序，那么在排好序后"Mary Jones”和"Tom Jones”将保持原来的Jr顺序，因为它们的姓是相同的。
稳定的排序算法可按主、次关键字对数据进行排序，例如按姓和名排序(换句话说，主要按姓排序，但对姓相同的数据还要按名排序)。在具体实现时，就是先按次关键字排序，再按主关键字排序。
(3)内部排序(internal sort)和外部排序(external sort)
待排数据全部在内存中的排序方法被称为内部排序，待排数据在磁盘、磁带和其它外存中的排序方法被称为外部排序。
查找
和排序算法一样，查找(searching)算法也是计算机科学中研究得最多的问题之一。查找算法和排序算法是有联系的，因为许多查找算法依赖于要查找的数据集的有序程度。基本的查找算法有以下4种：
·顺序查找(sequential searching)。
·比较查找(comparison searching)
·基数查找(radix searching)
·哈希查找(hashing)
下面仍然以一付乱序的牌为例来描述这些算法的工作过程。
顺序查找的过程为：从第一张开始查看每一张牌，直到找到要找的牌。
比较查找(也被称作binarysearching，即折半查找)要求牌已经排好序，其过程为：任意抽一张牌，如果这张牌正是要找的牌，则查找过程结束。如果抽出的这张牌比要找的牌大，则在它前面的牌中重复查找操作；反之，则在它后面的牌中重复查找操作，直到找到要找的牌。
基数查找的过程为：先将牌按点数分成13堆，或者按花色分成4堆。然后找出与要找的牌的点数或花色相同的那一堆牌，再在这堆牌中用任意一种查找算法找到要找的牌。
哈希查找的过程为：
(1)在桌面上留出可以放若干堆牌的空间，并构造一个函数，使其能根据点数和花色将牌映射到特定的堆中(这个函数被称为hashfunction，即哈希函数)。
(2)根据哈希函数将牌分成若干堆。
(3)根据哈希函数找到要找的牌所在的堆，然后在这一堆牌中找到要找的牌。
例如，可以构造这样一个哈希函数：
pile=rank+suit
其中，rank是表示牌的点数的一个数值；suit是表示牌的花色的一个数值；pile表示堆值，它将决定一张牌归入到哪一堆中。如果用1，2，……，13分别表示A，2，……．K，用0，1，2和3分别表示梅花、方块、红桃和黑桃，则pile
的值将为1，2，……，16，这样就可以把一付牌分成16堆。
哈希查找虽然看上去有些离谱，但它确实是一种非常实用的查找算法。各种各样的程序，从压缩程序(如Stacker)到磁盘高速缓存程序(如SmartDrive)，几乎都通过这种方法来提高查找速度，
排序或查找的性能
有关排序和查找的一个主要问题就是速度。这个问题经常被人们忽视，因为与程序的其余部分相比，排序或查找所花费的时间几乎可以被忽略。然而，对大多数排序或查找应用来说，你不必一开始就花很多精力去编制一段算法程序，而应该先在现成的算法中选用一种最简单的(见3．1和3．4)，当你发现所用的算法使程序运行很慢时，再换用一种更好的算法(请参见下文中的介绍)。
下面介绍一种判断排序或查找算法的速度的方法。
首先，引入一个算法的复杂度的概念，它指的是在各种情况(最好的、最差的和平均的)下排序或查找需要完成的操作次数，通过它可以比较不同算法的性能。
算法的复杂度与排序或查找所针对的数据集的数据量有关，因此，引入一个基于数据集数据量的表达式来表示算法的复杂度。
最快的算法的复杂度O(1)，它表示算法的操作次数与数据量无关。复杂度O(N)(N表示数据集的数据量)表示算法的操作次数与数据量直接相关。复杂度
O(logN)介于上述两者之间，它表示算法的操作次数与数据量的对数有关。复杂度为O(NlogN)(N乘以logN)的算法比复杂度为O(N)的算法要慢，而复杂度为O(N2)的算法更慢。
注意：如果两种算法的复杂度都是O(logN)，那么logN的基数较大的算法的速度要快些，在本章的例子中，logN的基数均为10。
表3．1 本章所有算法的复杂度
----------------------------------------------------------------- 算法最好情况平均情况最坏情况
-----------------------------------------------------------------
快速排序 O(NlogN) O(NlogN) O(N2)
归并排序 O(N) O(NlogN) O(NlogN)
基数排序 O(N) O(N) O(N)
线性查找 O(N)
折半查找 O(NlogN)
哈希查找 O(N/M)*
健树查找 O(1)**
-----------------------------------------------------------------
* M是哈希表项的数目
** 实际上相当于有232个哈希表项的哈希查找
表3. 1列出了本章所有算法的复杂度。对于排序算法，表中给出了最好的、平均的和最差的情况下的复杂度，平均情况是指数据随机排列的情况；排序算法的复杂度视数据的初始排列情况而定，它一般介于最好的和最差的两种情况之
间。对于查找算法，表中只给出了平均情况下的复杂度，在最好的情况(即要找的数据恰好在第一次查找的位置)下，查找算法的复杂度显然是O(1)；在最坏的情况(即要找的数据不在数据集中)下，查找算法的复杂度通常与平均情况下的复杂度相同。
需要注意的是，算法的复杂度只表示当N值变大时算法的速度变慢的程度，它并不表示算法应用于给定大小的数据集时的实际速度。算法的实际速度与多种因素有关，包括数据集的数据类型以及所用的编程语言、编译程序和计算机等。换句话说，与复杂度高的算法相比，复杂度低的算法并不具备绝对的优越性。实际上，算法的复杂度的真正意义在于，当N值大于某一数值后，复杂度低的算法就会明显比复杂度高的算法快。
为了说明算法的复杂度和算法的实际执行时间之间的关系，表3．2列出了本章所有例子程序的执行时间。本章所有例子程序均在一台以Linux为操作系统的90MHz奔腾计算机上由GNU C编译程序编译，在其它操作系统中，这些例子程序的执行时间与表3．2所列的时间是成比例的。
表3. 2 本章所有例子程序的执行时间
---------------------------------------------------------------------------
例子程
序算法 2000 4000 6000 8000 10000
---------------------------------------------------------------------------
例3．1 qsort() 0．02 0．05 0．07 0．11 0，13
例3．2a 快速排序 0．02 0．07 0．13 0．18 0．20 例3．2b 归并排序 0．03 0．08 0．14 0．18 0．26 例3．2c 基数排序 0．07 0．15 0．23 0．30 0．39 例3．4 bsearch() 0. 37 0．39 0．39 0．40 0．41 例3．5 折半查找 0．32 0．34 0．34 0．36 0．36 例3．6 线性查找 9．67 20．68 28．71 36．31 45.
51
例3．7 键树查找 0．27 0．28 0．29 0．29 0．30 例3．8 哈希查找 0．25 0．26 0．28 0．29 0．28 ---------------------------------------------------------------------------
注意：(1)表中所列的时间以秒为单位。(2)表中所列的时间经过统一处理，只包括排序或查找所花费的时间。(3)2000等数值表示数据集的数据量。(4)数据集中的数据是从文件／usr／man／manl／gcc．1(GNUC编译程序中的一个文件)中随机提取的词。(5)在查找算法中，要查找的数据是从文件／usr／man／manl ／g++．1(GNUC++编译程序中的一个文件)中随机提取的词。(6)函数qsort()和bseareh()分别是C标准库函数中用于快速排序算法和折半查找算法的函数，其余例子程序是专门为本章编写的。
在阅读完以上内容后，你应该能初步体会到如何根据不同的情况来选用一种
合适的排序或查找算法。在Donald E．Knuth所著的《The Art Of Computer Programming，Volume 3，Sorting and Searching》一书中，作者对排序和查找算法进行了全面的介绍，在该书中你将读到更多关于复杂度和复杂度理论的内容，并且能见到比本章中所提到的更多的算法。
公用代码
本章中的许多例子程序是可以直接编译运行的。在这些例子程序中，许多代码是相同的，这些相同的代码将统一在本章的末尾列出。
3．1 哪一种排序方法最方便?
答案是C标准库函数qsort()，理由有以下三点：
(1)该函数是现成的；
(2)该函数是已通过调试的；
(3)该函数通常是已充分优化过的。
qsort()函数通常使用快速排序算法，该算法是由C. A．R．Hoare于1962年提出的。以下是qsort()函数的原型：
void qsort(void *buf，size_t hum，size_t size，
int(*comp)(const void *ele1，const void *ele2));
qsort()函数通过一个指针指向一个数组(buf)，该数组的元素为用户定义的数据，数组的元素个数为num，每个元素的字节长度都为size。数组元素的排序是通过调用指针comp所指向的一个函数来实现的，该函数对数组中由ele1和ele2所指向的两个元素进行比较，并根据前者是小于、等于或大于后者而返回一个小于、等于或大于0的值。
例3．1中给出了一个函数sortStrings()，该函数就是通过qsort()函数对一个以NULL指针结束的字符串数组进行排序的。将例3．1所示的代码和本章结尾的有关代码一起编译成一个可执行程序后，就能按字母顺序对一个以NULL指针结束的字符串数组进行排序了。
1:#include
2:
3: /*
4: * This routine is used only by sortStrings(), to provide a
5: * string comparison {unction to pass to qsort().
6: */
7: static int comp(const void * elel, const void * ele2)
8: {
9: return strcmp( * (const char * * ) ele1,
10: * (const char * * ) ele2);
11: }
12:
13: / * Sort strings using the library function qsort() * /
14: void sortStrings(const char * array[-'])
15: {
16, /* First, determine the length of the array * /
17: int num;
18:
19: for (num=O; array[num]; num++)
20:
21: qsort(array, num, sizeof( * array), comp) ;
22: }
在例3．1中，第19行和第20行的for循环语句用来计算传递给qsort()函数的数组元素个数，函数comp()的作用是将函数qsort()传递给它的类型(const void *)转换为函数strcmp()
所要求的类型(const char *)。因为在函数qsort()中，ele1和ele2是指向数组元素的指针，而在例3．1中这些数组元素本身也是指针，因此，应该先将ele1和ele2转换为const char **类型，然后在转换结果前加上指针运算符“*”，才能得到函数strcmp()所要求的类型。
尽管有qsort()函数，但程序员经常还要自己编写排序算法程序，其原因有这样几点：第一，在有些异常情况下，qsort()函数的运行速度很慢，而其它算法程序可能会快得多；第二，qsort()函数是为通用的目的编写的，这给它带来了一些不利之处，例如每次比较时都要通过用户提供的一个函数指针间接调用一个函数；第三，由于数组元素的长度在程序运行时才能确定下来，因此用来在数组中移动数组元素的那部分代码没有针对数组元素长度相同的情况进行优化；第四，qsort()函数要求所有数据都在同一个数组中，而在实际应用中，数据的长度和性质千变万化，可能很难甚至无法满足这一要求；第五，qsort()函数通常不是一种稳定的排序方法。
请参见：
3．2 哪一种排序方法最快?
3．3 当要排序的数据集因太大而无法全部装入内存时，应怎样排序?
3．7 怎样对链表进行排序?
7．1 什么是间接引用(indirection)?
7，2 最多可以使用几层指针?
7．5 什么是void指针? ·
7．6 什么时候使用void指针?
3．2 哪一种排序方法最快?
首先，对大多数包含排序应用的程序来说，排序算法的速度并不重要，因为在程序中排序的工作量并不是很多，或者，与排序相比，程序中其它操作所花费的时间要多得多。
实际上，没有哪一种排序算法永远是最快的，在运行程序的软硬件环境相同的情况下，不同排序算法的速度还与数据的长度、性质以及数据的初始顺序有关。
在笔者的“工具箱”中，有三种算法在不同的情况下都是最快、最有用的，这三种算法分别是快速排序、归并排序和基数排序。
快速排序
快速排序是一种分割处理式的排序算法，它将一个复杂的排序问题分解为若
干较容易处理的排序问题，然后逐一解决。在快速排序算法中，首先要从数据集的数据中选择一个数据作为分割值，然后将数据分成以下3个子集：
(1) 将大于分割值的数据移到分割值前面，组成子集1；
(2) 分割值本身为子集2；
(3) 将小于分割值的数据移到分割值后面，组成子集3。
等于分割值的数据可以放在任意一个子集中，这对快速排序算法没有任何影响。
由于子集2已经是有序的，所以此后只需对子集1和子集3进行快速排序。
需要注意的是，当数据集很小时，无法进行快速排序，而要使用其它排序算法。显然，当数据集中的数据只有两个或更少时，就不可能将数据集再分割成三个子集。实际上，当数据集比
较小时，程序员就应该考虑是否仍然采用快速排序算法，因为在这种情况下另外一些排序算法往往更快。
例3. 2a用快速排序算法重写了例3．1中的字符串数组排序程序，你同样可以将它和本章末尾的有关代码一起编译成一个可执行程序。程序中定义了一个宏，它可使程序更易读，并能加快执行速度。
快速排序算法是由程序中的myQsort()函数实现的，它是按升序对一个字符串数组进行排序的。函数myQsort()的具体工作过程如下：
(1)首先检查最简单的情况。在第17行，检查数组中是否没有或只有一个元素——在这种情况下，数组已经是有序的，函数就可以返回了。在第19行，检查数组中是否只有两个元素——在这种情况下，要么数组已经是按升序排列的，要么交换这两个元素的位置，使它们按升序排列。
(2)在第28行至第53行，将数组分割为两个子集：第一个子集中的数据大于或等于分割值，第二个子集中的数据小于分割值。
在第28行，选择数组中间的元素作为分割值，并将其和数组中的第一个元素交换位置。
在第37行至第39行，在数组中找到属于第二个子集的第一个元素；在第45行至第47行，在数组中找到属于第一个子集的最后一个元素。
在第49行，检查属于第二个子集的第一个元素是否位于属于第一个子集的最后一个元素的后面，如果是，则第一个子集的所有元素都已在第二个子集的所有元素的前面，数据已经划分好了；否则，交换这两个元素的位置，然后重复上述这种检查。
(3)当两个子集分割完毕后，在第55行，将分割值和第一个子集中的最后一个元素交换位置，排序结束时这个分割值将仍然排在现在这个位置。在第57行和第58行，分别调用myQsort()函数对分割所得的子集进行排序。当所有的子集都经过排序后，整个数组也就排好序了。
例3. 2a一个不使用qsort()函数的快速排序算法程序
1: #include
2:
3: #define exchange(A, B, T) ((T) = (A), (A) = (B),(B)=(T))
4:
5:
6: / * Sorts an array of strings using quick sort algorithm * / 7: static void myQsort(const char * array[], size_t num)
8: {
9: const char * temp
10: size_t i, j;
11:
12: /*
13: * Check the simple cases first:
14: * If fewer than 2 elements, already sorted
15: * If exactly 2 elements, just swap them (if needed). 16: * /
17: if (num <2)
18: return;
19: else if (num==2)
20: {
21: if (strcmp(array[O], array[1])>O)
22: exchange (array[0], array[1] ,temp)
23: }
24: / *
25: * Partition the array using the middle (num/2)
26: element as the dividing element.
27: * /
28: exchange (array[0], array[num / 2], temp)
29: i=1;
30: j=num;
31: for (; ;)
32: {
33: / *
34: * Sweep forward until and element is found that 35: * belongs in the second partition.
36: * /
37: while (i 38: <=0) 39: i++; 40: / * 41: * Then sweep backward until an element 42: * is found that belongs in the first 43: * partition. 44: * / 45: while (i 46: >=0) 47: j--; 48: / * If no out-of-place elements, you're done * / 49: if (i>=j) 50: break 51: / * Else, swap the two out-of-place elements * / 52: exchange(array[i], array[j-l], temp) 53: } 54: / * Restore dividing element * / 55: exchange(array[O], array[i-1], temp) 56: / * Now apply quick sort to each partition * / 57: myQsort (array, i-1 ) 58: myQsort (array + i, num-i) 59: } 60: 61: / * Sort strings using your own implementation of quick sort * / 62: void sortStrings (char * array[]) 63: { 64: / * First, determine the length of the array * / 65: int num 66: 67: for (num = O; array[num] ; num++ ) 68: 69: myQsort((void * ) array, num) 70: } 归并排序 归并排序也是一种分割处理式的排序算法，它是由Johnyon Neumann于1945年提出的。 在归并排序算法中，将待排序数据看作是一个链表序列，每个链表(最坏的情况下每个链表中只有一个元素)中的数据都已经排好序，然后不断地将相邻的链表合并为一些较大的链表，当所有的链表都合并为一个链表时，排序过程也就结束了。归并排序算法特别适合于对键表或其它非数组形式的数据结构进行排序，它还能对无法放入内存的数据进行排序；或者被作为一种特定的排序算法来使用。 例3．2b是实现归并排序算法的一个例子，你可以将它和本章结尾的有关代码一起编译成一个可执行程序。有关list_t类型及其操作函数的代码也已在本章末尾列出。 在例3．2b中，字符串被存放在一个链表中，而不是一个数组中。实际上，将数据组织为链表后更利于归并排序算法对其进行处理，因为数组中的元素是无法合并的，除非利用另外分配的内存空间。 例3．2b通过以下4个函数共同实现归并排序算法： (1)split()函数 split()函数将一个字符串链表分割为一个由多个字符串链表组成的链表，其中每一个字符串链表都已经是排好序的。例如，如果初始链表为("the" "quick""brown" "fox")，则split()函数将返回一个由3个链表组成的链表，这3个链表分别为(“the”)，("quick”)和("brown”“fox”)。因为字符串 “brown”和“fox”已经是排好序的，所以它们被放到一个链表中。 尽管split()函数将初始链表分割为一系列只含一个数据的链表后，本例的排序算法仍然能很好地执行，但是，如果初始链表中的数据已经接近有序，那么在分割初始链表时，将相邻的有序数据放到同一个链表中，就能大大减少以后的工作量，从而使本例的排序算法成为自然的排序算法(见本章开始部分中的介绍)。 当输入链表不为空时，程序第14—24行的循环将一直进行下去。在每次循环中，程序第16行将构造一个新的链表；第17—22行将把输入链表中的元素不断地移到所构造的链表之中，直到处理完输入链表中的所有元素，或者检查到两个无序的元素；第23行将把所构造的链表添加到输出链表(它的数据也是链表)中。 (2)merge()函数 merge()函数将两个数据已经有序的链表合并为一个数据有序的链表。 当正在合并的两个链表都不为空时，程序第37—45行的循环将一直进行下去。第40行的if 语句将比较两个链表中的第一个元素，并把较小的元素移到输出链表中。当正在合并的两个链表中有一个为空时，另一个链表中的元素必须全部添加到输出链表中。第46行和第47行将已为空的链表和另一个链表与输出链表链接上，从而结束整个合并过程。 (3)mergePairs()函数 通过调用merge()函数，mergePairs()函数分别对一个由字符串链表组成的链表中的每个对链表进行合并，并用合并所得的链表代替原来的那对链表。 当输入链表不为空时，程序第61—77行的循环将一直进行下去。第63行的if语句检查输入链表中是否至少有两个字符串链表，如果没有，第76行就把这个单独的链表添加到输出链表中；如果有，第65行和第66行将从输入链表中选出头两个链表，第68行和69行将合并这两个链表，第72行将把合并所得的链表添加到输出链表中，第70行、第71行和第73行将释放所分配的过渡性结点，第72行和第73行将从输入链表中删去头两个链表。 (4)sortStrings()函数 sonStrings()函数对一个字符串数组进行归并排序。 程序第88行和第89行将字符串数组转换为一个字符串链表。第90行调用split()函数将初始链表分割为一个由字符串链表组成的链表。第91行和第92行调用mereePairs()函数将分割所得的链表中的所有字符串链表合并为一个字符串链表。第93行检查合并所得的链表是否为空(当原来的字符串数组中只有。个元素时该链表为空)，若不为空，才能将该链表从分割所得的链表中移出。 需要注意的是，sortStrings()函数没有释放它所用过的内存。 例3．2b一个归并排序算法程序 1. #include 2: #include "list.h" 3: 4: /* 5: * Splits a list of strings into a list of lists of strings 6: * in which each list of strings is sorted. 7: */ 8: static list-t split(list_t in) 9: { 10: list-t out 11: list-t * curr; 12: out. head=out, tail=NULL; 13: 14: while (in. head) 15: { 16: curr =newList(); 17: do 18: { 19: appendNode (curr, removeHead (&in)); 20: } 21: while (in. head && strcmp (curr->tail->u. str, 22: in. head->u.str) < = 0); 23: appendNode(&out, newNode(curr)); 24: } 25: return Out; 26: } 27: 28: /* 29: * Merge two sorted lists into a third sorted list, 30: *.which is then returned. 31: * / 32: static list_t merge (list_t first, list_t second) 33: { 34: list_t out; 35: out.head=out, tail=NULL; 36: 37: while (first. head && second, head) 38: { 39: listnode_t * temp; 40: if (strcmp (first. head->u.str, 41: second. head->u.str) <=0) 42: appendNode(&out, removeHead(&first)); 43: else 44: appendNode (&out, removeHead (&second)); 45: } 46: concatList (&out, &first); 47: concatList (&out, &second); 48: return out; 49: } 50: 51: /* 52: * Takes a list of lists 0{ strings and merges'each pair of 53: * lists into a single list. The resulting list has 1/2 as 54: * many lists as the original. 55: * / 56: static list_t mergePairs(list_t in) 57: { 58: list_ t out; 59: out. head:out, tail=NUll; 60: 61: while (in. head) 62: { 63: if (in. head->next) 64: { 65: list_t * first =in. head->u.list; 66: list_t * second; 67: in.head->next->u.list 68: in. head->u.list = copyOf (merge ( * first, 69: * second)); 70: free (first); 71: free (second); 72: appendNode (&out, removeHead (&in)) 73: free (removeHead (&in)); 74: } 75: else 76: appendNode (&out, removeHead (&in)); 77: } 78: return out 79: } 80: 81: / * Sort strings using merge sort * / 82: void sortStrings (const char * array[]) 83: { 84: int i; 85: list_t out; 86: out.head=out, tail=NULL; 87: 88: for (i=0; array[i]; i++) 89: appendNode(&out, newNode((void * ) array[i])) 90: out= split (out); 91: while (out.head ! =out.tail) 92: out = mergePairs (out); 93: if (out.head) 94: out = * out.head->u.list; 95: for (i=O; array[i]; i++) 96: array[i] = removeHead (&out)->u.str; 97: } 陕西科技大学实验报告 班级学号姓名实验组别 实验日期室温报告日期成绩 报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：查找与排序算法的实现和应用 实验目的： 1. 掌握顺序表中查找的实现及监视哨的作用。 2. 掌握折半查找所需的条件、折半查找的过程和实现方法。 3. 掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。 4. 掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方 法。 5. 掌握直接插入排序、希尔排序、快速排序算法的实现。 实验环境（硬/软件要求）：Windows 2000,Visual C++ 6.0 实验内容： 通过具体算法程序，进一步加深对各种查找算法的掌握，以及对实际应用中问题解决方 法的掌握。各查找算法的输入序列为：26 5 37 1 61 11 59 15 48 19输出 要求：查找关键字37,给出查找结果。对于给定的某无序序列，分别用直接插入排序、希尔排序、快速排序等方法进行排序，并输出每种排序下的各趟排序结果。 各排序算法输入的无序序列为：26 5 37 1 61 11 59 15 48 19。 实验要求： 一、查找法 1. 顺序查找 首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序 表中进行查找。 2. 折半查找 任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后再改有序表上 使用折半查找算法进对给定值key 的查找。 3. 二叉树查找 任意输入一组数据作为二叉排序树中节点的键值，首先创建一颗二叉排序树，然后再次二叉排序树上实现对一 定k的查找过程。 4. 哈希表查找 任意输入一组数值作为个元素的键值，哈希函数为Hash （key ）=key%11, 用线性探测再散列法解决冲突问题。 二、排序算法 编程实现直接插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行测试。 实验原理： 1. 顺序查找： 在一个已知无（或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以 查找、排序的应用 一、问题描述 对学生的基本信息进行管理。 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能： 1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 二、问题分析 1.定义储存学生信息的储存结构 2.对学生信息进行查询和排序。 3.查询用到两种查询方式：折半查找和顺序查找. 4.排序用到两种方式：插入排序和选择排序。 三、算法设计 (1)定义学生信息存储结构 typedef struct//定义每个记录（数据元素）的结构 { string name;//姓名 string sex;//性别 int number;//学号 float grade1,grade2;//成绩1，成绩2 float score;//总分 }RecordType,RT[MAXSIZE]; (2)查找方法 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令 low=1,high=n,mid= (low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 实验六、七：查找、排序算法的应用 班级 10511 学号 20103051114 姓名高卫娜 一、实验目的 1 掌握查找的不同方法，并能用高级语言实现查找算法。 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法，并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。 二、实验内容 1 创建给定的顺序表。表中共包含八条学生信息，信息如下： 学号姓名班级C++ 数据结构 1 王立03511 85 76 2 张秋03511 78 88 3 刘丽03511 90 79 4 王通03511 7 5 86 5 赵阳03511 60 71 6 李艳03511 58 68 7 钱娜03511 95 89 8 孙胜03511 45 60 2 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。 3 使用二分查找方法，从查找表中查找学号为7和12的学生。如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。（注意：创建静态查找表时必须按学号的从小到大排列！） 4 使用直接插入排序方法，对学生信息中的姓名进行排序。输出排序前和排序后的学生信息表，验证排序结果。 5 使用直接选择排序方法，对学生信息中的C成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。 6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。输出排序前和排序后的学生信息表，验证排序结果。 7 编写一个主函数，将上面函数连在一起，构成一个完整程序。 8 将实验源程序调试并运行。 三、实验结果 源程序代码为： #include 二叉排序树 #include "c1.h" #include "stdio.h" #include "stdlib.h" typedef int KeyType; typedef struct node{ KeyType key; struct node *lchild,*rchild; }BiTNode,*BiTree; void InsertBST(BiTree &bst,KeyType key) { BiTNode *t; if(bst==NULL) { t=(BiTree)malloc(sizeof(BiTNode)); t->key=key; t->lchild=NULL; t->rchild=NULL; bst=t; } else if(key } BiTree SearchBST(BiTree bst,KeyType key) { if(!bst) return NULL; else if(bst->key==key) return bst; else if(key 实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号姓名实验日期实验成绩 一、实验目的 (1)掌握交换排序算法（冒泡排序）的基本思想； (2)掌握交换排序算法（冒泡排序）的实现方法； (3)掌握折半查找算法的基本思想； (4)掌握折半查找算法的实现方法； 二、实验内容 1.对同一组数据分别进行冒泡排序，输出排序结果。要求： 1)设计三种输入数据序列：正序、反序、无序 2)修改程序： a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置， 算法如何改进？ 三、设计与编码 1.本实验用到的理论知识 2.算法设计 3.编码 package sort_search; import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;i 本科学生综合性实验报告 （封面） 项目组长＿郑慧乐＿＿＿学号＿0174280＿＿＿＿ 成员郑慧乐 专业＿物联网＿＿＿班级＿173＿＿＿ 实验项目名称＿＿＿＿＿实验五查找与排序 指导教师及职称＿＿＿黄淑英＿＿＿＿＿＿＿开课学期2018 至＿2019 学年＿第一＿学期上课时间2018 年12 月 3 日 学生实验报告 一、实验目的及要求： 1、目的 1．进一步掌握有序顺序表的折半查找算法。 2．进一步巩固排序的算法，编写对20个及以上的无序数据进行希尔排序和快 速排序的实现程序。 2、内容及要求 1.建立一20个及以上数据的有序顺序表，表中可以仅存放记录的关键字，实现对该有序的折半查找算法，测试数据应充分考虑查找成功和查找不成功两种情况。 2.建立一20个及以上数据的无序顺序表，表中可以仅存放记录的关键字，实现对该无序表进行希尔排序，给出每一趟希尔排序的结果。 3.建立一20个及以上数据的无序顺序表，表中可以仅存放记录的关键字，实现对该无序表进行快速排序，给出每一趟快速排序的结果。 二、仪器用具： DevC++ 三、实验方法与步骤: #include KeyType key; InfoType otherinfo; }RedType; typedef struct { RedType R[MAXSIZE + 1]; int length; }SqList; int Search_Bin (SqList ST, KeyType key) { KeyType low, high, mid; low = 1; high = ST.length; while (low <= high) { mid = (low + high) / 2; if (key == ST.R[mid].key) return mid; else if (key < ST.R[mid].key) high = mid - 1; else low = mid + 1; } return OK; } 实验四：查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 2.编写折半查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct { Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length; 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若key 排序与查找 1．实验目的 掌握在数组上进行排序和查找的方法和算法 理解方法特点，并能灵活运用 加深对排序和查找方法的理解，逐步培养解决实际问题的编程能力 题1 编写程序，使用冒泡排序法对给定数组进行排序。（数组可自定，例如a[]={210,108,65,49,72,88,67,5,19,36, 90,35,1,112,215,6,23,46,51,29,77,19,0,55,27,48,18,22,30,56}） 实验流程图如下： 题2 使用折半查找法对给定的有序数组进行查找。数组可自行定义。 题一的实验结果如下 ： 分析： 冒泡排序既是将数据一个一个比较，将大的不断往后放，知道所有数据都进行了比较，循环结束。 题二实验结果如下： 分析： 折半查找需要数据有序，本实验在递增的情况下进行的，所以对数据需要输入递增序列，然后将数据与最中间的进行比较，如果大，则在后一半进行查找，然后继续依次比较，直至查找到对应数据，如果没有，则显示没有。 附代码： 题1 编写程序，使用冒泡排序法对给定数组进行排序。（数组可自定，例如a[]={210,108,65,49,72,88,67,5,19,36, 90,35,1,112,215,6,23,46,51,29,77,19,0,55,27,48,18,22,30,56}） 题2 使用折半查找法对给定的有序数组进行查找。数组可自行定义。 #include 实验五 查找及排序 实验课程名： 数据结构与算法 一、实验目的及要求 1、掌握查找的不同方法，并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。 3、掌握常用的排序方法，并能用高级语言实现排序算法。 4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。 5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验内容 任务一：顺序表的顺序查找。 有序表的折半查找。 完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。 解答： （1）源代码：#include 数据与结构实验报告 折半查找法、冒泡法与堆排序一实验设计： （1）用折半查找法找到需要查找目标的位置 （2）用冒泡法把输入数据从小到大排列 （3）用堆排序法把输入的数据从小到大排列 二算法设计： 1.冒泡排序与折半查找的共同应用 #include } } } for(i=0;i #include for(i=2;i 第二轮排序和查找算法综合1 行政班：教学班：姓名：学号： 根据课本上的排序算法和查找算法回答1-6题： 1．【加试题】有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24那么该数组的原始顺序不可能 ．．．的是（） A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，7 2.【加试题】对下列数据序列进行冒泡升序排序，排序效率最低的序列（） A.31，29，24，20，15，10 B.10，15，20，24，29，31 C.29，10，31，15，20，24 D.24，29，31，20，15，10 3．【加试题2】数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（） A．69 B．66、69 C．66、76、69 D．56、66、76、69 4.【加试题2】用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34，55”中查找数字13,两种方法都能访问到的数字是（） A.3 B.5 C.8 D.34 5.【加试题2】在有序单词序列“bike，cake，data，easy，feel，great，hive，mark,sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为（） A.feel, data, easy B.great, data, easy C.bike, cake, dada，easy D.feel,cake,data,easy 6.【加试题2】下列有关查找的说法，正确的是（） A．进行对分查找时，被查找的数据必须已按升序排列 B．进行对分查找时，如果查找的数据不存在，则无需输出结果 C．在新华字典中查找某个汉字，最适合使用顺序查找 D．对规模为n的数据进行顺序查找，平均查找次数是21 n 7. 【加试题】实现某排序算法的部分VB程序如下：数组元素a(1)到a(5)的数据依次为“38，70，53，57，30”。经过下列程序“加工”后数组元素a(1)到a(5)的数据应该是（） For i = 1 To 1 For j = 5 To i + 1 Step -1 If a(j) > a(j - 1) Then t = a(j) a(j) = a(j - 1) a(j - 1) = t End If Next j Next i 命题：杜宗飞 A.70，57，38，53，30 B.30, 38，70，53，57 C.70，38，57，53，30 D.30, 38，57，53，70 8.【加试题】有如下程序段： 实验五查找的应用 一、实验目的： 1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。 2、增强上机编程调试能力。 二、问题描述 1.分别利用顺序查找和折半查找方法完成查找。 有序表（3,4,5,7,24,30,42,54,63,72,87,95） 输入示例： 请输入查找元素：52 输出示例： 顺序查找： 第一次比较元素95 第二次比较元素87 …….. 查找成功，i=**/查找失败 折半查找： 第一次比较元素30 第二次比较元素63 ….. 2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查 询。 输入输出示例同题1的要求。 三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明） （1）逻辑结构设计 顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。 （2）存储结构设计 采用顺序存储的结构，开辟一块空间用于存放元素。 （3）存储结构形式说明 分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据 四、算法设计 （1）算法列表（说明各个函数的名称，作用，完成什么操作） 序号 名称 函数表示符 操作说明 1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素 2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素 3 初始化 Init 对顺序表进行初始化，并输入元素 4 树初始化 CreateBST 创建一棵二叉排序树 5 插入 InsertBST 将输入元素插入到二叉排序树中 6 查找 SearchBST 在根指针所指二叉排序树中递归查找关键字 数据元素 （2）各函数间调用关系（画出函数之间调用关系） typedef struct { ElemType *R; int length; }SSTable; typedef struct BSTNode{ Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; typedef struct Elem{ int key; }Elem; typedef struct { int key;//关键字域 }ElemType; 折半查询 一、实验目的 1，掌握排序算法及基本思想及实现的技术；能够根据实际问题特点的要求选择合理的排序方法，理解排序在数据处理中的重要性； 2.学会比较各种排序方法的稳定性分析以及在最好、最坏和平均情况的时间性能分析。 3.掌握顺序查找和折半查找两种查找的算法及实现技术；了解它们各自的优缺点。 4.熟悉各种查找方法的适用范围和条件；掌握顺序查找、折半查找的基本思想及效率分析。 二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows 2.软件：DOS或Windows操作系统+Turbo C; 三、实验要求 1.本次实验较为简单，每个同学独立按时完成，通过实验掌握记录的概念，为以后数据库技术打好基础。 2.如果输入数据较为繁琐，可减低每个班的人数。 3.输入输出数据要有提示，方便用户操作。 四、实验内容 1.现在某个学院有20名同学分属于2个班级（Class1和Class2，每个班有10名同学，每个同学记录包括：班级、学号、姓名、性别、电话号码等信息）。 2.以学号为主关键字，以班级为次关键字，建立一个顺序表，表中的每个数据元素是一个记录，其中的某个域用来存储关键字的值，按关键字的值进行顺序查找。为分析排序方法的稳定性，关键字可用次关键字。#include"stdio.h" #include"malloc.h" #include"string.h" typedef struct {int cla; int num; char name[7]; char sex; long phnum; }stu_hc; typedef struct {stu_hc *elem; int length; int sum; }sqlist_hc; sqlist_hc *initlist_hc() {sqlist_hc *l;int n; l=(sqlist_hc*)malloc(sizeof(sqlist_hc)); if(!l)printf("出错!\n"); printf("输入学生人数:");scanf("%d",&n); l->length=0;l->sum=n; l->elem=(stu_hc*)malloc(n*sizeof(stu_hc)); 每天都在叫嚣自己会什么技术，什么框架，可否意识到你每天都在被这些新名词、新技术所迷惑，.NET、XML等等技术固然诱人，可是如果自己的基础不扎实，就像是在云里雾里行走一样，只能看到眼前，不能看到更远的地方。这些新鲜的技术掩盖了许多底层的原理，要想真正的学习技术还是走下云端，扎扎实实的把基础知识学好，有了这些基础，要掌握那些新技术也就很容易了。 要编写出优秀的代码同样要扎实的基础，如果排序和查找算法学的不好，怎么对程序的性能进行优化？废话不多说，本文要介绍的这些排序算法就是基础中的基础，程序员必知！ 1、直接插入排序 （1）基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排 好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数 也是排好顺序的。如此反复循环，直到全部排好顺序。 （2）实例 2、希尔排序（也称最小增量排序） （1）基本思想：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。 （2）实例： 3、简单选择排序 （1）基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 （2）实例： 4、堆排序 （1）基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足 （hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 （2）实例： 初始序列：46,79,56,38,40,84 建堆： 实验七查找和排序算法的实现 ?实验目的及要求 （1）学生在实验中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。 （2）掌握运用查找和排序解决一些实际应用问题。 二.实验内容： （1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等）算相应的ASL。 （2）编程实现一种内部排序算法（如插入排序、快速排序等）。 三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页） （1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等）算相应的ASL。 程序代码: 折半查找: 头文件: #defi ne EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)v(b)) #defi ne maxle ngth 20 typedef int ElemType; typedef struct{ ElemType key; ElemType other; }card;〃每条记录包含的数据项 typedef struct{ card r[maxle ngth]; int len gth; }SSTable;〃一张表中包含的记录容量 void Create(SSTable & L); int Search(SSTable L,i nt elem); 功能函数： #i nclude"1.h" #i nclude"stdio.h"，并计，并计 void Create(SSTable &L) { printf(" 新的线性表已经创建，请确定元素个数(不超过20) \n"); scanf("%d",&L.length); printf(" 请按递增序列输入具体的相应个数的整数元素(空格隔开) \n"); for(int i=0;i实验8查找与排序算法的实现和应用
查找、排序的应用
实验6 查找和排序 (2)(1)
二叉排序树 折半查找 顺序查找 数据结构
数据结构实验五-查找与排序的实现
实验五 查找与排序
查找与排序实验报告
(完整word版)查找、排序的应用 实验报告
排序与查找
实验五查找及排序讲解
折半查找冒泡排序堆排序
几种常用的查找和排序算法
2018年浙江省选考信息技术查找与排序强化习题一答案
数据结构——查找,顺序查找,折半查找
数据结构折半排序查找
八种排序和三大查找
查找和排序算法的实现(实验七)