2024年4月30日发(作者：)

维普资讯

电脑知识与技术　．．．．．．数据库与信息管理．　

Ｃ中用指针动态建立单链表的几种方法　

廖远来　

（河源职业技术学院信息技术系，广东河源５１７０００）　

摘要：通常用数组可以实现线性表的顺序存储，但是，数组事先要定义固定的长度，并且所分配的存储空间是连续的。这样一来，就不　

能达到真正意义上的动态分配存储空间以及充分利用存储空间的目的；另外，用数组不利于实现线性表中结点的动态增加与删除。而用　

链袁则可以弥补以上不足。本文主要以建立学生信息链表为例，分别介绍无头结点、有头结点单链表的逆序建立和顺序建立过程以及算　

法实现。　

关键词：指针：链表：单链表；动态建立　

中图分类号：ＴＰ３１１　文献标识码：Ａ　文章编号：１００９－３０４４（２００６）２３－００２２－０２　

ＬＩＡＯ　Ｙｕａｎｇ——ｌａｉ　

Ｓｅｖｅｒａｌ　Ｍｅｔｈｏｄｓ　ｏｆ　Ｄｙｎａｍｉｃ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　Ｓｏｌｅ　Ｃｈａｉｎ　Ｌｉｓｔ　ｂｙ　Ｎｅｅｄｌｅ　ｗｉｔｈｉｎ　Ｃ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｌａｎｇｕａｇｅ　

（Ｈｅｙｕａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ，Ｈｅｙｕａｎ　５１７０００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｏｒｄｉｎａｒｉｌｙ，ｏｒｄｅｒ　ｓｔｏｒａｇｅ　ｏｆ　ｌｉｎｅａｒ　ｔａｂｌｅｓ　ｃａｎ　ｂｅ　ｒｅａｌｉｚｅｄ　ｔｈｒｏｕｇｈ　ａｒｒａｙｓ．Ｈｏｗｅｖｅｒ，ｅａｃｈ　ａｒｒａｙ　ｍｕｓｔ　ｐｒｅｖｉｏｕｓｌｙ　ｂｅ　ａｓｓｉｇｎｅｄ　ｇｉｖｅｎ　

ｌｅｎｇｔｈ　ａｎｄ　ｔｈｅ　ｓｔｏｒａｇｅ　ｓｐａｃｅｓ　ｄｉｓｔｒｉｂｕｔｅｄ　ａｒｅ　ｓｕｃｃｅ￣ｉｖｅ．Ａｓ，ｏｆ　ｃｏｕｍｅ，ｃａｎ　ｔ　ｆｕｌｌｙ　ｒｅａｃｈ　ｔｈｅ　ａｉｍｓ　ｏｆ　ｄｙｎａｍｉｃ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｓｔｏｒａｇｅ　ｓｐａｃｅｓ　ａｎｄ　

ｃｏｍｐｌｅｔｅｌｙ　ｕｔｉｌｉｚｅ　ｔｈｅｍ．Ｍｏｒｅｏｖｅｒ，ｉｔ　ｓ　ｎｏｔ　ｉｎ　ｆａｖｏｒ　ｏｆ　ｒｅａｌｉｚｉｎｇ　ｔｈｅ　ｄｙｎａｍｉｃ　ａｄｄｉｎｇ　ａｎｄ　ｄｅｌｅｔｉｏｎ　ｏｆ　ｎｏｄｅ　ｉｎ　ｌｉｎｅａｒ　ｔａｂｌｓ　ｂｙ　ｕｅｓｉｎｇ　ａｒｒａｙｓ．Ｉｎ—　

ｓｔｅａｄ，ｔｈｅ　ｓｈｏｒｔａｇｅｓ　ｃａｎ　ｂｅ　ｃｏｖｅｒｅｄ　ｗｈｅｎ　ｕｓｉｎｇ　ｃｈａｉｎ　ｌｉｓｔｓ．Ｍａｉｎｌｙ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｏｕｓｔｒｕｃｆｉｏｎ　ｏｆ　ｓｔｕｄｅｎｔｓ　

