精华内容
下载资源
问答
  • 链表遍历**

    2015-09-22 08:07:14
    对于一个链表遍历的遍历,我们判断是否到了最后一个位置一般是判断结构体中的next是否为NULL,其实也可以用**指针进行操作。#include #include #include #include using namespace std; typedef struct Node{ ...

    对于一个链表遍历的遍历,我们判断是否到了最后一个位置一般是判断结构体中的next是否为NULL,其实也可以用**指针进行操作。

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    using namespace std;
    typedef struct Node{
        int mx;
        struct Node * next;
    }Node;
    
    int main(){
        Node * pnode, * hnode;
    
        hnode = NULL;
        int T = 10;
        while(T--){
            pnode = (Node *)malloc(sizeof(Node));
            pnode->mx = T;
            pnode->next = NULL;
            pnode->next = hnode;
            hnode = pnode;
        }
        Node ** ppnode;
        ppnode = &hnode;
        while(*ppnode != NULL){
            printf("%p %d\n",*ppnode,(*ppnode)->mx);
            ppnode = &((*ppnode)->next);
        }
    
        return 0;
    }
    
    展开全文
  • 推荐使用链表遍历框架,使用两个指针来遍历链表,cur指针指向当前节点,pre指针指向前一个节点,用代码表示: ListNode prev = null; ListNode curr = head; while (curr != null) { // 进行操作,prev 表示前一个...

    在这里插入图片描述
    来自面向大象编程 ,作者nettee,侵删。
    推荐使用链表遍历框架,使用两个指针来遍历链表,curr指针指向当前节点,prev指针指向前一个节点,用代码表示:
    在这里插入图片描述

    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        // 进行操作,prev 表示前一个结点,curr 表示当前结点
        if (prev == null) {
            // curr 是头结点时的操作
        } else {
            // curr 不是头结点时的操作
        }
        // 两个指针往后走
        prev = curr;
        curr = curr.next;
    }
    

    最终状态curr走到最后的null,prev成为最后一个节点。
    例题思路:
    第一步:套用框架
    这道题实际上就是一个典型的链表的遍历-处理的操作,于是我们套用使用上面所讲的链表遍历框架。要反转链表,实际上就是要反转所有相邻结点之间的指针。那么,整体的代码框架应该是:

    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        // 反转 prev 和 curr 之间的指针
        prev = curr;
        curr = curr.next;
    }
    

    接下来只需要关注每一步如何反转结点之间的指针即可。
    第二步:写好单步操作
    单步操作是“反转prev和curr之间的指针”。这里涉及到指针指向的改变,需要小心指针丢失的问题。在思考的时候,要考虑到和前一步、后一步的链接。
    假设现在遍历到了链表中部的某个节点。链表应该会分成两个部分:prev指针之前的一半链表已经进行了反转;curr之后的一半链表还是原来的顺序。这次循环让curr的指针改为指向prev, 就将当前节点从后一半链表放进了前一半链表。
    而头结点的特殊情况是,全部链表都还未进行反转,即前一半链表为空。显然,curr.next应该置为null。
    将单步操作放入代码框架,我们得到了一份初版的解题代码:

    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        if (prev == null) {
            curr.next = null;
        } else {
            curr.next = prev;
        }
        prev = curr;
        curr = curr.next;
    }
    

    第三步:细节处理
    上面的代码已经基本上比较完整了,但是还存在着明显的错误,那就是存在指针丢失的问题。
    我们使用curr.next=prev来反转指针,但这会覆盖掉curr.next本来存储的值,丢掉这个指针之后,链表后续的节点就访问不到了!
    在这里插入图片描述
    要解决指针丢失的问题也很简单,使用一个临时指针保存 curr 的下一个结点即可。如下图所示:
    在这里插入图片描述
    不过这样一来,我们遍历框架中更新指针的操作也要随之进行微调。框架本来就不是一成不变的,需要根据实际题目灵活调整。
    根据以上两点的细节处理,我们修改得到完整版的代码:

    ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode cnext = curr.next;
            if (prev == null) {
                curr.next = null;
            } else {
                curr.next = prev;
            }
            prev = curr;
            curr = cnext;
        }
        return prev;
    }
    
    展开全文
  • 算法之递归(2)- 链表遍历 在递归(1)中,简单的介绍了递归的思想,并且通过一个例子简单阐述了递归是如何工作的,并且递归的实现是以线性结构来表示的。之所以用线性的,是因为其易于理解;如果使用树结构,将...

    算法之递归(2)- 链表遍历

    在递归(1)中,简单的介绍了递归的思想,并且通过一个例子简单阐述了递归是如何工作的,并且递归的实现是以线性结构来表示的。之所以用线性的,是因为其易于理解;如果使用树结构,将加大对问题的难度,不利于初学者理解递归的思想。

    为什么用递归

    关于为什么用递归,我个人的理解是递归不要违背算法的初衷,即期待传入xxx值,加工后返回xxx值。不要为了递归而递归,容易造成对函数语义的奇异。另外,通过递归,可以让代码更加整洁,短小,精湛,优美。当然,还会存在一定程度的性能损耗;不过,合理的使用,对于那部分的损耗可以忽略不计。

     

    让我们以单链表为例,理解一下递归是如何工作的。

    1. 遍历单链表

    循环

    递归

        

     private void TraveserL(LNode head)
     {
         if (head == null)
             return;
    
         while (head != null)
         {
             Console.WriteLine(p.data);
             p = p.next;
         }
     }


    private
    void TraveserR(LNode head) { if (head == null) return; Console.WriteLine(head.data); TraveserR(head.next); }



     

    对于循环遍历我想不用多说了吧。不过,值得注意的是递归的遍历,先对数据进行打印,然后遍历下一个节点。有趣的是,如果将打印语句放在递归调用的后面,将是一个逆序的打印。

    分析

    假设链表的结构是这样的

    A->B->C->D->E->F

    递归调用时将发生如下情形

    1.在递归调用之前打印(意味着进入函数体的时候打印)

    (1)进入函数 (从左到右读)

    A->

    B->

    C->

    D->

    E->

    F->

    打印A

    打印B

    打印C

    打印D

    打印E

    打印F

     

    输出:A, B, C, D, E, F.

    (2)当函数退出 (从右到左度)

    <-A

    <-B

    <-C

    <-D

    <-E

    <-F

     

    2. 在递归调用之后 (意味着只有退出函数体的时候,才进行打印)

    (1)    进入函数体(从左到右读)

    A->

    B->

    C->

    D->

    E->

    F->

     

    (2)    退出出函数体(从右到左读)

    <-A

    <-B

    <-C

    <-D

    <-E

    <-F

    打印A

    打印B

    打印C

    打印D

    打印E

    打印F

     

    输出:F, E, D, C, B, A

    结论,当操作在递归调用之后进行,那么是从后向前对链表执行操作。这也是栈的特性之一。当然,具体何时决定,取决与程序员自己,是想从头开始顺序操作,还是后到前逆序操作,具体问题具体分析。

    转载于:https://www.cnblogs.com/lucasluo/archive/2012/07/30/2615902.html

    展开全文
  • 在日常内核驱动开发过程中,往往需要遍历内核的某个链表,内核提供了一套完整的双链表机制,使开发者可以在内核私有数据结构中轻松构建双向链表,这里一起学习以下双向链表的构建和遍历方法,具体链表的知识可以参考...

    0x01:链表
    链表是Linux内核中非常重要的数据结构,在日常内核驱动开发过程中,往往需要遍历内核的某个链表,内核提供了一套完整的双链表机制,使开发者可以在内核私有数据结构中轻松构建双向链表,这里一起学习以下双向链表的构建和遍历方法,具体链表的知识可以参考文末链接;

    0x02:双向链表的构建和遍历
    直接给出代码:

    //list.c
    #include <linux/kernel.h>
    #include <linux/init.h>
    #include <linux/module.h>
    
    /* header of list */
    #include <linux/list.h>
    
    /* private structure */
    struct node {
        const char *name;
        struct list_head list;
    };
    
    /* Initialize a group node structure */
    static struct node node0 = { .name = "BiscuitOS_node0", };
    static struct node node1 = { .name = "BiscuitOS_node1", };
    static struct node node2 = { .name = "BiscuitOS_node2", };
    static struct node node3 = { .name = "BiscuitOS_node3", };
    static struct node node4 = { .name = "BiscuitOS_node4", };
    static struct node node5 = { .name = "BiscuitOS_node5", };
    static struct node node6 = { .name = "BiscuitOS_node6", };
    
    /* Declaration and implement a bindirect-list */
    LIST_HEAD(BiscuitOS_list);
    
    static __init int list_entry_init(void)
    {
      struct node *np;
    
      /* add a new entry on special entry */
      list_add_tail(&node0.list, &BiscuitOS_list);
      list_add_tail(&node1.list, &BiscuitOS_list);
      list_add_tail(&node2.list, &BiscuitOS_list);
      list_add_tail(&node3.list, &BiscuitOS_list);
      list_add_tail(&node4.list, &BiscuitOS_list);
      list_add_tail(&node5.list, &BiscuitOS_list);
      list_add_tail(&node6.list, &BiscuitOS_list);
    
      printk("BiscuitOS_list:\n");
      /* Traverser all node on bindirect-list */
      list_for_each_entry(np, &BiscuitOS_list, list)
        printk("%s\n", np->name);
    
      /* get the struct for this entry */
      np = list_entry(BiscuitOS_list.next, struct node, list);
      printk("The entry struct node: %s\n", np->name);
    
      /* get the first element from a list */
      np = list_first_entry(&BiscuitOS_list, struct node, list);
      printk("The first entry struct node: %s\n", np->name);
    
      return -1;
    }
    
    
    static void __exit list_entry_exit(void)
    {
      printk("Bye bye list_entry\n");
    }
    
    module_init(list_entry_init);
    module_exit(list_entry_exit); 
    MODULE_LICENSE("GPL");
    

    Makefile:

    obj-m += list.o
    
    KBUILD_CFLAGS+= -g
    
    all:
    	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
    
    clean:
    	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
    

    0x03:实际效果

    [ 2113.170373] BiscuitOS_list:
    [ 2113.170374] BiscuitOS_node0
    [ 2113.170374] BiscuitOS_node1
    [ 2113.170375] BiscuitOS_node2
    [ 2113.170375] BiscuitOS_node3
    [ 2113.170375] BiscuitOS_node4
    [ 2113.170375] BiscuitOS_node5
    [ 2113.170375] BiscuitOS_node6
    [ 2113.170376] The entry struct node: BiscuitOS_node0
    [ 2113.170376] The first entry struct node: BiscuitOS_node0
    

    0x04:代码分析
    主要代码逻辑为:
    1.建立私有数据结构体 struct node;
    2.初始化数据结构;
    3.声明链表头,用于后续数据访问;
    4.list_for_each_entry()函数遍历双向链表,参数1为私有数据结构类型,参数2为头节点,参数3为struct node list_head;

    参考链接:
    https://biscuitos.github.io/blog/LIST/

    展开全文
  • 链表遍历和反转

    2021-01-19 17:48:29
    建立头结点,逐个遍历,== 将当前node指向next即ok,返回头结点的next 2206. 反转链表
  • 循环链表遍历的猫腻

    千次阅读 2019-03-08 16:44:27
    循环链表 ...循环链表的其它操作同单链表,但对于遍历循环链表就有一些小技巧了。 循环链表遍历 第一种: public static void printList(Node head){ Node cur = head; while(cur....
  • 从键盘输入一个正整数N(1到100),之后输入N个字符并用头插法(先输入的数据在链表的尾部)创建链表,然后遍历链表,最后对链表进行逆置并遍历。 要求: 1)写一个主函数 2)写一个函数创建链表 3)写一个函数...
  • 双指针解决链表遍历

    2020-10-19 11:20:01
    ​ 冷静 集中 专注 努力 算法之路 ​ 这段时间接触链表相关的算法,其中双指针的思想的应用可以说是链表算法中...​ 第一眼看到这个题目的反应,就是遍历先去取得链表的长度,然后再正序去取链表长度-n个节点,这样可.
  • 链表创建和链表遍历算法

    千次阅读 2017-11-27 15:19:25
    //遍历链表 int main( void ) { PNODE pHead = NULL; //等价于 struct Node * pHead=NULL; pHead = create_list(); //创建一个非循环单链表,并将该链表的头结点地址赋给pHead traverse_list(pHead); //...
  • 有向图邻接链表遍历

    2013-05-02 19:58:41
    该资源浅显易懂的讲述了有向图邻接链表的深度优先遍历,对于初学者是非常有帮助的
  • 最近在用java回顾数据结构以及算法的有关知识,那肯定免不了要用链表,然后手写链表的时候发现了一个小问题,底下是我的链表类中的一个添加节点的方法,结果是有问题的 //添加节点 public void add(Node node) { ...
  • 在这里插入代码片 从事程序行业两年,对这些基础的东西没有好好复习,,基础不牢,地动山摇 #include #include “LinkList.h” using namespace std; /* @autor:Hu Pinghui @version:V1.0 @param:LinkList ...
  • 双循环链表遍历

    2015-03-15 22:22:00
    void CPage1::RenWuBL(DWORD base) { DWORD pFirstNode=base; wchar_t *name; char * aa=""; _try { DWORD pNextNode = pFirstNode; while (pFirstNode != *...
  • 链表遍历一次删除倒数第N个节点

    千次阅读 2017-09-13 09:55:59
    Remove Nth Node From End of List 的题目,一开始想这算是easy的题目了,只需要遍历一次,记录n个节点,然后减去倒数的节点数,就得到所要删除的节点。但是没注意题目的只遍历一次。 解决这道题目的主要思路是,...
  • #include using namespace std; struct listNode ...listNode *reverse(listNode* head)//链表翻转 { if(head==NULL)//特殊输入处理 要时刻有记得处理异常输入 return NULL; listNode * p1=he
  • 数据结构与算法——JS实现(链表遍历链表遍历 链表逆置 一些比较基础的数据结构与算法的知识,敲出来巩固巩固。 链表遍历 const arr = [1, 2, 3, 4, 5, 6, 7, 8]; function Node(value) { this.value = value; ...
  • 反转链表有几种方法,在这先介绍一种时间复杂度为O(n)的遍历算法。  反转链表就是让所有节点的链接反向:本指向下一个节点的指针指向上一个节点。因此: 我们首先想到初始化一个当前指针cur指向与head指向相同的...
  • 看内核代码都会发现,内核链表的操作常用的二个宏list_for_each_entry和list_for_each_entry_safe 循序渐进,先从最底层的函数container_of 函数说起,其内核定义如下: 先看offsetof宏,根据优先级的顺序,最...
  • 86. Partition List(以及没有头结点遍历删除节点的思考)
  • 邻接链表遍历

    2020-03-08 10:51:36
    在知道数组的遍历链表遍历之后,邻接链表遍历自然也会了。 构建邻接链表结构并遍历 /** * 链表所需节点 */ public class Node { public int val; public Node next; public Node(int val){ ...
  • 单向链表(一) 结构体、创建链表遍历链表
  • 链表遍历链表

    千次阅读 2019-10-23 19:58:28
    遍历链表 # include # include # include typedef struct AA { int id ; char * name ; char * tel ; struct AA * pNext ; } Node ; int main ( ) { Node a = { 1 , ...
  • 链表的后续遍历相关链接一、基本框架1.1 二叉树遍历方式1.2 链表遍历方式二、典型例题2.1 引例2.2 回文链表 相关链接  labuladong的算法小抄  LeetCode 234. 回文链表 一、基本框架 1.1 二叉树遍历方式 void ...
  • 链表遍历

    2020-10-10 17:16:12
    有n个记录存储在带头结点的双向链表中,利用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。看这里 主体思想 从头结点的下一个结点开始往后遍历,在...
  • 数据结构-链表遍历和链接链表遍历-改进学生录入程序单向链表实现链表的链接 链表遍历-改进学生录入程序 改进单向链表学生成绩录入,添加一个查找函数,再输入结束后通过查找函数来查找用户输入的特定成绩。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,220
精华内容 12,088
关键字:

链表遍历