排序.cpp

对链表进行排序

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


//定义一个链表的结构体变量
typedef struct lnode
{int data;
struct lnode *next;
}lnode,*linklist;

//输出链表
void print(linklist head)
{linklist p;
printf("输出链表中的数据 \n");
p=head;
p=p->next;
if(head!=NULL)
do
{
	printf("%d ",p->data);
p=p->next;
}
while(p!=NULL);
printf("\n");
}

//链表操作的有关函数
//创建带有头节点的链表

linklist createlist()

{linklist head;
linklist p1,p2;

head=(linklist)malloc(sizeof(lnode));
p2=head;
p1=(linklist)malloc(sizeof(lnode));

scanf("%d",&p1->data);
while(p1->data!=32767)
{

 p2->next=p1;
p2=p1;
p1=(linklist)malloc(sizeof(lnode));
scanf("%d",&p1->data);
}

p2->next=NULL;

return head;
}


//利用链表排序
linklist  sort(linklist l)
{
	linklist h=l;
linklist p1,p2,q1,q2,p,q,p3,ha;
p=h->next;
p1=p->next;
h->next->next=NULL;



while(p1)
{q=h->next;
//要插位置的前驱
ha=h;
	while(q)
	{if(p1->data<q->data)
{
		p3=p1;
		p1=p1->next;
		p3->next=q;
		ha->next=p3;
 break;
}
	else {q=q->next;
	ha=ha->next;}
}



if(q==NULL)
{
	ha->next=p2=p1;
	p1=p1->next;
	p2->next=NULL;
	
}



}



return h;
}




void main()
{//lnode *la,*lb,*lc;
	linklist la,lb,lc;
	int n;
	while(1)
	{ printf("输入你所选的序号1表示继续做，0表示退出\n");
	scanf("%d",&n);
	if(n==0)
		break;
	else if(n==1)
	{
	printf("input the list 32767 end\n");
la=createlist();
la=sort(la);



print(la);
	}
	}
}