Blog despre resurse educaţionale din IT » programming

Zend Framework Reference 1.11 Русская версия

admin — Tue, 13 Sep 2011 11:38:58 +0000

Zend_Acl…………………………………………………………………………………………………….. 2

Введение……………………………………………………………………………………………………… 2

Ресурсы……………………………………………………………………………………………………. 2

Роли………………………………………………………………………………………………………….. 2

Создание списка контроля доступа (ACL)……………………………………………………………………………………………….. 4

Регистрация ролей……………………………………………………………………………………………………………………………… 4

Определение контроля доступа………………………………………………………………………………………………………. 5

Запросы к ACL……………………………………………………………………………………………. 6

Настройка управления доступом………………………………………………………………………………………………… 8

Точное управление доступом………………………………………………………………………………………………………………. 8

Удаление правил доступа……………………………………………………………………………………………………… 9

Zend_Application…………………………………………………………………………………….. 11

Введение…………………………………………………………………………………………………… 11

Zend_Application – Быстрый старт……………………………………………………………………………………………………………. 11

Использование вместе с Zend_Tool……………………………………………………………………………………………………… 11

Добавление Zend_Application в приложение……………………………………………………………………………………….. 13

Добавление и создание ресурсов……………………………………………………………………………………………………….. 15

Следующие шаги с Zend_Application……………………………………………………………………………………………………. 16

Расширенное использование………………………………………………………………………………………………………………… 17

Постоянное хранение данных ACL………………………………………………………………………………………………………. 17

Написание условных правил ACL с утверждениями……………………………………………………………………………….. 17

Теоретические основы работы с Zend_Application……………………………………………………………………………………. 19

Начальная загрузка……………………………………………………………………………………………………………………………. 20

Методы ресурсов……………………………………………………………………………………………………………………………… 20

Загрузки, использующие плагины ресурсов………………………………………………………………………………………….. 21

Реестр ресурсов……………………………………………………………………………………………………………………………….. 23

Отслеживание зависимостей……………………………………………………………………………………………………………… 25

Плагины ресурсов……………………………………………………………………………………………………………………………… 26

Zend_Cache………………………………………………………………………………………………………………………………………….. 28

Введение……………………………………………………………………………………………………………………………………………. 28

Теория кэширования……………………………………………………………………………………………………………………………. 30

Фабричный метод Zend_Cache……………………………………………………………………………………………………………. 30

Добавление тегов к записям………………………………………………………………………………………………………………. 31

Очистка кэша……………………………………………………………………………………………………………………………………. 31

Фронтэнды Zend_Cache……………………………………………………………………………………………………………………….. 32

Zend_Cache_Core…………………………………………………………………………………………………………………………………. 32

Введение……………………………………………………………………………………………………………………………………………. 32

Доступные опции……………………………………………………………………………………………………………………………… 32

Примеры…………………………………………………………………………………………………………………………………………. 33

Zend_Cache_Frontend_Output……………………………………………………………………………………………………………….. 35

Введение……………………………………………………………………………………………………………………………………………. 35

Доступные опции……………………………………………………………………………………………………………………………… 35

Примеры…………………………………………………………………………………………………………………………………………. 35

Zend_Cache_Frontend_Function……………………………………………………………………………………………………………… 36

Введение……………………………………………………………………………………………………………………………………………. 36

Доступные опции……………………………………………………………………………………………………………………………… 36

Примеры…………………………………………………………………………………………………………………………………………. 36

Zend_Cache_Frontend_Class………………………………………………………………………………………………………………….. 36

Введение……………………………………………………………………………………………………………………………………………. 36

Доступные опции……………………………………………………………………………………………………………………………… 36

Примеры…………………………………………………………………………………………………………………………………………. 37

Zend_Cache_Frontend_File…………………………………………………………………………………………………………………….. 37

Введение……………………………………………………………………………………………………………………………………………. 37

Доступные опции……………………………………………………………………………………………………………………………… 38

Примеры…………………………………………………………………………………………………………………………………………. 38

Zend_Cache_Frontend_Page………………………………………………………………………………………………………………….. 38

Введение……………………………………………………………………………………………………………………………………………. 38

Доступные опции……………………………………………………………………………………………………………………………… 39

Примеры…………………………………………………………………………………………………………………………………………. 40

Отмена кэширования……………………………………………………………………………………………………………………………. 41

Бэкэнды Zend_Cache……………………………………………………………………………………………………………………………. 43

Zend_Cache_Backend_File……………………………………………………………………………………………………………………… 43

Доступные опции:…………………………………………………………………………………………………………………………….. 43

Zend_Cache_Backend_Sqlite…………………………………………………………………………………………………………………… 43

Доступные опции:…………………………………………………………………………………………………………………………….. 43

Zend_Cache_Backend_Memcached…………………………………………………………………………………………………………. 44

Доступные опции:…………………………………………………………………………………………………………………………….. 44

Zend_Cache_Backend_Apc…………………………………………………………………………………………………………………….. 44

Zend_Cache_Backend_Xcache………………………………………………………………………………………………………………… 44

Доступные опции:…………………………………………………………………………………………………………………………….. 45

Zend_Cache_Backend_ZendPlatform……………………………………………………………………………………………………….. 45

Zend_Cache_Backend_TwoLevels……………………………………………………………………………………………………………. 45

Доступные опции:…………………………………………………………………………………………………………………………….. 45

Zend_Cache_Backend_ZendServer_Disk и Zend_Cache_Backend_ZendServer_ShMem……………………………………. 46

Zend_Config………………………………………………………………………………………………………………………………………….. 47

Введение……………………………………………………………………………………………………………………………………………. 47

Теоретические основы работы с Zend_Config………………………………………………………………………………………….. 48

Zend_Config_Ini……………………………………………………………………………………………………………………………………. 49

Zend_Config_Xml………………………………………………………………………………………………………………………………….. 51

Zend_Config_Writer……………………………………………………………………………………………………………………………… 55

Zend_Controller……………………………………………………………………………………………………………………………………. 57

Zend_Controller – Быстрый старт…………………………………………………………………………………………………………….. 57

Введение……………………………………………………………………………………………………………………………………………. 57

Быстрый старт…………………………………………………………………………………………………………………………………… 57

Создайте файловую структуру…………………………………………………………………………………………………………….. 57

Установите корневую директорию для документов………………………………………………………………………………. 57

Создайте свои правила перезаписи…………………………………………………………………………………………………….. 57

Создайте файл загрузки……………………………………………………………………………………………………………………… 58

Создайте свой контроллер действий, используемый по умолчанию……………………………………………………….. 59

Создайте скрипт вида………………………………………………………………………………………………………………………… 60

Создайте контроллер ошибок…………………………………………………………………………………………………………….. 60

Смотрим сайт!………………………………………………………………………………………………………………………………….. 61

Основы Zend_Controller………………………………………………………………………………………………………………………… 62

Фронт-контроллер……………………………………………………………………………………………………………………………….. 65

Обзор………………………………………………………………………………………………………………………………………………. 65

Ключевые методы…………………………………………………………………………………………………………………………….. 65

getInstance()…………………………………………………………………………………………………………………………………….. 65

setControllerDirectory() и addControllerDirectory()………………………………………………………………………………….. 65

addModuleDirectory() и getModuleDirectory()……………………………………………………………………………………….. 66

dispatch()…………………………………………………………………………………………………………………………………………. 66

run()………………………………………………………………………………………………………………………………………………… 67

Методы-аксессоры для конфигурирования………………………………………………………………………………………….. 67

Параметры фронт-контроллера………………………………………………………………………………………………………….. 69

Расширение фронт-контроллера………………………………………………………………………………………………………… 70

Объект запроса……………………………………………………………………………………………………………………………………. 71

Введение…………………………………………………………………………………………………………………………………………. 71

HTTP-запросы………………………………………………………………………………………………………………………………………. 71

Доступ к данным запроса…………………………………………………………………………………………………………………… 71

Базовый URL и поддиректории……………………………………………………………………………………………………………. 73

Определение HTTP-метода запроса……………………………………………………………………………………………………. 74

Определение запросов AJAX……………………………………………………………………………………………………………… 74

Создание подклассов объекта запроса………………………………………………………………………………………………… 74

Стандартный маршрутизатор………………………………………………………………………………………………………………… 76

Введение…………………………………………………………………………………………………………………………………………. 76

Использование маршрутизатора………………………………………………………………………………………………………… 78

Базовые операции Rewrite Router……………………………………………………………………………………………………….. 78

Маршруты, используемые по умолчанию……………………………………………………………………………………………. 79

Базовый URL и поддиректории……………………………………………………………………………………………………………. 80

Глобальные параметры…………………………………………………………………………………………………………………….. 81

Типы маршрутов………………………………………………………………………………………………………………………………….. 81

Zend_Controller_Router_Route……………………………………………………………………………………………………………. 81

Значения переменных по умолчанию…………………………………………………………………………………………………. 82

Требования к переменным………………………………………………………………………………………………………………… 83

Переводимые сегменты…………………………………………………………………………………………………………………….. 83

Zend_Controller_Router_Route_Static…………………………………………………………………………………………………… 86

Zend_Controller_Router_Route_Regex…………………………………………………………………………………………………. 86

Zend_Controller_Router_Route_Hostname……………………………………………………………………………………………. 90

Zend_Controller_Router_Route_Chain………………………………………………………………………………………………….. 90

Объединение маршрутов через Zend_Config……………………………………………………………………………………….. 91

Использование Zend_Config вместе с RewriteRouter…………………………………………………………………………………. 94

Создание подклассов маршрутизатора…………………………………………………………………………………………………… 94

Диспетчер…………………………………………………………………………………………………………………………………………… 96

Обзор………………………………………………………………………………………………………………………………………………. 96

Создание подклассов диспетчера……………………………………………………………………………………………………….. 97

Контроллеры действий……………………………………………………………………………………………………………………….. 101

Введение……………………………………………………………………………………………………………………………………….. 101

Инициализация объекта…………………………………………………………………………………………………………………… 102

Перехватчики Pre- и Post-Dispatch……………………………………………………………………………………………………… 103

Аксессоры………………………………………………………………………………………………………………………………………. 103

Интеграция вида……………………………………………………………………………………………………………………………… 104

Инициализация вида……………………………………………………………………………………………………………………….. 104

Рендеринг видов…………………………………………………………………………………………………………………………….. 105

Сервисные методы………………………………………………………………………………………………………………………….. 106

Создание подклассов контроллера действий……………………………………………………………………………………… 106

Помощники действий………………………………………………………………………………………………………………………….. 109

Введение……………………………………………………………………………………………………………………………………….. 109

Инициализация помощника……………………………………………………………………………………………………………… 109

Брокер помощников………………………………………………………………………………………………………………………… 109

Встроенные помощники действий…………………………………………………………………………………………………….. 111

ActionStack……………………………………………………………………………………………………………………………………… 111

AutoComplete…………………………………………………………………………………………………………………………………. 113

Автодополнение c Dojo……………………………………………………………………………………………………………………. 114

Автодополнение с Scriptaculous………………………………………………………………………………………………………… 117

ContextSwitch и AjaxContext……………………………………………………………………………………………………………… 118

Доступные по умолчанию контексты…………………………………………………………………………………………………. 119

Создание своего контекста……………………………………………………………………………………………………………….. 120

Установка контекстов для действий…………………………………………………………………………………………………… 121

Инициализация переключения контекста………………………………………………………………………………………….. 123

Дополнительный функционал………………………………………………………………………………………………………….. 123

Функционал AjaxContext………………………………………………………………………………………………………………….. 125

FlashMessenger……………………………………………………………………………………………………………………………….. 126

Введение……………………………………………………………………………………………………………………………………….. 126

Базовый пример использования……………………………………………………………………………………………………….. 126

JSON………………………………………………………………………………………………………………………………………………. 127

Redirector……………………………………………………………………………………………………………………………………….. 128

Введение……………………………………………………………………………………………………………………………………….. 128

Базовые примеры использования……………………………………………………………………………………………………… 130

ViewRenderer………………………………………………………………………………………………………………………………….. 133

Введение……………………………………………………………………………………………………………………………………….. 133

API…………………………………………………………………………………………………………………………………………………. 134

Примеры базового использования…………………………………………………………………………………………………….. 139

Примеры продвинутого использования……………………………………………………………………………………………… 142

Написание собственных помощников………………………………………………………………………………………………… 143

Объект ответа……………………………………………………………………………………………………………………………………. 145

Использование……………………………………………………………………………………………………………………………….. 145

Управление заголовками…………………………………………………………………………………………………………………. 146

Именованные сегменты…………………………………………………………………………………………………………………… 147

Проверка на исключения в объекте ответа…………………………………………………………………………………………. 149

Создание подклассов объекта ответа…………………………………………………………………………………………………. 150

Плагины…………………………………………………………………………………………………………………………………………….. 151

Введение……………………………………………………………………………………………………………………………………….. 151

Написание плагинов………………………………………………………………………………………………………………………… 151

Использование плагинов………………………………………………………………………………………………………………….. 152

Извлечение и работа с плагинами……………………………………………………………………………………………………… 153

Плагины, включенные в стандартную поставку…………………………………………………………………………………… 153

ActionStack……………………………………………………………………………………………………………………………………… 153

Zend_Controller_Plugins_ErrorHandler…………………………………………………………………………………………………. 154

Использование ErrorHandler в качестве обработчика ошибки 404………………………………………………………….. 155

Управление сгенерированным ранее выводом…………………………………………………………………………………… 157

Примеры использования плагина……………………………………………………………………………………………………… 157

Пример контроллера ошибок…………………………………………………………………………………………………………… 158

Использование модульной структуры директорий…………………………………………………………………………………. 159

Введение……………………………………………………………………………………………………………………………………….. 159

Определение директорий контроллеров в модулях……………………………………………………………………………. 160

Маршрутизация применительно к модулям……………………………………………………………………………………….. 161

Модуль или глобальный контроллер по умолчанию…………………………………………………………………………… 161

Исключения………………………………………………………………………………………………………………………………………. 162

Введение……………………………………………………………………………………………………………………………………….. 162

Обработка исключений……………………………………………………………………………………………………………………. 162

Исключения в MVC, с которыми вы можете встретиться………………………………………………………………………. 163

Zend_Db……………………………………………………………………………………………………………………………………………… 167

Zend_Db_Adapter……………………………………………………………………………………………………………………………….. 167

Соединение с БД с использованием адаптера…………………………………………………………………………………….. 167

Использование конструктора адаптера Zend_Db…………………………………………………………………………………. 167

Использование фабрики Zend_Db……………………………………………………………………………………………………… 168

Использование Zend_Config с фабрикой Zend_Db……………………………………………………………………………….. 169

Параметры адаптера……………………………………………………………………………………………………………………….. 169

Управление отложенными соединениями…………………………………………………………………………………………. 171

Пример базы данных……………………………………………………………………………………………………………………….. 172

Чтение результатов запроса……………………………………………………………………………………………………………… 173

Извлечение полного набора результатов…………………………………………………………………………………………… 173

Изменение режима извлечения……………………………………………………………………………………………………….. 174

Извлечение результатов выборки в виде ассоциативного массива………………………………………………………… 175

Извлечение единственного столбца из результатов выборки……………………………………………………………….. 175

Извлечение пар ключ-значение из результатов выборки…………………………………………………………………….. 175

Извлечение единственной строки из результатов выборки………………………………………………………………….. 176

Извлечение единственного скалярного значения из результатов выборки…………………………………………….. 176

Изменение данных в БД…………………………………………………………………………………………………………………… 176

Добавление данных………………………………………………………………………………………………………………………… 176

