淺談抽象思維在計算機學習與研究中的應用

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

摘要：本文從抽象思維的角度，運用“數據結構”中的經典例子來闡述在計算機的學習與研究過程中應運用抽象思維的方法達到“學其思維，掠其形式”的目的。同時論述了在計算機的應用中應運用科學的思維方法和注重計算機科學理論的研究。

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

中圖分類號：G642

文獻標識碼：B

在幾年的計算機教學與實踐中，作者發現，大家在學習與應用計算機的過程中，往往采用的是具體的思維方法，即通過舉一個實際的例子來“一步一步”地理解算法思想。本文認為這種“學其形式，掠其思維”的學習與研究方法是不足取的。在學習與研究計算機的過程中，我們應當運用抽象的思維方法，達到“學其思維，掠其形式”的目的。下面我們通過“數據結構”中的典型例子來說明抽象思維方法在計算機中的妙用。

1線性表中的單鏈表的逆轉(在利用原結點的情況下)

設逆轉后的單鏈表的表頭結點為reversed_head(初始值為NIL)，當前正在轉換的結點為current，未被轉換的結點的單鏈表的表頭結點為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;

可見，運用抽象的思維方法，該算法變得很精煉。

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

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

(1) 無論哪種遍歷次序，二叉樹的葉子始終以相同的相對次序出現，因為L始終在R的前面；

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

在對稱序線索二叉樹的刪除算法中，運用抽象的思維方法，我們可以假設該線索二叉樹的LNR次序遍歷的結點序列為……rP……P1……或……P1……rP……，如圖2所示：

這樣，刪除結點P時，可以找出如下的思路。

思路1：刪除結點P時，將其右子樹成為r的右子樹，或將P的左了樹成為P的右子樹的最左下結點的左子樹。

思路2：刪除結點P時，用r結點去替換結點P，此時，r的左子樹應成為其雙親的右子樹，或以P為根的二叉樹的右子樹的最左下結點去替換結點P，此時最左下結點的右子樹應成為其雙親的左子樹。

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

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

r↑.rchild:=P↑.rchild’

dispose(P);

3圖中求最短徑的Dijkstra算法

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

其中dist[k]代表源點到當前確定最短路徑長度的頂點k的最短路徑長度；

dist[j]代表源點到原先運用貪婪法確定的最短路徑長度的頂點j的最短路徑長度；

cost[k，j]代表頂點k和頂點j之間的邊上的權值。

弄清楚這種關系之后，顯然我們可以得知：

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

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

這就是Dijkstra算法的核心語句。

4各種排序與查找算法

對于各種排序算法，初學者在學習的過程中，往往通過運用具體的方法(舉一個實際的例子)來理解這些算法的思想。其實，只要我們運用抽象思維，就可以將幾種排序算法歸結為一種思想，而且如果該算法不是一種穩定的算法，我們可以很快舉出一個反例。

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

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

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

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

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

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

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

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

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

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

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

5綜合應用

為了進一步說明抽象思維的妙處，最后我們舉一個綜合性的例子(鏈表、查找與排序等知識相結合)。

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

其中llink表示左指針，指向該結點的前驅；

freq表示該結點訪問的頻度；

info表示該結點的信息；

rlink表示右指針，指向該結點的后繼；

于是其存儲結構可用如下的圖5描述：

假設當前訪問的結點是p所指向的結點，則進行p↑.preq←p↑.preq+1的操作后，應當調整其在原鏈表中的位置，使得該鏈表以不增的次序排列，調整方法如下：

按照直接插入排序(鏈式存儲)的方法尋找結點p應處的位置，其中表頭結點作為監視哨，然后按照循環雙鏈表的插入和刪除算法進行結點的重新排列。核心算法如下(假設當前欲訪問信息為x的結點，若不存在信息為x的結點，則將信息為x的結點加到雙鏈表的尾部)：

head↑.info:=x; p:=head↑.rlink; q:=head;{將head作為監視哨}

while p↑.info<>x do{尋找信息為x的結點}

begin

q:=p;

p:=p↑.rlink

end;

if p<>head then{若找到，則調整}

begin

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

q:=p↑.llink; head↑.freq:=p↑.freq;{將head作為監視哨}

while q↑.freq

q:=q↑.llink;

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

begin

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

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

end;

end;

else{生成新的結點}

begin

new(p);

p↑.freq:=0;

p↑.info:=x

end;

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

p↑.llink:=q;

q↑.rlink↑.llink:=p;

q↑.rlink:=p;

通過以上的例子大家可以發現，運用抽象思維方法理解算法思想時，可以達到事半功倍的效果，而且可以在原有算法的基礎上進行完善和擴充。這說明，我們在研究一門學科時，應當是“學其思維，掠其形式”，而不是反之。同時這又說明了在計算機的應用中，我們應運用科學的思維方法和注重計算機科學理論的研究。

參考文獻：

[1] 嚴蔚敏. 數據結構[M]. 北京：清華大學出版社.

[2] 許卓群. 數據結構[M]. 北京：高等教育出版社.