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
--  發布時間：2005-4-6 13:09:06

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

    例 一個簡單的哈希查找算法程序
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
--  發布時間：2005-4-6 13:10:33

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

    上例中所定義的這種形式的宏通常被稱為標識符。在上例中，標識符VERSION_STAMP即代表字符串"1．02"——在編譯預處理時，源代碼中的每個VERSION_STAMP標識符都將被字符串“1．02”替換掉。
    以下是另一個宏定義的例子：
    #define CUBE(x)((x)，(x)*(x))
    上例中定義了一個名為CUBE的宏，它有一個參數x。CUBE宏有自己的宏體，即((x)*(x)*(x))——在編譯預處理時，源代碼中的每個CUBE(x)宏都將被((x)*(x)*(x))替換掉。
    使用宏有以下幾點好處；
    (1)在輸入源代碼時，可省去許多鍵入操作。    
    (2)因為宏只需定義一次，但可以多次使用，所以使用宏能增強程序的易讀性和可靠性。
    (3)使用宏不需要額外的開銷，因為宏所代表的代碼只在宏出現的地方展開，因此不會引起程序中的跳轉。
    (4)宏的參數對類型不敏感，因此你不必考慮將何種數據類型傳遞給宏。
    需要注意的是，在宏名和括起參數的括號之間絕對不能有空格。此外，為了避免在翻譯宏時產生歧義，宏體也應該用括號括起來。例如，象下例中這樣定義CUBE宏是不正確的：
denne CUBE(x)   x * x * x
  對傳遞給宏的參數也要小心，例如，一種常見的錯誤就是將自增變量傳遞給宏，請看下例：
#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究竟等于多少呢?實際上，y既不等于125(5的立方)，也不等于336(6* 7*8)，而是等于512。因為變量x被作為參數傳遞給宏時進行了自增運算，所以上例中的CUBE宏實際上是按以下形式展開的：
    y = ((++x) * (++x) * (++x))；
    這樣，每次引用x時，x都要自增，所以你得到的結果與你預期的結果相差很遠，在上例中，由于x被引用了3次，而且又使用了自增運算符，因此，在展開宏的代碼時，x實際上為8，你將得到8的立方，而不5的立方。
    上述錯誤是比較常見的，作者曾親眼見過有多年C語言編程經驗的人犯這種錯誤。因為在程序中檢查這種錯誤是非常費勁的，所以你要給予充分的注意。你最好試一下上面的例子，親眼看一下那個令人驚訝的結果值(512)。
    宏也可使用一些特殊的運算符，例如字符串化運算符“#”和。連接運算符“##”?！?”運算符能將宏的參數轉換為帶雙引號的字符串，請看下例：
    define DEBUG_VALUE(v)  printf(#v"is equal to %d．\\n"，v)
    你可以在程序中用DEBUG_VALUE宏檢查變量的值，請看下例:
    int x＝20；
    DEBUG_VALUE(x);
    上述語句將在屏幕上打印"x is equal to 20"。這個例子說明，宏所使用的“#”運算符是一種非常方便的調試工具。

--------------------------------------------------------------------------------
 
--  作者：PrOve
--  發布時間：2005-4-6 13:11:29

--  
18.預處理程序(preprocessor)有什么作用?    
    C語言預處理程序的作用是根據源代碼中的預處理指令修改你的源代碼。預處理指令是一種命令語句(如#define)，它指示預處理程序如何修改源代碼。在對程序進行通常的編譯處理之前，編譯程序會自動運行預處理程序，對程序進行編譯預處理，這部分工作對程序員來說是不可見的。
    預處理程序讀入所有包含的文件以及待編譯的源代碼，然后生成源代碼的預處理版本。在預處理版本中，宏和常量標識符已全部被相應的代碼和值替換掉了。如果源代碼中包含條件預處理指令(如#if)，那么預處理程序將先判斷條件，再相應地修改源代碼。
    下面的例子中使用了多種預處理指令：
# 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
    }
}
   上例通過預處理指令定義了3個標識符常量(即TRUE，FALSE和PIG_LATIN)和一個宏(即GREATER(a，b))，并使用了一組條件編譯指令。當預處理程序處理上例中的源代碼時，它首先讀入stdio.h頭文件，并解釋其中的預處理指令，然后把所有標識符常量和宏用相應的值和代碼替換掉，最后判斷PIG_LATIN是否為TRUE，并由此決定是使用拉丁文還是
使用英文。
    如果PIG_LATIN為FALSE，則上例的預處理版本將如下所示：
/ * 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");
    }
}

    多數編譯程序都提供了一個命令行選項，或者有一個獨立的預處理程序，可以讓你只啟動預處理程序并將源代碼的預處理版本保存到一個文件中。你可以用這種方法查看源代碼的預處理版本，這對調試與宏或其它預處理指令有關的錯誤是比較有用的。

--------------------------------------------------------------------------------
 
--  作者：PrOve
--  發布時間：2005-4-6 13:12:04

--