李丽萍，教巍巍

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

一、链表的知识重点

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

二、引入链表知识的原因

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

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

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