Получение сгенерированного значения…………………………………………………………………………………………….. 177

Обновление данных………………………………………………………………………………………………………………………… 179

Удаление данных……………………………………………………………………………………………………………………………. 180

Заключение в кавычки значений и идентификаторов…………………………………………………………………………… 180

Использование quote()…………………………………………………………………………………………………………………. 181

Использование quoteInto()…………………………………………………………………………………………………………. 182

Использование quoteIdentifier()…………………………………………………………………………………………….. 183

Управление транзакциями……………………………………………………………………………………………………………….. 184

Листинг и описание таблиц……………………………………………………………………………………………………………….. 185

Закрытие соединения………………………………………………………………………………………………………………………. 186

Запуск других операторов БД……………………………………………………………………………………………………………. 186

Примечания к отдельным адаптерам………………………………………………………………………………………………… 187

IBM DB2………………………………………………………………………………………………………………………………….. 187

MySQLi……………………………………………………………………………………………………………………………………. 187

Oracle……………………………………………………………………………………………………………………………………….. 187

PDO для IBM DB2 и Informix Dynamic Server (IDS)………………………………………………………………….. 188

PDO Microsoft SQL Server………………………………………………………………………………………………………… 188

PDO MySQL…………………………………………………………………………………………………………………………….. 188

PDO Oracle………………………………………………………………………………………………………………………………. 189

PDO PostgreSQL………………………………………………………………………………………………………………………. 189

PDO SQLite……………………………………………………………………………………………………………………………… 189

Firebird/Interbase……………………………………………………………………………………………………………………….. 190

Zend_Db_Statement……………………………………………………………………………………………………………………………. 191

Создание оператора………………………………………………………………………………………………………………………… 191

Выполнение оператора……………………………………………………………………………………………………………………. 191

Извлечение результатов выполнения оператора SELECT…………………………………………………………………… 192

Извлечение одной строки из набора результатов……………………………………………………………………………….. 192

Извлечение всего набора результатов……………………………………………………………………………………………….. 193

Изменение формата извлечения………………………………………………………………………………………………………. 193

Извлечение одного столбца из набора результатов…………………………………………………………………………….. 194

Извлечение строки в виде объекта……………………………………………………………………………………………………. 194

Zend_Db_Profiler………………………………………………………………………………………………………………………………… 195

Введение……………………………………………………………………………………………………………………………………….. 195

Использование профилировщика……………………………………………………………………………………………………… 196

Расширенное использование профилировщика………………………………………………………………………………….. 197

Фильтрация по времени выполнения запроса…………………………………………………………………………………….. 198

Фильтрация по типу запроса……………………………………………………………………………………………………………… 198

Получение профилей по типу запроса……………………………………………………………………………………………….. 199

Специализированные профилировщики……………………………………………………………………………………………. 199

Profiling with Firebug…………………………………………………………………………………………………………………………. 199

Zend_Db_Select………………………………………………………………………………………………………………………………….. 201

Обзор…………………………………………………………………………………………………………………………………………….. 201

Создание объекта Select…………………………………………………………………………………………………………………… 201

Построение запросов Select……………………………………………………………………………………………………………… 201

Добавление предложения FROM………………………………………………………………………………………………………. 202

Добавление колонок……………………………………………………………………………………………………………………….. 203

Добавление столбцов выражений…………………………………………………………………………………………………….. 204

Добавление столбцов в существующую таблицу FROM или JOIN…………………………………………………………… 205

Добавление в запрос другой таблицы c помощью JOIN………………………………………………………………………… 206

Добавление предложения WHERE…………………………………………………………………………………………………….. 209

Добавление предложения GROUP BY………………………………………………………………………………………………… 211

Добавление предложения HAVING…………………………………………………………………………………………………… 211

Добавление предложения ORDER BY…………………………………………………………………………………………………. 212

Добавление предложения LIMIT……………………………………………………………………………………………………….. 213

Добавление модификатора DISTINCT…………………………………………………………………………………………………. 214

Добавление модификатора FOR UPDATE……………………………………………………………………………………………. 214

Произведение запросов на выборку………………………………………………………………………………………………….. 214

Произведение запросов на выборку из адаптера БД……………………………………………………………………………. 214

Произведение запросов на выборку через объект Select……………………………………………………………………… 214

Преобразование объекта Select в SQL-строку……………………………………………………………………………………… 215

Другие методы……………………………………………………………………………………………………………………………….. 215

Получение частей объекта Select………………………………………………………………………………………………………. 215

Сброс частей запроса в объекте Select……………………………………………………………………………………………….. 216

Zend_Db_Table…………………………………………………………………………………………………………………………………… 218

Класс таблицы – введение………………………………………………………………………………………………………………… 218

Определение класса таблицы…………………………………………………………………………………………………………… 218

Определение имени и схемы таблицы………………………………………………………………………………………………. 218

Определение первичного ключа таблицы………………………………………………………………………………………….. 219

Переопределение методов установки таблицы………………………………………………………………………………….. 220

Инициализация таблицы………………………………………………………………………………………………………………….. 220

Создание экземпляра класса таблицы……………………………………………………………………………………………….. 221

Установка адаптера БД…………………………………………………………………………………………………………………….. 221

Установка используемого по умолчанию адаптера БД…………………………………………………………………………. 221

Хранение адаптера БД в реестре………………………………………………………………………………………………………. 222

Добавление строк в таблицу…………………………………………………………………………………………………………….. 222

Использование таблицы с автоинкрементным ключом……………………………………………………………………….. 223

Использование таблицы с последовательностью………………………………………………………………………………… 223

Использование таблицы с естественным ключом……………………………………………………………………………….. 224

Обновление строк в таблице…………………………………………………………………………………………………………….. 224

Удаление строк из таблицы………………………………………………………………………………………………………………. 225

Извлечение строк по первичному ключу……………………………………………………………………………………………. 225

Извлечение наборов строк……………………………………………………………………………………………………………….. 227

API для произведения выборки………………………………………………………………………………………………… 227

Извлечение набора строк………………………………………………………………………………………………………….. 228

Расширенное использование…………………………………………………………………………………………………….. 229

Извлечение одной строки………………………………………………………………………………………………………………… 230

Получение метаданных таблицы………………………………………………………………………………………………………. 231

Кэширование метаданных таблицы…………………………………………………………………………………………………… 231

Расширение класса таблицы…………………………………………………………………………………………………………….. 233

Использование собственных классов строки и набора строк…………………………………………………….. 233

Определение собственной логики для добавления, обновления и удаления строк…………………….. 235

Определение собственных методов для поиска………………………………………………………………………… 235

Определение инфлекции в Zend_Db_Table……………………………………………………………………………….. 236

Zend_Db_Table_Row…………………………………………………………………………………………………………………………… 238

Введение……………………………………………………………………………………………………………………………………….. 238

Извлечение строки………………………………………………………………………………………………………………………….. 238

Чтение значений столбцов из строки…………………………………………………………………………………………………. 238

Получение данных строки в виде массива………………………………………………………………………………………….. 238

Извлечение данных из связанных таблиц…………………………………………………………………………………………… 239

Редактирование строк в БД………………………………………………………………………………………………………………. 239

Изменение значений столбцов в строке……………………………………………………………………………………. 239

Вставка новой строки………………………………………………………………………………………………………………. 239

Изменение значений в нескольких столбцах………………………………………………………………………………………. 240

Удаление строки……………………………………………………………………………………………………………………………… 241

Сериализация и десериализация строк………………………………………………………………………………………………. 241

Сериализация объекта строки…………………………………………………………………………………………………………… 241

Десериализация данных строки………………………………………………………………………………………………………… 241

Восстановление соединения для объекта строки………………………………………………………………………………… 242

Расширение класса строки……………………………………………………………………………………………………………….. 242

Инициализация строки…………………………………………………………………………………………………………………….. 243

Определение собственной логики для добавления, обновления и удаления в Zend_Db_Table_Row…………. 243

Определение инфлекции в Zend_Db_Table_Row………………………………………………………………………………… 245

Zend_Db_Table_Rowset……………………………………………………………………………………………………………………….. 247

Введение……………………………………………………………………………………………………………………………………….. 247

Получение набора строк………………………………………………………………………………………………………………….. 247

Получение строк из набора………………………………………………………………………………………………………………. 247

Получение набора строк в виде массива…………………………………………………………………………………………….. 248

Сериализация и десериализация наборов строк………………………………………………………………………………….. 249

Расширение класса набора строк………………………………………………………………………………………………………. 250

Связи между таблицами Zend_Db_Table………………………………………………………………………………………………… 252

Введение……………………………………………………………………………………………………………………………………….. 252

Определение связей……………………………………………………………………………………………………………………….. 252

Извлечение зависимых строк……………………………………………………………………………………………………………. 254

Извлечение родительской строки……………………………………………………………………………………………………… 256

Извлечение строк через связи “многие-ко-многим”…………………………………………………………………………….. 257

Каскадные операции записи……………………………………………………………………………………………………………… 260

Примечания относительно каскадных операций…………………………………………………………………………………. 261

Zend_Debug………………………………………………………………………………………………………………………………………… 263

Дамп переменных……………………………………………………………………………………………………………………………… 263

Отладка с применением Zend_Log…………………………………………………………………………………………………….. 263

Zend_Dom…………………………………………………………………………………………………………………………………………… 264

Введение…………………………………………………………………………………………………………………………………………… 264

Zend_Dom_Query……………………………………………………………………………………………………………………………….. 264

Теория работы………………………………………………………………………………………………………………………………… 264

Доступные методы………………………………………………………………………………………………………………………….. 266

Zend_Dom_Query……………………………………………………………………………………………………………………………. 266

Zend_Dom_Query_Result………………………………………………………………………………………………………………….. 266

Zend_Exception…………………………………………………………………………………………………………………………………… 267

Использование исключений………………………………………………………………………………………………………………… 267

Basic usage…………………………………………………………………………………………………………………………………………. 267

Previous Exceptions……………………………………………………………………………………………………………………………… 267

Zend_Filter………………………………………………………………………………………………………………………………………….. 269

Введение…………………………………………………………………………………………………………………………………………… 269

Что есть фильтр?……………………………………………………………………………………………………………………………… 269

Основы использования фильтров………………………………………………………………………………………………………. 269

Использование статического метода get()………………………………………………………………………………………….. 269

Цепочки фильтров……………………………………………………………………………………………………………………………… 270

Написание фильтров…………………………………………………………………………………………………………………………… 271

Zend_Form………………………………………………………………………………………………………………………………………….. 272

Zend_Form…………………………………………………………………………………………………………………………………………. 272

Zend_Form – Быстрый старт………………………………………………………………………………………………………………….. 272

Создание объекта формы…………………………………………………………………………………………………………………. 272

Добавление элементов в форму……………………………………………………………………………………………………….. 272

Визуализация формы……………………………………………………………………………………………………………………….. 274

Проверка корректности данных формы……………………………………………………………………………………………… 276

Получение статуса ошибки……………………………………………………………………………………………………………….. 276

Объединяя изложенное…………………………………………………………………………………………………………………… 277

Использование объекта Zend_Config…………………………………………………………………………………………………. 278

Заключение……………………………………………………………………………………………………………………………………. 279

Zend_Http…………………………………………………………………………………………………………………………………………… 280

Zend_Http_Client – Введение………………………………………………………………………………………………………………… 280

Введение……………………………………………………………………………………………………………………………………….. 280

Параметры конфигурации………………………………………………………………………………………………………………… 280

Выполнение базовых HTTP-запросов…………………………………………………………………………………………………. 281

Добавление параметров GET и POST………………………………………………………………………………………………….. 281

Получение последних запроса и ответа……………………………………………………………………………………………… 282

Zend_Json…………………………………………………………………………………………………………………………………………… 284

Введение…………………………………………………………………………………………………………………………………………… 284

Основы применения…………………………………………………………………………………………………………………………… 284

Объекты JSON……………………………………………………………………………………………………………………………………. 284

XML to JSON conversion……………………………………………………………………………………………………………………….. 285

Zend_Layout……………………………………………………………………………………………………………………………………….. 287

Введение…………………………………………………………………………………………………………………………………………… 287

Zend_Layout – Быстрый старт………………………………………………………………………………………………………………… 287

Скрипты макетов…………………………………………………………………………………………………………………………….. 287

Использование Zend_Layout с MVC Zend Framework-а…………………………………………………………………………. 288

Использование Zend_Layout как отдельной компоненты…………………………………………………………………….. 290

Пример макета……………………………………………………………………………………………………………………………….. 292

Опции конфигурирования Zend_Layout…………………………………………………………………………………………………. 293

Примеры………………………………………………………………………………………………………………………………………… 293

Использование Zend_Layout для опытных разработчиков……………………………………………………………………….. 295

Собственные объекты вида………………………………………………………………………………………………………………. 295

Собственные плагины фронт-контроллера…………………………………………………………………………………………. 297

Собственные помощники действий…………………………………………………………………………………………………… 297

Собственное определение пути к скрипту макета: использование инфлектора………………………………………. 297

Zend_Loader……………………………………………………………………………………………………………………………………….. 299

Динамическая загрузка файлов и классов………………………………………………………………………………………………. 299

Zend_Loader vs. require_once()………………………………………………………………………………………………………….. 299

Загрузка файлов………………………………………………………………………………………………………………………………. 299

Загрузка классов……………………………………………………………………………………………………………………………… 299

Проверка на возможность чтения из файла…………………………………………………………………………………………. 300

Использование автозагрузчика…………………………………………………………………………………………………………. 300

Автозагрузчик…………………………………………………………………………………………………………………………………….. 302

Использование автозагрузчика…………………………………………………………………………………………………………. 302

Итерфейс автозагрузчика…………………………………………………………………………………………………………………. 303

Справка по автозагрузчику……………………………………………………………………………………………………………….. 303

Zend_Mail…………………………………………………………………………………………………………………………………………… 310

Введение…………………………………………………………………………………………………………………………………………… 310

Начало работы………………………………………………………………………………………………………………………………… 310

Конфигурирование транспорта, используемого по умолчанию…………………………………………………………….. 310

Отправка через SMTP………………………………………………………………………………………………………………………….. 311

Отправка нескольких сообщений за одно SMTP-соединение…………………………………………………………………… 311

Использование различных транспортов………………………………………………………………………………………………… 312

Сообщение в формате HTML………………………………………………………………………………………………………………… 313

Вложения………………………………………………………………………………………………………………………………………….. 313

Добавление получателей……………………………………………………………………………………………………………………. 314

Контроль за разделителями MIME……………………………………………………………………………………………………….. 314

Дополнительные заголовки………………………………………………………………………………………………………………… 314

Наборы символов……………………………………………………………………………………………………………………………….. 314

Кодировка…………………………………………………………………………………………………………………………………………. 315

SMTP-аутентификация………………………………………………………………………………………………………………………… 315

Securing SMTP Transport………………………………………………………………………………………………………………………. 316

Zend_Navigation…………………………………………………………………………………………………………………………………. 317

Введение…………………………………………………………………………………………………………………………………………… 317

Страницы и контейнеры…………………………………………………………………………………………………………………… 317

Страницы……………………………………………………………………………………………………………………………………….. 317

Контейнеры……………………………………………………………………………………………………………………………………. 317

Разделение данных (модели) и отображения (вида)…………………………………………………………………………… 317

Страницы…………………………………………………………………………………………………………………………………………… 318

Общие функциональные возможности страниц…………………………………………………………………………………… 318

Zend_Navigation_Page_Mvc………………………………………………………………………………………………………………. 320

Zend_Navigation_Page_Uri………………………………………………………………………………………………………………… 323

