揭秘編程核心：基本數(shù)據(jù)結(jié)構(gòu)與算法思想詳解

編程的關(guān)鍵在于選擇數(shù)據(jù)結(jié)構(gòu)和算法，數(shù)據(jù)結(jié)構(gòu)用于描述問題，算法用于描述解決問題的方法和步驟。

描述問題的數(shù)據(jù)除了各數(shù)據(jù)元素本身，還要考慮各元素的邏輯關(guān)系，主要是一對一的線性關(guān)系，一對多的樹型關(guān)系和多對多的圖形關(guān)系。另外，內(nèi)存中對各數(shù)據(jù)元素的存儲(chǔ)只有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式，所以數(shù)據(jù)結(jié)構(gòu)還要考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，并考慮邏輯結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)如何有效地結(jié)合到一起。

用算法描述問題，當(dāng)問題比較復(fù)雜時(shí)，通常的思路是分而治之，并輔以適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。

1 分治法Divide and Conquer

分治法通常描述為以下三步：

Divide the problem into more subproblems（分解問題為眾多的子問題）;

Conuqe(solve) the subproblems（解決各子問題）;

Combine(merge) the solution of subproblems(if need)（合并各子問題的解（如果需要））.

如用分治法來計(jì)算2^10?

2^10＝2^5*x^5=2^2*x^3*x^5=32*32=1024

相對于順序查找，二分查找有更高的效率，前提是二分查找需要事先排好序：

int binarySearchLoop(int arr[], int len, int findData)
{
if(arr==NULL || len <=0)
return -1;
int start = 0;
int end = len-1;
while(start<=end)
  {
int mid = start+(end-start)/2;
if(arr[mid] == findData)
return mid;
else if(findData < arr[mid])
      end = mid-1;
else
      start = mid+1;
  }
return -1;
}

2 枚舉法也是一種暴力縮小問題規(guī)模的算法

簡單的枚舉算法也是可以優(yōu)化的，即盡可能縮小搜索的空間，如判斷質(zhì)數(shù)：

質(zhì)數(shù)（prime number）又稱素?cái)?shù)，有無限個(gè)。質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。

判斷質(zhì)數(shù)的函數(shù)：

int isPrime(int n)
{
if(n<= 1)// 小于等于1的整數(shù)不可能是素?cái)?shù)
return 0;
if(n == 2); // 2 是素?cái)?shù)
return 1;
if(n%2 == 0); // 能被2整除的其他整數(shù)都不是素?cái)?shù)
return 0;
int limit = (int)sqrt((double)n)+1;
for(int i = 3; i <= limit; i=i+2)
  {
if(n % i == 0)
return 0;
  }
return 1;
}

isPrime()沒有必要枚舉所有的因子。

I 只要發(fā)現(xiàn)任何一個(gè)大于1小于n的因子，就能停下來報(bào)告n不是素?cái)?shù)。

II 如果n能被2整除，直接報(bào)告n不是素?cái)?shù)。如果n不能被2整除，那么它也不可能被4或6或其他偶數(shù)整除。因此，isPrime只需要檢查2和奇數(shù)（由3開始，步長為2）。但注意有個(gè)特例，2能被2整除，但2是素?cái)?shù)。

III 如果n不是素?cái)?shù)，則必有一個(gè)因子小于√n 。因此不需要檢查到n為止。只需檢查到√n（n=√n*√n） 。

因?yàn)槿绻鹡能被2~n-1之間任一整數(shù)整除，其二個(gè)因子必定有一個(gè)小于或等于√n，另一個(gè)大于或等于√n。例如24可以表示為：2*12、3*8、4*6，前面的因子小于√24，后面的因子大于√24，檢驗(yàn)出了小因子，即可判斷n是否為素?cái)?shù)，就像邏輯運(yùn)算的短路求值。

3 程序的模塊化

分治法在程序思想中的應(yīng)用就是實(shí)現(xiàn)程序的模塊化，包括面向過程的函數(shù)化和面向?qū)ο蟮膶ο蠡?/p>

許多原因都促使我們將應(yīng)用程序分解成函數(shù)，下面僅列舉其中三個(gè)：

函數(shù)一般小而具體。用一系列函數(shù)來寫程序，勝于一氣呵成寫完整個(gè)程序。這稱為“分而治之”，使你的精力一次集中在一個(gè)函數(shù)上。

包含許多小函數(shù)的應(yīng)用程序比單一的長程序更容易閱讀和調(diào)試。

函數(shù)可以重用。函數(shù)寫好后可在程序的其他任何地方調(diào)用。這減少了編碼量，提高了開發(fā)效率。

4 函數(shù)調(diào)用與棧

首先討論一個(gè)從a點(diǎn)出發(fā)去f點(diǎn)，然后回到a點(diǎn)的問題（中間的b、c、d、e都有多個(gè)分岔口）：

