十、裝配火車的樂趣

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

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

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

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

     好了，有了這個車廂，那么下面就需要利用這個車廂組成火車，使用Node的一個好處就是可以自由裝配，雖然在堆棧這個結(jié)構(gòu)中還看不出來的這個好處，但是在后面的結(jié)構(gòu)中這個好處會越來越明顯的體現(xiàn)出來。想象著這樣一個火車是停在車站里面的，車頭前面是一個站臺，也就是說這個火車的前面沒有路了，這里也有一個細節(jié)，對于這個車頭，你既可以把它看做一個普通車廂也可以把它看做是一個特殊的車廂，把它看做是一個不能搭載乘客的車廂，它的作用是表明這后面是一個火車，它沒有元素，在實現(xiàn)上這樣一個節(jié)點叫做頭節(jié)點。我們?yōu)榱撕唵纹鹨姡捎?**種方式，當然后面我也會特別再描述一下這個問題的?；氐交疖嚨膯栴}上來，下面我們要裝配這個火車，火車的前面已經(jīng)沒有鐵軌了，我們想裝配火車只能從或者的尾部開始一節(jié)一節(jié)的車廂裝配上去。裝配的辦法就是將火車車廂連接的掛鉤一個一個連接起來，這樣就可以組成一個火車，當要去掉一個車廂也只能從尾部一個一個的去掉車廂，這樣就是一個堆棧的結(jié)構(gòu)。

     先看看頭文件的組成吧。

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; 
}; 

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

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; 
} 

     我們看一下效果，同樣還是使用前面的幫助實現(xiàn)交互的函數(shù)：

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

【編輯推薦】