數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——圖(4&5&總結(jié)&后記)

2019-11-17 05:47:51

字體：大中小

供稿：網(wǎng)友

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——圖【4】（最短路徑）    happycock（原作）
要害字     數(shù)據(jù)結(jié)構(gòu) 最短路徑

      最短路徑恐怕是圖的各種算法中最能吸引初學(xué)者眼球的了——在地圖上找一條最短的路或許每個人都曾經(jīng)嘗試過。下面我們用計算機來完成我們曾經(jīng)的“愿望”。

      在圖的算法中有個有趣的現(xiàn)象，就是問題的規(guī)模越大，算法就越簡單。圖是個復(fù)雜的結(jié)構(gòu)，對于一個特定問題，求解特定頂點的結(jié)果都會受到其他頂點的影響——就好比一堆互相碰撞的球體，要求解特定球體的狀態(tài)，就必須考慮其他球體的狀態(tài)。既然每個頂點都要掃描，假如對所有的頂點都求解，那么算法就非常的簡單——無非是遍歷嗎。然而，當(dāng)我們降低問題規(guī)模，那很自然的，我們希望算法的規(guī)模也降低——假如不降低，不是殺雞用牛刀？但是，正是由于圖的復(fù)雜性，使得這種降低不輕易達到，因此，為了降低算法的規(guī)模，使得算法就復(fù)雜了。

      在下面的介紹中，清楚了印證了上面的結(jié)論。人的認(rèn)知過程是從簡單到復(fù)雜，雖然表面看上去，求每對頂點之間的最短路徑要比特定頂點到其他頂點之間的最短路徑復(fù)雜，但是，就像上面說的，本質(zhì)上，前者更為簡單。下面的介紹沒有考慮歷史因素（就是指哪個算法先提出來），也沒有考慮算法提出者的真實想法（究竟是誰參考了或是沒參考誰），只是從算法本身之間的聯(lián)系來做一個闡述，如有疏漏，敬請原諒。

預(yù)備工作
      一路走下來，圖類已經(jīng)很“臃腫”了，為了更清楚的說明問題，需要“重起爐灶另開張”，同時也是為了使算法和儲存方法分開，以便于復(fù)用。

首先要為基本圖類添加幾個接口。

template
class Network
{
public:
       int find(const name& v)
       dist& getE(int m, int n)
       const dist& NoEdge()
};

template
class AdjMatrix
{
public:
       dist& getE(int m, int n)
};

template
class Link
{
public:
       dist& getE(int m, int n)
       {
              for (list::iterator iter = vertices[m].e->begin();
              iter != vertices[m].e->end() && iter->vID < n; iter++);
              if (iter == vertices[m].e->end()) return NoEdge;
              if (iter->vID == n) return iter->cost;
              return NoEdge;
       }
};

      然后就是為了最短路徑算法“量身定做”的“算法類”。求某個圖的最短路徑時，將圖綁定到算法上，例如這樣：

Network > a(100);
//插入點、邊……
Weight > b(&a);

#include "Network.h"
template
class Weight
{
public:
       Weight(Network* G) : G(G), all(false), N(G->vNum())
       {
              length = new dist*[N]; path = new int*[N];
              shortest = new bool[N]; int i, j;
              for (i = 0; i < N; i++)
              {
                     length[i] = new dist[N]; path[i] = new int[N];
              }

              for (i = 0; i < N; i++)
              {
                     shortest[i] = false;
                     for (j = 0; j < N; j++)
                     {
                            length[i][j] = G->getE(i, j);
                            if (length[i][j] != G->NoEdge()) path[i][j] = i;
                            else path[i][j] = -1;
                     }
              }
       }

       ~Weight()
       {
              for (int i = 0; i < N; i++)
              delete []length; delete []path; delete []shortest;
       }

PRivate:

       void print(int i, int j)
       {
              if (path[i][j] == -1) cout << "No Path" << endl; return;
              cout << "Shortest Path: "; out(i, j); cout << G->getV(j) << endl;
              cout << "Path Length: " << length[i][j] << endl;
       }

