第10章_線性數(shù)據(jù)結(jié)構(gòu).ppt.ppt

1、0,西安交通大學(xué) 計算機教學(xué)實驗中心,第10章 線性數(shù)據(jù)結(jié)構(gòu),計算機程序設(shè)計（C+）,內(nèi)容提要,數(shù)據(jù)間的邏輯聯(lián)系 生命游戲 括號匹配問題 荷蘭國旗問題,1,數(shù)據(jù)間的邏輯聯(lián)系,數(shù)據(jù)結(jié)構(gòu)（Data Structure） 計算機中存儲、組織數(shù)據(jù)的方式 本課程目的 不是數(shù)據(jù)結(jié)構(gòu)課程 沒有按照數(shù)據(jù)結(jié)構(gòu)的概念來組織內(nèi)容 以簡單的數(shù)據(jù)結(jié)構(gòu)概念為契機來幫助同學(xué)理解計算思維的有關(guān)重要概念 對數(shù)據(jù)結(jié)構(gòu)感興趣的同學(xué)可以通過學(xué)習(xí)相關(guān)專業(yè)書籍獲得更詳細(xì)的資訊,2,從數(shù)組談起 int array10=2,4,6,7,9,0,1,2,4,3; 該數(shù)組在內(nèi)存中的存儲結(jié)構(gòu)如下所示：,3,線性表(Linear List) 數(shù)據(jù)元

2、素之間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。 線性表在實際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。,4,線性表的基本運算,初始化線性表InitList( double array210; unsigned int array310; char array410; char* array510; 對于邏輯聯(lián)系相同的同一種數(shù)據(jù)結(jié)構(gòu)，必須根據(jù)數(shù)據(jù)類型的不同重復(fù)進行多次的定義。,7,泛型(Generic Programming),面向?qū)ο笤趯λ惴ǖ某橄竺枋龇矫娲嬖谌毕荨?class LinearList DataType data100; /最大元素為100個

3、public: bool IsEmpty(); int Length(); bool Find(int i, DataType ,8,template關(guān)鍵字,template class LinearList T data100; /最大元素為100個 public: bool IsEmpty(); int Length(); bool Find(int i, T ,9,LinearList aList; class LinearList int data100; /最大元素為100個 public: bool IsEmpty(); int Length(); bool Find(int i,

4、 int,10,泛型,泛型可以在幾乎無損于效率的情況下支持代碼的高度可復(fù)用性 說面向?qū)ο蟮睦^承實現(xiàn)了子類型的多態(tài)的話，那么泛型則是實現(xiàn)了類的參數(shù)的多態(tài)，兩者都是抽象機制的重要組成部分 繼承往往代表了不同的算法，但泛型往往代表了相同的算法不同的類型,11,和普通的數(shù)組相比，我們?nèi)绻胍獙崿F(xiàn)一個線性表類，至少有兩個問題需要解決 支持多種數(shù)據(jù)類型 長度可變，基本沒有最大長度的限制，但也不能過于浪費內(nèi)存,12,不能盲目開大數(shù)組 template class LinearList T data10000; public: . ;,13,動態(tài)內(nèi)存分配仍有缺陷 template class LinearLi

5、st T* data; int n;/線性表長度 public: LinearList(int k) n = k; data = new Tn; LinearList() delete data; . ;,14,正確的處理方案 當(dāng)所有有可能增加線性表長度的函數(shù)執(zhí)行過程中(包括Insert、線性表連接Concat等)，如果發(fā)現(xiàn)長度可能超過預(yù)先申請的長度，則重新申請一片更大的內(nèi)存空間，并把原內(nèi)存空間的數(shù)據(jù)拷貝進去，釋放掉原空間。（習(xí)題10-1）。,15,Dont Reinvent the Wheel,標(biāo)準(zhǔn)模板庫（STL，Standard Template Library） 包含了諸多在計算機科學(xué)領(lǐng)

6、域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法 為廣大C+程序員們提供了一個可擴展的應(yīng)用框架 高度體現(xiàn)了軟件的可復(fù)用性,16,vector,17,18,19,【例10-1】vector使用簡單示例。按要求編程完成以下功能： 1)聲明一個元素為int型的vector對象，插入13、75、38、35四個元素，打印出所有元素的值； 2)將vector中所有的元素值乘2，打印出所有元素的值。 3)輸出vector中所有元素的值，并在第2個元素后插入一個新元素88，再次打印出所有的值，以上均要求使用迭代器實現(xiàn)。 【問題分析】都是很基礎(chǔ)的功能，使用vector的相應(yīng)成員函數(shù)不難實現(xiàn)。需要注意的是迭代器(iterato

7、r)這個概念，在STL中非常常用，大家可以近似地理解為一種可以定位數(shù)據(jù)結(jié)構(gòu)內(nèi)部元素的智能指針，和直接使用下標(biāo)訪問相比，迭代器支持訪問多種不同的數(shù)據(jù)結(jié)構(gòu)，而且更加安全。有關(guān)迭代器的更多信息大家可以閱讀STL的相關(guān)書籍。,20,源程序,#include #include using namespace std; int main() vector intlist; int i; /初始化vector intlist.push_back(13); intlist.push_back(75); intlist.push_back(38); intlist.push_back(35);,21,/直接使用

