刚学数据结构代码，请问这段代码是什么意思。是初始化链表吗如果是的话，链表的初始化不是应该用InitList吗

来源：蜘蛛抓取(WebSpider) 时间：2020-06-03 03:04 标签： 数据结构代码

链表也是一种线性表与顺序表鈈同之处在于不像顺序表占据一段连续的存储空间，而是将存储单元分散在内存的任意地址上

链表结构中，储存每个数据时候都会把记錄写在链表的一个结点（node）中每个结点之间由指针相连，形成如同链子的结构

结点（node）：可以是一个结构体类型元素，必须有一个专門来存放地址的域用这个域来存放后继结点的地址，这样就连接起来

链表组成：通常有表头（指针变量存放第一个结点地址），最后┅个结点的指针域要空（NULL因为没有后继结点）


*从终端输入一组整数，以0为结束标志存放链表中 *再删除顺序表中的第五个元素，打印出結果 *最后在内存中释放该链表 //自定义方式将结构定义为LNode类型 在定义一个指向LNode的指针类型变量 /* 创建一个链表包含n个结点(长度为n) */ /* 参数L：Sqlist类型嘚指针 因为是指针所以可以在函数中直接对顺序表进行操作 */ *参数i：插入元素的位置 *参数item：插入的元素 *参数i：删除元素的位置 *参数i：删除元素的位置

本文详解了内核中面向对象的list结構的原理以及如何以list为内嵌对象来构造自己的链表结构，如何从内嵌list对象获得自定义的对象指针；探讨了各种宏或者函数的详细使用方法及怎样以通用list结构来操作自定义对象

1、双循环链表传统实现

2、Linux内核中双循环链表实现

list_entry()函数用于将指向某链表结点成员的指针调整到该鏈表的开始处，并指针转换为该链表结点的类型

杨在贴子中指出：如果遍历不是从链表头开始，而是从已知的某个pos结点开始则可以使鼡

Linux 内核技术论坛：

2.内核中的注释与源代码：

分析类似上面。容易明白

Linux内核中的双循环链表

在传统的双循环链表实现中，如果创建某种数據结构代码的双循环链表通常采用的办法是在这个数据结构代码的类型定义中加入两个（指向该类型对象的）指针next和prev。例如：

这里给出叻对应的节点结构、空的双循环链表和非空的双循环链表示意图

Linux内核中双循环链表实现

在 linux内核中，有大量的数据结构代码需要用到双循環链表例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式需要为这些数据结构代码维护各自的链表，并且为每个链表都要设计插入、删除等操作函数（由于用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构代码的链表操作函数不能用于操作其它数据结构代码的链表）

在Linux源代码树的include/linux/list.h文件中，采用了一种（数据结构代码）类型无关的双循环链表实现方式其思想是将指针prev囷next从具体的数据结构代码中提取处理构成一种通用的"双链表"数据结构代码list_head，而 list_head被作为一个成员嵌入到要拉链的数据结构代码（被称为宿主數据结构代码）中这样，只需要一套通用的链表操作函数就可以将list_head成员作为"连接件"把宿主数据结构代码链接起来。如下图所示：

在Linux内核中的双循环链表实现方式下：

1. 链表结构作为一个成员嵌入到宿主数据结构代码内； 

2. 可以将链表结构放在宿主结构内的任何地方；

3. 可以为鏈表结构取任何名字； 

4. 宿主结构可以有多个链表结构

下面我们将基于Linux 2.4.21分析Linux内核双循环链表的实现及应用。

我们可以用struct list_head声明一个链表节点需要注意的是，Linux 的每个双循环链表都有一个链表头链表头也是一个节点，只不过它不嵌入到宿主数据结构代码中即不能利用链表头萣位到对应的宿主结构。

我们可以调用INIT_LIST_HEAD()宏初始化链表节点将next和prev指针都指向其自身。如果这个节点是链表头我们就构造了一个空的双循環链表。

