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: }

--------------------------------------------------------------------------------
 
--  作者：PrOve
--  發(fā)布時(shí)間：2005-4-6 13:09:06

--  
16.什么是哈希查找?
  哈希查找的本質(zhì)是先將數(shù)據(jù)映射成它的哈希值。哈希查找的核心是構(gòu)造一個(gè)哈希函數(shù)，它將原來直觀、整潔的數(shù)據(jù)映射為看上去似乎是隨機(jī)的一些整數(shù)。
    哈希查找的產(chǎn)生有這樣一種背景——有些數(shù)據(jù)本身是無法排序的(如圖像)，有些數(shù)據(jù)是很難比較的(如圖像)。如果數(shù)據(jù)本身是無法排序的，就不能對(duì)它們進(jìn)行比較查找。如果數(shù)據(jù)是很難比較的，即使采用折半查找，要比較的次數(shù)也是非常多的。因此，哈希查找并不查找數(shù)據(jù)本身，而是先將數(shù)據(jù)映射為一個(gè)整數(shù)(它的哈希值)，并將哈希值相同的數(shù)據(jù)存放在同一個(gè)位置一即以哈希值為索引構(gòu)造一個(gè)數(shù)組。
    在哈希查找的過程中，只需先將要查找的數(shù)據(jù)映射為它的哈希值，然后查找具有這個(gè)哈希值的數(shù)據(jù)，這就大大減少了查找次數(shù)。如果構(gòu)造哈希函數(shù)的參數(shù)經(jīng)過精心設(shè)計(jì)，內(nèi)存空間也足以存放哈希表，查找一個(gè)數(shù)據(jù)元素所需的比較次數(shù)基本上就接近于一次。
    影響哈希查找效率的一個(gè)重要因素是哈希函數(shù)本身。當(dāng)兩個(gè)不同的數(shù)據(jù)元素的哈希值相同時(shí)，就會(huì)發(fā)生沖突。為減少發(fā)生沖突的可能性，哈希函數(shù)應(yīng)該將數(shù)據(jù)盡可能分散地映射到哈希表的每一個(gè)表項(xiàng)中。解決沖突的方法有以下兩種：
    (1) 開放定址法
    如果兩個(gè)數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個(gè)表項(xiàng)。
當(dāng)程序查找哈希表時(shí)，如果沒有在第一個(gè)對(duì)應(yīng)的哈希表項(xiàng)中找到符合查找要求的數(shù)據(jù)元素，程序就會(huì)繼續(xù)往后查找，直到找到一個(gè)符合查找要求的數(shù)據(jù)元素，或者遇到一個(gè)空的表項(xiàng)。
    (2) 鏈地址法
    將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中，在查找哈希表的過程中，當(dāng)查找到這個(gè)鏈表時(shí)，必須采用線性查找方法。
    例是一個(gè)簡單的哈希查找算法程序，你可以將它和本章結(jié)尾的有關(guān)代碼一起編譯連接成一個(gè)可執(zhí)行程序。

    例 一個(gè)簡單的哈希查找算法程序
