韓瑩 白靈

【摘要】實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式，順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是兩種最主要的存儲(chǔ)方式。但是數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)對學(xué)生來說是一個(gè)很抽象的概念。根據(jù)多年講授C語言的實(shí)踐和體會(huì)，并結(jié)合C語言課程的特征，通過使用類比教學(xué)法，深度剖析了順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，使學(xué)生全面的理解和掌握數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的概念。

【關(guān)鍵詞】類比法 C語言教學(xué) 數(shù)據(jù)存儲(chǔ) 鏈表 數(shù)組

【 基金項(xiàng)目】防災(zāi)科技學(xué)院重點(diǎn)教研項(xiàng)目2012A04；防災(zāi)科技學(xué)院第一批精品建設(shè)課程。

【中圖分類號】TP313 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號】2095-3089（2013）06-0136-02

形象類比法屬于講授教學(xué)方法的一種，即借助于兩類不同本質(zhì)事物之間的相似性，通過比較，形象地將一種已經(jīng)熟悉或掌握的特殊對象推移到另一種新的特殊對象上去的推理手段，也是教學(xué)中創(chuàng)設(shè)真實(shí)生動(dòng)情景的有效工具之一[1]。

在自然界中，數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)關(guān)系存在兩種不同的表示方法：順序映象和非順序映象，并由此得到在計(jì)算機(jī)中兩種不同的物理存儲(chǔ)結(jié)構(gòu)表示：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)。鏈接存儲(chǔ)方法它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針類型來實(shí)現(xiàn)。

數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)對初學(xué)者來說非常抽象，文章提出了形象類比法將抽象概念形象化，幫助學(xué)生很好的掌握數(shù)據(jù)在計(jì)算機(jī)中的物理存儲(chǔ)概念。

一、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的創(chuàng)建

如何來理解順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，分別以一維數(shù)組和單鏈表為例，用一個(gè)形象的例子來說明空間是如何來分配的。

假如現(xiàn)在一個(gè)有20個(gè)人的班級的全體同學(xué)出去旅游幾天，首先解決的就是住宿問題，內(nèi)存就像一個(gè)很大的賓館，這20個(gè)人有兩種入住的的方法。

1.1建立數(shù)組

第一種，假設(shè)目前是旅游淡季，20個(gè)同學(xué)在賓館里要了連續(xù)的20個(gè)房間，然后按學(xué)號的順序入住在這20間房間里，用C程序語言描述為：

int a[20]；// 內(nèi)存連續(xù)的分配20個(gè)int大小的空間

1.2建立單鏈表

第二種，假設(shè)目前是旅游旺季，沒有連續(xù)的20個(gè)房間，還要保證在知道第一個(gè)學(xué)生的房間號的情況下，能找到所有其他學(xué)生的房間號，那么如何分配呢？首先給1號學(xué)生分配一個(gè)房間，把1號學(xué)生的房間號告訴班主任；然后給2號學(xué)生分配一個(gè)房間，把2號學(xué)生的房間號告訴1號學(xué)生；再給3號學(xué)生分配一個(gè)房間，把3號學(xué)生的房間號告訴2號學(xué)生……最后當(dāng)所有學(xué)生的都入住進(jìn)去之后，單鏈表就形成了。建立一個(gè)含有20個(gè)元素的單鏈表，用C程序語言描述為：

typedef struct Node

{ int data；

struct Node *next；

}List；

List *Create（）

{ int a，i=1；

List *head，*p，*q；

p=（List *）malloc（sizeof（struct Node））；//為第一個(gè)學(xué)生分配一個(gè)房間

scanf（“%d”，&p->data）；

head=p；

while（i<20）

{ q=（List *）malloc（sizeof（struct Node））；//為后面的每一個(gè)學(xué)生分配一個(gè)房間

scanf（“%d”，&q->data）；

q->next=NULL；

p->next=q；

p=q；

i++；

}

return head；

}

整個(gè)鏈表建立完成之后，返回單鏈表的首地址，也就是班級負(fù)責(zé)人記錄下1號學(xué)生的房間號。

二、數(shù)據(jù)的查找

2.1在一維數(shù)組中查找數(shù)據(jù)

如何在順序表中查找某一個(gè)元素呢？現(xiàn)在我們已經(jīng)知道第一個(gè)學(xué)生的房間號，根據(jù)數(shù)組數(shù)據(jù)存放的特點(diǎn)，即20個(gè)學(xué)生之間是連續(xù)的入住在賓館里，那么我們可以通過學(xué)號計(jì)算出任何一個(gè)學(xué)生的房間號。Loc表示某個(gè)元素的地址，那么：Loc（a[i]）=Loc（a[0]）+i；時(shí)間復(fù)雜度為O（1），所以數(shù)組是隨機(jī)存取結(jié)構(gòu)，可以隨機(jī)存取數(shù)組中的任意一個(gè)元素。

2.2在單鏈表中查找數(shù)據(jù)

如何在單鏈表中查找某一個(gè)元素呢？例如：如何查找4號學(xué)生的房間號？我們知道4號學(xué)生的房間號3號學(xué)生知道，而3號學(xué)生的房間號2號學(xué)生知道……所有我們要在單鏈表中查找某個(gè)學(xué)生的房間號必須從1號學(xué)生開始，1號學(xué)生知道2號學(xué)生的房間號，2號學(xué)生知道3號學(xué)生的房間號……。查找的時(shí)間復(fù)雜度為O（n）。用C程序語言表示如下：

List *Search（List *head，int i）//head 存放1號學(xué)生的房間號，i待查找的學(xué)生的學(xué)號

{ List *p；

p=head；

while（i！=p->data） p-p->next；

return p； //返回i號學(xué)生的房間號

}