       void out(int i, int j)
       {
              if (path[i][j] != i) out(i, path[i][j]);
              cout << G->getV(path[i][j]) << "->";
       }
       dist** length; int** path; bool* shortest; bool all; int N;
       Network* G;
};

      發(fā)現(xiàn)有了構(gòu)造函數(shù)真好，算法的結(jié)果數(shù)組的初始化和算法本身分開了，這樣一來，算法的基本步驟就很輕易看清楚了。

所有頂點之間的最短路徑（Floyed算法）

      從v1到v2的路徑要么是v1->v2，要么中間經(jīng)過了若干頂點。顯然我們要求的是這些路徑中最短的一條。這樣一來，問題就很好解決了——最初都是源點到目的點，然后依次添加頂點，使得路徑逐漸縮短，頂點都添加完了，算法就結(jié)束了。

void AllShortestPath() //Folyed
{
       if (all) return;
       for (int k = 0; k < N; k++)
       {
              shortest[k] = true;
              for (int i = 0; i < N; i++)
                     for (int j = 0; j < N; j++)
                            if (length[i][k] + length[k][j] < length[i][j])
                            {
                                   length[i][j] = length[i][k] + length[k][j];
                                   path[i][j] = path[k][j];
                            }
       }
       all = true;
}

單源最短路徑（Dijkstra算法）
仿照上面的Floyed算法，很輕易的，我們能得出下面的算法：

void ShortestPath(int v1)
{
      //Bellman-Ford
       for (int k = 2; k < N; k++)
              for (int i = 0; i < N; i++)
                    for (int j = 0; j < N; j++)
                            if (length[v1][j] + length[j][i] < length[v1][i])
                            {
                                  length[v1][i] = length[v1][j] + length[j][i];
                                   path[v1][i] = j;
                            }
}

      這就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的時間復(fù)雜度從O(n3)降到預(yù)期的O(n2)，只是空間復(fù)雜度從O(n2)降到了O(n)，但這也是應(yīng)該的，因為只需要原來結(jié)果數(shù)組中的一行。因此，我并不覺得這個算法是解決“邊上權(quán)值為任意值的單源最短路徑問題”而專門提出來的，是Dijkstra算法的“推廣”版本，他只是Floyed算法的退化版本。

      顯然，F(xiàn)loyed算法是經(jīng)過N次N2條邊迭代而產(chǎn)生最短路徑的；假如我們想把時間復(fù)雜度從O(n3) 降到預(yù)期的O(n2)，就必須把N次迭代的N2條邊變?yōu)镹條邊，也就是說每次參與迭代的只有一條邊——問題是如何找到這條邊。

      先看看邊的權(quán)值非負(fù)的情況。假設(shè)從頂點0出發(fā)，到各個頂點的距離是a1,a2……，那么，這其中的最短距離an必定是從0到n號頂點的最短距離。這是因為，假如an不是從0到n號頂點的最短距離，那么必然是中間經(jīng)過了某個頂點；但現(xiàn)在邊的權(quán)值非負(fù)，一個比現(xiàn)在這條邊還長的邊再加上另一條非負(fù)的邊，是不可能比這條邊短的。從這個原理出發(fā)，就能得出Dijkstra算法，注重，這個和Prim算法極其相似，不知道誰參考了誰；但這也是難免的事情，因為他們的原理是一樣的。

