14-数据结构-有序链表排序

问题：

给你一个链表，然后去进行排序，并输出。

思路：

1. 排序时，类似于冒泡排序。这里则定义两个链表指针，一个指向第一位，一个指向第一位的后一位。
2. 由于需要排序的是数据，因此定义一个中间变量 int temp，用于后面的数据域比较排序
3. 两层循环，外循环是指向第一位的指针，每次遍历，都会给一个数，于后面的进行比较，外循环遍历开始时，先让第二位的指针，指向第一位的后方。随后进入第二层循环，该层就是进行交换操作了，操作完后，内循环指针后移，让另一个数与外循环的那一个数比较，直到遍历结束，跳到外循环，此时外循环指针也后移，换下一个数与内循环的数字比较，

代码如下：

#include <stdio.h>
#include <malloc.h>
//单链表的应用
typedef struct lnode
{
	int data;
	lnode *next;
}lnode,*linklist;
bool inilist(linklist &l)
{
	if(l==NULL)
	return false;
	
	l->next=NULL;
	return true;
}
linklist creatlist(linklist &l)
{
	l=(linklist)malloc(sizeof(lnode));
	l->next=NULL;
	lnode *s;
	int x;
	printf("请输入需要添加值\n");
	scanf("%d",&x);
	while(x!=9999)
	{
		s=(lnode *)malloc(sizeof(lnode));
		s->data=x;
		s->next=l->next;
		l->next=s;
		printf("请再次输入下一个数据，直到输入9999为止\n");
		scanf("%d",&x);
	}
	return l;
}

void paixulist(linklist &l)
{
	
	linklist p=l->next;	//第一个指针指向第一个位置 
	linklist q=NULL;  	//第二个指针指向第一个指针的后继 
	int temp=0;   		//用来交换数据的中间变量 
	while(p!=NULL)		//当第一个结点不为空时 ，开始遍历第一个数，从第一个数进行比较 
	{	q=p->next;		//q指向第一个结点的后继结点 
		while(q!=NULL)	//拿外循环的那个数字，与其后面的数字挨个遍历，直到q遍历完 
		{
		
			if(q->data < p->data)//数据域比较 ，从而交换 
			{
				temp=p->data;
				p->data=q->data;
				q->data=temp;	
			}
			q=q->next;//第一个数与第二个数比较结束，开始q指针往后移，开始第一个数与第三个数比较。 
		}
		p=p->next;   //第一个数与其他数比较完毕，p指针后移，开始下个数字，与后面的挨个比较 
	}
	
	
}
void printlist(linklist &l)
{
	
	lnode *p=l->next;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
	
}
   
 
int main()
{
	linklist l;
//	inilist(l);
	l=creatlist(l);
	printlist(l);
	paixulist(l);
	//pansheng(l);
	printlist(l);
	return 0;
}