給數(shù)據(jù)結(jié)構(gòu)初學者跨過算法和程序之間的鴻溝

1、給數(shù)據(jù)結(jié)構(gòu)初學者：跨過算法和程序之間的鴻溝 【摘要】學習數(shù)據(jù)結(jié)構(gòu)時，將各種基本操作通過程序?qū)崿F(xiàn)，可以加深對算法的理解，也是提高編程能力的一種有效手段。針對初學者在搭建算法和 程序之間聯(lián)系困難的問題，本文以線性表部分為例，介紹了如何從讀算法中找出實現(xiàn)程序的線索，圍繞算法和程序之間的聯(lián)系、抽象的描述和具體的實現(xiàn)之間的關(guān) 系，引導讀者學到抽象算法的精髓，最后對實踐的路線、方案等進行了總結(jié)，并給出一些建議。【正文】計算機是算法的科學。學習IT的童鞋，在算法中下多大的功夫都不為過。在學習數(shù)據(jù)結(jié)構(gòu)課程的時候，將教 材中給出的算法用程序代碼描述出來，在實現(xiàn)的過程中，可以不斷加深思考；在調(diào)試程序的過程中，對算

2、法的細節(jié)能夠進行精細的鉆研，這些都是獲得算法精髓的方 法。算法往往用“偽代碼”的形式給出，學生在學習過程中，將這種抽象的描述與能夠執(zhí)行的具體形態(tài)的代碼之間建立聯(lián)系，使得算法形象起來，這樣一個學習過 程，以及由此帶來的體驗，將會使學生在技術(shù)成長之路上受益菲淺。在我組織的“未來IT工程師協(xié)會/CSDN高校俱樂部”的活動中，結(jié)合同學們正在“算法與數(shù)據(jù)結(jié)構(gòu)”課程，創(chuàng)辦“算法達人修煉營”，組成合作學習團體，實踐相關(guān)的各種算法，討論在算法學習中遇到的問題，以此來提高駕馭算法的能力。為幫助同學們做好抽象的數(shù)據(jù)結(jié)構(gòu)、算法與某種語言編寫的程序之間的過渡，特撰寫此文。結(jié)合我校大二同學已經(jīng)有的知識結(jié)構(gòu)，本文以嚴蔚敏

3、老師的數(shù)據(jù)結(jié)構(gòu)（C語言版）為基礎(chǔ)說數(shù)據(jù)結(jié)構(gòu)和算法，實現(xiàn)算法的語言用C和C+。（建議：讀本文中，一邊翻著教材才有感覺。）一、讀算法中找出實現(xiàn)程序的線索要看懂算法，解決其中存在的障礙，需要同學們在讀書時能夠做到前后對照。以P23中的算法2.3為例講讀算法的方法，以及如何前后對照。算法2.3的順序存儲的線性表的初始化問題，偽代碼是：為便于后續(xù)的說明，為算法加些行號：plain view plaincopyprint?1. 1. Status InitList_sq(SqList &L)  2. 2.  /構(gòu)造一個空的線性表

