C++的基于函數模板實現單向鏈表

宮彥軍　史小飛

?

C++的基于函數模板實現單向鏈表

宮彥軍1史小飛2

（1.湖南科技學院 電子與信息工程學院，湖南 永州 425199；2.湖南科技學院 圖書館，湖南 永州 425199）

在“C++程序設計”教學中函數模板部分是難點，文章給出利用鏈表函數模板實現單向鏈表節點的創建、有序插入和刪除的操作，文章中的鏈表函數模板可以實現具有任意數據域的單向鏈表節點的創建、有序插入和刪除，只是要事先設計好鏈表的數據類或者數據類型，對于有序插入，數據類型具有比較運算，如果是數據類，需要重載數據類的比較運算符。

C++語言；構造函數；調用

1　引　言

C++語言中的函數模板能提高編程的效率[1]。文獻[2]采用漸進式的三步教學法進行函數模板的教學，能取得良好的教學效果。文獻[3]利用C++函數模板的方法完成模板參數類型的顯式轉換機制。文獻[4]研究了函數模板的概念和語法規則。文獻[5]從鏈表的實現討論C/C++與數據結構的教學。文章利用函數模板實現鏈表的創建、插入和刪除的基本操作。

2　鏈表的創建和插入函數模板

2.1鏈表的創建和插入

鏈表是一種常見的數據結構，C++語言有指針，指針是存儲變量地址的變量，C++的鏈表用類指針來實現的。首先定一個類，類包含一個數據元素域和一個指向本類類型指針域，下面是鏈表創建和插入的函數模板。

template

void insert(T *&head,const T1 &data)

{//把1個數據插入鏈表

T *pb=head,*pf; T *pi=new T;

pi->data=data;

if(head==NULL){

head=pi;pi->next=NULL;}

else{ while((pi->data<=pb->data)&&(pb->next!=NULL)){

pf=pb;pb=pb->next;}

if(pi->data>pb->data){

if(head==pb){head=pi;pi->next=pb;}

else{pf->next=pi;pi->next=pb;}

else{pb->next=pi;pi->next=NULL;}

}

2.2鏈表的創建和插入操作

insert這個函數模板，包含創建和插入兩種鏈表操作，使用時首先定義頭結點head，是指針，賦初值NULL，具體代碼如下，

首先，定義包含一個數據域和指向本類指針的一個類。

class nodei

{public:

nodei(){data=0;next=NULL;}int data; nodei *next;};

nodei的數據域只包含一個整型數。

其次，聲明一個頭結點，即指向nodei的指針，賦初值NULL。具體代碼：nodei *numi=NULL;insert(numi,1);

由于numi的初值為NULL，則這時的insert創建頭結點，數據域存儲的是整數1。我們開發詞根分解程序用到nodei型鏈表。創建過程如圖1所示。

圖1.用insert創建nodei型頭節點

insert的第一個形參為指針引用，指針引用在調用時，形參為實參的拷貝，和實參指針變量的地址相同，可以實現鏈表的創建和插入。圖2為nodei型節點的插入過程。

圖2.鏈表插入

insert的插入為順序插入，為從大到小排序，使用文章的insert函數模板，數據域的數據名稱為data，具有“<=”運算符比較，如果數據域的數據為類，必需要重載運算符“<=”，下面是我們編寫詞根分解程序中用到的另外一個鏈表。

數據域的類：

class dispart_word{

public:

CString word;int rootl;int rootnum;nodei *maxrootl;

dispart_word(const CString &word="",

const int &rootl=0,const int &rootnum=0);

virtual ~dispart_word();

dispart_word& operator=(const dispart_word &);

dispart_word(const dispart_word& t);

bool operator>(const dispart_word &);

bool operator<=(const dispart_word &);

bool operator!=(const dispart_word &);

bool operator==(const dispart_word &);

void DeleteMaxrootl();

};

dispart_word重載了運算符“<=”，定義包含一個數據域dispart_word和指向本類指針的一個類。

class node{

public:

node(){next=NULL;}dispart_word data; node *next;

};

創建鏈表的具體過程如下：

node *m_record=NULL;insert(m_record,t);

這里的t是dispart_word類的對象。執行insert前如圖3所示，執行insert后如圖4所示，

圖3. node型頭結點初始化為NULL

圖4.用insert創建node型頭節點

在圖4所示的創建節點后，插入1個節點后如圖5所示。

圖5. node型節點的插入

從圖5可以看出在鏈表中插入1個節點的過程，圖5中的鏈表含有2個節點。

3　刪除鏈表

鏈表的刪除操作的函數模板如下，

template

void Delete(T *&head)

{

T *t;

while(head!=NULL){

t=head;head=head->next;delete t;}

head=NULL;

}

圖6給出刪除前面定義的nodei型鏈表的過程，圖6(a)為nodei型鏈表刪除前，圖6(b)為nodei型鏈表刪除后。從圖6(a)可以看出刪除前鏈表包含8個數據，刪除后鏈表為NULL。

圖6.nodei型鏈表的刪除

圖7給出刪除前面定義的node型鏈表的過程，圖7(a)為node型鏈表刪除前，圖7(b)為nodei型鏈表刪除后。從圖7(a)可以看出刪除前鏈表包含2個數據，刪除后鏈表為NULL。

圖7.node型鏈表的刪除

結　論

文章給出了利用函數模板實現鏈表的創建、有序插入和刪除，這里的創建和插入用同一個函數模板實現的，當定義節點的指針為NULL時，執行插入操作時就是創建鏈表的頭節點。文章通過編寫的詞根分解程序中用到的2個鏈表進行了鏈表的創建、有序插入和刪除的演示。

[1] 王大志.函數模板在數據持久化中的應用[J].電腦編程技巧與維護,2013,(10):36-38.

[2] 葛建芳.C++函數模板教學方法探討[J].福建電腦,2006, (11):213+171.

[3] 何遠強,李全艷,彭海平,等.C++函數模板的模板參數類型轉換技術[J].科技創新導報,2014,(10):19-20.

[4] 陳偉柱.函數模板[J].程序員,2003,(12):120-123.

[5] 胡傳福.從鏈表的實現論C/C++與數據結構教學[J].東莞理工學院學報,2013,(3):125-127.

（責任編校：何俊華）

2017－01－08

永州市指導性科技創新及應用研究項目（永科發(2016)32號）；湖南省普通高等學校“十三五”專業綜合改革試點項目（湘教通〔2016〕276號）；湖南省自然科學基金資助項目(13JJ6079)。

宮彥軍（1969－），男，吉林公主嶺人，湖南科技學院教授，博士，研究方向為目標與環境的電磁散射與光散射特性，以及電磁（光）波傳播與散射。

G642.0

A

1673-2219（2017）10-0042-03