单链表不同建立算法研究

摘 要:单链表是最简单的一类数据结构――线性表的非顺序机内表示,在计算机科学以及其他研究领域都有广泛应用。深入分析基于C++引用参数和基于C/C++指针建立单链表的两类不同算法的具体实现原理。并在对后一算法常见错误进行深入分析的基础上,给出两种基于C/C++指针的单链表建立算法。以期对相关领域的研究及软件开发有启发和指导意义。

关键词:单链表;算法;指针;引用参数

中图分类号:TP311文献标识码:A

文章编号:1004-373X(2010)04-132-03

Study of Algorithms for Creating Simply-linked Linear List

XIE Juanying

(School of Computer Science,Shaanxi Normal University,Xi′an,710062,China)

Abstract:Simply-linked linear list is the physical structure of a linear list,and it can be applied in many fields.A thorough analysis is carried out on the algorithms of creating a simply-linked linear list based on the reference parameter of C++ and on the pointers of C/C++.Then the error that often occurs in the later algorithm is analyzed,and two pointer-based algorithms are presented for creating a simply-linked linear list as well.

Keywords:simply-linked linear list;algorithm;pointer;reference parameter

0 引 言

单链表是线性表的一种非顺序存储表示[1-5],属于非数值计算领域的数学模型――线性结构的范畴,是计算机科学中数据结构的一项重要研究内容,也是数学建模的一个非常重要部分,在应用软件开发和科学研究中有着重要且广泛的应用[6-11]。关于单链表的建立算法,目前存在两种方案:采用C++中的引用参数和基于C/C++的指针。但是,基于指针的单链表建立算法,稍不细心,或者程序语言中变量的有效范围、参数传递的方式、指针的应用等稍不留神,就会出现问题,达不到预期目标,甚至引起意想不到的错误。

在此结合C/C++程序设计语言中的变量有效范围、参数传递方式、指针应用等,深入分析了基于C++引用参数的单链表建立算法和基于C/C++指针的单链表建立算法;剖析了常见的基于指针建立单链表的算法所容易犯的错误;给出了基于指针的两种单链表建立算法,同时对他们的正确性进行了深入分析。

1 建立单链表的两类不同实现方案

单链表建立算法所用到的类型定义:

struct Lnode;

typedef Lnode* linklist;

typedef struct Lnode

{

datatype data;//datatype可以根据实际应用需要给出具体定义

linklist next;

}LNode;

1.1 基于C++引用参数的单链表建立算法

1.1.1 基于C++引用参数的单链表建立算法描述和一个简单的driver

void creat( linklist& la)

{

p=new LNode;

p->next=NULL;

la=p;

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=la->next;

la->next=s;

cin>>x;

}

}

int main()

{

creat(l);// linklist l;

traverse(l);//访问单链表

return 0;

}

1.1.2 基于C++引用参数的单链表建立算法实现原理分析

上面基于C++引用参数的单链表建立算法,由于采用了C++的引用参数作为单链表建立函数creat的参数,在creat函数被调用时,形参la获得并接受了实参指针变量l的地址[10]。因此,形参la和实参l共享了同一段存储空间,在creat函数的函数体内部对于形参la所指存储单元内容的修改直接影响实参l的内容。即在creat函数体内对于函数形参la所指存储单元内容的修改实际上是修改了实参l指存储单元的内容,因此修改后的值可以被带回主调函数,从而建立了单链表。

1.2 基于C/C++指针的单链表建立算法

1.2.1 基于C/C++指针的单链表建立算法的常见错误及其分析

void creat( linklist la)

{

p=new LNode;

p->next=NULL;

la=p;

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=la->next;

la->next=s;

cin>>x;

}

}

对应的simple driver 如下:

int main()

{

creat(l);//linklist l;

traverse(l);//访问单链表

return 0;

}

