數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)中指針相關(guān)問(wèn)題

孔 兵，陳紅梅，袁國(guó)武

（云南大學(xué) 信息學(xué)院，云南 昆明 650091）

【學(xué)法指導(dǎo)】

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)中指針相關(guān)問(wèn)題

孔 兵，陳紅梅，袁國(guó)武

（云南大學(xué) 信息學(xué)院，云南 昆明 650091）

《數(shù)據(jù)結(jié)構(gòu)》是實(shí)踐性很強(qiáng)的計(jì)算機(jī)專業(yè)核心課程，一般以C語(yǔ)言作為程序設(shè)計(jì)語(yǔ)言，但指針往往成為學(xué)生編程中的難點(diǎn)。結(jié)合《數(shù)據(jù)結(jié)構(gòu)》課程的需要，從指針的本質(zhì)出發(fā)，討論了指針基本概念、指針和數(shù)組及指向函數(shù)的指針幾個(gè)問(wèn)題，目的是幫助學(xué)生在《數(shù)據(jù)結(jié)構(gòu)》課程的學(xué)習(xí)中更好地理解和應(yīng)用指針。

指針；C語(yǔ)言；實(shí)驗(yàn)；數(shù)據(jù)結(jié)構(gòu)

一、引言

《數(shù)據(jù)結(jié)構(gòu)》作為實(shí)踐性很強(qiáng)的計(jì)算機(jī)專業(yè)的基礎(chǔ)課，教學(xué)中必然離不開(kāi)實(shí)踐。針對(duì)《數(shù)據(jù)結(jié)構(gòu)》的課程設(shè)計(jì)實(shí)踐不僅可以幫助學(xué)生鞏固和加深對(duì)課程內(nèi)容的理解，更重要的是可以進(jìn)一步鍛煉程序設(shè)計(jì)的技能[1]。C語(yǔ)言是數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)中重要的程序設(shè)計(jì)語(yǔ)言，指針是C語(yǔ)言中一個(gè)非常重要的概念。在C語(yǔ)言中，指針的應(yīng)用非常靈活，對(duì)于程序設(shè)計(jì)初學(xué)者來(lái)說(shuō)比較難掌握，更談不上靈活合理的應(yīng)用?！稊?shù)據(jù)結(jié)構(gòu)》中（注：文中的討論圍繞嚴(yán)蔚敏老師的《數(shù)據(jù)結(jié)構(gòu)》C語(yǔ)言版教材[2]），為了實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，指針在線性表、樹(shù)和圖的存儲(chǔ)中都有重要的應(yīng)用，可以說(shuō)，數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)繞不開(kāi)指針的應(yīng)用，如果學(xué)生掌握不好指針，是無(wú)法進(jìn)行數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)學(xué)習(xí)的。

教學(xué)中注意到，學(xué)生的主要問(wèn)題是對(duì)指針的本質(zhì)缺乏清晰的理解，知其然不知其所以然，導(dǎo)致在應(yīng)用時(shí)只會(huì)依葫蘆畫(huà)瓢，不會(huì)靈活應(yīng)用。針對(duì)學(xué)生理解和應(yīng)用中的難點(diǎn)問(wèn)題，剖析了指針的本質(zhì)，以此為基礎(chǔ)，討論了指針的使用、指針和數(shù)組及指向函數(shù)的指針幾個(gè)問(wèn)題，希望能夠加深學(xué)生對(duì)指針的理解，并在數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)中靈活應(yīng)用。

二、指針

1.變量和數(shù)據(jù)類型。變量和數(shù)據(jù)類型是C語(yǔ)言中的基本概念，是否能理解它們的本質(zhì)，對(duì)后續(xù)指針概念的理解非常重要。但是，由于它們是最基本的東西，教師和學(xué)生都認(rèn)為很好理解，不是很重視。因此，學(xué)生對(duì)它們的理解往往流于表面，產(chǎn)生模糊的認(rèn)識(shí)，如：變量是會(huì)變化的量；對(duì)變量名和變量的關(guān)系，變量和數(shù)據(jù)類型的關(guān)系等認(rèn)識(shí)不清。

圖1 變量示意圖

對(duì)變量的理解應(yīng)該強(qiáng)調(diào)變量最本質(zhì)的意義：內(nèi)存中的一塊存儲(chǔ)空間，即所謂變量就是一塊存儲(chǔ)空間，如圖1所示。

