从链表的实现论C/C++与数据结构教学

胡传福

(东莞理工学院 计算机学院，广东东莞 523808)

1 数据结构课程及教学

《数据结构》课程是计算机科学与技术的一门综合性专业基础课，是学习操作系统、编译原理、数据库原理等专业核心课程的基础;同时也是设计和实现各种系统软件和大型应用程序的重要基础。由于其内容多，难度大，针对现代大学生的实际情况，最初的面授课程非常重要，除了从总体上把握本课程主要内容和作用外，更要回顾、补充有关的C/C++相关程序设计语言的基本知识。平时的面授辅导，做到概念讲解简洁，甚至跳过，可以多作相同点和不同点的比较，针对算法思想和算法描述，多用习题讲解，并用多媒体课件进行实例演示，同时强调上机操作。

2 C/C++与数据结构的关系

数据结构的主要内容之一是典型数据结构及其操作的算法实现，这与程序设计语言密切相关。

C 语言是在国内外广泛使用的一种计算机语言。C 语言功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好。特别适合于编写系统软件［1］。因此，许多高校都开设了C 语言课程。C++更是全面兼容了C，同时提供了比C 更严格、更安全的语法［2］。从这个意义上讲，C++首先是一个更好的C。

虽然数据结构的大部分内容(尤其是算法及算法分析)都是描述性的、与语言无关的，但是，算法要真正实现还是需要特定程序设计语言的支持。由于C 语言的简洁易懂、同时又是计算机相关专业的最基础课程(高中升大学即可学习，无需先修课)，故国内外很多数据结构相关的书籍教材大多采用类C 语言作为数据结构的描述语言，并把C 语言作为数据结构算法的实现语言。

C++除了修正了许多C 语言的语法方面的缺陷之外，还提供了直接结构(类和模版)来实现抽象数据类型的通用数据结构。面向对象的方法更是将数据和对数据的操作放在一起，作为一个相互依存、不可分离的整体—对象。即对同类型对象抽象出其共性，形成类，只通过一个简单的外部接口与外界发生关系［2］。

3 链表的不同实现

线性表一般是《数据结构》课程的开篇章节，是一种线性结构，同时也是一种最简单的数据结构。线性表可以用顺序存储结构或链式存储结构存储，分别叫顺序表和链表。链表存储数据元素的方法是，把存储有数据元素的结点用指针域构造成链。指针是指向物理存储单元地址的变量，以单链表为例，一个数据元素域和一个指针域(指向直接后继结点的指针)组成的结构体称为单链表的一个结点。其中，数据域用来存放数据元素，指针域用来构造数据元素之间的关联关系。链式存储结构的特点是，数据元素间的逻辑关系表现在结点的链接关系上［2］。

根据存储方式的不同，单链表主要有以下几种不同的实现方式:

1)单链表:用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。

存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

链表中结点的逻辑顺序和物理顺序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)信息，这个信息称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如图1 所示。

图1 链表中的结点结构图

链表正是通过每个结点的指针域将线性表的n 个结点按其逻辑次序链接在一起的。

每一个结点只包含一个指针域的链表，称为单链表。

为了操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head 指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。

data :数据域，存放结点的值。next :指针域，存放结点的直接后继的地址。

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。

例1:线性表L=(bat，cat，eat，fat，hat)

其带头结点的单链表的逻辑状态和物理存储方式如图2 和图3所示。

图2 线性表L 的逻辑状态

图3 线性表L 的物理存储方式

对于链表的教学，一般的教材比较注重逻辑状态的教学，虽然说逻辑状态才是数据结构的主要内容，但是，仅仅描述链表的逻辑状态对于那些C/C++功底不强尤其是指针内容把握不清的初学者来说，理解起来就存在很大的障碍。而物理存储方式能直观地展现数据在内存中存储的方式，以图示的方式准确、明了地说明各数据元素之间的关系以及从一个结点访问下一个结点的方式，而不是以一个象图2 的箭头那样就能对下一结点进行访问了。实际上，在相关指针内容的教学上，笔者更注重强调一点，其实箭头并不存在!

2)静态链表:在链式存储结构中，实现数据元素之间的关系依靠指针。也可以用数组来构造链表，方法是:在数组中增加一个(或两个)指针域，这些指针域用来存放下一个(或上一个)数据元素在数组中的下标，从而构成用数组构造的单链表。由于相对于申请结点内存空间的动态性而言，数组内存空间的申请方式是静态的，所以这种存储结构称作静态链表。由于静态链表中增加的指针仿真了链式存储结构中的指针，所以静态链表中的指针也称作仿真指针［3］。

静态链表在内存中的存储方式与图2 有点类似，不同的地方在于它的各结点是以数组方式顺序存储的，虽然当前被访问的节点和它的下一个节点在存储上也不要求是地址连续的，但是，所有的节点的确一定是存储在一个连续地址空间的内存块中。而单链表的各节点并没有这种要求。在教学中，一般可以作为单链表的实现形式的一种对比与补充。

对于此类数组有关的数据结构的教学中，理解并把握一些数组的基本特性对于初学者来说是非常重要的，笔者建议在教学中应该着重强调!下面是C/C++基本数组的一些重要特性:

①对程序员来说，数组是指向一块内存的指针变量，其实际大小必须由程序员确定。

②内存块可以通过malloc 函数或new［］来分配，对应的用free 函数或delete 释放。

③内存块的大小不能改变!如果想要一块更大的，必需重新分配一块。但可以通过用原数组来初始化新数组以达到宏观上数组长大的表象。

3)STL 中的向量和表:在C++语言的库中包含有公共数据结构的实现。就是标准模版库(Standard Template Library，简称STL)。使用STL 中的vector 可以很轻松的实现一个可增长的表的数组实现，list提供了表的双向链表的实现。Vector 和list 都是用其所包含的项的类型来例示的类模版［4］。

Vector 是基本类类型，这意味着不同于C++中的基本数组，vector 可以复制并且其占用的内存可以自动回收(通过其析构函数)。由于Vector 类自身实现了内存管理，对初学者来说，并不能从其学到相关数据结构对内存的要求等方面的知识，建议在教学中对中高级学员进行了解性的介绍，对初学数据结构的学生不做介绍，以免陷入误区。

4 结语

《数据结构》课程是计算机科学教育的一个重要组成部分，是计算机相关专业重要的理论基础课程，课程中涉及的内容很多。而程序设计语言是数据结构的实现工具，也是对客观世界的具体描述，如何在课程教学中既能传授基本知识，又能把当代计算机科学与技术学科和计算机科学技术的新发展、新技术初步传授给学生，而且使学生初步了解一些解决实际应用问题的方法和手段等方面，需要不断地探索和实践。

［1］谭浩强. C 程序设计_新世纪计算机基础教育丛书［M］.3 版.北京:清华大学出版社，2005.

［2］严蔚敏，吴伟民. 数据结构:C 语言版［M］.北京:清华大学出版社，2002.

［3］朱战立. 数据结构—使用C 语言［M］.4 版.北京:电子工业出版社，2011.

［4］(美)Mark Allen Weiss . 数据结构与算法分析C++描述［M］.3 版.张怀勇，译.北京:人民邮电出版社，2007.