C 语言程序设计中链表的教学方法

李丽萍，教巍巍

(辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001)

一、链表的知识重点

所谓链表，是指由同一类型的若干个结构体类型数据(每一个数据称为一个“结点”)通过指向同一类型的结构体的指针变量，将分散在各个不连续存储区域中的各个结点依次连接起来[1]。结点中的成员必须具备以下特点：其一，必须有数据项，即必须有对用户有用的数据；其二，必须有指针域，即用来存放下一个结点地址的一个指针类型数据项。链表分为单向链表、双向链表和循环链表，本文只介绍单向链表。单向链表要求：必须有一个存放第一结点地址的头指针，通过头指针能找到第一个结点；还要有若干个结点，每一个结点的其中一个成员必须是存放同一类型结构体结点的指针域，这样可以通过指针域中的地址找到下一个结点。通过这种方式，实现多个结点首尾相连。

二、引入链表知识的原因

案例1：在C语言中，有一个名为a的数组，数组元素个数5个，即a[5]。每个数组元素已经赋值。现在想删除第一个数据，如何处理？

常用的方法：从第二个数组元素值开始依次前移一个位置，即用后面数组元素的值覆盖前面的数组元素的值。采用这样的方法，5个数需要执行4次移动操作；那么有100个数组元素，则需要执行99次移动操作，这显然不是一个好的解决问题的方法。

案例2：同样有5个数组元素已经赋值，现在想在第一个数组元素和第二个数组元素之间插入一个数据，如何处理？

常用的方法：从第五个数组元素值开始依次后移一个位置，即将第5个数组元素值移动到第六个位置，依次后移，直到把第二个数组元素值移动到第三个位置为止，然后将要插入的数据放到第二个位置。采用这样的方法，5个数，需要执行4次移动操作；那么有100个数组元素，则需要执行99次移动操作，这显然也不是一个好的解决问题的方法。

为了解决大量数据插入或删除的问题，用前面学过的知识处理太繁琐，因此，引入了链表这个知识。链表在进行插入和删除等一些操作中比数组更加便捷、高效，因此在实际应用中使用非常广泛。

三、链表知识引入的难点

链表综合了C语言中顺序结构、选择结构、循环结构、数组、指针、结构体等等诸多知识，与之前所学知识不同的地方是结构体变量包含多个成员，而想成功建立链表，要求其中的一个成员必须是指向正在定义的结构体类型的指针变量[2]，因此很多学习C语言的学生普遍反映链表很难学。

四、链表知识引入策略

通过对上述难点的分析，并反思日常教学中面对的学生理解知识困难的情况，将回归教育心理学的本源与联系C语言程序设计教学的特点相结合，对教学方法进行革新。

（一）理论支撑

1.当代建构主义学习观。当代建构主义认为，学生的学习是在自身原有经验基础上的再建构。即教学并非知识的传递而是知识的处理和转换，尤其强调学习的主动建构性、社会互动性和情境性。所以，在教学中应该积极将新的学习知识与学生自身状况进行结合。这种结合一方面要关注学生已有的储备知识，这种知识可以是专业理论上的，也可以是社会生活上的；另一方面，这种结合是一定要上升到学生的现实实践中去的，这与当今实用型人才的培养动向也是高度一致的[3]。本文采用大家都熟悉的师生户外郊游事例，讲解静态链表的建立、删除和插入。将链表知识进行生活化描述、情境性讲解，能够帮助学生对知识的理解和掌握。

2.认知派学习理论。认知派的代表人物奥苏贝尔认为，人的学习包含着一种认知结构的迁移。认知结构即学生头脑中形成的知识结构，这种知识结构一部分是知识经验，包括从前的学习和经验；另一部分是指，经验是有组织地存储于头脑中的。所以教学应该借助于先行组织者这一桥梁，通过引导性的材料来促进学生的理解。这种材料既要与学习任务关联，又要与学生头脑中已有的知识结构相关联。只有这样，才能实现知识的迁移，形成新知识。

（二）教学方法的提案

如何让学生很容易地理解、掌握链表部分知识呢？可以通过师生户外郊游的教学方法，让学生透彻理解链表的真正含义。在讲解单向链表的知识时引用案例，将链表结构进行生活化描述：