圍繞對(duì)變量本質(zhì)的理解應(yīng)該強(qiáng)調(diào)幾點(diǎn)：①一塊空間（變量）具有兩個(gè)特征，一是這塊空間在內(nèi)存中的起始地址（計(jì)算機(jī)內(nèi)部16進(jìn)制地址表示不便，本文中用3位10進(jìn)制數(shù)示意），表示這塊空間的開(kāi)始，二是從起始地址開(kāi)始的空間大小，這兩個(gè)特征一起確定了一個(gè)變量；②作為內(nèi)存的一塊存儲(chǔ)空間，自然可以存儲(chǔ)不同的值，會(huì)變化；③變量的聲明是提出分配存儲(chǔ)空間的要求，沒(méi)有分配空間，當(dāng)然不能存值，不能使用；④為了在程序中方便使用變量，變量可以取一個(gè)名字，即變量名。

變量都有數(shù)據(jù)類型，從存儲(chǔ)空間分配的角度看，數(shù)據(jù)類型的本質(zhì)是對(duì)分配空間大小的約定。要給一個(gè)變量分配存儲(chǔ)空間，涉及兩個(gè)東西：分在那，分多大。分在那由當(dāng)前內(nèi)存情況確定，而分多大則由變量所屬的數(shù)據(jù)類型確定，如int型就分4個(gè)字節(jié)大小。

2.指針的概念。指針是C語(yǔ)言中的派生數(shù)據(jù)類型，如int *p，聲明了一個(gè)由整型派生的指針變量p，如圖2所示。學(xué)生在為什么要用指針、指針變量和原類型之間是什么關(guān)系等問(wèn)題上往往產(chǎn)生混淆，不能夠清晰理解。

圖2 指針示意圖

對(duì)指針概念的理解應(yīng)該強(qiáng)調(diào)幾點(diǎn)：①指針變量也是變量，聲明了指針變量后同樣需要給該變量分配一塊存儲(chǔ)空間，只是該空間存儲(chǔ)的內(nèi)容有點(diǎn)特殊，是一個(gè)地址。②獲取數(shù)據(jù)存儲(chǔ)空間的基本方式有兩種，一是在程序的數(shù)據(jù)說(shuō)明部分進(jìn)行聲明，這樣，程序執(zhí)行時(shí)存儲(chǔ)空間已經(jīng)預(yù)先分配，并建立了變量名和存儲(chǔ)空間之間的映射，可稱為靜態(tài)分配。二是在程序執(zhí)行的過(guò)程中，通過(guò)申請(qǐng)（如malloc函數(shù)）獲得存儲(chǔ)空間，可稱為動(dòng)態(tài)分配，這樣的空間無(wú)法給予變量名，存取這樣空間的唯一辦法只能通過(guò)該空間的地址，即指向該地址的指針來(lái)存取。如圖2中圈1所示，malloc函數(shù)申請(qǐng)了一塊大小為4個(gè)字節(jié)的空間，空間起始地址是300，為了在后續(xù)程序中使用這塊存儲(chǔ)空間，該地址賦

值給指向整型的指針p，p中存儲(chǔ)的內(nèi)容變?yōu)?00。③應(yīng)該強(qiáng)調(diào)，作為派生類型，指針變量也是有數(shù)據(jù)類型的，其數(shù)據(jù)類型是指針變量所指向的存儲(chǔ)空間大小的約定。如圖2中定義的p是一個(gè)指向整型的指針，強(qiáng)調(diào)這一點(diǎn)有助于學(xué)生對(duì)指針應(yīng)用的理解。例如，表達(dá)式中，出現(xiàn)在指針變量前的*稱為指針運(yùn)算符，如賦值語(yǔ)句*p=21，其意義是給p中地址所指向的存儲(chǔ)空間賦值，圖2中，p中存有地址300，確定了被賦值空間的起始地址，而p的類型-整型，確定了這塊空間的大小，即*p確定了一塊從300開(kāi)始，長(zhǎng)度為4的存儲(chǔ)空間。變量的本質(zhì)是一塊存儲(chǔ)空間，那么反過(guò)來(lái)說(shuō)，一塊確定的存儲(chǔ)空間就是一個(gè)變量，*p確定了一塊存儲(chǔ)空間，它等價(jià)于變量，給*p賦值等價(jià)于給整型變量賦值。

三、指針的應(yīng)用

1.指針和數(shù)組。C語(yǔ)言中，數(shù)組名代表數(shù)組的起始地址，是一個(gè)常數(shù)，可以看做一個(gè)指針?！稊?shù)據(jù)結(jié)構(gòu)》中，線性表的順序映像存儲(chǔ)結(jié)構(gòu)是通過(guò)動(dòng)態(tài)申請(qǐng)的數(shù)組實(shí)現(xiàn)的，設(shè)線性表為a1，a2，…，an（n=20），數(shù)據(jù)元素類型為整型，其存儲(chǔ)結(jié)構(gòu)的定義如下所示：

