0

Всем доброго времени суток))

Задача следующая: «Ввести предложения на русском в односвязный список, организованный в виде очереди (в списке должны храниться только адреса, а сами предложения размещаться в памяти отдельно). Определить предложение, в котором используется наибольшее количество различных букв русского алфавита, и сделать это предложение первым в списке. И исключить из списка предложение, в котором меньше всего различных букв. Разработать функцию, определяющую количество различные буквы, используемые в данной строке символов».

Прошу помощи с двумя пунктами:
1)Посмотрите функцию int CountAlpha() для поиска количества разных букв и скажите точно ли с ней все ок
2)Помогите с реализацией алгоритма сортировки односвязного списка по кол-ву разных букв в предложении(опять же предложения на русском языке). Хотя бы дайте наводку как и что нужно делать

Всем заранее спасибо за помощь :)

Код:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <locale.h>
#define LMES 80

typedef struct inform { // структура данных
    int index;
    char message[LMES];
} INFORM;

typedef struct list_elem { // структура элемента списка
    INFORM inform;
    struct list_elem* next;
} LEL;

void MakeList(void); // прототипы функций
LEL* AddElem(LEL* last);
void PrintList(void);
int CountAlpha();
LEL* Sort();
void FreeList(void);

LEL* list; // указатель на начало списка

void main(void){

    setlocale(LC_ALL, "rus");
    system("chcp 1251");

    MakeList(); // формирование списка

    PrintList(); // печать сформированного списка

    FreeList(); // освобождение ДП
}

// Функция формирования списка-очереди
void MakeList(void)
{
    puts("\n Входные данные (для завершения индекс - 0):\n");
    LEL* list_end = NULL; // указатель на последний элемент списку

    do { list_end = AddElem(list_end); } while (list_end != NULL);// цикл формирования списка
}

// Функция добавления нового элемента до хвоста списку
LEL* AddElem(LEL* last)
{
    LEL* pel; // указатель на новый элемент
    static int num = 1; // номер элемента, который вводиться
    pel = (LEL*)malloc(sizeof(LEL)); // выдиление ДП для элемента
    if (pel == NULL)
    {
        puts("\n Нет больше свободной памяти...\n Формирование списка завершено.");
        return NULL; // нет свободной ДП
    }
    printf("\n %d элемент: \nИндекс - ", num);
    scanf_s("%d", &pel->inform.index);
    rewind(stdin);

    if (pel->inform.index == 0) { // конец введения
        free(pel);
        return NULL;
    }
    printf("Предложение: ");
    gets_s(pel->inform.message);
    pel->next = NULL; // элемент будет последним в списке
    if (list == NULL) // если это первый элемент
        list = pel; // делаем его головой списка
    else
        last->next = pel; // иначе добавляем к последнему в списке
    num++;
    return pel;
}

// Функция вывода на экран списка
void PrintList(void)
{
    LEL* pel = list; int n = 0;
    puts("\n\n\t Сформированный список:\n");
    while (pel != NULL) {
        printf(" %d)%7d\t%-.65s\n", ++n, pel->inform.index, pel->inform.message);
        pel = pel->next;
    }
}

// Функция нахождения кол-ва уникальных букв в предложениях
int CountAlpha() {
    LEL* pel = list;
    char* p1, * p2;
    int count = 0, saveCount = 1;

    p1 = pel->inform.message;

    while (pel != NULL) {
        for (p1; *p1 != '\0'; p1++) {
            p2 = p1++;
            for (p2; *p2 != '\0'; p2++) {
                if (*p2 == *p1) {
                    saveCount = 0;
                }
                count += saveCount;
            }
        }
        return count;
        pel = pel->next;
    }
}

LEL* Sort() {
    ???
}

// Функция стирания всего списка
void FreeList(void)
{
    LEL* pel = list;
    while (pel != NULL) {
        list = list->next; // первым в списке становится следующий элемент
        free(pel); // удаление поточного элемента
        pel = list;
    }
    puts("\n\n Список вытерт. \n");
}
4
  • Ловите
    – avp
    14 мая 2022 в 21:23
  • 1
    Нарушено требование задачи "в списке должны храниться только адреса". Вы храните сами фразы, не их адреса. 15 мая 2022 в 8:26
  • 3
    В задаче не требуется упорядочивать список. Требуется только переставить самое "богатое" предложение первым. Это в десять раз проще сортировки. 15 мая 2022 в 8:34
  • Скорее всего от вас хотят чтобы вы динамически выделяли память под предложения в структуру списка struct list_elem { char* message; list_elem* next; }
    – DmitryK
    16 мая 2022 в 17:41

1 ответ 1

0

Ваша функция CountAlpha() не считает количество уникальных букв в предложении. Непонятно, что она считает. Проще всего это с делать с использованием контейнера unordered_map<> или map<> из стандартной библиотеки шаблонов. Но если без использования STL, то как-то так:

int CountAlpha(char *str) // передаем указатель на с-строку (с 0 в конце)
// int CountAlpha(inform &inf) // можно передать по ссылке или указателю объект класса inform 
{
// массив для признаков наличия буквы в предложении
int counts[33] = { 0, 0, 0, 0, 0, 0, 0, 0, ..... ,0};
// массивы с буквами русского языка для строчных и заглавных
char a_symb[33] = {'А', 'Б', ..... ,'Я'};
char b_symb[33] = {'а', 'б', ..... ,'я'};

char *s = str; // указатель на начало строки, в которой считаем уникальные буквы
for( ; s != 0; s++)  // перебираем строку до нулевого символа для с-строк, или можно итерироваться до длины строки
   for(int i=0; i<33; i++) // проходим по массиву букв русского языка, чтобы определить есть ли эта буква в предложении 
      if(*s == a_symb[i] || *s == b_symb[i]) // если встретили букву то признак = 1 
         { counts[i] = 1;
           break;   // или `i=33;` чтобы выйти из внутреннего цикла
         }

int letter_count = 0;
// проходим по массиву признаков, и подсчитываем количество уникальных букв в строке
for(int i=0; i<33; i++)
   letter_count += counts[i];

return letter_count;
} 

Да, и не забудьте про абсолютно правильные комментарии @Stanislav Volodarskiy

7
  • Не нужен тут цикл от 0 до 33 и все эти массивы.. Достаточно одной 32-бит переменной (по биту на букву, адресовать биты надо по индексу буквы. Для каждой буквы смотрим ее бит. Если 0, то увеличиваем счетчик и ставим бит в 1. Ну, если считать Ё и Е разными, то придется взять 64-бит переменную).
    – avp
    16 мая 2022 в 15:24
  • @avp А зачем? Чтобы съэкономить 124 байта? Ну возьмите вместо int тип int8_t. Массив станет 36 байт (с выравниванием). А человеку, который только С начал изучать и не дошел до классов и STL в задаче на полчаса времени рассказывать про битовые поля мне кажется незачем. А вообще варианты есть - можно по-быстрому свой простенький unordered_map<> написать. Или вычислять коды букв. Или ещё что-нибудь.
    – DmitryK
    16 мая 2022 в 16:50
  • Для красоты (в широком смысле). А то с такими рассуждениями мы и дошли до того, что комп с гигабайтом памяти уже практически нельзя использовать (мало памяти). А также при таком подходе много лишних операций (поиск кода буквы в цикле, вместо вычисления его несколькими инструкциями (и вот уже гигагерцев не хватает). Ну и т.д. и т.п. ....
    – avp
    16 мая 2022 в 17:01
  • Для красоты - согласен! Но красота понятие относительное! :) У каждого она своя.
    – DmitryK
    16 мая 2022 в 17:14
  • Это верно. Задумайтесь только, в компанию с кем вы сами себя засовываете
    – avp
    16 мая 2022 в 17:16

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.