精华内容
下载资源
问答
  • 一步一步写算法(之双向链表

    万次阅读 多人点赞 2011-10-07 20:03:53
    那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:  (1)在数据结构中具有双向指针  (2)插入数据的时候需要考虑前后的方向的...

    【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】


        前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:

        (1)在数据结构中具有双向指针

        (2)插入数据的时候需要考虑前后的方向的操作

        (3)同样,删除数据的是有也需要考虑前后方向的操作

        那么,一个非循环的双向链表操作应该是怎么样的呢?我们可以自己尝试一下:

        (1)定义双向链表的基本结构

    typedef struct _DOUBLE_LINK_NODE
    {
    	int data;
    	struct _DOUBLE_LINK_NODE* prev;
    	struct _DOUBLE_LINK_NODE* next;
    }DOUBLE_LINK_NODE;
        (2)创建双向链表节点
    DOUBLE_LINK_NODE* create_double_link_node(int value)
    {
    	DOUBLE_LINK_NODE* pDLinkNode = NULL;
    	pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
    	assert(NULL != pDLinkNode);
    
    	memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
    	pDLinkNode->data = value;
    	return pDLinkNode;
    }
        (3)删除双向链表

    void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
    {
    	DOUBLE_LINK_NODE* pNode;
    	if(NULL == *pDLinkNode)
    		return ;
    
    	pNode = *pDLinkNode;
    	*pDLinkNode = pNode->next;
    	free(pNode);
    	delete_all_double_link_node(pDLinkNode);
    }
    
        (4)在双向链表中查找数据

    DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)
    {
    	DOUBLE_LINK_NODE* pNode = NULL;
    	if(NULL == pDLinkNode)
    		return NULL;
    
    	pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
    	while(NULL != pNode){
    		if(data == pNode->data)
    			return pNode;
    		pNode = pNode ->next;
    	}
    	
    	return NULL;
    }
        (5)双向链表中插入数据

    STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
    {
    	DOUBLE_LINK_NODE* pNode;
    	DOUBLE_LINK_NODE* pIndex;
    
    	if(NULL == ppDLinkNode)
    		return FALSE;
    
    	if(NULL == *ppDLinkNode){
    		pNode = create_double_link_node(data);
    	    assert(NULL != pNode);
    		*ppDLinkNode = pNode;
    		(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
    		return TRUE;
    	}
    
    	if(NULL != find_data_in_double_link(*ppDLinkNode, data))
    		return FALSE;
    
    	pNode = create_double_link_node(data);
    	assert(NULL != pNode);
    
    	pIndex = *ppDLinkNode;
    	while(NULL != pIndex->next)
    		pIndex = pIndex->next;
    
    	pNode->prev = pIndex;
    	pNode->next = pIndex->next;
    	pIndex->next = pNode;
    	return TRUE;
    }
        (6)双向链表中删除数据

    STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
    {
    	DOUBLE_LINK_NODE* pNode;
    	if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
    		return FALSE;
    
    	pNode = find_data_in_double_link(*ppDLinkNode, data);
    	if(NULL == pNode)
    		return FALSE;
    
    	if(pNode == *ppDLinkNode){
    		if(NULL == (*ppDLinkNode)->next){
    			*ppDLinkNode = NULL;
    		}else{
    			*ppDLinkNode = pNode->next;
    			(*ppDLinkNode)->prev = NULL;
    		}
    
    	}else{
    		if(pNode->next)
    		    pNode->next->prev = pNode->prev;
    	    pNode->prev->next = pNode->next;
    	}
    
    	free(pNode);
    	return TRUE;
    }
        (7)统计双向链表中数据的个数

    int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)
    {
    	int count = 0;
    	DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
    
    	while(NULL != pNode){
    		count ++;
    		pNode = pNode->next;
    	}
    	return count;
    }
        (8)打印双向链表中数据

    void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)
    {
    	DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
    
    	while(NULL != pNode){
    		printf("%d\n", pNode->data);
    		pNode = pNode ->next;
    	}
    }
        注意:

            今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?


    【预告: 下面我们讨论的是循环单向链表】


    展开全文
  • 本文将会根据c#从双链表的特点、用途、实现来介绍双向链表。本人属于“懒散型”不逼到最后就不会去总结的人,实在是遇到双向链表问题较为频繁,错失众多机会,今在这不得不总结一下,让自己去更好的了解一下。(看到...

    本文将会根据c#从双链表的特点、用途、实现来介绍双向链表。本人属于“懒散型”不逼到最后就不会去总结的人,实在是遇到双向链表问题较为频繁,错失众多机会,今在这不得不总结一下,让自己去更好的了解一下。(看到一句话挺好的:Technology is all!)

    首先要知道的是:当我们碰见一个新的东西要去了解一下它是用来解决哪个问题的,才会能更好的理解好使用它。

    链表的特点:一组任意储存单元来存储线性表的数据元素,每个数据元素不仅储存本身信息之外还需要储存指向另一个数据元素的信息。双向链表即数据元素除了储存自身信息外还储存指向上一个数据元素和下一个数据元素的两个信息。

    链表的用途:所有的数据容器无非就是用来储存和管理需要的数据,即数据的增、删、改、查。双向链表的存在就是为了解决顺序表增删的耗费性能,单链表查询耗性能的问题。(由于链表申请的内存在堆中且位置是任意的,因此在增删时不必像顺序表一样需要依次移动后续元素。双向链表的数据元素储存了指向它的前驱元素和后继元素信息,因此查询时不必像单链表一样只能从头节点开始查询)

    双向链表的实现:除了c#封装好的链表,自己去实现一个链表会对它有更好的理解。

    using System;
    //using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 双向链表
    {
        class Program
        {
            public static LinkList<int> intlist = new LinkList<int>();
            static void Main(string[] args)
            {
                intlist.AddData(1);
                intlist.AddData(2);
                intlist.AddData(3);
    
                Console.WriteLine(intlist.GetNode(1).Data);
                intlist.Append(1,4);
                Console.ReadKey();
            }
        }
    
        //双向链表的节点类  //里面存放数据信息和  指向 前驱数据元素和后继元素的信息  指针
        public class LinkListNode<T>
        {
            public T Data;//储存的信息
            public LinkListNode<T> Next;//指向后继的指针
            public LinkListNode<T> Prev;//指向前驱的指针
    
            public LinkListNode(T date)
            {
                this.Data = date;
            }
    
            ///构造函数
            public LinkListNode(T data, LinkListNode<T> next, LinkListNode<T> prev)
            {
                this.Data = data;
                this.Next = next;
                this.Prev = prev;
            }
        }
    
        //双向链表操作  //链表的 增 删 改 查
        public class LinkList<T>
        {
            public readonly LinkListNode<T> LinkHead;//链表的表头 声明链表就是声明一个表头初始化表头
            public int Size;
            public LinkList()
            {
                //default关键字  类型的默认值 引用类型 null  int类型 0  bool类型 false
                LinkHead = new LinkListNode<T>(default(T), null, null);
                LinkHead.Next = LinkHead;
                LinkHead.Prev = LinkHead;
                Size = 0;
            }
    
            public bool IsEmpty() => (Size == 0);
            public int GetSize() => (Size);
    
            //添加数据元素
            public void AddData(T t)
            {
                LinkListNode<T> node = new LinkListNode<T>(t);
                if (Size.Equals(0))
                {
                    LinkHead.Next = node;
                    LinkHead.Prev = node;
                    node.Prev = LinkHead;
                    node.Next = LinkHead;
                }
                else
                {
                    node.Next = LinkHead;
                    node.Prev = LinkHead.Prev;
                    LinkHead.Prev = node;
                    LinkHead.Prev.Prev.Next = node;
                }
    
                Size++;
            }
    
            //通过下表查找数据元素(节点)
            public LinkListNode<T> GetNode(int index)
            {
                if (index < 0 || index >= Size)
                {
                    throw new IndexOutOfRangeException("下标有错");
                }
                //正向查找
                LinkListNode<T> node = LinkHead;
                if (index < Size / 2)
                {
                    for (int i = 0; i < Size / 2; i++)
                    {
                        node = node.Next;
                    }
                }
                if (index >= Size / 2)
                {
                    for (int i = 0; i < Size - index; i++)
                    {
                        node = node.Prev;
                    }
                }
                return node;
            }
    
            //在index下标插入数据元素t
            public void Append(int index, T t)
            {
                LinkListNode<T> node = new LinkListNode<T>(t);
                LinkListNode<T> node1 ;
                if (index < 0 || index >= Size)
    
                {
                    throw new IndexOutOfRangeException("下标有错");
                }
                else
                {
                    node1 = GetNode(index);
                    node.Next = node1;
                    node.Prev = node1.Prev;
                    node1.Prev.Next = node;
                    node1.Prev = node;
    
                    Size++;
                }
            }
    
            //删除下表index的数据元素
            public void Delete(int index)
            {
                LinkListNode<T> node = GetNode(index);
                node.Prev.Next = node.Next;
                node.Next.Prev = node.Prev;
                Size--;
            }
    
            //改变下标的值
            public void ChangeDate(int index, T t)
            {
                LinkListNode<T> node = GetNode(index);
                node.Data = t;
            }
    
        }
    }
    

     

    展开全文
  • 通用双向链表,指的是通过一个通用的数据结构,然后添加特定数据形成有具体用途的链表。这主要涉及到代码复用,在C++中实现非常方便,只需要定义一个双向链表的类,每一个具体业务只需要继承它,然后添加自己的数据...

    通用双向链表,指的是通过一个通用的数据结构,然后添加特定数据形成有具体用途的链表。这主要涉及到代码复用,在C++中实现非常方便,只需要定义一个双向链表的类,每一个具体业务只需要继承它,然后添加自己的数据成员即可。但有时候我们需要用C语言而不是C++,那么该如何实现这种层次关系呢?

    首先我们来看两个宏。

    第一个是offsetof(可参考Linux内核代码include/linux/Stddef.h):

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    这个宏什么意思呢,它返回MEMBER成员在结构体TYPE中的偏移量,下面举个例子说明,假设有个结构体A如下:

    struct struct_A
    {
        int a[2];
        int b;
    }

    其中,成员a相对于结构的偏移量为0,成员b相对于结构体的偏移量为8;结构体struct_A的变量m在内存中地址结构如下图所示:

    内存示意图

    对地址0取b成员,然后再取地址,减去结构体首地址就是偏移量,由于首地址是0,故这个结果就是偏移量8。

    第二个宏是container_of(可参考Linux内核代码include/linux/Kernel.h):

    #define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) );})

    这个宏先把ptr指针转化为char指针,这样指针移动操作单位为字节;然后减去其在结构体中的偏移量,就能回到ptr所在的结构体的开头,即得到了结构体指针,最后强制转换成目标类型指针,就得到了ptr指针所在结构体变量的首地址,即得到一个type结构体指针。

    接着进入正文。

    我们已经得到从结构体某一成员地址反推结构体指针的办法,就可以通过把“通用数据结构”作为结构体成员的办法,来构建一个带业务功能的双向链表,而不是一般思路中的链表中包含数据的方法。

    假设一个双向链表如下:

    struct list_head
    {
        struct list_head *next, *prev;
    };

    然后我们创建一个雇员信息结构:

    struct employee
    {
        char name[32];
        int age;
        struct list_head *listnode;
    };

    创建雇员信息节点时,需要初始化雇员信息结构,然后在链表中添加一个节点,最后把雇员信息结构中的链表指针指向新添加的链表节点,这样就完成了雇员列表的创建。
    当需要取一个雇员信息时,首先确定链表节点,然后通过container_of宏取得雇员信息。比如以下代码:

    struct list_head *ptr_node = NULL;
    struct employee *emp_info = NULL;
    …
    ptr_node = x;
    emp_info = container_of(ptr_node, struct employee, listnode);
    展开全文
  • 数组模拟双向链表

    2020-02-27 10:01:00
    用途:多次删除插入操作 准备:l[N],r[N];分别记录该数的左右 操作1.连接两个元素 eg.连接u,v l[v] = u; r[u] = v; 小技巧:虚拟位置0的使用 插入第一个元素1,则r[0] = 1;l[1] = 0; 操作2.插入元素 1.将v插在u的...

    用途:多次删除插入操作

    准备:l[N],r[N];分别记录该数的左右

    操作1.连接两个元素

    eg.连接u,v

    l[v] = u;
    r[u] = v;

    小技巧:虚拟位置0的使用

    插入第一个元素1,则r[0] = 1;l[1] = 0;

     

    操作2.插入元素

    1.将v插在u的右侧

    2.将v插在u的左侧

    //将v插在u的右侧
    r[v] = r[u];
    l[v] = u;
    l[r[u]] = v;
    r[u] = v;
    
    //将v插在u的左侧
    r[v] = u;
    l[v] = l[u];
    r[l[u]] = v;
    l[u] = v;
    

      

    操作3.删除元素

    l[u] u r[u]//删除元素u
    
    l[r[u]] = l[u];
    r[l[u]] = r[u];
    l[u] = r[u] = 0;

      

    操作4.遍历数组

    for(int i = r[0]; i; i = r[i]){
        /*输出以及其他操作*/
    }
    

      

    例题:洛谷P1160

    展开全文
  • 三大数据结构的实现方式 数据结构 实现方式 ...双向链表 数组与链表实现方式的比较 数组与链表都很快 如果能精确预测栈或者队列所需要容纳的数据量 --- 数组 如果不能...
  • 【 声明:版权所有,转载请标明出处,请勿用于商业用途。 联系信箱:libin493073668@sina.com】 前言: 动态单链表,静态单链表,循环单链表,不知不觉中我们已经学了这么多链表了,但是这几个链表都是...
  • 【 声明:版权所有,转载请标明出处,请勿用于商业用途。 联系信箱:libin493073668@sina.com】 题目链接:...
  • Linux内核源码分析-链表代码分析分析人:余旭分析时间:2005年11月17日星期四 11:40:10 AM雨 温度:10-11度编号:1-4 类别:准备工作Email:yuxu9710108@163.com时代背景:开始在www.linuxforum.net Linux内核技术...
  • Linux内核源码分析-链表代码分析 分析人:余旭 分析时间:2005年11月17日星期四 11:40:10 AM 雨 温度:10-11度 编号:1-4 类别:准备工作 Email:yuxu9710108@163.com 时代背景:开始在www.linuxforum.net Linux内核...
  • 链表应该是继数组之后...接下来本篇博文会讲解到单链表,双端链表,有序链表,双向链表,和有迭代器的链表。(迭代器是用来随机访问链表元素的一种方法)链表的实现一般需要用到两个类,链表对象(包含对第一个链表节...
  • 原文也可见:链表 - 数据结构在实际项目中的使用 - Jiajun的编程随想链表的实际用途非常广泛,但是一般...链表根据结构通常分为单向链表和双向链表,因为链表中总是有一个地方存储下 一个节点的位置,因此我们抽象来...
  • JAVA数据结构之链表

    2019-10-09 00:42:09
    链表应该是继数组之后应用最广的通用存储结构... 接下来本篇博文会讲解到单链表,双端链表,有序链表,双向链表,和有迭代器的链表。(迭代器是用来随机访问链表元素的一种方法)  链表的实现一般需要用到两个类...
  • Redis数据结构之链表

    2018-06-03 16:38:00
    Redis使用的链表双向无环链表,链表节点可用于保存各种不同类型的值。 一、链表结构定义1. 链表节点结构定义: 2. 链表结构定义: 示例: 二、链表在Redis中的用途1. 作为列表键的底层实现之一:当...
  • 目录一、链表两种双向链表模板0.指针1.数组AcWing 136. 邻值查找1.平衡树2.链表3.线段树二、邻接表 声明: 本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记,主要是因为我...
  • 终于讲到书中的最后一个链表了,前面我们一步一步的介绍了顺序表,单链表,静态单链表,循环链表,双向链表,这次总算是进入了最后的链表学习了,那就是带头结点的线性链表,按照书本所说,这个是比前面几个更具有...
  • 本文源码下载 〇、声明 ...本文的链表双向链表,不光存储下一个节点的指针,还存储上一个节点的指针,也就是除了能找到当前节点的下一个节点,还能反向找到上一个节点。 泛型的基本原理就是利用...
  • list容器

    2020-09-23 19:49:37
    list容器介绍用途头文件以及构造方法插入数据以及遍历list函数插入从末端插入元素[push_back()]从头部插入元素[push_front()]获取头部元素[front()]与尾部元素...list容器与双向链表 用途 快速插入删除 头文件以及构
  • container     堆操作/双向链表/环形链表 context      上下文类型 crypto      常用的密码(算法) database/sql   数据库接口 encoding     数据编码 errors       创建错误函数 expvar ...
  • 一步一步写算法(之排序二叉树)

    万次阅读 多人点赞 2011-10-10 21:26:20
    【 声明:版权所有,欢迎转载,请勿用于商业... 前面我们讲过双向链表的数据结构。每一个循环节点有两个指针,一个指向前面一个节点,一个指向后继节点,这样所有的节点像一颗颗珍珠一样被一根线穿在了一起。然而今天
  • 双向链表,有前驱和后驱指针 有头尾指针 无环的 维护了一个len表示链表长度 比较简单就详细讲了。 二、字典 保存键值对的抽象数据结构。哈希键的底层实现之一就是字典,集合也会使用到字典结构。 如: set name ...
  • 我的伟大航路(8)

    2020-01-29 21:25:57
    今天学了循环链表、双向链表、循环双向链表,以及昨天的栈和队列 栈 栈是一种后进先出的结构,对于栈的用处我一直有疑惑,但是我思考以后,想,栈的用途与它的特点是离不开的,后进先出的特点,优再先进去的数,...
  • 本文档的Copyleft归yfydz所有,使用GPL发布,可以自由拷贝,转载,转载时请保持文档的完整性,严禁用于任何商业用途。msn: yfydz_no1@hotmail.com来源:... 2. 双向链表(list) linux内核中的双向链表通过结
  • 本文档的Copyleft归yfydz所有,使用GPL发布,可以自由拷贝,转载,转载时请保持文档的完整性,严禁用于任何商业用途。 msn: yfydz_no1@hotmail.com 来源:... 2. 双向链表(list) linux内核中的双向链表通过结构 s
  • 本文档的Copyleft归yfydz所有,使用GPL发布,可以自由拷贝,转载,转载时请保持文档的完整性,严禁用于任何商业用途。msn: yfydz_no1@hotmail.com来源... 2. 双向链表(list) linux内核中的双向链表通过结构 struct l

空空如也

空空如也

1 2 3 4
收藏数 70
精华内容 28
热门标签
关键字:

双向链表用途