Ответы пользователя по тегу Структуры данных
  • Как присвоить динамическому массиву типа void* значение в Си?

    @res2001
    Developer, ex-admin
    Нельзя выделить память для произвольного типа, т.к. размер произвольного типа - произвольный. Память всегда выделяется конкретного размера.

    В вашем примере вы выделяете память для двух указателей (void*). На всех распространенных платформах указатель, не важно на какой тип он ссылается, имеет один и тот же размер.
    Нельзя сделать разъименование void*, т.к. это указатель с неопределенным типом - компилятор не знает какого типа данные лежат по адресу в указателе, а следовательно не может с ними корректно работать. Для нормальной работы нужно привести указатель к какому-нибудь типу и потом уже можно делать разъименование (ваш 3 пример).

    Ваш пример не корректен для х64 платформы, т.к. sizeof(void*) там 8 байт, а sizeof(int) - 4 байта.
    Вы mallocом выделяете 16 байт памяти (2 указателя), а в 3 присваивании (которое работает) присваиваете значение 10 старшей половине первого указателя. В общем выглядит как бред.
    Для х32 - корректен, т.к. тут sizeof(void*) == sizeof(int)

    Для копирования двух массивов произвольного типа и размера, нужно знать размер массива в байтах (не в элементах). Можно не знать тип, но знать размер необходимо - иначе ничего не поучится. Выделяете память заданного размера, приводите указатель к char* и побайтово копируете (memcpy).
    Приводить к int* и копировать intы в этом случае нельзя, т.к. массив может быть, например 3 байта или 33, тогда при копировании через приведение к int* вы неминуемо выйдете за границу массива.
    Ответ написан
    Комментировать
  • Для чего внутри связного списка нужен массив?

    @res2001
    Developer, ex-admin
    Видимо планируется хранить список на медленном устройстве хранения (на диске). Тогда такое построение связного списка вполне оправдано - за одно чтение можно прочитать несколько блоков данных.
    Возможно примерно таким же способом хранятся таблицы в СУБД. Называться это может по разному.
    Так же в СУБД часто применяют b-tree для хранения индексов, в этом дереве то же хранится несколько элементов данных в одном узле.
    Ответ написан
    Комментировать
  • Что лучше использовать словарь или массив или связный список?

    @res2001
    Developer, ex-admin
    Надо знать достоинства и недостатки каждого контейнера и решить какие требования к контейнеру предъявляет конкретная задача (какие операции контейнера будут критичными для конкретной задачи).

    1. Массив (не отсортированный)
    Плюсы: доступ к элементу по индексу - O(1)
    Минусы: произвольный поиск - O(n); вставка, удаление - O(n) требуется перевыделение памяти и копирование всего контейнера
    2. Список
    Плюсы: вставка - если известно место вставки O(1); удаление - если известен удаляемый элемент O(1)
    Минусы: доступ по индексу, произвольный поиск - O(n);
    3. Словарь
    Может быть внутри реализован как дерево или как хеш-таблица. Как реализованы в питоне стандартный объект не знаю.
    3.1. Дерево. Обычно используется какой-то вариант сбалансированных двоичных деревьев поиска (красно-черное и т.п.)
    Плюсы: произвольный поиск, вставка, удаление - O(log(n))
    Минусы: для обеспечения сбалансированности дерева используются дополнительные "внутренние" операции с деревом, что увеличивает время каждой отдельно взятой операции вставки и удаления. Эти операции обычно достаточно "легкие" и константные по времени.
    3.2. Хеш-таблица
    Плюсы: произвольный поиск, вставка, удаление - O(1);
    Минусы: вставка и удаление могут в некоторых случаях приводить к перевыделению памяти и полному копированию и/или к пересчету хешей в зависимости от реализации.

    Как видите, нет универсального 100% подходящего контейнера на все случаи жизни. У всех есть свои плюсы и минусы.
    Ответ написан
    Комментировать
  • Применим ли симметричный обход для не бинарных деревьев?

    @res2001
    Developer, ex-admin
    Просто размышление.
    Логика подсказывает, что такой подход применяется, когда нужно не просто обойти все дерево как-нибудь, а обойти в порядке сортировки дерева (или в обратном порядке).

    Конечно вы можете применять такое и с деревьями с большим количеством узлов. Но это будет уже, скорее всего, не симметричный обход, потому что симметрей чисто визуально тут уже и не пахнет, но алгоритмическе все то же самое. В некоторых конфигурациях деревьев с количеством дочерних узлов больше 2, обход вполне может остаться симметричным (когда дочерних узлов четное количество и родителя проверяете по середине).

    На каком именно этапе проверять родителя в таком случае зависит от того как сортируются потомки относительно родителя в данном конкретном случае. Т.е. в бинарном дереве левый потомок меньше родителя, а правый больше - это правило и создает упорядоченность при обходе. Если узлов больше 2, то нужно определить аналогичное правило упорядоченности для потомков относительно родителя. в соответствии с этим правилом и совершать обход.
    Ответ написан
    1 комментарий
  • Как организовать концепцию столбца?

    @res2001
    Developer, ex-admin
    Кроме "переноса строки", должен быть еще и "разделитель колонок". Дальше все просто - после первого разделителя колонок идет второй столбец, и т.д.
    Ответ написан
    Комментировать
  • Структура студент возникла проблема кто может помочь?

    @res2001
    Developer, ex-admin
    Все более-менее нормально.
    Уберите cin.ignore();
    Замените getline(cin,FIO); на cin >> FIO;
    Ответ написан
  • Есть ли у кого маленькая шпаргалка по перебору связного списка?

    @res2001
    Developer, ex-admin
    Обычно
    list.next == null - значит текущий элемент (list) - последний в списке
    list == null - нет никакого списка, возможно ошибка

    Оба варианта могут употребляться в одной и той же реализации в разных ситуациях.
    Кроме того могут быть нюансы и list.next == null в данной конкретной реализации списка является ошибкой и т.п.
    Ответ написан
    Комментировать
  • Что не так с кодом? Как правильно делать?

    @res2001
    Developer, ex-admin
    Кодировка консоли в винде по умолчанию cp866 (а не 1251 как многие думают). Но можно переключить.
    Для простоты сохраните ваши исходники в 866 кодировке.
    setlocale работает только на вывод. Для ввода используйте cout.imbue.

    Переключать кодировку консоли из утилиты - дурной тон. Для студенческой лабы это еще терпимо, но нормальная русская консольная утилита должна уметь правильно выводить текст не зависимо от того какая кодировка установлена в консоли 866 или 1251. Например, почти все родные виндовые консольные утилиты с этим справляются успешно.

    По уму делать примерно по следующей схеме:
    1.Исходники в UTF8
    2.Все строковые константы с префиксом L"string"
    3.Строки хранить в wchar_t
    4.Определять кодировку консоли для ввода и вывода и перекодировать свои юникодные строки в нужную кодировку и только потом выводить или после ввода перекодировать в UTF8. Для перекодирования в WinAPI все есть, но без windows.h не обойтись.
    Ответ написан
    Комментировать
  • С++ - как отсортировать структуру?

    @res2001
    Developer, ex-admin
    Реализуйте в структуре конструктор копирования и/или копирующий оператор присваивания, и сортируйте пузырьком (т.к. самая простая реализация соритровки). Можно еще реализовать несколько функций сравнения по разным атрибутам и передавать эти функции в пузырек (чтоб можно было делать сортировку по разным атрибутам с помощью одной функции сортировки).

    По коду:
    1.Вы начинаете писать на С++, а потом перескакиваете на Си (puts, printf) ...
    2.В struct student поля surname и gr объявлены как char, а в коде вы их используете как си-строки - это абсолютно разные вещи.
    3.Вы не правильно используете функцию puts. В таком виде у вас программа не соберется. Посмотрите документацию.

    Возможно что-то еще ...
    Ответ написан
    Комментировать