精华内容
下载资源
问答
  • 双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表。各种链表的简单区别如下:单向链表:基本链表;单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代...
  • 双向循环链表是在双向链表的基础上发展的,双向链表的最后一个节点指向起始节点,起始节点的上一个节点指向最后一个节点,就得到双向循环链表双向循环链表比双向链表具有更多的优势,节点的增加和删除有很多优化的...

    双向循环链表是在双向链表的基础上发展的,双向链表的最后一个节点指向起始节点,起始节点的上一个节点指向最后一个节点,就得到双向循环链表。

    双向循环链表比双向链表具有更多的优势,节点的增加和删除有很多优化的地方,从起点开始不必循环完整个链表就可以增加或删除节点。

    首先定义双向链表的基本类和节点的基本类:

    链表类的操作有几个核心的地方,第一个是判断是否为最后一个节点,通过链表的相关特性,如单向链表最后一个节点的next属性为None、单向循环链表的最后一个节点的next属性等于头部节点;第二个是使用游标来替代节点指向,这个在操作节点的时候需要有时还需要两个游标,但是对于双向节点而言只需要一个游标,通过当前节点的属性可以找到上下节点。

    下面我们添加基本属性方法的逻辑,注意判断是否为最后一个节点的方式是:最后一个节点的下一个节点是否指向头部指向的节点,具体源码如下:

    class Node():

    def __init__(self,item):

    self.item = item #该节点的值

    self.next = None #连接下一个节点的值

    self.prev = None #连接上一个节点的值

    class DoubelCircularLinkedList():

    #"""双向循环列表类"""

    def __init__(self):

    self.head = None

    def is_empty(self):

    return self.head == None

    def length(self):

    if self.is_empty():

    return 0

    else:

    cur = self.head

    num = 0

    while cur.next != self.head:

    cur = cur.next

    num += 1

    return num+1

    def ergotic(self):

    if self.is_empty():

    raise ValueError("ERROR NULL")

    else:

    cur = self.head.next

    print(self.head.item)

    while cur != self.head:

    print(cur.item)

    cur = cur.next

    def add(self,item): #头部增加节点

    node = Node(item)

    if self.is_empty():

    node.next = node

    node.prev = node

    self.head = node

    else:

    node.next = self.head

    node.prev = self.head.prev

    self.head.prev.next = node

    self.head = node

    def append(self,item):

    if self.is_empty():

    self.add(item)

    else:

    node = Node(item)

    self.head.prev.next = node

    node.prev = self.head.prev

    node.next = self.head

    self.head.prev = node

    def insert(self,index,item):

    if index == 0:

    self.add(item)

    elif index > self.length() - 1:

    self.append(item)

    else:

    cur = self.head

    num = 1

    while cur.next != self.head:

    if num == index:

    break

    cur = cur.next

    num += 1

    node = Node(item)

    node.next = cur.next

    cur.next.prev = node

    node.prev = cur

    cur.next = node

    def delet(self,index):

    if self.is_empty():

    raise ValueError("ERROR NULL")

    elif index == 0 and self.length() == 1:

    self.head = None

    elif index == 0 and self.length() > 1:

    self.head.prev.next = self.head.next

    self.head.next.prev = self.head.prev

    self.head = self.head.next

    elif index == self.length() - 1:

    self.head.prev = self.head.prev.prev

    self.head.prev.next = self.head #已经改变了self.head.prev的值

    else:

    cur = self.head

    num = 1

    while cur.next != self.head:

    if num == index:

    break

    cur = cur.next

    num += 1

    cur.next.next.prev = cur

    cur.next = cur.next.next

    只以基本的思路实现基本的方法,对于双向循环链表而言还有很多可以优化的地方,正向遍历和逆向遍历获得结果的时间是不一样的。

    展开全文
  • //空表,头结点的前驱和后继指针均指向了自己,这也是判断双向循环链表是否为空的条件, //双向循环链表具有对称性 //缺点,是要付出空间代价的双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,...

    //双向链表,将头结点和尾结点链接起来,就构成了双向循环链表
    //双向循环链表是将头结点的前驱指针指向了尾结点,同时将尾结点的后劲指针指向了头结点.
    //空表,头结点的前驱和后继指针均指向了自己,这也是判断双向循环链表是否为空的条件,
    //双向循环链表具有对称性
    //缺点,是要付出空间代价的

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

    代码

    #pragma mark 定义结点类型
    typedef int ElemType;
    typedef struct DuLNode
    {
        ElemType data;
        struct DuLNode *prior;//指向前驱结点
        struct DuLNode *next; //指向后继结点
    
    }DuLNode,*DuLinkList;
    
    #pragma mark 带头结点的双向循环链表的基本操作
    
    
    #pragma mark ---1.初始化空的双向循环链表
    void InitList(DuLinkList *L)
    { /* 产生空的双向循环链表L */
        *L=(DuLinkList)malloc(sizeof(DuLNode));
        if(*L){
            (*L)->next=*L;
            (*L)->prior=*L;
        } else
            exit(0);
    }
    
    #pragma mark ---2.销毁双向循环链表
    void DestroyList(DuLinkList L)
    {
        DuLinkList q,p=L->next; /* p指向第一个结点 */
        while(p!=L) /* p没到表头 */
        {
            q=p->next;
            free(p);
            p=q;
        }
        free(L);
        L=NULL;
    }
    
    #pragma mark ---2.将双向循环链表置空
    void ClearList(DuLinkList L) /* 不改变L */
    {
        DuLinkList q,p=L->next; /* p指向第一个结点 */
        while(p!=L) /* p没到表头 */
        {
            q=p->next;
            free(p);
            p=q;
        }
        L->next=L->prior=L; /*头结点的两个指针域均指向自身 */
    }
    #pragma mark ---3 验证表是否为空表
    int ListEmpty(DuLinkList L)
    {
        /* 初始条件:线性表L已存在 */
       if(L->next==L&&L->prior==L)
       return 1;
       else
       return 0;
    
    }
    
    #pragma mark 计算元素的个数
    int ListLength(DuLinkList L)
    { /* 初始条件:L已存在。操作结果: */
        int i=0;
        DuLinkList p=L->next; /* p指向第一个结点 */
        while(p!=L) /* p没到表头 */
        {
            i++;
            p=p->next;
        }
        return i;
    }
    
    #pragma mark 赋值
    Status GetElem(DuLinkList L,int i,ElemType *e)
    { /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
        int j=1; /* j为计数器 */
        DuLinkList p=L->next; /* p指向第一个结点 */
        while(p!=L&&j<i)
        {
            p=p->next;
            j++;
        }
        if(p==L||j>i) /* 第i个元素不存在 */
            return ERROR;
        *e=p->data; /* 取第i个元素 */
        return OK;
    }
    //查找元素前驱
    
    Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
    { /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
        /* 否则操作失败,pre_e无定义 */
        DuLinkList p=L->next->next; /* p指向第2个元素 */
        while(p!=L) /* p没到表头 */
        {
            if(p->data==cur_e)
            {
                *pre_e=p->prior->data;
                return OK;
            }
            p=p->next;
        }
        return ERROR;
    }
    //查找元素后继
    
    Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
    { /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */
        /* 否则操作失败,next_e无定义 */
        DuLinkList p=L->next->next; /* p指向第2个元素 */
        while(p!=L) /* p没到表头 */
        {
            if(p->prior->data==cur_e)
            {
                *next_e=p->data;
                return OK;
            }
            p=p->next;
        }
        return ERROR;
    }
    //查找元素地址
    
    DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */
    { /* 在双向链表L中返回第i个元素的地址。i为0,返回头结点的地址。若第i个元素不存在,*/
        /* 返回NULL */
        int j;
        DuLinkList p=L; /* p指向头结点 */
        if(i<0||i>ListLength(L)) /* i值不合法 */
            return NULL;
        for(j=1;j<=i;j++)
            p=p->next;
        return p;
    }
    //元素的插入
    
    Status ListInsert(DuLinkList L,int i,ElemType e)
    { /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长+1 */
        /* 改进算法2.18,否则无法在第表长+1个结点之前插入元素 */
        DuLinkList p,s;
        if(i<1||i>ListLength(L)+1) /* i值不合法 */
            return ERROR;
        p=GetElemP(L,i-1); /* 在L中确定第i个元素前驱的位置指针p */
        if(!p) /* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱) */
            return ERROR;
        s=(DuLinkList)malloc(sizeof(DuLNode));
        if(!s)
            exit(0);
        s->data=e;
        s->prior=p; /* 在第i-1个元素之后插入 */
        s->next=p->next;
        p->next->prior=s;
        p->next=s;
        return OK;
    }
    
    Status ListDelete(DuLinkList L,int i,ElemType *e)
    { /* 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1≤i≤表长 */
        DuLinkList p;
        if(i<1) /* i值不合法 */
            return ERROR;
        p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */
        if(!p) /* p=NULL,即第i个元素不存在 */
            return ERROR;
        *e=p->data;
        p->prior->next=p->next;
        p->next->prior=p->prior;
        free(p);
        return OK;
    }
    
    
    void visit(ElemType c)
    {
        printf("%d ",c);
    }
    

    调用

    int main(int argc, const char * argv[]) {
        // insert code here...
        DuLinkList L;
        ElemType e;
        int j;
        Status i;
        InitList(&L); /* 初始化单循环链表L */
    
        ListInsert(L, 1, 15);
        ListInsert(L, 2, 25);
        ListInsert(L, 3, 35);
        ListInsert(L, 4, 45);
    
    
        j=ListLength(L);
        printf("L中数据元素个数=%d\n",j);
    
        ListTraverse(L,visit);
    
        PriorElem(L,25,&e); /* 求元素5的前驱 */
        printf("25前面的元素的值为%d。\n",e);
        NextElem(L,35,&e); /* 求元素3的后继 */
        printf("35后面的元素的值为%d。\n",e);
        printf("L是否空 %d(1:空 0:否)\n",ListEmpty(L));
    
    
        //删除第二个元素
        ListDelete(L, 2, &e);
        j=ListLength(L);
        printf("L中数据元素个数=%d\n",j);
        ListTraverse(L,visit);
        return 0;
    }
    

    运行结果
    这里写图片描述

    10.总结一下线性表的顺序实现和链试实现的比较
    比较两者的时间性能和空间性能进行比较
    1.位置查找运算 顺序表示随机存取,时间复杂度为O(1),单链表需要对表元素进行扫描,它的时间复杂度为O(n)
    2.定位运算 基本操作是比较 ,两者均为O(n)
    3.插入,删除运算 在顺序表和链表中,都需要进行定位.
    顺序表,其基本操作是元素的比较和结点的移动,平均时间复杂度为O(n).
    单链表,基本操作是元素的比较,尽管不需要移动,其平均时间复杂度依然为O(n).

    各有优缺点,具体问题,具体分析

    单链表的每个结点包括数据域和指针域,指针域需要占用额外的空间

    从整体考虑,顺序表需要提前分配空间,如果分配过大,造成浪费,分配过小,内存溢出;单链表不需要预先分配空间,只要内存空间没有耗尽.单链表的结点就没有限制

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

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

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

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

      当链表为空的时候,哨兵的前驱和后继都是其自身。(以上内容总结自《算法导论》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

    展开全文
  • C++双向循环链表实现

    2015-12-15 00:39:00
    双向循环链表C++实现 1.单链表: 结构图: 2.双向链表: 3.双向循环链表: 对于本程序中,则是给定一个_head 头结点,而不是指针,因为这样更加方便避免一些空判断问题 /* 版权信息:狼 文件...

    双向循环链表C++实现

     

    1.单链表:

    结构图:

    2.双向链表:

    3.双向循环链表:

    对于本程序中,则是给定一个_head  头结点,而不是指针,因为这样更加方便避免一些空判断问题

     

    /*
    版权信息:狼
    文件名称:BidCirList.h
    文件标识:
    文件摘要:
        利用C++实现简单的双向链表功能。增,删,查,改
        //太烦了。。我直接给个 带头结点的  表
        //swap 移花接木已经是个给力的方法。。just try
    当前版本:1.1
    作    者:狼
    完成时间:2015-12-13
    
    */
    #ifndef _BIDCIRLIST_H
    #define _BIDCIRLIST_H
    
    #include"afxstd.h"
    
    typedef int DataType;
    typedef struct ListNode
    {
        ListNode(DataType x=0)
        : _data(x)
        //默认初始化是自环而非  NULL
        , _prev(this)
        , _late(this)
        {}
    
        DataType _data;
        struct ListNode* _prev;
        struct ListNode* _late;
    }ListNode;
    
    class BidCirList
    {
    public:
        BidCirList()
            :_head(0)
        {}
    
        BidCirList(DataType *array, size_t n = 0)
            :_head(0)
        {
            size_t i = 0;
            while (n--)
            {
                InsertAter(array[i++]);
            }
        }
    
        BidCirList(BidCirList & list)
            :_head()
        {
            ListNode* cur = list._head._prev;
            while (cur)
            {
                InsertAter(cur->_data);
                cur = cur->_prev;
                if (cur == &list._head)
                    break;
            }
        }
    
        ~BidCirList()
        {
            Destoty();
        }
        
        BidCirList operator+(BidCirList& list)
        {
            BidCirList tmp(*this);
            ListNode* cur = list._head._prev;
    
            while (cur != &list._head)
            {
                tmp.InsertAter(cur->_data);
                cur = cur->_prev;
            }
            return tmp;
        }
    
        BidCirList& operator = (BidCirList& list)
        {
            if (this != &list)
            {
                BidCirList S(list);
    
                Swap(S);
            }
            return *this;
        }
    
        //清空空间
        void Destoty()
        {
            ListNode*cur = &_head;
            while (cur->_prev != &_head)
            {
                DelPrev();
            }
        }
    
        //删除结点之前的结点。默认为头
        void DelPrev(ListNode *del = NULL)
        {
            if (_head._prev == &_head)
                return;
            if (del == NULL)
            {
                //删除头之前
                _head._prev = _head._prev->_prev;
                delete _head._prev->_late;
    
                _head._prev->_late = &_head;
            }
            else
            {
                del->_prev = del->_prev->_prev;
                delete del->_prev->_late;
    
                del->_prev->_late = del;
            }
        }
    
        //删除结点之后一个,,默认为头
        void DelLate(ListNode *del = NULL)
        {
            if (_head._prev == &_head)
                return;
            if (del == NULL)
            {
                _head._late = _head._late->_late;
                delete _head._late->_prev;
    
                _head._late->_prev = &_head;
            }
            else
            {
                del->_late = del->_late->_late;
                delete del->_late->_prev;
    
                del->_late->_prev = del;
            }
        }
    
        //在结点之前插入,默认为头
        void InsertAter(DataType x ,ListNode* ins= NULL)
        {
            ListNode* tmp = new ListNode(x);
    
            if (ins == NULL)
            {
                tmp->_prev = &_head;
                tmp->_late = _head._late;
    
                tmp->_late->_prev = tmp;
                tmp->_prev->_late = tmp;
            }
            else
            {
                tmp->_prev = ins;
                tmp->_late = ins->_late;
    
                tmp->_late->_prev = tmp;
                tmp->_prev->_late = tmp;
            }
        }
    
        ListNode* Find(DataType x)
        {
            ListNode* cur = _head._prev;
            while (cur)
            {
                if (cur == &_head)
                    return NULL;
                if (cur->_data == x)
                {
                    return cur;
                }
                cur = cur->_prev;
            }
        }
    
        void Erase(ListNode * node)
        {
            if (node == &_head)
            {
                return;
            }
            else
            {
                ListNode* tmp = node;
                node->_prev->_late = node->_late;
                node->_late->_prev = node->_prev;
                delete tmp;
                tmp = NULL;
            }
        }
    
        //反向打印
        void PrintPrev()
        {
            ListNode* cur = _head._prev;
            while (cur)
            {
                if (cur == &_head)
                    break;
                cout << cur->_data << " -> ";
                cur = cur->_prev;
            }
            cout << " Over! " << endl;
        }
        //正向打印
        void PrintLate()
        {
            ListNode* cur = _head._late;
    
            while (cur)
            {
                if (cur == &_head)
                    break;
                cout << cur->_data << " -> ";
                cur = cur->_late;
            }
            cout << " Over! " << endl;
        }
    
        void Swap(BidCirList &list)
        {
            ::swap(_head._prev->_late, list._head._prev->_late);
            ::swap(_head._prev, list._head._prev);
    
            ::swap(_head._late->_prev, list._head._late->_prev);
            ::swap(_head._late, list._head._late);
    
        }
        
    private:
        ListNode _head;
    };
    
    #endif

     

    转载于:https://www.cnblogs.com/lang5230/p/5046960.html

    展开全文
  • java链表之--双向循环链表

    千次阅读 2016-07-06 16:01:16
    为了克服这种缺点,有了双向链表----继而为了更加高效-----双向循环链表 此外引用不知哪位大神的一句话:判断数据结构使用 如果你要把数据集合看成一个环,可以顺时针走,也可以逆时针走,那你就可以用双向...
  • 双向循环链表题目思想实验结果完整源代码 题目 建立一个带头结点的双向循环链表, 赋值,判断是否对称,写出算法计算时间复杂度 思想 travel the Link ;遍历链表 put values into a array ;赋值给一个数组 compare...
  • 双向循环链表定义 双向循环链表(Double Cycle Linked List)是双向链表的一种更复杂的变形,头结点的上一节点链接域指向尾结点,而尾结点的下一节点链接域指向头节点。 节点示意图 表元素域elem用来存放具体的...
  • 编写出判断带头结点的双向循环链表L是否对称相等的算法#include using namespace std; typedef int ElemType; typedef struct DNode{ ElemType data; struct DNode *prior; struct DNode *next; }DLinkList; ...
  • 1.循环链表:首尾相连的链表。 2.单循环链表:在单链表中,如果最后一个结点的链域值不是NULL,而是指向头结点,则...5.判断双向循环链表为空的条件:头结点的前驱和后继指针均指向了自己。 6.算法package com.bocl
  • C语言 双向循环链表,增删查改,判断回文,排序,论文,代码,自写可用,vs2013,课程设计,答辩
  • 用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
  • 双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表。各种链表的简单区别如下:单向链表:基本链表; 单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当...
  • 线性表(List) 阜向循环链表一元多项式 双向循环链表 小结和作业 题讲解 单向循环链表 定义:最后一个结点的指针不是空指针,而 是指向了头结点 逻辑形态 L 单向循环链表 差异 1判断空表的条件 L->next==NULL变为L->...
  • 一般来说, 链表我们用的最多的是不带头单向链表 和 带头双向循环链表。 所谓带头与不带头的区别在于头结点是否存储数据。 1、带头意味着头结点不会真正存放结点信息, 一般存放一些记账信息(例如链表多长等) 2、...
  • 循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在是判断p->next是否为头结点。除此之外,还有多重链的循环链表——将表中结点链在多个环上。 判断空链表的条件是 head==head...
  • 用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
  • 1. 简介一种更复杂的链表是“双向链表”或“双面链表”。... 操作is_empty()判断链表是否为空length()返回链表的长度travel()遍历add(elem)在头部添加一个节点append(elem)在尾部添加一个节点insert(pos,ele...
  • 四、双向循环链表的实现 template <class T> class CycDulList{ public: CycDulList():head_(nullptr),size_(0){} ~CycDulList(); //获取链表大小 size_t size(){return size_;} //判断链表是否为空 ...
  • package datastruct.... * 不用单向循环链表 * 不仅要在最后维护first和last * 还要注意linkBefore和unLink中的非空判断 */ public class HtqCircleLinkedList<E> { private static class Node<E>{
  • 改了这个函数,在主函数中create_node后要判断是否成功,不成功就提示并退出函数,退出前别忘了还要释放链表! 同时create_link这个函数中也要判断head是否申请成功,不成功的话同样提示并退出函数。 #include &...
  • 线性表之链式存储结构 双向循环链表 基本操作: 初始化 __init__ 线性表空判断 empty 清空线性表 clear 获取元素 get 是否存在数据 exist 插入操作 insert 删除操作 delete 线性表的长度 length 扩展操作 ...
  • 简介:在双向链表中,我们可以通过任意一个结点访问到其前驱元素和后继元素,时间复杂度为O(1),所以双向链表是十分方便的,我们通常构建链表也会选择去构建双向链表。 单个节点包括两个指针: 空表的判断体条件是L...
  • 循环链表双向链表

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

    2017-10-10 19:13:37
    循环链表与顺序链表之间的区别:循环链表最后一个数据的next指针域不为空,而是指向头结点,其他基本操作大体相同,只是在判断表结束的条件变为判断节点的引用域是否为头引用 双向链表 /** * @author NeoSong ...
  • 双向链表的构建在内存分配时就已经做好了工作,并且多出一节末端用来判断数据,有效的预防了比如CString容器类不好判断的问题。 3.链表方法类 通过此类建立内存分配、迭代器、与链表类的关联,简单而且灵活。 ...
  • 双向链表: 1、为了方便编程,以及节点的插入删除,可以在首尾增加一个空节点,方便一系列的操作和判断,最后一个节点指针指向空数据的节点或者指向空。 2、双向链表在访问元素时,可以从任何结点开始...3、循环链表
  • C语言全面描述双向循环链表的基本操作,代码逻辑清楚,注释详细。 基本操作包含了对双向循环链表: *1.节点的设计 *2.链表的初始化 *3.判断空表 *4.创建节点 *5.插入节点 *6.删除节点 *7.移动节点 *8.查找节点 *9....

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 317
精华内容 126
关键字:

判断双向循环链表