双链表-双链表的排序（非节点值排序，而是节点排序）

柔情只为你懂 2023-02-19 08:25 27阅读 0赞

双链表的排序

#include <stdio.h>
    #include <stdlib.h>
    
    
    // 双链表
    typedef struct node_t{ 
    	int val;
    	int idx;
    	struct node_t *next, *prev;
    }in, *in_p;
    
    void  showList( struct node_t *h )
    { 
    	printf("++++++++++++showList+++++++++++++\n");
    	while( h ){ 
    		printf("h->idx = %d , h->val = %d\n", h->idx, h->val );
    		h = h->next;
    	}
    }
    void  showRList( struct node_t *h )
    { 
    	printf("+++++++++++showReverse++++++++++++++\n");
    	while( h->next ){ 
    		h = h->next;
    	}
    	while( h ){ 
    		printf("h->idx = %d , h->val = %d\n", h->idx, h->val );
    		h = h->prev;
    	}
    }
    
    void insertHead( struct node_t **h, struct node_t *n )
    { 
    	n->next = *h;
    	if( *h != NULL ){ 
    		(*h)->prev = n;
    	}
    	*h = n;
    }
    
    void insertTail( struct node_t **h, struct node_t *n )
    { 
    	if( *h == NULL ){ 
    		*h = n;
    		return;
    	}
    	struct node_t *p = *h;
    	while( p->next ){ 
    		p = p->next;
    	}
    	p->next = n;
    	n->prev = p;
    }
    
    in_p sort_list(in_p h){ 
    	in_p newhead = NULL, min = NULL, head = NULL;
    	while(h){ 
    		min = h;
    		head = h;
    	
    		while(head->next){ 
    			if(min->val > head->next->val){ 
    				min = head->next;
    			}
    		head = head->next;
    		}
    			
    		if(min == h){ 
    			h = h->next;
    		}
    		else{ 
    			min->prev->next = min->next;
    			if(min->next){ 										//以防最后一个节点是最小值，如果没有这判断，可能段错误
    				min->next->prev = min->prev;
    			}
    		}
    		min->next = NULL;										//
    		min->prev = NULL;										//让min指向的这个节点完全脱开链表
    
    		min->next = newhead;
    		if(newhead != NULL){ 
    			newhead->prev = min;
    		}
    		newhead =  min;
    	}
    	return newhead;
    }
    
    int main()
    { 
    	int arr[] = { 10,10,9,8,5,20,10,10,30,20,10,10};
    	struct node_t *head = NULL;
    	int i = 0;
    	struct node_t *newnode = NULL;
    	while( i < sizeof(arr)/sizeof(int) ){ 	
    		newnode = malloc( sizeof(struct node_t) );	
    		newnode->val = arr[i];
    		newnode->idx = i;
    		newnode->next = NULL;
    		newnode->prev = NULL;
    		insertTail( &head , newnode );	
    	// head = insertTail( head, newnode );
    	// insertTail1( &head, newnode );
    		i++;
    	}
    	showList( head );	
    	head = sort_list(head);
    	showList( head );	
    	return 0;
    }