第三章 算法
前言：許多人對算法的看法是截然不同的，我之前提到過了。不過，我要說的還是那句話：算法體現編程思想，編程思想指引算法。
同時，有許多人認為簡單算法都太簡單了，應當去學習一些更為實用的復雜算法。不過，許多復雜算法都是從簡單算法演繹而來的，這裡就不一一舉例了。而且，算法千千萬萬。更為重要的是從算法中體會編程的思想。
4.1 簡單問題算法
PS：接下來是一些入門問題，簡單到都沒有具體算法可言。但這些問題是我們當初對算法的入門。如果不喜歡，可以跳過。
實例111 任意次方後的最後三位
問題：編程實現一個整數任意次方後的最後三位數，即求xy的最後三位數，x和y的值由鍵盤輸入。
邏輯：無論是剛接觸編程還是現在，看到這個問題，你的腦海裡都不會出現一個有名有姓的具體算法。但是，你卻能夠找到解決問題的邏輯步驟。而這個邏輯步驟的清晰指令就是算法。其次，這種情況不僅僅面對這題。當以後遇到諸多問題時都是這樣，了解問題->分析問題->建立模型->尋找算法->編寫程序->解決問題。最後，這題還體現了我在之前篇章強調的一點，編程解決問題的同時，還可以依靠數學的思想簡化問題及程序。這題如果直接計算xy，也許還沒等我們提取xy最後三位，xy的值就越界了。所以在每一次循環計算z*x之後，取z*x的最後三位作為z的值。其實，如果x的值大於999,也可以取x的後三位為新的x，結果不變。
代碼：
1 #include<stdio.h>
2 main()
3 {
4 int i, x, y, z = 1;
5 printf("please input two numbers x and y(x^y):\n");
6 scanf("%d%d", &x, &y);
7 //輸入底數和冪數
8 for (i = 1; i <= y; i++)
9 z = z * x % 1000;
10 //計算一個數任意次方的後三位
11 printf("the last 3 digits of %d^%d is:%d\n", x, y, z);
12 //輸出最終結果
13 }
反思&總結：一個簡單的問題，往往也可以從中分析到許多重要結論。就如同接下來許多算法，雖然簡單、基礎，卻也是日後復雜算法的基礎。
4.2 排序算法
PS:排序是數據處理中的一種重要算法。其中由於待排序的記錄數量不同，使得排序過程中涉及的存儲器不同，可將排序算法分為兩大類：內部排序（待排序記錄存放在RAM）與外部排序（排序過程中涉及ROM）。排序算法眾多，最好的算法往往是與需求相關的。不過從使用上來說，頻率最高的是歸並排序，快速排序，堆排序（因為當n較大時，時間復雜度O（nlog2n）的上述三種算法最為迅捷）。
PS：從網絡上找到的一張圖。
實例119 直接插入排序
問題：通過直接插入排序，編程實現排序。
邏輯：插入排序是將一個數據插入到已排序的有序序列中，使得整個序列在插入了該數據後仍然有序（默認單個數據的序列為有序序列）。插入排序中較為簡單的一種方法便是直接插入排序，它插入的位置的確定是通過將待插入的數據與有序區中的個數據自左向右依次比較其關鍵字值大小來確定的。
代碼：
1 #include <stdio.h>
2 void insort(int s[], int n)
3 /*自定義函數isort*/
4 {
5 int i, j;
6 for (i = 2; i <= n; i++)
7 /*數組下標從2開始，0做監視哨，1一個數據無可比性*/
8 {
9 s[0] = s[i];
10 /*給監視哨賦值*/
11 j = i - 1;
12 /*確定要進行比較的元素的最右邊位置*/
13 while (s[0] < s[j])
14 {
15 s[j + 1] = s[j];
16 /*數據右移*/
17 j--;
18 /*移向左邊一個未比較的數*/
19 }
20 s[j + 1] = s[0];
21 /*在確定的位置插入s[i]*/
22 }
23 }
24 main()
25 {
26 int a[11], i;
27 /*定義數組及變量為基本整型*/
28 printf("please input number:\n");
29 for (i = 1; i <= 10; i++)
30 scanf("%d", &a[i]);
31 /*接收從鍵盤中輸入的10個數據到數組a中*/
32 printf("the original order:\n");
33 for (i = 1; i < 11; i++)
34 printf("%5d", a[i]);
35 /*將為排序前的順序輸出*/
36 insort(a, 10);
37 /*調用自定義函數isort()*/
38 printf("\nthe sorted numbers:\n");
39 for (i = 1; i < 11; i++)
40 printf("%5d", a[i]);
41 /*將排序後的數組輸出*/
42 printf("\n");
43 }
PS：設立監視哨是為了避免數據在後移時丟失。
反思：直接插入算法應該是大多數人接觸的第一個算法了。但是，有多少人自己將這個算法進一步優化呢？
實例120 希爾排序
問題：通過希爾排序，編程實現排序。
邏輯：希爾排序是在直接插入排序的基礎上進行了改進。將要排序的序列按固定增量d分成若干組，即將等距離者（相距d的數據）劃分在同一組中，再在組內進行直接插入排序。然後減小增量d，再在新劃分的組內進行直接插入排序。重復上述操作，直至增量d減小到1（即所有數據都放在了同一組內進行直接插入排序）。
代碼：
1 #include <stdio.h>
2 void shsort(int s[], int n)
3 /*自定義函數shsort*/
4 {
5 int i, j, d;
6 d = n / 2;
7 /*確定固定增量值*/
8 while (d >= 1)
9 {
10 for (i = d + 1; i <= n; i++)
11 /*數組下標從d+1開始進行直接插入排序*/
12 {
13 s[0] = s[i];
14 /*設置監視哨*/
15 j = i - d;
16 /*確定要進行比較的元素的最右邊位置*/
17 while ((j > 0) && (s[0] < s[j]))
18 {
19 s[j + d] = s[j];
20 /*數據右移*/
21 j = j - d;
22 /*向左移d個位置*/
23 }
24 s[j + d] = s[0];
25 /*在確定的位置插入s[i]*/
26 }
27 d = d / 2;
28 /*增量變為原來的一半*/
29 }
30 }
31 main()
32 {
33 int a[11], i;
34 /*定義數組及變量為基本整型*/
35 printf("please input numbers:\n");
36 for (i = 1; i <= 10; i++)
37 scanf("%d", &a[i]);
38 /*從鍵盤中輸入10個數據*/
39 shsort(a, 10);
40 /*調用shsort()函數*/
41 printf("the sorted numbers:\n");
42 for (i = 1; i <= 10; i++)
43 printf("%5d", a[i]);
44 /*將排好序的數組輸出*/
45 }
反思：其實希爾排序就是一個分組排序。通過比較固定距離（稱為增量）的數據，使得在數據的一次移動時可能跨過多個元素，則在一次數據比較就可能消除多個數據交換。而這就是希爾排序較直接插入排序的美麗之處。
實例120.5.1 簡單選擇排序
問題：通過簡單選擇排序，編程實現排序。
邏輯：從待排序區間中找出關鍵字值最小（/最大）的數據（選擇），將其與待排序區間第一個數據a[0]交換（默認本身可以與本身交換）.將其中再從剩余的待排序區間（a[1]-a[n])重復上述操作，直至最後一個數據完成交換。
代碼：
1 #include <stdio.h>
2 main()
3 {
4 int i, j, t, a[11];
5 /*定義變量及數組為基本整型*/
6 printf("please input 10 numbers:\n");
7 for (i = 1; i < 11; i++)
8 scanf("%d", &a[i]);
9 /*從鍵盤中輸入要排序的10個數字*/
10 for (i = 1; i <= 9; i++)
11 for (j = i + 1; j <= 10; j++)
12 if (a[i] > a[j])
13 /*如果後一個數比前一個數大則利用中間變量t實現倆值互換*/
14 {
15 t = a[i];
16 a[i] = a[j];
17 a[j] = t;
18 }
19 printf("the sorted numbers:\n");
20 for (i = 1; i <= 10; i++)
21 printf("%5d", a[i]);
22 /*將排好序的數組輸出*/
23 }
反思：簡單選擇排序存在其改進算法——二元選擇排序，簡單選擇排序每次循環都只能確定一個數據（關鍵字值最大/最小）的定位。那麼在每次循環同時確定關鍵字值最大和關鍵字值最小的數據，那麼就可以在n/2次循環後完成排序。
實例120.5.2 堆排序
問題：通過堆排序，編程實現排序。
邏輯：堆排序是一種樹形選擇排序，是對直接選擇算法更為徹底的改進。堆排序中的堆指代的就是完全二叉樹。堆又分為：大根堆和小根堆。大根堆要求完全二叉樹中的每個節點的值都不大於其父節點的值。根據定義，大根堆的堆頂一定是關鍵字值最大的。同理，可理解小堆根的定義與堆頂關鍵字值最小。
（圖片選自網絡資源）
代碼：（經過考慮，還是選了蘭亭風雨的代碼，比較易於理解）
1 #include<stdio.h>
2 #include<stdlib.h>
3 /* arr[start+1...end]滿足最大堆的定義， 將arr[start]加入到最大堆arr[start+1...end]中， 調整arr[start]的位置，使arr[start...end]也成為最大堆 注：由於數組從0開始計算序號
4
5 ，也就是二叉堆的根節點序號為0， 因此序號為i的左右子節點的序號分別為2i+1和2i+2 */
6 void HeapAdjustDown(int *arr,int start,int end)
7 {
8 int temp=arr[start];
9 //保存當前節點
10 int i=2*start+1;
11 //該節點的左孩子在數組中的位置序號
12 while(i<=end)
13 {
14 //找出左右孩子中最大的那個
15 if(i+1<=end && arr[i+1]>arr[i])
16 i++;
17 //如果符合堆的定義，則不用調整位置
18 if(arr[i]<=temp)
19 break;
20 //最大的子節點向上移動，替換掉其父節點
21 arr[start]=arr[i];
22 start=i;
23 i=2*start+1;
24 }
25 arr[start]=temp;
26 }
27 /* 堆排序後的順序為從小到大 因此需要建立最大堆 */
28 void Heap_Sort(int *arr,int len)
29 {
30 int i;
31 //把數組建成為最大堆
32 //第一個非葉子節點的位置序號為(len-1)/2 for(i=(len-1)/2;i>=0;i--)
33 for(i=(len-1)/2;i>=0;i--)
34 HeapAdjustDown(arr,i,len-1);
35 //進行堆排序 for(i=len-1;i>0;i--)
36 for(i=len-1;i>0;i--)
37 {
38 //堆頂元素和最後一個元素交換位置，
39 //這樣最後的一個位置保存的是最大的數，
40 //每次循環依次將次大的數值在放進其前面一個位置，
41 //這樣得到的順序就是從小到大
42 int temp=arr[i];
43 arr[i]=arr[0];
44 arr[0]=temp;
45 //將arr[0...i-1]重新調整為最大堆
46 HeapAdjustDown(arr,0,i-1);
47 }
48 }
49 int main()
50 {
51 int num;
52 printf("請輸入排序的元素的個數：");
53 scanf("%d",&num);
54 int i;
55 int *arr = (int *)malloc(num*sizeof(int));
56 printf("請依次輸入這%d個元素（必須為整數）：",num);
57 for(i=0;i<num;i++)
58 scanf("%d",arr+i);
59 printf("堆排序後的順序：");
60 Heap_Sort(arr,num);
61 for(i=0;i<num;i++)
62 printf("%d ",arr[i]);
63 printf("\n");
64 free(arr);
65 arr = 0;
66 return 0;
67 }
反思：由於開始建立初始堆時比較次數較多，故不適合數據較少的排序。
實例121 冒泡排序
問題：通過冒泡排序，編程實現排序。
邏輯：冒泡排序可以說是直接排序後遇到的最早的排序方法，同時也是許多C語言入門考試的重點。對n個數據進行冒泡排序，那麼就要進行n-1趟比較（PS：在第j趟比較中要進行n-j次兩兩比較）。每次通過比較相鄰的兩個數據，將關鍵字值較小的上升（下降），將關鍵字值較大的下降（上升）。由於這樣的模式就像是水中的泡泡在上升，故命名為冒泡排序。
代碼：
1 #include <stdio.h>
2 main()
3 {
4 int i, j, t, a[11];
5 /*定義變量及數組為基本整型*/
6 printf("please input 10 numbers:\n");
7 for (i = 1; i < 11; i++)
8 scanf("%d", &a[i]);
9 /*從鍵盤中輸入10個數*/
10 for (i = 1; i < 10; i++)
11 /*變量i代表比較的趟數*/
12 for (j = 1; j < 11-i; j++)
13 /*變量j代表每趟兩兩比較的次數*/
14 if (a[j] > a[j + 1])
15 {
16 t = a[j];
17 /*利用中間變量實現倆值互換*/
18 a[j] = a[j + 1];
19 a[j + 1] = t;
20 }
21 printf("the sorted numbers:\n");
22 for (i = 1; i <= 10; i++)
23 printf("%5d", a[i]);
24 /*將冒泡排序後的順序輸出*/
25 }
反思：冒泡排序算法是一個看到名字就可以想象到其原理的一個算法。所以是很好理解、記憶的。
實例122 快速排序
問題：通過快速排序，編程實現排序
邏輯：快速排序是冒泡排序的一種改進。主要的算法思想是在待排序的n個數據中去第一個數據作為基准值，將所有的數據分為3組，使得第一組中各數據均小於或等於基准值，第二組便是做基准值的數據，第三組中個數據均大於或等於基准值。這就實現了第一趟分割，然後對第一組和第三組分別重復上述方法，以此類推，直到每組中只有一個數據為止。
代碼：
1 #include <stdio.h>
2 void qusort(int s[], int start, int end)
3 /*自定義函數qusort()*/
4 {
5 int i, j;
6 /*定義變量為基本整型*/
7 i = start;
8 /*將每組首個元素賦給i*/
9 j = end;
10 /*將每組末尾元素賦給j*/
11 s[0] = s[start];
12 /*設置基准值*/
13 while (i < j)
14 {
15 while (i < j && s[0] < s[j])
16 j--;
17 /*位置左移*/
18 if (i < j)
19 {
20 s[i] = s[j];
21 /*將s[j]放到s[i]的位置上*/
22 i++;
23 /*位置右移*/
24 }
25 while (i < j && s[i] <= s[0])
26 i++;
27 /*位置右移*/
28 if (i < j)
29 {
30 s[j] = s[i];
31 /*將大於基准值的s[j]放到s[i]位置*/
32 j--;
33 /*位置右移*/
34 }
35 }
36 s[i] = s[0];
37 /*將基准值放入指定位置*/
38 if (start < i)
39 qusort(s, start, j - 1);
40 /*對分割出的部分遞歸調用函數qusort()*/
41 if (i < end)
42 qusort(s, j + 1, end);
43 }
44 main()
45 {
46 int a[11], i;
47 /*定義數組及變量為基本整型*/
48 printf("please input numbers:\n");
49 for (i = 1; i <= 10; i++)
50 scanf("%d", &a[i]);
51 /*從鍵盤中輸入10個要進行排序的數*/
52 qusort(a, 1, 10);
53 /*調用qusort()函數進行排序*/
54 printf("the sorted numbers:\n");
55 for (i = 1; i <= 10; i++)
56 printf("%5d", a[i]);
57 /*輸出排好序的數組*/
58 }
反思：快速排序與希爾排序都采用了分組排序來優化已有的排序方法。其實對算法及其他許多方面而言，多線操作有著許多優勢。只是這可能在一定程度上，人們大腦不習慣，從而導致人們忽視計算機在這方面的優勢。就好像許多人在研究人工智能，我並不贊同一味地追求讓計算機和人類大腦一樣思考，工作。宇宙中的每一件東西都有著其獨特的魅力，人類只是宇宙的一員，並沒有超脫其上。那麼為什麼一切都以人類的視角去考慮問題呢？
實例124 歸並排序
問題：通過歸並排序，編程實現排序。
邏輯：歸並是將兩個或者多個有序記錄序列合並成一個有序序列。歸並方法有多種，一次對兩個有序記錄序列進行歸並，成為兩路歸並排序，也有三路歸並排序及多路歸並排序。不過，這次代碼采用的是兩路歸並排序。其實學會兩路，多路也就會了。
代碼：
1 #include <stdio.h>
2 void merge(int r[], int s[], int x1, int x2, int x3)
3 /*實現一次歸並排序函數*/
4 {
5 int i, j, k;
6 i = x1;
7 /*第一部分的開始位置*/
8 j = x2 + 1;
9 /*第二部分的開始位置*/
10 k = x1;
11 while ((i <= x2) && (j <= x3))
12 /*當i和j都在兩個要合並的部分中*/
13 if (r[i] <= r[j])
14 /*篩選兩部分中較小的元素放到數組s中*/
15 {
16 s[k] = r[i];
17 i++;
18 k++;
19 }
20 else
21 {
22 s[k] = r[j];
23 j++;
24 k++;
25 }
26 while (i <= x2)
27 /*將x1~x2范圍內的未比較的數順次加到數組r中*/
28 s[k++] = r[i++];
29 while (j <= x3)
30 /*將x2+1~x3范圍內的未比較的數順次加到數組r中*/
31 s[k++] = r[j++];
32 }
33 void merge_sort(int r[], int s[], int m, int n)
34 {
35 int p;
36 int t[20];
37 if (m == n)
38 s[m] = r[m];
39 else
40 {
41 p = (m + n) / 2;
42 merge_sort(r, t, m, p);
43 /*遞歸調用merge_sort函數將r[m]~r[p]歸並成有序的t[m]~t[p]*/
44 merge_sort(r, t, p + 1, n);
45 /*遞歸調用merge_sort函數將r[p+1]~r[n]歸並成有序的t[p+1]~t[n]*/
46 merge(t, s, m, p, n);
47 /*調用函數將前兩部分歸並到s[m]~s[n]*/
48 }
49 }
50 main()
51 {
52 int a[11];
53 int i;
54 printf("please input 10 numbers:\n");
55 for (i = 1; i <= 10; i++)
56 scanf("%d", &a[i]);
57 /*從鍵盤中輸入10個數*/
58 merge_sort(a, a, 1, 10);
59 /*調用merge_sort函數進行歸並排序*/
60 printf("the sorted numbers:\n");
61 for (i = 1; i <= 10; i++)
62 printf("%5d", a[i]);
63 /*將排序後的結構輸出*/
64 }
反思：其實，就我感覺，歸並排序並不是指一種排序方法。而是對多個排序方法的一種綜合體現。
實例124.50 基數排序
問題：通過基數排序，編程實現排序。
邏輯：基數排序屬於分配式排序，是透過關鍵字值的各位鍵值咨詢來排序。這種排序方法說實話解釋麻煩，但通過例子一眼就懂。
例子：
（圖片選自網絡資源）
代碼：（此處略過，主要這種排序難點只在於理解。有了上面的例子圖片，就十分簡單了。提取各數位值的方法之前就學過了。）
反思：說實話，當我第一次看到這個算法時，我第一反應是編碼。這個算法最精彩的地方是它從另外一個角度向大家展示了排序的方法。這個算法可以說另辟蹊徑。
總結：排序算法只介紹這些常用的八種基礎算法。雖然沒有囊括所有的算法，但這八種算法也展現了大部分排序算法的思路。可以多多體會。
4.3 查找算法
PS:查找算法時數據處理中使用較為頻繁的一種操作了。當數據量較大時，一個優秀的查找算法就可以帶來驚人的效益了。
PS:常見查找算法分為四類：順序查找、二分查找、分塊查找、哈希（散列）查找。
實例125 順序查找
問題：通過順序查找，編程完成數據查找
邏輯：由於順序查找最為符合多數人查找的邏輯，所以較為簡單，故順序查找一般是大家最早接觸的查找算法。說白了，就是開著循環，遍歷所有數據，比對著每一個遍歷到的數據，直到找到需要的數據。
代碼：
1 #include <stdio.h>
2 void search(int key, int a[], int n)
3 /*自定義函數search*/
4 {
5 int i, count = 0, count1 = 0;
6 for (i = 0; i < n; i++)
7 {
8 count++;
9 /*count記錄查找次數*/
10 if (a[i] == key)
11 /*判斷要查找的關鍵字與數組中的元素是否相等*/
12 {
13 printf("search %d times a[%d]=%d\n", count, i, key);
14 /*輸出查找次數及在數組中的位置*/
15 count1++;
16 /*count1記錄查找成功次數*/
17 }
18 }
19 if (count1 == 0)
20 /*判斷是否查找到h*/
21 printf("no found!");
22 /*如果未查找到輸出no found*/
23 }
24 main()
25 {
26 int n, key, a[100], i;
27 printf("please input the length of array:\n");
28 scanf("%d", &n);
29 /*輸入要輸入的元素個數*/
30 printf("please input element:\n");
31 for (i = 0; i < n; i++)
32 scanf("%d", &a[i]);
33 /*輸入元素存到數組a中*/
34 printf("please input the number which do you want to search:\n");
35 scanf("%d", &key);
36 /*指定要查找的元素*/
37 search(key, a, n);
38 /*調用自定義的search函數*/
39 }
反思：由於順序查找算法貼近人的邏輯，所以一般入門C的查找算法考試范圍裡只有順序查找算法這一種。其實許多人，包括學過和沒學過的，提到查找算法時，都第一個想到順序查找算法。甚至只想到順序查找算法。可惜，就如同暴力破解密碼一般，順序查找算法一般是所有查找算法內最為耗時的。所以，還是要記住其他查找算法的。
實例126 二分查找
問題：通過二分查找，編程實現數據查找。
邏輯：二分查找又稱折半查找，針對且只針對於有序表。首先選取有序表中間位置的數據，將其關鍵字於給定的關鍵字key進行比較，若相等，則查找成功；若key的值較大，則要找的數據一定在右子表中，繼續對右子表進行二分查找；若key的值較小，則要找的數據一定在左子表中，繼續對左子表進行二分查找。如此類推，直到查找成功或者查找失敗。
代碼：
1 #include <stdio.h>
2 void binary_search(int key, int a[], int n)
3 /*自定義函數binary_search*/
4 {
5 int low, high, mid, count = 0, count1 = 0;
6 low = 0;
7 high = n - 1;
8 while (low < high)
9 /*當查找范圍不為0時執行循環體語句*/
10 {
11 count++;
12 /*count記錄查找次數*/
13 mid = (low + high) / 2;
14 /*求出中間位置*/
15 if (key < a[mid])
16 /*當key小於中間值*/
17 high = mid - 1;
18 /*確定左子表范圍*/
19 else if (key > a[mid])
20 /*當key大於中間值*/
21 low = mid + 1;
22 /*確定右子表范圍*/
23 else if (key == a[mid])
24 /*當key等於中間值證明查找成功*/
25 {
26 printf("success!\nsearch %d times!a[%d]=%d", count, mid, key);
27 /*輸出查找次數及所查找元素在數組中的位置*/
28 count1++;
29 /*count1記錄查找成功次數*/
30 break;
31 }
32 }
33 if (count1 == 0)
34 /*判斷是否查找失敗*/
35 printf("no found!");
36 /*查找失敗輸出no found*/
37 }
38 main()
39 {
40 int i, key, a[100], n;
41 printf("please input the length of array:\n");
42 scanf("%d", &n);
43 /*輸入數組元素個數*/
44 printf("please input the element:\n");
45 for (i = 0; i < n; i++)
46 scanf("%d", &a[i]);
47 /*輸入有序數列到數組a中*/
48 printf("please input the number which do you want to search:\n");
49 scanf("%d", &key);
50 /*輸入要查找的關鍵字*/
51 binary_search(key, a, n);
52 /*調用自定義函數*/
53 }
反思：其實二分查找就好像高中數學中“二分法”一樣。所以也較為容易理解。雖然這種算法極為快捷，可惜該種查找算法只針對有序表。所以仍然需要學習其他算法。
實例127 分塊查找
問題：通過分塊查找，編程實現數據查找
邏輯：分塊查找，又稱為索引順序查找，是對順序查找和折半查找的綜合改進。其實從分塊、索引二詞就可以知道起思想。通過對數據的分塊，不同塊負責放下不同范圍的數據，不可以存在重疊數據范圍。當需要查找一個給定數據時，可以通過索引表來確定數據范圍，從而確定到具體的一個數據塊，借此來提升效率。
代碼：
1 #include <stdio.h>
2 struct index
3 /*定義塊的結構*/
4 {
5 int key;
6 int start;
7 int end;
8 } index_table[4];
9 /*定義結構體數組*/
10 int block_search(int key, int a[])
11 /*自定義實現分塊查找*/
12 {
13 int i, j;
14 i = 1;
15 while (i <= 3 && key > index_table[i].key)
16 /*確定在那個塊中*/
17 i++;
18 if (i > 3)
19 /*大於分得的塊數，則返回0*/
20 return 0;
21 j = index_table[i].start;
22 /*j等於塊范圍的起始值*/
23 while (j <= index_table[i].end && a[j] != key)
24 /*在確定的塊內進行查找*/
25 j++;
26 if (j > index_table[i].end)
27 /*如果大於塊范圍的結束值，則說明沒有要查找的數,j置0*/
28 j = 0;
29 return j;
30 }
31 main()
32 {
33 int i, j = 0, k, key, a[16];
34 printf("please input the number:\n");
35 for (i = 1; i < 16; i++)
36 scanf("%d", &a[i]);
37 /*輸入由小到大的15個數*/
38 for (i = 1; i <= 3; i++)
39 {
40 index_table[i].start = j + 1;
41 /*確定每個塊范圍的起始值*/
42 j = j + 1;
43 index_table[i].end = j + 4;
44 /*確定每個塊范圍的結束值*/
45 j = j + 4;
46 index_table[i].key = a[j];
47 /*確定每個塊范圍中元素的最大值*/
48 }
49 printf("please input the number which do you want to search:\n");
50 scanf("%d", &key);
51 /*輸入要查詢的數值*/
52 k = block_search(key, a);
53 /*調用函數進行查找*/
54 if (k != 0)
55 printf("success.the position is :%d\n", k);
56 /*如果找到該數，則輸出其位置*/
57 else
58 printf("no found!");
59 /*若未找到則輸出提示信息*/
60 }
反思：分塊查找算法是通過將順序查找和二分查找綜合而來。效率處於兩者之間，同樣缺點也是有的。雖然分塊查找算法不需要數據表呈線性，但需要建立有序索引表。所有，相對而言，分塊查找更加適應於需要多次查找的數據表。
實例128 哈希查找
問題：通過哈希查找，編程實現數據查找。
邏輯： 哈希查找可以說是這四類查找方法中最為復雜的查找方法。主要它的處理方法並不唯一，相反還很多。
哈希查找是通過給定哈希函數計算數據存儲位置的方法。操作步驟：1）利用給定的哈希函數計算，構造哈希表；2）根據選擇的沖突處理方法結局地址沖突；3）在哈希表的基礎上實現哈希查找。
哈希函數的構造函數常用的有5種：數字分析法、平方取中法、分段疊加、偽隨機數法、余數法（接下來的代碼將采取最為常用的余數法）。
雖然通過構造好的哈希函數可以減少沖突，但是沖突是不可能完全避免的，所以就相應地產生了避免哈希沖突的四種方法，分別是：
1.開放定址法：1）線性探測再散列（接下來的代碼將采取該方法）；2）二次探測再散列。
2.鏈地址法。
3.再哈希法。
4.建立公共溢出區（公共溢出區問題我會在接下來的Win32編程的第三章中提及）。
開放定址法中的線性探測再散列比較常用，該方法的特點是沖突發生時，順序查看表中的下一單元，直到找出一個空單元或者查遍全表。
代碼：
1 #include <stdio.h>
2 #include <time.h>
3 #define Max 11
4 #define N 8
5 int hashtable[Max];
6 int func(int value)
7 {
8 return value % Max;
9 /*哈希函數*/
10 }
11 int search(int key)
12 /*自定義函數實現哈希查詢*/
13 {
14 int pos, t;
15 pos = func(key);
16 /*哈希函數確定出的位置*/
17 t = pos;
18 /*t存放確定出的位置*/
19 while (hashtable[t] != key && hashtable[t] != - 1)
20 /*如果該位置上不等於要查找的關鍵字且不為空*/
21 {
22 t = (t + 1) % Max;
23 /*利用線性探測求出下一個位置*/
24 if (pos == t)
25 /*如果經多次探測又回到原來用哈希函數求出的位置則說明要查找的數不存在*/
26 return - 1;
27 }
28 if (hashtable[t] == - 1)
29 /*如果探測的位置是-1則說明要查找的數不存在*/
30 return NULL;
31 else
32 return t;
33 }
34 void creathash(int key)
35 /*自定義函數創建哈希表*/
36 {
37 int pos, t;
38 pos = func(key);
39 /*哈希函數確定元素的位置*/
40 t = pos;
41 while (hashtable[t] != - 1)
42 /*如果該位置有元素存在則進行線性探測再散列*/
43 {
44 t = (t + 1) % Max;
45 if (pos == t)
46 /*如果沖突處理後確定的位置與原位置相同則說明哈希表已滿*/
47 {
48 printf("hash table is full\n");
49 return ;
50 }
51 }
52 hashtable[t] = key;
53 /*將元素放入確定的位置*/
54 }
55 main()
56 {
57 int flag[50];
58 int i, j, t;
59 for (i = 0; i < Max; i++)
60 hashtable[i] = - 1;
61 /*哈希表中初始位置全置-1*/
62 for (i = 0; i < 50; i++)
63 flag[i] = 0;
64 /*50以內所有數未產生時均標志為0*/
65 srand((unsigned long)time(0));
66 /*利用系統時間做種子產生隨機數*/
67 i = 0;
68 while (i != N)
69 {
70 t = rand() % 50;
71 /*產生一個50以內的隨機數賦給t*/
72 if (flag[t] == 0)
73 /*查看t是否產生過*/
74 {
75 creathash(t);
76 /*調用函數創建哈希表*/
77 printf("%2d:", t);
78 /*將該元素輸出*/
79 for (j = 0; j < Max; j++)
80 printf("(%2d) ", hashtable[j]);
81 /*輸出哈希表中內容*/
82 printf("\n");
83 flag[t] = 1;
84 /*將產生的這個數標志為1*/
85 i++;
86 /*i自加*/
87 }
88 }
89 printf("please input number which do you want to search:");
90 scanf("%d", &t);
91 /*輸入要查找的元素*/
92 if (t > 0 && t < 50)
93 {
94 i = search(t);
95 /*調用search進行哈希查找*/
96 if (i != - 1)
97 printf("success!The position is:%d\n", i);
98 /*若查找到該元素則輸出其位置*/
99 else
100 printf("sorry,no found!");
101 /*未找到輸出提示信息*/
102 }
103 else
104 printf("inpput error!");
105 }
反思：哈希查找的難點在於兩點：1.使用的方法難以迅速理解，造成記憶困難；2.其中可能采取的哈希函數、沖突解決方法不唯一。兩者疊加，造成對哈希查找的忘卻。
總結：至此，主要的四種查找方法都已經詳細講述了。需要按照順序一步步理解，記憶。
4.4 其他重要算法
實例110 迪傑斯特拉算法
問題：通過迪傑斯特拉算法求解如圖所示的頂點1到各頂點的的最短路徑。
邏輯：迪傑斯特拉算法是一種圖譜搜索算法。許多問題都可以建模為圖譜，再通過這個算法計算出最短路徑。其算法思想：設置並逐步擴充一個集合S，存放已求出其最短路徑的頂點，則尚未確定最短路徑的頂點集合是V-S（其中V是網中所有頂點集合）。按最短路徑長度遞增的順序逐個將V-S中的頂點加到S中，直到S中包含全部頂點，而V-S為空。
代碼：
1 #include<stdlib.h>
2 #include<stdio.h>
3 #define MAXNODE 30
4 #define MAXCOST 1000
5 int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=5;
6 void dijkstra(int v0)
7 {
8 int s[MAXNODE];
9 int mindis,dis,i,j,u;
10 for(i=1;i<=n;i++)
11 {
12 dist[i]=cost[v0][i];
13 s[i]=0;
14 }
15 s[v0]=1;
16 for(i=1;i<=n;i++)
17 {
18 mindis=MAXCOST;
19 for(j=1;j<=n;j++)
20 if(s[j]==0&&dist[j]<mindis)
21 {
22 u=j;
23 mindis=dist[j];
24 }
25 s[u]=1;
26 for(j=1;j<=n;j++)
27 if(s[j]==0)
28 {
29 dis=dist[u]+cost[u][j];
30 dist[j]=(dist[j]<dis)?dist[j]:dis;
31 }
32 }
33 }
34 void display_path(int v0)
35 {
36 int i;
37 printf("\n 頂點 %d 到各頂點的最短路徑長度如下:\n",v0);
38 for(i=1;i<=n;i++)
39 {
40 printf(" (v%d->v%d):",v0,i);
41 if(dist[i]==MAXCOST)
42 printf("wu lun jing\n");
43 else
44 printf("%d\n",dist[i]);
45 }
46 }
47 main()
48 {
49 int i,j,v0=1;
50 for(i=1;i<=n;i++)
51 for(j=1;j<=n;j++)
52 cost[i][j]=MAXCOST;
53 for(i=1;i<=n;i++)
54 cost[i][i]=0;
55 cost[1][2]=10;
56 cost[1][5]=100;
57 cost[1][4]=30;
58 cost[2][3]=50;
59 cost[4][3]=20;
60 cost[3][5]=10;
61 cost[4][5]=60;
62 dijkstra(v0);
63 display_path(v0);
64 }
反思：這個算法是上一章圖論部分中特意留取下來的。這個算法在互聯網、物流等多個方面有著其重要作用。
總結：其實還有許多算法這裡都沒有寫到。這裡只是寫到一些基礎算法。之後如果有時間的話，會單開章節寫一些其他算法，諸如傅裡葉變換於快速傅裡葉變換等算法。
摘錄： 八大排序算法 http://blog.csdn.net/hguisu/article/details/7776068
統治世界的十大算法 http://36kr.com/p/212499.html
百度圖片、百度知道、百度百科、搜狗百科等
回到頂部
2016.10.03發布