void ShortestPath(const name& vex1, const name& vex2)//Dijkstra
{
       int v1 = G->find(vex1); int v2 = G->find(vex2);
       if (shortest[v1])
       bool* S = new bool[N]; int i, j, k;
       for (i = 0; i < N; i++) S[i] = false; S[v1] = true;
       for (i = 0; i < N - 1; i++)//Dijkstra Start, like Prim?
       {
              for (j = 0, k = v1; j < N; j++)
                     if (!S[j] && length[v1][j] < length[v1][k]) k = j;
              S[k] = true;
              for (j = 0; j < N; j++)
                     if (!S[j] && length[v1][k] + length[k][j] < length[v1][j])
                     {
                            length[v1][j] = length[v1][k] + length[k][j];
                            path[v1][j] = k;
                     }
       }
       shortest[v1] = true; print(v1, v2);
}

      假如邊的權(quán)值有負(fù)值，那么上面的原則不再適用，連帶的，Dijkstra算法也就不再適用了。這時候，沒辦法，只有接受O(n3) Bellman-Ford算法了，雖然他可以降低為O(n*e)。不過，何必讓邊的權(quán)值為負(fù)值呢？還是那句話，合理的并不好用。

特定兩個頂點之間的最短路徑（A*算法）

      其實這才是我們最關(guān)心的問題，我們只是想知道從甲地到乙地怎么走最近，并不想知道別的——甲地到丙地怎么走關(guān)我什么事？自然的，我們希望這個算法的時間復(fù)雜度為O(n)，但是，正像從Floyed算法到Dijkstra算法的變化一樣，并不是很輕易達到這個目標(biāo)的。

      讓我們先來看看Dijkstra算法求特定兩個頂點之間的最短路徑的時間復(fù)雜度究竟是多少。顯然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，當(dāng)S[v2]==true時，算法就可以中止了。假設(shè)兩個頂點之間直接的路徑是他們之間的路徑最短的（不需要經(jīng)過其他中間頂點），并且這個路徑長度是源點到所有目的點的最短路徑中最短的，那么第一次迭代的時候，就可以得到結(jié)果了。也就是說是O(n)。然而當(dāng)兩個頂點的最短路徑需要經(jīng)過其他頂點，或者路徑長度不是源點到未求出最短路徑的目的點的最短路徑中最短的，那就要再進行若干次迭代，對應(yīng)的，時間復(fù)雜度就變?yōu)镺(2n)、O(3n)……到了最后才求出來（迭代了N－1次）的就是O(n2)。

      很明顯的，迭代次數(shù)是有下限的，最短路徑上要經(jīng)過多少個頂點，至少就要迭代多少次，我們只能使得最終的迭代次數(shù)接近最少需要的次數(shù)。假如再要減低算法的時間復(fù)雜度，我們只能想辦法把搜索范圍的O(n)變?yōu)镺(1)，這樣，即使迭代了N－1次才得到結(jié)果，那時間復(fù)雜度仍為O(n)。但這個想法實現(xiàn)起來卻是困難重重。

      仍然看Dijkstra算法，第一步要尋找S中的頂點到S外面頂點中最短的一條路徑，這個min運算使用基于比較的方法的時間復(fù)雜度下限是O(longN)（使用敗者樹），然后需要掃描結(jié)果數(shù)組的每個分量進行修改，這里的時間復(fù)雜度就只能是O(n)了。原始的Dijkstra算法達不到預(yù)期的目的。

      現(xiàn)在讓我們給圖添加一個附加條件——兩點之間直線最短，就是說假如v1和v2之間有直通的路徑（不經(jīng)過其他頂點），那么這條路徑就是他們之間的最短路徑。這樣一來，假如求的是v1能夠直接到達的頂點的最短路徑，時間復(fù)雜度就是O(1)了，顯然比原來最好的O(n)（這里實際上是O(logN)）提高了效率。

      這個變化的產(chǎn)生，是因為我們添加了“兩點之間直線最短”這樣的附加條件，實際上就是引入一個判定準(zhǔn)則，把原來盲目的O(n)搜索降到了O(1)。這個思想就是A*算法的思想。關(guān)于A*算法更深入的介紹，恕本人資料有限，不能滿足大家了。有愛好的可以到網(wǎng)上查查，這方面的中文資料實在太少了，大家做好看E文的預(yù)備吧。

