文章編號(hào)：1672-5913(2008)16-0068-03

摘要：本文從抽象思維的角度，運(yùn)用“數(shù)據(jù)結(jié)構(gòu)”中的經(jīng)典例子來(lái)闡述在計(jì)算機(jī)的學(xué)習(xí)與研究過(guò)程中應(yīng)運(yùn)用抽象思維的方法達(dá)到“學(xué)其思維，掠其形式”的目的。同時(shí)論述了在計(jì)算機(jī)的應(yīng)用中應(yīng)運(yùn)用科學(xué)的思維方法和注重計(jì)算機(jī)科學(xué)理論的研究。

關(guān)鍵詞：抽象思維；鏈表；二叉樹；圖；排序與查找

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

在幾年的計(jì)算機(jī)教學(xué)與實(shí)踐中，作者發(fā)現(xiàn)，大家在學(xué)習(xí)與應(yīng)用計(jì)算機(jī)的過(guò)程中，往往采用的是具體的思維方法，即通過(guò)舉一個(gè)實(shí)際的例子來(lái)“一步一步”地理解算法思想。本文認(rèn)為這種“學(xué)其形式，掠其思維”的學(xué)習(xí)與研究方法是不足取的。在學(xué)習(xí)與研究計(jì)算機(jī)的過(guò)程中，我們應(yīng)當(dāng)運(yùn)用抽象的思維方法，達(dá)到“學(xué)其思維，掠其形式”的目的。下面我們通過(guò)“數(shù)據(jù)結(jié)構(gòu)”中的典型例子來(lái)說(shuō)明抽象思維方法在計(jì)算機(jī)中的妙用。

1線性表中的單鏈表的逆轉(zhuǎn)(在利用原結(jié)點(diǎn)的情況下)

設(shè)逆轉(zhuǎn)后的單鏈表的表頭結(jié)點(diǎn)為reversed_head(初始值為NIL)，當(dāng)前正在轉(zhuǎn)換的結(jié)點(diǎn)為current，未被轉(zhuǎn)換的結(jié)點(diǎn)的單鏈表的表頭結(jié)點(diǎn)為not_reversed_head，如圖1所示。

則我們可以很快寫出如下的算法：

procedure reverse_link(var head:pointer);

var

reversed_head，current，not_reversed_head:pointer;

begin

reversed_head:=nil;

current:=head;

not_reversed_head:=current↑.link;

while current<>nil do

begin

current↑.link:=reversed_head;

reversed_head:=current;

current:=not_reversed_head;

not_reversed_head:=current↑.link

end;

head:=reversed_head

end;

可見(jiàn)，運(yùn)用抽象的思維方法，該算法變得很精煉。

2二叉樹遍歷的遞歸算法與線索二叉樹的刪除算法

二叉樹遍歷的算法有三種，即前序遍歷、中序(對(duì)稱序)遍歷和后序遍歷，通常用NLR，LNR，LRN來(lái)表示。運(yùn)用抽象的思維方法，我們可以從NLR，LNR，LRN的書寫當(dāng)中，得出：

(1) 無(wú)論哪種遍歷次序，二叉樹的葉子始終以相同的相對(duì)次序出現(xiàn)，因?yàn)長(zhǎng)始終在R的前面；

(2) 在NLR次序遍歷的結(jié)點(diǎn)中，第一個(gè)結(jié)點(diǎn)是二叉樹的根，最后一個(gè)結(jié)點(diǎn)是二叉樹的最右下的結(jié)點(diǎn)；在LNR次序遍歷的結(jié)點(diǎn)中，第一個(gè)結(jié)點(diǎn)是二叉樹的最左下的結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)是二叉樹的最右下的結(jié)點(diǎn)；在LRN次序遍歷的結(jié)點(diǎn)中，第一個(gè)結(jié)點(diǎn)是二叉樹的最左下的結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)是二叉樹的根。

在對(duì)稱序線索二叉樹的刪除算法中，運(yùn)用抽象的思維方法，我們可以假設(shè)該線索二叉樹的LNR次序遍歷的結(jié)點(diǎn)序列為……rP……P1……或……P1……rP……，如圖2所示：

這樣，刪除結(jié)點(diǎn)P時(shí)，可以找出如下的思路。

思路1：刪除結(jié)點(diǎn)P時(shí)，將其右子樹成為r的右子樹，或?qū)的左了樹成為P的右子樹的最左下結(jié)點(diǎn)的左子樹。

思路2：刪除結(jié)點(diǎn)P時(shí)，用r結(jié)點(diǎn)去替換結(jié)點(diǎn)P，此時(shí)，r的左子樹應(yīng)成為其雙親的右子樹，或以P為根的二叉樹的右子樹的最左下結(jié)點(diǎn)去替換結(jié)點(diǎn)P，此時(shí)最左下結(jié)點(diǎn)的右子樹應(yīng)成為其雙親的左子樹。

