链表(线性表)

链表(线性表)

时间: 1ms        内存:128M

描述:

(线性表)设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相等的整数存在),试编写能实现下列功能的算法 :(要求用最少的时间和最小的空间)
(1)确定在序列中比正整数x大的数有几个(相同的数只计算一次);
(2) 在单链表将比正整数x小的数按递减次序排列;

输入:

输入长度:13

输入数据:4 5 7 7 8 10 11 15 15 16 17 20 20

输入x:10

输出:

5

8 7 7 5 4

示例输入:

7
1 2 3 4 5 6 6
4

示例输出:

2
3 2 1 

提示:

参考答案(内存最优[752]):

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

struct stu *create( int num );
struct stu *res( struct stu *head );

struct stu
{
	int n;
	struct stu *next;
};

int main()
{
	int num1, num2;
	int i;
	int sum, rep = -1;
	struct stu *p1, *p2;

	scanf("%d", &num1);
	p1 = create(num1);
	scanf("%d", &num2);
	p2 = res(p1);
	p1 = p2;

	for( i = 0, sum = 0; i < num1-1; i++ )
	{
		if( p1->n > num2 &&p1->n != rep )
		{
			rep = p1->n;
			sum++;
		}
		p1 = p1->next;
	}
	printf("%d\n", sum);
	p1 = p2;
	while( p1 )
	{
		if( num2 > p1->n )
		{
			printf("%d ", p1->n);
		}
		p1 = p1->next;
	}
	printf("\n");
	return 0;
}

struct stu *create(int num)
{
	struct stu *head, *p1, *p2;
	int i;

	p1 = (struct stu *)malloc(sizeof(struct stu));
	head = NULL;
	for( i = 0; i < num; i++ )
	{
		if( NULL ==head )
		{
			head = p1;
			p2 = p1;
		}
		else
		{
			p2->next = p1;
			p2 = p1;
		}
		scanf("%d", &p1->n);
		p1 = (struct stu *)malloc(sizeof(struct stu));
	}
	p2->next = NULL;
	
	return head;

}

struct stu *res( struct stu *head )
{
	struct stu *p1, *p2;
	p1 = head;
	head = NULL;

	while( p1 )
	{
		p2 = p1;
		p1 = p1->next;
		p2->next = head;
		head = p2;
	}
	return head;
}

参考答案(时间最优[0]):

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

struct stu *create( int num );
struct stu *res( struct stu *head );

struct stu
{
	int n;
	struct stu *next;
};

int main()
{
	int num1, num2;
	int i;
	int sum, rep = -1;
	struct stu *p1, *p2;

	scanf("%d", &num1);
	p1 = create(num1);
	scanf("%d", &num2);
	p2 = res(p1);
	p1 = p2;

	for( i = 0, sum = 0; i < num1-1; i++ )
	{
		if( p1->n > num2 &&p1->n != rep )
		{
			rep = p1->n;
			sum++;
		}
		p1 = p1->next;
	}
	printf("%d\n", sum);
	p1 = p2;
	while( p1 )
	{
		if( num2 > p1->n )
		{
			printf("%d ", p1->n);
		}
		p1 = p1->next;
	}
	printf("\n");
	return 0;
}

struct stu *create(int num)
{
	struct stu *head, *p1, *p2;
	int i;

	p1 = (struct stu *)malloc(sizeof(struct stu));
	head = NULL;
	for( i = 0; i < num; i++ )
	{
		if( NULL ==head )
		{
			head = p1;
			p2 = p1;
		}
		else
		{
			p2->next = p1;
			p2 = p1;
		}
		scanf("%d", &p1->n);
		p1 = (struct stu *)malloc(sizeof(struct stu));
	}
	p2->next = NULL;
	
	return head;

}

struct stu *res( struct stu *head )
{
	struct stu *p1, *p2;
	p1 = head;
	head = NULL;

	while( p1 )
	{
		p2 = p1;
		p1 = p1->next;
		p2->next = head;
		head = p2;
	}
	return head;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注