a→b2→c1→d3→e2→f，每個(gè)分岔口都有一個(gè)信封，告訴你應(yīng)該走哪一個(gè)分支，為了能夠正確地回到起點(diǎn)a，正確的做法是拿到一個(gè)信封后，即將這個(gè)信封疊在上一次拿到的信封的上面，回去時(shí)，依次從上面拿取信封，按提示即可正確返回。

其做法就是依次放入，依次取出，信封之間是順序關(guān)系，只在一端操作，也就是不管是放入還是取出都不在中間操作。這樣一種思路在計(jì)算機(jī)上用數(shù)據(jù)來描述就是后進(jìn)先出的棧，函數(shù)的調(diào)用、返回，遞歸、回溯算法都需要使用棧這種數(shù)據(jù)結(jié)構(gòu)（由程序員或遞歸時(shí)由編譯器來實(shí)現(xiàn)）。

在C++中，函數(shù)不能嵌套定義，但可以嵌套調(diào)用，在函數(shù)調(diào)用時(shí)，編譯器需要確保在逐級(jí)調(diào)用后能夠回歸到最初的調(diào)用點(diǎn)，編譯器會(huì)隱式實(shí)現(xiàn)一個(gè)堆棧，用來保存每一級(jí)函數(shù)調(diào)用時(shí)的函數(shù)返回地址和局部變量，依次入棧和出棧。

C++也支持遞歸函數(shù)的遞歸調(diào)用，同樣是由編譯器隱式地實(shí)現(xiàn)了一個(gè)堆棧。

5 深度搜索與廣度搜索

如果將上述的問題稍微擴(kuò)展一點(diǎn)，要從源點(diǎn)到目標(biāo)點(diǎn)，中間的節(jié)點(diǎn)可能有多個(gè)分叉，這樣的問題可以用一個(gè)樹或圖來描述。

而探路的方法可以分為兩種，一種是深度優(yōu)先搜索（下一點(diǎn)、下一點(diǎn)……回溯……），一種是廣度優(yōu)先搜索（下一點(diǎn)的全部分叉、下一點(diǎn)的全部分叉……）：

5.1 深度優(yōu)先搜索用棧（stack）來實(shí)現(xiàn)，整個(gè)過程可以想象成一個(gè)倒立的樹形：

1）把根節(jié)點(diǎn)壓入棧中。

2）每次從棧中彈出一個(gè)元素，搜索所有在它下一級(jí)的元素，把這些元素壓入棧中。并把這個(gè)元素記為它下一級(jí)元素的前驅(qū)。

3）找到所要找的元素時(shí)結(jié)束程序。

4）如果遍歷整個(gè)樹還沒有找到，結(jié)束程序。

5.2 廣度優(yōu)先搜索使用隊(duì)列（queue）來實(shí)現(xiàn)，整個(gè)過程也可以看做一個(gè)倒立的樹形：

1）把根節(jié)點(diǎn)放到隊(duì)列的末尾。

2）每次從隊(duì)列的頭部取出一個(gè)元素，查看這個(gè)元素所有的下一級(jí)元素，把它們放到隊(duì)列的末尾。并把這個(gè)元素記為它下一級(jí)元素的前驅(qū)。（取出的元素也可以保存到一個(gè)隊(duì)列）

3）找到所要找的元素時(shí)結(jié)束程序。

4）如果遍歷整個(gè)樹還沒有找到，結(jié)束程序。

廣度優(yōu)先搜索相對于深度優(yōu)先搜索，因?yàn)槭侵饘犹剿鞯?，可以確保以較少的點(diǎn)到達(dá)目標(biāo)點(diǎn)，缺點(diǎn)是存儲(chǔ)量較大。

6 遞歸算法

遞歸就是某個(gè)函數(shù)直接或間接的調(diào)用自身。

語法形式上: 在一個(gè)函數(shù)的運(yùn)行過程中, 調(diào)用這個(gè)函數(shù)自己：

直接調(diào)用: 在fun()中直接執(zhí)行fun()；

間接調(diào)用: 在fun1()中執(zhí)行fun2(); 在fun2()中又執(zhí)行fun1() ；

問題的求解過程是劃分成許多相同性質(zhì)的子問題的求解，而小問題的求解過程可以很容易的求出。這些子問題的解就構(gòu)成里原問題的解。

待求解問題的解可以描述為輸入變量x的函數(shù)f(x)。

通過尋找函數(shù)g( )，使得f(x) = g(f(x-1))。

且已知f(0)的值, 就可以通過f(0)和g( )求出f(x)的值。

擴(kuò)展到多個(gè)輸入變量x, y, z等, x-1也可以推廣到 x - x1 , 只要遞歸朝著 “出口” 的方向即可。

