摘要：链式存储结构是数据在计算机中的一种存储方式，是数据结构课程中重要的教学内容。然而，掌握链式存储结构并灵活使用是不容易的。在分析平时教学中学生学习链式存储结构时常出现的问题的基础上，分别在概念、特点、定义和操作四个方面探讨了讲授链式存储结构的方法和技巧。
关键词：链式存储结构;数据结构;存储结构;教学方法
1 链式存储结构的概念
掌握链式存储结构的概念是学习各种不同数据结构的链式表示和实现的前提。因此，教学中首先要让学生明白什么是链式存储结构。相对于可使用数组实现的顺序存储结构来说，学生在学习数据结构之前不仅对链式存储结构的概念是陌生的，而且大多对实现链式结构的基础知识如结构体、指针等也不熟练。因此，在教学中深入浅出地将链式存储结构概念讲解清楚很重要。讲授时可按数据的结构、存储结构再到链式存储结构的顺序从外到内逐层深入地方式讲解，以帮助学生理解概念。
1.1 结构结构指数据元素之间的一种或多种关系，关系可能是线性的，也可能是非线性的。常见的基本结构分为四类，分别是集合、线性表、树和图。当然，通常所说的关系是指数据元素之间的逻辑关系即数据的逻辑结构。简单地理解，结构就是关系。
1.2 存储结构为了在计算机中实现操作，除了分析数据元素之间的关系即得到数据的逻辑结构外，还要考虑它们在计算机中如何存储。数据元素和关系在计算机中的表示称为数据的存储结构，也称为物理结构。简单地理解，存储结构就是数据在计算机中的存储方式。
1.3 链式存储结构链式存储结构是通过记录元素的位置来表示元素与元素之间逻辑关系的一种存储结构。比如，在线性结构中，若两个逻辑上相邻的数据元素在实际存储时不相邻，则可以通过将后一个元素所在的位置记录到前一个元素来实现两个数据元素之间的前后关系。若是非线性结构，同样可以通过记录位置的方式实现两个元素之间的非线性关系，比如双亲和孩子的关系、邻接点关系等。其中，位置是存储元素的地址即指针。在静态链表中，位置是数组的下标。
2 链式存储结构的特点
数据结构和算法是计算机科学和工程的基础[1] ，任何一个算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据的存储结构[2] 。因此，只有掌握了数据存储结构的特点，才能根据实际情况使用合适地存储结构来实现算法。作为一种非顺序存储结构，链式结构有着其自身的特点，掌握这些特点是灵活使用链式存储结构并充分发挥其优点的基础。授课时，可以通过比喻和类比等方式帮助学生掌握其优缺点。
2.1 什么是链链式存储结构的特点体现在“链”字上。所谓“链”，可以想象为用一根绳将原本有一定关系的数据元素串起来，通过“链” 可以访问与指定数据元素有关系的其它元素。举个线性结构的例子来说明如何链接，比如，同学A的后面是同学B，即A是 B前驱或者说B是A的后继。排座位时，为了能体现出两者的前后关系，若A坐在某个位置，则可以将B直接安排在A的后面，这样A直接往后就可以找到后面的同学B了。当然，也可以选择另一种方式，即B不直接坐在A的后面，而是坐在任何一个空位上，只要将他所坐的位置告诉A，这样A同样可以找到 B了。这个例子里，两个数据元素之间的先后关系不是在存储时直接体现出来而是通过记录位置完成的。可以想象，当多个数据元素都按这种方式存储时就类似用一个链串起了所有的元素，用这种方式存储的线性表就称为链表。当然，“链”不仅可以表示线性关系，还可以将“链”进行扩展，根据需要实现如树、图等其它更复杂的关系的表示。
2.2 优点链式存储结构借助地址来表示数据元素之间的关系，数据元素在存储时是按非顺序的方式存储的，因此弥补了顺序存储结构的不足。为使学生更清楚地了解链式存储结构的优点，授课时可采用与顺序存储结构相比较的方式从以下两个方面来讲解。第一，链式存储结构存储元素时所需存储单元是动态申请的，不必担心操作过程中随数据量变化而引起的存储空间不足或浪费问题。在顺序存储结构中，存储空间由一组连续的存储单元组成，因此，存储容量受限。然而，链式存储结构采用需要存储一个元素就动态申请一个存储单元的方式，存储单元可以是连续的，也可以是非连续的。第二，在插入和删除操作时不需要移动数据元素，并且插入、删除操作灵活。在链式存储结构中，由于数据元素之间的关系是借助地址来表示的，因此在进行插入、删除操作时，只需要改变地址就可以实现数据元素之间关系的变化。相对于顺序存储结构来说，不需要将待插入的数据元素位置空出，也不需要将删除的数据元素位置补上。
3 链式存储结构的定义
在数据结构中，常见的链式存储结构有单链表、循环链表、双向链表、十字链表、二叉链表和邻接表等，不同的链式存储结构可用来满足不同的数据结构的表示和实现。然而，无论哪一种数据结构，若要使用链式存储结构，首先要完成它在计算机中的表示，即该链式存储结构所需的结构体类型定义。通常，链式存储结构的结构体类型包括两部分：一是为存储数据元素而封装成结点的结点类型，二是描述该链式结构的结构类型。比如，在单链表中，为了实现将后一个数据元素的地址记录到前一个数据元素中，需要将数据元素封装成一个结点，这个结点存储数据元素的值和其后继元素所在的地址。因此，自定义一个结构体类型即结点类型struct LNode，它包含两个域，分别为数据域data和指向下一个结点的指针next。设数据元素类型为ElemType，则结点类型定义用C语言[3] 描述如下： struct LNode{ ElemType data; struct LNode *next; }; 这里的指针next在定义时采用了递归定义，由于指针指向的是结点，因此定义为结点类型struct LNode。另外，当所有结点连接成一个链表后，这个链表就构成了单链表，单链表也需要通过定义来描述其作为一个线性表所具有的特征，比如第一个数据元素的地址、数据元素个数等。显然，若有一个指针L 指向链表的第一个结点(头结点或首元结点)，则通过此指针就可以找到整个链表，类似于数组的首地址，这个指向链表的指针 L 称为头指针，头指针指向的是结点，因此定义为 struct LNode类型。它的类型定义如下： struct LNode *L; 显然，对于一个单链表来说，只要有了头指针就可以找到链表并访问所有元素。因此对整个链表而言，定义一个头指针即可，其它属性如数据元素个数可以通过计数操作来实现。学生在初始学习时很容易在定义指针类型上犯错，不清楚指针究竟该定义成什么类型。其实，指针定义成什么类型完全取决于指针指向的对象类型。比如，单链表中指针next的类型是结点类型 struct LNode 而不是数据元素类型 ElemType，因为指针指向的是将数据元素封装成包含数据域和指针域的结点而不是一个数据元素。
4 链式存储结构的操作
当使用链式存储结构时，常常需要实现创建、插入、删除、查找等操作。但是，无论哪种链式存储结构，其多数操作的实现主要还是单链表插入、删除操作的延伸和扩展。因此只要熟练掌握链表的插入和删除，就能实现其它更为复杂的操作。举例说明，设q指向链表中的结点A，p指向待插入的结点B。若要将 B 插入到 A 之后，执行 p→next=q→next 和 q→next=p 两条语句即可。为了保证能正确地完成元素的插入，实现插入语句时需满足“先连上，后断开”的原则，即先使用p→next=q→next 将待插入的结点 B 连到链表中(结点 A 的后面)，然后再执行 q→next=p，将A的后继链从链表中断开并连到B上。这两条语句不能颠倒，若将两条语句的顺序颠倒，即先将A的指针指向 B，那么A后继链就断掉了，B就无法再连接到链表中。因此，插入操作中需要按“先连上，再断开”的顺序进行，只要记住了这个原则就可避免实现插入时出错。当实现链式存储结构的删除操作时，执行语句也很简单。设p指向链表中的结点A，若要删除A后面的结点B，执行p→ next=p→next→next即可。但是，实际操作中，往往还需要将删除结点的元素值带回，因此多引入一个指针q，让q先指向待删除的结点B，即执行q=p→next，然后再执行p→next=q→next，将 B从链表中删除。这样，即使B已经从链表中删除，但是结点B 还是由q指向，因为B的地址存在q中，此时只要在释放q之前把q→data赋值给某个变量就可以通过该变量继续使用删除的数据元素。因此，在删除操作中，由被删除的数据元素值是否还需要使用来决定删除语句。如果不需要，执行p→next=p→ next→next即可。但是，若还需要使用被删除的元素值，则多引入一个辅助的指针 q，同时执行 q=p→next 和 p→next=q→next 两条语句。相对单链表来说，其它的链式存储结构可能在指针域或数据域扩充后有更为复杂的操作。然而，只要将最基本的单链表的插入和删除操作掌握好，就可以在实现其它链式存储结构操作时轻松应对。
5 结束语
在处理数据时，不仅要学会分析数据的逻辑结构，还应能使用合适的存储结构来高效地实现算法。在数据结构中，尽管有多种不同的链式存储结构如单链表、双链表、循环链表、二叉链表、邻接表和十字链表等，但这些存储结构毕竟是有限的，不一定能满足实际应用的需求。因此，学习链式存储结构是学习借助地址表示数据元素之间关系的思维方法，即学习“链式”思维。当用“链式”思维解决存储问题时，即使没有已有的链式存储结构可供使用，也能根据需要去自行设计。
参考文献：
[1] 萨特吉,萨尼. [M]. 数据结构、算法与应用 C++语言描述[M] 王立柱,刘志红,译.2版. 北京：机械工业出版社, 2015.
[2] 严蔚敏,吴伟民. 数据结构(C语言版)[M]. 北京：清华大学出版社, 2007.
[3] 谭浩强. C 语言程序设计[M]. 2 版. 北京：清华大学出版社, 1999.
《数据结构中链式存储结构的教学探讨》来源：《电脑知识与技术》，作者：周张兰。
