Структуры данных. Линейные списки. Стек и очередь. Двоичные деревья



Скачать 118.46 Kb.
страница3/6
Дата06.11.2018
Размер118.46 Kb.
Название файла-
1   2   3   4   5   6
Абстрактные структуры данных.

Наиболее часто встречающимися абстрактыми структурами данных являются строка, граф, дерево, стек, очередь, таблица.



Строка

Строка - конечное множество символов с отношением линейного прядка, определяющем следование символов в строке.

Примеры: текст, программа, формула.

Свойства строк:

1.Переменная длина;

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.Поставка товаров Кто поставляет заданный товар


Поделитесь с Вашими друзьями:
1   2   3   4   5   6


База данных защищена авторским правом ©rppna.ru 2017
обратиться к администрации

    Главная страница