题目描述
(线性表)设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相等的整数存在),试编写能实现下列功能的算法 :(要求用最少的时间和最小的空间)
(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
参考代码
#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("%dn", 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;
}
解析
暂无