十、裝配火車的樂趣

      國慶放假結束了，***天真是不想來上班啊，接著國慶之前的吧，上一篇寫的是利用數組實現堆棧的結構，使用數組的兩個致命的弱點是大小必須在使用前指定和效率非常差。那么先前的大牛們就開始思考如何提高效率呢？而在C/C++語言里有一種可以直接操作內存的東西叫做指針并且可以動態指定大小，于是不得不讓人思考怎么樣利用指針來克服原有的弱點重新實現數據結構。

     在使用指針實現之前，先看看數組為什么能實現堆棧等類似的結構，首先，一個數組可以通過下標來進行遍歷，也就是說可以讓我們從一個元素尋訪到下一個元素或者某一個元素，第二個，數組可以包含元素。那么我們需要用指針也構造出具有這樣兩個特點的一個結構出來，也就是說，這個結構里面必須包含一個元素另外至少可以允許我們訪問到下一個元素，也就是可以練成一個整體。在這種思維的趨勢下，我們可以確定的是一個結構要包含元素很簡單，只要給他聲明一個成員變量就可以了，那么如何使用某一個方法來讓其可以在總體上標示自己或者訪問到下一個元素呢？我們可以利用指針，所以在創建堆棧之前，我們首先需要做的是需要創建一個這樣的結構，一般情況下將這種結構成為節點（Node),節點的意思是“是在運行時存在的物理元素,它表示了一種可計算的資源,它通常至少有一些記憶能力和處理能力。”從這個定義上也可以看出節點的特征。

struct Node{ 
     char ele; 
        Node* next;     
 }; 

     其實你可以把Node想象成為一節火車車廂，里面的元素就是火車里面的負載，指針就是火車車廂連接處的掛鉤，通過這個掛鉤連接成為一個整體的火車。其實這個小小的struct包含了很多計算機知識，你可以問問自己這個Node*寫成Node為什么就不行了？

     好了，有了這個車廂，那么下面就需要利用這個車廂組成火車，使用Node的一個好處就是可以自由裝配，雖然在堆棧這個結構中還看不出來的這個好處，但是在后面的結構中這個好處會越來越明顯的體現出來。想象著這樣一個火車是停在車站里面的，車頭前面是一個站臺，也就是說這個火車的前面沒有路了，這里也有一個細節，對于這個車頭，你既可以把它看做一個普通車廂也可以把它看做是一個特殊的車廂，把它看做是一個不能搭載乘客的車廂，它的作用是表明這后面是一個火車，它沒有元素，在實現上這樣一個節點叫做頭節點。我們為了簡單起見，采用***種方式，當然后面我也會特別再描述一下這個問題的。回到火車的問題上來，下面我們要裝配這個火車，火車的前面已經沒有鐵軌了，我們想裝配火車只能從或者的尾部開始一節一節的車廂裝配上去。裝配的辦法就是將火車車廂連接的掛鉤一個一個連接起來，這樣就可以組成一個火車，當要去掉一個車廂也只能從尾部一個一個的去掉車廂，這樣就是一個堆棧的結構。

     先看看頭文件的組成吧。

class Stack{ 
public : 
    Stack(); 
    ~Stack(); 
 
    void Push(char ele); 
    char Pop(); 
    int Top(); 
    char GetValue(int Pos); 
    bool CheckEmpty(); 
    int GetCount(); 
 
private: 
    Node *cur;  
    int count; 
}; 

    大部分和使用數組的實現的差不多，不同的是構造函數之中沒有大小了，因為使用指針可以動態的制定大小，還有一個就是成員變量換成了節點，這就好比一節車廂。下面就要思考如何實現了，構造函數就是初始化，構造上面說的一個火車，最開始什么都沒有的情況下應該先把火車頭先開來放好，然后這個火車頭后面什么也沒有連接，在程序上也就是指針指向null，你可以理解為火車頭后面的掛鉤掛著nothing。然后就是push，如果現在要在后面掛一節車廂，那么就是將車廂開來（聲明一個新的節點），用后一節車廂的掛鉤掛上前面面一節車廂（在程序上實現就是將當前Node結構的指針指向“->"這個新添加的節點，符號"->"我認為是C/C++里最形象的符號，因為看到它就有指向的意思），同時需要標示***一節車廂的位置，因為不然你就不知道下一節新來的車廂掛哪了。再接下來是Pop，你可以想象是卸載掉一個車廂，因為你首先要讓車廂里的乘客下車，所以在卸載之前你得先找個地讓乘客下車（聲明一個變量保存Node中的元素），然后重新找到卸載后***一個節點，將掛鉤取下（消除這個節點的內存）。***一個是析構函數，你可以理解為如果我裝配好的整列火車都不要了怎么辦（當然這個比方不怎么恰當），你需要一個一個的將車廂都卸載掉，讓其不要占鐵軌資源。使用Node實現的堆棧如下：

Stack::Stack() 
{ 
    cur=new Node(); 
    count=0; 
} 
 
Stack::~Stack() 
{ 
    Node* tmp=new Node(); 
    while(cur->next!=NULL) 
    { 
        tmp=cur;     
        cur=tmp->next; 
        delete tmp; 
    } 
    delete tmp; 
    delete []stackArray; 
} 
 
bool Stack::CheckEmpty() 
{ 
    return (count==0); 
} 
 
void Stack::Push(char ele) 
{ 
  
    Node *tmp=new Node(); 
    tmp->ele=ele; 
    tmp->next=NULL; 
 
    if(count==0) 
        cur->ele=ele; 
    else 
    { 
        tmp->next=cur; 
        cur=tmp; 
    } 
    count++; 
 
} 
 
char Stack::Pop() 
{ 
    if(count==0) 
    { 
        cout<<"stack is empty!"<<endl; 
        return -1; 
    } 
    --count; 
    Node *tmp=cur; 
    char result=cur->ele; 
    if(count!=0) 
    { 
       
       cur=cur->next;   
       delete tmp; 
    } 
    else 
    { 
        cur=new Node(); 
    } 
    return result; 
} 
 
char Stack::GetValue(int Pos) 
{       
    Node *tmp=new Node; 
    tmp=cur; 
    int i=0; 
    while(i<Pos) 
    { 
        tmp=tmp->next; 
        i++; 
    } 
    return tmp->ele; 
} 
 
  
 
 
int Stack::GetCount()  
{ 
    return count; 
} 

     我們看一下效果，同樣還是使用前面的幫助實現交互的函數：

原文鏈接：http://www.cnblogs.com/ZXYloveFR/archive/2012/10/08/2714707.html

【編輯推薦】