精华内容
下载资源
问答
  • 前面写了 线性表的链式存储方式中的存储结构就是链表的形式,主要以单链表的形式写了相关的操作,这篇文章写一下循环链表...但是在循环链表中,没有指针域为空的结点,所以不能以指针域为空作为判断是否时终端结点的依

    目录

    循环链表

    单循环链表

    空表

    单循环链表判断终端结点

    单循环链表的优点

    单循环链表合并——尾指针操作

    双循环链表


    前面写了 线性表的链式存储方式中的存储结构就是链表的形式,分别以单链表和双链表的写了相关的操作,这篇文章写一下循环链表。

    循环链表

    循环链表是一种头尾相接的链表结构,链表中最后一个结点的指针域指向头节点,是整个链表成为一个环。循环链表又分单循环链表双循环链表

    单循环链表

    空表

    与单链表不同,循环链表的空表只有data 域是空,指针域是指向自己的。

    单循环链表判断终端结点

    在单链表中,可以根据结点的指针域为空判断该结点时最后一个结点即终端结点。但是在循环链表中,没有指针域为空的结点,所以不能以指针域为空作为判断是否时终端结点的依据。

    在循环链表中,根据结点指针域是否等于头节点来判断该结点是否是最后一个结点,对应的判断一个结点是否为空的依据也是结点是否等于头节点。

    单循环链表的优点

    从表中的任意结点出发,均可找到表中其他的结点。

    单循环链表合并——尾指针操作

    在单链表中,结点操作都是以头指针在链表首元结点开始操作的。而在循环链表中,如果仍然使用头指针,那么对于终端结点元素的操作和单链表一样 会存在时间复杂度是O(n)的问题。

    在循环链表中,使用尾指针进行首尾结点操作会更加方便,如:两个循环链表的合并操作,该算法的时间复杂度是 O(1)

    双循环链表

    和单循环链表类似,双向链表对应的也有双循环链表。

    展开全文
  • 文章目录双向链表构建双向链表判断链表是否为空(与单链表同)链表长度遍历添加元素:头插法添加元素:尾插法添加元素:指定位置删除节点查找节点是否存在单向循环链表构建单向循环链表判断链表是否为空链表长度遍历...

    双向链表

    格式

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

    构建双向链表

    #coding:utf-8
    class Node(object):
        '''节点'''
        def __init__(self,item):
            self.elem=item
            self.next=None
            self.prev=None
    class DoubleLinkList(object):
        '''双链表'''
        def __init__(self,node=None):
            self.__head=node
    

    判断链表是否为空(与单链表同)

        def is_empty(self):
            '''链表是否为空'''
            return self.__head is None
    

    链表长度

        def length(self):
            '''链表长度'''
            # cur游标,用来移动遍历节点
            cur = self.__head
            # count记录数量
            count = 0#一定要设置为0,满足空链表特殊情况
            while cur != None:
                count += 1
                cur = cur.next
            return count
    

    遍历

        def travel(self):
            '''遍历整个列表'''
            cur=self.__head
            while cur!=None:
                print(cur.elem,end=" ")
                cur=cur.next
            print()
    

    添加元素:头插法

        def add(self,item):
            '''链表头部添加元素,头插法'''
            node=Node(item)
            node.next=self.__head
            self.__head.prev=node
            self.__head=node  #"="右边是被指向的
            #或先self.__head=node,再node.next.prev=node
    

    在这里插入图片描述

    添加元素:尾插法

        def append(self,item):
            '''链表尾部添加元素,尾插法'''
            node=Node(item)
            if self.is_empty():
                self.__head=node
            else:
                cur = self.__head
                while cur.next != None:
                    cur = cur.next
                cur.next = node
                node.prev=cur
    

    添加元素:指定位置

        def insert(self,pos,item):
            '''指定位置添加元素
            pos从0开始索引'''
            if pos<=0:
                self.add(item)
            elif pos>(self.length()-1):
                self.append(item)
            else:
                cur = self.__head
                count = 0
                while count < (pos-1):
                    count += 1
                    cur = cur.next
                    # 当循环退出后,pre指向pos-1位置
                node = Node(item)
                node.next = cur
                node.prev = cur.prev
                cur.prev.next=node
                cur.prev=node
    

    在这里插入图片描述

    删除节点

        def remove(self,item):
            '''删除节点'''
            cur=self.__head
            while cur!=None:
                if cur.elem==item:
                    #先判断此节点是否是头节点
                    #头节点
                    if cur==self.__head:
                        self.__head=cur.next
                        if cur.next:
                            #判断链表是否只有一个节点
                            cur.next.prev = None
                    else:
                        cur.prev.next=cur.next
                        if cur.next:
                            cur.next.prev = cur.prev
                    break
                else:
                    cur=cur.next
    
    

    在这里插入图片描述

    查找节点是否存在

        def search(self,item):
            '''查找节点是否存在'''
            cur=self.__head
            while cur !=None:
                if cur.elem == item:
                    return True
                else:
                    cur = cur.next
            return False
    

    单向循环链表

    单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。
    在这里插入图片描述

    构建单向循环链表

    #coding:utf-8
    class Node(object):
        '''节点'''
        def __init__(self,elem):
            self.elem = elem
            self.next = None
    
    
    class SingleCycleLinkList(object):
        '''单向循环链表'''
        def __init__(self,node=None):
            self.__head=node
            if node:
                node.next = node
    
    

    判断链表是否为空

        def is_empty(self):
            '''链表是否为空'''
            return self.__head==None
    

    链表长度

        def length(self):
            '''链表长度'''
            if self.is_empty():
                return 0
            # cur游标,用来移动遍历节点
            cur = self.__head
            # count记录数量
            count = 1 #count从1开始,因为不像单链表一样判断cur在None停;而是cur.next
            while cur.next!= self.__head:
                count += 1
                cur = cur.next
            return count
    

    遍历整个列表

        def travel(self):
            '''遍历整个列表'''
            if self.is_empty():
                return
            cur=self.__head
            while cur.next!=self.__head:
                print(cur.elem,end=" ")
                cur=cur.next
            #退出循环,cur指向尾节点,但尾节点的元素未打印,下一句代码打印
            print(cur.elem)
    

    添加元素:头插法

        def add(self,item):
            '''链表头部添加元素,头插法'''
            node=Node(item)
            if self.is_empty():
                self.__head=node
                node.next=node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环,cur指向尾节点
                node.next = self.__head
                self.__head = node
                # cur.next=node   与下一句代码等价
                cur.next = self.__head
    

    在这里插入图片描述

    添加元素:尾插法

        def append(self,item):
            '''链表尾部添加元素,尾插法'''
            node=Node(item)
            if self.is_empty():
                self.__head=node
                node.next=node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                    #node.next=cur.next  与下一句代码等价
                node.next=self.__head
                cur.next=node
    

    在这里插入图片描述

    添加元素:指定位置添加元素

        def insert(self,pos,item):
            '''指定位置添加元素
            pos从0开始索引'''
            if pos<=0:
                self.add(item)
            elif pos>(self.length()-1):
                self.append(item)
            else:
                pre = self.__head
                count = 0
                while count < (pos-1):
                    count += 1
                    pre = pre.next
                    # 当循环退出后,pre指向pos-1位置
                node = Node(item)
                node.next = pre.next
                pre.next = node
    

    删除元素

        def remove(self,item):
            '''删除节点'''
            if self.is_empty():
                return
            cur=self.__head
            pre=None
            while cur.next!=self.__head:
                if cur.elem==item:
                    #先判断此节点是否是头节点
                    if cur==self.__head:
                        # 头节点的情况
                        #找尾节点
                        rear=self.__head
                        while rear.next!=self.__head:
                            rear=rear.next
                        self.__head=cur.next
                        rear.next=self.__head
                    else:
                        #中间节点
                        pre.next=cur.next
                    return
                else:
                    pre=cur
                    cur=cur.next
            #退出循环,cur指向尾节点
            if cur.elem==item:
                if cur==self.__head:
                #链表只有一个节点
                    self.__head=None
                else:
                    pre.next=cur.next
    

    查找元素

        def search(self,item):
            '''查找节点是否存在'''
            if self.is_empty():
                return False
            cur=self.__head
            while cur.next!=self.__head:
                if cur.elem == item:
                    return True
                else:
                    cur = cur.next
            #退出循环,cur指向尾节点
            if cur.elem==item:
                return True
            return False
    
    
    展开全文
  • 对于普通的双向循环链表,因为同其他节点相比,头尾元素是特别的,需要特别处理,所以在插入和删除节点的时候需要判断边界条件,这会让代码显得臃肿。头节点的特殊之处在于它的前驱是指针,尾节点的特殊之处在于它...
    • 思路分析

      对于普通的双向循环链表,因为同其他节点相比,头尾元素是特别的,需要特别处理,所以在插入和删除节点的时候需要判断边界条件,这会让代码显得臃肿。头节点的特殊之处在于它的前驱是空指针,尾节点的特殊之处在于它的后继节点是空指针。

      如果能令头尾元素不再特别,就可以省去边界条件的处理了。那么问题来了,如何让他们不特殊呢?那就需要让每个元素的前驱和后继都不为空。自然会想到在头元素之前,尾元素之后分别添加一个无意义的节点,使得他们的前驱和后继不空。

      如此一来,一个空的链表从初始化就有了两个无意义的节点。然后你会发现,这里有了数据冗余,两个无意义的节点其实可以省略掉一个,让头尾节点都与同一个哨兵节点相连,到此,就形成了一个有哨兵的双向循环链表。哨兵的作用是可以降低运行时间中的常数因子。

      当链表为空的时候,哨兵的前驱和后继都是其自身。(以上内容总结自《算法导论》10.2例题)下面附上一个简单的C++实现。

    struct Node
    {
        Node* pPrev;    //前驱节点
        Node* pNext;    //后继节点
        int   key;        //当前节点的键值
    };
    
    class DoubleLinkedList
    {
    public:
        DoubleLinkedList();
        ~DoubleLinkedList();
    
        Node* Search(int key);    //查找键值为key的节点,若没有找到返回空指针
        void Insert(int key);                    //在头部插入一个键值为key的节点
        void Delete(Node* p);                    //删除节点p
    private:
        Node m_sentinel;
    };
    
    DoubleLinkedList::DoubleLinkedList()
    {
        m_sentinel.pPrev = &m_sentinel;    //初始化时链表为空,哨兵的前驱和后继都指向其自身。
        m_sentinel.pNext = &m_sentinel;
    }
    
    DoubleLinkedList::~DoubleLinkedList()
    {
        Node* pCurrent = m_sentinel.pNext;
        Node* pNext = nullptr;
        while(pCurrent != &m_sentinel)
        {
            pNext = pCurrent->pNext;
            delete pCurrent;    //循环的每一步负责删除当前节点,并将pCurrent指向下一个节点,直到回到哨兵为止。
            pCurrent = pNext;
        }
    }
    
    Node* DoubleLinkedList::Search(int key)   //运行时间为O(n)
    {
        Node* pCurrent = m_sentinel.pNext;
        while(pCurrent != &m_sentinel && pCurrent->key != key)
            pCurrent = pCurrent->pNext;
        return pCurrent == &m_sentinel ? nullptr : pCurrent;
    }
    
    void DoubleLinkedList::Insert(int key)     //运行时间为O(1)
    {
        Node* pNew = new Node;                //构建新节点
        pNew->key = key;
        pNew->pPrev = &m_sentinel;             //新节点与前驱后继相互关联
        pNew->pNext = m_sentinel.pNext;
        m_sentinel.pNext->pPrev = pNew;
        m_sentinel.pNext = pNew;
    }
    
    void DoubleLinkedList::Delete(Node* p)    //运行时间为O(n)
    {
        p->pPrev->pNext = p->pNext;    //将自身的前驱和后继相互关联
        p->pNext->pPrev = p->pPrev;
        delete p;                                     //删除自身
    }
    
    • 优化方法

      Search方法的每一次循环都需要两步测试pCurrent != &m_sentinel 和 pCurrent->key != key,能不能省略前一个,只留下pCurrent->key != key?
      我们可以利用哨兵的键值,让其等于要找的key,这样一来,即使链表里没有找到key,也会在pCurrent回到哨兵的时候及时跳出循环。优化后的Search方法是这样的:

    Node* DoubleLinkedList::Search(int key)
    {
        Node* pCurrent = m_sentinel.pNext;
        m_sentinel.key = key;
        while(pCurrent->key != key)
            pCurrent = pCurrent->pNext;
        return pCurrent == &m_sentinel ? nullptr : pCurrent;
    }
    • 带哨兵的单向循环链表
    struct Node    //与双向链表不同的是,每个节点只保存一个后继节点
    {
        Node* pNext;
        int key;
    };
    
    class SingleLinkedList
    {
    public:
        SingleLinkedList();
        ~SingleLinkedList();
        Node* Search(int key);    //Search和Insert方法的运行时间与双向链表一样,Search依然是O(n)
        void Insert(int key);        //Insert 依然是 O(1)
        void Delete(Node* p);       //但是Delete有所不同,因为删除过程需要拿到待删除元素的前驱和后继,其中前驱节点必须通过一次遍历查找得到,所以Delete的运行时间和Search一样,都是O(n)
    private:
        Node m_sentinel;
    };
    
    SingleLinkedList::SingleLinkedList()
    {
        m_sentinel.pNext = &m_sentinel;
    }
    
    SingleLinkedList::~SingleLinkedList()
    {
        Node* pCurrent = m_sentinel.pNext;
        Node* pNext = nullptr;
        while(pCurrent != &m_sentinel)
        {
            pNext = pCurrent->pNext;
            delete pCurrent;
            pCurrent = pNext;
        }
    }
    
    Node* SingleLinkedList::Search(int key)
    {
        m_sentinel.key = key;
        Node* pCurrent = m_sentinel.pNext;
        while(pCurrent->key != key)
            pCurrent = pCurrent->pNext;
        return pCurrent == &m_sentinel ? nullptr : pCurrent;
    }
    
    void SingleLinkedList::Insert(int key)
    {
        Node* pNew = new Node;
        pNew->pNext = m_sentinel.pNext;
        pNew->key = key;
        m_sentinel.pNext = pNew;
    }
    
    void SingleLinkedList::Delete(Node* p)
    {
        Node* pCurrent = m_sentinel.pNext;
        Node* pPrevious = &m_sentinel;
        while(pCurrent != p)
        {
            pPrevious = pCurrent;
            pCurrent = pCurrent->pNext;
        }
        pPrevious->pNext = pCurrent->pNext;
        delete pCurrent;
    }
    • 将双向和单向链表加以对比,我们发现在插入和查找频繁,而删除不频繁的场景下,使用单向链表可以节省空间,而在需要频繁删除的场景下,使用双向链表,可以显著节省运行时间。

    转载于:https://www.cnblogs.com/meixiaogua/p/9677957.html

    展开全文
  • 循环链表双向链表

    2016-04-19 22:16:52
    其实循环链表和单链表的主要差异在于循环的判断条件上,原来是判断p->next是否为空,现在则是判断p->next是否等于头结点,则表示循环结束 改造单链表,不用头指针,而是用指向终端结点的尾指针来表示循环链表,此时...

    单链表:

    将单链表中的终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾想接的单链表称为单循环链表,简称循环链表。其实循环链表和单链表的主要差异在于循环的判断条件上,原来是判断p->next是否为空,现在则是判断p->next是否等于头结点,则表示循环结束

    改造单链表,不用头指针,而是用指向终端结点的尾指针来表示循环链表,此时查找结束结点和头结点都很方便。

    将两个循环链表合并在一起的时候,有尾指针就显得简单很多

    p=rearA->next;

    rearA->next=rearB->next->next;

    q=rearB->next;

    rearB->next=p;

    delete(q)

    双链表:

    双向链表是在单链表的每一个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱

    展开全文
  • 循环链表,双向链表

    2017-10-10 19:13:37
    循环链表与顺序链表之间的区别:循环链表最后一个数据的next指针域不为空,而是指向头结点,其他基本操作大体相同,只是在判断表结束的条件变为判断节点的引用域是否为头引用 双向链表 /** * @author NeoSong ...
  • 循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在是判断p->next是否为头结点。除此之外,还有多重链的循环链表——将表中结点链在多个环上。 判断空链表的条件是 head==head...
  • 1. 简介一种更复杂的链表是“双向链表”或“双面链表”。... 操作is_empty()判断链表是否为空length()返回链表的长度travel()遍历add(elem)在头部添加一个节点append(elem)在尾部添加一个节点insert(pos,ele...
  • 循环链表/双向链表

    2018-10-17 23:09:07
    is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item) 在尾部添加一个节点 insert(pos, item) 在指定位置pos添加节点 remove(item) 删除...
  • 这里使用python实现单,链表。作为简单链表的改进,操作和链表大致相同 单循环链表 """ @author: LSY123 @file: maina.py @time: 2020/02/13 @desc: 单项循环链表 单链表的...# •is_empty() 判断链表是否为空 # ...
  • 双向循环链表定义 双向循环链表(Double Cycle Linked List)是双向链表的一种更复杂的变形,头结点的上一节点链接域指向尾结点,而尾结点的下一...is_empty() 判断链表是否为空 length 链表长度 travel() 遍历整个链
  • 线性表(List) 阜向循环链表一元多项式 双向循环链表 小结和作业 题讲解 单向循环链表 定义:最后一个结点的指针不是指针,而 是指向了头结点 逻辑形态 L 单向循环链表 差异 1判断空表的条件 L->next==NULL变为L->...
  • 四、双向循环链表的实现 template <class T> class CycDulList{ public: CycDulList():head_(nullptr),size_(0){} ~CycDulList(); //获取链表大小 ... //判断链表是否为空 bool em...
  • 一般来说, 链表我们用的最多的是不带头单向链表 和 带头双向循环链表。 所谓带头与不带头的区别在于头结点是否存储数据。 1、带头意味着头结点... (置为nullptr的话,方便插入元素的时候判断头结点是否为空。) 双向
  • 判断表是否为空,如果为空则返回true,不空返回false. 给出表中数据元素的个数。 给定一个索引(位置),返回指向该位置的数据元素的指针,如果给定的位置号不合法,则返回空指针。 给定数据元素x,如果表中有该元素...
  • 1.循环链表:首尾相连的链表。 2.单循环链表:在单链表中,如果最后一个结点的链域值不是NULL,而是指向头结点,则...5.判断双向循环链表为空的条件:头结点的前驱和后继指针均指向了自己。 6.算法package com.bocl
  • 数据结构之循环链表和双向链表 1.循环链表 循环链表是另一种形式的链式存储结构,其特点是单链表的最后一个结点的指针不为空,而是指向头结点(带头结点的...对于单循环链表而言,判断链表是否为空不再是panda头...
  • 判断表是否为空,如果为空则返回true,不空返回false. 给出表中数据元素的个数。 给定一个索引(位置),返回指向该位置的数据元素的指针,如果给定的位置号不合法,则返回空指针。 给定数据元素x,如果表中有该...
  • 循环链表前言一、循环单链表的初始化二、判断是否为空或表尾结点三、循环链表的初始化四、循环链表的插入与删除 前言 对于循环单链表而言,在进行插入和删除时,可以让指针指向尾部,对于表头(通过尾部找到头部...
  • 通用C 双向 循环 链表 一.用法详解: 链表节点struct list_head { struct list_head *prev; struct list_head *next; };...自定义一个链表节点,并初始化:struct list_head list... 判断链表是否为空:list_empty(&list
  • 循环链表 将单链表中终端结点的指针端由 NULL 改 指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。...循环链表和单链表的主要差异就在于循环的条件判断上,原来是 ...
  • 单链表和循环链表的唯一区别就是尾结点的指针值,所以循环判断时,由原来的是否为空,现在则是是否为头结点,则循环结束。 1.2.2 实现 与单链表实现类似,修改循环判断条件即可。可参考:https://www.cnb...
  • 将单链表中终端节点的指针端由指针改指向头结点,就使得整个单链表形成一个环,这种头尾相接的单循环链表简称单循环链表 注:并不是说循环链表一定要有头结点 循环链表的单链表的主要差距就在于循环的判断空...
  • //空表,头结点的前驱和后继指针均指向了自己,这也是判断双向循环链表是否为空的条件, //双向循环链表具有对称性 //缺点,是要付出空间代价的双向链表也叫链表,是链表的一种,它的每个数据结点中都有两个指针,...
  • 其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。 所以插入删除什么的都是一样的 循环链表的合并 代码部分 // 保存A 和B ...
  • 文章目录链表定义初始化链表和判断是否为空向后插入元素前向插入元素删除后继节点q销毁链表遍历节点循环链表循环单链表初始化和判断是否为空循环链表初始化和判空向后插入和删除小小总结静态链表初始化判空...
  • 如何判断一个链表是否为空

    万次阅读 2018-05-07 22:24:19
    L指向表头结点的指针,分别写出带有头结点的单链表、单项循环链表和双向循环链表的条件单链表 NULL==L-&gt;next单向循环 L==L-&gt;next双向循环 L==L-&gt;next&amp;&amp;L==L-&gt;...
  • 与单链表区别,原来判断p->next是否为空,现在判断p->next不等于头结点则循环结束不用头指针,使用指向终端节点的尾指针表示循环链表 将两个循环链表合并成一个:p=rearA->next;//保存A头结点 rearA->next = ...
  • 文章目录前言1. 循环双链表2. 基本操作3....2. 基本操作操作名称操作说明InsertInHead(val_list)头插法创建循环双链表InsertInTail(val_list)尾插法创建循环双链表IsEmpty()判断循环双链表是否为空LengthL...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 184
精华内容 73
关键字:

双循环链表判断为空