Реферат: Структуры данных

🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

При разработке программ и алгоритмов важным этапом является этап подбора математической абстракции для описания данных, используемых в формулировке задачи. Например, в случае поиска оптимальной стратегии для игры чет-нечет таким объектом была игра, в случае задачи об Ариадне и Тезее - лабиринт, в задаче о ходе коня - шахматная доска, в примере из лекции 16 - учреждение. Будем называть предстваление этих объектов-данных ввиде математических абстракций Абстрактными Структурами Данных (АСД). В случае игры в качестве АСД мы использовали дерево; в случае лабиринта - граф; в случае шахматной доски - матрицу.
Выбрав подходящую по своим математическим свойствам структуру АСД, мы приходим к другой проблеме - как представить выбранную АСД в терминах тех структур данных, с которыми умеет работать исполнитель алгоритмов, которые есть в испоьзуемом языке программирования. Назовем эти струтктуры данных Структурами Данных Хранения (СДХ). Например, в случае задачи об Ариадне и Тезее мы представили граф, представляющий лабиринт, в виде матрицы смежности, которую мы представили в виде соотвествующей СДХ - массива, для шахматной доски мы применили ту же структуру данных для хранения данных задачи, для учреждения - мы использовали запись.
Критерием выбора для АСД подходящей СДХ является эффективность операций над СДХ, являющихся аналогами соотвествующих операций над АСД. Под эффективностью мы понимаем сложность алгоритмов над СДХ.
Итак, мы приходим к следующей проблеме: задано АСД, набор СДХ; требуется построить отображение АСД -> СДХ так, чтобы сложность алгоритмов операций над СДХ, соотвествующих надлежащим оперциям над АСД, была бы минимальной.
Структура G на множестве M - это пара (R,M) где R это отношение порядка на множестве M.
Отношение порядка на множестве M это подмножество множества M*M обладающее следующими свойствами:
2.если a<=b и b<=c, то a<=c - транзитивность;
3.если a<=b и b<=a, то a=b - антисимметричность.
Если отношение не обладает свойством антисимметричности, то оно называется предпорядком.
Отношение порядка назывется линейным, если оно определено для любых a и b из M.
Множество называется частично упорядоченным если на нем зафиксирован некоторый порядок.
1. Множество натуральных чисел с отношением <=.
2. Множество слов в алфавите с отношением лексико-графического упорядочения.
3. Множество людей с отношением родства.
4. Множество людей с отношением начальник-подчиненный.
Для выбора и обозачения элементов на M используют индексацию I: I - это отображение M -> [ 1.. |M| ].
Наиболее часто встречающимися абстрактыми структурами данных являются строка, граф, дерево, стек, очередь, таблица.
Строка - конечное множество символов с отношением линейного прядка, определяющем следование символов в строке.
Примеры: текст, программа, формула.
2.Обращеие к элементам строки в отношении порядка, а не индексации;
3.Строка может иметь дополнительную структуру, называемую синтаксис, но это дополнительная структура.
замена заданного символа другим заданным символом.
Графом G=(X,U) где X - множество, а U - отношение порядка на X.
Если U - отношение частичного порядка, то G ориентированный граф. Дело в том, что согласно определению частичного порядка из условия (a,b)принадл.U не следует (b,a)принадл.U.
Если U - предпорядок со свойством симметричности, то G - неориентированный.
Граф G - взвешенный если задано отображение m:U -> R. Иногда вес называют длиной дуги.
Граф G - размеченный (помеченный) если задано отображение W: X -> A (U->A), где A - множество меток.
Примеры. Объект Задача 1. Сеть дорог Найти кратчайший маршрут 2.Блок-схема программы Найти неиспользуемый участок 3.Электрическая схема Вычислить характеристики цепи 4.Общество Найти взаимосвязь групп 5.Чертежи Сравнить 6.Химические молекулы Поиск подструктур 7.Сети ЭВМ Найти критический путь 8.Поставка товаров Кто поставляет заданный товар
Графический, матрица смежности, матрица инциденостей.
Степенью вершины называется число дуг входящих и исходящих из этой вершины (инцидентных данной вершине).
Стпенью исхода (захода) вершины называется число вершин исходящих (входящих) в эту вершину.
Граф называется регулярным если степень всех его вершин - величина постоянная.
Последоватедность вершин (x1, x2, x3, ...xN ) графа G называется цепью если для любого i, принадл.[1..n] => {(x(i), x(i+1))принадл.U}.
Последоватедность вершин (x1, x2, x3, ...xN ) графа G называется путем если для любого i, принадл.[1..n] => {(x(i), x(i+1) )принадл.U и (x(i+1), x(i) )принадл.U}. Иными словами путь это цепь, рассматриваемая без учета ориентации вершин.
При этом n - длина пути, цепи соответственно.
Если x1=xN , то путь назывется циклом.
Если x1=xN в цепи, то цикл называется ориентированным.
Граф назывется слабо связным если для любых его двух вершин есть путь их соединяющий без учета ориентации дуг графа.
Граф назывется сильно связным если для любых его двух вершин есть путь их соединяющий без с учетом ориентации дуг графа.
Весом пути называется m(x1, x2, x3, ...xN) = m(x1, x2) + m(x2, x3) + ... + m(x(N-1), xN).
В терминах графов строка - линейный неориентированный граф.
Раздел математики изучающий свойства графов называется теорией графов.
Дерево - связный ациклический (без циклов) граф.
Подчеркнем что здесь в цикле ориентация дуг не учитывается.
Одна вершина в дереве имеет степень захода 0. Эта вершина назывется корнем дерева.
Одна или несколько вершин в дереве имееют степень исхода 0. Эти вершины называются листьями.
Следствием условия ацикличности является то, что все вершины в графе, кроме корня, имеют сепень захода 1.
Деревья могут быть как ориентированные так и нет.
Высотой дерева называется самый длинный путь в дереве из корня к листу.
1. Группа родственников с отношением быть ребенком;
3. Слова в алфавите: разбиваются на классы эквивалентности по первому символу, каждый класс в свою очередь разбивается на классы эквивалентности по второму символу и т.д.
Не связный ациклический граф называется лесом.
1.Множество из одной вершины - дерево;
2.Если Т1, Т2, ...ТN - деревья, то вершина
заменить одну заданную вершину на другую;
При построении алгоритмов, реализующих эти равно как и другие операции над деревьями надо учитывать, что в дереве возможны самые разнообразные последователльности промотра вершин. Было бы полхо если результат операции зависел бы от порядка обхода дерева. Основные направления обхода: сверху-вниз, снизу-вверх, справа-налево, слева-направо.
Дерево называется K-ичным если все внутренние вершины в нем имеют степень исхода K.
Соответсвенно дерево называется единичным или линейным, если степень исхода его внутренних вершин равна 1; в двоичном или бинарном дереве она соответсвенно равна 2.
Попробуем подсчитать число двоичных деревьев, имеющих n вершин. Обознаячим b(i) - число бинарных деревьев из i вершин. Тогда следуя рекурсивному определению дерева, можно написать
b(n)=b(0)b(n-1) +b(1)b(n-2) +b(2)b(n-3) +...+b(n-1)b(0)
Нетрудно подсчитать что b(1)=1, b(2)=2, b(3)=b(0)b(2) + b(1)b(1) + b(2)b(0) , полагая b(0)=1, получаем, что b(3)=2+1+2=5. Соответственно b(4)=5+2+2+5=14, b(5)=14+5+4+5+14=42.
В общем случае b(n)=C(n, 2n) / (n+1) = (2*n!) / (n! * n!)
Дерево называется совершенным (или полностью сбалансированным) если любой путь в нем от корня к листу не более чем на единицу отличается от длины самого длинного пути в этом дереве.
Совершенное дерево из n вершин имеет минимальную высоту среди всех деревьев, имеющих n вершин.
Подсчитаем высоту совершенного бинарного дерева из n вершин. Пусть в нем i ярусов. (Ярусом назовем множество вершин равно отстоящих от корня дерева.) Тогда число вершин в дереве можно выразить следующим соотношением:
Отсюдаполучаем2^i -1=n, i=log2 (n+1) - 1. Или в приближенно log n. Отметим, что число совершенных деревьев составляет лишь малую часть общего числа деревьев. Например, при n=4 их всего 4.
Совершенные деревья интересны, например, тем что сложность доступа от корню к любому листу практически одна и та же. Здесь под сложностью доступа мы понимаем длину пути от корня к листу.
Стеком называется линейное дерево. В отличии от деревьев для операций со стеком есть ограничения. Доступ в стеке возможен только к корню дерева, которое в случае стека называется окном стека. Поэтому чтобы посмотреть элемент или изъять его или добавить новый - все это можно сделать только через корень. Примеры стека: подносы в столовой, патроны в обойме.
Основные операции: добавить элемент в стек, изъять элемент.
Очередь - это линейное дерево, но в отличие от стека добавить элемент в очередь можно только в корень дерева, который в случае очереди называется хвостом или концом очереди, а изъять элемент из очереди можно только со стороны листа, который называется головой очереди.
Пример: банальная очередь в магазине, в столовой. Основные операции изъять элемент, добавить элемент.
Упорядоченное множество пар (ключ,тело).
функция может быть представлена как пара (аргумент, результат),
таблица с записями о людях. В такой таблице ФИО - ключ, данные о человеке - тело. Мы здесь не будем подробно останавливаться на таблицах, так как им будет посвящено особое место в курсе.
В Pascal можно выделить две базовые структуры хранения: вектор из записей и список. С идей списка мы уже сталкивались когда рассматривали динамические структуры данных. Когда мы не можем фиксировать заранее число компонентов в структуре. Однако, как мы увидим позднее связывание статических элемнтов памяти посредством ссылок в цепочки позволяет динамически упралять не только числом компонентов, но и структурой в целом. Например, когда мы заранее не знаем степень вершин в графе.
На базовый характер этих структур так же указывает и то, что в их терминах можно описать все остальные структуры данных в Pascal. Более этого, важно помнить и то, что "за кулисами Pascal" стоит ЭВМ с ее структурой памяти. которая есть вектор из слов - адресуемой единице памяти. памяти.

