1

Доброе время суток. Помогите пожалуйста алгоритмом. Нужно напечатать фамилии спортсменов, имеющих худший результат (по одному для каждого вида спорта). Виды спорта естественно могут повторятся. И можно считать, что список уже сформирован.

typedef struct SPORTSMAN {
    char firstName [10];
    char lastName [20];
    int  result;
    char sport[20];
    struct SPORTSMAN *next;
} lelem;
10
  • А в чём проблема? Обходите список, запоминаете для просмотренного куска текущий наихудший результат и фамилию спортсмена с таким результатом. При рассмотрении следующего спортсмена обновляете данные, если надо. Какая часть алгоритма не получается?
    – VladD
    Commented 15 апр. 2013 в 21:19
  • 2
    @VladD, сдаётся мне, что это слишком просто :) А чуть сложней если у нас не отдельный список на каждый вид спорта, а все в одном. Здесь я бы сделал 2 прохода: на первом посчитал бы количество разных видов, потом выделил бы память для сохранения результатов по каждому, и потом уже по первой схеме.
    – user6550
    Commented 15 апр. 2013 в 22:24
  • 1
    @klopp: ваша правда, не заметил разные виды спорта в условии.
    – VladD
    Commented 15 апр. 2013 в 22:35
  • 1
    Сортируем список по ключу (sport, result). Далее пробегаемся по списку, и после каждой смены вида спорта выводим имя.
    – dzhioev
    Commented 15 апр. 2013 в 23:15
  • Сортировки списков до памяти жручи... Сейчас покажу грязный хак, памяти требует не больше N * sizeof(указатель) :)
    – user6550
    Commented 16 апр. 2013 в 0:26

2 ответа 2

3

Аналогичное хулиганство, основанно на man tsearch.

Идея крайне проста. Организуем двоичное дерево по видам спорта, т.е. для каждого вида спорта в дереве будет один узел. Другими словами это множество видов спорта, представленное ссылками на результаты

Читаем список результатов. Перебираем его и каждый результат ищем в дереве. Если такого спорта еще нет, то помещаем в дерево адрес данного выступления. (Я так понимаю, что struct SPORTSMAN - это одно выступление). Иначе, если новый результат хуже уже запомненного, то заменяем хранящийся в дереве адрес, на адрес текущего выступления.

В конце просто обходим дерево в алфавитном порядке названий видов спорта и печатаем самые худшие результаты.

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

#include <search.h>

#define FIRST_NAME_SZ   10
#define LAST_NAME_SZ    20
#define SPORT_NAME_SZ   20

struct SPORTSMAN 
{
    char    firstName[FIRST_NAME_SZ];
    char    lastName[LAST_NAME_SZ];
    int     result;
    char    sport[SPORT_NAME_SZ];
    struct  SPORTSMAN *next;
};

struct link1list {
  struct SPORTSMAN *head, *tail;
};

struct link1list get_results (); // читает список SPORTSMAN

// пара функций для бинарного дерева из <search.h>
// сравнение названий видов спорта (вызов из tsearch())
static int 
cmpsport (const void *s1, const void *s2)
{
  struct SPORTSMAN *sp1 = *(struct SPORTSMAN **)s1, 
    *sp2 = *(struct SPORTSMAN **)s2;

  return strcmp(sp1->sport, sp2->sport);
}

// печать дерева в естественном порядке (вызов из twalk())
static void
printres (const void *p, const VISIT which, const int depth)
{
  struct  SPORTSMAN *s = **(struct SPORTSMAN ***)p;

  if (which == leaf || which == postorder)
    printf ("%s \t\t%-10s %d\n", s->sport, s->firstName, s->result);
}

int
main ()
{
  void *sptree = 0; // дерево по видам спорта, каждый узел адресует худшего 
  struct link1list list = get_results(); // прочтем из stdin весь список 
  struct SPORTSMAN *p, **sportref, ***treeref;

  puts("\nAll results");
  for (p = list.head; p; p = p->next) {
    printf ("%s %s :\t %s\t %d\n",
        p->firstName, p->lastName, p->sport, p->result);

    // добавим в дерево новый спорт с ссылкой на худший результат
    sportref = (struct SPORTSMAN **)malloc(sizeof(void *));
    *sportref = p;
    treeref = (struct SPORTSMAN ***)tsearch(sportref, &sptree, cmpsport);

    if (*treeref != sportref) { // такой спорт уже был
      if ((*(*treeref))->result > p->result)
        **treeref = p;          // заменим  на адрес худшего
      free(sportref);
    }
  }
  puts(" Low results by sport");

  twalk(sptree, printres);

  return 0;
}

IMHO довольно компактно и должно быстро работать.

Функцию чтения имен и результатов в список приводить не стал, она элементарная.

1
  • Спасибо конечно, но это сложновато для моего уровня. Буду разбирать вариант kloppa
    – RubyNub
    Commented 28 апр. 2013 в 16:30
2

Прошу относиться к этому как к хулиганству :)

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

#define FIRST_NAME_SZ   10
#define LAST_NAME_SZ    20
#define SPORT_NAME_SZ   20

struct SPORTSMAN 
{
    char    firstName[FIRST_NAME_SZ];
    char    lastName[LAST_NAME_SZ];
    int     result;
    char    sport[SPORT_NAME_SZ];
    struct  SPORTSMAN *next;
};

static struct SPORTSMAN *
add_to_list ( struct SPORTSMAN * source,
                const char * firstName, const char * lastName, 
                int result, const char * sport )
{
    struct SPORTSMAN * data = malloc( sizeof(struct SPORTSMAN) );
    memset( data, 0, sizeof(struct SPORTSMAN) );
    strncpy( data->firstName, firstName, FIRST_NAME_SZ-1 );
    strncpy( data->lastName, lastName, LAST_NAME_SZ-1 );
    strncpy( data->sport, sport, SPORT_NAME_SZ-1 );
    data->result = result;
    if( source ) source->next = data;
    return data;
}

int main()
{
    struct  SPORTSMAN * head;
    struct  SPORTSMAN * list;
    struct  SPORTSMAN * item = NULL;
    struct  SPORTSMAN ** result;
    size_t  i, sz = 1;

    list = add_to_list( NULL, "first1", "last1", 1, "moto" );
    head = list;
    list = add_to_list( list, "first2", "last2", 2, "velo" );
    list = add_to_list( list, "first3", "last3", 3, "moto" );
    list = add_to_list( list, "first4", "last4", 4, "velo" );
    list = add_to_list( list, "first5", "last5", 5, "golf" );
    list = add_to_list( list, "first6", "last6", 6, "velo" );
    list = add_to_list( list, "first7", "last7", 7, "moto" );
    list = add_to_list( list, "first8", "last8", 8, "moto" );
    list = add_to_list( list, "first9", "last9", 9, "golf" );
    list = add_to_list( list, "first10", "last10", 10, "golf" );

    list = head;
    /* 
        грязный хак: мы не считаем сколько видов спорта всего, 
        а просто увеличиваем счётчик при смене вида. в результате
        получим больше, но не больше размера списка. плюс в том,
        что не надо нигде сохранять сосчитанные виды спорта 
    */
    while( list )
    {
        if( item )
        {
            if( strcmp( item->sport, list->sport ) )
            {
                sz++;
            }
        }
        item = list;
        list = list->next;
    }

    /* calloc() же обнуляет? если да, то пропустим это */
    result = calloc( sz, sizeof(struct SPORTSMAN *) );

    /*
        основной цикл
    */
    list = head;
    while( list )
    {
        for( i = 0; i < sz; i++ )
        {
            if( !result[i] )
            {
                /* заносим вид спорта, которого пока нет */
                result[i] = list; break;
            }
            if( !strcmp(result[i]->sport, list->sport) )
            {
                /* наш спорт? сравниваем результаты и отваливаемся */
                if( result[i]->result > list->result )
                {
                    result[i] = list;
                }
                break;
            }
        }
        list = list->next;
    }

    for( i = 0; i < sz; i++ )
    {
        if( !result[i] ) break;
        printf
        ( 
            "[%s] %d, %s %s\n", 
            result[i]->sport, result[i]->result, 
            result[i]->firstName, result[i]->lastName 
        );
    }

    list = head;
    while( list )
    {
        head = list;
        list = list->next;
        free( head );
    }
    free( result );
    return 0;
}
2
  • Ну первый цикл посчитает одинаковый спорт только в случаи совпадения у текущего со следующим или я что-то не догоняю?
    – RubyNub
    Commented 28 апр. 2013 в 20:27
  • Первый цикл нужен для сокращения размера памяти, в котором хранится список указателей. Проще было бы взять размер исходного списка, но так можно чуть-чуть сэкономить :) А точно считать кол-во видов спорта я не стал по одной причине: тогда пришлось бы заводить ещё один список для хранения уже посчитанных вариантов. Это и дольше, и памяти больше ушло бы.
    – user6550
    Commented 28 апр. 2013 в 20:33

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.