上述代碼主要定義了結(jié)構(gòu)體數(shù)據(jù)類型Sqlist，該結(jié)構(gòu)體類型中包含3個(gè)域：elem，length和listsize，其中elem是一個(gè)整型的指針變量，用來(lái)指向申請(qǐng)存儲(chǔ)空間的起始地址。類型定義后可以聲明該類型的變量，如SqlistL；線性表的存儲(chǔ)空間（數(shù)組）需要申請(qǐng)，如圖3所示。

圖3 數(shù)組空間分配示意圖

malloc函數(shù)申請(qǐng)了一塊大小為80個(gè)字節(jié)的存儲(chǔ)空間，該空間的起始地址假設(shè)為100，函數(shù)返回后，地址100被賦值給整型的指針變量L.elem，即指針變量L.elem中存有地址100。

學(xué)生對(duì)靜態(tài)數(shù)組的使用相對(duì)熟練些，但往往不習(xí)慣動(dòng)態(tài)申請(qǐng)數(shù)組的使用，下面以線性表的遍歷為例來(lái)說(shuō)明一下其使用方式。動(dòng)態(tài)申請(qǐng)數(shù)組中遍歷的實(shí)現(xiàn)有兩種常用方式：一是把指針當(dāng)做數(shù)組名來(lái)使用。數(shù)組名是地址，可以看做指針，反之，指針同樣能夠看做是數(shù)組名。遍歷的代碼可以寫(xiě)為：

這里要注意理解中括號(hào)[]的意義，中括號(hào)本質(zhì)上是運(yùn)算符，它的意義是執(zhí)行操作L.elem+i（這里要關(guān)注指針的類型，即不同類型的指針加i，計(jì)算結(jié)果是不同的），找到存儲(chǔ)ai+1這個(gè)整型數(shù)據(jù)的4個(gè)字節(jié)空間的起始地址，隨后根據(jù)指針的類型（確定大?。嫒∵@4個(gè)字節(jié)的存儲(chǔ)空間。

二是通過(guò)指針來(lái)進(jìn)行遍歷。遍歷的代碼可以寫(xiě)為：

整型指針p首先被賦值L.elem，圖3中是100，這時(shí)p指向數(shù)組中第0號(hào)單元的起始地址，通過(guò)指針運(yùn)算符*p存取從100開(kāi)始的4個(gè)字節(jié)空間，即數(shù)組中第0號(hào)單元。隨后，通過(guò)p的自加運(yùn)算，指針p后移4個(gè)字節(jié)（p是整型指針），依次對(duì)數(shù)組中所有元素進(jìn)行遍歷。從結(jié)果上來(lái)看，代碼（1）和代碼（2）是完全等價(jià)的。

2.鏈表。線性表的非順序映像存儲(chǔ)結(jié)構(gòu)是鏈表實(shí)現(xiàn)的。定義鏈表結(jié)點(diǎn)（結(jié)構(gòu)體），動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)存儲(chǔ)空間，線性表每個(gè)數(shù)據(jù)元素存儲(chǔ)在一個(gè)結(jié)點(diǎn)中，通過(guò)指針描述數(shù)據(jù)元數(shù)之間的關(guān)系，其結(jié)點(diǎn)的定義如下所示：

上述代碼主要定義了結(jié)構(gòu)體數(shù)據(jù)類型LNode 和指向結(jié)構(gòu)體的指針類型LinkList，該結(jié)構(gòu)體類型中包含2個(gè)域：存儲(chǔ)數(shù)據(jù)元素的域data和指針域next，next用來(lái)指向本結(jié)點(diǎn)數(shù)據(jù)元數(shù)在邏輯結(jié)構(gòu)中的后繼，鏈表如圖4所示。

圖4 鏈表示意圖

仍以線性表的遍歷為例來(lái)說(shuō)明其使用方式，利用指針p來(lái)進(jìn)行遍歷，代碼可以寫(xiě)為：

p被賦值p=head-＞next，指向首元結(jié)點(diǎn)，隨后通過(guò)循環(huán)中p=p-＞next語(yǔ)句，p依次指向后繼結(jié)點(diǎn)，直到鏈表結(jié)束。這里要注意對(duì)-＞操作符的理解，當(dāng)指針p指向一個(gè)結(jié)構(gòu)體存儲(chǔ)空間時(shí)，如果需要存取結(jié)構(gòu)體中的某個(gè)域，可以使用“p-＞域名”的方式，如p-＞data就是存取該結(jié)構(gòu)體中的data域；另有一種等價(jià)的方式“*p.域名”，如*p.data，*p確定一塊結(jié)構(gòu)體空間（結(jié)構(gòu)體變量），用“.”操作符存取結(jié)構(gòu)體變量的某個(gè)域。

