Алгоритм сортировки произвольного количества слов (в алфавитном порядке) с использованием struct в качестве «базы данных» - PullRequest
Новая
       9

Алгоритм сортировки произвольного количества слов (в алфавитном порядке) с использованием struct в качестве «базы данных»

0 голосов
/ 23 мая 2019

Так что я должен выполнить алгоритм сортировки как домашнее задание CS.

Он должен прочитать произвольное количество слов, каждое из которых заканчивается на \ n.После того, как он прочитает «.», Он должен напечатать слова в алфавитном порядке.

Например: ВХОД: яблоко собака австрия Яблоко

ВЫХОД: яблоко яблоко австрийская собака

Iхочу сохранить слова в структуре.Я думаю, что для работы с произвольным числом слов я должен создать массив структур.

До сих пор я пытался создать структуру typedef только с одним членом (строкой) и планировал создатьмассив структур из этого, в который я затем сохраню каждое из слов.

Что касается "случайности" количества слов, я хотел установить тип структуры в main после выяснения, сколькослова были написаны, а затем сохранены каждое слово в каждом элементе массива структуры.

Моя проблема: 1. Я не знаю, как узнать количество слов.Единственное, что я попробовал, - это создание функции, которая подсчитывает, сколько раз происходило '\ n', хотя это не очень хорошо работало.

Что касается структуры данных, я придумал, что структура имеет толькоодин строковый член: 

typedef struct{
char string[MAX];
}sort;

затем в основной функции я сначала читаю количество слов, которые должны прийти (не фактическое назначение, а только в целях обеспечения работы кода)

и после"len" Я объявил переменную типа sort: 

int main(){
/*code, scanf("%d", &len) and stuff*/
sort sort_t[len];

for(i = 0; i < len; i++){
    scanf("%s", sort_t[i].string);
}

Вопрос: Является ли такая вещь "законной" и я использую хороший подход?

Q2: Как мне добраться дознать количество слов для хранения (для массива структур), прежде чем я начну их хранить?

1 Ответ

0 голосов
/ 24 мая 2019

ИМХО, идея резервирования одинакового максимального хранилища для каждой строки немного расточительна.Вероятно, вам лучше придерживаться динамических NUL-концевых строк, как это обычно делается в C-коде.Это то, что библиотека C поддерживает лучше всего.

Что касается управления неизвестным количеством строк, у вас есть выбор.Возможность 1 состоит в том, чтобы использовать связанный список, как упомянуто Ксавье.Возможно, это наиболее элегантное решение, но отладка может занять много времени, и в конечном итоге вам нужно преобразовать его в массив, чтобы использовать один из распространенных алгоритмов сортировки.

Возможность 2 - использовать что-то похожеев C ++ std :: vector объект.Скажем, задача выделения памяти делегирована некоторому объекту «bag».Код, работающий с «bag», имеет монополию на вызов функции realloc () , упомянутой Владом.Ваша основная функция вызывает только bag_create () и bag_put (bag, string) .Это менее изящно, но, вероятно, проще понять.

Поскольку вы сосредоточены на алгоритме сортировки, я бы предпочел использовать подход № 2.Вы можете использовать фрагмент кода ниже в качестве отправной точки. 

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

typedef struct {
    size_t    capacity;
    size_t    usedSlotCount;
    char**    storage;
} StringBag;


StringBag* bag_create()
{
    size_t initialSize = 4;  /* start small */
    StringBag*   myBag = malloc(sizeof(StringBag));

    myBag->capacity      = initialSize;
    myBag->usedSlotCount = 0;
    myBag->storage       = (char**)malloc(initialSize*sizeof(char*));

    return myBag;
}

void bag_put(StringBag* myBag, char* str)
{
    if (myBag->capacity == myBag->usedSlotCount) {
        /* have to grow storage */
        size_t  oldCapacity = myBag->capacity;
        size_t  newCapacity = 2 * oldCapacity;
        myBag->storage = realloc(myBag->storage, newCapacity*sizeof(char*));
        if (NULL == myBag->storage) {
            fprintf(stderr, "Out of memory while reallocating\n");
            exit(1);
        }
        fprintf(stderr, "Growing capacity to %lu\n", (unsigned long)newCapacity);
        myBag->capacity = newCapacity;
    }

    /* save string to new allocated memory, as this */
    /* allows the caller to always use the same static storage to house str  */

    char* str2 = malloc(1+strlen(str));
    strcpy(str2, str);
    myBag->storage[myBag->usedSlotCount] = str2;
    myBag->usedSlotCount++;
}


static char inputLine[4096];


int main()
{
    StringBag*  myBag = bag_create();

    /* read input data  */
    while(scanf("%s", inputLine) != EOF) {
        if (0 == strcmp(".", inputLine))
            break;
        bag_put(myBag, inputLine);
    }

    /* TODO: sort myBag->storage and print the sorted array */

}
...