ｄｕｃｅｓ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｄｉｓｏｒｄｅｒ　ａｎｄ　ｏｒｄｅｒ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ｎｏｄｅ　ｓｌｏｅ　ｃｈａｉｎ　ｉｓｔｌ．　

ｉｎｆｏｒｍａｔｉｏｎ　ｃｈａｉｎｓ，ｔｈｅ　ａｒｔｉｄｅ　ｉｎｔｒｏ－　

Ｋｅｙ　ＷＯｒｄＳ：ｎｅｅｄｌｅ；ｃｈａｉｎ　ｌｉｓｔ；ｓｏｌｅ　ｃｈａｉｎ　ｉｌｓｔ；ｄｙｎａｍｉｃ　ｃｏｎｓｔｒｕｃｔｉｏｎ　

１链表概要　

链表概念：链表是线性表的链式存储结构的实现。特点是用　

一

ｍｔ　ｐ；　

Ｐ＝＆ｂ：　

组任意的存储单元存储线性表的数据元素（这组存储单元可以　

是连续的也可以是不连续的）。为了表示每个数据元素ａｉ与其直　

接后继数据元素ａｉ＋ｌ之间的逻辑关系，对数据元素ａｉ来说，除了　

存储其本身的信息，还需存储一个指示其直接后继的信息（直接　

后继的存储位置）。这两部分信息组成一个结点，它包括两个域：　

其中存储数据元素信息的域称为数据域；存储直接后继存储位置　

的域称为指针域。指针域中存储的信息称做指针或链。　

单链表概念：每个结点中都只有一个指针域的链表称为单链　

表。　

￣ｎｔｆ（“％ｄ”，　ｐ）；　

这就有一种逻辑上的指向关系．１００３指向１００３所在的存储　

单元习惯上说Ｐ指向ｂ存储单元。由于通过地址能找到所需的变　

量单元，我们可以说，地址“指向”该变量单元。因此Ｃ语言中，将　

地址形象化地称为“指针”。　

３　Ｃ中单链表的表示　

在Ｃ语言中可用“结构指针”来描述单链表。　

Ｓｔｒｕｅｔ　ｌｎｏｄｅ　

２指针概念的引出　

我们知道内存是按字节编址的，即每一个字节的存储单元都　

有其固定的物理地址。我们所说的“地址”就是这个物理地址。Ｃ程　

序中，我们定义的变量、数组、和函数等，都要在内存中分配一个　

存储空间。每一个存储空间由若干个字节组成，一个存储空间的　

“地址”指的是该空间中第一个字节的地址。这样以来。形式上，我　

｛　

ｅｌｅｍｔｙｐｅ　ｄａｔｅ；／／定义结点类型　

ｓｔｒｕｅｔ　ｌｎｏｄｅ　ｎｅｘｔ：　

，／定义该结点类型的指针用于指向下一个结点　

｝；　

Ｓｔｒｕｅｔ　ｌｎｏｄｅ＊ｈｅａｄ；　

本文有关建立链表的实例都采用以下定义：　

以建立学生信息链表为例，假设一个学生信息包括：学号，　

姓名．量化分￥／　

ｓｔｒｕｅｔ　ｌｎｏｄｅ　

们可以通过定义的变量名或地址访问系统分配给变量的存储空　

间。（直接访问）　

假设编译时系统分配给变量ａ，ｂ的存储单元如图：　

１００３　

１００４　

１００５　

ｌ００６　

■　

｛　

ｉｎｔ　ｘｕｅｈａｏ；　学号￥／　

ｃｈａｒ　ｎａｍｅ［２０］；　姓名　／　

ｌｆｏａｔ　ｓｃｏｒｅ；　量化分￥／　

ｓｔｒｕｅｔ　ｌｎｏｄｅ　ｎｅｘｔ；　

ｉｎｔ　ａ＇ｂ＝６；　

Ｓｃａｎｆ（“％ｄ”，＆ａ）；　

Ｐｒｉｎ　“％ｄ％ｄ”，ａ，ｂ）；　

实际上，上例中的用变量名ａ，ｂ将这两个变量所对应的存储　

空间里的值打印出来，最终编译系统也要将变量名跟物理地址联　

系起来，归结为通过地址取出ａ，ｂ所在存储空间里的值．再打印　

