双向链表 订阅
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 展开全文
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
信息
类    别
链表
特    点
每个数据结点中都有两个指针
方    法
正序查找,逆序查找
中文名
双向链表
亦    称
双链表
应    用
孔子电路
双向链表链表的操作
线性表的双向链表存储结构:带头结点的双向循环链表的基本操作:销毁双向循环链表L:重置链表为空表:验证是否为空表 [1]  :
收起全文
精华内容
下载资源
问答
  • 双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表双向链表...
  • 双向链表

    万次阅读 2019-12-08 21:39:42
    双向链表 1.创建一个双向链表的结构体,里面有两个指针,可以指向前后两个相邻的节点 /*! *\brief 双向链表节点结构体 */ typedef struct list_node { struct list_node* next; struct list_node* previous; }...

    双向链表

    在这里插入图片描述

    1.创建一个双向链表的结构体,里面有两个指针,可以指向前后两个相邻的节点

    /*!
     *\brief    双向链表节点结构体
     */
    typedef struct list_node
    {
    	struct list_node* next;         
    	struct list_node* previous;
    }list_item_t;
    

    2.双向链表初始化

    /*!
     * \brief    双向链表初始化
     *
     * \param    链表头节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_init(list_item_t* list_head)
    {
    	list_head->next      = list_head;
    	list_head->previous  = list_head;
    }
    

    3.双向链表插入一个节点

    /*!
     * \brief    双向链表在一个节点后面插入一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_insert_after(list_item_t* l, list_item_t* n)
    {
    	l->next->previous = n;
    	n->next = l->next;
    
    	l->next = n;
    	n->previous = l;
    }
    
    
    
    
    /*!
     * \brief    双向链表在一个节点前面插入一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_insert_before(list_item_t* l, list_item_t* n)
    {
    	l->previous->next = n;
    	n->previous = l->previous;
    
    	l->previous = n;
    	n->next = l;
    }
    

    4.删除一个节点

    /*!
     * \brief    双向链表删除一个节点
     *
     * \param    链表节点
     *
     * \return   无
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    void list_remove(list_item_t* l)
    {
    	l->previous->next = l->next;
    	l->next->previous = l->previous;
    
    	l->next = l->previous = l;
    }
    

    5.其他函数

    
    /*!
     * \brief    检查双向链表是否为空
     *
     * \param    链表节点
     *
     * \return   1:空   0:非空
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    uint8_t list_isempty(list_item_t* l)
    {
    	return (uint8_t)(l->next ==  l);
    }
    
    /*!
     * \brief    获取双向链表长度
     *
     * \param    链表节点
     *
     * \return   长度
     *
     * \note     无
     *
     * \see      
     *
     * \date     2019/12/08 16:57
     */
    uint32_t list_getlen(list_item_t* l)
    {
    	uint32_t len = 0;
    	const list_item_t* p = l;
    
    	while (p->next != l)
    	{
    		p = p->next;
    		len++;
    	}
    	return len;
    }
    

    双向链表的使用

    双向链表的函数不多,其他应用都是在上面的几个函数的基础上增加的。
    常用的用法有两种,第一种就是改变双向链表结构体,里面增加数据等其他的功能,然后在此基础上操作

    /*!
     *\brief    双向链表节点结构体
     */
    typedef struct list_node
    {
    	struct list_node* next;         
    	struct list_node* previous;
    	uint32_t data;
    }list_item_t;
    

    另一种是直接用上面的双链表函数,重新根据需要构造新的数据结构,比如构造一个学生数据结构体,将双链表当作一个钩子。

    typedef struct student
    {
    	list_item_t  list;
    	uint32_t     grade;
    	char name[20];
    	float score;
    }student_t;
    

    但是这样的话,可以通过学生结构体中的list变量,链接到上下两个学生结构体的list成员,但是我们需要操作的是学生变量,因此我们需要根据结构体的list成员地址,求出学生结构体的地址(这个是linux/rtt系统中常用的操作)。

    /**
     * 根据list的地址 获取结构体的基地址
     */
    #define rt_container_of(ptr, type, member) \
        ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
    

    创建100个学生数据结构

    uint8_t grade_init(student_t* head, uint32_t num)
    {
    	student_t* pstudent;
    
    	list_init(&head->list); //初始化头节点
    	head->score = (float)num;
    	head->grade = 0;
    	memset(head->name, 0, offsetof(student_t, score) - offsetof(student_t, name));
    
    	while (num--)
    	{
    		pstudent = (student_t*)malloc(sizeof(student_t));
    		
    		if (pstudent == NULL)
    		{
    			return 1; //分配内存失败
    		}
    		list_insert_after(&head->list, &pstudent->list);
    		pstudent->score = 0;
    		pstudent->grade = 0;
    		memset(pstudent->name, 0, offsetof(student_t, score) - offsetof(student_t, name));
    		
    	}
    	return 0;
    }
    
    int main(void)
    {
    	printf("hello world!\n");
    
    	student_t * student_head = (student_t *)malloc(sizeof(student_t));
    
    	uint8_t err = grade_init(student_head, 100);
    	if (err != 0)
    	{
    		printf("初始化失败\n");
    	}
    	
        /*  通过钩子链表访问上下节点 */
    	student_t * student_head3 = rt_container_of(student_head->list.next->next->next, student_t, list);
    
    	student_head3->score = 18.756;
    /* vs 使用strcpy 需要屏蔽警告 */
    #pragma warning(disable : 4996)
    	strcpy(student_head3->name, "张三");
    
    
    	while (1)
    	{
    
    	}
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,912
精华内容 13,564
关键字:

双向链表