精华内容
下载资源
问答
  • 主要说一下冒泡排序的一些关键地方的个人理解,比如算法思想,两个循环的作用意义,中间循环变量范围的确定等。原理:比较两个相邻的元素,将值大的元素交换至右端。思路:依次比较相邻的两个数,将小数放在前面,...

    主要说一下冒泡排序的一些关键地方的个人理解,比如算法思想,两个循环的作用意义,中间循环变量范围的确定等。

    原理:比较两个相邻的元素,将值大的元素交换至右端。

    思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。

    第一趟比较完成后,最后一个数一定是数组中最大的一个数,所以第二趟比较的时候最后一个数不参与比较;

    第二趟比较完成后,倒数第二个数也一定是数组中第二大的数,所以第三趟比较的时候最后两个数不参与比较;

    依次类推,每一趟比较次数-1;

    ……

    举例说明:要排序数组:int[] arr={6,3,8,2,9,1};

    第一趟排序:

    第一次排序:6和3比较,6大于3,交换位置: 3 6 8 2 9 1

    第二次排序:6和8比较,6小于8,不交换位置:3 6 8 2 9 1

    第三次排序:8和2比较,8大于2,交换位置: 3 6 2 8 9 1

    第四次排序:8和9比较,8小于9,不交换位置:3 6 2 8 9 1

    第五次排序:9和1比较:9大于1,交换位置: 3 6 2 8 1 9

    第一趟总共进行了5次比较, 排序结果: 3 6 2 8 1 9

    第二趟排序:

    第一次排序:3和6比较,3小于6,不交换位置:3 6 2 8 1 9

    第二次排序:6和2比较,6大于2,交换位置: 3 2 6 8 1 9

    第三次排序:6和8比较,6大于8,不交换位置:3 2 6 8 1 9

    第四次排序:8和1比较,8大于1,交换位置: 3 2 6 1 8 9

    第二趟总共进行了4次比较, 排序结果: 3 2 6 1 8 9

    第三趟排序:

    第一次排序:3和2比较,3大于2,交换位置: 2 3 6 1 8 9

    第二次排序:3和6比较,3小于6,不交换位置:2 3 6 1 8 9

    第三次排序:6和1比较,6大于1,交换位置: 2 3 1 6 8 9

    第二趟总共进行了3次比较, 排序结果: 2 3 1 6 8 9

    第四趟排序:

    第一次排序:2和3比较,2小于3,不交换位置:2 3 1 6 8 9

    第二次排序:3和1比较,3大于1,交换位置: 2 1 3 6 8 9

    第二趟总共进行了2次比较, 排序结果: 2 1 3 6 8 9

    第五趟排序:

    第一次排序:2和1比较,2大于1,交换位置: 1 2 3 6 8 9

    第二趟总共进行了1次比较, 排序结果: 1 2 3 6 8 9

    最终结果:1 2 3 6 8 9

    由此可见:N个数字要排序完成,总共进行N-1趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数,即

    for(i=0;ifor(j=0;j外层循环的作用是: 提取出目前未排序数组中最大的数,放置于已排数据的左边。也就是说我们第一次外层循环,是把最大数的位置交换到数组的最右边,第二次外层循环是把次大数交换到数组的次右边,依次类推。

    内层循环的作用是: 实现我们想要的大数下沉的过程。每次比较的是相邻两个数据,所以一个数组的长度为n,我们只需要做 n-1 次相邻的比较,就可以实现大数下沉,而 之前循环已经沉淀的大数并不需要再进行 排序了。

    很清楚的看到N个数字要排序完成,总共进行N-1趟排序

    为什么外层循环判断条件是i

    n 个数字总共需要 n-1 趟排序,外层循环 i 从0到 n-1 正好是 n-1 次。

    为什么内层循环判断条件是j

    这要从冒泡排序原理说起:冒泡排序每循环排序一次,就把最大的一个数排在了最右边(默认升序排),每一次排序都是在上一次排序的基础上再排序,(比如)第2次排序之后,i已经成2了,第三次排序是要在第二次的基础上在进行排序,而第二次排序后就已经把两个最大的数已经放到最后了,所以第三次排序就不需要在去比他俩,就得把这个“2“减掉,只需要循环n-i次(此时的i是2);为什么-i之后还要-1呢? 这是因为在内层循环的判断中是把当前值和后面一个值做比较的。如果不减1,则当循环到最后一个值的时候,再取下一个值就取不到,就需要额外的操作,或者抛出数组下标越界的异常。

    其实内层的 j

    1 就是标准解释 上述的防止数组下标越界,比如n[] = {5, 22, 7, 42, 23},个数n=5,i现为2,n-i=3,i为2即进行第3趟,两个数已经确定好,只需要比较前三个数了,而这只需要比较2次,即n-i(为2)-1=2。如果不减一,这里就是n-i(为2)= 3比三次,这显然是错的。就是正常是:

    if n(0)>n(1)

    if n(1)>(2) 这是正确的

    不正确时,5-2=3 j从0到3 得比3次:

    if n(0)>n(1)

    if n(1)>(2)

    if n(2)>(3) 这就比错了 这都把 确定好的倒数第二大的数再给比较,这就是错了。就成乐下表越界了。

    2 每趟的比较中,都是n-1次,每趟中都是比总共这次要比的数的个数减一次,再加上要把i这已经确定的数的个数减去,即就是 j-i-1。实际上这也是n-i,n把来的i减去,剩下的待排序的数共有多少个,他们的个数再减去一就是他们这些剩下的数需要比较的次数了,这个跟网上说的数组是从下标0开始,没啥关系,下标从0或1开始,影响的是内层循环的比较,是0,就直接引用,是1,就得n[i-1]。至于说的这个从0开始的说法,则它根本上也是想说防止下标越界。

    至于算法优化什么的,暂时不考虑,这里只简单说明了算法中几个关键的点。

    个人学习感悟,如有错误,还请指正。

    附一些讲冒泡比较好的说的文章:

    https://blog.csdn.net/kelinfeng16/article/details/84034386

    https://www.cnblogs.com/shen-hua/p/5422676.html

    展开全文
  • Shell脚本:双层循环

    2021-05-13 19:17:07
    双层循环听到整个名字相必大家们并不陌生,有点语言基础的都知道就是在循环里面在嵌套一层循环。下面我会通过九九乘法口诀表的例子来详细解析双层循环。 例题如下 通过for循环来实现九九乘法表: #!/bin/bash/ for...

    双层循环听到整个名字相必大家们并不陌生,有点语言基础的都知道就是在循环里面在嵌套一层循环。下面我会通过九九乘法口诀表的例子来详细解析双层循环。

    例题如下
    通过for循环来实现九九乘法表:

    #!/bin/bash/
    
    for((i=1; i<=9; i++))
    do
            for((j=1; j<=i;j++))
            do
    
            sum=$[ $i * $j ]
            echo -ne  "$i*$j=$sum\t"
            done
    echo ""
    done
    

    在这里插入图片描述
    在这里插入图片描述
    不难发现上述代码可以轻而易举的实现九九乘法表。

    通过while来实现九九乘法表

    i=1
    while [ $i -le 9 ]
    do
                    j=1
            while [ $j -le $i ]
            do
                    sum=$[ $i * $j ]
                    echo -ne "$i*$j=$sum\t" 
                    let j++
            done
            let i++
    echo ""
    done
    

    在这里插入图片描述
    在这里插入图片描述
    不难发现while双层循环代码也可以轻而易举的实现九九乘法表。

    上述举例两种类型的代码实现。不难发现其实双层循环的意思就是先执行一次外层循环,然后在进行内层循环,内层循环结束之后,在进行第二次的外层循环,然后内层循环继续执行到结束之后在开始进行下一次的外层循环,以此内推,这就是双层循环的本质了。

    下面我们会通过一系列的例子来让带火们感受一下双层循环的快乐。

    例题1: 通过代码实现矩形。(可自由定义层数)

    #!/bin/bash/
    read -p "请输入矩形的长:" length
    read -p "请输入矩形的宽:" weigth
    for((i=0; i<weigth; i++))
    {
            for((j=0; j<length; j++))
            {
                    echo -n "*"
            }
    echo ""
    }
    

    在这里插入图片描述

    在这里插入图片描述

    例题2: 通过代码实现直角三角形。(可自由定义层数)

    #!/bin/bash/
    read -p "请输入三角形的高度:" length
    for ((i=0; i<length; i++ ))
    {
            for ((j=0; j<=i; j++))
            {
                    echo -n  "*"
            }
    echo ""
    }
    

    在这里插入图片描述
    在这里插入图片描述
    例题3: 通过代码实现等腰三角形。(可自由定义层数)

    #!/bin/bash/
    read -p "请输入您需要实现的行数:" line
    for ((i=1; i<=line; i++))
    do
            for((j=line-1; j>=i; j--))
            do
                    echo -n " "
            done
            k=$[2*i -1]
            for ((n=0; n<k; n++))
            do
                    echo -n "*"
            done
            echo ""
    done
    

    在这里插入图片描述
    在这里插入图片描述
    例题4: 通过代码实现菱形。(可自由定义层数)

    #!/bin/bash/
    read -p "请输入您需要实现的行数:" line
    for ((i=1; i<=line; i++))
    do
            for((j=line-1; j>=i; j--))
            do
                    echo -n " "
            done
            k=$[2*i -1]
            for ((n=0; n<k; n++))
            do
                    echo -n "*"
            done
            echo ""
    done
    for ((i=line-1; i>=1; i--))
    do
            for ((j=line-1; j>=$i; j-- ))
            do
                    echo -n " "
            done
            for ((n=1; n<=2*i-1; n++))
            do
                    echo -n "*"
            done
            echo ""
    done
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 原标题:C语言从入门到精通:嵌套循环C编程语言允许使用一个循环内嵌套的另一个循环。下面的内容展示几个例子来说明这个概念。 语法在C语言中嵌套for语句循环的语法如下:for ( init; condition; increment ){ for ...

    原标题:C语言从入门到精通:嵌套循环

    C编程语言允许使用一个循环内嵌套的另一个循环。下面的内容展示几个例子来说明这个概念。

    205cbec83b82d53556116ae7e95424f1.png

    语法

    在C语言中嵌套for语句循环的语法如下:

    for ( init; condition; increment ){ for ( init; condition; increment ) { statement(s); } statement(s);}

    在C编程语言中嵌套while循环声明的语法如下:

    while(condition){ while(condition) { statement(s); } statement(s);}

    在C编程语言嵌套do...while循环语句的语法如下:

    do{ statement(s); do { statement(s); }while( condition );}while( condition );

    在循环嵌套最后需要说明的是,可以把任何类型的循环的任何其他类型的循环内。例如,对于环可以是一个while循环,或反之亦然内部。

    例子:

    下面的程序使用嵌套for循环从2至100找出素数:

    (adsbygoogle = window.adsbygoogle || []).push({});

    (adsbygoogle = window.adsbygoogle || []).push({});

    #include int main (){ /* local variable definition */ int i, j;

    for(i=2; i

    ", i); }

    return 0;}返回搜狐,查看更多

    责任编辑:

    展开全文
  • 【摘要】本文详解了内核中面向对象的list结构的原理,以及如何以list为内嵌对象来构造自己的...【关键字】双向循环链表,list,list_entry,typeof,containerof,list_for_each, list_for_each_entry1、双循环链表...

    【摘要】本文详解了内核中面向对象的list结

    构的原理,以及如何以list为内嵌对象来构造自己的链表结构,如何从内嵌list对

    象获得自定义的对象指针;探讨了各种宏或者函数的详细使用方法及怎样以通用list结

    构来操作自定义对象。

    【关键字】双向循环链表,list,list_entry,typeof,containerof,list_for_each, list_for_each_entry

    1、双循环

    链表传统实现...1

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

    3、定义和

    初始化...3

    4、通用链

    表操作接口...4

    4.1添加节点...4

    4.2删除节点...5

    4.3移动节点...6

    4.4链表判空...6

    4.5链表合并...7

    5、获取宿主对象指针...8

    6、遍历...11

    6.1 List-head链表遍历...11

    6.2遍历宿主对象...12

    7、如何使用Linux中的双循环链表...14

    、双循环链表传统实现

    在传统的双循环链表实现中,如果创建某种数据结构的双循环链表,通常采用的办法是在这个数据结构的类

    型定义中加入两个(指向该类型对象的)指针next和prev。例如:

    typedef struct foo {

    struct

    foo *prev;

    struct

    foo *next;

    } foo_t;

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

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

    在linux内核中,有大量的数据结

    构需要用到双循环链表,例如进程、文件、模块、页面等。若采用双循环链表的传统实现

    方式,需要为这些数据结构维护各自的链表,并且为每个链表都要设计插入、删除等操作函数。因

    为用来维持链表的next和prev指针指向对应类型的对象,

    因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。

    在Linux源代码树的include/linux/list.h文件中,采用了一种类型无关的双循环链表实

    现方式。其思想是将指针prev和next从具体的数据结构中提取出来构成一种通用的"双链表"数据结构list_head。如果需要构造某类对象的特定链表,则在其

    结构(被称为宿主数据结构)中定义一个类型为list_head类型的成员,通过这个成员将这类对

    象连接起来,形成所需链表,并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数,即可

    构造和操作不同对象的链表,而无需为每类对象的每种列表编写专用函数,实现了代码的重用。

    list_head结构

    -----------struct list_head{}及初始化宏---------

    struct list_head

    {

    struct

    list_head *next, *prev;

    };

    当用此类型定义一个独立的变量时,其为头结点。

    当其为某个结构体的一个成员时,其为普通结点。尽管形式一样,但表达的意义不同,是否应该定义为两

    个类型list_head和list_node???无法分开,空链表时指向了自己

    list_head成员作为"连接

    件",把宿主数据结构链接起来。如下图所示:

    在Linux内核中的双循环链表实现

    方式下:

    1. list_head类型的变量作为一个成员嵌入到宿主数据结构内;

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

    3.可以为链表结构取任何名字;

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

    5.用list_head中的成员和相对

    应的处理函数来对链表进行遍历;

    6.如果想得到宿主结构的指针,使用list_entry可以算出来。

    、定义和初始化

    --LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------

    #define LIST_HEAD_INIT(name) {

    &(name), &(name) }

    #define LIST_HEAD(name) /

    struct

    list_head name = LIST_HEAD_INIT(name)

    需要注意的是,Linux的每个双循环链表都有一个链表头,链表头也是一个节点,只不过它不嵌入到宿

    主数据结构中,即不能利用链表头定位到对应的宿主结构,但可以由之获得虚

    拟的宿主结构指针。

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

    静态定义一个list_head类型变量,该变量一定为头节点。name为struct list_head{}类型的一个变量,&(name)为该结构体变量的地址。用name结

    构体变量的始地址将该结构体变量进行初始化。

    #define INIT_LIST_HEAD(ptr) do { /

    (ptr)->next

    = (ptr); (ptr)->prev = (ptr); /

    } while (0)

    动态初始化一个已经存在的list_head对象,ptr为一个结构体的指针,这样可以初始化堆栈以及全局区定义的list_head对象。ptr使用时候,当用括号,(ptr),避免ptr为表达式时宏扩展带来的异常问题。此宏很少用于动态初始化内嵌的list对象,主要是链表合并或者删除后重新初始化头部。若是在堆中申请了这个链表头,调用INIT_LIST_HEAD()宏初始化链表节点,将next和prev指针都指向其自身,我们就构造了一个空的双循环链表。

    2.6内核中内联函数版本如下:

    static inline void

    INIT_LIST_HEAD(struct list_head *list)

    {

    list->next

    = list;

    list->prev

    = list;

    }

    此时的参数有明确的类型信息struct

    list_head,同时可以看出其为指针,list无须象宏中那样(),即使参数为表达式,其也是求值后再作为参数传入的。内联函数有严格的参数类型检

    查,同时不会出现宏函数扩展带来的异常问题,但是运行效率和空间效率与宏函数一致。

    、通用链表操作接口

    添加节点

    在上面的设计下,所有链表(包括添加、删除、移动和拼接等)操作都是针对数据结构list_head进行的。提供给用户的的添加链表的操作有两种:表头添加和表尾添加。注意到,Linux双循环链表中有一个链表头,表头添加是指添加到链表头之后,而表尾添加则是添加到链表头的prev所指链表节点之后。

    ------------__list_add()------list_add()------list_add_tail()-------

    static inline void __list_add(struct list_head *new, struct list_head *prev,struct list_head *next)

    {

    next->prev

    = new;

    new->next

    = next;

    new->prev

    = prev;

    prev->next

    = new;

    }

    普通的在两个非空结点中插入一

    个结点,注意new、prev、next都不能是空值。

    Prev可以等于next,此时在只含头节点的链表中插入新节点。

    static inline void list_add(struct

    list_head *new, structlist_head *head)

    {

    __list_add(new,

    head, head->next);

    }

    在head和head->next两指针所指向的结点之间插入new所

    指向的结点。

    即:在head指针后面插入new所指向的结点。Head并非一定为头结点。

    当现有链表只含有一个头节点时,

    上述__list_add(new,

    head, head->next)仍然成立。

    static inline void list_add_tail(struct

    list_head *new, struct list_head *head)

    {

    __list_add(new,

    head->prev, head);

    }

    在结点指针head所指向结点的前面插入new所指向的结点。当head指

    向头节点时,也相当于在尾结点后面增加一个new所指向的结点。

    注意:

    head->prev不能为空,即若head为

    头结点,其head->prev当指向一个数值,一般为指向尾结点,构成循

    环链表。

    上述三个函数实现了添加一个节点的任务,其中__list_add()为底层函数,“__”通常表示该函数是底层函数,供其他模块调用,此处实现了较好的代码复用,list_add和list_add_tail虽然原

    型一样,但调用底层函数__list_add时传递了不同的参数,从而实现了在head指

    向节点之前或之后添加新的对象。

    删除节点

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

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

    -----------__list_del()---list_del()-----list_del_init()----------

    static inline void __list_del(struct

    list_head * prev, struct list_head * next)

    {

    next->prev

    = prev;

    prev->next

    = next;

    }

    在prev和next指针所指向的结点之间,两者互相所指。在后面会看到:prev为待删除的结点的前面一个结点,next为待删除的结点的后面一个结点。

    static inline void list_del(struct

    list_head *entry)

    {

    __list_del(entry->prev,

    entry->next);

    entry->next

    = LIST_POISON1;

    entry->prev

    = LIST_POISON2;

    }

    删除entry所指的结点,同时将entry所指向的结点指针域封死。

    对LIST_POISON1,LIST_POISON2的解释说明:

    Linux内核中解释:These arenon-NULL

    pointers that will result in page faultsunder normal

    circumstances, used to verify that nobody usesnon-initialized

    list entries.

    #define LIST_POISON1((void

    *) 0x00100100)

    #define LIST_POISON2((void

    *) 0x00200200)

    常规思想是:entry->next = NULL; entry->prev = NULL;保证不可通过该节点进行访问。

    ---------------list_del_init()--------------------

    static inline void list_del_init(struct

    list_head *entry)

    {

    __list_del(entry->prev,

    entry->next);

    INIT_LIST_HEAD(entry);

    }

    删除entry所指向的结点,同时调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的空双循环链表。

    移动节点

    Linux还提供了两个移动操作:list_move和list_move_tail。

    -----------list_move()--list_move_tail()----------

    static inline void list_move(struct

    list_head *list, struct list_head *head)

    {

    __list_del(list->prev,

    list->next);

    list_add(list,

    head);

    }

    将list结点前后两个结点互相指向

    彼此,删除list指针所指向的结点,再将此结点插入head,

    和head->next两个指针所指向的结点之间。

    即:将list所指向的结点移动到head所指向的结点的后面。

    static inline void

    list_move_tail(struct list_head *list,struct

    list_head *head)

    {

    __list_del(list->prev,

    list->next);

    list_add_tail(list,

    head);

    }

    删除了list所指向的结点,将其插入到head所指向的结点的前面,如果head->prev指向链表的尾结点的话,就是将list所指向的结点插入到链表的结尾。

    链表判空

    由list-head构成的双向循环链表中,通常有一个头节点,其不含有有效信息,初始化时prev和next都指向自身。判空操作是判断除了头节点外是否有其他节点。

    ---------------------list_empty()-------------

    static inline int list_empty(const

    struct list_head *head)

    {

    return

    head->next == head;

    }

    测试链表是否为空,如果是只有一个结点,head,head->next,head->prev都指向

    同一个结点,则这里会返回1,表示空;但这个空不是没有任何结点,而是

    只有一个头结点,因为头节点只是纯粹的list节点,没有有效信息,故认为为空。

    --------------------list_empty_careful()---------

    static inline int list_empty_careful(const struct list_head *head)

    {

    struct

    list_head *next = head->next;

    return

    (next == head) && (next == head->prev);

    }

    分析:

    1.只有一个头结点head,

    这时head指向这个头结点,head->next,head->prev指向head,即:head==head->next==head->prev,这时候list_empty_careful()函数返回1。

    2.有两个结点,head指

    向头结点,head->next,head->prev均指向后面那个结点,即:head->next==head->prev,而head!=head->next,head!=head->prev.所以函数将返回0

    3.有三个及三个以上的结点,这是一般的情况,自己容易分析了。

    注意:这里empty list是指只有一个空的头结点,而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head

    链表合并

    Linux还支持两个链表的拼接,提供给用户的具体函数是list_splice和list_splice_init:

    ---------------__list_splice()------------------

    static inline void __list_splice(struct

    list_head *list,struct list_head *head)

    {

    struct

    list_head *first = list->next;

    struct

    list_head *last= list->prev;

    struct

    list_head *at= head->next;

    first->prev

    = head;

    head->next

    = first;

    last->next

    = at;

    at->prev

    = last;

    }

    将一个非空链表插入到另外一个链表中。不作链

    表是否为空的检查,由调用者默认保证。因为每个链表只有一个头节点,将空链表插入到另外一个链表中是没有意义的。但被插入的链表可以是空的。

    --------------------list_splice()----------------

    /**

    *

    list_splice - join two lists

    * @list:被合并的链表的头节点.

    * @head: the place to add it in the first list.

    */

    static inline void list_splice(struct

    list_head *list, struct list_head *head)

    {

    if

    (!list_empty(list))

    __list_splice(list,

    head);

    }

    这种情况会丢弃list所

    指向的头结点,这是特意设计的,因为两个链表有两个头结点,要去掉一个头结点。只要list非空链,head无任何限制,该程序都可以实现链表合并。

    --------------------list_splice_init()-----------------------------------

    /**

    *

    list_splice_init - join two lists and reinitialise the emptied list.

    * @list:

    the new list to add.

    * @head:

    the place to add it in the first list.

    *

    * The list

    at @list is reinitialised

    */

    static inline void

    list_splice_init(struct list_head *list,

    struct list_head *head)

    {

    if

    (!list_empty(list)) 0

    {

    __list_splice(list,

    head);

    INIT_LIST_HEAD(list);

    }

    }

    将一个链表的有效信息合并到另外一个链表后,重新初始化空的链表头。

    、获取宿主对象指针

    如果需要有某种数据结构的队列,就在这种数据结构定义内部放上一个list_head数据结构。例如,建立数据结构foo链

    表的方式是,在foo的定义中,嵌入了一个list_head成员list。这里foo就是所指的"宿主"。

    typedef struct foo {

    struct

    list_head list;

    };

    但是,如何通过list_head成员访问到宿主结构项呢?毕竟list_head不过是个连接件,而我们

    需要的是一个"特定"的数据结构链表。

    先介绍几个基本宏:offsetof、typeof、containerof

    -------/linux/stddef.h-----offsetof()-----------

    #define __compiler_offsetof(a,b)__builtin_offsetof(a,b)

    而__builtin_offsetof()宏就是在编译器中已经设计好了的函数,直接调用即可。

    -------------------------------

    #undef

    offsetof//取消先前的任何定义,可以保证下面的定义生效

    #ifdef __compiler_offsetof

    #define offsetof(TYPE,MEMBER)__compiler_offsetof(TYPE,MEMBER)

    #else

    #define offsetof(TYPE, MEMBER)

    ((size_t) &((TYPE *)0)->MEMBER)

    #endif

    一共4步

    1. ( (TYPE *)0 ) 0地址强制"转换"为TYPE结构的指针;

    2. ((TYPE *)0)->MEMBER访问结构中的数

    据成员;

    3.&(

    ( (TYPE *)0 )->MEMBER)取

    出数据成员的地址;

    4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之

    处在于将0转换成(TYPE*),结构以内存空间首地址0作为起始地址,则成员地址自然为偏移地址;

    举例说明:

    #include

    typedef struct _test

    {

    char

    i;

    int j;

    char

    k;

    }Test;

    int main()

    {

    Test

    *p = 0;

    printf("%p/n",

    &(p->k));

    }

    这里使用的是一个利用编译器技术的小技巧(编

    译器自动算出成员的偏移量),即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址,然后根据结构体的首地址为0,从而得出该偏移地址就是该结构体变量在该结构体中的偏移,即:该结构体成员变量距离结构体首的距

    离。在offsetof()中,这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构,offsetof(type,member)是一个常量,list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。

    ---------------------typeof()--------------------

    unsigned int i;

    typeof(i) x;

    x=100;

    printf("x:%d/n",x);

    typeof()是gcc的扩展,和sizeof()类似。

    ------------------------

    在container_of宏

    中,它用来给typeof()提供参数,以获得member成员的数据类型;

    ---------------container_of()--------------------

    container_of()来自/linux/kernel.h

    内核中的注释:container_of - cast a

    member of a structure out to the containing structure。

    ptr:the pointer to the member.

    type:the type of the container struct this is embedded

    in.

    member:the

    name of the member within the struct.

    #define container_of(ptr, type, member)

    ({/

    const

    typeof( ((type *)0)->member ) *__mptr = (ptr);/

    (type

    *)( (char *)__mptr - offsetof(type,member) );})

    自己分析:

    1.(type *)0->member为设计一个type类

    型的结构体,起始地址为0,编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变量的地址,由于结构体

    起始地址为0,所以此结构体成员变量的偏移地址就等于其

    成员变量在结构体内距离结构体开始部分的偏移量。即:&(type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为:(size_t)(& ((type *)0)->member)经过size_t的强制类型转换后,其

    数值为结构体内的偏移量。该偏移量这里由offsetof()求出。

    2.typeof( ( (type

    *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针,

    其指向ptr所指向的变量处。

    3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) )用来求出结构体起始地址(为char *型指针),然后(type

    *)( (char *)__mptr - offsetof(type,member) )在(type *)作用下进行将字节

    型的结构体起始指针转换为type *型的结构体起始指针。

    这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。

    介绍了上面的几种基本宏后,对list_entry的理解就容易了。

    ----------------list_entry()--------------------

    list_entry()宏,获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针,即

    指向宿主结构项的list_head成员。第二个参数是宿主数据结构的定义类型。第三个参数为宿主结构类型定义中list_head成员名。

    #define list_entry(ptr, type, member) /

    container_of(ptr,

    type, member)

    扩展替换即为:

    #define list_entry(ptr, type, member) /

    ((type

    *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

    例如,我们要访问foo链

    表(链表头为head)中首个元素,则如此调用:

    list_entry(head->next,

    struct foo, list);

    经过C预处理的文字替换,这一行的内容

    就成为:

    ((struct foo *)((char *)(head->next)

    - (unsigned long)(&((struct foo *)0)->list)))

    获取宿主对象指针的原理如上图所示。我们考虑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_for_each()------------------

    #define list_for_each(pos, head) /

    for

    (pos = (head)->next; prefetch(pos->next), pos != (head); /

    pos = pos->next)

    head为头节点,遍历过程中首先从(head)->next开始,当pos==head时退出,故head节

    点并没有访问,这和list结构设计有关,通常头节点就是纯粹的list结

    构,不含有其他有效信息,或者头节点含有其他信息,如内核PCB链表中的头节点为idle任务,但其不参予比较优先级,因此此时头节点只是作为双向链表遍历一遍的

    检测标志。

    为提高遍历速度,还使用了预取。

    -----asm-x86_64/processor.h---prefetch()---------

    static inline void prefetch(void *x)

    {

    asm

    volatile("prefetcht0 %0" :: "m" (*(unsigned long *)x));

    }

    将x指针作强制类型转换为unsigned long *型,然后取出该内存操作数,送入高速缓存。

    ----------------__list_for_each()-----------------

    #define __list_for_each(pos, head) /

    for

    (pos = (head)->next; pos != (head); pos = pos->next)

    list_for_each()有prefetch()用于复杂的表

    的遍历,而__list_for_each()无prefetch()用于简单的表

    的遍历,此时表项比较少,无需缓存。

    ----------------list_for_each_prev()-------------

    #define list_for_each_prev(pos, head) /

    for

    (pos = (head)->prev; prefetch(pos->prev), pos != (head); /

    pos = pos->prev)

    反向遍历节点

    ----------------list_for_each_safe()--------------

    如果在遍历过程中,包含有删除或移动当前链接节点的操作,由于这些操作会修改遍历指针,这样会导致遍

    历的中断。这种情况下,必须使用list_for_each_safe宏,在操作之前将遍历指针缓存下来:

    内核中解释的精华部分:

    /*

    *

    list_for_each_safe-iterate

    over a list safe against removal of list entry

    */

    #define list_for_each_safe(pos, n,

    head) /

    for

    (pos = (head)->next, n = pos->next; pos != (head); /

    pos

    = n, n = pos->next)

    在for循环中n暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。也就是说你可以遍历完当前节点后将其删除,同时

    可以接着访问下一个节点,遍历完毕后就只剩下一个头节点。这就叫safe。十分精彩。典型用途是多个进程等待在同一个等待队列上,若事件发生时唤醒

    所有进程,则可以唤醒后将其依次从等待队列中删除。

    遍历宿主对象

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

    为list_head结构,第三个参数为list_head结构在宿主结构中的成员名。

    -------------list_for_each_entry()---------------

    #define list_for_each_entry(pos, head,

    member)/

    for

    (pos = list_entry((head)->next, typeof(*pos),

    member);/

    prefetch(pos->member.next), &pos->member != (head); /

    pos = list_entry(pos->member.next,

    typeof(*pos), member))

    这是用于嵌套的结构体中的宏:

    struct example_struct

    {

    struct

    list_head list;

    int

    priority;

    ...

    //其他结构体成员

    };

    struct example_struct *node =

    list_entry(ptr,struct example_struct,list);

    自己分析:对比list_entry(ptr,type,member)可知有以下结果:

    其中list相当于member成员,struct example_struct相当于type成员,ptr相当于ptr成员。而list{}成员嵌套于example_struct{}里面。ptr指向example_struct{}中的list成员变量的。在list_entry()作用下,

    将ptr指针回转指向struct example_struct{}结构体的开始处。

    pos当指向外层结构体,比如指向struct example_struct{}的结点,最开始时候,head指

    向链表结构体struct list_head{}的头结点,头节点不含有有效信息,(head)->next则指向第一个外层结点的内嵌的链表结点struct list_head{} list,由此得出的pos当指向第一个有效结点。member即是指出该list为其内嵌的结点。

    思路:用pos指向外层结构体的结点,用head指向内层嵌入的结构体的结点。用(head)->next,pos->member.next(即:ptr->list.next)来在内嵌的结构体结点链表中遍历。每遍历一个结点,就用list_entry()将内嵌的pos->member.next指针回转为指向该结点外层结构体起始处的指针,并将指针进行指针类型转换为外层结构体型pos。&pos->member! = (head)用pos外层指针引用member即:list成员,与内层嵌入的链表之头结点比较来为循环结束条件。

    当遍历到头节点时,此时并没有pos这样一个type类型数据指针,而是以member域强制扩展了一个type类型的pos指针,此时其member域的地址就是head指

    针所指向的头节点,遍历结束,头节点的信息没有被访问。

    -------------list_for_each_entry_reverse()-------

    #define

    list_for_each_entry_reverse(pos, head, member)/

    for

    (pos = list_entry((head)->prev, typeof(*pos), m+ember);/

    prefetch(pos->member.prev), &pos->member

    != (head); /

    pos = list_entry(pos->member.prev,

    typeof(*pos), member))

    分析类似上面。

    ---------------list_prepare_entry()---------------

    如果遍历不是从链表头开始,而是从已知的某个pos结

    点开始,则可以使用list_for_each_entry_continue(pos,head,member)。但为了确保pos的

    初始值有效,Linux专门提供了一个list_prepare_entry(pos,head,member)宏,如果pos有

    值,则其不变;如果没有,则从链表头强制扩展一个虚pos指针。将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。

    内核中的list_prepare_entry()的代码:

    #define list_prepare_entry(pos, head,

    member) /

    ((pos)

    ? : list_entry(head, typeof(*pos),

    member))

    分析:

    :前面是个空值,即:若pos不为空,则pos为其自身。等效于:

    (pos)?(pos):

    list_entry(head,typeof(*pos),member)

    注意内核格式::前后都

    加了空格。

    ------------list_for_each_entry_continue()--------

    内核中的list_for_each_entry_continue()的代码:

    #define

    list_for_each_entry_continue(pos, head, member) /

    for

    (pos = list_entry(pos->member.next,

    typeof(*pos), member);/

    prefetch(pos->member.next), &pos->member

    != (head);/

    pos = list_entry(pos->member.next,

    typeof(*pos), member))

    此时不是从头节点开始遍历的,但仍然是以头节点为结束点的,即没有遍历完整个链表。

    要注意并不是从pos开

    始的,而是从其下一个节点开始的,因为第一个有效pos是从pos->member.next扩展得到的。

    -------------list_for_each_entry_safe()-----------

    它们要求调用者另外提供一个与pos同

    类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。

    内核中的注释与源代码:

    /**

    *

    list_for_each_entry_safe - iterate over list of given type safe against

    removal of list entry

    * @pos:the type * to use as a loop counter.

    * @n:another type * to

    use as temporary storage

    * @head:the head for your list.

    * @member:the name of the list_struct within the struct.

    */

    #define list_for_each_entry_safe(pos,

    n, head, member)/

    for

    (pos = list_entry((head)->next, typeof(*pos), member),/

    n

    = list_entry(pos->member.next, typeof(*pos), member);/

    &pos->member != (head); /

    pos = n, n = list_entry(n->member.next,

    typeof(*n), member))

    分析类似上面。容易明白。

    --------list_for_each_entry_safe_continue()-------

    #define

    list_for_each_entry_safe_continue(pos, n, head, member) /

    for

    (pos = list_entry(pos->member.next, typeof(*pos), member), /

    n

    = list_entry(pos->member.next, typeof(*pos), member);/

    &pos->member != (head);/

    pos = n, n = list_entry(n->member.next,

    typeof(*n), member))

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

    本文例子来自,只是对其中注释部分作了翻译。

    #include

    #include

    #include "list.h"

    struct kool_list{

    int to;

    struct

    list_head list;

    int

    from;

    };

    int main(int argc, char **argv){

    struct

    kool_list *tmp;

    struct

    list_head *pos, *q;

    unsigned

    int i;

    struct

    kool_list mylist;

    INIT_LIST_HEAD(&mylist.list);

    /*您也可以使用宏LIST_HEAD(mylist)来声明并初始化这个链表*/

    /*向链表中添加元素*/

    for(i=5;

    i!=0; --i){

    tmp=

    (struct kool_list *)malloc(sizeof(struct kool_list));

    /*INIT_LIST_HEAD(&tmp->list);调用这个函数将初始化一个动态分配的list_head。也可以不调用它,因为在后面调用的add_list()中将设置next和prev域。*/

    printf("enter

    to and from:");

    scanf("%d

    %d", &tmp->to, &tmp->from);

    /*将tmp添加到mylist链表中*/

    list_add(&(tmp->list),

    &(mylist.list));

    /*也可以使用list_add_tail()将新元素添加到链表的尾部。*/

    }

    printf("/n");

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

    /*list_for_each()定义了一个for循

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

    printf("traversing

    the list using list_for_each()/n");

    list_for_each(pos,

    &mylist.list){

    /*此刻:pos->next指向了

    下一项的list变量,而pos->prev指向上一项的list变

    量。而每项都是struct

    kool_list类型。但是,我们需要访问的是这些项,

    而不是项中的list变量。因此需要调用list_entry()宏。*/

    tmp=

    list_entry(pos, struct kool_list, list);

    /*给定指向struct list_head的指针,它所属的宿主数据结构的类型,以及它在宿主数据结构中的名称,list_entry返回指向宿主数据结构的指针。例如,在上面一行,list_entry()返回指向pos所

    属struct kool_list项的指针。*/

    printf("to=

    %d from= %d/n", tmp->to, tmp->from);

    }

    printf("/n");

    /*因为这是一个循环链表,我们也可以向前遍历。只需要将list_for_each替换为list_for_each_prev。我们也可以使用list_for_each_entry()遍历链表,在给定类型的项间进行循环。例如:*/

    printf("traversing

    the list using list_for_each_entry()/n");

    list_for_each_entry(tmp,

    &mylist.list, list)

    printf("to=

    %d from= %d/n", tmp->to, tmp->from);

    printf("/n");

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

    printf("deleting

    the list using list_for_each_safe()/n");

    list_for_each_safe(pos,

    q, &mylist.list){

    tmp=

    list_entry(pos, struct kool_list, list);

    printf("freeing

    item to= %d from= %d/n", tmp->to, tmp->from);

    list_del(pos);

    free(tmp);

    }

    return

    0;

    }

    注意:上述代码在使用gcc编

    译时需要加上__KERNEL__定义。

    转自:http://blog.csdn.net/sailor_8318/article/details/2471129

    展开全文
  • vue中的双重for循环

    千次阅读 2020-12-22 16:35:41
    举例说明 this.tablebottombox中的数据是这样的 表头 表格数据 效果图 代码是这样的 {{ item[headItem.fieldName] }}
  • 实例之while循环

    千次阅读 2021-05-21 06:12:04
    } 用do~while循环解决完全平方数问题 n+100是完全平方数且n+268是完全平方数,求 n #include #include int main() { int n,a,b; n=0; do { a=sqrt(n+100); b=sqrt(n+268); if(n+100 == a*a && n+268 == b*b) { ...
  • 循环左移: 例:1 2 3 4 5循环左移一位后变成2 3 4 5 1,循环左移两位后变成3 4 5 2 1。 下面用for循环实现: int i,k,j,temp,a[n]={1,2,3,4,5}; //数组长度为n,所以最后一位的下标为n-1 for(i=0;i<k;i++) ...
  • 在Java程序中可能使用多层循环来处理复杂的逻辑。但如果要从最内层循环跳出最外层循环是比较麻烦。在Java程序中可能使用多层循环来处理复杂的逻辑。但如果要从最内层循环跳出最外层循环是比较麻烦。下面的代码是一个...
  • 要全部的循环语句的用法。。。。不需要有例子,只需要用法就可以C语言循环语句用法有三种主要形式:1. for()循环2. while()循环3....循环 for()循环用法:for( e1 ;... 1.4种循环都可以用来处理同样问题,但一般...
  • for循环——有趣例子

    2021-04-20 11:31:44
    % Script file: timings.m%% Purpose:% This program calculates the time required to% calculate the squares of all integers from 1 to% 10,000 in three different ways:% 1. Using a for loop with an uniniti...
  • 第5章 循环结构程序设计,C 语言程序设计,北京航空航天大学 交通科学与工程学院 徐国艳,2019/7/12,2,循环的基本概念 不同形式的循环控制 多重循环问题,2019/7/12,3,什么是循环? 为什么要使用循环?,?,5.1 循环的...
  • 本文实例讲述了smarty循环嵌套用法。分享给大家供大家参考,具体如下:test3.php:require "main.php";$forum = array(array("category_id" => 1, "category_name" => "公告区","topic" => array(array(...
  • C语言多重循环语句

    2021-05-20 02:30:05
    1、复习循环控制结构,学习内容,3、while循环,5、for循环,6、循环的嵌套,4、do-while循环,7、几种循环结构的比较,1、循环控制概述,2、goto语句和goto循环,重难点,1、 while语句、do-while语句和for语句及三种循环之间...
  • 5循环结构程序设计

    2021-05-24 01:50:24
    1、第5章 循环结构程序设计,继戮景亚匡滔叭陀薪裁量滁壬纳婴锚沃符迄玛沼拦志仆料饵荒札鞠贴势穆5 循环结构程序设计5 循环结构程序设计,当某段程序要重复执行时,使用循环结构 使程序精炼 C语言提供4种循环控制语句: ...
  • 循环结构 问题 G: 例题5-7 求圆周率pi的近似值题目描述输入输出样例输入样例输出示例代码 题目描述 用如下公式 求圆周率PI的近似值,直到发现某一项的绝对值小于10-6为止(该项不累加)。 要求输出的结果总宽度占10...
  • 本程序适用于Intel的51系统单片机例 将(R2R3)和(R6R7)两个字节无符号数相乘,结果送R4R5R6R7。用移位和迭加的方式,步骤如下:1)清部分积(高16位)R4R5=0。循环数16。2)把R4R5R6R7右移一位,从最低位开始检查乘数R6...
  • 方法1:自定义异常# -*- coding:utf-8 -*-"""功能:python跳出循环"""# 方法1:自定义异常class Getoutofloop(Exception):passtry:for i in range(5):for j in range(5):if i == j == 2:raise Getoutofloop()else:...
  • 如果你不服气,上去辩驳俩下:“嵌套是你代码习惯问题,你看我,直接一个Row,反手一个Column,在children中把widget一提,层次分明,年轻人望你耗子尾汁,莫要瞎带节奏”;然后你可能就被一群人喷成狗,大意了,这...
  • (1)采用分支结构来实现,程序如下: %if语句分支结构 x=input('请输入x的值:'); if x==10 y=cos(x+1)+sqrt(x.^2+1); else y=x*sqrt(x+sqrt(x)); end y (2)采用单分支if语句来实现,程序如下: %if语句...
  • (当然他也确实有可能是无限群) 这个理解了,那接下来就是循环群了: 这里可以向上解释一下:a在这里是生成元,在上面相当于生成系。G在这里被a生成了,可不就是上面那无数子群取交所得的,生成群。不过这里,G自己...
  • 巧妙处理 return 遇上 for 循环

    千次阅读 2020-12-20 07:43:09
    有点晕,那就举例看看我们先看一个简单的 for 循环的栗子:我们的需求是:返回 i 的全部元素我们现在把这个循环放在函数中,我们直接调用函数看看。结果等于 1 ,为啥?因为 for 循环一旦遇到 return 就会马上终止...
  • MATLAB嵌套循环

    2021-04-18 13:15:27
    MATLAB嵌套循环语法:在 MATLAB 中嵌套 for 循环语句的语法如下:for m = 1:jfor n = 1:k;endend在 MATLAB 中嵌套 while 循环语句的语法如下:while while endend详细例子我们将使用一个嵌套循环来把所有从1到100的...
  • 循环是一种常用的程序控制结构。我们常说,机器相比人类的最大优点之一,就是机器可以不眠不休的重复做某件事情,但人却不行。而**“循环”**,则是实现让机器不断重复工作的关键概念。在循环语法方面,Python 表现...
  • 原文链接:python的垃圾回收机制及循环引用 - libochou - 博客园 https://www.cnblogs.com/libochou/p/10150048.html[转]java垃圾回收之循环引用 - kkmm - 博客园 ...
  • 故zhi任取daoa∈G,a的阶版要么是1要么是p,若a≠1,则权a的阶=p,如此a^p=1且a、a^2、a^3…a^(p-1)∈G,又因为|G|=p,故G={1,a,a^2…a^(p-1)},这就证明了G是循环群。扩展资料:...
  • C语言中 循环结构.ppt

    2021-05-22 08:16:46
    《C语言中 循环结构.ppt》由会员分享,可在线阅读,更多相关《C语言中 循环结构.ppt(42页珍藏版)》请在皮匠网上搜索。1、第五章循环控制结构,1,本章知识点:,while语句的一般形式及应用for语句的一般形式及应用do....
  • } 本算法中,用指针rear指向H的尾结点,而在此双向循环链表中,rear==H->prior,因此也可省去rear指针,则插入到链表尾的操作可修改如下: s->next=H; s->prior=H->prior; H->prior->next=s; H->prior=s;

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,120
精华内容 20,848
关键字:

双循环问题举例