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

    2019-05-25 16:11:08
    1:创建单向循环链表 2:遍历单向循环链表 3:单向循环链表节点插入 4:单向循环链表节点删除 5:单向循环链表倒序 6:单向循环链表排序 7:单向循环链表销毁 8:获取单链表的长度 9:单向循环链表判空 */ ...

    /*
        1:创建单向循环链表
        2:遍历单向循环链表
        3:单向循环链表节点插入
        4:单向循环链表节点删除
        5:单向循环链表倒序
        6:单向循环链表排序
        7:单向循环链表销毁
        8:获取单链表的长度
        9:单向循环链表判空
    */
    #include <iostream>
    using namespace std;
    typedef struct node{
        int value;
        struct node *pNext;
    }List;
    /*创建单向循环链表*/
    void Create(List* &Head,List* &End,int &NodeCount)
    {
        if(NodeCount <= 0)  return ;
        int nodevalue_ = 0;
        List* node = NULL;
        for(int i=0;i<NodeCount;i++){
            cin>>nodevalue_;
            node = new List;
            node->value = nodevalue_;
            node->pNext = NULL;
            if(Head == NULL){
                Head = node;
            }
            else{
                End->pNext = node;
            }
            End = node;
        }
        End->pNext = Head;
    }
    /*遍历单项循环链表*/
    void Traval(List* &Head,List* &End)
    {
        if (Head == NULL || End == NULL)  return ;
        List* ptr = Head;
        while(ptr != End){
            cout<< ptr->value<<" ";
            ptr = ptr->pNext;
        }
        cout<< ptr->value<<endl;
    }
    /*获取单向链表的长度*/
    void Length(List* &Head,List* &End,int &Length)
    {
        if (Head == NULL || End == NULL)  {
            Length = 0 ; 
            return ;
        }
        Length = 1;
        List* ptr = Head;
        while(ptr != End){
            Length++;
            ptr = ptr->pNext;
        }
    }
    /*单向循环链表节点插入*/
    void Insert(List* &Head,List* &End,int &InsertPos,int &InsertValue)
    {
        if ((Head == NULL || End == NULL) && InsertPos != 1)  return ;
        int length = 0;
        Length(Head,End,length);
        List* insertnode = new List;
        insertnode->value = InsertValue;
        insertnode->pNext = NULL;
        if (InsertPos == 1 || (InsertPos == (++length))) {
            insertnode->pNext = Head;
            End->pNext = insertnode;
            if(InsertPos == 1){
                Head = insertnode;
            }
            else{
                End = insertnode;
            }
            return ;
        }
        else{
            int insertpos = 2;
            List* InsertPrior = Head;
            List* InsertNext = InsertPrior->pNext;
            while(insertpos != InsertPos){
                insertpos++;
                InsertPrior = InsertPrior->pNext;
                InsertNext = InsertNext->pNext;
            }
            insertnode->pNext = InsertNext;
            InsertPrior->pNext = insertnode;
        }
    }
    /*单向循环链表节点删除*/
    void Del(List* &Head,List* &End,int &DelPos)
    {
        int length;
        Length(Head,End,length);
        if (Head ==  NULL || End == NULL || DelPos <=0 || DelPos > length)  return ;
        List* DelPrior = End;
        List* DelNext = Head->pNext;
        if (DelPos == 1 ){
            End->pNext = DelNext;
            delete Head;
            Head = DelNext;
        }
        else {
            DelPrior = Head;
            DelNext = DelPrior->pNext->pNext;
            int delpos = 2;
            List* ptr = NULL;
            while(delpos != DelPos){
                DelPrior = DelPrior->pNext;
                DelNext = DelPrior->pNext->pNext;
                delpos++;
            }
            ptr= DelPrior->pNext;
            DelPrior->pNext = DelNext;
            if (ptr == End){
                End = DelNext;
            }
            delete ptr;
            ptr = NULL;
        }
    }
    /*单向循环链表倒序*/
    void Reverse(List* &Head,List* &End)
    {
        if(Head == NULL || End == NULL)  return ;
        List* ptr = Head,*ptr_next= NULL;
        End->pNext = NULL;
        while(ptr != End){
            ptr_next = ptr->pNext;
            ptr->pNext = End->pNext;
            End->pNext = ptr;
            ptr = ptr_next;
        }
        ptr = Head;
        Head = End;
        End = ptr;
        End->pNext = Head;
    }
    /*单向循环链表排序*/
    void Sort(List* &Head,List* &End)
    {
        if( Head == NULL || End == NULL)  return ;
        End->pNext = NULL;
        int listlength = 0;
        Length(Head,End,listlength);
        List *node = Head,*node_pNext = node->pNext;
        List *tmp = NULL;
        List *node_prior = NULL;
        int nflag ;
        for(int i=0;i<listlength;i++){
            nflag = 0;
            node = Head;
            node_pNext = Head->pNext;
            node_prior = Head;
            for(int j=0;j<listlength-i-1;j++){
                if(node_pNext->value < node->value){
                    tmp = node_pNext;
                    node->pNext = node_pNext->pNext;
                    node_pNext->pNext = node;
                    if(node != Head){
                        node_prior->pNext = node_pNext;
                    }
                    if(node == Head){
                        Head = node_pNext;
                    }
                    if (node_pNext == End){
                        End = node;
                    }
                    tmp = node;
                    node = node_pNext;
                    node_pNext = tmp;
                    nflag = j+1;
                }
                node_prior = node;
                node = node->pNext;
                node_pNext = node->pNext;    
            }
            if (nflag == 0 ){
                break;
            }
            i = listlength - nflag - 1;
        }
        End->pNext = Head;
    }
    /*单向链表销毁*/
    void Destroy(List* &Head,List* &End)
    {
        if(Head == NULL || End == NULL)  return ;
        List* ptr = Head,*ptr_next = NULL;
        while(ptr != End){
            ptr_next = ptr->pNext;
            delete ptr;
            ptr = NULL;
            ptr = ptr_next;
        }
        Head = NULL;
        End = NULL;
    }
    bool m_is_empty(List* &Head,List* &End)
    {
        if(Head == NULL && End == NULL)  return true;
        else return false;
    }
    int main()
    {
        List *Head = NULL ,*End = NULL;
        int length = 0,nodecount = 0,insertpos = 0,insertvalue = 0,delpos = 0;
        /*创建单向循环链表*/
        cin>>nodecount;
        Create(Head,End,nodecount);
        Traval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*单向循环链表插入节点*/
        cin>>insertpos >> insertvalue;
        Insert(Head,End,insertpos,insertvalue);
        Traval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*删除单向循环链表的节点*/
        cin>>delpos;
        Del(Head,End,delpos);
        Traval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*单向循环链表的倒序*/
        Reverse(Head,End);
        Traval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*单向循环链表排序*/
        Sort(Head,End);
        Traval(Head,End);
        Length(Head,End,length);
        cout<<length<<endl;
        /*单向循环链表判空*/
        bool b_empty = m_is_empty(Head,End);
        if(b_empty == true){
            cout<<"is_empty"<<endl;
        }
        else{
            cout<<"is_not_empty"<<endl;
        }
        /*销毁单向链表*/
        Destroy(Head,End);
        if(Head == NULL && End == NULL){
            cout<<"is_empty"<<endl;
        }
        else{
            cout<<"not_empty"<<endl;
        }
        system("pause");
        return 0;
    }

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,011
精华内容 1,604
关键字:

单向循环链表