十、裝配火車(chē)的樂(lè)趣

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

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

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

     其實(shí)你可以把Node想象成為一節(jié)火車(chē)車(chē)廂，里面的元素就是火車(chē)?yán)锩娴呢?fù)載，指針就是火車(chē)車(chē)廂連接處的掛鉤，通過(guò)這個(gè)掛鉤連接成為一個(gè)整體的火車(chē)。其實(shí)這個(gè)小小的struct包含了很多計(jì)算機(jī)知識(shí)，你可以問(wèn)問(wèn)自己這個(gè)Node*寫(xiě)成Node為什么就不行了？

     好了，有了這個(gè)車(chē)廂，那么下面就需要利用這個(gè)車(chē)廂組成火車(chē)，使用Node的一個(gè)好處就是可以自由裝配，雖然在堆棧這個(gè)結(jié)構(gòu)中還看不出來(lái)的這個(gè)好處，但是在后面的結(jié)構(gòu)中這個(gè)好處會(huì)越來(lái)越明顯的體現(xiàn)出來(lái)。想象著這樣一個(gè)火車(chē)是停在車(chē)站里面的，車(chē)頭前面是一個(gè)站臺(tái)，也就是說(shuō)這個(gè)火車(chē)的前面沒(méi)有路了，這里也有一個(gè)細(xì)節(jié)，對(duì)于這個(gè)車(chē)頭，你既可以把它看做一個(gè)普通車(chē)廂也可以把它看做是一個(gè)特殊的車(chē)廂，把它看做是一個(gè)不能搭載乘客的車(chē)廂，它的作用是表明這后面是一個(gè)火車(chē)，它沒(méi)有元素，在實(shí)現(xiàn)上這樣一個(gè)節(jié)點(diǎn)叫做頭節(jié)點(diǎn)。我們?yōu)榱撕?jiǎn)單起見(jiàn)，采用***種方式，當(dāng)然后面我也會(huì)特別再描述一下這個(gè)問(wèn)題的?；氐交疖?chē)的問(wèn)題上來(lái)，下面我們要裝配這個(gè)火車(chē)，火車(chē)的前面已經(jīng)沒(méi)有鐵軌了，我們想裝配火車(chē)只能從或者的尾部開(kāi)始一節(jié)一節(jié)的車(chē)廂裝配上去。裝配的辦法就是將火車(chē)車(chē)廂連接的掛鉤一個(gè)一個(gè)連接起來(lái)，這樣就可以組成一個(gè)火車(chē)，當(dāng)要去掉一個(gè)車(chē)廂也只能從尾部一個(gè)一個(gè)的去掉車(chē)廂，這樣就是一個(gè)堆棧的結(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ù)組的實(shí)現(xiàn)的差不多，不同的是構(gòu)造函數(shù)之中沒(méi)有大小了，因?yàn)槭褂弥羔樋梢詣?dòng)態(tài)的制定大小，還有一個(gè)就是成員變量換成了節(jié)點(diǎn)，這就好比一節(jié)車(chē)廂。下面就要思考如何實(shí)現(xiàn)了，構(gòu)造函數(shù)就是初始化，構(gòu)造上面說(shuō)的一個(gè)火車(chē)，最開(kāi)始什么都沒(méi)有的情況下應(yīng)該先把火車(chē)頭先開(kāi)來(lái)放好，然后這個(gè)火車(chē)頭后面什么也沒(méi)有連接，在程序上也就是指針指向null，你可以理解為火車(chē)頭后面的掛鉤掛著nothing。然后就是push，如果現(xiàn)在要在后面掛一節(jié)車(chē)廂，那么就是將車(chē)廂開(kāi)來(lái)（聲明一個(gè)新的節(jié)點(diǎn)），用后一節(jié)車(chē)廂的掛鉤掛上前面面一節(jié)車(chē)廂（在程序上實(shí)現(xiàn)就是將當(dāng)前Node結(jié)構(gòu)的指針指向“->"這個(gè)新添加的節(jié)點(diǎn)，符號(hào)"->"我認(rèn)為是C/C++里最形象的符號(hào)，因?yàn)榭吹剿陀兄赶虻囊馑迹?，同時(shí)需要標(biāo)示***一節(jié)車(chē)廂的位置，因?yàn)椴蝗荒憔筒恢老乱还?jié)新來(lái)的車(chē)廂掛哪了。再接下來(lái)是Pop，你可以想象是卸載掉一個(gè)車(chē)廂，因?yàn)槟闶紫纫屲?chē)廂里的乘客下車(chē)，所以在卸載之前你得先找個(gè)地讓乘客下車(chē)（聲明一個(gè)變量保存Node中的元素），然后重新找到卸載后***一個(gè)節(jié)點(diǎn)，將掛鉤取下（消除這個(gè)節(jié)點(diǎn)的內(nèi)存）。***一個(gè)是析構(gòu)函數(shù)，你可以理解為如果我裝配好的整列火車(chē)都不要了怎么辦（當(dāng)然這個(gè)比方不怎么恰當(dāng)），你需要一個(gè)一個(gè)的將車(chē)廂都卸載掉，讓其不要占鐵軌資源。使用Node實(shí)現(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; 
} 

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

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

【編輯推薦】