- •Ф.Ф. Павлов языки программирования
- •Санкт-Петербург
- •230201 - Информационные системы и технологии
- •Тема 2 посвящена изучению жизненного цикла программы и основным этапам решения задач на эвм.
- •Тема 4 изучает типы пользовательских интерфейсов, классификацию диалогов и основные компоненты графических пользовательских интерфейсов.
- •Тема 8 посвящена структурам данных фиксированного размера (массивы), а также типам данных, определяемых пользователем (структуры, объединения, перечисления).
- •Тема 10 изучает динамические структуры данных: виды и способы реализации списков, динамическое выделение памяти.
- •Тема 12 затрагивает вопросы обработки файлов данных: понятия записи, файла данных и способы доступа, операции и средства обработки файлов, контроль операций обработки файлов.
- •Тема 14 вводит в технологию объектно-ориентированного программирования.
- •Раздел I Принципы программирования на языках высокого уровня
- •Тема 1. Эволюция языков программирования
- •1.1. Неструктурированное, «стихийное» программирование
- •1.2. Процедурное (модульное) программирование
- •1.3. Объектно-ориентированное программирование
- •1.4. Компонентные технологии программирования
- •Тема 2. Жизненный цикл программы и основные
- •2.1. Дружественность, жизненный цикл программы
- •2.2. Постановка задачи и спецификация программы
- •2.3. Проектирование и реализация программы
- •2.4. Способы записи алгоритма
- •2.5. Критерии качества программы
- •3.1. Классификация программных продуктов
- •3.3. Модели программирования в ms-dos и Windows
- •Тема 4. Диалоговые программы
- •4.1. Типы пользовательских интерфейсов
- •4.2. Классификация диалогов и их реализация
- •4.3. Основные компоненты графических
- •Тема 5. Программа на языке высокого уровня
- •5.1. Структура программы и функции
- •5.2. Стандартные типы данных и операции над ними
- •5.3. Адресные типы данных: указатели и ссылки
- •5.4. Стандартные библиотеки языка
- •5.5. Классы памяти
- •Раздел 2 Управляющие структуры и структуры данных
- •Тема 6. Представление управляющих структур
- •6.1. Структура следования
- •6.2. Структуры ветвления
- •6.3. Структуры повторения
- •Int kol, //счетчик введенных оценок
- •Int god; //число лет
- •Тема 7. Адресные типы данных
- •7.1. Указатели
- •7.2. Ссылки
- •Тема 8. Структуры данных фиксированного размера
- •8.1. Массивы
- •8.2. Типы данных, определяемые пользователем
- •Тема 9. Функции (процедуры)
- •9.1. Определение, прототип и вызов функции
- •9.2. Передача параметров
- •9.3. Программирование рекурсивных алгоритмов
- •Тема 10. Динамические структуры данных
- •10.1. Списки: основные виды и способы реализации
- •10.2. Динамическое выделение памяти
- •Раздел 3 Процедурное программирование
- •Тема 11. Ввод/вывод данных
- •11.1. Видеофункции библиотеки conio.H
- •11.2. Функции библиотеки потокового ввода/вывода
- •Тема 12. Обработка файлов данных
- •12.1. Записи и файлы данных
- •12.2. Операции и средства обработки файлов
- •12.3. Контроль операций обработки файлов
- •Тема 13 Технология процедурного программирования
- •13.1. Способы конструирования программ
- •13.2. Проектирование программы: методы декомпозиции и и модульного программирования
- •13.3. Реализация программы: методы структурного
- •Тема 14. Введение в технологию объектно-
- •14.1. Основные понятия объектно-ориентированного
- •14.2. Проектирование программы
- •14.3. Реализация программы
- •Утверждаю
- •Рабочая программа
- •Технология программирования
- •Санкт-Петербург
- •Тема 1. Технология программирования и этапы ее
- •Тема 2. Жизненный цикл программы и основные этапы
Тема 10. Динамические структуры данных
10.1. Списки: основные виды и способы реализации
Ранее были рассмотрены структуры данных фиксированного размера: массивы, структуры. Размер таких наборов данных зафиксирован при компиляции и не может быть изменен.
Динамические структуры данных – это наборы данных, размеры которых нарастают и сокращаются во время выполнения программы. Рассмотрим основные виды динамических структур данных: списков и способы реализации операций с данными.
Связные списки (linked lists) – наборы элементов данных, называемых узлами, связанные при помощи связующих указателей в линейную структуру данных, причем операции вставки элементов данных и их удаления осуществляются в любом месте списка. Каждый узел содержит адреса (связующие указатели) последующего и предыдущего указателя списка (прямые и обратные цепочки). Доступ к связному списку начинается через указатель на первый элемент списка, а затем через связующие указатели каждого списка.
Стеки (stacks) – частный случай связных списков, в которых операции вставки и удаления проводятся в конце стека (в его вершине), т.е. по принципу «первый пришел, последний ушел»; применяется в компиляторах и операционных системах. Пример использования стеков и описание алгоритмов операций с элементами списка представлен в § 7.1 при программировании класса «spisok» методом объектно-ориентированного программирования.
Очереди (queues) - частный случай связных списков, в которых операция вставки проводится в конце очереди (хвосте очереди), а операция удаления проводится в начале очереди (голове очереди), т.е. по принципу «первый пришел, первый ушел».
Бинарные деревья (binary trees) – нелинейные структуры данных, обеспечивающие высокоскоростной поиск и сортировку данных.
10.2. Динамическое выделение памяти
Создание и сопровождение динамических структур данных ведет к динамическому распределению памяти, т. е. к наращиванию и сокращению области памяти в процессе выполнения программы.
Для управления динамической памятью используются:
оператор new для резервирования памяти из heap (кучи);
оператор delete для освобождения памяти.
Синтаксис оператора new (три формы):
new <тип> или new (<тип>) //резервирование памяти под
//объект типа <тип>;
new <тип>(x) //резервирование памяти и инициализация
//значением x
new <тип>[<выражение>] //резервирование под массив
//типа <тип>.
Примеры оператора new:
int* p1=new int; //резервирование памяти под объект
//типа int
int* p2=new int(5); //резервир. и инициализация значением x
char* tabn=new char[20]; //резервир. под массив типа char
t* p=new t; //резервир. под переменную типа структура t:
//struct t {char tabn[10]; float oklad;}
Результат оператора new – указатель на выделенную память, либо 0, если произошла ошибка.
Синтаксис оператора delete имеет две формы:
delete p; //освобождение памяти, p – указатель из new
delete[] p; //освобождение памяти, занятой массивом
Примеры оператора delete:
delete p1; //освобождение памяти, на которую указывает p1
delete[] tabn; //освобождение массива, на который указывает tabn
Операторы new и delete особенно эффективны при работе с объектами классов в объектно-ориентированном программировании.
Сравним структуры данных фиксированного размера (массивы) и динамические структуры данных (списки) с точки зрения их использования при программировании. Списки эффективны по сравнению с массивами в тех случаях, когда число элементов данных в структуре данных заранее не известно и может изменяться во время выполнения программы. Конечно, можно и в этих случаях использовать массивы, объявив заранее массив под максимальное число элементов, но это приведет к избыточному расходу памяти. Таким образом, связные списки экономят память.
Сравнивая операцию сортировки, можно сказать, что списки имеют преимущество, так как имеют возможность вставки нового элемента прямо в соответствующую позицию списка. Также операции вставки и удаления в массиве будут более длительными, так как все элементы при этих операциях сдвигаются.
Но массивы имеют огромное преимущество, связанное с быстрым доступом к элементам массива, так как адрес индексированного элемента массива вычисляется мгновенно по отношению к началу массива. Это объясняется распределением памяти под массив, когда элементы массива размещаются в памяти непрерывно. И в этом недостаток списков, так как узлы списков физически не хранятся в памяти по соседству друг с другом.
Контрольные вопросы
Дайте определение динамических структур данных.
Какие существуют основные виды списков?
Охарактеризуйте динамический класс памяти.
Сравните структуры данных фиксированного типа (массивы) с динамическими структурами данных (списки).