2205: 链表(线性表)

题目描述

（线性表）设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间）
(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;
}

解析

暂无