總結(jié)
      不同于現(xiàn)有的教科書，我把求最短路徑的算法的介紹順序改成了上面的樣子。我認(rèn)為這個順序才真正反映了問題的本質(zhì)——當(dāng)減低問題規(guī)模時，為了降低算法的時間復(fù)雜度，應(yīng)該想辦法縮小搜索范圍。而縮小搜索范圍，都用到了一個思想——盡可能的向接近最后結(jié)果的方向搜索，這就是貪婪算法的應(yīng)用。

      假如反向看一遍算法的演化，我們還能得出新的結(jié)論。Dijkstra算法實際上不用做n2次搜索、比較和修改，當(dāng)求出最短路徑的頂點后，搜索范圍已經(jīng)被縮小了，只是限于儲存結(jié)構(gòu)，這種范圍的縮小并沒有體現(xiàn)出來。假如我們使得這種范圍縮小直接體現(xiàn)出來，那么，用n次Dijkstra算法代替Floyed算法就能帶來效率上的提升。A*算法也是如此，假如用求n點的A*算法來代替Dijkstra算法，也能帶來效率的提升。

      但是，每一步的進化實際上都伴隨著附加條件的引入。從Floyed到Dijkstra是邊上的權(quán)值非負(fù)，假如這個條件不成立，那么就只能退化成Bellman-Ford算法。從Dijkstra到A*是另外的判定準(zhǔn)則的引入（本文中是兩點之間直線最短），假如這個條件不成立，同樣的，只能采用不完整的Dijkstra（求到目的頂點結(jié)束算法）。

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——圖【5】活動網(wǎng)絡(luò)（AOV、AOE）    happycock（原作）
要害字     AOV AOE

      這部分是和工程相關(guān)的，也就是說，當(dāng)AOV、AOE很復(fù)雜的時候，才能顯示出這部分的價值——簡單的話，手工都要比程序快，輸入數(shù)據(jù)那段時間手工結(jié)果就出來了。我也沒什么例子好舉，總給我一種沒底氣的感覺，勉為其難的把程序?qū)懲昃退阃晔掳?。和前邊的相比，這部分專業(yè)了一點，換而言之，不是每個人都感愛好，不想看就跳過去吧。

預(yù)備工作

      活動網(wǎng)絡(luò)主要有兩個算法，拓?fù)渑判蚝颓笠β窂剑笳咭郧罢邽榛A(chǔ)。仿照上篇，另外構(gòu)造一個“算法類”，需要算法時，將圖綁定到算法上。

#include "Network.h"
#define iterator list::edge>::iterator
#define begin(i) G->data.vertices[i].e->begin()
#define end(i) G->data.vertices[i].e->end()
strUCt CriAct
{
       CriAct() {}
       CriAct(int source, int dest) : s(source), d(dest) {}
       int s, d;
};

template
class ActivityNetwork
{
public:
       ActivityNetwork(Network >* G) : G(G), N(G->vNum()), outCriAct(CA)
       {
              count = new int[N]; result = new int[N];
       }

       ~ActivityNetwork()
       {
              delete []count; delete []result;
       }
       const vector& outCriAct;
       const int* out;
private:
       void initialize()
       {
             for (int j = 0; j < N; j++) count[j] = 0;
             for (int i = 0; i < N; i++)
              {
                     for (iterator iter = begin(i); iter != end(i); iter++) count[iter->vID]++;
              }
              out = result;
       }
       Network >* G;
       vector CA;
       int N, *count, *result;
};

      因為AOV和AOE的邊都不會太多（想象一下邊多的情況，那事件就都是雞毛蒜皮了），所以儲存結(jié)構(gòu)直接選擇了鄰接表。并且為了體現(xiàn)鄰接表的優(yōu)勢，需要直接操作私有數(shù)據(jù)，因此要把這個類聲明為Link類和Network類的友元，另外由于這個類在后面，所以需要前視聲明。具體如下：

template  class ActivityNetwork;
template  class Link
;
template  class Network
;

拓?fù)渑判?br />
      這個算法很精巧，避免了對已經(jīng)排好序的頂點的再次掃描，另外，殷版上用計數(shù)數(shù)組來充當(dāng)棧的方法也很巧妙。算法的說明參閱相關(guān)的教科書，不再贅述。

