Тип исполнения б/у?

Question

Существует вопрос, который я пытался решить некоторое время, но мне трудно понять правильную реализацию для него. Если мы напишем программу, которая будет манипулировать тысячами записей, каждая из которых будет содержать название продукта, тип, серийный номер, розничную цену и т. Д. В каждом случае ниже объясните, какой абстрактный тип данных (очередь, стек, не сортированный и отсортированный список) вы использовали бы , и какая реализация (массив или связанная структура). Кратко оправдывайте свой выбор.

1) Записи будут получены в том же порядке, в каком они были сохранены. Нельзя заранее сказать, сколько записей будет обработано и как.

• Я предпочитаю Unsorted список для этой цели, которая используется реализацией связанного списка, потому что мы не знаем, количество записей в начале, и данные будут извлечены, поскольку они хранятся, следовательно, они должны быть связаны, который также может быть возможным ADT, как Queue или Stack, но они используют реализацию массива, поэтому возникает проблема распределения памяти.

2) Все записи будут вставлены в начале, один раз и в произвольном порядке. Они будут извлекаться очень часто, основываясь на серийном номере.

• Даже в случае печати всех данных записей за один раз это возможно в списке Unsorted.

3) большое, но неизвестное количество записей продукта будет вставлен, как и в случае необходимости. Их редко будут получать индивидуально. Большинство операций будут состоять из обработки всех записей за один раз, например, для печати всего.

• Однако здесь отсортированный и несертифицированный список имел большую эффективность использования, но я предпочитаю список без сортировки, потому что для сортировки требуется время, которое снижает его эффективность.

Что вы, ребята, думаете?

Answer 1

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

Очередь

Очередь - это труба. Материал идет в одну сторону и выдает другую в том же порядке (сначала сначала, AKA FIFO). Вы можете или не сможете увидеть что-либо в очереди, кроме предмета, который должен выйти. Другими словами, чтобы посмотреть на следующий элемент в очереди, вам нужно удалить текущий элемент. Поиск - очень плохая идея, потому что, вероятно, вы не можете найти его, чтобы не вытащить все и снова вернуть его обратно.

Стек

Стек - это только что. Куча вещей. Вы кладете вещи поверх кучи, затем вы берете вещи из кучи. Вещи выходят из стека в обратном порядке, в который они были помещены. Это первое, последнее или FILO. Опять же, вы не сможете увидеть ничего, кроме самого верхнего элемента в стеке, поэтому, чтобы перейти к следующему элементу, вам нужно удалить верхний элемент. Поиск - плохая идея по той же причине, что и очередь.

Unsorted Список

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

отсортированный список

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