出来。　

｝；　

ｓｔｒｕｅｔ　ｌｎｏｄｅ＊ｈｅａｄ，　ｐ；　定义该结点类型的头指针变量ｈｅａｄ，　

指向新结点的指针变量ｐ＊／　

４动态建立无头结点的单链表　

４．１逆序建立过程　

为了打印出ｂ的值可不可以先将ｂ变量的地址放到另一变　

量中，然后通过另一变量去取出ｂ的值打印出来呢？答案是肯定　

的（问接访问）。　

收稿日期：２００６－０５－１９　

４．１．１无头结点单链表的逆序建立过程图　

（１）准备链接第１个结点的情形　

Ｐ－ｎｅｘｔ＝ｈｅａｄ；　将ｈｅａｄ里面的值放新结点的指针域里面￥／　

作者简介：廖远来（１９７９一），男，江西石城人，广东省河源职业技术学院信息技术系教师，研究方向：计算机软件与理论、程序设计语言。　

２２　电－知识与技术　

．　

维普资讯

维普资讯

电脑知识与技术　

的逼近目标函数。　

．．．．．．网络通讯与安全．．　

ｔｅｍ　Ｓｙｍｐｏｓｉｕｍ，Ｈｉｍｓｈｉｍａ，ＰＰ．５２９－５３２，１９９２．　

参考文献：　

［１　１Ｉ．Ｃ．Ｂｅｚｄｅｋ，Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ　ｗｉｔｈ　Ｆｕｚｚｙ　Ｏｂｊｅｃｔｉｖｅ　

Ｆｕｎｃｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ，Ｐｌｅｎｕｍ　Ｐｒｅｓｓ，Ｎｅｗ　Ｙｏｒｋ，１９８１．　

『５１Ｍ．Ｍｉｚｕｍｏｔｏ　ａｎｄ　Ｍ．１ｗａｋｉｉ，ＳｅＩｒｆ－ｆｅｎｅｒａｔｉｏｎ　ｏｆ　ｆｕｚｚｙ　ｒｕｌｅｓ　ｂｙ　

ｆｕｚｚｙ　ｓｉｎｇｌｅｔｏｎ－ｔｙｐｅ　ｒｅａｓｏｎｉｎｇ　ｍｅｔｈｏｄ，Ｐｒｏｃ．Ｏｆ　ｔｈｅ　９ｔｈ　Ｆｕｚｚｙ　

Ｓｙｓｔｅｍ　Ｓｙｍｐｏｓｉｕｍ，Ｓａｐｐｏｒｏ，ＰＰ．５８５－５８８，１９９３．　

【２１Ｒ．Ｌ．Ｃａｎｎｏｎ，Ｊ．Ｖ．Ｄａｖｅａｎｄ　ａｎｄ　Ｊ．Ｃ．Ｂｅｚｄｅｋ，Ｅ珩ｃｉｅｎｔ　

ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｆｕｚｚｙ　ｃ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｈｍｓ，ＩＥＥＥ　ｔ

Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｖｏ１．８，　

Ｎｏ．２，ＰＰ．２４８－２５５，１９８６．　

【６１Ｍ．Ｍｉｚｕｍｏｔｏ，Ｆｕｚｚｙ　ｃｏｎｔｒｏｌｓ　ｂｙ　ｆｕｚｚｙ　ｓｉｎｇｌｅｔｏｎ　ｔｙｐｅ　ｅａｓｒｏｎｉｎｇ　

ｍｅｔｈｏｄ，Ｐｍｃ．Ｏｆ　ｔｈｅ　５ｔｈ　ＩＦＳＡ　Ｃｏｎｇｒｅｓｓ，Ｓｅｏｕｌ，Ｖｏ１．Ｉ１，ＰＰ．９４５—　

９４８，１９９３．　

【７１Ｙ．Ｓｈｉ，Ｍ．Ｍｉｚｕｍｏｔｏｍ，Ｎ．Ｙｕｂａｚａｋｉ　ａｎｄ　Ｍ．Ｏｔｎｉａ，Ａ　ｌｅａｒｎｉｎｇ　