bool TopoSort()
{
       initialize(); int i, top = -1;
       for (i = 0; i < N; i++) if (!count[i])
       for (i = 0; i < N; i++) //TopoSort Start
       {
              if (top == -1) return false;
              result[i] = top; top = count[top];
              for (iterator iter = begin(result[i]); iter != end(result[i]); iter++)
                     if (!--count[iter->vID])
       }
       return true;
}

      由于public數(shù)據(jù)成員out和private數(shù)據(jù)成員result指向同一個數(shù)組，在類的外面可以通過out來得到排序結(jié)果，只是不能改變（當(dāng)然，非要改變const數(shù)據(jù)也不是沒有辦法）。下面是測試程序，數(shù)據(jù)來自殷版：

#include
using namespace std;
#include "ActivityNetwork.h"
int main()
{
       Network > a;
       a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);a.insertV(5);
       a.insertE(0,3,1);a.insertE(0,1,1);a.insertE(1,5,1);a.insertE(2,1,1);
       a.insertE(2,5,1);a.insertE(4,0,1);a.insertE(4,1,1);a.insertE(4,5,1);
       ActivityNetwork b(&a);
       if (b.TopoSort()) for (int i = 0; i < a.vNum(); i++) cout << b.out[i] << ' ';
       return 0;
}

要害路徑

      有了拓?fù)渑判虻慕Y(jié)果，這個程序就比較好寫了，那些所謂的“技巧”就不用了，如下的程序，很直白，算法說明請參考教科書。

bool Cripath()
{
       if (!TopoSort()) return false; int i; iterator iter; CA.clear();
       dist* Ve = new dist[N]; dist* Vl = new dist[N];//Ve最早開始時間，Vl最遲開始時間
       for (i = 0; i < N; i++) Ve[i] = 0;//Ve初始化

       for (i = 0; i < N; i++)//按拓?fù)漤樞蛴嬎鉜e
              for (iter = begin(result[i]); iter != end(result[i]); iter++)
                     if (Ve[result[i]]+iter->cost>Ve[iter->vID]) Ve[iter->vID]= Ve[result[i]] + iter->cost;

       for (i = 0; i < N; i++) Vl[i] = Ve[N - 1];//Vl初始化

       for (i = N - 2; i >= 0; i--)//按逆拓?fù)漤樞蛴嬎鉜l
              for (iter = begin(result[i]); iter != end(result[i]); iter++)
                     if (Vl[iter->vID]-iter->cost < Vl[result[i]]) Vl[result[i]] = Vl[iter->vID] - iter->cost;

       for (i = 0; i < N; i++)//計算各個活動的最早開始時間和最遲開始時間
              for (iter = begin(i); iter != end(i); iter++)
                     if (Ve[i] == Vl[iter->vID] - iter->cost) CA.push_back(CriAct(i, iter->vID));

       return true;
}

      同樣的在類的外面可以通過outCriAct得到結(jié)果，是一個const引用。如下的測試程序，數(shù)據(jù)來自殷版：

