C++的基于函數(shù)模板實(shí)現(xiàn)單向鏈表

宮彥軍　史小飛

?

C++的基于函數(shù)模板實(shí)現(xiàn)單向鏈表

宮彥軍1史小飛2

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

在“C++程序設(shè)計(jì)”教學(xué)中函數(shù)模板部分是難點(diǎn)，文章給出利用鏈表函數(shù)模板實(shí)現(xiàn)單向鏈表節(jié)點(diǎn)的創(chuàng)建、有序插入和刪除的操作，文章中的鏈表函數(shù)模板可以實(shí)現(xiàn)具有任意數(shù)據(jù)域的單向鏈表節(jié)點(diǎn)的創(chuàng)建、有序插入和刪除，只是要事先設(shè)計(jì)好鏈表的數(shù)據(jù)類或者數(shù)據(jù)類型，對(duì)于有序插入，數(shù)據(jù)類型具有比較運(yùn)算，如果是數(shù)據(jù)類，需要重載數(shù)據(jù)類的比較運(yùn)算符。

C++語言；構(gòu)造函數(shù)；調(diào)用

1　引　言

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

2　鏈表的創(chuàng)建和插入函數(shù)模板

2.1鏈表的創(chuàng)建和插入

鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，C++語言有指針，指針是存儲(chǔ)變量地址的變量，C++的鏈表用類指針來實(shí)現(xiàn)的。首先定一個(gè)類，類包含一個(gè)數(shù)據(jù)元素域和一個(gè)指向本類類型指針域，下面是鏈表創(chuàng)建和插入的函數(shù)模板。

template

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

{//把1個(gè)數(shù)據(jù)插入鏈表

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鏈表的創(chuàng)建和插入操作

insert這個(gè)函數(shù)模板，包含創(chuàng)建和插入兩種鏈表操作，使用時(shí)首先定義頭結(jié)點(diǎn)head，是指針，賦初值NULL，具體代碼如下，

首先，定義包含一個(gè)數(shù)據(jù)域和指向本類指針的一個(gè)類。

class nodei

{public:

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

nodei的數(shù)據(jù)域只包含一個(gè)整型數(shù)。

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

由于numi的初值為NULL，則這時(shí)的insert創(chuàng)建頭結(jié)點(diǎn)，數(shù)據(jù)域存儲(chǔ)的是整數(shù)1。我們開發(fā)詞根分解程序用到nodei型鏈表。創(chuàng)建過程如圖1所示。

圖1.用insert創(chuàng)建nodei型頭節(jié)點(diǎn)

insert的第一個(gè)形參為指針引用，指針引用在調(diào)用時(shí)，形參為實(shí)參的拷貝，和實(shí)參指針變量的地址相同，可以實(shí)現(xiàn)鏈表的創(chuàng)建和插入。圖2為nodei型節(jié)點(diǎn)的插入過程。

圖2.鏈表插入

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

數(shù)據(jù)域的類：

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重載了運(yùn)算符“<=”，定義包含一個(gè)數(shù)據(jù)域dispart_word和指向本類指針的一個(gè)類。

class node{

public:

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

};

創(chuàng)建鏈表的具體過程如下：

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

這里的t是dispart_word類的對(duì)象。執(zhí)行insert前如圖3所示，執(zhí)行insert后如圖4所示，

圖3. node型頭結(jié)點(diǎn)初始化為NULL

圖4.用insert創(chuàng)建node型頭節(jié)點(diǎn)

在圖4所示的創(chuàng)建節(jié)點(diǎn)后，插入1個(gè)節(jié)點(diǎn)后如圖5所示。

圖5. node型節(jié)點(diǎn)的插入

從圖5可以看出在鏈表中插入1個(gè)節(jié)點(diǎn)的過程，圖5中的鏈表含有2個(gè)節(jié)點(diǎn)。

3　刪除鏈表

鏈表的刪除操作的函數(shù)模板如下，

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個(gè)數(shù)據(jù)，刪除后鏈表為NULL。

圖6.nodei型鏈表的刪除

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

圖7.node型鏈表的刪除

結(jié)　論

文章給出了利用函數(shù)模板實(shí)現(xiàn)鏈表的創(chuàng)建、有序插入和刪除，這里的創(chuàng)建和插入用同一個(gè)函數(shù)模板實(shí)現(xiàn)的，當(dāng)定義節(jié)點(diǎn)的指針為NULL時(shí)，執(zhí)行插入操作時(shí)就是創(chuàng)建鏈表的頭節(jié)點(diǎn)。文章通過編寫的詞根分解程序中用到的2個(gè)鏈表進(jìn)行了鏈表的創(chuàng)建、有序插入和刪除的演示。

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

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

[3] 何遠(yuǎn)強(qiáng),李全艷,彭海平,等.C++函數(shù)模板的模板參數(shù)類型轉(zhuǎn)換技術(shù)[J].科技創(chuàng)新導(dǎo)報(bào),2014,(10):19-20.

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

[5] 胡傳福.從鏈表的實(shí)現(xiàn)論C/C++與數(shù)據(jù)結(jié)構(gòu)教學(xué)[J].東莞理工學(xué)院學(xué)報(bào),2013,(3):125-127.

（責(zé)任編校：何俊華）

2017－01－08

永州市指導(dǎo)性科技創(chuàng)新及應(yīng)用研究項(xiàng)目（永科發(fā)(2016)32號(hào)）；湖南省普通高等學(xué)?！笆濉睂I(yè)綜合改革試點(diǎn)項(xiàng)目（湘教通〔2016〕276號(hào)）；湖南省自然科學(xué)基金資助項(xiàng)目(13JJ6079)。

宮彥軍（1969－），男，吉林公主嶺人，湖南科技學(xué)院教授，博士，研究方向?yàn)槟繕?biāo)與環(huán)境的電磁散射與光散射特性，以及電磁（光）波傳播與散射。

G642.0

A

1673-2219（2017）10-0042-03