8、下標(biāo)輸出 for(i=0;i:iterator listit; /注意迭代器訪問數(shù)據(jù)的方式 for(listit=intlist.begin();listit!=intlist.end();+listit) cout*listit ; coutendl;,22,listit=intlist.begin(); +listit; +listit; intlist.insert(listit,88); for(listit=intlist.begin();listit!=intlist.end();+listit) cout*listit ; coutendl; return 0; ,23,運行結(jié)果

9、,13 75 38 35 26 150 76 70 26 150 76 70 26 150 88 76 70,24,vector完整實現(xiàn)了一個線性表所需的所有功能(比我們設(shè)計的線性表類功能可要強大多了)，而且代碼久經(jīng)考驗，正確性和健壯性也有保證。所以我們應(yīng)當(dāng)熟練使用STL的常用數(shù)據(jù)結(jié)構(gòu)和算法，并應(yīng)用在自己的程序中，可以顯著提高程序開發(fā)的效率。 從另一個方面來看，倘若初學(xué)者純粹使用標(biāo)準(zhǔn)庫來開發(fā)程序，不知道這些強大的類庫是如何開發(fā)出來的，只知其然而不知其所以然，對技術(shù)的進一步提高也是很不利的。,25,生命游戲,生命游戲是英國數(shù)學(xué)家約翰何頓康威在1970年發(fā)明的。它最初于1970年10月在科學(xué)美國人

10、雜志中馬丁葛登能（Martin Gardner，19142010）的“數(shù)學(xué)游戲”專欄出現(xiàn)。生命游戲的學(xué)名稱為“元胞自動機”(Cellular Automaton,CA)。,26,一個二維矩形世界 這個世界中的每個方格居住著一個活著的或死了的細(xì)胞 一個細(xì)胞在下一個時刻的生死取決于相鄰八個方格中活著的或死了的細(xì)胞的數(shù)量。 相鄰方格活著的細(xì)胞數(shù)量過多，這個細(xì)胞會因為資源匱乏而在下一個時刻死去 如果周圍活細(xì)胞過少，這個細(xì)胞會因太孤單而死去,27,每個格子的生死遵循下面的原則： 如果一個細(xì)胞周圍有3個細(xì)胞為生（一個細(xì)胞周圍共有8個細(xì)胞），則該細(xì)胞為生（即該細(xì)胞若原先為死，則轉(zhuǎn)為生，若原先為生，則保持不變

11、）。 如果一個細(xì)胞周圍有2個細(xì)胞為生，則該細(xì)胞的生死狀態(tài)保持不變； 在其它情況下，該細(xì)胞為死（即該細(xì)胞若原先為生，則轉(zhuǎn)為死，若原先為死，則保持不變）。,28,生命游戲的一些有趣結(jié)構(gòu),29,【例10-2】根據(jù)上一節(jié)中生命游戲的介紹，嘗試做一次上帝，編寫一個程序來模擬這些生存在小格子之中的蕓蕓眾生。 【問題分析】由于生命游戲所處的世界是一個平面的、二維的世界，所以使用二維數(shù)組來模擬是一個很自然的想法。二維數(shù)組也是一種特殊的線性表，該線性表中的每一個元素也是一個線性表。類似地，三維、四維乃至N維數(shù)組都是線性表，N維線性表中的每一個元素是一個N-1維線性表。所以也可以使用STL中的vector來模擬這

12、個世界?？紤]到生命游戲中的世界大小是穩(wěn)定的，直接使用多維數(shù)組更加簡單，效率也更高。,30,const int maxrow=20,maxcol=60; class Life public: void initialize(); /初始化 void print(); /打印世界狀態(tài) void update();/根據(jù)當(dāng)前世界狀態(tài)，計算下一時刻狀態(tài) private: int gridmaxrow+2maxcol+2; int neighbor_count(int row,int col); ; 【問題分析】以上為Life類， 默認(rèn)的最大行數(shù)(長度)為20，最大列數(shù)(寬度)為60。考慮到還要檢查邊界