ｌｇｏｒａｉｔｈｍ　ｆｏｒ　ｔｕｎｉｎｇ　ｆｕｚｚｙ　ｔｕｌｌｅｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｇｒａｄｉｅｎｔ　ｄｅｓｃｅｎｔ　

ｍｅｔｈｏｄ，Ｐｍｃ．Ｏｆ　ｔｈｅ　５ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｆｕｚｚｙ　

【３ＩＲ．Ｎ．Ｄａｖｅ　ａｎｄ　Ｓ．Ｋ．Ｂｈａｓｗａｎ，Ａｄａｐｔｉｖｅ　ｆｕｚｚｙ　ｃ—ｓｈｅＵ　

ｃｌｕｓｔｅｒｉｎｇ，Ｐｒｏｃ．Ｏｆ　ｔｈｅ　１０ｔｈ　Ａｎｎｕａｌ　Ｎｏｒｔｈ　Ａｍｅｒｉｃａｎ　Ｆｕｚｚｙ　

Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｓｏｃｉｅｔｙ　Ｍｅｅｔｉｎｇ（ＮＡＦＩＰ　９１），Ｃｏｌｕｍｂｉａ，ＰＰ．　

１９５一ｌ９９．１９９１．　

Ｓｙｓｔｅｍｓ（ＦＵＺＺ－ＩＥＥＥ　９６），Ｎｅｗ　Ｏｒｌｅａｎｓ，ＵＳＡ，Ｖｏ１．１，ＰＰ．５５－６１，１９９６．　

【８１７＝士同．神经模糊系统及其应用【Ｍ】．北京航空航天大学出版　

社．１９９８．　

【４１Ｍ．Ｍｉｚｕｍｏｔｏ，Ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　ｆｕｚｚｙ　ｃｏｎｔｏｌｒｓ（、ｒＩ），一Ｃａｓｅ　ｂｙ　

ｕｚｚｙ　ｓｉｆｎｇｌｅｔｏｎ－ｔｙｐｅ　ｒｅａｓｏｎｉｎｇ　ｍｅｔｈｏｄ－，Ｐｒｏｃ．Ｏｆ　ｔｈｅ　８ｔｈ　Ｆｕｚｚｙ　Ｓｙｓ—　

【９】赵振宇，徐用懋．模糊理论和神经网络的基础与应用【Ｍ】．清　

华大学出版社，１９９６．　

（上接第２３页）　

５．１．２逆序建立带头结点的单链表的程序实现　

ｓｔｒｕｃｔ　ｌｎｏｄｅ＊ｎｃｒｅａｔｅｌｉｓｔＯ　

｛ｓｔｒｕｃｔ　ｌｎｏｄｅ　ｈｅａｄ，　ｐ；　

ｃｈａｒ　ｎｕｍｓｔｒ［２０】；　

ｈｅａｄ＝（ｓｔｒｕｃｔ　ｌｎｏｄｅ　）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｓｔｕｃｔｒ　ｌｎｏｄｅ））；　

为头结点开辟空间￥，　

ｈｅａｄ一＞ｎｅｘｔ＝ｎｕｌｌ；　

ｄｏ　

５．２．２顺序建立带头结点的单链表的程序实现　

ｓｔｒｕｃｔ　ｌｎｏｄｅ　ｓｃｅａｔｒｅｌｉｓｔ０　

｛ｓｔｒｕｃｔ　ｌｎｏｄｅ　ｈｅａｄ，　，　１；　

ｃｈａｒ　ｎｕｍｓｔｒ［２０］；　

ｈｅａｄ＝（ｓｔｕｃｔｒ　ｌｎｏｄｅ　）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｓｔｒｕｃｔ　ｌｎｏｄｅ））；　为头结点开　

辟空间　，　

ｈｅａｄ－＞ｎｅｘｔ＝ｎｕｌｌ；　，　

｛ｐ＝（ｓｔｒｕｃｔ　ｌｎｏｄｅ　）ｍａｌｌｏｃ（ｓｅｚｅｏｆ（ｓｔｒｕｃｔ　ｌｎｏｄｅ））；　

为新结点开辟空间　，　

ｇｅｔｓ（ｎｕｍｓｔｒ）；ｐ－＞ｘｕｅｈａｏ＝ａｔｏｉ（ｎｕｍｓｎ．；　