Creating custom page types………………………………………………………………………………………………………………… 323

Creating pages using the page factory…………………………………………………………………………………………………… 324

Zend_Paginator…………………………………………………………………………………………………………………………………… 327

Введение…………………………………………………………………………………………………………………………………………… 327

Использование…………………………………………………………………………………………………………………………………… 327

Разбиение наборов данных на страницы……………………………………………………………………………………………. 327

Адаптеры DbSelect и DbTableSelect……………………………………………………………………………………………………. 328

Рендеринг страниц через скрипты видов……………………………………………………………………………………………. 329

Примеры постраничной навигации……………………………………………………………………………………………………. 331

Список свойств………………………………………………………………………………………………………………………………… 333

Конфигурация…………………………………………………………………………………………………………………………………….. 334

Расширенное использование………………………………………………………………………………………………………………. 334

Создание собственных адаптеров к источникам данных………………………………………………………………………. 334

Создание своих стилей прокрутки……………………………………………………………………………………………………… 334

Возможности кэширования………………………………………………………………………………………………………………. 335

Интерфейс Zend_Paginator_AdapterAggregate…………………………………………………………………………………….. 336

Zend_Registry……………………………………………………………………………………………………………………………………… 338

Использование реестра………………………………………………………………………………………………………………………. 338

Установка значений в реестре…………………………………………………………………………………………………………… 338

Получение значений из реестра………………………………………………………………………………………………………… 338

Создание объекта реестра……………………………………………………………………………………………………………….. 338

Доступ к реестру как к массиву………………………………………………………………………………………………………….. 339

Доступ к реестру как к объекту…………………………………………………………………………………………………………. 339

Проверка существования индекса……………………………………………………………………………………………………… 340

Создание подклассов……………………………………………………………………………………………………………………….. 341

Уничтожение статического реестра…………………………………………………………………………………………………… 341

Zend_Search_Lucene…………………………………………………………………………………………………………………………… 341

Обзор……………………………………………………………………………………………………………………………………………….. 341

Введение……………………………………………………………………………………………………………………………………….. 341

Объекты документа и поля………………………………………………………………………………………………………………. 342

Значение типов полей……………………………………………………………………………………………………………………… 344

HTML-документы…………………………………………………………………………………………………………………………….. 344

Индексация……………………………………………………………………………………………………………………………………….. 347

Создание нового индекса…………………………………………………………………………………………………………………. 347

Обновление индекса………………………………………………………………………………………………………………………….. 347

Обновление документов………………………………………………………………………………………………………………….. 347

Получение размера индекса…………………………………………………………………………………………………………….. 348

Оптимизация индекса………………………………………………………………………………………………………………………. 348

Опция автоматической оптимизации MaxBufferedDocs………………………………………………………………………… 350

Опция автоматической оптимизации MaxMergeDocs…………………………………………………………………………… 350

Опция автоматической оптимизации MergeFactor……………………………………………………………………………….. 350

Ограничения…………………………………………………………………………………………………………………………………… 351

Поиск по индексу……………………………………………………………………………………………………………………………….. 351

Построение запросов………………………………………………………………………………………………………………………. 351

Парсинг запроса………………………………………………………………………………………………………………………………. 352

Результаты поиска……………………………………………………………………………………………………………………………… 353

Ранжирование результата………………………………………………………………………………………………………………… 354

Сортировка результатов поиска………………………………………………………………………………………………………… 354

Подсветка результатов поиска………………………………………………………………………………………………………….. 355

Язык запросов……………………………………………………………………………………………………………………………………. 355

Элементы………………………………………………………………………………………………………………………………………. 355

Поля………………………………………………………………………………………………………………………………………………. 356

Модификаторы элементов……………………………………………………………………………………………………………….. 356

Поиск по критерию близости…………………………………………………………………………………………………………….. 356

Усиление элемента…………………………………………………………………………………………………………………………. 357

Булевы операторы………………………………………………………………………………………………………………………….. 357

AND………………………………………………………………………………………………………………………………………… 357

OR…………………………………………………………………………………………………………………………………………… 357

NOT…………………………………………………………………………………………………………………………………………. 358

Операторы &&, ||, и !………………………………………………………………………………………………………………………. 358

+………………………………………………………………………………………………………………………………………………. 358

-……………………………………………………………………………………………………………………………………………….. 358

Отсутствие оператора………………………………………………………………………………………………………………………. 358

Групирование…………………………………………………………………………………………………………………………………. 358

Группирование полей……………………………………………………………………………………………………………………… 359

Экранирование специальных символов……………………………………………………………………………………………… 359

API для построения запросов……………………………………………………………………………………………………………….. 360

Исключения, бросаемые парсером запросов……………………………………………………………………………………… 360

Простой запрос (запрос по одному ключевому слову)………………………………………………………………………….. 360

Составной запрос (запрос по нескольким ключевым словам)……………………………………………………………….. 360

Фразовый запрос…………………………………………………………………………………………………………………………….. 362

Кодировки…………………………………………………………………………………………………………………………………………. 365

Поддержка UTF-8 и однобайтных наборов символов…………………………………………………………………………… 365

Используемый по умолчанию анализатор текста………………………………………………………………………………… 365

Совместимый с UTF-8 анализатор текста…………………………………………………………………………………………….. 365

Расширяемость………………………………………………………………………………………………………………………………….. 366

Анализ текста………………………………………………………………………………………………………………………………….. 366

Фильтрация лексем…………………………………………………………………………………………………………………………. 368

Алгоритмы ранжирования………………………………………………………………………………………………………………… 370

Контейнеры хранения……………………………………………………………………………………………………………………… 371

Взаимодействие с Java Lucene………………………………………………………………………………………………………………. 375

Форматы файлов……………………………………………………………………………………………………………………………… 375

Директория для индекса………………………………………………………………………………………………………………….. 375

Исходный код Java…………………………………………………………………………………………………………………………… 375

Zend_Session………………………………………………………………………………………………………………………………………. 376

Введение…………………………………………………………………………………………………………………………………………… 376

Базовое использование………………………………………………………………………………………………………………………. 377

Учебные примеры…………………………………………………………………………………………………………………………… 377

Итерация по пространствам имен……………………………………………………………………………………………………… 378

Методы доступа для пространств имен……………………………………………………………………………………………… 378

Расширенное использование………………………………………………………………………………………………………………. 380

Старт сессии……………………………………………………………………………………………………………………………………. 380

Блокировка пространств имен………………………………………………………………………………………………………….. 381

Время жизни пространства имен……………………………………………………………………………………………………….. 382

Инкапсуляция сессий и контроллеры…………………………………………………………………………………………………. 383

Ограничение количества экземпляров Zend_Session_Namespace до одного на каждое пространство имен.. 384

Работа с массивами в пространствах имен………………………………………………………………………………………….. 385

Использование сессий вместе с аутентификацией……………………………………………………………………………….. 386

Использование сессий с юнит-тестами……………………………………………………………………………………………….. 387

Общее управление сессиями……………………………………………………………………………………………………………….. 390

Zend_Session::setOptions()……………………………………………………………………………………………………………….. 390

Опции……………………………………………………………………………………………………………………………………………. 391

regenerateId()…………………………………………………………………………………………………………………………………. 392

Введение: идентификаторы сессий…………………………………………………………………………………………… 392

Угон и фиксация сессии…………………………………………………………………………………………………………… 394

rememberMe(integer $seconds)…………………………………………………………………………………………………………. 395

forgetMe()………………………………………………………………………………………………………………………………………. 396

sessionExists()………………………………………………………………………………………………………………………………….. 396

destroy(bool $remove_cookie = true, bool $readonly = true)……………………………………………………………………. 396

stop()……………………………………………………………………………………………………………………………………………… 396

writeClose($readonly = true)………………………………………………………………………………………………………………. 396

expireSessionCookie()……………………………………………………………………………………………………………………….. 397

setSaveHandler(Zend_Session_SaveHandler_Interface $interface)……………………………………………………………. 397

namespaceIsset($namespace)……………………………………………………………………………………………………………. 397

namespaceUnset($namespace)………………………………………………………………………………………………………….. 397

namespaceGet($namespace)……………………………………………………………………………………………………………… 397

getIterator()…………………………………………………………………………………………………………………………………….. 398

Zend_Validate…………………………………………………………………………………………………………………………………….. 399

Введение…………………………………………………………………………………………………………………………………………… 399

Что такое валидатор?………………………………………………………………………………………………………………………. 399

Базовое использование валидаторов…………………………………………………………………………………………………. 399

Установка собственных сообщений от ошибках…………………………………………………………………………………… 400

Использование статического метода is()…………………………………………………………………………………………….. 401

Перевод сообщений………………………………………………………………………………………………………………………… 402

Цепочки валидаторов…………………………………………………………………………………………………………………………. 402

Написание валидаторов………………………………………………………………………………………………………………………. 403

Zend_View………………………………………………………………………………………………………………………………………….. 408

Введение…………………………………………………………………………………………………………………………………………… 408

Скрипт контроллера………………………………………………………………………………………………………………………… 408

Скрипт вида……………………………………………………………………………………………………………………………………. 408

Опции……………………………………………………………………………………………………………………………………………. 409

Короткие теги в скриптах вида………………………………………………………………………………………………………….. 410

Вспомогательные аксессоры…………………………………………………………………………………………………………….. 411

Скрипты контроллеров……………………………………………………………………………………………………………………….. 411

Установка переменных……………………………………………………………………………………………………………………. 411

Выполнение скрипта вида………………………………………………………………………………………………………………… 412

Пути к скриптам вида……………………………………………………………………………………………………………………….. 412

Скрипты видов…………………………………………………………………………………………………………………………………… 413

Экранирование вывода……………………………………………………………………………………………………………………. 414

Использование других шаблонизаторов…………………………………………………………………………………………….. 415

Шаблонизаторы c использованием скриптов видов…………………………………………………………………………….. 415

Шаблонизаторы с использованием Zend_View_Interface……………………………………………………………………… 416

Помощники видов………………………………………………………………………………………………………………………………. 422

Начальный набор помощников…………………………………………………………………………………………………………….. 422

Помощник Action…………………………………………………………………………………………………………………………….. 426

Zend_Acl

Введение

Zend_Acl предоставляет легковесную и гибкую реализацию списка прав доступа (ACL) и управления привилегиями. Приложение может использовать такие списки для контроля доступа одних объектов к другим – защищенным.

В рамках данной документации,

Ресурс – объект, доступ к которому контролируется.
Роль – объект, который может запрашивать доступ к ресурсу.

Говоря проще, роли запрашивают доступ к ресурсам. Например, если парковщик запрашивает доступ к автомобилю, то парковщик – это роль, а автомобиль – ресурс, поскольку доступ к автомобилю не может предоставляться всем без исключения.

Благодаря спецификации и использованию списка прав доступа (ACL) приложение может контролировать предоставление ролям доступа к ресурсам.

Ресурсы

Создать ресурс в Zend_Acl очень просто. Zend_Acl предоставляет интерфейс ресурса Zend_Acl_Resource_Interface для облегчения процесса создания ресурса. Этот интерфейс содержит только один метод, getResourceId(). Классу достаточно реализовывать этот интерфейс для того, чтобы Zend_Acl рассматривал объект этого класса как ресурс. Кроме того, Zend_Acl предоставляет Zend_Acl_Resource в качестве базового класса, который разработчики могут расширять по желанию.

Zend_Acl предоставляет древовидную структуру, в которую могут добавляться различные ресурсы. В этой структуре они могут быть организованы от общих (корень дерева) к специфическим (листья дерева). При запросах к определенным ресурсам в иерархии будет выполнен автоматический поиск правил, относящихся к ресурсам-предкам, учитывающий простое наследование правил. Например, если некое общее правило должно действовать в каждом здании города, то проще прикрепить его к городу, чем крепить к каждому зданию в городе. Однако, для некоторых зданий могут потребоваться исключения из этого правила, в Zend_Acl это достигается путем закрепления исключений за каждым зданием, требующим исключений из правила. Ресурс может наследовать только от одного родительского ресурса, однако сам родительский ресурс может, в свою очередь, наследовать от другого родительского ресурса и т.д.

Zend_Acl также поддерживает права доступа к ресурсам (например, “создание”, “чтение”, “обновление”, “удаление”), разработчик может присваивать правила, которые будут влиять на все или определенные права доступа к ресурсу.

Роли

Как и в случае с ресурсами, создавать роль тоже очень просто. Все роли должны реализовывать интерфейс Zend_Acl_Role_Interface. Этот интерфейс содержит единственный метод getRoleId(). Кроме того, Zend_Acl предоставляет Zend_Acl_Role в качестве базового класса, который разработчики могут расширять по желанию.

В Zend_Acl роль может наследовать от одной или от нескольких ролей. Это реализовано для поддержки наследования правил между ролями. Например, пользовательская роль, такая как “Салли”, может принадлежать одной или нескольким родительским ролям, таким как “редактор” и “администратор”. Разработчик может привязывать правила к “редактору” и “администратору” раздельно, и “Салли” будет наследовать правила обоих ролей. Нет необходимости привязывать правила непосредственно к “Салли”.

Хотя множественное наследование ролей – очень полезная возможность, она также усложняет разработку. Следующий пример демонстрирует неопределенное условие и показывает, как Zend_Acl решает эту проблему.

Example #1 Множественное наследование ролей

Следующий код определяет три базовые роли: “guest“, “member” и “admin“, от которых будут наследовать другие роли. Далее создается “someUser“, он наследует от этих только что созданных трех ролей. Порядок, в котором эти роли появляются в массиве $parents, важен. При необходимости Zend_Acl ищет правила доступа не только для запрашиваемых ролей (в нашем случае, “someUser“), но и для ролей, от которых запрашиваемая роль унаследована (в нашем примере, “guest“, “member” и “admin“):

1. $acl = new Zend_Acl();

3. $acl->addRole(new Zend_Acl_Role(‘guest’))

4. ->addRole(new Zend_Acl_Role(‘member’))

5. ->addRole(new Zend_Acl_Role(‘admin’));

7. $parents = array(‘guest’, ‘member’, ‘admin’);

8. $acl->addRole(new Zend_Acl_Role(‘someUser’), $parents);

10.$acl->add(new Zend_Acl_Resource(‘someResource’));

11.

12.$acl->deny(‘guest’, ‘someResource’);

13.$acl->allow(‘member’, ‘someResource’);

14.

15.echo $acl->isAllowed(‘someUser’, ‘someResource’) ? ‘разрешен’ : ‘запрещен’;

Поскольку нет правил, определенных специально для роли “someUser” и ресурса “someResource“, то Zend_Acl должен производить поиск правил, которые могут быть определены для ролей, от которых “someUser” наследуется. Сперва проверяется роль “admin“, и обнаруживается, что для нее не определены правила доступа. Затем проверяется роль “member“, и Zend_Acl обнаруживает, что есть правило разрешающее доступ для “member” к “someResource“.

Download Zend Framework Reference

Structuri de date. Stive. Cozi. (Pascal)

admin — Thu, 04 Aug 2011 14:18:38 +0000

Stucturi de date

8.1 Noţiuni generale

Orice algoritm lucrează cu date (numere întregi, reale, şiruri de caractere etc.). Referitor la acestea, în informatică, s-au cristalizat anumite concepte fundamentale, pe care le vom prezenta în continuare.

Printr-un tip de dată înţelegem o mulţime cu elemente numite valori.