以思路1為例，我們可以寫出如下的核心算法：

P1↑.lchild:=P↑.lchild;或P1↑.rchild:=P↑.lchild;

r↑.rchild:=P↑.rchild’

dispose(P);

3圖中求最短徑的Dijkstra算法

Dijkstra在求圖中從一個(gè)源點(diǎn)到其他任意頂點(diǎn)的最短路徑時(shí)，運(yùn)用貪婪法的思想，將頂點(diǎn)集分為“已確定最短路徑的頂點(diǎn)集”和“未確定最短路徑的頂點(diǎn)集”兩部分，按照路徑長(zhǎng)度遞增的順序選擇當(dāng)前路徑長(zhǎng)度最短的頂點(diǎn)，同時(shí)修改當(dāng)前“未確定最短路徑的頂點(diǎn)集”的頂點(diǎn)的最短路徑長(zhǎng)度，直到選擇完畢。初學(xué)者對(duì)該算法在選擇的同時(shí)又進(jìn)行修改，往往不能理解。如果我們運(yùn)用抽象思維，用如下的圖3表示這種情況，則會(huì)易于理解。

其中dist[k]代表源點(diǎn)到當(dāng)前確定最短路徑長(zhǎng)度的頂點(diǎn)k的最短路徑長(zhǎng)度；

dist[j]代表源點(diǎn)到原先運(yùn)用貪婪法確定的最短路徑長(zhǎng)度的頂點(diǎn)j的最短路徑長(zhǎng)度；

cost[k，j]代表頂點(diǎn)k和頂點(diǎn)j之間的邊上的權(quán)值。

弄清楚這種關(guān)系之后，顯然我們可以得知：

if dist[k]+cost[k，j]

dist[j]:= dist[k]+cost[k，j]

這就是Dijkstra算法的核心語(yǔ)句。

4各種排序與查找算法

對(duì)于各種排序算法，初學(xué)者在學(xué)習(xí)的過(guò)程中，往往通過(guò)運(yùn)用具體的方法(舉一個(gè)實(shí)際的例子)來(lái)理解這些算法的思想。其實(shí)，只要我們運(yùn)用抽象思維，就可以將幾種排序算法歸結(jié)為一種思想，而且如果該算法不是一種穩(wěn)定的算法，我們可以很快舉出一個(gè)反例。

(1) 思路1：將被排序文件的排序碼看成一個(gè)整體

在這種思路中，我們又可以分成以下幾種方法。

方法1：將被排序文件分成“已排序好”部分和“未排序好”部分兩個(gè)部分。

(1) 假設(shè)“R1R2…Ri-1”已經(jīng)有序(但不一定是最終有序)，怎樣使得“R1R2…Ri-1Ri”有序(但不一定是最終有序)。這個(gè)問(wèn)題的實(shí)質(zhì)是在“未排序好”部分選擇Ri，將其放到“已排序好”的“R1R2…Ri-1”的適當(dāng)位置，使得“R1R2…Ri-1Ri”變成有序(但不一定最終有序)。根據(jù)尋找Ri的位置的方法不同，有直接插入排序、二分法插入排序等。

(2) 假設(shè)“R1R2…Ri-1”已經(jīng)有序并且是最終有序，怎樣在“未排序好”的部分選擇一個(gè)排序碼(我們不妨稱之為Ri)，使得“R1R2…Ri-1Ri”有序并且是最終有序。這個(gè)問(wèn)題的實(shí)質(zhì)是在“未排序好”的部分如何選擇Ri。根據(jù)選擇Ri的方法不同，有直接選擇排序、樹形選擇排序、堆排序、冒泡排序等。

(3) 假設(shè)“R1R2…Ri-1”、 “Ri”、 “Ri+1Ri+2…Rn”有序并且最終有序(但“R1R2…Ri-1”和“Ri+1Ri+2…Rn”不一定有序)。怎樣使得“R1R2…Ri-1”和“Ri+1Ri+2…Rn”這兩個(gè)區(qū)間也變成這種形式。該問(wèn)題的實(shí)質(zhì)是一個(gè)遞歸算法(當(dāng)然可以將其改為非遞歸算法)或者說(shuō)是一個(gè)怎樣分區(qū)的問(wèn)題。根據(jù)分區(qū)是靜態(tài)還是動(dòng)態(tài)進(jìn)行，有快速排序(靜態(tài)的)、二叉排序樹(動(dòng)態(tài)的)、平衡二叉排序樹(AVL樹，動(dòng)態(tài)的)等。

方法2：將被排序文件分成“已排序好”部分和“未排序好”部分多個(gè)部分。