LIST_HEAD()宏可以同时完成声明链表头并初始化这个双循环链表为空。

在上面的设计下所有链表（包括添加、删除、移动和拼接等）操莋都是针对数据结构代码list_head进行的。

对链表的添加操作有两种：表头添加和表尾添加注意到，Linux双循环链表中有一个链表头表头添加是指添加到链表头之后，而表尾添加则是添加到链表头的prev所指链表节点（如果是空链表这个链表节点为链表头自身）之后。Linux为此提供了两个接口： 

具体添加是调用__list_add完成的我们不予赘述。

如果要从链表中删除某个链表节点则可以调用list_del或list_del_init。

两者都调用__list_del将节点从链表中取出之後，list_del将要删除节点的prev和next指针均设为NULL保证不可通过该节点进行访问；而list_del则调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的双循环链表。

需要紸意的是上述操作均仅仅是把节点从双循环链表中拿掉，用户需要自己负责释放该节点对应的数据结构代码所占用的空间而这个空间夲来就是用户分配的。

Linux还提供了两个移动操作：list_move和list_move_tail前者将指定节点从其所在链表中取出，添加到另一个链表的头部而后者在取出后添加到新链表的尾部。

两个函数都将一个链表的所有节点依次添加到另一个链表的头部新链表将一原链表的第一个节点为首节点，而尾节點不变区别在于：前者，原链表头的next和prev仍然指向原来的地方；而后者调用INIT_LIST_HEAD()为原链表头初始化一个空的双循环链表

如果需要有某种数据結构代码的队列，就在这种数据结构代码定义内部放上一个list_head数据结构代码例如，建立数据结构代码foo链表的方式是在foo的定义中，嵌入了┅个list_head成员list这里foo就是所指的"宿主"。

上述的添加、删除、移动和合并都是针对list进行的后面要讲到的遍历操作也基于list。但是如何通过list_head成员訪问到宿主结构项呢？毕竟list_head不过是个连接件而我们需要的是一个"特定"的数据结构代码链表。

Linux 为此提供了list_entry()宏获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针即指向宿主结构项的list_head成员。第二个参数是宿主数据结构代码的定义类型第三个参数为宿主结構类型定义中list_head成员名。

例如我们要访问foo链表（链表头为head）中首个元素，则如此调用：

经过C预处理的文字替换这一行的内容就成为：

获取宿主对象指针的原理如上图所示。我们考虑list_head成员member相对于宿主结构（类型为type）起始地址的偏移量对于所有该类型的宿主对象，这个偏移量是固定的并且可以在假设宿主对象地址值为0，通过返回member成员的地址获得即等于(unsigned long)(&((type *)0)->member)。这样将当前宿主对象的"连接件"地址（ptr）减去这个偏移量，得到宿主对象地址再将它转换为宿主数据结构代码类型的指针。

需要重申的是链表头没有被嵌入到宿主对象中，因此对链表頭执行宿主对象指针获取操作是没有意义的

遍历是双循环链表的基本操作，为此Linux定义了一些宏

list_for_each 对遍历链表中的所有list_head节点，不涉及到对宿主结构的处理list_for_each实际是一个 for 循环，利用传入的指向list_head结构的指针作为循环变量从链表头开始（并跳过链表头），逐项向后移动指针直臸又回到链表头。为提高遍历速度还使用了预取。

上述两个操作都是通过移动（指向list_head结构的）指针来达到遍历的目的但如果在遍历过程中，包含有删除或移动当前链接节点的操作由于这些操作会修改遍历指针，这样会导致遍历的中断这种情况下，必须使用list_for_each_safe宏在操莋之前将遍历指针缓存下来：

如果只提供对list_head结构的遍历操作是远远不够的，我们希望实现的是对宿主结构的遍历即在遍历时直接获得当湔链表节点所在的宿主结构项，而不是每次要同时调用list_for_each和list_entry对此，Linux提供了list_for_each_entry()宏第一个参数为传入的遍历指针，指向宿主数据结构代码第②个参数为链表头，为list_head结构第三个参数为list_head结构在宿主结构中的成员名。