Exemplu:{-32768, 32767, …….0,1,……..32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. Un element al acestei mulţimi este 7 (valoarea 7). În Turbo Pascal un astfel de tip se numeşte integer. Şi este predefinit (este cunoscut de limbaj, nu trebuie definit de programator).

Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului.

Exemplu: Pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc.

Pentru fiecare tip se defineşte modul în care se valorile sale.

Exemplu: Pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi.

Pentru a lucra cu date de un anumit tip se folosesc variabile.

O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi).

Tipuri de date pot fi simple (mulţimile care alcătuiesc nu sunt rezultate ca produs cartezian a altor mulţimi) şi stucturate în caz contrar. Exemplu:tipul integer este simplu, iar tipul record este structurat.

Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date. Limbajul Turbo Pascal este un exemplu în acest sens.

Noţiunea de tip de date este strânsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date.

Exemplu: Mulţimea este o structură de date (după cum vom arăta). În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi. Sarcina noastră este să înţelegem structura de date numită mulţime şi să o implementăm în orice limbaj de programare dorim.

Un curs de algoritmi trebuie să fie independenţi de orice limbaj. Fapt că în aceasta lucrare algoritmii se implementează în Turbo Pascal nu înseamnă că ei pot fi folosiţi numai în acest limbaj. Din acest motiv, orice curs de algoritmi va utiliza noţiunea de structură de date.

Structurile de date se clasifică în două mari categorii:statice şi dinamice.

Criteriul de clasificare este dat de modul de alocare a memoriei interne.

Astfel, pentru structurile statice memoria se alocă la începutul execuţiei programului şi rămăne alocată pînă cînd se încheie execuţia acestuia. Pentru structurile dinamice se alocă memorie în timpul execuţiei programului, iar cînd nu mai este necesară, memoria se eliberează.Modalitatea prin care se poate realiza aceasta în Turbo Pascal va fi arătată chiar în acest capitol.

8.1.1 Structuri statice

Aceste structuri ne sunt deja binecunoscute. În acest capitol le vom prezenta în mod sistematic şi, pe cît posibil, formalizat.

1) Tabloul

Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale.

Fie M=An1 x An2 x…..x Ank produsul cartezian a k astfel de mulţimi.

Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare.

Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente.

Atenţie! Frecvent se confundă numărul componentelor cu dimensiunea tabloului.

De exemplu, despre un vector cu n componente se spune că este de dimensiune n (cînd, de fapt, toţi vectorii au dimensiunea 1).

Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indici (aceştia sunt elemente ale produsului cartezian pe care este definită funcţia).

2) Articolul

Fie A1, A2,….An n mulţimi finite. În general, natura elementelor acestor mulţimi poate fi diferită. De exemplu, A1 poate fi alcătuită din numere întregi, A2 poate fi alcătuită din caractere etc. Fie A=A1xA2x…xAn produsul cartezian a celor n mulţimi. Un articol reţine un element al mulţimii A. Un cîmp reţine un element al mulţimii Ai. Majoritatea limbajelor de programare evaluate cunosc tipul structurat articol (record în Turbo Pascal). Oricare cîmp poate fi, la rîndul său, articol (record în record).

3) Mulţimea

Fie A o mulţime finită. Ea poate fi privită ca o structură de date. Puţine dintre limbaje (Turbo Pascal) admit chiar un tip de date numit mulţime (set). Însă şi aici numărul elementelor unei mulţimi nu poate fi mai mare decît 255 (avantajul este că sunt predefinite operaţiile cu mulţimi ). În ipoteza că programatorul doreşte să implementeze algoritmi care lucrează cu mulţimi, indiferent de limbaj, se poate folosi vectorul caracteristic. Astfel , pentru o mulţime cu n elemente, orice submulţime a sa (v) va fi definită cu ajutorul unui vector cu n componente, în care fiecare componentă poate lua doar două valori 0 şi 1.

¥ i Є{1..n} avem v(i)=

În acest caz, este sarcina programatorului să stimuleze diversele operaţii cu mulţimi.

4) Stiva alocată static

Structura de date numită stivă a fost prezentată şi este binecunoscută cititorului. Nu ne rămîne decît să precizăm faprul că, pînă acum, a fost impementată ca structură statică, cu ajutorul vectorilor . modul în care s-a realizat implementarea ne este clar, cu ajutorul unui vector (ST l-am numit) şi a unei variabile k (indică vîrful ei). Principalul dezavantaj al unei astfel de implementări este dat de faptul că, deşi ca structură de date nu are limitat numărul nivelelor (putem folosi oricîte), practice, numărul acestora nu poate fi mai mare decît numărul componentelor vectorului. Acest dezavantaj se reduce simţitor în cazul cînd în care stivă este implementată dinamic, însă, din cauza limitării memoriei interne, se menţine totuşi.

5) Coada alocată static

Coada este acea structură de date în care toate înserările sunt făcute la unul din capetele cozii, iar toate ştergerile (în general, prelucrările) sunt făcute la celălalt capăt.

Este cu totul nerecomandabilă utilizarea vectorilor pentru stimularea cozii (alocarea statică). Facem această precizare deoarece, în această situaţie are loc un fenomen de migraţie a datelor de la dreapta la stînga în cadrul vectorului.

Să presupunem că stimulăm o coadă cu ajutorul unui vector cu zece componente, care reţin numere întregi. Presupunem de asemenea că niciodată în coadă nu vom mai avea mai mult bde 4 elemente. Introducem în coadă numerele 1,2,3,4. pentru a avea unde să introducem şi alte completăm vectorul de la dreapta la stînga.

Dacă scoatem din coadă pe 1 şi introducem în coadă pe 5, coada va arăta astfel:

Scoatem din coadă pe 2 şi obţinem pe 6:

Se observă acest fenomen de migraţie a datelor, de la dreapta spre stînga.

O altă soluţie ar fi ca, după fiecare stocare de date din coadă, să deplasăm întregul şir de date cărte dreapta, însă în acest caz se consumă mult timp.

O soluţie mai bună de implementare a cozii este să folosim un vector pe care îl privim ca fiind “circular” (facem convenţia ca după ultima componentă să urmeze prima). Adresa componentei de început a cozii va fi reţinută de altă variabilă, iar adresa componentei de sfîrşit va fi reţinută de o altă variabilă. Un astfel de procedeu poate fi folosit, dar nu este recomandabil atît timp cît există alocarea dinamică a memoriei (aşa se lucra prin anii 70, când limbajele “la modă” Fortan şi Cobol nu putea aloca memoria dinamic).

Din cele prezentate nu rezultă în nici un fel la ce foloseşte această structură de date. Deşi are numeroase utilizări (rol fundamental în informatică) pentru moment nu putem da exemple (ne lipsesc condiţiile necesare). Vezi parcurgerea în lăţime a arborilor oarecare.

8.1.2. Alocarea dinamică a memoriei în Turbo Pascal

Din punct de vedere al unui programator, memoria calculatorului se prezintă ca o succesiune de octeţi, fiecare octet avînd o adresă binară bine stabilită. Aceşti octeţi sunt identificaţi prin numere cuprinse între 0 şi n-1. convenim să numim adresă numărul de ordine al unui octet. Un octet este format din 8 biţi. Fiecare bit poate memora fie cifra binară 1, fie cifra binară 0, diversele tipuri de date cunoscute pînă acum (INTEGER, REAL) ocupă 2 sau mai mulţi octeţi consecutive. Pentru fiecare tip de dată cunoscut există o anumită logică potrivit căreia se face memorarea efectivă a conţinutului. De exemplu, pentru tipul INTEGER memorarea se face în COD COMPLEMENTAR. Nu ne propunem să prezentăm modul de reprezintare a datelor. Ne mărginim numai să atragem atenţia că o variabilă folosită de noi în program are un nume (simbolic), o valoare şi o adresă la care o găsim memorată (adresa primului octet din cei p octeţi consecutive ocupaţi de variabilă). În general, în limbajele evaluate nu este necesar ca programatorul să cunoască adresa la care se găsesc variabilele cu care lucrează.

Se cunosc două forme de alocare a memoriei de către programator în cadrul limbajului PASCAL: statică şi dinamică.

Utilizînd forma de alocare statică, variabilele se declară utilizînd cuvîntul cheie VAR la începutul programului.
Utilizînd forma de alocare dinamică, în timpul rulării programului, în funcţie de necesităţi, se alocă memorie suplimentară sau se renunţă la ea.

Pentru alocarea dinamică utilizăm tipul de date referinţă. Se consideră secvenţa de program:

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var c:ref;

Aici variabila c este o variabilă de tip referinţă. Ea reţine adrese de înregistrări. La rîndul ei, o înregistrare are două cîmpuri: nr, care conţine un număr întreg (informaţia utilă) şi adrurm (adresa următoare), care conţine adresa unei alte înregistrări.

Procedura NEW (c) rezervă spaţiu (un număr de octeţi cosecutivi) pentru o înregistrare, adresa primului octet fiind depusă în variabila c. Presupunem că variabila c conţine adresa unei înregistrări.

Procedura DISPOSE (c) eliberează spaţiul de memorie afectat acelei înregistrări care avea adresa în c. Cuvîntul cheie NIL are semnificaţia ” nici o adresă”.

Observaţii:

1) c se referă la adresa care se găseşte în variabila c;

2) c^.nr se referă la cîmpul numeric al înregistrării care are adresa memorată în variabil c;

3) c^.adrurm semnifică adresa de înregistrare care se găseşte memorată în cadrul înregistrării care are adresa c;

4) c^.adrurm.nr semnifică variabila nr care se găseşte în înregistrarea care care adresa plasată în cîmpul adrurm al înregistrării cu adresa c.

Observaţie foarte importantă: spaţiul necesar variabilelor alocate dinamic se rezervă într-o zonă de memorie, special destinată numită HEAP (pentru PC compatibile i.B.M.).

8.2 Structuri dinamice.

8.2.1 Listă liniară simplu înlănţuită

O listă liniară simplu înlănţuită este o structură de forma:

adr1 adr2 adrn

Semnificaţia notaţiilor folosite este următoarea:

adr1, adr2,…,adrn reprezintă adresele din memorie ale celor n înregistrări;
in1, in2,…, inn reprezintă informaţiile utile din cele n înregistrări (altele decît cele de adresă pentru înregistrarea următoare ).

Denumirea “simplu înlănţuită” provine din faptul că fiecare element al listei conţine o singură adresă, şi anume adresa elementului următor din listă. Aici avem o excepţie pentru ultimul element, care are în cîmpul de adresă cuvîntul cheie NIL (semnificînd “nici o adresă”). Operaţiile pe care le putem face în legătură cu această structură de date sunt următoarele:

1) creare;

2) listare;

3) adăugare;

4) ştergere;

În programul care urmează aceste operaţii sunt realizate de procedurile cu acelaşi nume (facem precizarea că, în program, informaţiile utile sunt date de numere 1,2,…,n). Am recurs la această cale din dorinţa de a simplifica pe cît posibil prezentarea.

1) Creare

Se cere numărul n de înregistrări. Se creează o primă înregistrare avînd ca informaţie utilă numărul 1. Variabila b de tip referinţă reţine adresa primei înregistrări din listă. Pentru fiecare i cuprins între 2 şi n se adaugă cite o nouă înregistrare listei. Variabila d reţine adresa ultimei înregistrări deja create pentru a-i completa cîmpul de adresă. Se procedează astfel pentru că în momentul în care am creat o înregistrare nu se cunoaşte adresa înregistrării care urmează.

2) Listare

Am precizat faptul că b reţine adresa primei înregistrări. Pentru a nu deteriora această valoare, o vom memora în variabila c . Atît timp cît nu am ajuns la sfîrşitul listei, tipărim informaţia utilă şi încărcăm în c adresa înregistrării următoare.

3) Adăugare

Operaţia de adăugare a unui nou element la listă comportă cunoaşterea a două informaţii:

Informaţia utilă a elementului (înregistrării) din listă după care urmează să se facă adăugarea;
Informaţia utilă a elmentului care urmează să fie adăugat.

Adăugarea propriu-zisă constă în următoarele:

Poziţionarea pe înregistrarea după care urmează să adăugăm noua înregistrare;
Alocarea spaţiului pentru noua înregistrare;
Completarea informaţiei utile pentru aceasta;
Completarea adresei următoare a noii înregistrări, care va fi adresa următoare a înregistrării pe care suntem poziţionaţi;
Cîmpul de adresă al înregistrării pe care suntem poziţionaţi va lua ca valoare adresa noii înregistrări.

Observaţie:

- Aşa cum este concepută procedura, nu se poate adăuga o primă înregistrare listei. Propunem ca exerciţiu modificarea ei în acest sens.

4) Ştergerea

Pentru a şterge o înregistrare este necesar să cunoaştem informaţia utilă

a acesteia. Vom proceda în mod diferit pentru situaţiile în care se şterge prima înregistrare sau una diferită de prima.

În cazul în care ştergem prima înregistrare, efectuăm operaţiile:

Se salvează în variabila c adresa primei înregistrări (cea care urmează a fi ştearsă);
Variabila b (care reţine adresa primei înregistrări) va lua ca valoare adresa următoare primei înregistrări;
Se eliberează spaţiul rezervat înregistrării şterse;

În situaţia în care ştergem o altă înregistrare decît prima, procedăm în felul următor:

Se face poziţionarea pe înregistrarea care urmează a fi ştearsă;
Cîmpul de adresă al înregistrării precedente capătă valoarea cîmpului de adresă al înregistrării curente;
Eliberăm spaţiul rezervat înregistrării curente.

program 11n;

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var b,c,d:ref;

n,i: integer;

procedure creare;

begin

write (‘n=’); readln(n);

new ( c); c^.nr:=1;

b:=c; d:=c;

for i:=2 to n do

begin

new ( c);

c^.nr:=i;

d^.adrurm:=c;

d:=c

end;

procedure listare;

begin

c:=b;

while c< >nil do

begin

writeln( c^.nr);

c:=c^.adrurm

end

end;

procedure ştergere;

begin

write (‘i=’); readln(i);

if i=1 then

begin

c:=b;

b:=b^.adrurm;

dispose (c)

end

else

begin

c:=b;

while c^.nr< >i do

begin

d:=c;

c:=c^.adrurm

end;

d^.adrurm:=c^.adrurm;

dispose ( c)

end

end;

procedure adăugare;

begin

write(‘i=’); readln(i);

write(‘n=’); readln(n);

c:=b;

while c^.nr< >i do c:=c^.adrurm;

new (d );

d^.nr:=n;

d^.adrurm:=c^.adrurm;

c^.adrurm:=d

end;

begin

creare;

listare;

adăugare;

listare;

ştergere;

listare

end.

În continuare ne propunem să construim şi să tipărim o listă liniară simplu înlănţuită, utilizînd tehnici recursive.

Funcţia lista are sarcina de a construi lista liniară înlănţuită. La început se cere informaţia utilă. În situaţia în care aceasta este diferită de 0 (valoare care semnifică faptul că nu mai avem de adăugat nici un element), se rezervă un spaţiu pentru noua înregistrare, se completează informaţia utilă, iar cîmpul adrurm va lua valoarea funcţiei de tip lista care se autoapelează. În încheiere lista va lua valoarea c a cîmpului care reţine adresa noului element.

Este interesant să observăm că iniţial se creează lista simplu înlănţuită fără a completa cîmpul adresa, această completare urmînd să se facă la revenirea în procedură.

Să ne imaginăm că rulînd acest program dorim să creăm o listă cu două înregistrări care au informaţiile utile 1 şi 2.

Rularea decurge astfel:

