鏈式存儲結構在《數據結構》中的教法

摘要：鏈式存儲結的特色--指針以其靈活性而不易被學生掌握，針對諸如指針變量賦值運算的難點，提出新的教法與同仁共勉。

關鍵詞： 鏈式存儲結 指針變量 賦值運算

Teaching Methods of Linked Structure in \"Date structure\"

Kan Nan

（Department of Information Engineering， WuHan Vocational College of Information Transmission Technology， Nan Kan， 430074 ， China）

Abstract：Pointer is a difficulty for students to grasp in linked structure; there is one question about it. For example assignmentoperation about pointer variable，，Based on this， author discusses new teaching methods.

Keyword: linked structure; pointer variable; assignment operation

《數據結構》主要研究信息的邏輯結構及其基本操作在計算機中的表現和現實，是計算機專業的核心課程。鏈式存儲作為該課程討論的重要的儲結結構之一，是學生應掌握程序設計技巧的基礎。

從進幾年《數據結構》課程的教學過程反映出，當討論鏈式存儲結構時學生出現理解上的“瓶頸”現象。問題集中體現在：指針變量與指針賦值運算。下面就這一問題談談教法與感受，希望與同仁共勉。

首先我們引入兩個概念 “菜籃子”和“菜”而且要分清它們。 說到賦值語句，我們先來回顧一下賦值運算的實質。盡管不同語句的賦值語句有不同的語法結構，但大都數語句所定義的語意大體相同。下面以C語言為例說明：

某程序段中語句x=y；x和y是變量名，無論他們是數據類型，每一名字有兩個“身份”：一方面該變量名代表一定的存儲單元，另一方面代表該存儲單元里的內容，以該單元的內容為值。賦值語句x=y的意義是：“把y的值送入x所代表的存儲單元”，也就是說，賦值語句中賦值號“=”左右兩邊的變量名扮演著兩種不同的角色。為了區別一個變量名的兩種“身份”我們把一個名字所代表的那個存儲單元稱為該名的左值，通俗地說是“菜籃子”用來裝菜的；把一個名字所代表的的單元內容（值）稱為該名的右值，對應的就是“菜”。當變量名出現在等號左邊就是“菜籃子”出現在等號右邊就是“菜”，賦值運算就是把“菜”往“菜籃子”里放（注意這兒的“菜籃子”的特殊性：最后一次方的“菜”就覆蓋“菜籃子”里以前放的“菜”，且“菜籃子”里只能放一個“菜”）。

對變量名的雙重性有了以上的深刻認識在來討論指針變量的賦值運算學生就恍然大悟了。

例1： 有定義如下的雙向鏈接表

struct dnode {elemtp data;

struct dnode *prior， *next;}*p，*r;如圖1所示，在雙向鏈接表中的結點之前插入一個結點r使線性表（a1…ai，ai+1…an）變成（a1…ai，b，ai+1…an）。操作語句如下；

{1}r->prior=p->prior;

{2}r->next=p;

{3}p->prior->next=r

{4}p->prior=r;

以上4條語句的語義分別是：

{1}把數據元素ai所在的結點地址（在p的prior域中放著的地址值，此時表現為變量p->prior所代表的內容，以后簡稱右值，也就是我們所說的“菜”）放到結點r 的prior域中(此時r->prior應以其所代表的存儲單元的身份出現，即左值，也就是“菜籃子”)這就是把變量p->prior所代表的存儲單元的地址值賦值給變量r->prior所代表的存儲單元，即把“菜”放進“菜籃子”，線1所代表的鏈建成了。注意千萬不能把該語句中理解為其左值，我們是不可能把“菜籃子”放進“菜籃子”的

{2}把數據元素ai+1所在結點的地址（是變量p代表的內容，即p的右值）放到結點r 的next域（是變量r->next代表的存儲單元，即左值）。變量p的值作為“菜”放進了變量r->next這個“菜籃子”，線2所代表的鏈建成了。

{3}把被插入數據元素b所在的結點的地址（該地址作為值在r所代表的存儲單元中放著，即r右值）放到數據元素ai所在的結點next域中，而數據元素ai所在的結點就是p->prior（因為數據元素ai所在的結點地址在p->prior中放著，此時取其右值），那么數據元素ai所在的結點next域中就是p->prior->next這個“菜籃子”，此時語句實現使b變成ai的后續，經賦值后原鏈5自然斷掉。

{4}把被插入數據元素b所在的結點的中的地址，放到數據元素ai+1的地址，放到數據元素ai+1所在結點prior域中，變量r的值再次為“菜”放入了變量p->prior“菜籃子”，就使b稱為ai+1的前驅，經賦值后原鏈自然斷掉。

以上4條語句{1}，{2}的次序可以調換，{3}，{4}的次序不可以調換，而且{1}，{3}語句必須在{4}之前，只要學生對賦值語句能有以上的深刻理解，其原因就不言而喻了。再復雜的鏈式存儲結構及其操作一般都涉及改變鏈的狀態，其無非就是通過賦值語句來改變鏈，在操作中分清變量“菜籃子”和“菜”的雙重角色，對學生掌握鏈式存儲結構起著重要的作用。

參考文獻：

[1]Horowitz ES. Fundamentals of Data Structures. Pitmen Publishing Limited， 1976

[2]陳火旺。編譯原理 北京：國防工業出版社，1984