学步园

其实个人以为用单链表排序就是自己找麻烦,用数组排序多好啊,

但是转念一想,还是挑战一下自己吧,这个程序的声明和前几次的不同,但是仅仅是换汤不换药.

谨以此作为链表的练习吧.

#include<stdio.h>
#include<stdlib.h>
typedef int elem;
typedef struct node
{
	 elem data;
	struct node *link;
}lnode,*node;
void initlist(node l,int ms)
{
	node p;
	l->link = NULL;
	while(ms--)
	{
		p = (node)malloc(sizeof(lnode));
		scanf("%d",&p->data);
		p ->link = l->link;
		l->link = p;
	}
}
void bubble(node head)
{
	node pp,p,q,last;
	last = head;
	while(last->link!=NULL)
		last = last->link;                         //last指向链表末尾
	while(last!=head->link)                        //防止出现链表中只有一个元素的情况
	{
		pp = head;
		p = pp->link;
		while(p!=last)
		{
			q = p->link;
			if(p->data>q->data)
			{
				pp->link = q; p->link = q->link;
				q->link = p;
				if(last==q)last=p;
			}

			pp = (p->data < q->data)?p:q;
			p = pp->link;
		}
		last = pp;
	}
}
void travel(node l)
{
	while(l->link)
	{
		printf("%d ",l->link->data);
		l = l->link;
	}
}
int main()
{
	node l;
	int ms;
	scanf("%d",&ms);
	l = (node)malloc(sizeof(lnode));
	initlist(l,ms);
	bubble(l);
	travel(l);
	return 0;
}