Apelăm procedura;
Citim valoarea lui n şi anume 1;
Se alocă spaţiu pentru prima înregistrare;
Completăm informaţia utilă;
Pentru a completa adresa următoare înregistrării curente, se apelează din nou funcţia;
Citim valoarea lui n şi anume 2;
Alocăm spaţiu pentru a doua înregistrare;
Completăm informaţia utilă cu 2;
Se apelează din nou funcţia;
Se citeşte 0;
Funcţia ia valoarea NIL;
Se revine din apel şi se continuă de acolo de unde am rămas;
Cîmpul de adresă al celei de a doua înregistrări va lua valoarea NIL;
Funcţia capătă valoarea adresei înregistrării 2,
Se revine din apel;
Cîmpul de adresă al primei înregistrări ia valoarea celei de-a doua înregistrări;
Funcţia ia valoarea adresei primei înregistrări;
Se revine în programul principal.

Observăm că valoarea variabilei c a programului principal va fi după rulare adresa primei înregistrări.

Propunem ca exerciţiu construirea listei utilizînd o procedură recursivă. Putem defini recursiv lista astfel:

O mulţime vidă de înregistrări este o listă;
Dacă la o listă se adaugă o înregistrare, se obţine o listă.

Recursiv putem tipări informaţia utilă din listă în două moduri:

În ordinea în care a fost creată;
În ordinea inversă celei în care a fost creată.

Lăsăm pe seama cititorului analiza acestor două proceduri.

program 11r;

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var n:integer;

c:ref;

function lista:ref;

var c:ref;

begin

write(‘n=’); readln(n);

if n< >0

then

begin

new(c);

c^.nr:=n;

c^.adrurm:=lista;

lista:=c;

end

else lista:nil

end;

procedure tipard(c:ref);

begin

if c< >nil

then

begin

writeln(c^.nr);

tipard (c^.adrurm)

end

end;

procedure tipari(c:ref);

begin

if c< > nil tfen

begin

tipari (c^.adrurm);

writeln(c^.nr)

end

end;

begin

c:=lista;

tipard©;

writeln(‘————’);

tipari©

end.

Aplicaţie (Sortare topologică)

Presupunem că dorim sortarea numerelor. 1, 2, ….., n, numere care se găsesc într-o ordine oarecare, alta decît naturală. Pentru a afla relaţia în care se găsesc numerele, introducem un număr finit de perechi (i,j). O astfel de pereche ne spune că, în relaţia de ordine considerată, i se află înaintea lui j.

Exemplu 1: n=3 şi citim perechile (3,1) şi (3,2). Numărul 3 se află înaintea lui1 şi 3 se află înaintea lui 2. Apar două soluţii posibile: 3,1,2 şi 3,2,1, întucît nu avem nici o informaţie asupra relaţiilor dintre 1şi 2. Tragem de aici concluzia că o astfel de problemă poate avea mai multe soluţii.

Exemplu 2: n=3 şi citim (1,2), (2,3), (3,1). În acest caz nu avem soluţie.di primele două relaţii rezultă că ordinea ar fi 1,2,3 iar a-3-a contrazice această ordine.

În concluzie, problema ar avea sau nu soluţie, iar dacă are poate fi sau nu unică.

Algoritmul pe care îl prezentăm în continuare furnizează o singură soluţie atunci cînd problema admite soluţii. În caz contrar specifică faptul că problema nu admite soluţie.

Vom exemplifica funcţionarea algoritmului pe exemplu următor: n=4 şi se citesc perechile (3,4), (4,2), (1,2), (3,1).

Pentru fiecare număr între 1 şi n trebuie să avem următoarele informaţii:

Numărul predecesorilor săi;
Succesorii săi;

Pentru aceasta folosi doi vectori:

contor, vector care reţine numărul predecesorilor fiecărui k, cu k Є {1..n}.
a, care reţine adresele de început ale listelor de succesori ai fiecărui element.

Pentru fiecare element există o listă simplu înlănţuită a succesorulor săi. Fiecare înregistrare din aceste liste conţine două elemente:

succesorul;
adresa următorului element din listă.

Iniţial, în dreptul fiecărui element în vectorul „contor” se trece 0, iar în vectorul „a” se trece NIL.

Citirea unei perechi (i,j) înseamnă efectuarea următoarelor operaţii:

mărirea cu 1 a cîmpului contor (j) (j are un predecesor, şi anume pe i);
adăugarea lui j la lista succesorului lui i.

Pentru exemplu nostru, lucrurile decurg astfel:

CONTOR

În continuare se procedează astfel:

toate elementele au 0 în cîmpul lui contor se reţine într-un vector c;
pentru fiecare element al vectorului c se procedează astfel:
- se tipăreşte;
- se marchează cu -1 cîmpul său de contor;
- pentru toţi succesorii săi (aflaţi în lista succesorilor) se scade cu 1 din cîmpul contor (este normal, întrucît aceştia au un predecesor mai puţin).
- Se reia algoritmul dacă nu este îndeplinită una din condiţiile următoare:

v Au fost tipărite toate elementele, caz în care algoritmul se încheie cu succes;

v Nu avem nici un element cu 0 în cîmpul contor, caz în care relaţiile au fost incoerente.

1	2	-1	0
al1	nil	al3	al4
2		4	2

tipăresc 3, scad 1 din predecesorii lui 4 şi 1, cu -1 contorul lui 3;

0	1	-1	-1

Observaţie:

Algoritmul are mai multe aplicaţii, ca de exemplu:

Ordonarea unor activităţi, atunci cînd ele sunt condiţionate una după alta;
Ordonarea unor termeni care se cer explicaţi pentru a-i putea explica prin alţi deja prezentaţi.

Program stoop;

type ref=^inr;

inr=record

succ:integer;

urm:ref

end;

vector=array [1..100] of integer;

vectad=array [1..100]of ref;

var n, m, i, j, k:integer;

contor, c:vector;

a:vectad;

gasit:boolean;

procedure adaug (i,j:integer);

var c,d:ref;

begin

contor [j]:=contor [j]+1;

c:=a[i];

new (d);

d^.urm:=nil;

d^.succ:=j;

if c=nil

then a[i]:=d

else

begin

while c^.urm< >nil do c:=c^.urm;

c^.urm:=d

end

end;

procedure actual (i:integer);

var c:ref;

begin

c:=a[i];

while c < >nil do

begin

contor [c^.succ]:=contor[c^.succ]-1;

c:=c^.urm

end

end;

begin

write (’n=’); readln(n);

for i:=1 to n do

begin

contor [i]:=0;

a[i]:=nil

end;

while i< >0 do

begin

write (’tastati i,j=’);

readln (i,j);

if i< >0 then adaug (i,j)

end;

m:=n;

repeat

k:=1;

gasit:false;

for i:=1 to n do if contor [i]=0

then

begin

gasit:=true;

m:=m-1;

c[k]:=1;

k:=k+1;

contor [i]:=-1

end;

for i:=1 to k-1 do

begin

actual (c[i]);

writeln (c[i]);

end;

until (not gasit) or (m=0);

if m=0

then writeln (’totul e ok’)

else writeln (’relatii contradictorii’)

end.

8.2.2 Lista liniară dublu înlănţuită

O listă dublu înlănţuită este o structură de date de forma:

adr1 adr2 adrn

Operaţiile pe care le putem face cu o listă dublu înlănţuită sunt următoarele:

1) Creare;

2) Adăugare la dreapta;

3) Adăugare la stînga;

4) Adăugare în interiorul listei;

5) Ştergere din interiorul listei;

6) Ştergere la sînga listei;

7) Ştergere la dreapta listei;

8) Listare de la sînga la dreapta;

9) Listare de la dreapta la sînga;

1) Creare

O listă dublu înlănţuită se creează cu o singură înregistrare. Pentru a ajunge la numărul de înregistrări dorit, utilizăm proceduri de adăugare la stînga sau la dreapta. În programul de faţă acest lucru este realizat de procedura creare. Această procedură realizează operaţiile următoare:

Citirea informaţiei utile;
Completarea înregistrării cu informaţia utilă;
Completarea adreselor de legătură la stînga şi la dreapta cu NIL;
Variabilele tip referinţă b şi s vor căpăta valoarea adresei acestei prime înregistrări (b semnfică adresa înregistrării cea de mai din stînga, s adresa ultimei înregistrări din dreapta).

2) Adăugarea la dreapta

Această operaţie este realizată de procedura addr. Pentru adăugarea unei înregistrări se realizează următoarele operaţii:

Citirea informaţiei utile;
Alocarea spaţiului pentru înregistrare;
Completarea adresei la dreapta cu NIL;
Completarea adresei din stînga şcu adresa celei mai din dreapta înregistrări (reţinute în variabila s);
Modificare cîmpului de adresă la dreapta a înregistrării din s cu adresa noii înregistrări;
s va lua valorile noi înregistrări, deoarece va fi cea mai din dreapta.

3) Adăugarea la stînga

Această operaţie o propunem ca exerciţiu.

4) Adăugare în interiorul listei

Această operaţie este realizată de procedura includ, care realizează următoarele operaţii:

ü Parcurge lista de la stînga la dreapta căutînd înregistarea cu informaţia utilă m, în dreapta căreia urmează să introducem noua înregisrare;

ü Citeşte informaţia utilă;

ü Alocă spaţiu pentru noua înregistrare;

ü Completează informaţia utilă;

ü Adresa stîngă a noii înregistrări ia valoarea adresei înregistrării de informaţie utilă m;

ü Adresa dreaptă a noii înregistrări ia valoarea adresei dreapta a înregistrării de informaţia utilă m;

ü Adresa dreaptă a înregistrării cu informaţia utilă m ia valoarea noii înregistrări;

Observaţie:

Propunem ca exerciţiu realizarea unei proceduri de adăugare în interiorul listei a unei înregistrări la dreapta înregistrării cu informaţia utilă m.

5) Ştergere din interiorul listei

Această operaţie este realizată de procedura sterg. Operaţiile efectuate de această procedură următoarele:

ü Se parcurge lista de la stînga la dreapta pentru a ne poziţiona pe înregistrarea care urmează a fi ştearsă;

ü Cîmpul de adresă dreapta al înregistrării care o precede pe această şi va lua valoarea cîmpului de adresă dreapta al înregistrării care va fi ştearsă;

ü Cîmpul de adresă stînga al înregistrării care urmează înregistrării care va fi ştearsă va lua valoarea cîmpului de adresă stînga al înregistrării pe care o ştergem;

ü Se eliberează spaţiul de memorie rezervat înregistrării care se şterge.

6)-7) Ştergere la sînga şi la dreapta listei

Aceste două operaţii sunt propuse cititorului ca exerciţiu.

8) Listare de la sînga la dreapta

Această operaţie este realizată de procedura listare, procedură care realizează următoarele operaţii:

v Porneşte din stînga listei;

v Atît timp cît nun s-a ajuns la capătul din dreapta al listei, se tipăreşte informaţia utilă şi se trece la înregistrarea următoare.

9) Listare de la dreapta la sînga

O propunem ca exerciţiu.

Program 1di;

type ref=^inr;

inr=record

as:ref;

nr:integer;

ad:ref

end;

var b,s,c:ref;

n,m,i:integer;

procedure creare (var b,s:ref);

begin

write (‘n=’); readln (n);

new (b); b^.nr:=n;

b^.as:=nil; b^.ad:=nil;

s:=b

end;

procedure addr (var s:ref);

var d:ref;

begin

write (‘n=’); readln (n);

new (d); d^.nr:=n;

d^.as:=s; d^.ad:=nil;

s^.ad:=d; s:=d

end;

procedure listare (b:ref);

var d:ref;

begin

d:=b;

while d< >nil do

begin

writeln (d^.nr);

d:=d^.ad

end

end;

procedure include (m:integer; b:ref);

var d,e:ref;

begin

d:=b;

while d^.nr< >m do d:d^.ad;

write (‘n=’); readln (n);

new (e);

e^.nr:=n;

e^.as:=d;

d^.ad^.as:=e;

e^.ad:=d^.ad;

d^.ad:=e

end;

procedure sterg (m:integer; b:ref);

var d:ref;

begin

d:=b;

while d^.nr< >m do d:=d^.ad;

d^.as^.ad:=d^.ad;

d^.ad^.as:=d^.as;

dispose (d)

end;

begin

writeln (‘creare lista cu o singura inregistrare’);

creare (b, s);

write (‘cite inregistrari se adauga?’);

readln (m);

for i:=1 to m do addr (s);

writeln (‘acum listez de la stinga la dreapta’);

listare (b);

writeln (‘includem la dreapta o inregistrare’);

write (‘dupa care inregistrare se facec includerea?’);

readln (m);

include (m,b);

writeln (‘acum listez de la stinga la dreapta’);

listare (b);

writeln (‘Acum stergem o inregistrare din interior’);

write (‘Ce inregistrare stergem?’);

readln (m);

sterg (m,b);

writeln (‘Acum listez de la stinga la dreapta’);

listare (b)

end.

8.2.3 Lista circulară

Se consideră o listă liniară. Dacă, ultima înregistrare, adresa următoare va fi înregistrării, am definit o listă circulară. În cazul în care lista iniţială este simplu înlănţuită, listă circulară va fi simplu înlănţuită, iar dacă listă iniţială este dublu înlănţuită şi lista ciculară va fi dublu înlănţuită.

Întucît operaţiile care se efectuează cu aceasta sunt asemănătoare cu cele prezente anterior, ne oprim cu explicaţiile în acest punct.

8.2.4 Stiva

O stivă poate fi definită şi ca o listă liniară simplu înlănţuită în care toate intrările şi ieşirile se fac la un singur capăt al ei.

În acest caz, elementul de pe nivelul k al stivei va reţine adresa elementului de pe nivelul k-1.

În versiunile anterioare ale acestei cărţi am prezentat stiva ca fiind o listă liniară dublu înlănţuită, fapt pentru care am fost criticat. Motivul? Prezentînd stiva ca o listă dublu înlănţuită, am avantajul că o pot folosi în mai multe aplicaţii (de exemplu, pentru backtracking, unde pentru a valida un element era necesară comparaţia sa cu cele aflate în stivă pe nivelele inferioare). Desigur, chiar folosind pentru stiva actuala definiţie (prezentă în toate lucrările de specialitate) putem realiza toate aplicaţiile făcute pînă în acest moment, însă mai greu (recursiv, cu pierdere de timp). Chiar modul de lucru standart cu stiva calculatorului (în limbaj de asamblare) permite accesul la elemente ale stivei care nu se află pe ultimul nivel.

Datorită celor prezentate, vom implementa stiva tot ca listă liniară dublu înlănţuită. Cititorul, dacă nu este de acord cu aceasta, îşi poate scrie propriile rutine.

Fiecare înregistrare corespunzătoare stivei conţine trei informaţii: adresa înainte (a elementului următor), adresa înapoi şi informaţia utilă care se diferă de la caz la caz.

Pentru a lucra cu o astfel de stivă sunt suficiente două proceduri: adaug şi scot, cu rolul de a adăuga şi, respectiv, de a scoate o informaţie din stivă. Modul de alcătuire al acestora îl putem analiza din programul următor:

Program stivă;

type ref=^inr;

inr=record

adrurm, adrinap:ref

end;

var v:ref;

n:integer;

procedure adaug (var v:ref);

var c:ref;

n:integer;

begin

write (‘n=’); readln (n);

new (c);

c^.nr:=n;

c^.adrurm:=nil;

c^.adrinap:=v;

if v< >nil then v^.adrurm:=c;

v:=c

end;

procedure scot (var v:ref);

var c:ref;

begin

if v=nil

then

writeln (’Stiva este vida’)

else

begin

writeln (v^.nr);

c:=v;

v:=v^.adrinap;

dispose (c)

end

end;

begin

adaug (v); adaug (v);

scot (v); scot (v); scot (v)

end.