遞歸算法分解出的子問題與原問題之間是縱向的, 同類的關(guān)系（枚舉分解出的子問題之間是橫向的, 同類的關(guān)系）。

遞歸的三個(gè)要點(diǎn):

遞歸式：如何將原問題劃分成子問題；

遞歸出口：遞歸終止的條件, 即最小子問題的求解,可以允許多個(gè)出口；

界函數(shù)：問題規(guī)模變化的函數(shù), 它保證遞歸的規(guī)模向出口條件靠攏。

如一個(gè)求階乘的遞歸程序，給定n, 求階乘n!

階乘的棧：

二分搜索的遞歸實(shí)現(xiàn)：

int binarySearchRecursion(int arr[], int findData, int start, int end)
{
if(arr==NULL || start>end)
return -1;
int mid = start+(end-start)/2;
if(arr[mid] == findData)
return mid;
else if(findData < arr[mid])
      binarySearchRecursion(arr, findData, start, mid-1);
else
??????binarySearchRecursion(arr,?findData,?mid+1,?end);

7 歸并排序

歸并排序（merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并（2-way or binary merges sort）。

歸并排序在1945年由馮·諾伊曼首次提出。

2-路歸并的基本思路就是將數(shù)組分成二組A，B，如果這二組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序。如何讓這二組組內(nèi)數(shù)據(jù)有序？

可以將A，B組各自再分成二組。依次類推，當(dāng)分出來的小組只有一個(gè)數(shù)據(jù)時(shí)，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的二個(gè)小組就可以了。這樣通過先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。

歸并排序的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個(gè)合并有序數(shù)列的過程，時(shí)間復(fù)雜度可以記為O(N)，故一共為O(N*logN)。因?yàn)闅w并排序每次都是在相鄰的數(shù)據(jù)中進(jìn)行操作，所以歸并排序在O(N*logN)的幾種排序方法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。

歸并排序的實(shí)現(xiàn)分為遞歸實(shí)現(xiàn)與非遞歸(迭代)實(shí)現(xiàn)。遞歸實(shí)現(xiàn)的歸并排序是算法設(shè)計(jì)中分治策略的典型應(yīng)用，我們將一個(gè)大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個(gè)大問題。非遞歸(迭代)實(shí)現(xiàn)的歸并排序首先進(jìn)行是兩兩歸并，然后四四歸并，然后是八八歸并，一直下去直到歸并了整個(gè)數(shù)組。

7.1歸并排序分解

可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。

7.2歸并排序合并相鄰有序子序列

再來看看并階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實(shí)現(xiàn)步驟。

申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置；temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];

重復(fù)步驟3直到某一指針到達(dá)序列尾；

將另一序列剩下的所有元素直接復(fù)制到合并序列尾；

7.3歸并排序動(dòng)圖演示

7.4歸并排序代碼

8 回溯法和分書問題

回溯算法實(shí)際上是一個(gè)類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯“返回，嘗試別的路徑?？梢詤⒖家幌伦呙詫m的過程，一開始會(huì)隨機(jī)選擇一條道路前進(jìn)，一直到走不通之后就會(huì)回頭直到找到另外一條沒有試過的道路前進(jìn)。實(shí)際上，走迷宮的算法就是回溯法的經(jīng)典問題。

回溯法實(shí)際上也是一種試錯(cuò)的思路，通過不斷嘗試解的組合來達(dá)到求解可行解和最優(yōu)解的目的。雖然都有窮搜的概念蘊(yùn)含其中，但是回溯法和窮舉查找法是不同的。對于一個(gè)問題的所有實(shí)例，窮舉法注定都是非常緩慢的，但應(yīng)用回溯法至少可以期望對于一些規(guī)模不是很小的實(shí)例，計(jì)算機(jī)在可接受的時(shí)間內(nèi)對問題求解。

許多復(fù)雜的規(guī)模的問題都可以使用回溯法，有”通用解題方法”的美稱。分書問題和八皇后都是典型的回溯法問題。

分書問題能夠較有代表性地表現(xiàn)數(shù)據(jù)描述、遞歸、回溯的算法思路。

有編號(hào)為0，1，2，3，4的5本書，準(zhǔn)備分給5個(gè)人A，B，C，D，E，寫一個(gè)程序，輸出所有皆大歡喜的分書方案。

每個(gè)人的閱讀興趣用一個(gè)二維數(shù)組like描述：

Like[i][j] = true i喜歡書j Like[i][j] = false i不喜歡書j

設(shè)計(jì)一個(gè)函數(shù)trynext(int i)給第i個(gè)人分書。

用一個(gè)一維數(shù)組take表示某本書分給了某人。take[j]=i+1;//把第j本書分配給第i個(gè)人

依次嘗試把書j分給人i。

如果第i個(gè)人不喜歡第j本書，則嘗試下一本書，如果喜歡，并且第j本書尚未分配，則把書j分配給i。

