直接插入排序——对单链表进行非递减排序（带头结点）c语言实现

柔光的暖阳◎ 2024-04-18 16:49 44阅读 0赞

/*************************** 
    * author：vivi
    * date: 19-09-09
    ****************************/  
    #include <stdio.h>
    #include <stdlib.h>
    
    // function：单链表递增直接插入排序
    
    typedef struct Node
    {
        
    	int data;
    	struct Node* next;
    }Node,* SList;
    
    void init_list(SList* head)
    {
        
    	*head = (SList)malloc(sizeof(Node));
    	(*head)->next = NULL;
    }
    
    void CreatList(SList* head)
    {
        
        int x;
        int flag = 1;
        printf("input data end 0:\n");
        while(flag ==1)
        {
        
            scanf("%d",&x);
            if(x != 0)
            {
        
                Node* p =(Node*)malloc(sizeof(Node));
        	    p->data = x;
        	    p->next = (*head)->next;    //头插法 
        	    (*head)->next = p;
    	        flag = 1;
    	    }else flag = 0;
        }
    }
    
    void insertsort(SList head)
    {
        
    	Node* pre,*q,*p,*s;
        if(head->next != NULL)
    	{
        
    	    pre = head;
    		q = head->next;
    		if(q->next != NULL)
    		{
        
    		    p = q->next;
    			while(p != NULL)
    			{
        
    				while(p->data >= q->data)
    				{
        
    			        p = p->next;
    				    q = q->next;
    			    }
    				if(p != NULL && p->data < q->data)
    				{
        
    				    s = p;
    					q->next = p->next;
    					p = p->next;
    					while(s->data > pre->next->data)
    					    pre = pre->next;	
    					s->next = pre->next;
    					pre->next = s;
    					pre = head;
    				}	
    			}	
    		}	
    	} 
    }
    
    void print(SList head)
    {
        
    	Node* p = head;
    	while(p->next != NULL)
    	{
        
    		printf("%d ",p->next->data);
    		p = p->next;
    	}
    }
    
    int main() {
        
    	SList mylist;
    	init_list(&mylist);
    	CreatList(&mylist);
    	printf("原始链表：\n");
    	print(mylist);
    	printf("\n非递减链表：\n");
    	insertsort(mylist);
    	print(mylist);
    	return 0;
    }