精华内容
下载资源
问答
  • 双向循环链表

    2019-05-25 21:24:01
    /* 双向循环链表 1:双向循环链表创建 2:双向循环链表长度 3:双向循环链表正向遍历 ... 8:双向循环链表判空 9:双向循环链表排序 10:双向循环链表销毁 */ #include <iostream> u...

    /*
    双向循环链表
        1:双向循环链表创建
        2:双向循环链表长度
        3:双向循环链表正向遍历
        4:双向循环链表反向遍历
        5:双向循环链表节点插入
        6:双向循环链表节点删除
        7:双向循环链表倒序
        8:双向循环链表判空
        9:双向循环链表排序
        10:双向循环链表销毁
    */

    #include <iostream>
    using namespace std;
    typedef struct node{
        struct node *pFront;
        int value;
        struct node *pNext;
    }DCList;
    /*创建双向循环链表*/
    void Create(DCList* &Head,DCList* &End,int &nodecount )
    {
        if(nodecount <=0)  return ;
        DCList *node = NULL;
        int nodevalue = 0;
        for(int i=0;i<nodecount;i++){
            cin>>nodevalue;
            node = new DCList;
            node->value = nodevalue;
            node->pFront = node;
            node->pNext = node;
            if(Head == NULL){
                Head = node;
            }
            else{
                node->pNext = Head;
                End->pNext = node;
                node->pNext->pFront = node;
                node->pFront = End;
            }
            End = node;
        }
    }
    /*获取双向链表的长度*/
    void Length(DCList* &Head,DCList* &End,int &length)
    {
        length = 1;
        DCList* ptr= Head;
        while(ptr != End){
            length++;
            ptr = ptr->pNext;
        }
    }
    /*双向链表正向遍历*/
    void Traval(DCList* &Head,DCList* &End)
    {
        if(Head == NULL || End == NULL)  return ;
        DCList *ptr = Head;
        while(ptr != End){
            cout<<ptr->value<<" ";
            ptr= ptr->pNext;
        }
        cout<<End->value<<endl;
    }
    /*双线循环链表的反向遍历*/
    void ReTraval(DCList* &Head,DCList* &End){
        if(Head == NULL || End == NULL)  return ;
        DCList * ptr= End;
        while(ptr != Head){
            cout<<ptr->value<<" ";
            ptr=ptr->pFront;
        }
        cout<<Head->value<<endl;
    }
    /*双向循环链表节点插入*/
    void Insert(DCList* &Head,DCList* &End,int &InsertPos,int InsertValue)
    {
        if((Head == NULL || End == NULL) && InsertPos != 1)  return ;
        int length =0 ;
        Length(Head,End,length);
        if(InsertPos <=0 && InsertPos > length+1)  return ;
        DCList *insertnode = NULL;
        insertnode = new DCList;
        insertnode->value = InsertValue;
        int insertpos =1;
        DCList* insertfront = End;
        DCList* insertnext = Head;
        while(insertpos != InsertPos){
            insertfront = insertfront->pNext;
            insertnext =  insertfront->pNext;
            insertpos++;
        }
        insertnode->pNext = insertnext;
        insertnode->pNext->pFront = insertnode;
        insertfront->pNext = insertnode;
        insertfront->pNext->pFront = insertfront;
        if(InsertPos == 1){
            Head = insertnode;
        }
        else if(InsertPos == length+1){
            End = insertnode;
        }
    }
    /*双向循环链表节点删除*/
    void Del(DCList* &Head,DCList* &End,int &DelPos)
    {
        if(Head == NULL || End == NULL)  return ;
        int length =0;
        Length(Head,End,length);
        if(DelPos <= 0 || DelPos > length) return ;
        DCList * delfront = End;
        DCList * delnext =Head->pNext;
        int delpos = 1;
        while(delpos != DelPos){
            delfront = delfront->pNext;
            delnext = delnext->pNext;
            delpos++;
        }
        DCList *ptr = delfront->pNext;
        delfront->pNext = delnext;
        delnext->pFront = delfront;
        delete ptr ;
        ptr = NULL;
        if(DelPos == 1){
            Head = delnext;
        }
        else if(DelPos == length){
            End = delfront;
        }
    }
    /*双向循环链表倒序*/
    void Reverse(DCList* &Head, DCList* &End)
    {
        if(Head == NULL || End == NULL)  return ;
        DCList* Head_New = NULL;
        DCList* End_New = NULL;
        DCList *ptr = End;
        DCList *ptr_front = NULL;
        while(ptr != Head){
            ptr_front = ptr->pFront ;
            ptr->pFront = ptr;
            ptr->pNext = ptr;
            if(Head_New == NULL){
                Head_New = ptr;
            }
            else{
                ptr->pNext = Head_New;
                End_New->pNext = ptr;
                ptr->pNext->pFront = ptr;
                ptr->pFront = End_New;
            }
            End_New = ptr;
            ptr = ptr_front;
        }
        Head->pNext = Head_New;
        Head->pFront = End_New;
        Head_New->pFront = Head;
        End_New->pNext = Head;
        End_New = Head;
        Head = Head_New;
        End = End_New;
    }
    /*双向循环链表排序*/
    void Sort(DCList* &Head,DCList* &End)
    {
        if(Head == NULL || End == NULL)  return ;
        DCList *node = NULL;
        DCList* node_next = NULL;
        DCList* node_front = NULL;
        DCList* tmp = NULL;
        int length = 0;
        Length(Head,End,length);
        int nflag =0;
        for(int i=0;i<length;i++){
            nflag = 0;
            node = Head;
            node_next = node->pNext;
            node_front = Head;
            for(int j=0;j<length-i-1;j++){
                if(node->value > node_next->value){
                    node->pNext = node_next->pNext;
                    node->pNext->pFront = node;
                    node_next->pNext = node;
                    node_next->pNext->pFront = node_next;
                    if(node != Head){
                        node_front->pNext = node_next;    
                        node_next->pFront = node_front;
                    }
                    if(node == Head){
                        Head = node_next;
                        node_next->pFront = NULL;
                    }
                    if(node_next == End){
                        End = node;
                    }
                    tmp = node;
                    node = node_next;
                    node_next = tmp;
                    nflag = j+1;
                }
                node_front = node;
                node = node->pNext;
                node_next = node->pNext;
            }
            if(nflag == 0){
                break;
            }
            i = length-nflag-1;
        }
    }
    /*双向链表销毁*/
    void Destroy(DCList* &Head,DCList* &End){
        if(Head == NULL || End == NULL)        return ;
        DCList * ptr = Head;
        DCList* ptr_next = NULL;
        while(ptr != End){
            ptr_next = ptr->pNext;
            delete ptr ;
            ptr = NULL;
            ptr = ptr_next;
        }
        delete End ;
        End = NULL;
        Head = NULL;
    }
    /*双向链表判空*/
    bool m_is_empty(DCList* &Head,DCList* &End)
    {
        if(Head == NULL || End == NULL)  
            return true;
        else 
            return false;
    }
    int main(){
        int length,nodecount,insertpos,insertvalue,delpos;
        DCList *Head = NULL ,*End = NULL;
        /*创建双循环链表*/
        cin>> nodecount;
        Create(Head,End,nodecount);
        Traval(Head,End);
        ReTraval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        //cout<<End->pNext->value<<" "<<Head->pFront->value<<endl;
        /*双向循环链表节点插入*/
        cin>> insertpos >> insertvalue;
        Insert(Head,End,insertpos,insertvalue);
        Traval(Head,End);
        ReTraval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*双向循环链表节点删除*/
        cin>> delpos ;
        Del(Head,End,delpos);
        Traval(Head,End);
        ReTraval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*双向链表倒序*/
        Reverse(Head,End);
        Traval(Head,End);
        ReTraval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*双向循环链表排序*/
        Sort(Head,End);
        Traval(Head,End);
        ReTraval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*双向循环链表判空*/
        bool m_empty = m_is_empty(Head,End);
        if(m_empty ){
            cout<<"is_empty"<<endl;
        }
        else{
            cout<<"is_not_empty"<<endl;
        }
        Destroy(Head,End);
        m_empty = m_is_empty(Head,End);
        if(m_empty ){
            cout<<"is_empty"<<endl;
        }
        else{
            cout<<"is_not_empty"<<endl;
        }
        system("pause");
        return 0;
    }

    展开全文
  • 实现双向循环链表的创建新节点,初始化,销毁,增加,删除,查找,求长度以及判空等基本操作。 头文件 List.h #pragma once #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;...

    实现双向循环链表的创建新节点,初始化,销毁,增加,删除,查找,求长度以及判空等基本操作。

    头文件 List.h

    #pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    typedef int LTDataType;
    
    //双向循环带头链表
    typedef struct ListNode
    {
    	struct ListNode* _next;  //后继
    	struct ListNode* _prev;  //前驱
    	LTDataType _data;   //数据域
    }ListNode;
    typedef struct List
    {
    	struct ListNode* _head;
    	struct ListNode* _tail;
    	int _size;
    }List;
    void ListInit(List* lt);
    void ListDestory(List* lt);
    void ListPushBack(List* lt, LTDataType x);
    void ListPushFront(List* lt, LTDataType x);
    void ListPopBack(List* lt,ListNode* pos,LTDataType x);
    void ListPopFront(List* lt, ListNode* pos, LTDataType x);
    ListNode* BuyListNode(LTDataType x);
    ListNode* ListFind(List* lt, LTDataType x);
    void ListInsert(ListNode* pos, LTDataType x);
    void ListErase(List* lt,ListNode* pos,LTDataType x);
    int ListSize(List* lt);
    int ListEmpty(List* lt);
    void ListPrint(List* lt);
    void testListNode();

     

    test.c

    1.创建新节点

    #include "List.h"
    ListNode* BuyListNode(LTDataType x)
    {
    	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    	if (newnode != NULL)
    	{
    		newnode->_data = x;
    		newnode ->_prev = NULL;
    		newnode->_next = NULL;
    	}
    	return newnode;
    }

    2.链表初始化

    void ListInit(List* lt)
    {
    	assert(lt != NULL);
    	lt->_head= BuyListNode(0);
    	lt->_head->_next = lt->_head;
    	lt->_head->_prev = lt->_head;
    }

    3.链表销毁

    void ListDestory(List* lt)
    {
    	ListNode* cur = NULL;
    	ListNode* tail=NULL;
    	assert(lt!= NULL);
    		cur = lt;
    		while (cur!=tail)
    		{
    			ListNode* del = cur;
    			cur = cur->_next;
    			free(del);
    			del = NULL;
    		}
    		free(cur);
    }

    4.在链表中插入数据 注:因为是双向循环链表在任何地方插入都是一样的实现。

    void ListInsert(ListNode* pos, LTDataType x) //pos之前插入  prev newnode pos
    {
    	assert(pos != NULL);
    	ListNode* newnode;
    	newnode = BuyListNode(3);
    	newnode->_data = x;
    	ListNode* prev = pos->_prev;
    	prev->_next = newnode;
    	newnode->_prev = prev;
    	newnode->_next = pos;
    	pos->_prev = newnode;
    }
    void ListPushBack(List* lt, LTDataType x)// tail newnode head
    {
    	ListInsert(lt->_head, x);
    }
    void ListPushFront(List* lt, LTDataType x) // tail newnode head
    {
    	ListInsert(lt->_head, x);
    }

    5.查找链表中指定位置元素

    ListNode* ListFind(List* lt, LTDataType x)
    {
    	int i = 0;
    	while (lt != NULL && lt->_head->_data != x)//寻找值为x的元素**注意这里循环的条件不能写反。原因,当L == NULL 时候 L->data会出错
    	{
    		i++;
    		lt = lt->_head->_next;
    	}
    	if (lt == NULL)               //如果没找到返回-1
    		return -1;
    	else
    		return x;
    }

    6.删除指定位置元素

    void ListErase(List* lt,ListNode* pos,LTDataType x)
    {
    	if (lt == NULL && pos < 1)
    	{
    		return;
    	}
    	if (pos>ListSize(lt))
    	{
    		return;
    	}
    	ListNode *pNode = lt;
    	int count = 0;
    	while (count < ListSize(lt))
    	{
    		pNode = pNode->_next;
    		count++;
    	}
    	if (count != pos)
    		return;
    	x = pNode->_data;
    	pNode->_prev->_next = pNode->_next;
    	pNode->_next->_prev = pNode->_prev;
    	free(pNode);
    	pNode = NULL;
    
    }
    void ListPopBack(List* lt, ListNode* pos, LTDataType x) // tail head
    {
    	assert(lt != NULL);
    	ListErase(lt->_head, pos, x);
    }
    void ListPopFront(List* lt, ListNode* pos, LTDataType x)
    {
    	assert(lt != NULL);
    	ListErase(lt->_head, pos, x);
    }

    7.求链表长度

    int ListSize(List* lt)
    {
    	int size = 0;
    	assert(lt != NULL);
    	if (lt->_head!=lt->_head->_prev)
    	{
    		++size;
    		lt->_head = lt->_head->_next;
    	}
    	return size;
    }

    9.判断链表是否为空

    int ListEmpty(List* lt)
    {
    	if (ListSize(lt) == 0 && lt->_head->_next == lt->_head->_prev)
    		return 1;
    	else
    		return 0;
    }

    10.打印链表

    void ListPrint(List* lt)
    {
    	ListNode* cur = lt->_head->_next;
    	while (cur != lt->_head)
    	{
    		printf("%d ", cur->_data);
    		cur = cur->_next;
    	}
    	printf("\n");
    }

    主函数

    void testListNode()
    {
    	ListNode* s;
    	ListInit(&s);
    	ListPushBack(&s, 1);
    	ListPushBack(&s, 2);
    	ListPushBack(&s, 3);
    	ListPushBack(&s, 4);
    	ListPrint(&s);
    	int ret = ListFind(&s, 3);
    	if (ret != -1)
    	{
    		printf("%d ", ret);
    	}
    	else
    	{
    		printf("找不到");
    	}
    	printf("\n");
    	int size=ListSize(&s);
    	printf("%d ", size);
    	printf("\n");
    	int n = ListEmpty(&s);
    	printf("%d ", n);
    }
    int main()
    {
    	testListNode();
    	system("pause");
    	return;
    }

     

    展开全文
  • 双向循环链表一、双向循环链表0.头文件1. 判空2. 申请新结点3. 初始化4.获取长度5.插入1.按位置插2.头插3.尾插6.打印1.正向打印2.逆向打印7.删除1.按位置删除2.头删3.尾删8.主函数 一、双向循环链表 0.头文件 #...

    一、双向循环链表

    0.头文件

    #pragma once
    
    typedef int ElemType;
    typedef struct Node
    {
    	ElemType data;
    	struct Node* prior;
    	struct Node* next;
    }CDLNode,*CDLinkList;
    
    void InitCDLinkList(CDLinkList list);
    
    int InsertCDLinkListPos(CDLinkList list, ElemType val, int pos);
    int InsertCDLinkListHead(CDLinkList list, ElemType val);
    int InsertCDLinkListTail(CDLinkList list, ElemType val);
    
    void ShowCDLinkList(CDLinkList list);
    void RShowCDLinkList(CDLinkList list);
    
    
    int DeleteCDLinkListPos(CDLinkList list, int pos);
    int DeleteCDLinkListHead(CDLinkList list);
    int DeleteCDLinkListTail(CDLinkList list);
    
    

    1. 判空

    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include"cdlist.h"
    
    void DeterPointIsNull(CDLinkList list)
    {
    	assert(list != NULL);
    	if (list == NULL)
    	{
    		exit(0);
    	}
    }
    

    2. 申请新结点

    static CDLinkList ApplyNode(ElemType val, CDLinkList prior, CDLinkList next)
    {
    	CDLinkList p = (CDLinkList)malloc(sizeof(CDLNode));
    	assert(p != NULL);
    	p->data = val;
    	p->prior = prior;
    	p->next = next;
    	return p;
    }
    

    3. 初始化

    void InitCDLinkList(CDLinkList list)
    {
    	DeterPointIsNull(list);
    	list->prior = list->next=list;
    }
    

    4.获取长度

    int GetLen(CDLinkList list)
    {
    	DeterPointIsNull(list);
    	int len = 0;
    	CDLinkList p = list->next;
    	while (p != list)  //现在是循环链表  条件是p不等于头结点
    	{
    		len++;
    		p = p->next;
    	}
    	return len;
    }
    

    5.插入

    1.按位置插

    //可以考虑pos和长度一半比较   考虑从前往后跑还是从后往前跑
    int InsertCDLinkListPos(CDLinkList list, ElemType val, int pos)
    {
    	DeterPointIsNull(list);
    	if (pos<0 || pos>GetLen(list))
    	{
    		printf("Pos is error,Insert Fail\n");
    		return 0;
    	}
    	CDLinkList p = list;
    	while (pos > 0)
    	{
    		p = p->next;
    		pos--;
    	}
    	p->next->prior = ApplyNode(val, p, p->next);
    	p->next= ApplyNode(val,p,p->next);
    	return 1;
    }
    
    

    2.头插

    //O(1)
    int InsertCDLinkListHead(CDLinkList list, ElemType val)
    {
    	DeterPointIsNull(list);
    	return InsertCDLinkListPos(list,val, 0);
    }
    

    3.尾插

    //O(1)
    int InsertCDLinkListTail(CDLinkList list, ElemType val)
    {
    	DeterPointIsNull(list);
    	
    	//return InsertCDLinkListPos(list, val,GetLen(list));
    	//如果进行转调,反而会降低效率,提高时间复杂度,因为需要从头找到尾
    
    	CDLinkList p = list->prior;//p就是最后一个节点
    	p->next->prior = ApplyNode(val, p, p->next);
    	p->next = ApplyNode(val, p, p->next);
    	return 1;
    }
    

    6.打印

    1.正向打印

    void ShowCDLinkList(CDLinkList list)
    {
    	DeterPointIsNull(list);
    	CDLinkList p = list->next;
    	while (p != list)
    	{
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    

    2.逆向打印

    void RShowCDLinkList(CDLinkList list)
    {
    	DeterPointIsNull(list);
    	CDLinkList p = list->prior;
    	while (p != list)
    	{
    		printf("%d ", p->data);
    		p = p->prior;
    	}
    	printf("\n");
    }
    
    

    7.删除

    1.按位置删除

    int DeleteCDLinkListPos(CDLinkList list, int pos)
    {
    	DeterPointIsNull(list);
    	if (pos < 0 || pos >= GetLen(list))
    	{
    		printf("Pos is error,Delete Fail\n");
    		return 0;
    	}
    	CDLinkList p = list;
    	while (pos > 0)
    	{
    		p = p->next;
    		pos--;
    	}
    	CDLinkList s = p->next;
    	p->next = s->next;
    	s->next->prior = p;
    	free(s);
    	return 1;
    }
    

    2.头删

    int DeleteCDLinkListHead(CDLinkList list)
    {
    	DeterPointIsNull(list);
    	return DeleteCDLinkListPos(list, 0);
    }
    

    3.尾删

    int DeleteCDLinkListTail(CDLinkList list)
    {
    	DeterPointIsNull(list);
    	CDLinkList p = list->prior;
    	list->prior = p->prior;
    	p->prior->next = list;
    
    	free(p);
    	return 1;
    }
    

    8.主函数

    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include"cdlist.h"
    
    int main()
    {
    
    	return 0;
    }
    
    展开全文
  • 双向循环链表的实现

    千次阅读 2010-11-28 20:55:00
    对于单链表来说,每个结点都有一个引用域,即next域,用来指向下一个结点,即该结点的...双向循环链表具有以下特点: (1) 判空条件:head.next==head为空。 (2)双向循环链表的head指针的prior指向最后

    对于单链表来说,每个结点都有一个引用域,即next域,用来指向下一个结点,即该结点的后继结点,因此链表中的最后一个节点的引用域必定为空,单链表的这种存储方式决定了它的访问方式,只能从单链表的表头进行遍历。而双向循环链表是由双向链表和循环链表组合而成的,双向链中的数据结构中有三个域,前驱指针域,数据域,后继指针域。而循环链表的尾指针指向头指针。双向循环链表具有以下特点:

    (1) 判空条件:head.next==head为空。

    (2)双向循环链表的head指针的prior指向最后一个结点,而next指向第一个结点。而尾结点的next域指向头指针head.

    双向循环链表的实现类,有结点类和链表类。

    下面是双向循环链表的java实现:

     

    Dlnode结点类:

     

    /**


     * Dlnode用来定义双向循环链表 双向循环链表应该包括一个数据域,一个前驱域和一个数据域 最后一个节点指向第一个首节点
     *
     * @author Administrator
     *
     */
    public class Dlnode {

     Object data;// 数据域
     Dlnode prior;// 指向前驱的指针域
     Dlnode next;// 指向后继的指针域

     public Dlnode(Dlnode prior, Object data, Dlnode next) {
      this.prior = prior;
      this.data = data;
      this.next = next;
     }

     public Dlnode() {
      this(null, null, null);
     }

     public Object getData() {
      return data;
     }

     public void setData(Object data) {
      this.data = data;
     }

     public Dlnode getNext() {
      return next;
     }

     public void setNext(Dlnode next) {
      this.next = next;
     }

     public Dlnode getPrior() {
      return prior;
     }

     public void setPrior(Dlnode prior) {
      this.prior = prior;
     }
    }

     

     链表类的实现:

     /**
     * 此类是实现双向循环链表 双向循环链表的特点: (1)空结点:只有一个首结点,其前驱与后继都指向自身。 (2)非空:后一个结点的前驱指向前一个节点
     * 前一个节点的后继指向后一个节点 最后一个节点的后继指向首节点 首节点的前驱指向最后一个节点
     *
     * @author Administrator
     *
     */
    public class DlList {

     Dlnode dlhead;// 链表表头
     int size;

     public DlList() {
      dlhead = new Dlnode();
      dlhead.prior = dlhead;
      dlhead.next = dlhead;
      size = 0;
     }// 构造一个空表

     public DlList(Object[] a) {// 用数组a构造一个双向循环链表
      dlhead = new Dlnode();
      dlhead.prior = dlhead;
      dlhead.next = dlhead;
      Dlnode p = null;
      for (int i = a.length - 1; i >= 0; i--) {
       p = new Dlnode(dlhead, a[i], dlhead.next);
       dlhead.next.setPrior(p);
       dlhead.setNext(p);

      }

      size = a.length;

     }

     public void clear() {
      dlhead = new Dlnode();
      dlhead.prior = dlhead;
      dlhead.next = dlhead;
     }

     /**
      * 找到双向循环链表中第i个节点 首节点是第0个节点,然后 是第1个节点,依次类推
      *
      * @param i
      * @return
      */
     public Dlnode index(int i) {
      Dlnode p;
      int j;
      if (i < 0 || i > size)
       p = null;
      else if (i == 0)
       p = dlhead;
      else {
       p = dlhead.next;
       j = 1;
       while (j < i && p != null) {
        p = p.next;
        j++;

       }

      }

      return p;

     }

     /**
      * 得到第i个节点的data值
      *
      * @param i
      * @return
      */
     public Object get(int i) {
      Dlnode p;
      if (i <= 0 || i > size)
       return null;
      else {
       p = index(i);
       return p.getData();

      }

     }

     /**
      * 计算双向循环链表的长度
      *
      */

     public int len() {
      return size;
     }

     /**
      * 得到data域为el的节点索引号
      *
      * @param el
      * @return
      */
     public int loc(Object el) {
      Dlnode p;
      int j = 1;
      p = dlhead.next;
      while (!p.data.equals(el) && p != dlhead) {// 双向循环链表结束的条件是尾结点的下一个指针是否指向头结点
       j++;
       p = p.next;

      }

      if (p != dlhead)
       return j;
      else
       return 0;

     }

     /**
      * 第一个参数是插入的位置 第二个参数是插入节点的data值
      *
      * @param loc
      * @param el
      * @return
      */
     public boolean insert(int loc, Object el) {
      if (loc < 1 && loc > size + 1)
       return false;
      Dlnode p = index(loc - 1);
      Dlnode q = new Dlnode(p, el, p.next);
      p.next.setPrior(q);
      p.setNext(q);
      size++;

      return true;

     }

     /**
      * 删除结点,提供删除节点的索引号
      *
      */

     public Object delete(int i) {
      if (size == 0 || i < 1 || i > size)
       return null;
      Dlnode p = index(i);
      Object data = p.getData();
      p.prior.setNext(p.next);
      p.next.setPrior(p.prior);
      size--;
      return data;

     }

     public boolean empty() {
      return dlhead.next == dlhead;
     }

    }

     

     

     测试类:

     

    public class TestDllist {

     /**
      * @param args
      */
     public static void main(String[] args) {

      DlList dl = new DlList();

      for (int i = 0; i < 10; i++)
       dl.insert((i + 1), new Integer(i + 1));
      print(dl);

     }

     public static void print(DlList dl) {
      System.out.println("双向循环链表遍历结果:");
      Dlnode p;
      p = dl.dlhead.next;
      while (p != dl.dlhead) {
       System.out.print(p.getData() + " ");
       p = p.next;
      }

     }

    }

     双向循环链表插入与删除时间复杂度的分析:

    双向循环链表的插入与删除的时间复杂度都为O(1).由于删除时寻找前驱结点只需要p->prior即可。

     

     

    展开全文
  • 添加节点删除节点移动节点链表判空链表合并 获取宿主对象指针遍历 List-head链表遍历遍历宿主对象 如何使用Linux中的双循环链表 详解Linux内核之双向循环链表 Sailor_forever sailing_9806@163.com 转载请...
  • 双向循环链表的建立及操作

    千次阅读 2019-06-19 20:42:43
    项目名称:双向循环链表的建立与基本操作 编译环境:VC++ 2008 作者相关:。。。 最后修改:2019.6.19 学习目标:判空、求长、获取元素位置、返回某个位置的元素、插入元素、删除元素、清空链表、销毁链表 ...
  • 链表的结构 解析: 每一个结点都有一个数据域,两个...所以对于双向链表来说,它的判空条件是head->next=head或者是head->prev=head 下图为一个带头结点的空双链表链表基本操作的实现 (1)插入 1....
  • //双循环链表的实现 #include <stdio.h> #include <stdlib.h> typedef struct LNode{ int data; struct LNode *prior,*next; }LNode,*LinkList; //判空函数 bool Empty(LinkList &L){ if(L-&...
  • 本篇主要实现了带有头结点的双向循环链表的基本操作,其中包括增删改查以及清空销毁、判空、求结点个数等等。 头文件 DoubleLinkList.h # ifndef __DOUBLELINKLIST_H__ # define __DOUBLELINKLIST_H__ # ...
  • class Node:def __init__(self, elem):self.elem = elemself.prev = Noneself.next = Noneclass DoubleCycleLinkList:def __init__(self, node=None):self.__head = nodedef is_empty(self):"""判空"""if self.__...
  • 单链表的遍历,清空,判空,获取指定结点 循环链表 循环链表的定义 循环链表的插入和删除 循环链表的遍历,清空 双向链表 双向链表的定义 双向链表的插入和删除 本节代码传送门,欢迎star:https://github...
  • 单向循环链表 PS:有阴影的结点是头结点 概念: 最后一个结点的链域值不为NULL,而是...双向链表中的头结点的前趋指针域指向了尾结点,尾结点的后继指针域指向了头结点,即可称为双向循环链表 判空条件 头结点的前...
  • 一、循环链表循环链表(Circular linked ... 单链的循环链表和单链表的本质一样,唯一的区别在于判断链表结束由判空改为了判断是否为头结点。下面给出具体的C语言代码实现: 头文件CList.h中给出循环链表结构体定义
  • 如何判断一个链表是否为

    万次阅读 2018-05-07 22:24:19
    L为指向表头结点的指针,分别写出带有头结点的单链表、单项循环链表和双向循环链表判空的条件单链表 NULL==L-&gt;next单向循环 L==L-&gt;next双向循环 L==L-&gt;next&amp;&amp;L==L-&gt;...
  • 直接贴出完整代码,每个函数的功能及部分代码的解释都在注释中,代码亲测可行 /* 2018.8.15 注意三点: 1.不要将循环写成if //很尴尬,主要是我犯了这个... 2.循环链表判空操作是 p->rear != *L 3....
  • 和正常的单链表有所不同,首先是判空的条件,原来的为head->next 为NULL,而现在就是head为NULL 其次在循环的时候就不应该以NULL为结束的标志了。 最后,在插入和删除的时候,和之前稍有不同,建议画图体会一下。...
  • 循环链表的概念,双向循环链表的概念,插入和删除结点 多项式的链表表示,算法思想 1、概念级知识点:首尾相接的链表为循环链表。任一节点出发均就可以 找到表中其他节点,分 单向循环和双向循环链表 特殊...
  • 1.4双向链表 ...3、带头双向循环链表判空条件为head->prior==head或head->next==head; 代码实现: DLinkList.h #pragma once #include <stdio.h> #include <stdlib.h> typ
  • 用模板写链表主要还是为了实现代码的类型通用性,用模板写函数或类都与是类型无关的,因此,STL中都是用模板来实现容器,下面我们来介绍用模板实现顺序表和带头结点的双向循环链表。 以下代码将实现顺序表和链表的增...
  • 带头双向循环链表: 单链表逻辑结构示意图: 带头结点和不带头结点链表: 概念: 带头结点单链表: 插入操作如下 删除操作如下 统一表和非空表的处理 不带头结点单链表: 插入操作如下 删除操作如下 统一...
  • 目录链表的概念及结构创建节点类定义头节点插入头插法尾插法任意位置插入查找n位置节点删除节点其它方法判空计算链表长度打印链表完整代码 链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的...
  • //----------双向链表的存储结构------------ typedef struct DuLNode { ElemType date; struct DoLNode *prior; struct DoLNode *next;...判空 L-&gt;next=L; // L-&gt;prior=L;...
  • 这里环形数据结构主要包括:环形链表、环形...pHead为指向表头结点的指针,分别写出带有头结点的单链表、单项循环链表和双向循环链表判空的条件 单链表 NULL==pHead->next 单向循环 pHead==pHead->...
  • 循环链表 双向链表 二、线性表操作 一般线性表操作: MyArray(int size);//构造函数 ~MyArray();//析构 int get_length();//长度获取。 bool get_empty();//判空。 bool get_ele(int...
  • C#编程经验技巧宝典

    热门讨论 2008-06-01 08:59:33
    27 <br>0056 强行改变运算符的运算顺序 27 <br>第3章 程序算法 29 <br>3.1 数据结构 30 <br>0057 如何实现单向链表 30 <br>0058 如何实现双向链表 35 <br>0059 如何实现堆栈 41 ...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

双向循环链表判空