ｇｅｔｓ（ｐ一＞ｎａｍｅ）；　

ｇｅｔｓ（ｎｕｍｓｔｒ）；ｐ－＞ｓｃｏｒｅ＝ａｔｏｆ（ｎｕｍｓｔｒ）；　

ｉｆ（ｐ－＞ｘｕｅｈａｏ！＝ｏ１　

／＊ｉｆ语句使最后学号为０的结点不连到链表上　，　

将结点逆序链到头结点后面　，　

｛ｐ－＞ｎｅｘｔ＝ｈｅａｄ－＞ｎｅｘｔ；　

ｈｅａｄ－＞ｎｅｘｔ＝ｐ；　

ｌ＝ｈｅａｄ；／＊Ｌ为增设的用于链接后续结点的指针变量．首先指　

向头结点￥，　

ｄｏ　

｛ｐ＝（ｓｔｒｕｃｔ　ｌｎｏｄｅ　）ｍａｌｌｏｃ（ｅｚｓｅｏｆ（ｓｔｕｃｔｒ　ｌｎｏｄｅ））；　

为新结点开辟空间　，　

ｇｅｔｓ（ｎｕｍｓｔｒ１；ｐ－＞ｘｕｅｈａｏ＝ａｔｏｉ（ｎｕｍｓｔｒ）；　

ｇｅｔｓ（ｐ一＞ｎａｍｅ）；　

ｇｅｔｓ（ｎｕｍｓｔｒ）；ｐ－＞ｓｃｏｒｅ＝ａｔｏｆ（ｎｕｍｓｔｒ）；　

Ｉ　一＞ｘｕｅｈａｏ！＝０）／＊ｉｆ语句使最后学号为０的结点不连到链表　

上￥，　

｝　

｝ｗｈｉｌｅ（ｐ－＞ｘｕｅｈａｏ！＝０）；　当学生学号为０时结束链表的建立　

过程￥，　

将结点逆序链到头结点后面　，　

｛ｐ一＞ｎｅｘｔ＝１一＞ｎｅｘｔ；　

１－＞ｎｅｘｔ＝ｐ；　

１＝ｐ；　

ｅｔｒｕｒｎ０ａｅａｄ）；　

｝　

５．２顺序建立过程　

５．２．１顺序建立带头结点的单链表过程图　

（１）准备链接第一个结点的情形　

ｐ一＞ｎｅｘｔ＝Ｌ一＞ｎｅｘｔ；　

Ｌ－＞ｎｅｘｔ＝ｐ；　

｝　

｝ｗｈｉｌｅ（ｐ－＞ｘｕｅｈａｏ！＝０）；　当学生学号为０时结束链表的建立　

过程　，　

ｒｅｔｕｒｎ（ｈｅａｄ）；　

｝　

Ｌ：ｐ；／＊Ｌ为增设的用于链接后续结点的指针变量　，　

………

①………～　

参考文献：　

【ｌ】谭浩强．地址和指针概念【Ｊ】．Ｃ程序设计（第二版），１９９９．１０　

＿ｌ！　

Ｌ　ｐ　

（２）链接第一个结点后的情形　

（１）：２０１－２０２．　

【２】谭浩强，张基温，唐永炎．指针概述［Ｊ】．Ｃ语言程序设计教程　

（第二版），１９９８．６（１）：１７８—１８４．　

【３】黄明和，周定康，谢旭升，李云清．带头结点的链表［Ｊ］．数据结　

构．１９９８．２（４）：２２．　

【４】严蔚敏，吴伟明．线性表的链式表式和实现【Ｊ】．数据结构，　

１９９９．２（３）：２７－３０．　

【５】谭浩强．用指针处理链表阴．Ｃ程序设计（第二版），１９９９．１１　

Ｌ　ｐ　

（３）链上一个结点后，并且开辟了一个新的结点空间的情形　

１０２　啦细识与技术　

（７）：２７３－２７７．　

【６１ｉ１￣，张基温，唐永炎．动态存储分配——链表阴．Ｃ语言程　

序设计教程（第二版）．１９９８．７（６）；２５５—２６５．