#include
using namespace std;
#include "ActivityNetwork.h"
int main()
{
      Network > a;
      a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);
      a.insertV(5); a.insertV(6);a.insertV(7);a.insertV(8);
      a.insertE(0,1,6);a.insertE(0,2,4);a.insertE(0,3,5);
      a.insertE(1,4,1);a.insertE(2,4,1);a.insertE(3,5,2);
      a.insertE(4,6,9);a.insertE(4,7,7);a.insertE(5,7,4);
      a.insertE(6,8,2);a.insertE(7,8,4);
      ActivityNetwork b(&a);

      if (b.CriPath())
       for (int j = 0; j < b.outCriAct.size(); j++)
              cout <<'<'<' << ' ';
      return 0;
}

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——圖（總結(jié)）    happycock（原作）
要害字     圖

      以上就是現(xiàn)在的教科書里面，圖的全部內(nèi)容了。寫完之后，茫茫然，不知道學(xué)完之后有什么用……就像我在開篇寫的，圖的應(yīng)用太廣泛了，以至于現(xiàn)在覺得圖“沒什么用”——很希奇的邏輯，只有仔細(xì)體味才能覺察到寫教科書的人的無奈。

      不同于前面的鏈表和樹，在圖這里，儲存方法不是重點，我們更多的注重力放在了算法上。我在寫程序的時候，也盡量做到了算法和儲存方法無關(guān)。然而算法實際上就是現(xiàn)實問題的抽象，假如我們的常識所不及，我們也就沒有辦法來介紹算法，反過來說，幾乎遇不到的問題，我們也不會對它的算法感愛好。

      因此，在圖的算法里面，由鋪設(shè)管道引出了最小生成樹，由提高通信、交通網(wǎng)絡(luò)可靠性引出了關(guān)節(jié)點和重連通分量，由地圖尋徑引出了最短路徑，由工程預(yù)算引出了要害路徑。這些恐怕是我們能夠理解的全部了，假如再來一個電氣網(wǎng)絡(luò)計算，沒點物理知識恐怕是要完。

      但即使這樣，上面的各個算法仍然離我們很遠(yuǎn)，我們大多數(shù)人恐怕永遠(yuǎn)都不會知道管道是怎么鋪的。我想，這里面除了最短路徑能引起大多數(shù)人的愛好之外，其他的就只能走馬觀花的看看罷了。這也使得圖的學(xué)習(xí)很像“聾子的耳朵”，真正接觸到圖的用途的人不多，并且即使用到圖，也僅僅是個別的算法。

      正像數(shù)據(jù)結(jié)構(gòu)教學(xué)的通病一樣，學(xué)無所用經(jīng)常導(dǎo)致學(xué)無所成，前面的鏈表、樹好歹還能做點什么東西出來，到了圖這里，除了做個導(dǎo)游系統(tǒng)，我們也做不出別的什么了。寫到這里很無奈，但我也只能是無奈……

      那么，學(xué)完了圖，我們應(yīng)該把握什么呢，是上面零散的算法嗎？我的看法是，不是。我覺得我們更應(yīng)該知道那些算法是怎么“創(chuàng)造”出來的，假如碰到了類似的問題，能不能“派生”出新的算法。因此，我覺得《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-C++語言描述》這本書，將圖的最小生成樹、最短路徑、拓?fù)渑判蛩惴ǚ诺搅素澙匪惴ɡ镏v解，是一種更為合理的安排。

      最后對在學(xué)習(xí)圖時像我一樣茫然的人深表同情。

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——后記    happycock（原作）
要害字     數(shù)據(jù)結(jié)構(gòu)

      這回真的是后記了，也就是到了這些文章結(jié)束的時候了。雖然還有排序和查找兩大算法系沒有講，但是對于“數(shù)據(jù)結(jié)構(gòu)”而言，上面應(yīng)該是全部了。并且這些文章加在一起已經(jīng)很長了，每次打開Word來編輯，跳到末頁總是不那么順暢，是到了結(jié)束的時候了。對于那兩大算法系，我預(yù)備另外再開一個系列，姑且就叫做《數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）續(xù)》吧。忽然發(fā)現(xiàn)，在安排文章結(jié)構(gòu)上不知不覺的受了《計算機編程藝術(shù)》的影響了。

      我的參考書主要是三本，《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）》（殷人昆等），《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（嚴(yán)蔚敏、吳偉民），《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-C++語言描述》（中譯名，具體信息可查china-pub）。

      能寫完這些文章，首先要感謝C++語言，假如讓我拿C來寫，沒準(zhǔn)中途就放棄了。前不久還看到有人爭論數(shù)據(jù)結(jié)構(gòu)用什么語言描述最合適，有人還在堅持用C最好，按照他的看法，匯編沒準(zhǔn)是最好的（有愛好可以看看《計算機編程藝術(shù)》是拿什么語言寫的）。從ADT的思想來看，C是不合適的，因為C要把數(shù)據(jù)和數(shù)據(jù)上的操作封裝在一起非常的麻煩，并且只有利用文件來組織這種關(guān)系，而對于初學(xué)者來說，多模塊編譯鏈接本身就是一個很玄的事，當(dāng)年學(xué)C語言的時候這部分都沒敢看。而C++的類能非常完美的表達ADT的思想，并且模板、重載、繼續(xù)能更清楚的表述數(shù)據(jù)結(jié)構(gòu)之間的聯(lián)系。關(guān)于C++在解決問題上比C的優(yōu)勢，可以看看《C++沉思錄》，有非常有說服力的例子，當(dāng)然，從運行效率來說，C要強于C++。

      然而當(dāng)選用了C++之后，有件事就非常尷尬了，就是STL。常用的數(shù)據(jù)結(jié)構(gòu)、算法都已經(jīng)作為C++標(biāo)準(zhǔn)的一部分了，我就看到一本書是用STL來描述數(shù)據(jù)結(jié)構(gòu)的（只看到了書名，沒看到內(nèi)容）。前面的三部分，線性表在STL里全部都有現(xiàn)成的（變長數(shù)組、鏈表、隊列、棧），二叉搜索樹在SGI－STL里有紅黑樹的實現(xiàn)，只有圖標(biāo)準(zhǔn)庫沒有提供，但是圖最重要的是一堆算法。排序、查找在STL里也有現(xiàn)成的。

      這讓我想起了“程序員＝民工”的論調(diào)，的確，現(xiàn)在的語言、開發(fā)工具在給程序員提供了便利的同時，也限制了程序員的思維，養(yǎng)成了他們的惰性?，F(xiàn)在編程就是在Framework里面改寫若干的函數(shù)，在我們感到這種方式的便利的同時，也越來越感到自己力量的渺小。也許人就是種希奇的動物。

      或許數(shù)據(jù)結(jié)構(gòu)這門課程根本就不是讓你把握那些鏈表、樹是如何實現(xiàn)的。開設(shè)這門課第一個目的是讓你懂得“數(shù)據(jù)結(jié)構(gòu)＋算法＝程序”，第二個目的是培養(yǎng)數(shù)據(jù)抽象的能力。當(dāng)這兩個目的達到的同時，你也就具備了解決現(xiàn)實未知問題的能力，遺憾的是，大多數(shù)連把握已有的數(shù)據(jù)結(jié)構(gòu)的目標(biāo)都沒達到。出于這個原因，我總是建議你看看《計算機編程藝術(shù)》，這部有無數(shù)贊譽的巨著。最好不要買紙版的，弄個電子版就行了，紙版的恐怕會嚇得你不敢看，^_^。正如蓋茨說的，這本書很有趣，假如你不把它當(dāng)成參考書，你一定會有新的體會。

      所有的源程序都已打包，MyDS是線性鏈?zhǔn)浇Y(jié)構(gòu)，MyTree是樹結(jié)構(gòu)，Graph是圖結(jié)構(gòu)。加上這系列的WORD文檔，打成一個zip包，初步計劃放到C++中國聯(lián)盟的FTP上，下面是論壇的網(wǎng)址http://www.cppcn.com/bbs/

      要想學(xué)好數(shù)據(jù)結(jié)構(gòu)，最好親自把所有的算法完成一遍，從這個角度說，我的源程序有負(fù)面作用。我的初衷是使那些照書調(diào)不出來的不會因為寫不出程序而影響了學(xué)習(xí)的信心，究竟書上的錯漏在所難免，對自學(xué)的人和在照本宣科老師手下飽受煎熬的人來說，我的源程序應(yīng)該能起到預(yù)期的作用。

      本系列到此結(jié)束，續(xù)篇再見吧。

上一篇：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——圖（1&2&3&4）

下一篇：雙人黑白棋子游戲