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