1

Подпрограмма создает неупорядоченную таблицу, а нужно, что бы она сразу создавала упорядоченную с помощью бинарного поиска.

Входные данные имеют вид: 123dh678 iphone 100

8символов - шифр, название продукта и количество произведенного продукта. Все это в main читается из файла и добавляется в таблицу. current_num_tables - количество элементов в таблице.

struct table
{
char code[9];
char name[255];
int numb;
};

Упорядочить думаю будет лучше и легче всего по numb (количество произведенного продукта)

Как я понимаю, нужно с помощью бинарного поиска определять индекс элемента, и вставлять его по индексу в массив. Если место для вставки этого элемента не пусто, то нужно сдвинуть все элементы до индекса на -1.

В общем, убрал подпрограмму table_add и вставляю сразу с помощью бинарного поиска при чтении из файла.

Работает правильно, но при совпадении (если code будет одинаковым, например th00tf00 apple 1 th00tf00 apple 50, то в таблице должно быть только th00tf00 apple 51, а появляется th00tf00 apple 51 th00tf00 apple 50)

while (fscanf(f, "%s %s %i", code, name, &numb) != EOF && current_num_tables < N)
{
    int pos = insert(numb, t, &current_num_tables);
    for (int i = 0; i < current_num_tables; ++i)
    {
        if (!strcmp(code, t[i].code))
        {
            t[i].numb += numb;
        }
    }
    strcpy(t[pos].code, code);
    strcpy(t[pos].name, name);
}

Вот так работает, но без учета совпадений.

while (fscanf(f, "%s %s %i", code, name, &numb) != EOF && current_num_tables < N)
{
    int pos = insert(numb, t, &current_num_tables);
    strcpy(t[pos].code, code);
    strcpy(t[pos].name, name);
}

static int insert(size_t value, struct table *array, int *length)
{

int first = 0;
int last = *length - 1;
int pos = -1;

if (*length == 0)
{
    array[0].numb = value;
    ++(*length);
    return 0;
}

while (first <= last) {

    int i = first + (last - first) / 2;

    if (value < array[i].numb) {
        last = i - 1;
    }
    else if (value > array[i].numb) {
        first = i + 1;
    }
    else {
        pos = i;
        break;
    }
}
if (pos < 0) {
    pos = first;
}

// Подвигаем хвост массива, чтобы освободить место под элемент.
memmove(array + pos + 1, array + pos, (size_t)(*length - pos) * sizeof(array[0].numb));

array[pos].numb = value;

++(*length);

return pos;
}
4
  • 1
    может вы имете в виду метод вставки 21 июн 2017 в 8:41
  • Бинарный поиск подразумевает использование уже отсортированного массива. С помощью него не отсортировать 21 июн 2017 в 8:53
  • В чем проблема с приведенным кодом? Можете привести пример входа, на котором он выдает некорректный результат? 22 июн 2017 в 3:12
  • 1
    @defaultlocale исправил большое количество кода и привел пример, на котором он не работает и почему, только не понимаю, как исправить это
    – Alexandr
    22 июн 2017 в 3:26

1 ответ 1

3

В функцию бинарного поиска вы должны передать указатель на массив структур, в который собираетесь что-то вставить, то есть

int binarysearch(int value_for_insert, struct table* t, int max_size)
{
/* ... */
}

Дословно:

int binarysearch(<что>, <куда>, <доколе>)

А "препод" не принимает ваш вариант не из-за этого, а скорее из-за того, что у вас по ошибке на строку, причем ошибки смысловые.

В функции add_table вы оставили поиск по code в уже отсортированную по полю numb таблице.

Что получается? Вы первый элемент вставляете нормально, еще парочку возможно тоже, имеете сортированную по numb таблицу, а затем приходит элемент с таким же code, и вы без всякого бинарного поиска втыкаете +numb в некий элемент, и ломаете свою сортированную таблицу, после чего бинарный поиск становится бесполезен - таблица то не упорядочена больше.