1: #include<stdlib.h>
2: #include<string.h>
3: #include "list.h"
4: #include "hash.h"
5:
6: #define HASH_SIZE   1024
7:
8: static listnode_t  *hashTable[HASH_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 = hashTable[h]
16:     hashTable[h] = ele;
17: }
18:
19: void print (void)
20: {
21:      int  h;
22:
23:      for (h = 0; h < HASH_SIZE; h++)
24:      {
25:           listnode_t   * lp = hashTalbe[h];
26:
27:           if(lp == NULL)
28:                 continue;
29:            printf("[%d]" , h);
30:            while (lp)
31:            {
32:                  printf("\\t\'%s\'" , lp->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 = hashTable[h];
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: }

--------------------------------------------------------------------------------
 
--  作者：PrOve
--  發(fā)布時(shí)間：2005-4-6 13:10:33

--  
17.什么是宏(macro)?怎樣使用宏?
    宏是一種預(yù)處理指令，它提供了一種機(jī)制，可以用來替換源代碼中的字符串，宏是用“#define"語句定義的，下面是一個(gè)宏定義的例子：
    #define VERSION—STAMP "1．02"

    上例中所定義的這種形式的宏通常被稱為標(biāo)識(shí)符。在上例中，標(biāo)識(shí)符VERSION_STAMP即代表字符串"1．02"——在編譯預(yù)處理時(shí)，源代碼中的每個(gè)VERSION_STAMP標(biāo)識(shí)符都將被字符串“1．02”替換掉。
    以下是另一個(gè)宏定義的例子：
    #define CUBE(x)((x)，(x)*(x))
    上例中定義了一個(gè)名為CUBE的宏，它有一個(gè)參數(shù)x。CUBE宏有自己的宏體，即((x)*(x)*(x))——在編譯預(yù)處理時(shí)，源代碼中的每個(gè)CUBE(x)宏都將被((x)*(x)*(x))替換掉。
    使用宏有以下幾點(diǎn)好處；
    (1)在輸入源代碼時(shí)，可省去許多鍵入操作。    
    (2)因?yàn)楹曛恍瓒x一次，但可以多次使用，所以使用宏能增強(qiáng)程序的易讀性和可靠性。
    (3)使用宏不需要額外的開銷，因?yàn)楹晁淼拇a只在宏出現(xiàn)的地方展開，因此不會(huì)引起程序中的跳轉(zhuǎn)。
    (4)宏的參數(shù)對(duì)類型不敏感，因此你不必考慮將何種數(shù)據(jù)類型傳遞給宏。
    需要注意的是，在宏名和括起參數(shù)的括號(hào)之間絕對(duì)不能有空格。此外，為了避免在翻譯宏時(shí)產(chǎn)生歧義，宏體也應(yīng)該用括號(hào)括起來。例如，象下例中這樣定義CUBE宏是不正確的：
denne CUBE(x)   x * x * x
  對(duì)傳遞給宏的參數(shù)也要小心，例如，一種常見的錯(cuò)誤就是將自增變量傳遞給宏，請(qǐng)看下例：
#include <stdio. h>
#include CUBE(x) (x * x * x)
void main (void);
void main (void)
{
    int x, y;
    x = 5;
    y = CUBE( + +x);
    printfC\'y is %d\\n" . y);
}

    在上例中，y究竟等于多少呢?實(shí)際上，y既不等于125(5的立方)，也不等于336(6* 7*8)，而是等于512。因?yàn)樽兞縳被作為參數(shù)傳遞給宏時(shí)進(jìn)行了自增運(yùn)算，所以上例中的CUBE宏實(shí)際上是按以下形式展開的：
    y = ((++x) * (++x) * (++x))；
    這樣，每次引用x時(shí)，x都要自增，所以你得到的結(jié)果與你預(yù)期的結(jié)果相差很遠(yuǎn)，在上例中，由于x被引用了3次，而且又使用了自增運(yùn)算符，因此，在展開宏的代碼時(shí)，x實(shí)際上為8，你將得到8的立方，而不5的立方。
    上述錯(cuò)誤是比較常見的，作者曾親眼見過有多年C語言編程經(jīng)驗(yàn)的人犯這種錯(cuò)誤。因?yàn)樵诔绦蛑袡z查這種錯(cuò)誤是非常費(fèi)勁的，所以你要給予充分的注意。你最好試一下上面的例子，親眼看一下那個(gè)令人驚訝的結(jié)果值(512)。
    宏也可使用一些特殊的運(yùn)算符，例如字符串化運(yùn)算符“#”和。連接運(yùn)算符“##”。“#”運(yùn)算符能將宏的參數(shù)轉(zhuǎn)換為帶雙引號(hào)的字符串，請(qǐng)看下例：
    define DEBUG_VALUE(v)  printf(#v"is equal to %d．\\n"，v)
    你可以在程序中用DEBUG_VALUE宏檢查變量的值，請(qǐng)看下例:
    int x＝20；
    DEBUG_VALUE(x);
    上述語句將在屏幕上打印"x is equal to 20"。這個(gè)例子說明，宏所使用的“#”運(yùn)算符是一種非常方便的調(diào)試工具。

--------------------------------------------------------------------------------
 
--  作者：PrOve
--  發(fā)布時(shí)間：2005-4-6 13:11:29

--  
18.預(yù)處理程序(preprocessor)有什么作用?    
    C語言預(yù)處理程序的作用是根據(jù)源代碼中的預(yù)處理指令修改你的源代碼。預(yù)處理指令是一種命令語句(如#define)，它指示預(yù)處理程序如何修改源代碼。在對(duì)程序進(jìn)行通常的編譯處理之前，編譯程序會(huì)自動(dòng)運(yùn)行預(yù)處理程序，對(duì)程序進(jìn)行編譯預(yù)處理，這部分工作對(duì)程序員來說是不可見的。
    預(yù)處理程序讀入所有包含的文件以及待編譯的源代碼，然后生成源代碼的預(yù)處理版本。在預(yù)處理版本中，宏和常量標(biāo)識(shí)符已全部被相應(yīng)的代碼和值替換掉了。如果源代碼中包含條件預(yù)處理指令(如#if)，那么預(yù)處理程序?qū)⑾扰袛鄺l件，再相應(yīng)地修改源代碼。
    下面的例子中使用了多種預(yù)處理指令：
# include <stdio. h>
# define TRUE 1
# define FALSE (!TRUE)
# define GREATER (a, b) ((a) > (b) ? (TRUE) : (FALSE))
# define PIG-LATIN FALSE
void main (void);
void main (void)
{
    int x, y;
# if PIG_LATIN
    printf("Easeplay enternay ethay aluevay orfay xnay:") ;
    scanf("%d", &x) ;
    printf("Easeplay enternay ethay aluevay orfay ynay:");
    scanf("%d", &y);
#else
    printf(" Please enter the value for x: ");
    scanf("%d", &x);
    printf("Please enter the value for y: ");
    scanf("%d", &y);
# endif
    if (GREATER(x, y) = = TRUE)
    {
# if PIG- LATIN
    printf("xnay islay eatergray anthay ynay!\\n");
#else
    printf {" x is greater than y! \\n" ) ;
# endif
    }
    else
    {
# if PIG_LATIN
    printf ("xnay islay otnay eatergray anthay ynay!\\n");
#else
    printf ("x is not greater than y!\\n");
# endif
    }
}
   上例通過預(yù)處理指令定義了3個(gè)標(biāo)識(shí)符常量(即TRUE，F(xiàn)ALSE和PIG_LATIN)和一個(gè)宏(即GREATER(a，b))，并使用了一組條件編譯指令。當(dāng)預(yù)處理程序處理上例中的源代碼時(shí)，它首先讀入stdio.h頭文件，并解釋其中的預(yù)處理指令，然后把所有標(biāo)識(shí)符常量和宏用相應(yīng)的值和代碼替換掉，最后判斷PIG_LATIN是否為TRUE，并由此決定是使用拉丁文還是
使用英文。
    如果PIG_LATIN為FALSE，則上例的預(yù)處理版本將如下所示：
/ * Here is where all the include files
would be expanded. * /
void main (void)
{
    int x, y;
    printf("Please enter the value for X: ");
    scanf("%d", &x);
    printf("Please enter the value for y: ");
    scanf("%d", &y),
    if (((x) > (y) ? (1) : (!1)) == 1)
    {
        printf("x is greater than y!\\n");
    }
    else
    {
        printf{"x is not greater than y!\\n");
    }
}

    多數(shù)編譯程序都提供了一個(gè)命令行選項(xiàng)，或者有一個(gè)獨(dú)立的預(yù)處理程序，可以讓你只啟動(dòng)預(yù)處理程序并將源代碼的預(yù)處理版本保存到一個(gè)文件中。你可以用這種方法查看源代碼的預(yù)處理版本，這對(duì)調(diào)試與宏或其它預(yù)處理指令有關(guān)的錯(cuò)誤是比較有用的。

--------------------------------------------------------------------------------
 
--  作者：PrOve
--  發(fā)布時(shí)間：2005-4-6 13:12:04

--