你所能用到的數(shù)據(jù)結(jié)構(gòu)（六）：不一定很枯燥

作者：一心一懌 2012-10-16 09:52:27

大家在大學(xué)時(shí)代學(xué)數(shù)據(jù)結(jié)構(gòu)必定是枯燥乏味的。數(shù)據(jù)結(jié)構(gòu)是一本催眠的書(shū)，我想對(duì)于大多數(shù)人應(yīng)該是這樣的，當(dāng)然對(duì)我也是，看著一大堆的算法，結(jié)構(gòu)模型，不想睡覺(jué)那應(yīng)該可以歸結(jié)為geek一類(lèi)的，但是呢，后來(lái)我找到了一個(gè)辦法，就是動(dòng)手，我發(fā)現(xiàn)無(wú)論看的時(shí)候有多無(wú)聊，寫(xiě)寫(xiě)程序所帶來(lái)的那種興奮感和成就感現(xiàn)在已經(jīng)成為了支撐看完我一本書(shū)的精神動(dòng)力。

八、數(shù)據(jù)結(jié)構(gòu)不一定很枯燥

正如我現(xiàn)在實(shí)習(xí)的公司的一個(gè)同事說(shuō)的那樣，數(shù)據(jù)結(jié)構(gòu)是一本催眠的書(shū)，我想對(duì)于大多數(shù)人應(yīng)該是這樣的，當(dāng)然對(duì)我也是，看著一大堆的算法，結(jié)構(gòu)模型，不想睡覺(jué)那應(yīng)該可以歸結(jié)為geek一類(lèi)的，但是呢，后來(lái)我找到了一個(gè)辦法，就是動(dòng)手，我發(fā)現(xiàn)無(wú)論看的時(shí)候有多無(wú)聊，寫(xiě)寫(xiě)程序所帶來(lái)的那種興奮感和成就感現(xiàn)在已經(jīng)成為了支撐看完我一本書(shū)的精神動(dòng)力，所以我想在我開(kāi)始從堆棧到圖的過(guò)程中，我盡我所能讓所寫(xiě)的程序有更大的互動(dòng)性，由于我的目的是能夠讓一些初學(xué)者對(duì)于編程寫(xiě)代碼更感興趣，而且我這水平也只能給初學(xué)者提供一點(diǎn)我以前學(xué)習(xí)的經(jīng)驗(yàn)了，我本來(lái)想用MFC，用圖形化界面來(lái)增加交互性的，后來(lái)我發(fā)現(xiàn)對(duì)于一個(gè)沒(méi)有學(xué)過(guò)MFC的人，如果想很簡(jiǎn)短的說(shuō)清楚還是很難的，所以我只能盡我所能在DOS的黑屏下開(kāi)發(fā)出一些交互性來(lái)了。我始終相信最簡(jiǎn)單的東西才是最根本的，DOS界面雖然簡(jiǎn)陋，沒(méi)有界面，更不可能有WPF這些技術(shù)做出來(lái)的更炫更好的界面，但是往往就是這種簡(jiǎn)陋的界面才能更容易讓人去重視本質(zhì)和核心的東西。雖然說(shuō)我是想能夠提供更多的交互性，但是畢竟本人水平有限，加上思維僵化，所以我盡我最大的努力好了。

九、你不能小看任何簡(jiǎn)單的東西

堆棧，稍微對(duì)數(shù)據(jù)結(jié)構(gòu)有點(diǎn)了解的人，都會(huì)覺(jué)得這個(gè)結(jié)構(gòu)太簡(jiǎn)單了，其模型就是先進(jìn)后出，可以想象成為一摞盤(pán)子，盤(pán)子一個(gè)疊一個(gè)的，在正常情況下，你會(huì)永遠(yuǎn)往上摞盤(pán)子并且從上面取盤(pán)子，這樣抽象出來(lái)的一個(gè)結(jié)構(gòu)大體可以稱(chēng)之為堆棧。如果你玩過(guò)三國(guó)殺，你被樂(lè)不思蜀了，這時(shí)候閃電輪到了你的頭上，先判斷樂(lè)不思蜀還是閃電？根據(jù)規(guī)則是后來(lái)的先判，于是翻牌判斷閃電，然后樂(lè)不思蜀。這也就是一個(gè)堆棧啊！這個(gè)結(jié)構(gòu)廣泛的應(yīng)用于我們生活中，同時(shí)也廣泛的應(yīng)用于計(jì)算機(jī)中，電腦程序之所以能夠運(yùn)行，如果沒(méi)有堆棧這個(gè)結(jié)構(gòu)是不行的，你寫(xiě)的函數(shù)能夠正確的被調(diào)用，沒(méi)有堆棧的幫助也是不可以的。所以說(shuō)，看起來(lái)不起眼的結(jié)構(gòu)往往最實(shí)用，雖然結(jié)合堆棧的算法相比使用圖進(jìn)行的算法要簡(jiǎn)單的多，但是就實(shí)際運(yùn)用來(lái)說(shuō)，人們總是會(huì)選那些簡(jiǎn)單，實(shí)用，高效的東西。對(duì)堆棧的學(xué)習(xí)不僅僅是對(duì)數(shù)據(jù)結(jié)構(gòu)整個(gè)的一個(gè)啟蒙而且更是了解數(shù)據(jù)結(jié)構(gòu)到底在實(shí)際中有多大應(yīng)用的一個(gè)起點(diǎn)，大學(xué)學(xué)的幾門(mén)基礎(chǔ)課，我覺(jué)得如果你想成為一個(gè)工程師，那么你用到最多的三門(mén)課應(yīng)該是數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)網(wǎng)絡(luò)和操作系統(tǒng)。