3.指向函數(shù)的指針。函數(shù)載人內(nèi)存時(shí)，必定占有一塊存儲(chǔ)空間，可以定義指向函數(shù)的指針，通過(guò)指針來(lái)調(diào)用函數(shù)，例如：

首先定義了一個(gè)指向函數(shù)的指針p，隨后p被賦值函數(shù)名，即讓p指向函數(shù)fun，p指向fun后，可以通過(guò)指向函數(shù)的指針調(diào)用函數(shù)，其效果和通過(guò)函數(shù)名調(diào)用是等價(jià)的。應(yīng)該注意到，這樣用法毫無(wú)價(jià)值，能通過(guò)函數(shù)名調(diào)用，何必還要間接用指針調(diào)用。因此，指向函數(shù)的指針一般用作函數(shù)的形式參數(shù)，例如：

假設(shè)有數(shù)據(jù)元素為整型的二叉樹(shù)T，Preorder是實(shí)現(xiàn)二叉樹(shù)的先序遍歷的函數(shù)。上述代碼中，首先給出了兩個(gè)函數(shù)返回值為Status的函數(shù)原型，設(shè)Sub是對(duì)整數(shù)進(jìn)行減處理的函數(shù)，Add是進(jìn)行加處理的函數(shù)。那么，Preorder（T，Sub）調(diào)用時(shí)，函數(shù)名Sub作為實(shí)參傳遞給形參visit（指向函數(shù)的指針），則在遍歷過(guò)程中（*visit）（a）所調(diào)用的函數(shù)是Sub；同理，Preorder（T，Add）調(diào)用時(shí)，（*visit）（a）所調(diào)用的函數(shù)是Add。這里應(yīng)該強(qiáng)調(diào)，為什么要這么做？從上例中看，對(duì)二叉樹(shù)的遍歷過(guò)程是一樣的，通過(guò)兩次調(diào)用中visit所指的函數(shù)不同，對(duì)二叉樹(shù)T中數(shù)據(jù)元素的處理不同，一次是減，一次是加。指向函數(shù)的指針帶來(lái)的好處是，如果對(duì)數(shù)據(jù)元素的處理有新的變化，如增加乘的處理，僅需要編寫(xiě)乘的函數(shù)Mul，隨后調(diào)用Preorder（T，Mul）就可實(shí)現(xiàn)對(duì)二叉樹(shù)中數(shù)據(jù)元素的乘處理，不需要改變Preorder函數(shù)。這樣的程序結(jié)構(gòu)非常有利于提高程序的可維護(hù)性。

四、小結(jié)

作為實(shí)踐性很強(qiáng)的計(jì)算機(jī)專業(yè)核心課程，《數(shù)據(jù)結(jié)構(gòu)》課程的實(shí)驗(yàn)環(huán)節(jié)非常重要，指針的靈活應(yīng)用是課程實(shí)驗(yàn)中的難點(diǎn)。學(xué)生對(duì)指針了理解往往流于表面，只會(huì)模仿性應(yīng)用，不能深入理解和靈活應(yīng)用。文中，我們結(jié)合實(shí)際的教學(xué)經(jīng)驗(yàn)，總結(jié)了指針中的幾個(gè)學(xué)生不容易掌握的問(wèn)題，并分析討論了教學(xué)中的要點(diǎn)。通過(guò)多年的教學(xué)實(shí)踐，對(duì)學(xué)生《數(shù)據(jù)結(jié)構(gòu)》課程的學(xué)習(xí)和提高編程能力是有幫助的。

[1]陳越，何欽銘，馮雁.“數(shù)據(jù)結(jié)構(gòu)”綜合性課程設(shè)計(jì)教學(xué)探索與實(shí)踐[J].計(jì)算機(jī)教育，2008，（8）：54-55.

[2]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，2009.

G642

A

1674-9324（2014）04-0110-03

清華攜手Google助力西部教育項(xiàng)目-2012年精品課程建設(shè)項(xiàng)目“數(shù)據(jù)結(jié)構(gòu)”；2013年云南省教學(xué)改革研究項(xiàng)目“面向?qū)ο筌浖_(kāi)發(fā)系列課程教學(xué)改革探索”；云南大學(xué)“中青年骨干教師培養(yǎng)計(jì)劃”項(xiàng)目（編號(hào)：XT412004）。

孔兵，男，博士，副教授，研究方向?yàn)橹悄軘?shù)據(jù)處理；陳紅梅，博士，女，講師，研究方向?yàn)閿?shù)據(jù)挖掘；袁國(guó)武，男，博士，講師，研究方向?yàn)閳D形圖像處理。