单向链表的基本操作（单向链表的应用）



逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

  由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。

  图1 链式存储存放数据

  如图1所示，当每一个数据元素都和它下一个数据元素用指针链接在一起时，就形成了一个链，这个链子的头就位于第一个数据元素，这样的存储方式就是链式存储。

  线性表的链式存储结构生成的表，称作“”。

  链表中数据元素的构成每个元素本身由两部分组成：

  本身的信息，称为“数据域”；指向直接后继的指针，称为“指针域”。

  图2 结点的构成

  这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。

  图3 含有n个结点的链表

  图 3 中，由于每个结点中只包含一个指针域，生成的链表又被称为线性链表或单链表。

  链表中存放的不是基本数据类型，需要用结构体实现自定义：

  头结点、头指针和首元结点头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

  若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

  首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

  头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

  头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

  图 4 头结点、头指针和首元结点

  单链表中可以没有头结点，但是不能没有头指针！

  链表的创建和遍历万事开头难，初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时，要保证有一个指针永远指向的是链表的表头，这样做不至于丢失链表。

  例如创建一个链表（1，2，3，4）:

  链表中查找某结点一般情况下，链表只能通过头结点或者头指针进行访问，所以实现查找某结点最常用的方法就是对链表中的结点进行逐个遍历。

  实现代码：

  链表中更改某结点的数据域链表中修改结点的数据域，通过遍历的方法找到该结点，然后直接更改数据域的值。

  实现代码：

  向链表中插入结点

  链表中插入头结点，根据插入位置的不同，分为3种：

  插入到链表的首部，也就是头结点和首元结点中间；插入到链表中间的某个位置；插入到链表最末端；

  图 5 链表中插入结点5

  虽然插入位置有区别，都使用相同的插入手法。分为两步，如图 5 所示：

  提示：在做插入操作时，首先要找到插入位置的上一个结点，图4中，也就是找到结点 1，相应的结点 2 可通过结点 1 的 next 指针表示，这样，先进行步骤 1，后进行步骤 2，实现过程中不需要添加其他辅助指针。

  实现代码：

  注意：首先要保证插入位置的可行性，例如图 5 中单向，原本只有 5 个结点，插入位置可选择的范围为：1-6，如果超过6，本身不具备任何意义单向循环链表，程序提示插入位置无效。从链表中删除节点当需要从链表中删除某个结点时，需要进行两步操作：

  使用malloc函数申请的空间，一定要注意手动free掉。否则在程序运行的整个过程中，申请的内存空间不会自己释放（只有当整个程序运行完了以后，这块内存才会被回收），造成内存泄漏，别把它当成是小问题。

  实现代码：

  完整代码

  运行结果：

  总结线性表的链式存储相比于顺序存储，有两大优势：链式存储的数据元素在物理结构没有限制，当内存空间中没有足够大的连续的内存空间供顺序表使用时，可能使用链表能解决问题。（链表每次申请的都是单个数据元素的存储空间，可以利用上一些内存碎片）链表中结点之间采用指针进行链接，当对链表中的数据元素实行插入或者删除操作时，只需要改变指针的指向，无需像顺序表那样移动插入或删除位置的后续元素，简单快捷。

  链表和顺序表相比，不足之处在于，当做遍历操作时，由于链表中结点的物理位置不相邻，使得计算机查找起来相比较顺序表，速度要慢。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/kjbd-yiny/50596.html