那么，如何實(shí)現(xiàn)這樣一個(gè)先進(jìn)后出的結(jié)構(gòu)呢？首先，堆棧肯定是一種集合，一種具有特殊性質(zhì)的集合，那么很自然的想到利用數(shù)組來(lái)實(shí)現(xiàn)，比方說(shuō)我們有一個(gè)20個(gè)長(zhǎng)度的數(shù)組a，我們將第一個(gè)數(shù)放在索引為0的位置上，現(xiàn)在第二個(gè)數(shù)，我們將第一個(gè)數(shù)向后挪一位，挪到a[1],然后將新數(shù)放到a[0],依次類(lèi)推，這樣取數(shù)的時(shí)候永遠(yuǎn)取a[0]的數(shù)，然后將后面的數(shù)前移，這樣就能達(dá)到一個(gè)先進(jìn)去的數(shù)最后才能取到的目的。但是這種實(shí)現(xiàn)方案的最大的缺點(diǎn)是你每次都要移動(dòng)數(shù)組，這對(duì)計(jì)算機(jī)所造成的開(kāi)銷(xiāo)是非常大的，特別是對(duì)數(shù)組這樣一個(gè)效率很低的結(jié)構(gòu)（別小看數(shù)組，數(shù)組也是一種數(shù)據(jù)結(jié)構(gòu)）。那么，我們可不可以有所改進(jìn)呢？可以很自然的想到如果我將每次新進(jìn)來(lái)的元素都放在數(shù)組的末尾，也就是每次都在數(shù)組的最末尾添加元素，那樣對(duì)于插入操作的效率是最快的，那就將到來(lái)的數(shù)依次從0插入，如果需要取數(shù)的話(huà)，那么永遠(yuǎn)從最后一個(gè)數(shù)開(kāi)始取，同時(shí)用一個(gè)變量標(biāo)示數(shù)組中實(shí)際有多少元素，無(wú)疑，這樣對(duì)于效率的提高是非常大的。還有沒(méi)有更大的效率的實(shí)現(xiàn)方式呢？當(dāng)然，使用指針，永遠(yuǎn)記住，指針是一個(gè)很好的工具，如果你所做的是大型的系統(tǒng)，那么良好的使用指針?biāo)鶐?lái)的效率的提高是會(huì)讓你感到驚奇的一件事。對(duì)于使用指針實(shí)現(xiàn)的堆棧，我準(zhǔn)備下一節(jié)再寫(xiě)。

好，基本思路確定了，那么我們就開(kāi)始寫(xiě)了（這里我默認(rèn)你已經(jīng)懂得C++基本知識(shí)，不然你也不會(huì)看數(shù)據(jù)結(jié)構(gòu)了），但是我們還發(fā)現(xiàn)一個(gè)問(wèn)題，如果使用數(shù)組，那么我怎么知道我要用的堆棧有多大？這個(gè)解決的辦法很多，第一個(gè)就是申明一個(gè)很大的數(shù)作為這個(gè)數(shù)組的大小，但是很大是多大？永遠(yuǎn)有比很大更大的數(shù)，更不用說(shuō)這樣做導(dǎo)致的內(nèi)存浪費(fèi)，可能在你平時(shí)編寫(xiě)小程序的時(shí)候，你無(wú)法體會(huì)到內(nèi)存浪費(fèi)對(duì)于一個(gè)程序員深深地痛，另外一個(gè)痛是內(nèi)存泄露，所以有些東西還是先培養(yǎng)出一種習(xí)慣比較好的。第二個(gè)就是使用指針動(dòng)態(tài)申請(qǐng)數(shù)組的大小，這樣的話(huà)，我們需要一個(gè)含有參數(shù)的構(gòu)造函數(shù)（如果你不知道什么叫構(gòu)造函數(shù)的話(huà)，那么。。。那么。。。那么你可以關(guān)了這個(gè)界面，不過(guò)我的打算是把數(shù)據(jù)結(jié)構(gòu)寫(xiě)完了，寫(xiě)介紹基礎(chǔ)C++的文章，那個(gè)時(shí)候你可以再來(lái)看看），這個(gè)參數(shù)你要申明的數(shù)組的大小。

