基于数据结构的链表创建方法探究

2009-05-12李崇

现代电子技术 2009年2期

李　崇

摘要：链表是线性表的一种表现形式，是数据结构中的一个重要组成部分，而链表的创建方法直接影响人们对链表的理解，尤其是初学者。通过对“数据结构”多年教学实践经验的积累，对链表的创建方法进行了研究，并经过归纳和总结，提出了相对容易理解的创建思路；形成了简明、易懂的创建方法。

关键词：数据结构；线性表；链表；顺序创建法；逆序创建法；有序创建法

中图分类号：TP311文献标识码：B

文章编号：1004 373X(2009)02 117 03

Exploration of Link Table Creation Based on Data Structure

LI Chong

(Chongqing Vocational Institute of Engineering,Chongqing,400037,China)

Abstract：Link table is a form of linear table,which is an important part in data structure.Creation methods of link table helps apprehension of the link table directly,especially fornew learners.Based on many years teaching practice on "data structure",the creation methods of link table is explored.Creation methods relatively easy to understand are promoted after conclusion of the methods.

Keywords：data structure;linear list;link table;ascending creation;descending creation;in－order creation

0 引言

线性表是数据结构中的重要组成部分。也是程序设计中应用最广泛的一种数据结构，它的主要特点是在线性序列中的每一个结点只有1个前驱，也只有1个后继。线性表的存储方式有顺序存储方式和链式存储方式。用顺序存储方式实现线性表的存储，使得逻辑上连续的元素在物理存储上也是连续的，同时对线性表中的数据可以实现随机存取，而链式存储主要是对线性表中的相邻元素以相邻或不相邻的存储单元来保存。所以在链式存储结构中，每个结点除了保存元素信息以外，都至少还需1个指针来保存后继结点的地址。也就是说，1个结点由1个数据域和1个指针域组成。链式存储结构表示线性表中的数据元素时，要先通过1个算法来创建1个链表，称为线性链表。1个结点中只含有1个指针域的线性链表称为单链表或单向链表。而含有2个指针域的链表称为双向链表或双链表，双链表的每个结点中1个指针指向前驱结点，另一个指针指向后继结点。

链表是数据结构中的一个难点，也是数据结构中的一个重要组成部分。它对数据结构中其他知识点的理解具有重要的意义，而链表的创建是链表算法中的重点，很多关于数据结构的书籍都阐述了关于链表的创建方法，但都没有一个统一、全面、易懂的算法。通过多年对链表的研究发现，在链表的创建过程中，总是存在一定的规律。即每个链表都由若干个离散的结点组成，这些结点在创建链表时总是逐个生成的，从而把这些生成的结点逐个地链接起来，形成链表。

因此，在算法中只需要考虑这些结点的链接方式与链接顺序即可。在此从这些结点的链接顺序进行分析与归纳，以单向链表为例对链表的创建方法总结为以下3种，即顺序创建法、逆序创建法、有序创建法。

当然，在创建链表之前，也要对链表的特点进行全面的掌握。因为所创建的链表要符合这些特点，也便于对链表创建算法的实现。

现以单向链表为例，对链表的特点总结为如下5点：

（1）记住首结点；

（2）尾结点指向空；

（3）在某个结点之前插入1个新结点，必须找到该结点的前驱结点；

（4）在某个结点之后插入1个新结点，必须找到该结点；

(5) 在单向链表中访问任一结点，都必须从头开始，直走到待访问结点。

1 由前往后的顺序创建法

在顺序创建法中，根据单向链表的这些特点，从单向链表的首结点开始，由前往后一个结点一个结点的生成与链接，最终形成整个链表。其主要步骤如下：

（1）创建第一个结点A1，并用1个指针（在此中用指针P）指向这个新结点，第一个被创建的结点为首结点，并用1个专门的指针（在此中用h）记住这个结点。这时，链表中只有一个结点。因此，这个结点也是已经生成链表的尾结点。也用1个专门的指针(这里用q)记住这个链表的尾结点。如图1所示。

图1 创建结点A1

即:

p=(ND)malloc(sizeof(ND));

p-＞key=A1;

h=p;

q=p;