Spre deosebire de stimularea stivei prin intermediul vectorilor, aici avem avantajul că stiva nu este limitată la cele n componente alocate vectorului. Principalul dezavantaj al acestui mod de stimulaqre a stivei este faptul că pe lîngă informaţia utilă se reţin informaţii de adresă, fapt care duce la consum de memorie.

8.2.5 Coada

Structura de coadă a fost deja prezentată (nu şi exemplificată). Reamintim faptul că toate intrările se fac la un capăt şi toate ieşirile se fac la celălalt capăt. Coada nu se poate implementa dinamic cu mare uşurinţă. Astfel va fi implementată ca o listă simplu înlănţuită (sau, pentru a uşura anumite operaţii, chiar dublu înlănţuită). O variabilă de tip referinţă va reţine o adresă de început a cozii, iar alta de acelaşi tip va reţine adresa de sfîrşit. Exerciţiu: scrieţi un program care creează o coadă cu două, trei elemente, apoi le scoate. La sfîrşit se va da mesajul coadă vidă (asemănător cu programul care exemplifică stiva).

8.2.6 Structuri arborescente

8.2.6.1 Arbori binari

Vom defini arborii binari ca un set finit T de unul sau mai multe noduri, astfel încît:

există un nod cu destinaţie specială numită tulpina (rădăcina) arborelui;
Celelalte noduri sunt repartizate în două seturi disjuncte şi fiecare din aceste seturi este la rîndul lui un arbore.

Observaţii:

Cei doi arbori subordonaţi tulpinei poartă denumirea de subarbore stîng şi subarbore drept,
Definiţia este recursivă, acest lucru fiind de mare folos în continuare,
În cele ce urmează, pentru tulpină vom folosi şi termenul de vîrf,
Dacă un nod nu subordonează arbori, îl vom numi nod terminal, în caz contrar îl vom numi nod neterminal.

Ne propunem să construim un program care generează în memorie un arbore binar. Pentru aceasta, fiecare nod va fi o înregistrare care conţine trei cîmpuri: informaţia utilă, adresa subarborelui stîng şi adresa subarborelui drept. Modul recursiv de definire a arborilor binari ne conduce la ideea de a folosi o funcţie recursivă şi chiar de a utiliza metoda DIVIDE ET IMPERA conform acestei metode se procedează astfel:

Se citeşte informaţia utilă pentru un nod;

Se alocă spaţiu în memorie pentru aceasta;

Se completează informaţia utilă;

Se costruieşte subarborele stâng;

Se costruieşte subarborele drept;

Exact în acest mod se procedează funcţia arb de tip referinţă. Aici, este de remarcat modalitate de trecere la construcţia subarborilor stâg şi drept. Atunci cînd trebuie completate cîmpurile de adresă, acestea primesc ca valoare funcţiei, ceea ce duce autoapelarea ei. Semnalizarea faptului că nu avem subarbore stîng sau drept se face completînd 0 pentru informaţia utilă.

În principal se folosesc trei metode de parcurgere a arborilor.

Stînga, vîrf, dreapta sau inordine, în care se parcurg mai întîi subarborele stîng, rădăcina şi apoi subarborele drept;
Vîrf, stînga, dreapta saunpreordine, în care se parcurg mai întîi rădăcina, subarborele stîng şi apoi subarborele drept;
Stînga, dreapta, vîrf sau postordine, în care se parcurg mai întîi subarborele stîng, subarborele drept şi apoi rădăcina.

Fie arborele de mai jos:

Datele se introduc astfel:

1240050800360079001000.

Parcurgerea în inordine înseamnă:

4 2 5 8 1 6 3 9 7 10.

Parcurgerea în preordine înseamnă:

1 2 4 5 8 3 6 7 9 10.

Parcurgerea în postordine înseamnă:

8 5 2 6 9 10 7 3 1.

Parcurgerile arborului binar sunt realizate de procedurile: svd ( Stînga, vîrf, dreapta), vsd (Vîrf, stînga, dreapta), sdv (Stînga, dreapta, vîrf).în comentariul pe care îl facem acestor proceduri ne mărginim să precizăm că sunt realizate utilizînd tehnica DIVIDE ET IMPERA.

Program arbori;

type ref=^inr;

inr=record

st,dr:ref;

nr:integer

end;

var c:ref;

function arb:ref;

var n:integer;

c:ref;

begin

write (‘n=); readln (n);

if n< >0

then

begin

new (c);

arb:=c;

arb^.nr:=n;

arb^.st:=arb;

arb^.dr:=arb

end

else arb:=nil

end;

procedure svd (c:ref);

begin

if c< >nil

then

begin

svd (c^.st);

writeln (c^.nr);

svd (c^.dr)

end

end;

procedure vsd (c:ref);

begin

if c< >nil

then

begin

writeln (c^.nr);

vsd (c^.st);

vsd (c^.dr)

end

end;

procedure sdv (c:ref);

begin

if c< >nil

then

begin

svd (c^.st);

svd (c^.dr);

writeln (c^.nr)

end

end;

begin

c:=arb;

writeln (‘Parcurg stinga virf dreapta’);

svd(c);

writeln (‘Parcurg virf stinga dreapta’);

vsd (c);

writeln (‘Parcurg stinga dreapta virf’);

sdv (c)

end.

Aplicaţie. Forma poloneză

Se dă o expresie aritmetică. Să se construiască forma poloneză asociată acesteia.

Acest exerciţiu l-am rezolvat utilizînd diagramele de sintaxă. În acest capitol îl vom rezolva cu ajutorul arborilor binari. Tehnica de programare folosită va fi DEVIDE ET IMPERA.

Expresiile aritmetice pot fi reprezentate utilizînd arbori binari, respectînd următoarele reguli:

Fiecare operaţie corespunde unui nod neterminal, avînd ca informaţie utilă operaţia respectivă;
Fiecare nod terminal este etichetat cu o variabilă sau cu o constantă;
Pentru fiecare nod neterminal subarborele din stînga şi cel din dreapta reprezintă, în această ordine, cei doi operanzi;
Rădăcina corespunde ultimei operaţii executate la evaluarea expresiei.

Exemplu: Expresiei (a+b)*c-d/e i se asociază arborele binar din figura de mai jos. Parcurgerea acestui arbore în postordine va da chir forma poloneză: ab+c*de/-. Utilizînd cele spuse, pentru rezolvarea problemei, vom proceda în felul următor:

Construim arborele binar asociat, expresiei aritmetice;
Îl parcurgem în postordine pentru a obţine forma poloneză.

Parcurgerea arborelui a fost deja prezentată, problema principală rămînînd construirea acestuia.

Pentru aceasta vom acorda priorităţi operatorilor şi operanzilor (mai puţin parantezelor), după cum urmează:

Prioritatea iniţială a operatorilor ‘+’, ‘-’ este 1;
Prioritatea iniţială a operatorilor ‘*’, ‘/’ este 10;
La prioritatea unui operator se adună 10 pentru fiecare pereche de paranteze între care se găseşte;
Prioritatea unui operand este 1000.

În program acest lucru se realizează astfel:

Se citeşte expresia aritmetică în variabila e;
Se utilizează o variabilă j care indică ce număr se adaugă la prioritatea iniţială a unui operator (la întîlnirea unei paranteze deschise j creşte cu 10, iar la întîlnirea unei paranteze închise j scade cu 10);
Se parcurge expresia caracter cu caracter şi se pun în vectorul p priorităţile acestor operatori şi operanzi (mai puţin ale parantezelor);
În efp se construieşte expresia fără paranteze (la expresia aritmetică iniţială lipsesc parantezele), iar în pfp se obţine vectorul priorităţilor, din care, spre deosebire de p, lipsesc componentele corespunzătoare parantezelor (acestea nu aveau nici o valoare).

Utilizînd efp şi pfp ,cu ajutorul funcţiei arb, se construieşte arborele ataşat expresiei aritmetice. Un nod al acestui arbore are ca informaţie utilă un operator sau un operand.

Conform tehnicii DIVIDE ET IMPERA, funcţia arb procedează în felul următor:

de la limita superioară către limita inferioară (limite corespunzătoare subşirurilor de caractere tratate din efp) caută operatorul sau operandul cu prioritate minimă, reţinînd poziţia acestuia;
acesta constituie informaţia utilă din nod, care va fi completată;
în situaţia în care limita inferioară este diferită de limita superioară, pentru completarea adresei subarborelui din stînga şi a arborelui din dreapta se reapelează funcţia, iar în caz contrar aceste cîmpuri capătă valoarea NIL.

Pentru listarea în postordine se utilizează procedura parc .

program fp;

type ref=^inr;

sir=array [1..30] of char;

vector=array [1..30] of integer; inr=record

as, ad:ref;

op:char

end;

var e, efp:sir;

pfp, p:vector;

i, j, n:integer;

c:ref;

a:char;

function arb (1i,1s:integer; var efp:sir; var pfp:vector):ref;

var c:ref;

i, j, min: integer;

begin

min:=pfp [1s];

i:=1s;

for j:= 1s downto 1i do

if pfp [j] then

begin

min:=pfp [j];

i:=j

end;

new ( c);

arb:=c;

arb^.op:=efp [i];

if 1i=1s

then

begin

arb^.as:=nil;

arb^.ad:=nil

end

else

begin

arb^.as:=arb(1i, i-1, efp, pfp);

arb^.ad:=arb(i+1, 1s, efp, pfp)

end

end;

procedure parc (c:ref);

begin

if c< >nil

then

begin

parc ( c^.as);

parc (c^.ad);

write (c^.op)

end

end;

begin

j:=0;

read (a);

n:=1;

while a< >’.’ do

begin

e [n]:=a;

n;=n+1;

read (a )

end;

n:=n-1;

for I;=1 to n do

case e[i] of

‘)’:j:=j-10;

‘(‘:j:=j+10;

‘+’,’-‘:p[i]:=j+1;

‘*’,’/’:p[i]:=j+10

else p[i]:=1000

end;

j:=1;

for i:=1 to n do

if (e[i] < >’)’) and ( e[i]< >’(‘)

then

begin

efp[j]:=e[i];

pfp[j]:=p[i];

j:=j+1

end;

c:=arb (1,j-1, efp,pfp);

parc ( c);

writeln

end.

Aplicaţie. Arbori de căutare

Se numeşte arbore de căutare un arbore binar ale cărui noduri au o cheie de identificare ( mulţimea cheilor asociate nodurilor este o mulţime bine ordonată – între oricare două elemente distincte ale acestei mulţimi a şi b avem sau a>b sau a

Orice cheie asociată unui nod al subarborelui stîng este mai mică decît cheia asociată nodului;

Orice cheie asociată unui nod al subarborelui drept este mai mare decît cheia asociată nodului.

Orice nod al arborelui are asociate trei informaţii

Cheia de identificare (NR);

Adresa subarborelui stîng (AS);

Adresa subarborelui drept (AD).

Arborii de căutare au fost creaţi pentru regăsirea rapidă a informaţiei.

Aplicaţiile care creează şi actualizează un arbore de căutare, care reţine numerele naturale citite (acestea var fi şi chei asociate noduri).

Vor fi prezentate următoarele funcţii:

Inserarea şi căutarea;

Listarea;

Ştergerea;

Inserarea şi căutarea

Crearea arborilor de căutare se face aplicînd de un număr de ori operaţia de inserare. Regula de inserare este următoarea:

se compară cheia asociată a unui nod cu numărul de inserat;avem trei posibilităţi:

cheia coincide cu numărul – se renunţă la inserarea acelui număr;

cheia este mai mare decît numărul – se încearcă inserarea în subarborele stîng;

cheia este mai mic decît numărul – se încearcă inserarea în subarborele drept.

Inserarea propriu-zisă se realizează atunci cînd subarborele stîng, respectiv drept, este vid, altfel se reia.

Mecanismul descris este tipic tehnicii DIVIDE ET IMPERA.

Pornim de la un arbore de căutare vid. Inserăm numărul 10.

10

Inserăm 5. Acest număr se inserează în subarborele sting.

Inserăm 7. Acesta este mai mic decît 10. Se trece la subarborele stîng. Se compară cu 5, faţă de care este mai mare. Se inserează în subarborele drept.

Se inserează 15; cum acesta este mai mare decît 10 vom avea:

Iată cum arată arborele după inserarea numerelor 3, 9, 12, 30.

Operaţia de căutare este asemănătoare cu cea de inserare. Cheia căutată se compară cu cheia asociată vîrfului. În caz de egalitate imformaţia a fost găsită. Dacă este mai mică decît cheia asociată nodului, se caută în subarborele stîng iar dacă este mai mare se caută în subarborele drept. Dacă în procesul de căutare s-a ajuns să se caute cheia într-un subarbore vid, înseamnă că nodul cu cheia respectivă lipseşte.

Programul care urmează conţine o procedură de inserare (C_I). Când cheia pentru care se încearcă inserarea lipseşte se execută inserarea, altfel se dă un mesaj corespunzător.

Transmiterea parametrului c se face prin referinţă. Adresa de alocare (obţinută prin NEW) va fi trecută automat părintelui, ca adresă de subarbore stîng sau drept (după caz).

Odată creat, un arbore de căutare permite regăsirea mai rapidă a informaţiei decât în cazul în care ar fi memorate secvenţial. Odată analizată informaţia ataşată prin nod, în caz de inegalitate se trece la subarborele stâng (sau drept) caz în care informaţiile cu cheile din subarborele drept (sau stâng) nu se mai ia în calcul. Numărul de comparaţii este mai mic sau egal cu numărul de niveluri ale arborelui de căutare. De exemplu, pentru regăsirea unei imformaţii, în cadrul arborelui din figură se fac cel mult 4 comparaţii. Dacă pentru memorizare se utilizează o listă simplu înlănţuită, în cazul cel mai defavorabil trebuie de efectuate 8 comparaţii.

Există totuţi o problemă care poate duce la scăderea eficienţei de căutare. În cazul în care cheile sunt introduse în ordine strict crescătoare sau în ordine descrescătoare, arborele degenerează într-o listă liniară (fiecare nod are un singur subarbore nevid). Putem aprecia că introducerea numerelor în această ordine este improbabilă.

Listarea informaţiei

Informaţia se poate lista utilizând oricare din metodele cunoscute pentru parcurgerea arborilor. Dacă dorim listarea imformaţiilor în ordinea strict crescătoare a cheilor, se utilizează metoda stânga-vârf-dreapta (inordine), întucât pentru orice nod avem următoarele:

cheile nodurilor din subarborele stâng sunt mai mici decât cheia asociată nodului;

cheile nodurilor din subarborele drept sunt mai mari decât cheia asociată nodului.

Vom lista arborele stâng,informaţia din nod şi informaţiile din subarborele drept (SVD).

Ştergerea

După ştergerea unui nod care are o anumită cheie, arborele rămas trebuie să fie de căutare. Nodul care urmează a fi şters se caută după metoda de acum binecunoscută. Se disting 4 situaşii posibil:

a)     nodul care urmează a fi şters este nod terminal – în acest caz se face ştergerea având grijă ca la părintele lui să înlocuim adresa către el cu NIL;

b)    nodul care urmează a fi şters subordonează un singur subarbore – cel drept – caz în care părintelui i se va înlocui adresa către el cu adresa subarborelui drept, iar nodul respectiv se va şterge;

c)     nodul care urmează a fi şters subordonează un singur subarbore – cel stâng – caz în care părintelui i se va înlocui adresa către el cu adresa subarborelui stâng, iar nodul respectiv se va şterge;

d)    nodul care urmează a fi şters (după cum vom vedea, acesta se va şterge numai logic) subordonează doi subarbori, caz în care se fac operaţiile:

