Студопедия — Введение. к курсовому проекту по дисциплине
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Введение. к курсовому проекту по дисциплине






ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по дисциплине

“Структуры и алгоритмы обработки данных ”

на тему

ДЕРЕВЬЯ ПОИСКА (Search trees) ROPE

 

Выполнил студент Жуковец Павел Евгеньевич
  Ф.И.О.

 

Группы ИВ-15
   

 

Работу принял   доцент к.т.н. М.Г. Курносов
  подпись  

 

Защищена   Оценка  
       

 

Новосибирск – 2012
СОДЕРЖАНИЕ

ВВЕДЕНИЕ……………………………………….………………………………….3

1 Идея…………………………………………………………………………………4

2 Индексация…………………………………………………………………………6

Разбиение…………………………………………………………………………...7 4 Удаление и вставка……………………………………………………………….10

5 Оптимизация……………………………………………………………………...11

Балансировка……………………………………………………………..11

5.2 Прямое объединение малых строк……………………………………...13

Кэширование последней позиции………………………………………13

ЗАКЛЮЧЕНИЕ…………………………………………………………………….14

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………………15

1 Исходный текст программы……………………………………….…………….16

 


Введение

Большинство из нас так или иначе работает со строками. Этого не избежать — если ты пишешь код, ты обречен каждый день складывать строки, разбивать их на составные части и обращаться к отдельным символам по индексу. Мы давно привыкли что строки — это массивы символов фиксировнной длины, а это влечет за собой соответствующие ограничения в работе с ними.
Так, мы не можем быстро объединить две строки — для этого нам потребуется сначала выделить необходимое количество памяти, а потом скопировать туда данные из конкатенируемых строк. Очевидно, что такая операция имеет сложность порядка О(n), где n — суммарная длина строк.
Именно поэтому код:

 

string s = "";

for (int i = 0; i < 100000; i++) s += "a";

 

работает так медленно.
Хочешь выполнять конкатенацию гигантских строк быстро? Не нравится, что строка требует для хранения непрерывную область памяти? Надоело использовать буферы для построения строк?
Структура данных, которая нас спасет, называется Rope string, или «веревочная строка». Принцип ее работы очень прост и до него можно догадаться буквально из интуитивных соображений.


Идея

 

Пусть нам требуется сложить две строки:

Для классических строк мы просто выделим область памяти необходимого размера, в начало её скопируем содержимое первой строки, а в конец — второй:

Как уже упоминалось выше, сложность этой операции — O(n).

Но что если мы используем информацию о том что наша результирующая строка — это конкатенация двух исходных? И действительно, создадим объект который предоставляет интерфейс строки и хранит в себе информацию о своих компонентах — исходных строках:

Такой способ объединения строк работает за О(1) — нам нужно лишь создать объект-обертку для исходных строк. Так как этот объект — тоже строка, его можно комбинировать с другими строками для получения нужных нам конкатенаций:

Уже сейчас очевидно что наша структура — это двоичное дерево поиска, в листьях которого находятся элементарные составляющие нашей строки — группы символов. Так же очевидным становится способ перечисления символов строки — это обход дерева в глубину с последовательным перечислением символов в листьях дерева.

 

 








Дата добавления: 2015-09-04; просмотров: 300. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Меры безопасности при обращении с оружием и боеприпасами 64. Получение (сдача) оружия и боеприпасов для проведения стрельб осуществляется в установленном порядке[1]. 65. Безопасность при проведении стрельб обеспечивается...

Уравнение волны. Уравнение плоской гармонической волны. Волновое уравнение. Уравнение сферической волны Уравнением упругой волны называют функцию , которая определяет смещение любой частицы среды с координатами относительно своего положения равновесия в произвольный момент времени t...

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Основные разделы работы участкового врача-педиатра Ведущей фигурой в организации внебольничной помощи детям является участковый врач-педиатр детской городской поликлиники...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия