C语言常用单链表操作

存储多个数据时,除了使用数组外,还可以使用动态内存分配的方式来处理数据规模不确定的应用。例如在要求输入n个数据时,由于n值的不确定性,导致定义数组比较困难,此时就可以考虑使用动态分配内存的形式。

动态分配n个存储单元,可以有两种思路:

(1)一次分配n个连续的存储单元——动态数组。

(2)一次分配一个存储单元,分配n次——动态链表。

动态数组的使用形式前边指针一章已经学习过。比如:

开辟了一个含n个student类型单元的结构体数组。通过指针p访问该结构体数组,用法参照8.3.2用指向结构体的指针访问结构体数组。

下面重点学习动态链表的使用。

1.单链表的概念

为方便讲述,下面以存储n个整数为例。如果使用第二种思路,一次分配一个整型单元,循环n次也能够分配n个整型单元,但在执行动态内存分配时,每执行一次malloc函数,我们都会得到一个整型存储单元的地址,这样会产生n个地址,那么这n个地址该怎么保存?这个问题必须有一个解决的方法。

一个可行的方案是将整数作为结构体的一个成员来存放,而另一个成员定义成指向结构体的指针,用于保存开辟的第二个结构体单元的地址,第二个结构体的指针用来保存开辟的第三个结构体单元的地址,以此类推。这样的一个结构体称为一个“结点”,其结构如图8-5所示。

图8-5　单链表结点结构

结点可采用如下形式定义:

其中data成员可以用来保存一个整数数据,next指针成员用来保存下一个结点的地址。这里是以存储整数为例,在以后使用中如果要保存其他类型的数据,只要改变或增加结点中的数据成员即可,但其中至少要有一个指针成员。

如果有n个这样的结点,且每一个结点中的指针均保存下一个结点的地址,这样就通过指针将所有的结点连接在一起,由此得到的存储结构就叫作链表。如图8-6所示。

在这种存储形式中,数据域用来存放输入的数据,指针又叫作“链”,是在“链接”下一个结点。由于一个结点中只有一个指针,因此该链表又叫作单链表。使用单链表时,请注意以下几个重要概念。

图8-6　单链表结构

(1)头指针:在单链表存储结构中,由于将当前开辟结点的地址放入了前边一个结点的指针成员中,所以如果要使用第i个结点,就必须先找到其前边的第i－1个结点;同理,如果要找第i－1个结点,就要先找到第i－2个结点才能在其指针成员中找到第i－1个结点的地址。以此类推,若要找第2个结点,就要先找到第1个结点,问题是第1个结点前边已无其他结点,那么第1个结点的地址在哪里呢?为了存放第一个结点的地址,我们专门设一个指针(如图8-6中的h),用它来存放第一个结点的地址,这个指针就是头指针。在单链表存储结构中,不能够再随机访问每一个结点,每次要使用某结点时,都必须从头指针开始顺序向后查找该结点,因此头指针非常重要,是单链表的唯一标识,找到头指针就可以找到整个单链表。

(2)头结点:有时候为了使所有操作统一,方便编程,会将第一个结点“空”出来,里边不存放任何数据元素,这个被“空”出来的结点称为头结点,带有头结点的单链表如图8-7所示。下文中如无特殊声明,使用的均为带有头结点的单链表。

图8-7　带有头结点的单链表

(3)首元结点:真正存放数据元素时是从第2个结点开始按先后顺序存放,第2个结点此时称为“首元结点”,它是真正存放第一个数据元素的地方。

(4)尾结点:尾结点是单链表的最后一个结点,由于在它的后边不再有其他结点,一般会将空指针(NULL)放入该结点的指针成员,作为整个链表结束的标记。

(5)空链表:所谓的空链表指的是链表中不包含任何数据元素结点的链表。对于没有头结点的链表,空链表中自然没有任何结点,此时头指针h＝NULL;但是对于有头结点的单链表,当链表中没有了数据元素结点后,至少还有一个头结点,因此应是h－＞next＝NULL。带有头结点的空链表如图8-8所示。

图8-8　带头结点的空链表

这些概念对后边单链表的使用非常重要,请大家先行理解。在单链表常用操作中,创建单链表、输出单链表中的值、在单链表中查询指定数据、在单链表插入数据元素、删除单链表中的元素结点是一些非常重要的操作,下面重点学习。

2.创建单链表

建立单链表的过程是一个逐次开辟结点并将结点链接起来的过程,一般是先建立一个空链表,然后将每一个新开辟的结点链接到尾结点的后边并使新链入的结点成为新的尾结点。为了指示当前尾结点的位置,此方法中需引入尾结点指针以避免每次每次遍历整个链表寻找尾结点。建立单链表的函数如下:

结构体本身在内存中有地址,结构体中的每一个成员在内存中也有自己的地址,第一个成员的地址即为整个结构体的地址。请注意输入数据时需使用成员的地址,p－＞data仅代表当前结构体的data成员,不要认为p是指针这里就不需要地址。creat函数是一个返回指针的函数,将单链表的头指针head返回给主调函数。

3.输出单链表

输出单链表的过程就是从前到后遍历单链表的过程。可以设一个工作指针,初始时工作指针指向首元结点并输出其数据成员,然后工作指针后移指向下一个结点并重复这一过程直到工作指针为空。输出单链表的函数如下:

【例8-6】建立一个单链表并输出单链表中的值。

(www.xing528.com)

main函数中调用了前边定义的建立单链表和输出单链表函数,h是main函数中定义的单链表的头指针。注意creat函数中建立的是以head为头指针的单链表,main函数无法直接使用head,creat函数中返回了头指针head的值,执行h＝creat(m)语句后,h中获得head的值,此时h也成为单链表的头指针。

3.查询操作

从首元结点开始,可以给每一个结点一个唯一编号,首元结点编号为1,以此类推。一个数据元素在单链表中的“位置”指的就是该结点的编号值。查询就是从首元结点开始依次和给定数据比较的过程,如果某结点的数据成员等于给定值则查询成功,则返回该结点的位置;如果所有结点比较完都没有找到和给定值相等的结点,则返回0。这个过程类似于输出,实质上也是对单链表的遍历。查询函数如下:

【例8-7】输入一个整数,在例8-6建立的单链表中查询该整数是否存在。

此程序是在已建立单链表的基础上实现的,不能单独运行,同学们上机的时候可以将建立、输出、查询合并到一个main函数中。

查询还有另外一种情况,若查询成功,返回该数据所在结点的指针,否则返回空指针。这也是一个遍历过程,只需将查询函数修改为返回指针的函数即可,代码如下:

此查询函数和search1相比更简单,其中少了有关位置的操作,程序留给同学们自己上机验证。

4.插入操作

和数组相比,在单链表中插入一个结点的操作不需要移动数据元素,只需修改相应指针即可。由于新插入结点的地址要保存到其前边一个结点的指针成员中,因此在第i个位置插入结点时,应该先找到第i－1个结点。假设指针p指向第i－1个结点,当前待插入结点的指针为q,则插入结点操作由如下两个步骤完成:

(1)q－＞next＝p－＞next;

(2)p－＞next＝p;

操作过程如图8-9所示。

图8-9　单链表的插入

注意:两个语句的执行顺序不能颠倒,语句①将p原来后继结点的地址放入q－＞next,使得该结点成为q结点的后继结点;语句②将新结点地址q放入p－＞next,使得q结点成为p结点的后继,完成插入。若两个语句顺序颠倒,即先执行p－＞next＝q,此时p－＞next指针被改变,里边原后继结点的地址丢失,会导致整个链表的断裂。

由此可见,插入操作本身只需修改指针即可,关键是要找到正确的插入位置,插入函数源代码如下:

由于是带有头结点的单链表,所有位置的插入过程都是一致的,此时头指针head不会改变,函数中不用再返回头指针。如果单链表中没有头结点会是什么情况呢?一方面1号位置的插入操作和其他位置的插入操作不一致,如果要在1号位置插入结点,则需修改头指针的值,而其他位置修改的是待插入结点的前驱结点的指针域,插入时要根据位置的不同完成不同的操作,操作起来比较麻烦。另一方面,因为头指针有可能会改变,所以在完成插入操作后要返回头指针。而引入头结点后,头指针和头结点不会被改变,所有操作都在头结点之后,因此不用再做判断和区分,所有位置的操作都是统一的,这就是为什么要使用带有头结点的单链表的原因。

插入时也可能仅给出待插入数据而没有给出其相应的位置,其插入思想和前边所讲一样,仍要先找到操作的位置。为寻找插入位置,可以使用两个工作指针,一个指向当前正在比较的结点,一个指向当前结点的前驱。如要求在例8-6所建立的单链表中插入一个数据x,并仍然保持数据的有序,其函数如下:

利用插入的思想,可以完成另一种建立单链表的方法——头插法。所谓头插法是指每次都将新开辟的结点作为1号结点插入在头结点的后面。此方法中插入位置固定,可以省去查找插入位置的过程,但由于最后插入的结点在单链表的最前面,所创建的单链表中的数据顺和输入数据的顺序正好相反。函数如下:

请大家替换例8-6中的函数调用试一下。

5.删除操作

在单链表中删除一个结点的过程就是使得当前结点的前驱结点直接指向当前结点的后继结点,这样就会把当前结点从链表中“摘掉”,然后对当前结点执行free操作即可。假设当前待删除结点指针为p,其前驱结点指针为pre,删除语句如下:

其删除过程如图8-10所示。

从图8-10可以看成,删除当前结点p的操作主要仍是查找其前驱结点,这里只给出按位置删除的方法,如果要删除某一个数据而没有指定位置,可以通过查找函数先确定要删除数据在单链表中的位置。

图8-10　单链表的删除

按位置插入和按位置删除的两个函数中,没有给出位置合法性的判断,请大家上机时考虑插入和删除中的合法的位置范围并调试程序。