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

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

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

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

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

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

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

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

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

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

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

11、ist結(jié)構(gòu)體包括有三個(gè)數(shù)據(jù)成員，在函數(shù)中都會(huì)用到。Length和listsize成員的類型是整型int好理解，ElemType又是個(gè)什么類型？理解了前面Status抽象的意義后，可以猜到ElemType又是個(gè)抽象數(shù)據(jù)類型，對(duì)應(yīng)的是順序表中要存儲(chǔ)的數(shù)據(jù)的類型。ElemType（見名知義，元素類型）在教材前面出現(xiàn)過，但放在不同應(yīng)用背景下，可以給出不同的定義。這個(gè)數(shù)據(jù)可以是簡(jiǎn)單的整型（若干整數(shù)的序列構(gòu)成一個(gè)線性表），也可以是浮點(diǎn)型，甚至ElemType是一個(gè)字符串、結(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ù)是多項(xiàng)式中的一項(xiàng)，需要記錄數(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ù)的實(shí)現(xiàn)，不再給出分析和示例，道理一樣。理解了上面的內(nèi)容，從第2行開始就好辦了。第2行注釋說明了這個(gè)算法完成的操作，第3行分配內(nèi)存空間：cpp view plaincopyprint?1. L.elem&#

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

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

16、義#define、包含文件#include等，這是語言的要求。另外，還要增加mian()函數(shù)作為程序運(yùn)行的入口，在其中設(shè)置測(cè)試和調(diào)試程序的代碼，如果必要，還應(yīng)該增加一些專門用于輸入、輸出的函數(shù)。這樣，為實(shí)踐算法2.3寫出的對(duì)應(yīng)程序是：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 / 線性表存儲(chǔ)空間的初始分配量，為方便測(cè)試，改為10  9. typedef struct   10.   11. ElemType *elem; / 存儲(chǔ)空間基址  12. int length; / 當(dāng)前長(zhǎng)度  13. int listsize; / 當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)  1

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

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

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

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

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

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

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

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

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