13、上格子中生命的鄰居的狀態(tài)，為了簡化邊界條件，設(shè)定的世界長寬均比最大行列數(shù)大2，這樣不必對邊界上的格子做特殊處理。,31,我們使用一個易于實現(xiàn)的字符界面來描繪這個世界。Life類中的print函數(shù)負(fù)責(zé)將世界的當(dāng)前狀態(tài)打印出來。私有函數(shù)neighbor_count用于計算給定坐標(biāo)格子的鄰居個數(shù)(即周圍8個格子中狀態(tài)為“活”的格子個數(shù))。公有函數(shù)update用于根據(jù)當(dāng)前時刻世界的狀態(tài)計算下一時刻世界的狀態(tài)。,32,/打印當(dāng)前世界狀態(tài) void Life:print() int row,col; coutnThe current Life configuration is:endl; for(row=

14、1;row=maxrow;row+) for(col=1;col=maxcol;col+) if(gridrowcol=1)cout*; else cout ; coutendl; coutendl; ,33,/計算給定坐標(biāo)格子的鄰居(周圍8個格子的活細(xì)胞)個數(shù) int Life:neighbor_count(int row,int col) int i,j; int count=0; for(i=row-1;i=row+1;i+) for(j=col-1;j=col+1;j+) count+=gridij; count-=gridrowcol; return count; ,34,/根據(jù)當(dāng)前

