韓瑩 白靈

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

【關鍵詞】類比法 C語言教學 數(shù)據(jù)存儲 鏈表 數(shù)組

【 基金項目】防災科技學院重點教研項目2012A04；防災科技學院第一批精品建設課程。

【中圖分類號】TP313 【文獻標識碼】A 【文章編號】2095-3089（2013）06-0136-02

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

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

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

一、順序存儲和鏈式存儲的創(chuàng)建

如何來理解順序存儲結構和鏈式存儲結構，分別以一維數(shù)組和單鏈表為例，用一個形象的例子來說明空間是如何來分配的。

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

1.1建立數(shù)組

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

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

1.2建立單鏈表

第二種，假設目前是旅游旺季，沒有連續(xù)的20個房間，還要保證在知道第一個學生的房間號的情況下，能找到所有其他學生的房間號，那么如何分配呢？首先給1號學生分配一個房間，把1號學生的房間號告訴班主任；然后給2號學生分配一個房間，把2號學生的房間號告訴1號學生；再給3號學生分配一個房間，把3號學生的房間號告訴2號學生……最后當所有學生的都入住進去之后，單鏈表就形成了。建立一個含有20個元素的單鏈表，用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））；//為第一個學生分配一個房間

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

head=p；

while（i<20）

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

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

q->next=NULL；

p->next=q；

p=q；

i++；

}

return head；

}

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

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

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

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

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

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

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

{ List *p；

p=head；

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

return p； //返回i號學生的房間號

}

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

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

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

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

{ int i；

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

}

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

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

{ int i；

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

a[n]=m；

}

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

如何在單鏈表中刪除一個元素呢？現(xiàn)在仍然假設5號學生在旅游的第二天因為有事情提前返校，如何刪除數(shù)據(jù)使得單鏈表中的元素仍然是線性關系呢？顯然5號學生離開，只需要把他所知道的6號學生的房間號告訴4號學生就可以了。此算法的時間復雜度為O（1），用C程序語言來表示為：

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

{ List *p；

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

if（P->next！=NULL）

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

free（p->next）；

}

}

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

void insert（List *head，int n）

{ List *s，*p；

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

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

s->data=n；

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

p->next=s；

}

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

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

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

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

參考文獻：

[1] 徐學福.論類比教學模式[J].廣西師范大學學報（哲學社會科學版），1998，34（2）：27～32

[2]譚浩強.C程序多設計.第3版.清華大學出版社，2005

[3]嚴蔚敏.數(shù)據(jù)結構.第2版.清華大學出版社，2001

[4]韓瑩，豐繼林，單維鋒.C語言實訓教程.第1版.清華大學出版社，2013.1