如果i是最后一個(gè)人，則方案數(shù)加1，輸出該方案。否則調(diào)用trynext(i+1)為第i+1個(gè)人分書。

如果對第i個(gè)人枚舉了他喜歡的所有的書，都沒有找到可行的方案，那就回到前一個(gè)狀態(tài)i-1，讓i-1把分到的書退回去，重新找喜歡的書，再遞歸調(diào)用函數(shù)，尋找可行的方案。

#include 
#include 
using namespace std;
int like[5][5]={
{0,0,1,1,0},
{1,1,0,0,1},
{0,1,1,0,1},
{0,0,0,1,0},
{0,1,0,0,1}};
int take[5]={0,0,0,0,0};//記錄每一本書的分配情況
int n;//n表示分書方案數(shù)
void trynext(int i);
int main()
{
n=0;
trynext(0);
getch();
return 0;
}
//對第 i 個(gè)人進(jìn)行分配
void trynext(int i)
{
int j,k;
for(j=0;j<5;j++)
{
if(like[i][j]&&take[j]==0)
{
take[j]=i+1;//把第j本書分配給第i個(gè)人
if(i==4)//第5個(gè)人分配結(jié)束，也即所有的書已經(jīng)分配完畢，可以將方案進(jìn)行輸出
{
n++;
cout<<"第"<

	當(dāng)like矩陣的值為

	

	附歸并排序的代碼：
#include 
#include 
#include 
// 分類 -------------- 內(nèi)部比較排序
// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
// 最差時(shí)間復(fù)雜度 ---- O(nlogn)
// 最優(yōu)時(shí)間復(fù)雜度 ---- O(nlogn)
// 平均時(shí)間復(fù)雜度 ---- O(nlogn)
// 所需輔助空間 ------ O(n)
// 穩(wěn)定性 ------------ 穩(wěn)定
// 合并兩個(gè)已排好序的數(shù)組A[left...mid]和A[mid+1...right]
void Merge(int A[], int left, int mid, int right)
{
  int len = right - left + 1;
  int *temp = new int[len]; // 輔助空間O(n)
  int index = 0;
  int i = left; // 前一數(shù)組的起始元素
  int j = mid + 1; // 后一數(shù)組的起始元素
while (i <= mid && j <= right)
  {
    temp[index++] = A[i] <= A[j] ? A[i++] : A[j++]; // 帶等號(hào)保證歸并排序的穩(wěn)定性
  }
while (i <= mid)
  {
    temp[index++] = A[i++];
  }
while (j <= right)
  {
    temp[index++] = A[j++];
  }
for (int k = 0; k < len; k++)
  {
A[left++] = temp[k];
  }
}


// 遞歸實(shí)現(xiàn)的歸并排序(自頂向下)
void MergeSortRecursion(int A[], int left, int right)
{
if (left == right) // 當(dāng)待排序的序列長度為1時(shí)，遞歸開始回溯，進(jìn)行merge操作
return;
  int mid = (left + right) / 2;
MergeSortRecursion(A, left, mid); //左半部分排好序
MergeSortRecursion(A, mid + 1, right); //右半部分排好序
Merge(A, left, mid, right); //合并左右部分
}
// 非遞歸(迭代)實(shí)現(xiàn)的歸并排序(自底向上)
void MergeSortIteration(int A[], int len)
{
  int left, mid, right;// 子數(shù)組索引,前一個(gè)為A[left...mid]，后一個(gè)子數(shù)組為A[mid+1...right]
for (int i = 1; i < len; i *= 2) // 子數(shù)組的大小i初始為1，每輪翻倍
  {
left = 0;
while (left + i < len) // 后一個(gè)子數(shù)組存在(需要?dú)w并)
    {
      mid = left + i - 1;
right = mid + i < len ? mid + i : len - 1;// 后一個(gè)子數(shù)組大小可能不夠
Merge(A, left, mid, right);
left = right + 1; // 前一個(gè)子數(shù)組索引向后移動(dòng)
    }
  }
}
int main()
{
  int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 從小到大歸并排序
  int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
  int n1 = sizeof(A1) / sizeof(int);
  int n2 = sizeof(A2) / sizeof(int);
MergeSortRecursion(A1, 0, n1 - 1); // 遞歸實(shí)現(xiàn)
MergeSortIteration(A2, n2); // 非遞歸實(shí)現(xiàn)
  printf("遞歸實(shí)現(xiàn)的歸并排序結(jié)果：");
for (int i = 0; i < n1; i++)
  {
    printf("%d ", A1[i]);
  }
  printf("
    ");
    printf("非遞歸實(shí)現(xiàn)的歸并排序結(jié)果：");
for (i = 0; i < n2; i++)
  {
    printf("%d ", A2[i]);
  }
  printf("
    ");
    system("pause");
return 0;
}

	審核編輯：黃飛