一、单向链表的概念
单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。链表是使用指针进行构造的列表，并且是由一个个结点组装起来的，因此又称为结点列表。其中每个结点都有指针成员变量指向列表中的下一个结点，head指针指向第一个结点称为表头，而终止于最后一个指向nuLL的指针。
结点的数据结构
各个结点连接在一起构成一个单向链表（示意图）
二、单向链表的优缺点
和普通的线性结构（如数组）相比，链表结构有以下特点：
（1）单个结点创建非常灵活，普通的线性内存通常在创建的时候就需要设定数据的大小
（2）结点的删除、插入非常方便，不需要像线性结构那样移动剩下的数据
（3）结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表
三、单向链表的基本操作
1、建立一个新的链表
2、增加一个结点（增加到末尾）
3、删除一个结点
4、查找结点
5、统计结点个数
6、打印整个链表
7、删除整个链表
8、链表逆转
链表逆转就是把链表的方向反过来，头指针变成尾指针，尾指针变成头指针，实现草图如下
a、逆转并生成新的链表（非递归方式）
b、逆转并生成新的链表（递归方式）
c、原地逆转，不生成新链表（非递归方式）
d、原地逆转，不生成新链表（递归方式）
9、链表排序
a、选择排序
选择排序的基本思想就是反复从还未排好序的那些节点中，选出键值最小的节点， 依次重新组合成一个链表。可以通过以下三个步骤实现
（1）先在原链表中找最小的，找到一个后就把它放到另一个空的链表中
（2）空链表中存放第一个进来的节点，并且让它在原链表中分离出来
（3）继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针
b、插入排序
直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值排好序的，对于节点n在这个序列中找插入位置，使得n插入后新序列仍然有序。按照这种思想，依次对链表从头到尾执行一遍，就可以使无序链表变为有序链表。可以通过以下两个步骤实现
（1）先在原链表中以第一个节点为一个有序链表，其余节点为待定节点
（2）从原链表中依次取结点，插入到有序链表的相应位置，使得有序链表仍然有序，直至原链表的结点全部取完，排序结束。
c、冒泡排序
冒泡排序的基本思想就是对当前还未排好序的范围内的全部节点，自上而下对相邻的两个节点依次进行比较和调整，让键值较大的节点往下沉，键值较小的往上冒。即：每当两相邻的节点比较后发现它们的排序与排序要求相反时，就将它们互换。
四、单向链表运用示例
将链表的基本操作统一放在一个文件single_linkedlist.c里面，然后在single_linkedlist.h文件里面声明，这样调用起来比较方便。下面贴出各个文件的代码，方面下次快速使用。
single_linkedlist.c文件代码
single_linkedlist.h文件代码
main.c文件代码
Makefile文件代码
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/148490.html