4、L  3. 3.  L.elem =(ElemType *)malloc(LIST_INIT_SIZE * size(ElemType);  4. 4.  if(!L.elem) exit(OVERFLOW); /存儲分配失敗  5. 5.  L.length = 0;    /空表長度為0  6. 6.  L.lis

5、tsize = LIST_INIT_SIZE;    /初始存儲容量  7. 7.  return OK;  8. 8.   這個算法要解決的問題非常顯然，用思維導圖表達出來是： 算法中的邏輯非常簡單，常有同學說，算法是能看懂。這得益于抽象（后面專門要說），使我們忽略了很多實現(xiàn)中要考慮的細節(jié)，所以容易看懂，這是抽象的好 處。而恰好由于忽略了實現(xiàn)細節(jié)中的具體形態(tài)，使得在考慮如何實現(xiàn)算法時出現(xiàn)障礙。這不是一個大問題，卻成為初學者起步的一個障

6、礙，尤其是對程序設(shè)計的功底 并不很深的同學。（程序設(shè)計功底的加強是必需的，但已經(jīng)到了這個階段，并不是一定要先補上那一課再能學數(shù)據(jù)結(jié)構(gòu)，時候不等人。實際上，學數(shù)據(jù)結(jié)構(gòu)，同時也 促程序設(shè)計。）障礙主要來自于，算法描述中出現(xiàn)的“詞匯”和曾經(jīng)編程中用過的似乎并不相同?！白帧倍疾徽J識，談何理解，又何談實現(xiàn)。實際上，會看書的同學應該發(fā)現(xiàn)，算法中出現(xiàn)的“詞”，在教材前面都曾經(jīng)出現(xiàn)過，我們找出來，將其聯(lián)系到一起。說有些同學不會看書可能委屈，更多的是沒有耐心，一門課程起步階段，基礎(chǔ)性的內(nèi)容要看細了。算法第1行：Status InitList_sq(SqList &L)InitList

7、_sq是函數(shù)名自不用說。Status 顯然是函數(shù)InitList_sq()的返回值類型，但究竟是什么類型呢？C和C+中沒有這種數(shù)據(jù)類型，其他語言中也沒有，可以猜到是自定義類型。教材P10有解釋：教材接著給出了在C語言實現(xiàn)算法時的建議：cpp view plaincopyprint?1. /Status是函數(shù)的類型，其值是函數(shù)結(jié)果的代碼  2. typedef int Status  其實如果用PASCAL實現(xiàn)，需要按PASCAL語言的語法寫作：delphi view plaincopyprint?1. type S

8、tatus=integer;  一個函數(shù)執(zhí)行結(jié)束后，函數(shù)結(jié)果的代碼給出一些約定（如1是成功，0是失?。┩ㄟ^返回值通知調(diào)用函數(shù)執(zhí)行的情況，這種設(shè)計很常見。那么，此處Status用整型表示，其具體取值與含義是什么？從算法第7行 return OK;可以看出，這個OK就是Status可取的值。同樣在P10，有一些常定義（只列兩行，ERROR在其他函數(shù)中用到）：cpp view plaincopyprint?1. #define OK 1  2. #define ERROR 0  在

9、PASCAL中，對應的定義是：delphi view plaincopyprint?1. const OK=1;   2. const ERROR=0;   還沒有說Java，不說不夠意思。C/C+和PASCAL中利用自定義類型解決，而Java中沒有提自定義類型一詞，但實際就在不斷地聲明自定義類型(calss)。在此做自定義類實現(xiàn)涉嫌殺雞用牛刀，一種合適的解決方法是用枚舉類型（其實這種方法對C/C+也合適）：java view plaincopyprint?1. enum Status ERRO

10、R, OK;  理解：抽象的Status在各種語言中實現(xiàn)的途徑不同，甚至在一種語言中也可以有不同的實現(xiàn)方案。算法這樣的寫法有兩個方面的好處：（1）可以供使用不同語言編程的人使用；（2）對學習算法的人而言，可以忽略（用某語言實現(xiàn)的）細節(jié)，而將注意力集中到算法本身。這兩點好處對于后面的復雜算法更加重要。再次強調(diào)，要習慣并喜歡上這種抽象的描述。接下來講函數(shù)InitList_sq()的形式參數(shù)&L。形式參數(shù)&L的類型是對SqList類型的引用。SqList類型是何類型？自定義類型。SqList是一個結(jié)構(gòu)體類型，其定義就在P22，算法2.3前的一點點：SqL

11、ist結(jié)構(gòu)體包括有三個數(shù)據(jù)成員，在函數(shù)中都會用到。Length和listsize成員的類型是整型int好理解，ElemType又是個什么類型？理解了前面Status抽象的意義后，可以猜到ElemType又是個抽象數(shù)據(jù)類型，對應的是順序表中要存儲的數(shù)據(jù)的類型。ElemType（見名知義，元素類型）在教材前面出現(xiàn)過，但放在不同應用背景下，可以給出不同的定義。這個數(shù)據(jù)可以是簡單的整型（若干整數(shù)的序列構(gòu)成一個線性表），也可以是浮點型，甚至ElemType是一個字符串、結(jié)構(gòu)體。例如，可以是：cpp view plaincopyprint?1. typedef int ElemType

12、   還可以是：cpp view plaincopyprint?1. typedef struct student  2. char num10;  3. char name16;  4. int age;  5. float score;  6. ElemType;  在教材例2.4中，線性表中的數(shù)據(jù)是多項式中的一項，需要記錄數(shù)據(jù)下系數(shù)和指數(shù)，使用了結(jié)構(gòu)體：cpp view plain

13、copyprint?1. typedef struct  2. float coef;   /系數(shù)  3. int expn;      /指數(shù)  4. ElemType;  至于用其他語言和任務(wù)的實現(xiàn)，不再給出分析和示例，道理一樣。理解了上面的內(nèi)容，從第2行開始就好辦了。第2行注釋說明了這個算法完成的操作，第3行分配內(nèi)存空間：cpp view plaincopyprint?1. L.elem&#

14、160;=(ElemType *)malloc(LIST_INIT_SIZE * size(ElemType);  malloc()函數(shù)是分配內(nèi)存空間，相當于C+中的new運算符。查手冊知malloc()的原型是：cpp view plaincopyprint?1. void *malloc(unsigned int num_bytes);   由函數(shù)調(diào)用可以看出，分配的空間大小為LIST_INIT_SIZE * size(ElemType)，足夠存放LIST_IN

15、IT_SIZE（定義的常量，值為100，見P22）個ElemType型的值，返回的地址指針轉(zhuǎn)換為指向ElemType型的指針。函數(shù)調(diào)用結(jié)束后，將指針賦值給L.elem。算法第4行：if(!L.elem) exit(OVERFLOW);是在存儲分配失敗時的處理，OVERFLOW是P10定義的常量，值為-2。第5行和第6行算法就不再多述。其實也都是C中的內(nèi)容，不清楚的內(nèi)容通過參考資料可以解決。從上面的描述可以看出，教材中說得是用偽代碼描述算法，算法實際上已經(jīng)就是程序了。以C語言實現(xiàn)為例，在實現(xiàn)時，需要把這段算法/程序所需要的其他內(nèi)容寫到一個文件中。需要寫一些類型定義typedef、常量定

16、義#define、包含文件#include等，這是語言的要求。另外，還要增加mian()函數(shù)作為程序運行的入口，在其中設(shè)置測試和調(diào)試程序的代碼，如果必要，還應該增加一些專門用于輸入、輸出的函數(shù)。這樣，為實踐算法2.3寫出的對應程序是：cpp view plaincopyprint?1. #include<stdio.h> /printf()等  2. #include<malloc.h> / malloc()等  3. #include<process.h> /exit()

17、60; 4. #define OK 1  5. #define OVERFLOW -2  6. typedef int Status;    /Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等  7. typedef int ElemType;  /ElemType是線性表中數(shù)據(jù)元素的類型，此處用int  8. #define LIST_INIT_

18、SIZE 10 / 線性表存儲空間的初始分配量，為方便測試，改為10  9. typedef struct   10.   11. ElemType *elem; / 存儲空間基址  12. int length; / 當前長度  13. int listsize; / 當前分配的存儲容量(以sizeof(ElemType)為單位)  1

19、4. SqList;  15. Status InitList(SqList &L) / 算法2.3  16.    / 操作結(jié)果：構(gòu)造一個空的順序線性表  17.   L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);  18.   if(!L.elem)  19.   exit(OV

20、ERFLOW); / 存儲分配失敗  20. L.length=0; / 空表長度為0  21. L.listsize=LIST_INIT_SIZE; / 初始存儲容量  22. return OK;  23.   24. Status ListTraverse(SqList L)  25.        / 

21、;初始條件：順序線性表L已存在  26.     / 操作結(jié)果：依次輸出L中的每個數(shù)據(jù)元素，函數(shù)名沒有用display，而是用了更專業(yè)的術(shù)語遍歷Traverse  27.     ElemType *p;  28.     int i;  29.     p=L.elem;  30.   

22、  printf("線性表當前容量為: %d，", L.listsize);  31.     if (L.length>0)  32.       33.             printf("線性表中有 %d 個元素，分別是：&

23、quot;,L.length);  34.             for(i=1;i<=L.length;i+)  35.                         printf(&qu

24、ot;%d ",*p+);  36.       37.     else  38.             printf("目前還是空線性表。");  39.     printf("n");  4

25、0.     return OK;  41.   42. int main()  43.   44.     SqList La;  45.     Status i;  46.     i=InitList(La);  47.   

26、60; ListTraverse(La);  48.     return 0;  49.     對于上面的程序，運行結(jié)果為：上面的程序要用C+（或Java）實現(xiàn)時，將SqList定義為一個類，基本操作為成員函數(shù)（或稱為方法）。二、理解算法和程序之間的“跨度”下面羅列網(wǎng)上收集來的幾組說法，適當修改、補充，提供給讀者從多個角度分別體會：說法1：算法是解決問題的步驟；程序是算法的代碼實現(xiàn)。算法要依靠程序來完成功能；程序需要算法作為靈魂。說法2：算法與程序：(

27、1)一個程序不一定滿足有窮性，而算法需要在有限步驟內(nèi)完成。(2)程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。(3)算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。說法3：從計算機的角度講，程序是用一種計算機能理解并執(zhí)行的計算機語言描述解決問題的方法步驟。算法是解決問題的方法步驟（不一定要讓計算機能理解并執(zhí)行）。程序設(shè)計是分析解決問題的方法步驟，并將其記錄下來的過程，其關(guān)鍵就是將算法描述出來。數(shù)據(jù)結(jié)構(gòu)課程里面的代碼，都是偽代碼，也就是說，用C編譯器編譯是通不過的，還要做很多的修改才可以。算法是編程的核心，算法出來了，我們

28、就可以考慮用哪種語言實現(xiàn)比較簡單，不一定要選C。學數(shù)據(jù)結(jié)構(gòu)學的是算法思想，學會如何去解決問題，這才是最重要的，用C實現(xiàn)次之。在數(shù)據(jù)結(jié)構(gòu)C語言版里面，我們只是將這種數(shù)據(jù)結(jié)構(gòu)的操作用偽C代碼描述出來而已。而在實現(xiàn)時，再考慮語言細節(jié)，將算法用計算機可以接受的方式重新描述即可。說法4：算法和程序都是指令的有限序列 ，但是：程序是算法，而算法不一定是程序。 算法和程序的區(qū)別主要在于：(1) 在語言描述上，程序必須是用規(guī)定的程序設(shè)計語言來寫，而算法很隨意；(2) 在執(zhí)行時間上，算法所描述的步驟一定是有限的，而程序可以無限地執(zhí)行下去。所以： 程序 

29、= 數(shù)據(jù)結(jié)構(gòu) + 算法（這是面向過程程序設(shè)計的概念，在面向?qū)ο蟪绦蛟O(shè)計的語境下需要拓展。）三、理解算法與數(shù)據(jù)結(jié)構(gòu)中的抽象首先談一下計算科學中的抽象。抽象(Abstraction)是 簡化復雜的現(xiàn)實問題的途徑，可以忽略一個主題中與當前目標無關(guān)的那些方面，以便更充分地注意與當前目標有關(guān)的方面。抽象并不打算了解全部問題，而只是選擇 其中的一部分，暫時不用部分細節(jié)。運用抽象，可以使我們的注意力集中到要解決問題的主要矛盾上來，主要矛盾解決了，再解決次要矛盾。例如，在用計算機解決 問題時，先設(shè)計抽象的數(shù)據(jù)結(jié)構(gòu)和算法，再考慮如何用程序設(shè)計語言表達出來。除了降低難度，還利于保證正

30、確性、可靠性，也便于分工，便于工程組織。 抽象是計算機科學與技術(shù)中最基本的思維模式之一。抽象包括兩個方面，一是過程抽象，二是數(shù)據(jù)抽象。它側(cè)重于相關(guān)的細節(jié)和忽略不相關(guān)的細節(jié)。抽象作為識別 基本行為和消除不相關(guān)的和繁瑣的細節(jié)的過程，允許設(shè)計師專注于解決一個問題的考慮有關(guān)細節(jié)而不考慮不相關(guān)的較低級別的細節(jié)。在學習數(shù)據(jù)結(jié)構(gòu)時，要能看出抽象程序的高低。舉一個例子，本文前面舉例用的是P23的算法2.3，而不是p20的算法2.1，我為什么這樣安排？線性表可以采取順序表示和鏈式表示兩種方法進行實現(xiàn)。算法2.3對線性表的初始化針對的是順序表示。在鏈式表示時，針對初始化的操作，另有算法。算法2.3是和具體實現(xiàn)相關(guān)的算法。而