Категория
Информатика
Тип
реферат
Страницы
6 стр.
Дата
17.01.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18537.zip — 34.5 kb
  • otobrazhenie-asd-na-sdx_18537_1.rtf — 304.31 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Отображение АСД на СДХ
Отображение АСД на
СДХ.
Наша задача :
1.Найти отображение АСД -> СДХ;
2.Оценить сложность алгоритмов операций вставки, замены, поиска и удаления при различных способах отображениях.
1. Отображения на вектор.
Будем предполагать что мы имеем дело с неотсортированными структурами. Подробно что означает условие сортированности мы рассмотрим в разделе IV "Сортировка."
1.1. Строка
Отображение строки на вектор строится так:
1. Возьмем антитранзитиное отношение R' такое что его транзитивное замыкание дает R (для этого достаточно рассмотреть отношение линейного порядка
R без условия 2 - условия транзитивности :
если (a, b) и (b, c) принадлежат R, то (a, c) тоже принадлежит R;
Ясно что R' задает отношение соседства, т.е. (a,b) принадл. R' если и только если
Не существ. c: c принадл. M , (a,c)принадл.R' и (c,b)принадл.R'
2.Возьмем минимальный элемент в строке (он существует в силу свойства отношения линейного порядка R); пусть это a;
3.Элементу a сопоставим первый компонент вектора: I(a)=1;
4.Паре (b,c)принадл.R' сопоставим I(c)=I(b)+1.
В одном векторе можно хранить несколько строк. Для этого существует два принципиально разных способа: строки разделяются специальным признаком - признаком конца, которого нет среди символов строк; второй способ - в начале каждой строки указывается ее длина.
Последний способ предпочтительней когда мы имеем дело со строками переменной длины, а первый хорош когда строки фиксированной длины.
Рассмотрим сложность операций поиска, вставки, удаления и замены. Операции вставки, удаления и замены содержат операцию поиска как составную часть.
Предполагаем что частота встречаемости всех



Ваше мнение



CAPTCHA