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

    2019-05-25 21:24:01
    双向循环链表 1:双向循环链表创建 2:双向循环链表长度 3:双向循环链表正向遍历 4:双向循环链表反向遍历 5:双向循环链表节点插入 6:双向循环链表节点删除 7:双向循环链表倒序 8:双向循环链表判空 9...

    /*
    双向循环链表
        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;
    }

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,753
精华内容 3,501
关键字:

双向循环链表