Решение: вставка элементов должна идти только по алгоритму бинарного поиска, что гарантирует всегда отсортированную таблицу. Если вам нужно добавить значение numb к элементу с таким же code - вы обязаны вынуть этот элемент из таблицы, изменить его, а только потом вставить обратно тем же бинарным поиском. Тогда алгоритмически будет все правильно, дело за реализацией.

Вторая явная ошибка здесь - сдвиг элементов. У вас же элемент - это структура, почему вы присваиваете в цикле только поле numb? Это как иметь список сотрудников с зарплатой N рублей, а при увольнении сотрудника его зарплата переходит предыдущему сотруднику по алфавиту. При найме вы получаете зарплату следующего по списку. Вы бы стали работать старшим менеджером за зарплату грузчика?

Посмотрите:

for (i = 1; i < index; i++)
{
    t[i].numb = t[i - 1].numb;
}

Решение: замените на перенос структуры через memcpy (подразумевается, что размер одного блока равен sizeof(*t) и не содержит динамических данных вроде указателей и т.д., иначе их нужно корректно клонировать):

for (i = 1; i < index; i++)
{
    /* void *memcpy(void *dst, const void *src, size_t n); */
    memcpy(t[i], t[i - 1], sizeof(*t));
}

Третий вопрос возникает сам собой, если посмотреть на код:

/* Куда сохраняется результат вызова 'binarysearch()'?
   По коду функции результат равен -1 в случае ошибки или индексу в массиве для сдвига и вставки */
binarysearch(_numb, ??? , current_num_tables);
/* Чему равно значение 'index' здесь, и какой в нем смысл? */
if (t[index].numb != NULL)
    for (i = 1; i < index; i++)
    {
        t[i].numb = t[i - 1].numb;
    }
/* Выше происходит сдвиг элементов (возможно, для освобождения места для нового элемента?). Ниже - увеличивается размер таблицы. А где вставка элемента, индекс которого мы получили в бинарном поиске, и для которого освобождали место? Зачем мы проводили этот бинарный поиск, если не используем его результат? */
current_num_tables++;
return;

Решение: нарисовать на бумажке таблицу, ее устройство и действия программы. Лучше таких рисунков сделать штук 5-6, для разных состояний таблицы (пустая, 3 элемента, 10 элементов, вставка в начало, в середину, в конец). Это позволит вам понять, что происходит.

Как видите, вопросов к коду больше, чем ответов на ваш изначальный вопрос. Это нормально. Мой вам совет - напишите по шагам сначала алгоритм (простым русским языком, на листочке), осмыслите его, представьте, что это не код программы, а вы сами будете его выполнять - и тогда вам станет понятно, каким должен быть код.

Удачи )

11
  • Ахах, столько ошибок из за того, что я просто взял подпрограмму добавления из своей предыдущей версии программы, реализованной на пузырьковой сортировке, в ней не было ошибок и она идеально работала. Вот её "препод" не принял. Если бы я сдал то, что написал в посте, то у меня скорее всего больше не было бы препода))
    – Alexandr
    21 июн 2017 в 11:41
  • Вы уверены, что следует использовать memcpy ? Аргумент типа struct table несовместим с параметром типа const void*.
    – Alexandr
    21 июн 2017 в 11:48
  • Вы правы, именно поэтому мы передаем не сам struct table, а указатель на него, сдвинутый на i и i-1 соответственно. В параметр binarysearch() мы же передаем struct table* t, указатель на тип, правильно? А к const void* можно привести любой указатель, собственно для этого void* и существует
    – wirtwelt
    21 июн 2017 в 14:32
  • А почему тогда не компилится? Выдает ошибку из за memcpy(t[i], t[i - 1], sizeof(*t));
    – Alexandr
    21 июн 2017 в 16:24
  • Какой компилятор и какую ошибку выдает?
    – wirtwelt
    21 июн 2017 в 16:51

Ваш ответ

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

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