单链表的排序.c

《数据结构-使用C语言》第三版

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef int DataType;
#include"SLNode.h" 
  
void  ListChange(SLNode *head,int len)
{
	int i;
  	SLNode *h,*p,*pre,*q;
  
  	ListInitiate(&h);
  	h->next=head->next;
  	
  	p=head;
  	head->next=NULL;//先把头指针的下一个域至空，以便好插
  
  	for(i=0;i<len;i++)
   	{
        pre=h;
    	q=h;
    	
        while(pre->next!=NULL) 
        {   
			if(pre->next->data>q->next->data)
			q=pre;
			pre=pre->next;
        }
    	if(q->next->next==NULL)q->next=NULL;
		else q->next=q->next->next;
        
      	p->next=q->next;
        p=p->next;
        p->next=NULL;
 	}
 	free(head);
 
}

void ListCreat(SLNode *head)
{
	DataType t;
	SLNode *p,*r;
	
	
	p=head;
	while(1)
	{
		scanf("%d",&t);
		
		if(t==0)break;	//数据元素以'#'结束 
		if((r=(SLNode*)malloc(sizeof(SLNode)))==NULL) return;
	
			
		r->data=t;
			
		p->next=r;
		r->next=NULL;
		p=p->next;
		
	}
}			
			

int main()
{
	int len;
	SLNode *head,*p;
    
    while(1)
    {            
		ListInitiate(&head);
		ListCreat(head);
		
		len=ListLength(head);
		ListChange(head,len);
		
		p=head;
		while(p->next!=NULL)
		{
			printf("%d ",p->next->data);
			p=p->next;
		}
		printf("\n");
		
		ListDestory(&head);
	}
	return 0;
}