链表排序(线性表)

链表排序(线性表)

时间： 1ms        内存：128M

描述：

设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。

输入：

1 4 6 23 45 14 34 78 45 9

输出：

1 4 6 9 23 45 14 34 78 45

示例输入：

11 44 63 23 45 14 34 78 45 19

示例输出：

11 14 19 44 63 23 45 34 78 45 

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t;
struct date
{
	int num;
	struct date *next;
};
struct date * creat(int *p)
{
	struct date *head;
	struct date *p1,*p2;
	int t1=0,flog=0;
	char ch;
	t=0;
	t1++;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(scanf("%d",&p1->num))
	{
		scanf("%c",&ch);
		if(ch=='\n')
			flog=1;
		t1++;
		t++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
		if(flog==1)
			break;
	}
	p2->next=NULL;
	*p=t1;
	return (head);
}

void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}


int main()
{
	struct date *p,*p1,*p2,*p3,*p4,*p5;
	int m,a,t1=0;
	p=creat(&m);
	p1=p;
	while(p1)
	{
		p2=p1;
		p1=p1->next;
	}
	a=p2->num;
	m-=3;
	p1=p;
	while(m--)
		p1=p1->next;
	p1->next=NULL;
	p1=p;
	p3=p2;
	p4=p2;
	while(p)
	{
		if(p->num>a)
		{
			p=p->next;
			p3->next=p1;
			p1->next=NULL;
			p1=p;
			p3=p3->next;
		}
		else
		{
			t1++;
			if(t1==1)
			{
				p=p->next;
				p1->next=p2;
				p2=p1;
				p1=p;
				p5=p2;
			}
			else
			{
				p=p->next;
				p1->next=p4;
				p5->next=p1;
				p1=p;
				p5=p5->next;
			}
		}
	}
	print(p2);
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t;
struct date
{
	int num;
	struct date *next;
};
struct date * creat(int *p)
{
	struct date *head;
	struct date *p1,*p2;
	int t1=0,flog=0;
	char ch;
	t=0;
	t1++;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(scanf("%d",&p1->num))
	{
		scanf("%c",&ch);
		if(ch=='\n')
			flog=1;
		t1++;
		t++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
		if(flog==1)
			break;
	}
	p2->next=NULL;
	*p=t1;
	return (head);
}

void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}


int main()
{
	struct date *p,*p1,*p2,*p3,*p4,*p5;
	int m,a,t1=0;
	p=creat(&m);
	p1=p;
	while(p1)
	{
		p2=p1;
		p1=p1->next;
	}
	a=p2->num;
	m-=3;
	p1=p;
	while(m--)
		p1=p1->next;
	p1->next=NULL;
	p1=p;
	p3=p2;
	p4=p2;
	while(p)
	{
		if(p->num>a)
		{
			p=p->next;
			p3->next=p1;
			p1->next=NULL;
			p1=p;
			p3=p3->next;
		}
		else
		{
			t1++;
			if(t1==1)
			{
				p=p->next;
				p1->next=p2;
				p2=p1;
				p1=p;
				p5=p2;
			}
			else
			{
				p=p->next;
				p1->next=p4;
				p5->next=p1;
				p1=p;
				p5=p5->next;
			}
		}
	}
	print(p2);
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。