Задание
|
Реализовать абстрактный тип данных «Стек», «Дек», «Очередь» по варианту с учетом указанного в варианте способа реализации связи в линейном списке, а также способа организации линейного связанного списка
(1 балл из 7)
|
Реализовать отлаженный алгоритм сортировка заданного линейного списка (1 балл из 7), используя строго методы АТД, инкапсулируя тем самым структуру линейного списка (1 балл из 7)
|
Оценить трудоемкость каждого реализованного метода (в нотации О-символики или путем подсчета числа базовых операций в коде) (1 балл из 7).
|
№ вари-анта
|
Реализация связи элементов линейного списка
|
Способ организации линейного связанный список
|
Алгоритм сортировки
|
|
|
Указатели
|
Дек
|
«Сравнение и подсчет»
|
|
|
Указатели
|
Очередь головой и хвостом
|
«Сравнение и подсчет»
|
|
|
Указатели
|
Очередь с 1 головой
|
«Сравнение и подсчет»
|
|
|
Указатели
|
Стек
|
«Сравнение и подсчет»
|
|
|
Массив
|
Очередь
|
«Сравнение и подсчет»
|
|
|
Массив
|
Стек
|
«Сравнение и подсчет»
|
|
|
Библиотека классов
|
Очередь
|
«Сравнение и подсчет»
|
|
|
Библиотека классов
|
Стек
|
«Сравнение и подсчет»
|
|
|
Указатели
|
Дек
|
Алгоритм Шелла
|
|
|
Указатели
|
Очередь головой и хвостом
|
Алгоритм Шелла
|
|
|
Указатели
|
Очередь с 1 головой
|
Алгоритм Шелла
|
|
|
Указатели
|
Стек
|
Алгоритм Шелла
|
|
|
Массив
|
Очередь
|
Алгоритм Шелла
|
|
|
Массив
|
Стек
|
Алгоритм Шелла
|
|
|
Библиотека классов
|
Очередь
|
Алгоритм Шелла
|
|
|
Библиотека классов
|
Стек
|
Алгоритм Шелла
|
|
|
Указатели
|
Дек
|
Бинарная вставка
|
|
|
Указатели
|
Очередь головой и хвостом
|
Бинарная вставка
|
|
|
Указатели
|
Очередь с 1 головой
|
Бинарная вставка
|
|
|
Указатели
|
Стек
|
Бинарная вставка
|
|
|
Массив
|
Очередь
|
Бинарная вставка
|
|
|
Массив
|
Стек
|
Бинарная вставка
|
|
|
Библиотека классов
|
Очередь
|
Бинарная вставка
|
|
|
Библиотека классов
|
Стек
|
Бинарная вставка
|
|
|
Библиотека классов
|
Дек
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Указатели
|
Очередь головой и хвостом
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Указатели
|
Очередь с 1 головой
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Указатели
|
Стек
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Массив
|
Очередь
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Массив
|
Стек
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Библиотека классов
|
Очередь
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Библиотека классов
|
Стек
|
Быстрая сортировка Хоару (без медианного (pivot) элемента)
|
|
|
Указатели
|
Дек
|
Быстрая сортировка Хоару (c медианным (pivot) элементом)
|
|
|
Указатели
|
Очередь головой и хвостом
|
Быстрая сортировка Хоару (c медианным (pivot) элементом)
|
|
|
Указатели
|
Очередь с 1 головой
|
Быстрая сортировка Хоару (c медианным (pivot) элементом)
|
|
|
Указатели
|
Стек
|
Быстрая сортировка Хоару (c медианным (pivot) элементом)
|
|
|
Массив
|
Очередь
|
Быстрая сортировка Хоару (c медианным (pivot) элементом)
|
|
|
Массив
|
Стек
|
Быстрая сортировка Хоару (c медианным (pivot) элемнтом)
|
|
|
Библиотека классов
|
Очередь
|
Быстрая сортировка Хоару (c медианным (pivot) элеметом)
|
|
|
Библиотека классов
|
Стек
|
Быстрая сортировка Хоару (c медианным (pivot) элеметом)
|
|
|
Указатели
|
Дек
|
Естественное двухпутевое слияние
|
|
|
Указатели
|
Очередь головой и хвостом
|
Естественное двухпутевое слияние
|
|
|
Указатели
|
Очередь с 1 головой
|
Естественное двухпутевое слияние
|
|
|
Указатели
|
Стек
|
Естественное двухпутевое слияние
|
|
|
Массив
|
Очередь
|
Естественное двухпутевое слияние
|
|
|
Массив
|
Стек
|
Естественное двухпутевое слияние
|
|
|
Библиотека классов
|
Очередь
|
Естественное двухпутевое слияние
|
|
|
Библиотека классов
|
Стек
|
Естественное двухпутевое слияние
|
|
|
Указатели
|
Дек
|
Пирамидальная сортировка
|
|
|
Указатели
|
Очередь головой и хвостом
|
Пирамидальная сортировка
|
|
|
Указатели
|
Очередь с 1 головой
|
Пирамидальная сортировка
|
|
|
Указатели
|
Стек
|
Пирамидальная сортировка
|
|
|
Массив
|
Очередь
|
Пирамидальная сортировка
|
|
|
Массив
|
Стек
|
Пирамидальная сортировка
|
|
|
Библиотека классов
|
Очередь
|
Пирамидальная сортировка
|
|
|
Библиотека классов
|
Стек
|
Пирамидальная сортировка
|
|
|
Указатели
|
Дек
|
Простая вставка
|
|
|
Указатели
|
Очередь головой и хвостом
|
Простая вставка
|
|
|
Указатели
|
Очередь с 1 головой
|
Простая вставка
|
|
|
Указатели
|
Стек
|
Простая вставка
|
|
|
Массив
|
Очередь
|
Простая вставка
|
|
|
Массив
|
Стек
|
Простая вставка
|
|
|
Библиотека классов
|
Очередь
|
Простая вставка
|
|
|
Библиотека классов
|
Стек
|
Простая вставка
|
|
|
Указатели
|
Дек
|
Простой выбор
|
|
|
Указатели
|
Очередь головой и хвостом
|
Простой выбор
|
|
|
Указатели
|
Очередь с 1 головой
|
Простой выбор
|
|
|
Указатели
|
Стек
|
Простой выбор
|
|
|
Массив
|
Очередь
|
Простой выбор
|
|
|
Массив
|
Стек
|
Простой выбор
|
|
|
Библиотека классов
|
Очередь
|
Простой выбор
|
|
|
Библиотека классов
|
Стек
|
Простой выбор
|
|
|
Указатели
|
Дек
|
Пузырьковая
|
|
|
Указатели
|
Очередь головой и хвостом
|
Пузырьковая
|
|
|
Указатели
|
Очередь с 1 головой
|
Пузырьковая
|
|
|
Указатели
|
Стек
|
Пузырьковая
|
|
|
Массив
|
Очередь
|
Пузырьковая
|
|
|
Массив
|
Стек
|
Пузырьковая
|
|
|
Библиотека классов
|
Очередь
|
Пузырьковая
|
|
|
Библиотека классов
|
Стек
|
Пузырьковая
|
|
|
Указатели
|
Дек
|
Распределяющий подсчет
|
|
|
Указатели
|
Очередь головой и хвостом
|
Распределяющий подсчет
|
|
|
Указатели
|
Очередь с 1 головой
|
Распределяющий подсчет
|
|
|
Указатели
|
Стек
|
Распределяющий подсчет
|
|
|
Массив
|
Очередь
|
Распределяющий подсчет
|
|
|
Массив
|
Стек
|
Распределяющий подсчет
|
|
|
Библиотека классов
|
Очередь
|
Распределяющий подсчет
|
|
|
Библиотека классов
|
Стек
|
Распределяющий подсчет
|
|
|
Указатели
|
Дек
|
Фиксированное двухпутевое слияние
|
|
|
Указатели
|
Очередь головой и хвостом
|
Фиксированное двухпутевое слияние
|
|
|
Указатели
|
Очередь с 1 головой
|
Фиксированное двухпутевое слияние
|
|
|
Указатели
|
Стек
|
Фиксированное двухпутевое слияние
|
|
|
Массив
|
Очередь
|
Фиксированное двухпутевое слияние
|
|
|
Массив
|
Стек
|
Фиксированное двухпутевое слияние
|
|
|
Библиотека классов
|
Очередь
|
Фиксированное двухпутевое слияние
|
|
|
Библиотека классов
|
Очередь
|
Фиксированное двухпутевое слияние
|
|
|
Указатели
|
Дек
|
Пирамидальная сортировка
|
|
|
Указатели
|
Очередь головой и хвостом
|
Пирамидальная сортировка
|
|
|
Указатели
|
Очередь с 1 головой
|
Пирамидальная сортировка
|
|
|
Указатели
|
Стек
|
Пирамидальная сортировка
|
|
Скачать 15.85 Kb.