![]() |
|
сделать стартовой | добавить в избранное |
![]() |
Компьютеры, Программирование
Программное обеспечение
Динамические структуры данных |
МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ УКРАИНЫ Одесский национальный политехнический университет Институт компьютерных систем Кафедра &quo ;Компьютерные интеллектуальные системы и сети&quo ;Курсовая работа Динамические структуры данных2004 АннотацияЦелью данной работы служит разработка эффективных алгоритмов на динамических структурах данных. Главной особенностью динамических структур является возможность изменения их структуры и размера в процессе работы программы. Это существенно повышает гибкость программы, размер структуры ограничивается только размером памяти машины. Однако такая гибкость обходится несколько большими затратами памяти на хранение самой структуры и её обработку, поскольку дополнительную память требуют указатели. Алгоритмы работы с этими структурами очень сильно зависят от вида самой структуры. В данной работе представлены алгоритмы работы со стеком. Также здесь представлена инструкция пользователя по данной программе. СодержаниеАннотация 1. Теоретические сведения 1.1 Описание структуры данных &quo ;стек&quo ; 2. Разработка 2.1 Процедура добавления элемента 2.2 Процедура удаления элемента 2.3 Процедура очистки памяти 2.4 Распечатка содержимого 3. Инструкция пользователя 4. Код программы 5. Контрольный пример Заключение Перечень используемой литературы Приложения 1. Теоретические сведенияВ этом разделе мы ознакомимся с динамическими структурами данных и собственно стеком. Достоинства динамических структур данных Динамические структуры данных по определению характеризуются отсутствием физической смежности элементов структуры памяти непостоянством и непредсказуемостью размера (числа элементов4) структуры в процессе её обработки. В этом разделе рассмотрены особенности динамических структур, определяемые их первым характерным свойством. Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей: информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой-вектором, массивом, записью и т.п.; поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры. Когда связное представление данных используется для решения прикладной задачи, для конечного пользователя видимым делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком. Достоинства связного представления данных: в возможности обеспечения значительной изменчивости структур; размер структуры ограничивается только размером памяти машины; при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей.
Однако существуют и недостатки: работа с указателями требует, как правило, более высокой квалификации от программиста; на поля связок расходуется дополнительная память; доступ к элементам связной структуры может быть менее эффективным по времени. Применение динамических структур Последний недостаток является наиболее серьёзным и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента или информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск и требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, стеки, списки, деревья и т.д.). Задание курсового проекта По списку номер 2, тогда имеем следующее задание. Реализовать стек, содержащий 4-ре поля: Имя функции, возвращаемое значение, количество параметром и сами параметры. Реализовать для данного стека работу следующих операций: добавление элемента; удаление элемента; очистка памяти от стека; вывод на экран всех значений списка; проверка о переполнении стек; вывод сообщения на экран о переполнении стека. 1.1 Описание структуры данных &quo ;стек&quo ;Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Las -I , Firs -Ou ) - поступивший последним, обслуживается первым. Обычно над стеками выполняется три операции: начальное формирование стека (запись первой компоненты); добавление компоненты в стек; выборка компоненты (удаление). Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная. 2. РазработкаВ этом разделе будут последовательно рассмотрены процедуры (методы), работающие с данной структурой (стеком). Входные значения процедур вводятся с клавиатуры посредствам различных диалоговых окон с помощью программного продукта Builder C . Ниже приведена сама структура:s ruc S ack { char s rF ame ; // возвращаемое значение i umPar; // количество введених параметров char pParams; // указатель на парамаетры bool bFilled; // заполнен ли элемент S ack p ex ; // указатель на следующий элемент S ack () { p ex = ULL; // задаём начальные параметры стека, что он пуст umPar = 0; bFilled = false; } void Add (char s rF ame , char s rRValue , i umPar , char pParams ); void Dele e (); void Pri ( Memo memo); void Free (); };s rF ame - поле, хранящее имя функции; s rRValue - поле, хранящее возвращаемое значение; umParams - поле, хранящее количество параметров; pRarams - поле указателя, хранящего адресс значений параметров; Далее приведены описания процедур: void Add (char s rF ame , char s rRValue , i umPar , char pParams ); void Dele e (); void Pri ( Memo memo); void Free ().
2.1 Процедура добавления элементаНиже приведен код процедуры добавления элемента в стек: S ack emp; // создаём указатель emp типа S ack i um = 0; // количество элементов 0 i max um = 1000; // максимальное количество элементов равно 1000void S ack:: Add (char s rF ame , char s rRValue , i umPar , char pParams ) { if ( um == (max um-1)) MessageBox (&quo ;Almos Overload&quo ;, &quo ;War i g &quo ;, MB OK); // если элементов на единицу меньше максимального количества элементов, программа предупредит диалоговым окном if ( um == max um) // если элементов максимальное количество { MessageBox (&quo ;Overload&quo ;, &quo ;&quo ;, &quo ;Error&quo ;, MB OK); // диалоговое окно с ошибкой re ur ; // процедура добавления элемента останавливается } um ; // счетчик количества введенных элементов if (p ex ) // если есть ссылка на следующий элемент p ex -&g ;Add (s rF ame , s rRValue , umPar , pParams ); // добавляем элемент с адресом p ex else { if (! bFilled) // если элемент заполнен { s rcpy (s rF ame, s rF ame ); // копируем значения строк из одной переменной в другую s rcpy (s rRValue, s rRValue ); umPar = umPar ; pParams = ew char ; for (i i = 0; i &l ; umPar; i ) // повторяем цикл umPar раз { pParams ; // выделяем память для хранения одного параметра 6 байт из массива s r cpy (pParams , 6); // копируем значения из введённых, отсекая всё больше 6-ти байт } bFilled = rue; // поле считается заполненным } else { p ex = ew S ack; // выделяем память под новые элемент S ack p ex -&g ;Add (s rF ame , s rRValue , umPar , pParams ); // добавляем элемент } } }В этой функции реализована и проверка на переполнение стека. Проверка переполнения выполняется по количеству введенных элементов i max um = 1000; и счётчику текущего элемента um:if ( um == (max um-1)) MessageBox (&quo ;Almos Overload&quo ;, &quo ;War i g &quo ;, MB OK); // если элементов на единицу меньше максимального количества элементов, программа предупредит диалоговым окном if ( um == max um) // если элементов максимальное количество { MessageBox (&quo ;Overload&quo ;, &quo ;&quo ;, &quo ;Error&quo ;, MB OK); // диалоговое окно с ошибкой re ur ; // процедура добавления элемента останавливается } um ; // счетчик количества введенных элементовРеализация ввода параметров (по определенному введенному количеству) выполнена через массив указателей. Входные параметры поступают из методов С Builder через поля и кнопки исполнения. Выходного значения нету. 2.2 Процедура удаления элементаНиже приведен код удаления элемента:void S ack:: Dele e () { if (p ex ) // если есть следующий элемент if (p ex -&g ;p ex ) // если есть более 1-го элемента p ex -&g ;Dele e (); // запускаем рекурсивно метод Dele e () для следующего элемента else { dele e p ex ; // удаляем в памяти адрес указанный p ex p ex = ULL; // присваеваем значение указателя p ex равное нулю } }По определению стека - удалять можно только последний элемент, не разрушая стека. Входные параметры отсутствуют. Выходного значения нету. 2.3 Процедура очистки памятиПроцедура очистки памяти от всего стека, код:void S ack:: Free () { if ( emp) dele e emp; // если есть временная переменная emp, то очистить от неё память if (p ex ) // если есть хотя бы один элемент { emp = his; // emp присваивается текущее значение p ex -&g ;Free (); // запускаем метод Free () для следующего элемента } }Достаточно удалить первый элемент стека для разрушения стека, здесь удаляется весь стек с конца, т.е
Харриса), трансформационной грамматики, теории речевых актов, формальной логики в плане выполнения условий его правильной оформленности (когеренция и когезия) и следования дедуктивным правилам (теория речевых актов), т.е. анализ дискурса совпадал по существу со структуралистски ориентированными грамматикой текста, лингвистикой текста, семантикой дискурса в первоначальном европейском понимании (Вольфганг Дресслер, П.А.М. Сьюрен, Ольга Ивановна Москальская, Юрий Владимирович Попов и др.). Функционально-лингвистическое течение в анализе дискурса сложилось под влиянием коммуникативно-прагматических моделей языка и идей когнитивной науки. Оно обращает внимание на динамический характер дискурса как процесса конструирования говорящим / пишущим и процессов интерпретации слушающим / читающим (Дж. Браун и Дж. Юл, Т.А. ван Дейк). Здесь считается необходимым учёт при анализе прагматических факторов и контекста дискурса (референция, пресуппозиции, импликатуры, умозаключения), контекста ситуации, роли топика и темы, информационной структуры (данное -- новое), когезии и когеренции, знания мира (фреймы, скрипты, сценарии, схемы, ментальные модели)
1. Динамические структуры данных: очереди
2. Динамические структуры данных: стеки
3. Динамические структуры данных: стеки
4. Динамические структуры данных
5. Динамические структуры данных
9. Иерархические структуры данных в реляционных БД
10. Структуры данных и алгоритмы
11. Алгоритмы и структуры данных. Программирование в Cи
12. Структура данных программного комплекса "Q-дерево"
13. Структуры данных и алгоритмы
15. Структура и формирование исходных данных, необходимых для расчета параметров технологических схем
16. Неинерциальные полевые принципы формирования структуры материи. Закон динамической гравитации
18. Определение термина "состояние" в структуре динамического пространства сознания-тела
19. Структуры и алгоритмы обработки данных
20. Типы и элементы планировочной структуры города
21. Структура организации материи
25. Роль и значение машиностроительного комплекса в структуре народного хозяйства России
26. Дания
28. План статистического наблюдения и данные переписи населения
29. Безработица в России /данные на 1992г/
30. Государственный аппарат и его структура
31. Нормы права. Структура норм права
32. Структура государственных органов США по Конституции 1787 года
34. Международная организация труда- создание, структура, задачи и организация её работы
36. Структура, содержание и значение общей части Налогового кодекса России
37. Структура налоговых органов РФ права, обязанности и функции
42. Структура и функции государственного аппарата
43. Сравнительное описание слоговых структур английского и каракалпакского языков
44. Культура, её структура и функции
45. Структура и организация учебного процесса в средневековом университете (Болонья, Париж, Прага)
46. Судьба и творчество Даниила Хармса
47. Проблематика и структура пьесы Б. Шоу "Пигмалион"
48. Бальзак: структура и основные идеи "Человеческой комедии"
49. Сравнительное описание слоговых структур английского и каракалпакского языков
51. Методы компьютерной обработки статистических данных
52. Основные компоненты систем управления документооборотом. Фрейм: его структура и понятие
53. Интернет: административное устройство и структура глобальной сети
57. Системы и сети передачи данных
59. Динамическое распределение памяти
60. Информация, информатика, базы данных. Периферийные устройства
61. Динамические объекты /TurboPacal/
62. Сжатие данных
63. Анализ структур, характеристик и архитектур 32-разрядных микропроцессоров
64. Пример базы данных на Delphi 2.0
65. Структура и реализация макроязыков
66. Проектирование и разработка баз и банков данных
67. База данных для учета оплаты за междугородние разговоры
68. Реляционные Базы Данных. SQL - стандартный язык реляционных баз данных
69. Программа сложной структуры с использованием меню
73. Анализ пакетов обработки экспериментальных данных SABR и BOOTSTRAP
74. Разработка базы данных, отражающей учет успеваемости студентов
75. Разработка базы данных "Кадры"
76. Лекции по теории проектирования баз данных (БД)
78. Fox Pro - реляционная модель данных
79. Система управления базами данных ACCESS
80. База данных - Бактериологическая испытательная лаборатория Боханского района
81. Моделирование структуры книги
82. Разработка приложений на языке VBA в среде MS EXCEL по обработке данных для заданных объектов
83. Обработка данных о студентах
84. Инструкция по эксплуатации базы данных магазина «Телевизоры» средствами Access 2000
85. Системы обработки информации - язык баз данных SQL со средствами поддержания целостности
89. Работа в среде EXCEL. Средства управления базами данных в EXCEL
90. Структура сходящихся последовательностей
91. Применение алгоритма RSA для шифрования потоков данных
92. Структура аффинного пространства над телом
93. Исследование регрессии на основе численных данных
94. Общие данные о нервной системе
95. Структура арбитражных судов
96. Взяточничество и коррупция в деятельности преступных структур (сообществ)
98. Влияние экологических и медико-биологических требований на структуру исследований и разработок