se identifică cel mai din dreapta nod al subarborelui stâng corespunzător nodului care urmează a fi şters (acesta va fi şters ăn mod efectiv, ni înainte de a muta informaţiile sale la nodul care se şterge logic);

cheia acestuia şi alte informaţii utile conţinute de el (altele decât cele de adresă) se mută lanodul care urmează a fi şters;

subarborele stâng care se va şterge fizic se leagă:

în stânga nodului care se va şterge logic (dacă nodul identificat ca cel mai din dreapta din subarborele stâng este descendentdirect al nodului care se va şterge logic)

în dreapta tatălui nodului care se va şterge fizic (în caz contrar);

se şterge fizic nodul care a fost identificat şi ale cărui informaţii au fost mutate (cu cheia cea mai mare din suarborele stâng).

Exemlu: pentru cazul d):

Fie arborele din figura de mai jos la care se şterge nodul 6:

se identifică nodul cel mai din dreapta pentru subarborele stâng (5);

el nu este descendent direct al nodului care se şterge (6);

informaţia sa se trece nodului şi se obţine:

subarborele stâng al nodului care se şterge fizic este dat de nodul 4;

acesta se leagă în dreapta tatălui nodului care se şterge fizic (3);

se execută ştergerea fizică şi se obţine:

Ştergerea unui nod este realizată de procedura ŞTERG. Pentru situaţia în care un nod care urmează a fi şters subordonează doi arbori, se apelează procedura CMMD.

Mecanismul de transmitere al parametrilor prin referinţă face ca această procedură să fie exterm de scurtă. Astfel, căutarea nodului cel mai din dreapta pentru subarborele stâng (adresa F) se face recursiv, ce procedura a fost apelată pentru primul nod al subarborelui stâng. În situaţia în care acesta este subordonat direct nodului care se şterge, procedura nu se autoapelează, iar după transferul informaţiilor adresa subarborelui stâng (F^.AS) trece ca adresă în stînga nodului care se şterge logic. În caz contrar, datorită faptului că procedura s-a autoapelat, F^.AS trece ca adresa în dreapta pentru părintele nodului care se şterge fizic.

Întrebarea la care trebuie să răspundem în continuare este următoarea: de ce, dacă se şterge în acest mod un nod, arborele rămîne în căutare? Ştergerea unui nod se face în mod distinct pentru fiecare din cele 4 cazuri arătate. Datorită simplităţii prelucrării, primele 3 cazuri nu necesită comentarii. În cazul 4 se identifică nodul cel mai din dreapta din arborele stâng (care este cu cheia cea mai mare din aceste subarbore). Cheia acestuia trece în locul cheii nodului care se şterge. Aceasta este mai mică decât cheia iniţială (pentru că se găseşte în subarborele stâng), este în acelaşi timp cea mai mare cheie din subarborele stâng care este cea mai mică decât cheia care se şterge. Iată motivul pentru care aceasta trece în locul cheii şterge logic.

program c;

type ref=^inr;

inr=record

nr:integer;

as, ad:ref

end;

var v, man:ref;

k:integer;

opt:char;

procedure c_i (var c:ref; k:integer;);

begin

if c< >nil

then

if c^.nr=k

then

writeln (‘nr deja inserat’)

else

if c^.nr
then

c_i(c^.ad,k)

else

c_i(c^.as,k)

else

begin

new (c);

c^.as:=nil;

c^.ad:=nil;

c^.nr:=k

end;

end.

procedure svd (c:ref);

begin

if c< >nil then

begin

svd (c^.as);

writeln (c^.nr);

svd( c^.ad)

end;

end;

procedure cmmd (var c,f:ref);

begin

if f^.ad< >nil

then

cmmd (c,f^.ad)

else

begin

c^.nr:=f^.nr;

man:=f;

f:=f^.as;

dispose (man);

end;

end;

procedure sterg;

var f:ref;

begin

if c< >nil

then

if c^.nr=k

then

begin

if (c^.as=nil) and (c^.ad=nil)

then

begin

dispose (c);

c:=nil

end

else

if c^.as=nil

then

begin

f:=c^.ad;

dispose (c);

c:=f;

end

else

if c^.ad=nil

then

begin

f:=c^.as;

dispose (c);

c:=f;

end

else

cmmd (c, c^.as)

end

else

if c^.nr
then

sterg (c^.ad, k)

else

sterg (c^.as, k)

else

writeln (‘numar absent – tentativa esuata ‘)

end;

begin

v:=nil;

repeat

write (‘optiunea’);

readln (opt);

case opt of

’i’:    begin

write (‘k=’); readln (k);

c_i (v, k)

’l’:   svd (v);

’s’:   begin

write (‘se va sterge numarul ‘); readln (k);

sterg (v, k)

end;

end {case}

until   opt=’t’

end.

Teoria regăsirii informaţiei este deosebit de importantă pentru viaţa practică. Reţinem faptul că se pot crea arbori de căutare (echilibraţi) în care toate nodurile terminale se găsesc numai pe două niveluri consecutive. Aceasta conduce la o căutare rapidă (puţine operaţii).

8.2.7   Arbori oarecare

Vom defini arbori oarecare după D.E.   KNUTH. Se numeşte arbore oarecare un set finit T de unul sau mai multe noduri astfel încât:

există un nod cu destinaţie specială numit tulpina arborelui;

celelalte noduri sunt repartizate în m≥0 seturi disjunctive T1,T2, …, Tm unde fiecare din aceste seturi la rândul său este un arbore.

Am folosit această definiţie recursivă întrucît ne este de mare folos în scrierea programului care creează un arbore oarecare.

În programul care urmează construim un arbore oarecare în care fiecărui nod i se subordonează cel mult trei subarbori.

Pentru un nod se completează informaţia utilă (un număr întreg) precum şi un vector de adrese ale subarborilor subordonaţi nodului respectiv. Am utilizat tehnica DIVIDE ET IMPERA atât la creare cât şi la parcurgere.

Fie arborele oarecare din figura de mai jos:

Pentru a crea acest arbore vom introduce informaţiile în ordinea următoare:

1 2 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0.

Vom prezenta două dintre cele mai uzuale metode de parcurgere a arborilor oarecare:

1) Parcurgerea în adâncime (realizată de procedura padinc), în care se utilizează întâi tulpina, apoi subarborii de la stânga la dreapta (pentru arboreledin figura de mai sus avem: 1 2 3 4 5 6);

program arbg;

type ref=^inr;

vectad=array [1..3] of ref;

inr=record

nr:integer;

a:vectad

end;

var c:ref;

function arb:ref;

var c:ref;

n, i:integer;

begin

write (‘n=’); readln (n);

if n< >0

then

begin

new (c);

arb:=c;

arb^.nr:=n;

for i:=1 to 3 do arb ^.a[i]:=arb

end

else arb:=nil

end;

procedure padinc (c:ref);

var i:integer;

begin

if c< >nil then

begin

writeln (c^.nr);

for i:=1 to 3 do padinc (c^.a[i])

end

end;

begin

c:=arb;

padinc (c)

end.

2)    Parcurgerea în lăţime.

În acest caz, fiecare element al listei liniare care constituie coada va fi o înregistrare care cuprinde în general două câmpuri: adresa înapoi şi informaţia utilă. Dacă variabilele de tip referinţă b şi v vor reţine adresa utimului element introdus în coadă şi adresa elementului care poate fi scos din coadă.

Lucrul cu coada se poate face utilizînd trei proceduri:

1)    crearea cozii;

2)    adăugarea la coadă;

3)    scoaterea (prelucrarea) din coadă.

1)                Crearea cozii

Această operaţie este realizată de procedura ccoada. Crearea cozii constă în:

alocarea spaţiului pentru o înregistrare;

completarea informaţiei utile;

completarea informaţiei îapoi prin NIL.

2)                Adăugarea la coadă

Operaţia de adăugare la coadă este realizată de procedura adcoada. Parametrii ei sunt: t (informaţia utilă) şi b (adresa ultimului element introdus în coadă). Pentru aceasta se realizează următoarele operaţii:

alocarea spaţiului pentru noua înregistrare;

completarea informaţiei utile;

completarea câmpului de adresă înapoi a înregistrării de la b cu adresa noii înregistrări;

b va lua valoarea adresei noii înregistrări.

3)                Scoaterea din coadă

Această operaţie este realizată de procedura scoada. În acest sens se realizează operaţiile:

se reţine adresa elementului care urmează a fi scos din coadă;

se şterge înregistrarea acestui element;

v va lua valoarea adresei înregistrării plasate înaintea celei şterse.

O aplicaţie foarte importantă a structurii de coadă este parcurgerea în lăţime a arborilor oarecare.

Pentru arborele din figura de mai sus, ordinea de parcurgere a vârfurilor este următoarea:

1 2 5 6 3 4.

În exemplul care urmează, această parcurgere este realizată de procedura tipari. Ideea de lucru este următoarea:

se porneşte cu o coadă care conţine numai rădăcinile arborelui;

pentru fiecare element din vârful cozii procedăm astfel:

îl listăm;

îi încărcăm toţi succesorii în coadă;

algoritmul se încheie când coada este vidă.

Recomandăm cititorului analizarea cu atenţie a acestei proceduri.

program arbg;

type ref=^inr;

vectad=array [1..3]of ref;

inr=record

nr:integer;

a:vectad

end;

refl=^inr1;

inr1=record

inreg:inr;

inapoi:ref1

end;

var c:ref;

b, v:ref1;

function arb:ref;

var c:ref;

n,i:integer;

begin

write (‘n=’);

readln (n);

if n< >0

then

begin

new (c);

arb:=c;

arb^.nr:=n;

for i:=1 to 3 do arb^.a[i]:=arb

end

else arb:=nil

end;

procedure ccoada;

var d:ref1;

i:integer;

begin

new (d);

d^.inreg:=c^;

d^.inapoi:=nil;

b:=d;

v:=d

end;

procedure adcoada (t:inr; var b:ref1);

var d:ref1;

begin

new (d);

d^.inapoi:=nil;

d^.inreg:=t;

b^.inapoi:=d;

b:=d

end;

procedure scoada (var v:ref1);

var d:ref1;

begin

d:=v;

dispose (v);

v:=d^.inapoi

end;

procedure tipari (var b, v:ref1);

var d:ref;

t:inr;

i:integer;

begin

while v< >nil do

begin

writeln (v^.inreg.nr);

for i:=1 to 3 do begin

d:=v^.inreg.a[i];

if d< >nil

then

begin

t:=d^;

adcoada (t,b)

end

end;

scoada (v)

end

end;

begin

c:=arb;

ccoada;

tipari (b, v)

end.

Aplicaţie. Partiţia determinată de o relaţie de echivalenţă.

Un arbore oarecare poate fi memorat utilizînd o legătură de tip tată. Pentru aceasta este necesar un singur vector v, în care, pentru fiecare nod i, v(i) are semnificaţia de tatăl lui i. Avem v(i)=0 dacănodul lui i este vârf.

Observaţii:

- această formă de memorare este extrem de economică din punct de vedere al memoriei folosite (un nod poate avea mai multe noduri subordonate, dar numai un nod tată, deci avem o singură informaţie de adresă).

-parcurgerea arborilor reprezintanţi astfel de greoaie, fiind consumat mult timp.

Din matematică este cunoscută relaţia de echivalenţă. Aici o vom reaminti. O relaţie de echivalenţă ‘≈’ este o relaţie între elementele unei mulţimi, care satisface următoarele trei proprietăţi:

1)    x≈x (reflexivitate);

2)    dacă x≈y avem şi y≈x (simetrie);

3)    dacă x≈y şi y≈z, atunci x≈z (tranzitivitate).

Pentru că formează o submulţime aparte a mulţimii considerate, toate elementele sunt echivalente între ele. Cum fiecare element este cel puţin echivalent cu el însuşi, înseamnă că o relaţie de echivalenţă determină pe mulţimea considerată o partiţie.

Se consideră mulţimea primilor n numere naturale {1, 2, …, n}. Se dau un număr neprecizat de perechi echivalente de forma x≈y şi se cere partiţia determinată de această relaţie de echivalenţă.

Exemplu:

Fie n=4 şi perechile 1≈3, 1≈4, 3≈4.

În acest caz relaţia 3≈4 ar putea fi dedusă dinprimele două relaţii:anume din 1≈4 rezultă 4≈1 (simetrie), iar din 4≈1 şi 1≈3 rezultă 4≈3 (tranzitivitate), deci 3≈4 (simetrie). Partiţia determinată de această relaţie de echivalenţă este {1,3,4}, {2}.

Pentru rezolvare, considerăm o pădure cu arbori oarecare, cu nodurile elemente ale mulţimii considerate, reprezintaţi într-un vector cu n, componente, utilizând legătura de tip ‘tată’.

Iniţial, fiecare element constituie un arbore aparte, deci componentele vectorului v au valoarea 0.

Aplicăm soluţia următoare: toate elementele echivalente între ele (care vor alcătui o submulţime aparte a partiţiei) formează un arbore oarecare. Deci la citirea unei perechi j≈k se pune v(j) =k (adică tatăl lui j este k). Există posibilitatea ca j să fie subordonat unui alt părinte (v(j)≠0). În această situaţie j va lua valoarea lui v(j); raţionamentul continuă pînă când v(j) va fi 0 (se ajunge la tulpina arborelui construit pentru această submulţime). În acest moment v(j) va lua valoarea lui k, ceea ce înseamnă că întreg arborele se subordonează lui k. preluăm un exemplu al lui D.E. KNUTH.

Fie n=9 şi perechile citite: 1≈5, 6≈8, 7≈2, 9≈8, 3≈7, 4≈2, 9≈3.

Iniţial vectorul v va arăta astfel:

indici      1 2 3 4 5 6 7 8 9

v            0 0 0 0 0 0   0 0 0

arbori      1 2 3 4 5 6 7 8 9

indici      1 2 3 4 5 6 7 8 9

v             5 0 0 0 0 0 0 0 0            am citit 1=5

111

arbori      2   3   4   5 6 7 8 9

indici      1 2 3 4 5 6 7 8 9

v             5 0 0 0 0 8 0 0 0             am citit 6=8

arbori      2   3    4 5   7   8   9

1        6

6

indici      1 2 3 4 5 6 7 8 9

v             5 0 0 0 0 8 2 0 0            am citit 9=8

arbori        2 3 4      5 7   8

indici      1 2 3 4 5 6 7 8 9

v              5 0 7 2 0 8 2 0 8         am citit 3=7

arbori             2   4 5       8

3

1

7

indici      1 2 3 4 5 6 7 8 9

v             5 0 7 2   0 8 2 0 8       am citit 4=2

arbori            2         5      8

4

6

9

indici      1 2 3 4 5 6 7 8 9

5

2

v              5 0 7 2 0 8 2 3 8        am citit 8=3arbori

Se obţine partiţia {2,7,4,3,8,6,9} şi {5,1}.

Observaţie:

- Algoritmul nu înregistrează relaţii de forma j≈j sau, dacă a înregistrat j≈k, nu înregistrează k≈j. Pentru listare utilizăm procedura tipar. Precizăm faptul că, în acest algoritm nu sunt permise ca intrări informaţii redundante.

Exemplu:(1,2), (2,3), (3,1). Modificarea algoritmuui în acest sens este propusă ca exerciţiu.

program rechiv;

type vector=array [1..100] of integer;

var v:vector;

n, j, k:integer;

procedure adaug (var j, k:integer; var v:vector);

begin

while v[j]< >0 do j:=v[j];

if (j< >k) and (v[k]< >j) then v[j]:=k

end;

procedure tipar (j:integer);