假设休息日李老师和4 名同学小红、小明、小丽和小倩一起户外郊游。老师不允许大家带手机，除老师外的所有人必须带食物。老师只会记住小红的家庭住址，小红只记住小明的家庭住址，小明只记住小丽的家庭住址，小丽只记住小倩的家庭住址。休息日，李老师先找到小红同学，然后和她一起去找她记住地址的同学，依次类推……最后5 人一起出发。

1.户外郊游要求

（1）教师最先出发，她只记住第一位学生的地址，不带食物；

（2）第一位到第三位学生要记住一名学生的地址，还要带食物；

（3）第四位学生只需带食物，不用记住任何人的地址。

2.链表与户外郊游的对应关系。看下面的程序

程序中定义了一个结构体类型，其中包括两个成员，一个是用来存放数据的变量，另一个是与正在定义的结构体类型相同的指针变量。

在主函数中定义了一个指向结构体类型的指针变量head 和四个结构体类型的变量a,b,c,d。在链表中，每一个结构体变量称为一个结点，指针变量head 中存放第一个结点的地址，称为头指针。

在这个程序中有a,b,c,d四个结点。每一个结点都有两个成员，例如，a.num成员用来存放数据4，a.next成员用来存放b成员的地址。下面给出head头指针和四个结点之间的相互关系的示意图，也就是链表（图1）。

图1 链表

由图1 可以惊奇地发现，指针变量head 和四个结点a,b,c,d 与一个教师和四名学生的对应关系非常相似！指针变量head 中只存放变量a的地址。同样，教师只有小红的家庭地址，没有带食物。

结点a,b,c，每一个变量都有两个成员。一个成员用来存放有用的数据，另外一个成员用来存放下一个结点的地址。同样，小红、小明和小丽每个人都既需要带食物，还要有另外一个同学的地址。

结点d，只需要给数据成员赋值即可，指针变量内容为空。同样，小倩只需要带食物即可，不需要记其他同学的地址。链表的执行方式也与师生郊游出行时的联络方式相似。通过头指针head的内容可以找到结点a，由结点a的指针域a.next的内容可以找到结点b，以此类推。最后结点d的指针域d.next 值为空，链表断开。同样，老师手里有小红的地址可以找到小红，小红手里有小明的地址可以找到小明，以此类推。最后小倩手里没有任何人的地址，说明人已经全部集合完毕。

老师可以找到任意一名学生，同样，从头指针head 出发，可以找到任意一个结点。老师和学生们集合完毕，大手拉小手，可以愉快地去拥抱大自然了。现在我们也完成了单链表的建立。

五、链表的插入操作

假设小晖也想去郊游，他家住在小红和小明之间的位置，那怎么更改行动计划呢？

可以将小晖家的地址给小红，小明家的地址给小晖，问题就解决了。假设想在结点a 和结点b 之间插入一个结点p，如何操作呢？同理，将结点p的地址&p 赋值给a.next，将结点b的地址&b 赋值给p.next。这样就可以将结点p 插入到结点a 和b之间了，如图2 所示。

图2 链表的插入操作

六、链表的删除操作

假设小丽家里有事不能去郊游了，怎么更改计划呢？非常简单，将小倩家的地址给小明，问题就解决了。

假设想删除b 结点，如何操作呢？

同理，将结点c的地址&c 赋值给a.next。这样就可以将结点b 从链表中删除，如图3 所示。

图3 链表的删除操作

七、教学总结

将链表知识进行生活化描述，将深奥的知识赋予了生活化的气息，帮助学生理解和掌握。对于教育教学，不能只局限于书本知识，更要打破学生与书本之间的隔阂。教师是以学科知识的逻辑为出发点，站在理论的基础上思考教学；而学生的学科知识储备量较少，理论的应用也明显不足，很难在理论知识的角度上进行融会贯通。因此，教师的作用就是打破教材理论与学生经验之间的壁垒，更好地促进学生理解。本文中所探讨的，对难点理论进行生活化描述的方法，也只是其中一种展示，相信以后一定会有更多的研究对本领域进行扩展。