三、數(shù)據(jù)的插入和刪除

3.1在一維數(shù)組中插入和刪除數(shù)據(jù)

如何在順序表中刪除某一個(gè)元素呢？假設(shè)現(xiàn)在在旅游期間的第二天學(xué)號為5號的學(xué)生因?yàn)橛惺虑樘崆胺敌?，如何刪除該數(shù)據(jù)，使得其他數(shù)據(jù)在內(nèi)存中物理位置仍然是連續(xù)的，即剩余的其他同學(xué)在賓館中的房間是緊密相連的，應(yīng)該如何操作呢？那就要求從6號學(xué)生開始，后面的學(xué)生陸續(xù)搬家。6號學(xué)生搬到5號學(xué)生的房間，7號學(xué)生搬到8號學(xué)生的房間……直到20號學(xué)生搬到19號學(xué)生的房間。此算法的平均時(shí)間復(fù)雜度為O（n），用C程序語言表示為：

void delete（int a[]，int n）//在數(shù)組a中刪除下標(biāo)為n的元素

{ int i；

for（i=n；i<20；i++） a[i]=a[i+1]；

}

如何在順序表中插入一個(gè)元素呢？假設(shè)5號學(xué)生處理完學(xué)校的事情了，第四天又來回到賓館，為了讓他們?nèi)匀皇前凑諏W(xué)號有序的方式入住在連續(xù)相鄰的賓館里，該如何操作呢？這就要求從最后一名學(xué)生一直到6號學(xué)生陸續(xù)搬家，給5號學(xué)生騰出房間，即：19號學(xué)生搬回到原先的第20個(gè)房間，給18號學(xué)生騰出房間，18號學(xué)生搬到19號學(xué)生給騰出來的房間，17號學(xué)生搬到18學(xué)生騰出來的房間……直到5號房間空閑，5號學(xué)生住進(jìn)去。此算法的時(shí)間復(fù)雜度為O（n），用C程序語言表示為：

void insert（int a[]，int n，int m）//在數(shù)組a的下標(biāo)為n的位置插入一個(gè)元素m

{ int i；

for（i=19；i>n；i--） a[i]=a[i+1]；

a[n]=m；

}

3.2在單鏈表中插入和刪除數(shù)據(jù)

如何在單鏈表中刪除一個(gè)元素呢？現(xiàn)在仍然假設(shè)5號學(xué)生在旅游的第二天因?yàn)橛惺虑樘崆胺敌?，如何刪除數(shù)據(jù)使得單鏈表中的元素仍然是線性關(guān)系呢？顯然5號學(xué)生離開，只需要把他所知道的6號學(xué)生的房間號告訴4號學(xué)生就可以了。此算法的時(shí)間復(fù)雜度為O（1），用C程序語言來表示為：

void detele（List *head，int n）//在單鏈表中刪除一個(gè)元素

{ List *p；

p=search（head，n）；//search函數(shù)返回值為待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

if（P->next！=NULL）

{ p->next=p->p->next；

free（p->next）；

}

}

如何在單鏈表中插入一個(gè)元素呢？現(xiàn)在仍假設(shè)5號學(xué)生處理完學(xué)校的事情后第四天返回賓館，為了保證數(shù)據(jù)之間仍然是按學(xué)號的順序組成的一個(gè)鏈，該如何操作呢？首先給5號學(xué)生在賓館里分配一個(gè)空房間，5號學(xué)生住進(jìn)去；然后找到5號學(xué)生應(yīng)該插入的位置，在4號之后，6號之前，修改指針，即把6號學(xué)生的房間號告訴5號學(xué)生，然后把5號學(xué)生的房間號告訴4號學(xué)生，他們之間又形成了一條新的鏈。此算法的時(shí)間復(fù)雜度為O（1），用C程序語言表示如下：

void insert（List *head，int n）

{ List *s，*p；

p=search（head，n）；//search函數(shù)返回值為待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

s=（List *）malloc（sizeof（stuct node））

s->data=n；

s->next=p->next->next；

p->next=s；

}

四、數(shù)組與鏈表的優(yōu)缺點(diǎn)比較

通過形象的類比法，很容易看出數(shù)組和鏈表的差別及各自的優(yōu)缺點(diǎn)。

數(shù)組在內(nèi)存開辟連續(xù)的一片區(qū)域，而鏈表可以連續(xù)，也可以不連續(xù)；數(shù)組中的數(shù)據(jù)在內(nèi)存中是按順序存儲(chǔ)的，要訪問數(shù)組中的元素可以按照下標(biāo)索引來訪問，速度比較快；但是對數(shù)組進(jìn)行插入和刪除算法，平均需要移動(dòng)一半的元素，所以對數(shù)組進(jìn)行插入和刪除操作效率很低。

鏈表是隨機(jī)存儲(chǔ)的，鏈表的插入，刪除操作效率很高，只需要修改指針。但是要訪問鏈表中的某個(gè)元素的話，需從頭指針順著鏈表掃描才能取得，所以鏈表的隨機(jī)訪問的效率比數(shù)組低。

參考文獻(xiàn)：

[1] 徐學(xué)福.論類比教學(xué)模式[J].廣西師范大學(xué)學(xué)報(bào)（哲學(xué)社會(huì)科學(xué)版），1998，34（2）：27～32

[2]譚浩強(qiáng).C程序多設(shè)計(jì).第3版.清華大學(xué)出版社，2005

[3]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu).第2版.清華大學(xué)出版社，2001

[4]韓瑩，豐繼林，單維鋒.C語言實(shí)訓(xùn)教程.第1版.清華大學(xué)出版社，2013.1