對(duì)于堆棧這個(gè)類(lèi)的成員函數(shù)（突然覺(jué)得專(zhuān)業(yè)名詞好多？其實(shí)你可以去學(xué)學(xué)C++），添加元素的專(zhuān)業(yè)叫法是push（壓），取出元素的專(zhuān)業(yè)叫法是pop(彈出),你可以想象那種前幾年流行過(guò)的一種存硬幣的圓柱狀物品，你可以把硬幣一個(gè)一個(gè)壓入那里面，然后彈出最上面的硬幣。除了這兩個(gè)，還可以有的是檢查堆棧是否為空，返回棧頂元素（不彈出）和返回堆棧大小，為了增加交互性和盡量簡(jiǎn)單，我的實(shí)現(xiàn)里加入了一個(gè)遍歷堆棧元素的成員函數(shù)（這個(gè)是不好的，違背了堆棧的原理）。那么好，先看看.h文件。

#ifndef STACK_H 
 #define STACK_H 
 class Stack{ 
 public : 
     Stack(int size); 
     ~Stack(); 
  
     void Push(int ele); 
     int Pop(); 
     int Top(); 
     int GetValue(int Pos); 
     bool CheckEmpty(); 
     int GetCount(); 
  
 private: 
     int *stackArray; 
       
     int count; 
 }; 
 #endif

.h文件我的理解對(duì)于初學(xué)者可以將它看做一個(gè)索引，它讓你看看一個(gè)類(lèi)里大概有什么東西。看完索引，下面看看他的內(nèi)容吧。

Stack::Stack(int size) 
 { 
     stackArray=new int[size]; 
     for(int i=0;i<size;i++) stackArray[i]=0; 
     count=0; 
 } 
  
 Stack::~Stack() 
 { 
     delete []stackArray; 
 } 
  
 bool Stack::CheckEmpty() 
 { 
     return (count==0); 
 } 
  
 void Stack::Push(int ele) 
 { 
     stackArray[count]=ele; 
     ++count; 
 } 
  
 int Stack::Pop() 
 { 
     --count; 
     int result=stackArray[count]; 
     stackArray[count]=0; 
     return result; 
 } 
  
 int Stack::GetValue(int Pos) 
 {      
     return stackArray[count-Pos-1]; 
 } 
  
   
  
  
 int Stack::GetCount()  
 { 
     return count; 
 }

對(duì)于壓入我采用的是往數(shù)組的后面添加元素的方法，彈出是的話(huà)是將最后一個(gè)元素返回，然后設(shè)為0，同時(shí)堆棧的大小減一。同時(shí)，請(qǐng)大家注意，我的實(shí)現(xiàn)里面沒(méi)有加入一些對(duì)于錯(cuò)誤情況的判斷，比如如果已經(jīng)沒(méi)有元素了，那么彈出是不允許的，如果元素已經(jīng)滿(mǎn)了，那么壓入也是不允許的，這個(gè)部分我真心是想留給初學(xué)者做個(gè)練習(xí)，當(dāng)然，如果你有興趣的話(huà)。還有就是目前實(shí)現(xiàn)的堆棧只能壓入整數(shù)，我沒(méi)有使用模板或者typedef是因?yàn)槲蚁脒€是簡(jiǎn)單點(diǎn)比較好。

在大多數(shù)數(shù)據(jù)結(jié)構(gòu)書(shū)里面堆棧應(yīng)用舉例就是隨機(jī)生成多少個(gè)數(shù)，然后壓入，彈出，看看輸出結(jié)果是什么，我想的話(huà)，其實(shí)可以使用一個(gè)菜單，讓使用者每次選壓入還是彈出，然后觀(guān)看變化，所以我想了這樣兩個(gè)函數(shù)。

void printCube(int num) 
{ 
    cout<<"   "<<num<<"   "<<endl; 
    cout<<"*******"<<endl;  
} 
 
void menu() 
{ 
    cout<<"Please select one operation:"<<endl; 
    cout<<"1-Push"<<endl; 
    cout<<"2-Pop"<<endl; 
    cout<<"0-Quit"<<endl; 
}

當(dāng)然，你可以在我的基礎(chǔ)上擴(kuò)展，那么主函數(shù)如下所示：

void main() 
 { 
         int order,input; 
     menu(); 
      int size=20; 
       Stack s(size); 
     while(cin>>order) 
     { 
       if(order==1) 
       { 
          cin>>input; 
          s.Push(input); 
       } 
       if(order==2) 
           s.Pop(); 
       if(order==0) 
           break; 
  
       for(int i=0;i<s.GetCount();i++) 
            printCube(s.GetValue(i)); 
     } 
   
     int i; 
     cin>>i; 
      
 }