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

    2019-05-25 21:24:01
    /* 双向循环链表 1:双向循环链表创建 2:双向循环链表长度 3:双向循环链表正向遍历 4:双向循环链表反向遍历 ... 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;
    }

    展开全文
  • 排序双向 循环链表
  • 双向循环链表的冒泡排序 之前和群友水群的时候被认为双向循环链表不能实现冒泡排序,于是实现了一下,哪有什么不能的 ,下面是纯c的代码实现.如果错误还请指正. #include <stdio.h> #include <stdlib.h> ...

    双向循环链表的冒泡排序

    之前和群友水群的时候被认为双向循环链表不能实现冒泡排序,于是实现了一下,哪有什么不能的 ,下面是纯c的代码实现.如果错误还请指正.

    #include <stdio.h>
    #include <stdlib.h>
    int n = 0;//链表中的数据的数量++
    struct Two_way_list{
        struct Two_way_list* front;
        struct Two_way_list* behind;
        int val;
    };
    void Two_way_list_init(struct Two_way_list *head,struct Two_way_list* end){
        head = NULL;
        end = NULL;
        return ;
    }
    void Two_way_list_insert(struct Two_way_list** head,struct Two_way_list** end,int temp){
        if(n == 0){ // 如果是第一次插入数据
            *head = (struct Two_way_list *)malloc(sizeof(struct Two_way_list));
            *end = *head;
            (*head) -> front = head;
            (*head) -> behind = head;
            (*head)->val = temp;
        }
        else{
            struct Two_way_list* pte = (struct Two_way_list *)malloc(sizeof(struct Two_way_list));
            pte -> val = temp;
            (*end) -> behind = pte;
            pte -> front = *end;
            pte -> behind = *head;
            (*head) -> front = pte;
            *end = pte;
        }
        ++ n;
        return ;
    }
    void Two_way_list_print(struct Two_way_list *head,struct Two_way_list * end){
        struct Two_way_list * temp = head;
       while(temp != end){
            printf("%d ",temp->val);
            temp = temp -> behind;
        }
        printf("%d\n",temp->val);
        return ;
    }
    void Two_way_list_bubble(struct Two_way_list** H,struct Two_way_list** E){
    	if(n <= 1)
    		return ;
    	for(int i = 0;i < n;++ i){
    		struct Two_way_list *head = *H, * end = *E;
    		struct Two_way_list * temp = head;
    		while(temp != end){
    			if(temp->val > temp->behind->val){
    				temp -> behind -> front = temp -> front;
    				temp -> front -> behind = temp ->behind;
    				temp -> front = temp -> behind;
    				temp -> behind = temp -> behind -> behind;
    				temp -> behind -> front = temp;
    				temp -> front -> behind = temp;
    				temp = temp -> front;//交换之后temp向后移动了一个位置,所以移动回来
    			}
    			if(temp -> behind == head){
    				head = temp;
    				*H = temp;
    			}
    			if(temp == end){
    				end = temp -> behind;
    				*E = temp -> behind;
    			}
    			temp = temp -> behind;
    		}
    	}
    	return ;
    }
    
    int main(){
        struct Two_way_list *head ,*end;
        Two_way_list_init(head,end);
        int temp = 0;
        while(scanf("%d",&temp)!=EOF){
            Two_way_list_insert(&head,&end,temp);
        }
    	Two_way_list_bubble(&head, &end);
        Two_way_list_print(head,end);
    
    	while(scanf("%d\n",&temp)!=EOF){
    		Two_way_list_insert(&head, &end, temp);
    	}
    	Two_way_list_bubble(&head, &end);
        Two_way_list_print(head,end);
    
        return 0;
    }
    
    
    展开全文
  • 利用了双向循环链表实现了快速排序算法
  • 二叉排序树变成双向循环链表,二叉排序树变成双向循环链表,二叉排序树变成双向循环链表
  • c++双向循环链表实现基数排序 #include<iostream> using namespace std; #include<math.h> typedef struct node { int key; struct node *prior; struct node *next; }LNode; /*双循环链表是环形的...

    c++双向循环链表实现基数排序

    #include<iostream>
    using namespace std;
    #include<math.h>
    
    typedef struct node
    {
    	int key;
    	struct node *prior;
    	struct node *next;
    }LNode;
    
    /*双循环链表是环形的,首尾相连的*/
    //取下并删去双循环链表的第一个元素
    template<class Type>
    Type  *del_entry(Type *L)
    {
    	Type *p;
    	p=L->next;
    	if(p!=NULL){
    		p->prior->next=p->next;
    		p->next->prior=p->prior;
    	}
    	else 
    		p=NULL;
    	return p;
    }
    
    //把一个元素插入双循环链表的表尾
    template<class Type>
    void add_entry(Type *L,Type *p)
    {
    	p->prior=L->prior;
    	p->next=L;
    	L->prior->next=p;
    	L->prior=p;
    }
    
    //取p所指向关键字的第i位数字(最低位为0位)
    template <class Type>
    int get_digital(Type *p,int i)
    {
    	int key;
    	key=p->key;
    	if(i!=0)
    		key=key/pow(10,i);
    	return key%10;
    }
    
    //把链表L1所有元素加到链表L的末端(删去L1的头结点)
    template<class Type>
    void append(Type *L,Type *L1)
    {
    	if(L1->next!=L1){
    		L->prior->next=L1->next;    
    		L1->next->prior=L->prior;  
    		L1->prior->next=L;
    		L->prior=L1->prior;
    	}
    }
    
    //基数排序
    template<class Type>
    void radix_sort(Type *L,int k)
    {
    	Type *Lhead[10],*p;
    	int i;
    	for(i=0;i<10;i++){
    		Lhead[i]=new Type;//分配10个链表的头结点
    	}
    	for(i=0;i<k;i++){
    		for(int j=0;j<10;j++){    //把10个链表置为空表
    			Lhead[j]->prior=Lhead[j]->next=Lhead[j];
    		}
    		while(L->next!=L){
    			p=del_entry(L);    //删去L的第一个元素,使P指向该元素
    			j=get_digital(p,i);    //从P所指向的元素关键字取第i个数字
    			add_entry(Lhead[j],p);  //把p所指向的元素加入链表Lhead[j]的表尾
    		}
    		for(j=0;j<10;j++){
    			append(L,Lhead[j]);   //把10个链表的元素链接到L
    		}
    	}
    	for(i=0;i<10;i++)
    		delete(Lhead[i]);   //释放10个链表元素的头结点
    }
    
    void main()
    {
    	LNode *L=new LNode();
    	LNode *p;
    	L->next=L;
    	L->prior=L;
    	cout<<"请输入初始链表的值:"<<endl;
    	for(int i=0;i<8;i++){
    		p=new LNode;
    		cin>>p->key;
    		add_entry(L,p);
    	}
    	radix_sort(L,8);
    	p=L->next;
    	cout<<"基数排序后:"<<endl;
    	while(p!=L){
    		cout<<p->key<<" ";
    		p=p->next;
    	}
    	cout<<endl;
    }
    

    运行结果如下:

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

    千次阅读 2018-09-21 18:39:07
    //排序 void sort(dlist_t head) { dlist_t tmp = head-&gt;next,p = NULL,q = NULL; //将链表置空 head-&gt;next = head; head-&gt;prev = head; while(tmp!=head){ //保存原链表中tmp的下一个...
    //排序
    void sort(dlist_t head)
    {
        dlist_t tmp = head->next,p = NULL,q = NULL;
    
        //将链表置空
        head->next = head;
        head->prev = head;
    
        while(tmp!=head){
            //保存原链表中tmp的下一个节点
            q = tmp->next;
            
            //找到tmp插入的位置
            for(p=head->prev;p!=head&&p->data>tmp->data;p=p->prev);
            //将tmp插入到p之后
            tmp->prev = p;
            tmp->next = p->next;
            p->next->prev = tmp;
            p->next = tmp;
    
            //将tmp指向要插入的下一个节点
            tmp = q;
        }
        
    }

     

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

    2021-03-17 11:12:19
    VC++双向循环链表,实现功能:创建新链表、添加新节点;链表数据排序、输入链表信息;查找和删除链表数据、清屏、清空链表等,如果你对VC++的双向循环链表不太熟悉,这个例子对你的是比较有用的。 运行环境:...
  • 该代码用C++语言。实现排序双向循环链表。 请用Eclipse 导入查看代码
  • 双向循环链表的插入排序

    千次阅读 2017-11-30 21:55:53
    前两篇博文,我讨论了链表的冒泡排序和选择排序(以Linux内核链表为例),这篇文章,我想说说插入排序
  • 以Linux内核链表为例,进行选择排序
  • 双向循环链表 1.概念 双向循环链表的节点包含一个数据域,两个指针域,一个指针域指向上一个节点,另一个指针域指向下一个节点 这样双向循环链表构成了两个相反方向遍历的圆环 双向循环链表与单链表相比,提高了访问...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 782
精华内容 312
关键字:

双向循环链表排序