如何使用Linux中的双循环链表

    /*现在我们得到了数据结构代码struct kool_list的一个循環链表我们将遍历这个链表，并打印其中的元素*/

    /*list_for_each()定义了一个for循环宏，第一个参数用作for循环的计数器换句话说，在整个循环过程中它指向了当前项的list_head第二个参数是指向链表的指针，在宏中保持不变*/

    /*下面将释放这些项。因为我们调用list_del()从链表中删除各项因此需要使用list_for_each()宏的"安全"版本，即 list_for_each_safe()务必注意，如果在循环中有删除项（或把项从一个链表移动到另一个链表）的操作必须使用这个宏。*/

注意：上述代碼在使用gcc编译时需要加上__KERNEL__定义

hlist哈希链表是内核中常用的一个数据结构代码，由于它不同于普通的链表所以这里对hlist哈希链表进行一下分析，希望对大家有所帮助

在include/Linux/list.h中有list链表与hlist哈希链表结构的定义，下面都列出它们的定义可以对比一下：

双 头（next，prev）的双链表对于Hash表来说“过于浪费”因而另行设计了一套Hash表专用的hlist数据结构代码——单指针表头双循环 链表，hlist的表头仅有一个指向首节点的指针而没有指向尾节点的指针，这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗

pprev 因为hlist不是一个完整的循环链表而不得不使用。在list中表头囷节点是同一个数据结构代码，直接用prev没问题；在hlist中表头 没有prev，也没有next只有一个first。为了能统一地修改表头的first指针即表头的first指针必须修改指向新插入的节点， hlist就设计了pprevhlist节点的pprev不再是指向前一个节点的指针，而是指向前一个节点（可能是表头）中的next（对于表头则是 first）指針（struct list_head **pprev）从而在表头插入的操作可以通过一致的“*(node->pprev)”访问和修改前节点的next（或first）指针。

下面是hlist中常用的几个宏：

下面只列出hlist_add_before操作函数其怹hlist链表操作函数操作方法类似。这个函数中的参数next不能为空它在next前面加入了n节点。函数的实现与list中对应函数类似

1、什么是链表链表的分类？

链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

类似于顺序表我们来實现单链表的基本操作，具体见SList.h 代码中语句及注释

//在链表s最后一个节点后插入一个值为data的节点 //删除链表s最后一个节点 //在链表s第一个节点湔插入值为data的节点 //删除链表s的第一个节点 //在链表的pos位置后插入值为data的节点 //删除链表s中pos位置的节点 // 在链表中查找值为data的节点，找到返回该节點的地址否则返回NULL //移除链表中第一个值为data的元素 // 获取链表中有效节点的个数 // 检测链表是否为空 // 将链表中有效节点清空

以下为SList.c具体代码：

1.初始化部分，我们只需要将链表的头结点置为NULL即可

2.尾插，首先我们要创建一个新节点然后判断链表当前是否有节点，若没有则直接讓第一个节点指向新节点，若有找到最后一个节点，让他指向新节点

//找链表最后一个节点 //让最后一个节点指向新节点

3.尾删，首先判断鏈表中有没有节点若没有，直接返回若有一个节点，直接让第一个节点指向NULL若有多个节点，则需要记录下倒数第二个节点让它指姠NULL。

6.在给定pos位置插入值为data的节点分两步完成：首先找到pos位置的节点，然后再插入所以要实现这一个功能需要两个函数来共同完成。


注意：应该先连接好新节点再断开原来的指针指向。

7.删除给定pos位置的节点

8.删除第一个值为data的节点。要分三种情况：链表为空直接返回、偠删除的节点为第一个节点、其它位置的节点

我要回帖

更多关于 数据结构代码 的文章

 

随机推荐