C语言编程要点---第3章.doc

C语言编程要点-第3章 排序与查找（下）34 哪一种查找方法最方便?正如qsort()函数是最方便的排序方法一样，C标准库函数bsearch()是最方便的查找方法。bsearch()函数的原型如下：void *bsearch(const void *key，const void *bur，size_t num，size_t size，in(*comp)(const void*，const void *)；bsearch()函数在一个数据已经排好序的数组中进行折半查找。折半查找也是一种分割处理式的算法。bsearch()函数的查找过程为：首先比较关键字与数组中间的元素，如果两者相等，则查找结束；如果前者比后者小，则要查找的数据必然在数组的前半部，此后只需在数组的前半部中继续进行折半查找，如果前者比后者大，则要查找的数据必然在数组的后半部，此后只需在数组的后半部中继续进行折半查找。例34a给出一个调用bsearch()函数的简单函数。该例所用的comp()函数和例3. 1中qsort()函数所用的完全相同。例34b给出了一个在已排好序的字符串数组中查找一个字符串的折半查找算法程序。该例没有调用bsearch()函数。上述两例都可以和本章结尾的有关代码一起被编译连接成可执行程序。例34a一个使用bsearch()函数的例子1: #include 2:3: static int comp (const void * ele1, const void *ele2)4: 5: return strcmp( * (const char * * ele1,6: * (const char * * )ele2);7: 8:9: const char * search (const char * key, const char * *array,10:size_t num)11: 12: char * * p = bsearch(&ckey, array, num,13: sizeof( *array), comp);14: return p ? *P: NULL;15: 例3.4b 一个折半查找算法程序1: #include 2:3: const char *search(const char * key, cosnt char * *array,4: size_tnum)5: 6: int low = 0;7: int high = num-1;8:9: while (low = high)10: 11: int mid = (low + high) / 2;12: int n = strcmp(key, arraymid);13:14: if (n 0)17: low = mid + 1;18: else19: return arraymid;20: 21: return 0;22: 线性查找也是一种简单的查找方法。尽管在大量数据中进行查找时，线性查找要比bsearch()函数慢，但线性查找还是足以满足许多查找要求的。此外，如果数据未排序或无法随机存取，那么线性查找可能就是唯一可行的查找方法。线性查找的过程为：从数据集的第一个元素开始，依次将关键字和数据集中的每一个元素进行比较，直到找到要找的数据。例3. 4c给出了一个线性查找算法程序，它同样可以和本章结尾的有关代码一起编译连接成一个可执行程序。例34c一个线性查找算法程序1: #include 2:3: const char * search(const char *key, const char *array,4:size_ num)5: 6: int i;7:8: for (i = 0; i num; i+)9: 10: if (strcmp(key, array) = 0)11: return array12: 13: return 0;14: 请参见：3.5. 1哪一种查找方法最快？ 3.5 哪一种查找方法最快？ 折半查找，例如bsearch()函数，要比线性查找快得多，而哈希查找还要快。此外，将数据存放在键树中的键树查找算法也是一种特别快的查找方法不管数据集中有多少数据，键树查找所花费的时间几乎不变。 键树是一种多层数据结构(即树状数据结构)，每层都有N个分支(在下文的例子中有16个分支)。树状数据结构和树状查找所涉及的概念相当多，这里无法一一介绍，你可以从有关数据结构或算法的书籍中了解到更多的内容。 键树的概念可以用哈希表树的建立过程来描述： 假设有一个哈希函数，它将数据映射到一个完整的32位整数上，即它的哈希值是一个32位整数。你可以将这个32位的哈希值看作是8个4位的哈希值连接在一起，并用第一个4位哈希值作为索引，建立一个含16个表项的哈希表。 显然，一个仅含16个表项的哈希表将带来许多冲突，因为许多数据将映射到同一个表项中。如果用第二个4位哈希值作为索引，再建立一层哈希表(每个哈希表同样含16个表项)，并使第一个哈希表中的每一个表项都指向第二层中的一个哈希表，就能减少这种冲突。 在上述过程中，实际上你建立了一个哈希表树。对于一个32位的哈希值，按上述方法你可以建立一个8层哈希表树。 键树就是类似于哈希表树这样的一种数据结构。键树的数据容量与长整数的位数有关，如果在你的计算机中，长整数是32位的，那么键树就相当于一个含232个表项的哈希表。 键树查找综合了折半查找、基数查找和哈希查找的特性。键树查找的哈希查找特性在上文中已经介绍过；键树查找的折半查找特性是键树的每一层都有16个分支，查找数据的过程就是遍历键树的过程；键树查找的基数查找特性是键树的每一层都对应于4位连续的哈希值。 例3. 5是一个键树查找算法程序，你可以将它与本章结尾的有关代码一起编译连接成一个可执行程序。 例35一个键树查找算法程序1: #include2: #include3: #include list.h4: #include hash.h5:6: /*7: * NOTE: This code makes several assumptions about the8: * compiler and machine it is run on. It assumes that9:10: * 1. The value NuLL consists of all 0 bits.11:12: * If not, the calloc() call must be changed to13: * explicitly initialize the pointers allocated.14: *15: * 2. An unsigned and a pointer are the same size.16: *17: * If not, the use of a union might be incorrect, because18: * it is assumed that the least significant hit of the19: * pointer and unsigned members of the union are the20: * same bit.21: *22: * 3. The least significant bit of a valid pointer23: * to an object allocated on the heap is always 0.24: *25: * If not, that bit cant be used as a flag to determine26: * what type of data the,union really holds.27: * /28:29: / * number of bits examined at each level of the trie.* /30: #define TRIE_BITS 431:32: / * number of subtries at each level of the trie * /33: #define TRIE_FANOUT (1 depth) & TRIE_MASK;73: * nxtNode.node =74: eleInsert ( * nxtNode.node,75: ele, h, depth + TRIE_BITS);76:77: /*78: * Since t wasnt an array of tries, it must be a79: * list of elements. If it is empty, just add this80: * element.81: */82: else if (t.list = NULL)83: t.list = ele;84: / *85: * Since the list is not empty, check whether the86: * element belongs on this list or whether you should87: * make several lists in an array of subtries.88: * /89: else if (h = hash(t.list-u.str)90: 91: ele-next = t.list;92: t.list = ele;93: 94: else95: 96: /*97: * Youre making the list into an array or98: * subtries. Save the current list, replace99: * this entry with an array of TRIE-FANOUT100: * subtries, and insert both the element and101 * the list in the subtries.102 * /103: listnode_t *lp = t.list;104:105: /*106: * Calling caU0e() rather than malloc ()107: * ensures that the elements are initialized108: * to NULL.109: * /110: t.node = (trie_t *) calloc(TRIE_FANOUT,111: sizeof (trie_t) )112: tmnum | =1;113: t = eleInsert(t, lp, hash(lp-u, str),114: depth);115: t = elelnsert(t, ele, h, depth);116: 117: return t;118: 119:120: / *121: * Finds an element in a trie and returns the resulting122: * string, or NULL. For internal use by search() only.123: * /124: static const char * eleSearch(trie_t t, const char * string,125: unsigned h, int depth)126: 127: / *128: * If the trie is an array of subtries, look for the129: * element in the proper subtree.130: * /131: if (t.num & 1)132: 133: trie_t nxtNode = t;134: nxtNode.num* = 1;135, nxtNode.node + = (h depth) & TRIE_MASK;136: return eleSearch ( * nxtNode.node,137: string, h, depth + TRIE_BITS);138: 139: / *140: * Otherwise, the trie is a list. Perform a linear141: * search for the desired element.142: * /143: else144: 145: listnode_t *lp = t.list;146:147: while (lp)148: 149: if stremp (lp-u.str, string) = 0)150: return lp-u.str;151: lp = lp- next;152: 153: 154: return NULL;155: 156:157: / * Test function to print the structure of a trie * /158: void triePrint (trie_t t, int depth)159: 160: if (t.num & 1)161: 162: int i;163: trie_t nxtNode = t;164: nxtNode, hum &= 1;165: if (depth)166: printf(n );167: for (i = 0; i u.str);181: lp = lp -next;182: 183: putchar (n);184: 185: 186:187: static trie_t t;188:189: void insert(const char *s)190: 191: t = elelnsert(t, newNode(void *) s), hash(s), 0);192: 193:194: void print(void)195: 196: triePrint (t, 0);197: 198:199: const char * search(const char * s)200: 201: return eleSearch(t, s, hash(s), 0);202: 请参见： 34 哪一种查找方法最方便? 36 什么是哈希查找? 37 怎样查找链表中的数据? 3.6. 1什么是哈希查找? 36 什么是哈希查找?哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。 哈希查找的产生有这样一种背景有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像)。如果数据本身是无法排序的，就不能对它们进行比较查找。如果数据是很难比较的，即使采用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。 在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。如果构造哈希函数的参数经过精心设计，内存空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。 影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种： (1) 开放定址法 如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。 (2) 链地址法 将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。 例3. 6是一个简单的哈希查找算法程序，你可以将它和本章结尾的有关代码一起编译连接成一个可执行程序。 例36一个简单的哈希查找算法程序1: #include2: #include3: #include list.h4: #include hash.h5:6: #define HASH_SIZE 10247:8: static listnode_t *hashTableHASH_SIZE;9:10: void insert(const char * s)11: 12: listnode_t *ele = newNode(void * ) s)13: unsigned int h = hash(s) % HASH_SIZE;14:15: ele-next = hashTableh16: hashTableh = ele;17: 18:19: void print (void)20: 21: int h;22:23: for (h = 0; h u.str)33: lp = ip-next;34: 35: putchar (n);36: 37: 38:39: const char *search(const char *s)40: 39: unsigned int h = hash(s) % HASH_SIZE;42: listnode_t * lp = hashTableh;43:44: while (lp)45: 46: if (! strcmp (s, lp-u.str)47: return lp-u.str;48: lp = lp-next;49: 50: return NULL;51: 请参见： 3. 4 哪一种查找方法最方便? 35 哪一种查找方法最快? 38 怎样查找链表中的数据? 3.7. 1怎样对链表进行排序? 37 怎样对链表进行排序? 当对链表进行排序时，32中介绍的归并排序和基数排序(其代码分别见例32b和32c)都是较好的排序方法。 请参见： 3. 1 哪一种排序方法最方便? 3. 2 哪一种排序方法最快? 3. 3 当要排序的数据集因太大而无法装入内存时，应怎样排序? 3.8. 1怎样查找链表中的数据?3. 8 怎样查找链表中的数据? 当查找链表中的数据时，只能采用线性查找方法，因为链表元素只能被顺序存取。在有些情况下，你可以将链表中的数据取出并存储到另外一种数据结构中，这样可以提高查找的效率。 公用代码 本章前文中的每一个例子都可以和下文中的有关代码一起编译连接成一个可执行程序。在本章开始部分对“排序和查找的性能”的介绍中，列出了这些可执行程序针对同一个数据集的运行结果。 例3. 9是一个工程文件，通过一个make工具和该文件你可以编译连接本章所提到的每一个可执行程序。在例39中，每一个非空行都以一个例子的名称开始，其后是一个冒号和该例所需的源文件。具体的编译命令与你所用的编译程序的版本和编译选项(如存储模式)有关。如果你所使用的make工具不接受例3. 9中的格式，或者你没有make工具，你同样可以参考例39中的内容来编译连接所需的可执行程序。 例39之后列出前文一些例子中所需的主程序的源文件和链表代码。程序driver1.c(见例3. 9a)将其所有的命令行参数作为字符串进行排序，并打印排序结果，具体的排序算法由与它一起编译连接的算法程序决定。程序driver2.c(见例39b)先生成一个包含前10，000个质数的表，然后在该表中查找命令行参数(为数字)。 例37和例38中的算法程序并不是在一个数组中查找数据元素，因此它们的主程序是程序driver3c(见例39c)。程序driver3c先读入若干行输入的数据，直到文件结束，并打印整个键树或哈希表，然后在键树或哈希表中查找命令行参数，并打印查找结果。例3. 9编译连接本章程序的工程文件 3_1： 3_1c driver1c 3_2a： 3_2ac driver1C 3_2b： 3_2bc 1istc dyiver1C 3_2c: 3_2Cc 1istc driver1C 3_3： 3_3c 3_1c 3_4： 3_4c 3_1c dyiver2c 3_5： 3_5.c 3_1c driver2c 3_6： 3_6c 3_1c drivey2c 3_7： 3_7c 1istc hashc driver3c 3_8： 3_8c listc hashc driver3c 例39a本章所有排序算法程序(外部排序除外)的主程序driver1c#include extern void sortStrings(const char * * )/ * Sorts its arguments and prints them, one per line * /intmain(int argc, const char *argv) int i; sortStrings(argv + 1); for (i =1; i argc; i+); puts(argv); return 0; 例3. 9b采用bsearch()函数的查找算法程序及折半查找和线性查找算法程序的主程序driver2.c#include #include extern const char *search(const char * , const char * * , size-t);static int size;static const char * * array;static void initArray(int limit) char buf1000; array = (const char * * ) calloc(limit, sizeof(char * ); for (size = O; size limit; size+) if (gets (buf) = NULL) break; arraysize = strdup(buf); sortStrings(array.size);int main(int argc, char * * argv) int i; int limit; if(argc 2) fprintf(stderr,usage: %s size lookupsn, argv0); exit (1); limit = atoi (argv1); initArray (limit); for (i = 2 ; i %sn, argv, s); else printf( %s not foundn, argv); return 0;例3. 9c键树查找和哈希查找算法程序的主程序driver3c#include #include extern void insert(const char * )extern void print (void)extern const char *search(const char * )intmain(iht argc, char * argv) int i; int limit; char buf1000; if (argc 2) fprintf(stderr, usage: %s size lookupsn, argvO); exit(1); limit = atoi(argv1); for (i = 0; i limit; i+) if (gets (buf = NULL) break; insert (strdup (buf); . - print( ) for(i = 2; i %sn, argv, p); else printf( %s not foundn, argv); return 0; 例39d 提供一个简单的链表类型的头文件listh /* * Generic linked list node structure-can hold either * a character string or another Ust as data */typedef struct lisnode_s struct listnode_s * next union void * data; struct list_s * lists; const char * str; u; listnode_t;typedef struct list_s listnode_t * head; listnode_t * tail; list_t;extern void appendNode(list_t * , listnode_t * );extern listnode_t * removeHead(list_t * );extern void concatList(list_t * , list_t * );extern list_t * copyOf(list_t);extern listnode_t * newNode(void * );extern list_t * newList(); 例39e 提供一个简单的链表类型的源文件list.c#include #include list. h/* Appends a listnode_t to a list_t. * /void appendNode (list_t * list, listnode_t * node) node-next = NULL; if (list-head) list-tail-next = node; list-tail = node; else list-head = list-tail = node;/* Removes the first node from a list_t and returns it. */listnode