Название: Структуры данных
Раздел: Рефераты по математике
Тип: реферат
Добавлен 02:06:06 23 марта 2008 Похожие работы
Просмотров: 1102
Комментариев: 17
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Структуры данных
Сочинение Владимир Александрович Кочетков Кыш Килде
Курсовая работа по теме Ценообразование на базе анализа эластичности спроса
Политика Перестройки И Распад Ссср Реферат
Курсовая работа по теме Антикризове управління бізнесом
Практическая Работа 3 Подгруппа Кислорода
Курсовая работа по теме Планирование работы фирмы 'Комп+' по установке, ремонту и модернизации компьютерной техники и периферийного оборудования
Реферат На Тему Организм И Среда
Курсовая работа по теме Брадзот овец
Дипломная Работа На Тему Адаптация Радиостанции "Хитfm" К Изменившимся Условиям На Рынке Сми Г. Екатеринбурга
Дипломная Работа На Тему Диагностика Профессиональной Пригодности Специалистов
Курсовая работа: Наследственность и изменчивость
Реферат: John Marshall The Great Chief Justice Essay
Дипломная работа по теме Проект реконструкції споруд очищення побутових стічних вод в умовах каналізаційних очисних споруд
Сочинение 100 Лет Плану Гоэлро
Признаки Функций Государства Эссе
Реферат На Тему Россия В Эпоху Петра I (1682-1725 Гг.)
Реферат: Сюрреализм
Дипломная работа: Экономическая оценка городских земель
Понять Другого Эссе
Реферат по теме Ресурсосбережение и определение оптимального соотношения ресурсов
Сочинение: Cоциальные мотивы в лирике А. Блока
Реферат: Становление отечественной истории техники
Реферат: Виды цен