（2）生成第二个结点A2，并用前面已经形成链表的尾结点的指针指向这个新结点(即将新结点链接在已生成链表的尾部)。这时，这个新结点变成了已经生成链表的新的尾结点。所以，链表的尾指针q也要指向这个新的尾结点。如图2所示。

P=(ND)malloc(sizeof(ND));

p-＞key=A2;

q-＞next=p;

q=p;

（3）重复第二步的工作，直到所有结点都生成。

图2 生成节点A2

（4）将尾结点的指针指向空。

这种创建方法即为从链表的首结点开始，一个结点一个结点的往后连接，直到链表的尾结点便结束。下面以ＴＣ为例：

typedef struct node

{

int key;

struct node *next;

}ND;

ND * create(int n)

{

ND *p, *q ,*h;

int i;

for(i=1;i＜=n;i++)

{p=(ND *)malloc (sizeof(ND));

scanf(“%d”,&(p-＞key));

if(i= =1)h=p;/*记住首结点*/

else

q-＞next=p;

q=p;/*记住刚插入的结点*/

}

p-＞next=NULL;/*尾结点指针针向空*/

return (h);

}

在从前往后的顺序创建方式中，首结点一但形成，就不会发生变化，而尾结点在不断变化。因为每生成一个新结点，它都将链接在已经存在的链表的尾部，变成新的尾结点。如果元素的输入顺序为（A1,A2,A3,…,A璶）,则通过这种方式所建立的链表如图3所示：

图3 顺序创建方式建立的链表

2 由后往前的逆序创建法

在这种链表的创建方式中，首先也要掌握单向链表的特点，然后，根据单向链表的特点，从尾结点开始，逐个结点地向首结点方向链接，即每次生成的新结点，都将链接在已经存在的链表的首部，变成新的首结点。而尾结点是第一个创建的结点。因此，首先就要考虑第一个结点的指针要指向空（即尾结点的指针指向空）。整个链表的创建步骤如下：

（1）创建第1个结点A1。第1个被创建的结点为整个链表的尾结点。根据单向链表的特点，它的指针应指向空。同时，链表中只有1个结点，因此这个结点也是已经生成链表的首结点。并用一个专门的指针指（在此用h）向这个临时的首结点。如图4所示。

图4 创建第一个结点A1

（2）创建第2个结点A2，并用这个新创建的结点指向已经生成链表的临时首结点。这个新创建的结点A2就成为了已经生成链表的新的临时首结点。所以首结点指针h要指向这个新临时首结点。如图4所示。

图5 创建第二个节点A2

（3）重复第二步的工作，直到所有的结点都生成。

以下通过代码来实现从后往前的逆序创建方法：

typedef struct node

{

int key;

struct node *next;

}ND;

ND * create(int n)

{ND *p,*h=NULL;

int i;

for(i=1;i＜=n;i++)

{p=(ND *)malloc (sizeof(ND));

Scanf("%d",&(p-＞key))

p-＞next=h;/*将新结点连接在已经创建的

链表之前*/

h=p;/*指针h指向新创建的结点*/

}

return (h);

}

假设程序中的输入顺序为(A1,A2,…,A璶) ，则其所创建的链表如图6所示：

图6 逆序创建的链表

3 有序创建法

有序创建法即创建有序链表，也就是在创建链表时，就让链表结点的关键字按指定顺序进行排序，使得创建出来的链表是经过排序的有序链表。由于在创建链表之前，不知道输入结点关键字的顺序。因此，每生成一个结点，就要将它插入到已经生成的链表中。为了保证有序，所以在插入新结点时，要在已经存在的链表中查找它的合适位置，然后将该结点插入到所找到的位置上。

当然，在插入第一个结点之前，整个链表为空。而在插入第一个结点后，链表中就存在一个结点了。以后的每个结点都依次插入到这个链表中的合适位置。从而生成有序链表。现按从大到小的顺序创建有序链表，其程序代码如下：

typedef struct node

{

int key;

struct node *next;

}ND;

ND * insert(ND h,int k)

{ND *p,*q,*r;

P=(ND *)malloc(sizeof(ND));

p-＞key=k;

q=h;

while(q!==NULL&&q-;＞key＜k)