链表-链表的排序（非节点值的排序，而是节点排序），对什么排序又排序函数的参数决定（条件函数）

电玩女神 2023-02-19 01:26 19阅读 0赞

# 节点排序的函数 #

int cmpScore( struct node_t *n1, struct node_t *n2 )
    { 
    	return n1->score - n2->score;
    }
    
    int cmpVal( struct node_t *n1, struct node_t *n2 )
    { 
    	return n1->val - n2->val;
    }
    
    void sortList( struct node_t **h, 
    	int (*fp)(struct node_t *, struct node_t * ) )
    { 
    	struct node_t *newhead = NULL;
    	struct node_t *min = NULL;
    	struct node_t *minPrev = NULL;	
    	struct node_t *p = NULL;
    	while( *h ){ 
    		// find min
    		minPrev = NULL;
    		p = *h;
    		min = p;
    		while( p->next ){ 
    		// if( min->val > p->next->val ){ 
    			if( fp( min, p->next ) > 0 ){ 
    				minPrev = p;
    				min = p->next;
    			}
    			p = p->next;
    		}
    	// printf("min = %d\n", min->val );
    		// cut
    		if( min == *h ){ 
    			*h = (*h)->next;
    		}else{ 
    			minPrev->next = min->next;	
    		}
    		// insert
    		min->next = newhead;
    		newhead = min;
    	}
    	*h = newhead;
    }

# 节点排序完整的函数 #

#include <stdio.h>
    
    // 链表 : 链 头
    
    struct node_t{ 
    	int idx;
    	int val;
    	int score;
    	struct node_t *next;
    };
    
    
    void showList( struct node_t *h )
    { 
    	printf("++++++++++++++++++++++++++++++\n");
    	while( h ){ 
    		printf("h->idx = %d, h->val = %d, h->score = %d\n", 
    				h->idx, h->val, h->score );
    		h = h->next;
    	}
    }
    
    struct node_t* insertHead( struct node_t *h, struct node_t *n )
    { 
    	n->next = h;
    	return n;
    }
    
    void  insertHead1( struct node_t **h, struct node_t *n )
    { 	
    	n->next = *h;
    	*h = n;
    }
    
    struct node_t *insertTail( struct node_t *h , struct node_t *n )
    { 
    	if( h == NULL ){ 
    		return n;
    	}
    	
    	struct node_t *p = h;
    	while( p->next != NULL ){ 
    		p = p->next;
    	}
    	p->next = n;
    	return h;
    }
    
    void insertTail1( struct node_t **h, struct node_t *n )
    { 
    	while( *h ){ 
    		h = &((*h)->next);
    	}
    	*h = n;
    }
    
    // 排序: find min/max cut insert
    
    int cmpScore( struct node_t *n1, struct node_t *n2 )
    { 
    	return n1->score - n2->score;
    }
    
    int cmpVal( struct node_t *n1, struct node_t *n2 )
    { 
    	return n1->val - n2->val;
    }
    
    void sortList( struct node_t **h, 
    	int (*fp)(struct node_t *, struct node_t * ) )
    { 
    	struct node_t *newhead = NULL;
    	struct node_t *min = NULL;
    	struct node_t *minPrev = NULL;	
    	struct node_t *p = NULL;
    	while( *h ){ 
    		// find min
    		minPrev = NULL;
    		p = *h;
    		min = p;
    		while( p->next ){ 
    		// if( min->val > p->next->val ){ 
    			if( fp( min, p->next ) > 0 ){ 
    				minPrev = p;
    				min = p->next;
    			}
    			p = p->next;
    		}
    	// printf("min = %d\n", min->val );
    		// cut
    		if( min == *h ){ 
    			*h = (*h)->next;
    		}else{ 
    			minPrev->next = min->next;	
    		}
    		// insert
    		min->next = newhead;
    		newhead = min;
    	}
    	*h = newhead;
    }
    
    
    int main()
    { 
    	srand( time(NULL) );
    	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->score = rand() % 100;
    		newnode->next = NULL;
    		//head = insertHead( head, newnode );
    		//insertHead1( &head , newnode ); 
    	// head = insertTail( head, newnode );
    		insertTail1( &head, newnode );
    		i++;
    	}
    	
    	showList( head );
    	sortList( &head, cmpScore );
    	showList( head );
    }