這種方法的基本思想是首先分組，然后歸并。根據(jù)分組和歸并的方法不同，有Shell直接插入排序、二路歸并排序等。

(2) 思路2：將被排序文件的排序碼不看成一個(gè)整體

以上的思想，都是將排序碼看成一個(gè)整體，研究的是排序碼之間的有(無(wú))序關(guān)系，但沒(méi)有研究排序碼本身內(nèi)部的特點(diǎn)。如果我們既研究排序碼之間的有(無(wú))序關(guān)系，同時(shí)又研究排序碼本身內(nèi)部的特點(diǎn)，肯定更有助于問(wèn)題的解決。在這個(gè)思路上，有基數(shù)排序等。

在各種排序算法中，判斷該算法是穩(wěn)定的還是不穩(wěn)定的一種簡(jiǎn)單方法是：如果排序碼交換的距離大于1，則該算法是不穩(wěn)定的。

5綜合應(yīng)用

為了進(jìn)一步說(shuō)明抽象思維的妙處，最后我們舉一個(gè)綜合性的例子(鏈表、查找與排序等知識(shí)相結(jié)合)。

在實(shí)際生活中，我們經(jīng)常要訪問(wèn)某一類信息，并且還希望將訪問(wèn)過(guò)的信息按照訪問(wèn)頻度不增的次序排列，這樣有利于我們下一次的訪問(wèn)(更快地尋找到要訪問(wèn)的信息)。我們可以將信息組織成結(jié)點(diǎn)并且以循環(huán)雙鏈表(帶表頭結(jié)點(diǎn))的形式表示。結(jié)點(diǎn)如圖4所示：

其中l(wèi)link表示左指針，指向該結(jié)點(diǎn)的前驅(qū)；

freq表示該結(jié)點(diǎn)訪問(wèn)的頻度；

info表示該結(jié)點(diǎn)的信息；

rlink表示右指針，指向該結(jié)點(diǎn)的后繼；

于是其存儲(chǔ)結(jié)構(gòu)可用如下的圖5描述：

假設(shè)當(dāng)前訪問(wèn)的結(jié)點(diǎn)是p所指向的結(jié)點(diǎn)，則進(jìn)行p↑.preq←p↑.preq+1的操作后，應(yīng)當(dāng)調(diào)整其在原鏈表中的位置，使得該鏈表以不增的次序排列，調(diào)整方法如下：

按照直接插入排序(鏈?zhǔn)酱鎯?chǔ))的方法尋找結(jié)點(diǎn)p應(yīng)處的位置，其中表頭結(jié)點(diǎn)作為監(jiān)視哨，然后按照循環(huán)雙鏈表的插入和刪除算法進(jìn)行結(jié)點(diǎn)的重新排列。核心算法如下(假設(shè)當(dāng)前欲訪問(wèn)信息為x的結(jié)點(diǎn)，若不存在信息為x的結(jié)點(diǎn)，則將信息為x的結(jié)點(diǎn)加到雙鏈表的尾部)：

head↑.info:=x; p:=head↑.rlink; q:=head;{將head作為監(jiān)視哨}

while p↑.info<>x do{尋找信息為x的結(jié)點(diǎn)}

begin

q:=p;

p:=p↑.rlink

end;

if p<>head then{若找到，則調(diào)整}

begin

p↑.freq:=p↑.freq+1;

q:=p↑.llink; head↑.freq:=p↑.freq;{將head作為監(jiān)視哨}

while q↑.freq

q:=q↑.llink;

if q↑.rlink<>p then{若需要調(diào)整，先刪除}

begin

p↑.llink↑.rlink:=p↑.rlink;

p↑.rlink↑.llink:=p↑.llink

end;

end;

else{生成新的結(jié)點(diǎn)}

begin

new(p);

p↑.freq:=0;

p↑.info:=x

end;

p↑.rlink:=q↑.rlink;{插入}

p↑.llink:=q;

q↑.rlink↑.llink:=p;

q↑.rlink:=p;

通過(guò)以上的例子大家可以發(fā)現(xiàn)，運(yùn)用抽象思維方法理解算法思想時(shí)，可以達(dá)到事半功倍的效果，而且可以在原有算法的基礎(chǔ)上進(jìn)行完善和擴(kuò)充。這說(shuō)明，我們?cè)谘芯恳婚T學(xué)科時(shí)，應(yīng)當(dāng)是“學(xué)其思維，掠其形式”，而不是反之。同時(shí)這又說(shuō)明了在計(jì)算機(jī)的應(yīng)用中，我們應(yīng)運(yùn)用科學(xué)的思維方法和注重計(jì)算機(jī)科學(xué)理論的研究。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社.

[2] 許卓群. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社.