var i:integer;

begin

for i:=1 to n do if v[i]=j

then

begin

if j=0 then writeln (‘——-clasa——-‘);

writeln (i);

tipar (i);

end

end;

begin

write (‘n=’); readln (n);

for j:=1 to n do v[j]:=0;

while j< >0 do

begin

write (‘j k’);

readln   (j, k);

if j< >0 then adaug (j, k, v)

end;

tipar (0)

end.

Probleme propuse

1)    Se citesc n numere naturale, distincte. Să se sorteze crescător, utilizînd lista liniară simplu înlănţuită, după următorul algoritm

iniţial lista va conţine numai primul număr;

dacă al doilea este mai mare decît primul, se va pune în coada listei, altfel va fi primul element din listă;

orice număr se aşează în listă înaintea celui mai mic număr care este mai mare decît el (dacă există un astfel de număr), sau la sfîrşitul listei, în caz contrar.

În final, se listează conţinutul listei liniare simplu înlănţuită. (sortare prin inserţie).

2)    Să se rezolve una din problemele propuse la capitolul 1 utilizînd stiva implementată dinamic.

3)    Să se creeze un obiect numit LLSI – lista liniară simplu înlănţuită – care conţine numere naturale. Acesta va cuprinde metode pentru adăugarea la sfîrşitul listei, ştergerea unui element ş.a.m.d. (în general toate operaţiile care se fac cu liste liniar simplu înlănţuite).

4)    Utilizînd obiectul creat la problema anterioară să se construiască un descendent al acestuia, numit NUMĂR_MARE, în care fiecare element al listei reţine o cifră între 0 şi 9 (în ansamblu o astfel de listă va reţine un număr cu mai multe cifre). Obiectul va fi înzestrat cu metode pentru citarea şi tipărirea numărului.

5)    Să se scrie o procedură care poate aduna două ’’numere mari’’.

6)    Să se scrie o procedură care înmulţeşte două ’’numere mari’.

7)    Pentru realizarea unui curs în care se explică conţinutul a n noţiuni, se citesc p perechi de cuvinte de forma (ni, nj). Fiecare cpereche citită are semnificaţia următoare: noţiunea i foloseşte în definirea noţiunii j. Se cere să se precizeze ordinea de prezentare a noţiunilor în curs.

8)    În jurul arbitrului sunt aşezaţi în cerc N jucători, numerotaţi în sens orar. Arbitrul, începînd de la jucătorul K, numără pînă la M. persoana la care sa oprit numărătoarea este eliminată din cerc. Arbitrul se poziţionează pe următoarea persoană şi repetă procedeul pînă cînd în cerc rămîne un singur jucător (L).

Să se scrie un program care:

Citind M, N şi K, să-l determuine pe L;

Citind M, N şi L, să-l determuine pe K.

9)    Să se sorteze n numere naturale cu ajutorul arborilor de căutare.

10)               Evidenţa produselor aflate în stocul unui magazin se ţine pe baza unui arbore de căutare. Pentru fiecare produs se reţine:

denumirea;

preţul;

cantitatea existentă (buc.).

În fiecare seară arborele estev actualizat prin comenzi de forma:

i – se introduc produsele primite de la depozit (Atenţie! Un astfel de produs poate să mai existe în stoc);

s – se şterg produsele vândute în ziua respectivă;

De asemenea, programul acceptă şi comenzile:

v – se tipăreşte valoarea tuturor produselor aflate în stoc;

l – se tipăreşte o listă completă a produselor aflate în stoc, în ordine alfabetică. Pentru fiecare produs se va tipări şi numărul de bucăţi.

11)           Problema jocurilor între doi parteneri, în care unul din jucători este calculatorul. Pentru a putea juca, calculatorul îşi construieşte un arbore corespunzător situaţiilor care pot apărea.

Pentru a exemplifica vom considera un joc simplu, numit ’GRUNDY’. Se consideră o stivă de n monede. Unul din cei doi parteneri o împarte în două părţi inegale. Celălalt partener împarte una din cele două stive de monede rămase în două părţi inegale ş.a.m.d.. Pierde acel jucător care nu mai poate face o astfel de împărţire.

Vom considera cazul n=5. În această situaţie calculatorul îşi construieşte arborele din figura de mai jos:

O primă problemă care se pune este dacă într-o anumită situaţie, presupunînd că trebuie să mute calculatorul, acesta dispune sau nu de strategie sigură de cîştig. Această problemă se poate rezolva utilizînd algoritmul MINI-MAX. Aplicarea acestui algoritm presupune următoarele:

analiza nodurilor terminale ale arborelui, unde pot apărea două situaţii:

trebuie să mute calculatorul, caz în care nodul se etichetează cu 0;

trebuie să mute partenerul uman, caz în care nodul se etichetează cu 1;

analiza nodurilor neterminale ale arborelui, unde apar din nou două situaţii:

mută calculatorul, situaţie în care nodul se etichetează cu maximul dintre etichetele nodurilor subordonate acestuia;

mută partenerul uman, situaţie în care nodul se etichetează cu minimul dintre etichetele nodurilor subordonate acestuia.

Acest mod de etichetare îşi găseşte explicaţia în faptul că, la mutarea efectuată de calculator, acesta va alege o mutare convenabilă (se va duce într-un nod etichetat cu 1), iar la mutarea efectuată de partenerul uman se presupune că acesta va alege o mutare convenabilă lui (va face o mutare care îl va duce într-un nod etichetat 0).

Scrieţi un program cu ajutorul căruia calculatorul va juca Grundy cu dumneavoastră.

Paralab. Описание параллельных методов решения сложных вычислительных задач

admin — Mon, 31 Jan 2011 07:55:01 +0000

1.1. Сортировка данных

Общая схема параллельных вычислений при сортировке данных (см. раздел 3 пособия) состоит в разделении исходного упорядочиваемого набора на блоки и их распределения между процессорами, в ходе сортировки блоки пересылаются между процессорами и содержащиеся в них данные сравниваются между собой для упорядочения. Результирующий (отсортированный) набор, как правило, также разделен между процессорами; при этом для систематизации такого разделения для процессоров вводится та или иная система последовательной нумерации и обычно требуется, чтобы при завершении сортировки значения, располагаемые на процессорах с меньшими номерами, не превышали значений процессоров с большими номерами.

В системе ПараЛаб в качестве методов упорядочения данных представлены пузырьковая сортировка, сортировка Шелла, быстрая сортировка.

1.1.1. Алгоритм пузырьковой сортировки

Напомним кратко общую схему данного метода упорядочения данных [1]. Алгоритм основан на применении базовой операции “сравнить и переставить” (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки:

// операция “сравнить и переставить”

if ( a[i] > a[j] ) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

На первой итерации алгоритма осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому набору данных в последнем (верхнем) элементе оказывается максимальное значение (“всплывание пузырька”); далее для продолжения сортировки этот уже упорядоченный элемент не рассматривается и действия алгоритма повторяются:

// пузырьковая сортировка

for ( i=1; i
for ( j=0; j
<сравнить и переставить элементы (a[j],a[j+1])>

}

Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания: сравнение пар соседних элементов происходит строго последовательно. Для организации параллельных вычислений обычно используется модификация алгоритма пузырьковой сортировки – метод чет-нечетной перестановки [23]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами, т.е. на всех нечетных итерациях сравниваются пары:

(a₁, a₂), (a₃, a₄),…, (a_n-1, a_n) (при четном n),

на четных итерациях обрабатываются элементы

(a₂, a₃), (a₄, a₅),…, (a_n-2, a_n-1) (при нечетном n).

После n-кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным.

Параллельное обобщение этого алгоритма не вызывает затруднений, так как сравнение элементов в парах происходит независимо и может выполняться одновременно. Сначала рассмотрим схему вычислений, когда на каждый процессор приходится один элемент исходного массива. Предположим, что процессоры соединены в кольцо и элементы a_iрасположены на процессорах p_i(i=1, 2,…, n). Тогда сравнение пары значений a_i и a_i₊₁1≤ i i и P_i+₁соответственно, можно организовать следующим образом:

- выполнить взаимообмен имеющихся на процессорах P_i и P_i+₁значений (с сохранением на этих процессорах исходных элементов);

- сравнить на каждом процессоре P_i и P_i+₁получившиеся одинаковые пары значений ai и a_i+₁; результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т.е P_i+₁) запоминает для дальней обработки большее значение пары

a_i =min(a_i , a_i+₁), a_i+₁=max(a_i , a_i+₁).

Рассмотренная параллельная схема может быть надлежащим образом адаптирована и для случая pi и P_i+1для совместного упорядочения содержимого блоков A_i и A_i+1и может быть осуществлено следующим образом:

- выполнить взаимообмен блоков между процессорами P_i и P_i+1;

- объединить блоки A_i и A_i+1на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре P_i, а другую часть (с большими значениями соответственно) – на процессоре P_i+1.

Следует отметить, что сформированные в результате такой процедуры блоки на процессорах P_i и P_i+1 совпадают по размеру с исходными блоками A_i и A_i+1и все значения, расположенные на процессоре P_i, являются меньшими значений на процессоре P_i+1.

Рассмотренная процедура обычно именуется в литературе как операция “сравнить и разделить” (compare-split). Для пояснения такого параллельного способа сортировки на рис. 1 приведен пример упорядочения данных при n=8, p=4 (т.е. блок значений на каждом процессоре содержит n/p =2 элементов). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняется операция “сравнить и разделить”; взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

Вычислительная трудоемкость алгоритма определяется выражением:

Tp =6 (n/p)² +2n

Первая часть выражения определяет сложность начальной сортировки блоков с использованием алгоритма пузырьковой сортировки. Вторая часть отражает суммарную сложность всех итераций алгоритма чет-нечетной перестановки блоков (для слияния двух упорядоченных блоков размера n/p необходимо 2(n/p) операций).

Download Lab_3

Paralab. Постановка вычислительной задачи и выбор параллельного метода решения

admin — Mon, 31 Jan 2011 07:37:32 +0000

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

Общая схема организации таких вычислений может быть представлена следующим образом:

разделение процесса вычислений на части, которые могут быть выполнены одновременно;

распределение вычислений по процессорам;

обеспечение взаимодействия параллельно выполняемых вычислений.

Возможные способы получения методов параллельных вычислений:

разработка новых параллельных алгоритмов;

распараллеливание последовательных алгоритмов.

Условия эффективности параллельных алгоритмов:

равномерная загрузка процессоров (отсутствие простоев);

низкая интенсивность взаимодействия процессоров (независимость).

В системе ПараЛаб реализованы широко применяемые параллельные алгоритмы для решения ряда сложных вычислительных задач из разных областей научно-технических приложений: алгоритмы сортировки данных, матричного умножения и обработки графов.

Выбор задачи.

Для выбора задачи из числа реализованных в системе выберите пункт меню Задача и выделите левой клавишей мыши одну из строк: Сортировка, Матричное умножение, Обработка графов. Выбранная задача станет текущей в активном окне.

Download Lab_2

ПАРАЛАБ ПРОГРАММНАЯ СИСТЕМА ДЛЯ ИЗУЧЕНИЯ И ИССЛЕДОВАНИЯ МЕТОДОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙПАРАЛАБ ПРОГРАММНАЯ СИСТЕМА ДЛЯ ИЗУЧЕНИЯ И ИССЛЕДОВАНИЯ МЕТОДОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

admin — Mon, 31 Jan 2011 07:34:55 +0000

Программная система Параллельная Лаборатория (сокращенное наименование ПараЛаб) обеспечивает возможность проведения вычислительных экспериментов с целью изучения и исследования параллельных алгоритмов решения сложных вычислительных задач. Система может быть использована для организации лабораторного практикума по различным учебным курсам в области параллельного программирования, в рамках которого обеспечивается возможность

• моделирования многопроцессорных вычислительных систем с различной топологией сети передачи данных;

• получения визуального представления о вычислительных процессах и операциях передачи данных, происходящих при параллельном решении разных вычислительных задач;

• построения оценок эффективности изучаемых методов параллельных вычислений.

Проведение такого практикума может быть организовано на “обычных” однопроцессорных компьютерах, работающих под управлением операционных систем MS Windows 2000 или MS Windows XP (режим многозадачной имитации параллельных вычислений). Кроме режима имитации, в системе ПараЛаб обеспечивается удаленный доступ к имеющейся многопроцессорной вычислительной системе для выполнения экспериментов в режиме “настоящих” параллельных вычислений для сопоставления результатов имитации и реальных расчетов.

В целом система ПараЛаб представляет собой интегрированную среду для изучения и исследования параллельных алгоритмов решения сложных вычислительных задач. Широкий набор имеющихся средств визуализации процесса выполнения эксперимента и анализа полученных результатов позволяет изучить эффективность использования тех или иных алгоритмов на разных вычислительных системах, сделать выводы о масштабируемости алгоритмов и определить возможное ускорение процесса параллельных вычислений.

Реализуемые системой ПараЛаб процессы изучения и исследований ориентированы на активное освоение основных теоретических положений и способствуют формированию у пользователей своих собственных представлений о моделях и методах параллельных вычислений путем наблюдения, сравнения и сопоставления широкого набора различных визуальных графических форм, демонстрируемых в ходе выполнения вычислительного эксперимента.

Возможности системы. ПараЛаб – программный комплекс, который позволяет проводить как реальные параллельные вычисления на многопроцессорной вычислительной системе, так и имитировать такие эксперименты на одном последовательном компьютере с визуализацией процесса решения сложной вычислительной задачи.

При проведении имитационных экспериментов ПараЛаб предоставляет возможность для пользователя:

• определить топологию параллельной вычислительной системы для проведения экспериментов, задать число процессоров в этой топологии, установить производительность процессоров, выбрать характеристики коммуникационной среды и способ коммуникации;

• осуществить постановку вычислительной задачи, для которой в составе системы ПараЛаб имеются реализованные параллельные алгоритмы решения, выполнить задание параметров задачи;

• выбрать параллельный метод для решения выбранной задачи;

• установить параметры визуализации для выбора желаемого темпа демонстрации, способа отображения пересылаемых между процессорами данных, степени детальности визуализации выполняемых параллельных вычислений;

• выполнить эксперимент для параллельного решения выбранной задачи; при этом в системе ПараЛаб может быть сформировано несколько различных заданий для проведения экспериментов с отличающимися типами многопроцессорных систем, задач или методов параллельных вычислений, для которых выполнение эксперимента может происходить одновременно (в режиме разделения времени); одновременное выполнение эксперимента для нескольких заданий позволяет наглядно сравнивать динамику решения задачи различными методами, на разных топологиях, с разными параметрами исходной задачи. При выполнении серии экспериментов, требующих длительных вычислений, в системе имеется возможность их проведения в автоматическом режиме с запоминанием результатов в журнале вычислений [1-3].

Для реальных экспериментов на многопроцессорных вычислительных системах зависимости строятся по набору результатов проведенных вычислительных экспериментов. Любой из проведенных ранее экспериментов может быть восстановлен для повторного проведения. Кроме того, обеспечена возможность ведения журнала экспериментов с записью туда постановки задачи, параметров вычислительной системы и полученных результатов.

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

Downlaod Lab_1

Blog despre resurse educaţionale din IT » programming

Zend Framework Reference 1.11 Русская версия

Zend_Acl

Введение

Ресурсы

Роли

Structuri de date. Stive. Cozi. (Pascal)

Paralab. Описание параллельных методов решения сложных вычислительных задач

1.1. Сортировка данных

1.1.1. Алгоритм пузырьковой сортировки

Paralab. Постановка вычислительной задачи и выбор параллельного метода решения

Выбор задачи.