15、時刻世界的狀態(tài)計算下一時刻世界的狀態(tài) void Life:update() int row,col; /下一時刻狀態(tài)的緩沖存儲區(qū) int new_gridmaxrow+2maxcol+2; for(row=1;row=maxrow;row+) for(col=1;col=maxcol;col+) switch(neighbor_count(row,col) case 2: /2個鄰居，維持原狀態(tài) new_gridrowcol=gridrowcol; break; case 3: /3個鄰居，為生 new_gridrowcol=1; break; default: /其它情況，為死 new_gr

16、idrowcol=0; ,35,/從緩沖區(qū)copy到主存儲區(qū) for(row=1;row=maxrow;row+) for(col=1;col=maxcol;col+) gridrowcol=new_gridrowcol; ,36,void Life:initialize() /全部世界初始化為空 int row,col; for(row=0;row=maxrow+1;row+) for(col=0;col=maxcol+1;col+) gridrowcol=0; coutList the coordinates for living cellsendl; coutTerminate the

17、list with the special pair -1 -1endl;,37,/根據(jù)外界輸入初始化世界 cinrowcol; while(row!=-1|col!=-1) if(row=1 ,38,/處理用戶輸入，只允許用戶輸入y或n bool user_says_yes() int c; bool initial_response=true; do if(initial_response) cout(y,n)?flush; else coutRespond with either y or n:flush; do c=cin.get(); while(c=n|c= |c=t); init

18、ial_response=false; while(c!=y ,39,/提示信息輸出 void instructions() coutWelcome to Conways game of Life.endl; coutThis game uses a grid of sizemaxrow by maxcol in which endl; couteach cell can either be occupied by an organism or not.endl; coutThe occupied cells change from generation to generationendl;

19、coutaccording to the numbers of neighboring cells which are aliveendl; ,40,void main() Life configuration; instructions(); configuration.initialize(); configuration.print(); coutContinue viewing new generations?endl; while(user_says_yes() configuration.update(); configuration.print(); coutContinue v

20、iewing new generations?endl; ,41,運行結(jié)果,42,43,44,45,46,【思路擴展】上面給出的只是初始狀態(tài)的一種簡單配置，生命無法永存，其實如果精心的設(shè)置初始狀態(tài)的話，生命是可以永存的，大家可以嘗試尋找一下這些特定的狀態(tài)。提示：最簡單的一種永存狀態(tài)只需要3個初始細(xì)胞。,47,括號匹配問題,令人頭痛的四則運算練習(xí)題 118153612（6359）9 = ？ 需要按照先乘除、后加減的順序計算，同時還要考慮先計算小括號、中括號和大括號之內(nèi)的算式 直接編程進行四則運算對于初學(xué)者的我們來說過于復(fù)雜，現(xiàn)在討論的問題是四則運算問題的一個簡化版,48,【例10-3】給你一個表

21、達式，里面只包含(,),和,六種符號，編程序判斷這個字符串的括號匹配是否正確。 【問題分析】所謂括號匹配的正確性，是指該種括號匹配方式是否可能在實際的四則運算式（去除數(shù)字和運算符，只考慮括號）中出現(xiàn)。只需要括號配對即可，不需要遵循先小括號、后中括號，再大括號這樣的順序。比如：“（）”、“()”和“（）”這樣的排列都是正確的，而“（）”和“(”都是錯誤的。,49,特殊的線性表：棧,50,用變量T表示當(dāng)前盤子數(shù)，數(shù)組S存儲當(dāng)前放在桌上的盤子，其中S(i)表示從下往上數(shù)第i個盤子的編號。則兩種操作的實現(xiàn)如下： 取出盤子： xS(T) / 取出最頂端的盤子編號，存放在變量x中 T=T-1 / 盤子數(shù)減

22、少1 放入一個編號為x的新盤子： T=T+1 / 盤子數(shù)增加1 S(T)x / 在最頂端放入編號為x的盤子,51,觀察上述模擬中所運用到的數(shù)據(jù)結(jié)構(gòu)，我們發(fā)現(xiàn)有如下兩個特征： 如果將盤子看成一個元素，那么每個盤子只與它的上面的盤子（頂端除外）和下面的盤子（底端除外）有關(guān)系。因此它是一個線性結(jié)構(gòu)，其中S存儲的是這個線性表，T表示線性表中元素個數(shù)。 對于盤子i和j，若i比j后放入，則i必然在j之前被拿出。也就是說這個線性表的元素滿足后進先出(Last In First Out, LIFO)的性質(zhì)。 我們將這樣滿足后進先出性質(zhì)的線性表稱之為棧(stack)。特別地，不包含任何元素的棧稱為空棧。 可操作

23、端稱為棧頂 另一端稱為棧底 盤子堆的頂端（取、放盤子的一端）就是棧頂，底部就是棧底。,52,括號匹配的過程其實和取放盤子的過程有相通之處 1）如果有括號，肯定最先出現(xiàn)一個左括號； 2)一旦出現(xiàn)一個右括號，該右括號應(yīng)該和最晚出現(xiàn)的未和右括號匹配的左括號相匹配； 3)表達式結(jié)束，每個左括號都應(yīng)該有右括號相匹配，每個右括號也有左括號相匹配，沒有多余的未匹配的左括號與右括號。,53,54,使用STL解決該問題,stack 類 #include 原型 namespace std template class stack; ,55,stack類最重要的函數(shù)： 1）void push() 插入元素到棧頂 2

24、）void pop() 移除棧頂元素（注意，函數(shù)類型為 void） 3）value_type istr.length(); i+) /根據(jù)當(dāng)前字符處理 switch(stri) /左括號入棧 case (:temp_stack.push(); break; /右括號，和棧頂元素匹配，如果棧為空或不匹配則認(rèn)為出錯 case ): if (temp_stack.empty() return false; if (temp_stack.top() != () return false; else temp_stack.pop();break;,58,case :temp_stack.push();

25、break; case : if (temp_stack.empty() return false; if (temp_stack.top() != ) return false; else temp_stack.pop();break;,59,case :temp_stack.push(); break; case : if (temp_stack.empty() return false; if (temp_stack.top() != ) return false; else temp_stack.pop();break; default:break; ,60,/棧必須為空，否則出錯 i

26、f(temp_stack.empty() return true; else return false; ,61,int main(int argc, char* argv) std:string test_buffer7 = (), (), (), (), ()(),(,(); /測試 for (int i=0; i7; i+) std:coutThe string is : test_bufferi , The result is (judge_bracket(test_bufferi)?true:false) .std:endl; return 0; ,62,運行結(jié)果,The strin

27、g is : (), The result is true. The string is : (), The result is true. The string is : (), The result is false. The string is : (), The result is true. The string is : ()(), The result is true. The string is : (, The result is false. The string is : (), The result is false.,63,荷蘭國旗問題,【例10-4】現(xiàn)在我們面前有一

28、張桌子，桌子上整齊的擺放著紅色，白色，藍色三種線條，但他們的順序是凌亂的。我們的要求是：用一個算法把這些線條挑出來重新擺放順序，最后的結(jié)果就像上圖的荷蘭國旗，紅色在上，白色在中間，藍色在最下面。,64,最直接的想法,聲明一個變量flag來標(biāo)識我們當(dāng)前的需要擺放的位置。然后借助這個變量需遍歷整個數(shù)組，首先找紅色的線條(紅白藍線條我們可以用0，1，2模擬)，找到就把它和當(dāng)前位置的線條進行交換。當(dāng)紅色線條找全時就開始找白色線條，白色線條找完之后，剩下的肯定就是藍色的線條了。到此整個的算法結(jié)束。,65,聲明一個變量flag來標(biāo)識我們當(dāng)前的需要擺放的位置。然后借助這個變量需遍歷整個數(shù)組，首先找紅色的線條

29、(紅白藍線條我們可以用0，1，2模擬)，找到就把它和當(dāng)前位置的線條進行交換。當(dāng)紅色線條找全時就開始找白色線條，白色線條找完之后，剩下的肯定就是藍色的線條了。,66,int flag = 0; /標(biāo)識 while (flag red_white) /red_white 紅白分隔線位置 if (aflag != 0) for (int i = flag+1; i array_size; i+) if (ai = 0) swap(aflag,ai); break; +flag; ,67,while (flag = red_white ,68,第一次改進,首先將整個數(shù)組分為3個區(qū)域，即紅色區(qū)域，白色區(qū)

30、域，藍色區(qū)域，然后首先我們遍歷紅色區(qū)域判斷當(dāng)前單元的值是否是紅色，若是繼續(xù)遍歷，否則判斷該值是白色還是藍色，若是白色便去白色區(qū)域去尋找一個紅色的單元與之交換，反之便去藍色區(qū)域?qū)ふ乙粋€值與之交換。當(dāng)紅色區(qū)域遍歷完成之后，我們接著遍歷白色區(qū)域，若當(dāng)前單元不是白色，那肯定是藍色了，我們便去藍色的區(qū)域去尋找一個值與之交換。當(dāng)藍色區(qū)域遍歷完成之后。我們的工作就完成了。,69,int flag = 0; /標(biāo)識 while (flag red_white) /red_white 紅白分隔線位置 if (aflag = 1) for (int i = red_white; i white_blue; +i) if (ai = 0