鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在《數(shù)據(jù)結(jié)構(gòu)》中的教法

摘要：鏈?zhǔn)酱鎯?chǔ)結(jié)的特色--指針以其靈活性而不易被學(xué)生掌握，針對(duì)諸如指針變量賦值運(yùn)算的難點(diǎn)，提出新的教法與同仁共勉。

關(guān)鍵詞： 鏈?zhǔn)酱鎯?chǔ)結(jié) 指針變量 賦值運(yùn)算

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

《數(shù)據(jù)結(jié)構(gòu)》主要研究信息的邏輯結(jié)構(gòu)及其基本操作在計(jì)算機(jī)中的表現(xiàn)和現(xiàn)實(shí)，是計(jì)算機(jī)專業(yè)的核心課程。鏈?zhǔn)酱鎯?chǔ)作為該課程討論的重要的儲(chǔ)結(jié)結(jié)構(gòu)之一，是學(xué)生應(yīng)掌握程序設(shè)計(jì)技巧的基礎(chǔ)。

從進(jìn)幾年《數(shù)據(jù)結(jié)構(gòu)》課程的教學(xué)過(guò)程反映出，當(dāng)討論鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)學(xué)生出現(xiàn)理解上的“瓶頸”現(xiàn)象。問(wèn)題集中體現(xiàn)在：指針變量與指針賦值運(yùn)算。下面就這一問(wèn)題談?wù)劷谭ㄅc感受，希望與同仁共勉。

首先我們引入兩個(gè)概念 “菜籃子”和“菜”而且要分清它們。 說(shuō)到賦值語(yǔ)句，我們先來(lái)回顧一下賦值運(yùn)算的實(shí)質(zhì)。盡管不同語(yǔ)句的賦值語(yǔ)句有不同的語(yǔ)法結(jié)構(gòu)，但大都數(shù)語(yǔ)句所定義的語(yǔ)意大體相同。下面以C語(yǔ)言為例說(shuō)明：

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

對(duì)變量名的雙重性有了以上的深刻認(rèn)識(shí)在來(lái)討論指針變量的賦值運(yùn)算學(xué)生就恍然大悟了。

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

struct dnode {elemtp data;

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

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

{2}r->next=p;

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

{4}p->prior=r;

以上4條語(yǔ)句的語(yǔ)義分別是：

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

{2}把數(shù)據(jù)元素ai+1所在結(jié)點(diǎn)的地址（是變量p代表的內(nèi)容，即p的右值）放到結(jié)點(diǎn)r 的next域（是變量r->next代表的存儲(chǔ)單元，即左值）。變量p的值作為“菜”放進(jìn)了變量r->next這個(gè)“菜籃子”，線2所代表的鏈建成了。

{3}把被插入數(shù)據(jù)元素b所在的結(jié)點(diǎn)的地址（該地址作為值在r所代表的存儲(chǔ)單元中放著，即r右值）放到數(shù)據(jù)元素ai所在的結(jié)點(diǎn)next域中，而數(shù)據(jù)元素ai所在的結(jié)點(diǎn)就是p->prior（因?yàn)閿?shù)據(jù)元素ai所在的結(jié)點(diǎn)地址在p->prior中放著，此時(shí)取其右值），那么數(shù)據(jù)元素ai所在的結(jié)點(diǎn)next域中就是p->prior->next這個(gè)“菜籃子”，此時(shí)語(yǔ)句實(shí)現(xiàn)使b變成ai的后續(xù)，經(jīng)賦值后原鏈5自然斷掉。

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

以上4條語(yǔ)句{1}，{2}的次序可以調(diào)換，{3}，{4}的次序不可以調(diào)換，而且{1}，{3}語(yǔ)句必須在{4}之前，只要學(xué)生對(duì)賦值語(yǔ)句能有以上的深刻理解，其原因就不言而喻了。再?gòu)?fù)雜的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其操作一般都涉及改變鏈的狀態(tài)，其無(wú)非就是通過(guò)賦值語(yǔ)句來(lái)改變鏈，在操作中分清變量“菜籃子”和“菜”的雙重角色，對(duì)學(xué)生掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)起著重要的作用。

參考文獻(xiàn)：

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

[2]陳火旺。編譯原理 北京：國(guó)防工業(yè)出版社，1984