Динамические структуры данных 5

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Уральский федеральный университет имени первого Президента России Б.Н. Ельцина

Кафедра вычислительных методов и уравнений математической физики

Оценка работы

Преподаватель

Динамические структуры данных

Подпись Дата Ф.И.О.

Преподаватель _ Трясцина Т. С.

Студент _ Запалацкий В. С.

Группа Р-190901

Екатеринбург 2010

СОДЕРЖАНИЕ

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

1. ПОСТАНОВКА ЗАДАЧИ………………………………….……………………………….4

2. ТЕРЕТИЧЕСКАЯ ЧАСТЬ………………………………………………………………….5

3. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ………………………………………………………..7

4. ИНСТРУКЦИЯ ПРОГРАММИСТА………………………………………….……………8

5. МЕТОДИКА И РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ……………………………………..9

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

ПРИЛОЖЕНИЕ. ТЕКСТ ПРОГРАММЫ…………………………………………………..13

БИБЛИОГРАФИЧЕСКИЙ СПИСОК……………………………………………………….20

введение

Данная программа была разработана для изучения динамических структур данных таких, как стек, очередь и список. Применение их для решения практических задач. Создание графического интерфейса.

На сегодняшний день существует много средств для визуального проектирования программ, наиболее известные из них: Visual Studio (последняя версия 10.0) и Borland C++ Builder. В основе этих сред программирования лежит технология визуального проектирования и событийного программирования, суть которой заключается в том, что среда разработки берет на себя большую часть работы по генерации кода программы, остав­ляя автору работу по конструированию диалоговых окон и написа­нию функций обработки событий, благодаря этому скорость разработки программ возрастает.

1. постановка задачи

Текст помощи для некоторой программы организован в виде линейного списка.Каждая компонента текста помощи содержит термин(слово) и текст,содержащий пояснения к этому термину.Количество строк текста , относящихся к одному термину состовляет от одной до пяти.Написать программу ,которая обеспечивает : Начальное формирование текста помощи; вывод пояснительного текста для заданного термина.Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе
2. теоретическая часть

Динамические структуры данных

Часто в серьезных программах надо использовать данные, размер и структура которых должны меняться в процессе работы. Динамические массивы здесь не выручают, поскольку заранее нельзя сказать, сколько памяти надо выделить – это выясняется только в процессе рабо- ты. Например, надо проанализировать текст и определить, какие слова и в каком количество в нем встречаются, причем эти слова нужно расставить по алфавиту.

В таких случаях применяют данные особои? структуры, которые представляют собои? отдельные элементы, связанные с помощью ссылок . Каждыи? элемент (узел ) состоит из двух областеи? памяти: поля данных и ссылок . Ссылки – это адреса других узлов этого же типа, с которыми дан- ныи? элемент логически связан. В языке Си для организации ссылок используются переменные- указатели. При добавлении нового узла в такую структуру выделяется новыи? блок памяти и (с помощью ссылок) устанавливаются связи этого элемента с уже существующими. Для обозна- чения конечного элемента в цепи используются нулевые ссылки (NULL ).

Всего существует 6 основных видов динамических структур данных :

1Стек

2Очередь

3Хэш таблица

4Список (односвязный, двусвязный, циклический)

5Дерево

6Граф

Список

Существует 3 вида списков :

1односвязный (линейный)

2двусвязный

3циклический

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

Двусвязный список.

Многие проблемы при работе с односвязным списком вызваны тем, что в них невозможно переи?ти к предыдущему элементу. Возникает естественная идея – хранить в памяти ссылку не только на следующии?, но и на предыдущии? элемент списка. Для доступа к списку используется не одна переменная-указатель, а две – ссылка на «голову» списка (Head ) и на «хвост» - последнии? элемент (Tail ).

Очередь

Очередь – это упорядоченныи? набор элементов, в котором добавление новых элементов до-

пустимо с одного конца (он называется начало очереди), а удаление существующих элементов – только с другого конца, которыи? называется концом очереди.

Хорошо знакомои? моделью является очередь в магазине. Очередь называют структурои? типа FIFO (First In – First Out) – первым пришел, первым ушел. На рисунке изображена очередь из 3-х элементов.

Стек

Стек – это упорядоченныи? набор элементов, в котором добавление новых и удаление существующих элементов допусти

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать