Как отсортировать односвязный список на Си?
Всем доброго времени суток))
Задача следующая: «Ввести предложения на русском в односвязный список, организованный в виде очереди (в списке должны храниться только адреса, а сами предложения размещаться в памяти отдельно). Определить предложение, в котором используется наибольшее количество различных букв русского алфавита, и сделать это предложение первым в списке. И исключить из списка предложение, в котором меньше всего различных букв. Разработать функцию, определяющую количество различные буквы, используемые в данной строке символов».
Прошу помощи с двумя пунктами:
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");
}
Ответы (1 шт):
Ваша функция 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