上述算法不能建立单链表。因为creat函数参数表中的la属于该函数的局部变量[12]。它的有效范围只局限于其所在函数,在creat函数内对于la的改变不能被带回主调函数。同时,C/C++函数参数的传递都是单方向的值传递,要想将在函数内部改变了的值带回主调函数,只有让形参接受实参的地址,在被调函数内修改实参地址中的内容,从而达到目的。这样,就必须使用指针或引用参数。在此,实际上是需要使用指向指针相变量la的指针作为creat函数形参。因此,该creat函数不能达到建立一个带头结点的单链表l的预期目标。

1.2.2 基于C/C++指针建立单链表的两种算法

算法1:creat函数的参数使用指针,即指向指针的指针。

void creat( linklist* la)

{

p=new LNode;

p->next=NULL;

*la=p;

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=(*la)->next;

(*la)->next=s;

cin>>x;

}

}

相应的简单主调函数如下:

int main()

{

creat(&l);//linklist l;

traverse(l);//访问单链表

return 0;

}

特别注意:此处调用传递的是指针型变量l的地址[13]。这样形参才能获得指针性变量l的地址,对于实参l内容的改变才可以被带回主调函数,从而实现单链表的建立。此处,改变的是指针l值。

算法2:增加一个独立的初始化函数。creat函数也作相应修改。对应的simple driver也需要一些小改动。

void initiate(linklist* la)

{

(*la)=new LNode;

(*la)->next=NULL;

}

void creat(linklist la)

{

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=la->next;

la->next=s;

cin>>x;

}

}

int main()

{

initiate(&l);//linklist l;

creat(l);

traverse(l);//访问单链表

return 0;

}

这样,就可以正确建立单链表。因为经过初始化,已经建立了一个空的带头结点的单链表,creat函数将实参l的值传递给形参la,la接受了实参l的值,在creat函数中修改实参l(头指针)所指单元内的内容,即修改实参l所指单元的值,而并没有改变实参l的值。

2 结 语

从以上单链表建立算法的详细分析可见,关键问题还是需要深刻理解C/C++程序设计语言中的参数传递方式、变量有效范围、指针等,并能灵活应用。这样在实际应用编程中就不会出错,也不会在调试软件过程中出现一些莫名其妙的错误。

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006.

[2]耿国华.数据结构C语言描述[M].北京:高等教育出版社,2006.

[3][美] Robert L Kruse,Clovis L Tondo,Bruce P Leung.Data Structures & Program Design in C[M].Second Edition.Prentice-Hall International Inc.,1998.

[4][美]William Ford,William Topp.Data Structures with C++[M].Prentice-Hall International Inc.,1997.

[5]Wikipedia,The freeencyclopedia Linked List[EB/OL]./wiki/Linked-list,2008.

[6]张敬敏,王培崇,路凤佳.道路网络中的移动对象索引方法研究[J].计算机工程与应用,2009,45(12):144-146.

[7]孙玉强,顾玉宛,张聪品,等.基于PRAM模型的二叉树A序列并行算法的研究[J].计算机科学,2009,36(3):256-257,294.

[8]刘小龙,杨维芳.基于最小距离简单多边形的Delaunay三角剖分算法[J].计算机工程与设计,2009,30(5):1 270-1 271,1 275.

[9]王小兵,段振华.框架投影时序逻辑程序设计语言中的指针[J].西安电子科技大学学报:自然科学版,2008,35(6):1 069-1 074.

[10]李广元,唐稚松.时序逻辑语言 XYZ/E中指针的形式化表示与验证[J].软件学报,2000,11(3):285-292.

[11]何煦岚,何晓岚.基于多链表结构的嵌入式系统内存管理[J].计算机应用与软件,2008,25(4):58-59,81.

[12][美]Nell Dale,Chip Weems,Mark Heading.Programming and Problem Solving with C++[M].Third Edition.Jones and Bartlett Publishers,2003.

[13][美]Brian W Kernighan,Dennis M Ritchie.The C Programming Language[M].Second Edition.Prentice-Hall International,Inc.,2008.