# 链表(线性表)

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

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

}

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

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

``````

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

}

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

while( p1 )
{
p2 = p1;
p1 = p1->next;