- Мультисписок
-
В информатике, мультиспи́сок (англ. multilist) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в мультисписке, называются элементами мультисписка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.
Содержание
Определение
Мультисписок - структура данных, представляющая собой расширение понятия список путём добавления второго ссылочного поля. В результате каждый элемент мультисписка может ссылаться как на следующий элемент "по горизонтали" (как в классическом понимании списка), так и на следующий элемент "по вертикали". Таким образом, каждый элемент мультисписка может быть первым элементом другого мультисписка.
Свойства
У определённой таким образом структуры данных имеются некоторые свойства:
- Размер мультисписка — количество элементов в нём.
- Тип элементов — тип, над которым строится мультисписок; все элементы в мультисписке должны быть этого типа.
- Сравниваемость — мультисписки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения мультисписков может использовать разные технологии.
В файловом сервере Uniposter мультисписок используется для хранения в памяти читаемых из файла значений параметров конфигурационного файла. Использование мультисписка было выбрано за его возможность хранить:
- Данные произвольной длины.
- Набор данных произвольного размера.
- Возможность хранить как непосредственно данные, так и другие мультисписки данных.
- Возможность быстрой вставки данных в любое место мультисписка.
История
Мультисписок как контейнер для произвольных данных был разработан Пастуховым Геннадием в 1999 году при реализации файлового сервера Uniposter для сети Fido.
См. также
Типы данных Неинтерпретируемые Числовые Целый • С фиксированной запятой • С плавающей запятой • Рациональный • Комплексный • Длинный • Интервальный
Текстовые Указатель Адрес • Ссылка
Композитные Алгебраический тип данных (обобщённый) • Массив • Ассоциативный массив • Класс • Список • Кортеж • Объект • Option type • Product • Структура • Множество • Объединение (tagged)
Другие Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • First-class function • Opaque data type • Recursive data type • Семафор • Поток • Высший тип • Type class • Unit type • Void
Связанные темы Абстрактный тип данных • Структура данных • Интерфейс • Kind (type theory) • Примитивный тип • Subtyping • Шаблоны C++ • Конструктор типа • Parametric polymorphism
Структуры данных (список) Типы Массивы Ассоциативный массив • Multimap • Множество • Мультимножество • Хеш-таблица
Списки Деревья Графы На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.Категории:- Информатика
- Список
Wikimedia Foundation. 2010.