Тип реализации используется?
Есть вопрос, который я пытался решить какое-то время, но мне сложно понять правильную реализацию для него. Если мы напишем программу, которая будет манипулировать тысячами записей, каждая из которых содержит название продукта, тип, серийный номер, розничную цену и т. Д. В каждом нижеприведенном случае объясните, какой абстрактный тип данных (очередь, стек, несортированный и отсортированный список) вы бы использовали и какая реализация (массив или связанная структура). Кратко обоснуйте свой выбор.
1) Записи будут извлечены в том же порядке, в котором они были сохранены. Заранее неизвестно, сколько записей будет обработано и как.
- Для этой цели я предпочитаю Unsorted list, в котором использовалась реализация связанного списка, потому что мы не знаем количество записей в начале, и данные будут извлекаться по мере их хранения, следовательно, они должны быть связаны, что также возможно с помощью ADT, такого как Queue или Stack но они используют реализацию массива, поэтому возникает проблема выделения памяти.
2) Все записи будут вставлены в начале, один раз и в произвольном порядке. Они будут получены очень часто, на основе серийного номера.
- Даже в случае печати всех данных записей за один раз это будет возможно с помощью списка Unsorted.
3) По мере необходимости будет вставлено большое, но неизвестное количество записей о продуктах. Они редко будут найдены по отдельности. Большинство операций состоит из обработки всех записей за один раз, например, печати всех.
- Однако здесь отсортированный и Unsorted list был более эффективен в использовании, но я предпочитаю Unsorted list, потому что для сортировки требуется время, что снижает его эффективность.
Что, вы парни, думаете?
Решение
Подумайте, для чего предназначена каждая структура данных, и шаблоны доступа, представленные в вопросе и ответах на один и два, становятся очевидными. Три немного хитрее, но у вас есть информация, что у вас нет информации о том, как эти данные будут использоваться, кроме высокой вероятности того, что все они будут использованы.
Очередь это труба. Материал идет в одну сторону, а другой выходит в том же порядке (сначала в, сначала в AKA FIFO). Вы можете или не можете видеть в очереди что-либо, кроме предмета, который должен выйти. Другими словами, чтобы посмотреть на следующий элемент в очереди, вы должны удалить текущий элемент. Поиск — это очень плохая идея, потому что, скорее всего, вы не сможете найти его, если не взять все и не вернуть все обратно.
Стек — только это. Куча вещей. Вы кладете вещи на кучу, а затем берете вещи. Вещи выходят из стека в порядке, обратном тому, в который они были вставлены. Это первым, последним или FILO. Опять же, вы не сможете увидеть ничего, кроме самого верхнего элемента в стеке, поэтому, чтобы перейти к следующему элементу вниз, вы должны удалить верхний элемент. Поиск — плохая идея по той же причине, что и очередь.
Все можно положить куда угодно. Помещение материала в список — это легкая прогулка, потому что вам все равно, куда он идет. Поиск вещей в списке … Это облом. Вы буквально должны смотреть на каждый элемент один за другим (линейный поиск), пока не найдете то, что ищете. Если вам все равно, что находится в списке, и вам никогда не придется искать его, это ваша структура данных. По крайней мере, пока вы не соберете статистику использования и не найдете некоторые оптимизации.
Все на своем месте в соответствии с определенной схемой. Это делает поиск вещей тупо легким. Вполне возможно, что вы можете перейти прямо к искомому элементу, а если нет, то, как правило, можете подразделять список снова и снова, потому что, если элемент находился не с одной стороны, где бы вы ни выбрали, он должен быть с другой стороны (бинарный поиск). , Найти легко, но все, что вы вставляете, должно быть аккуратно размещено, а это может быть довольно дорого. Но если вы строите список один раз, а затем повторно просматриваете его, вы почти всегда выходите вперед.
Другие решения
Других решений пока нет …
detector