Лекция 29. Динамические структуры данных: однонаправленные и двунаправленные списки

Упражнения

Вопросы

Набор для практики

1. Почему в программах размер памяти под статические переменные должен быть определен на этапе компиляции?

2. За счет каких ресурсов выделяется память под динамические структуры?

3. Почему динамические структуры не требуют собственного описания в программе?

4. Как располагаются в памяти динамические величины?

5. Как осуществляется доступ к динамическим структурам из программного кода?

6. Как связываются между собой элементы динамической структуры?

7. В чем основное отличие смежного и связного представления данных?

8. Какого типа может быть поле данных в динамической структуре?

9. Почему для обращения к динамической структуре достаточно хранить в памяти адрес ее первого элемента?

10. За счет чего работа с динамическими данными замедляет выполнение программы?

1. Разработайте динамическую структуру для решения задачи. Последовательность чисел Фибоначчи задается по закономерности: f ₁ = 1, f ₂ = 1, …, f_n = f_{n -1} + f_{n -2}. Распечатайте n чисел Фибоначчи в следующем порядке: сначала все четные, затем все начетные элементы.

2. Разработайте динамическую структуру для решения задачи. Даны целые числа p и q. Получить все делители числа q, взаимно простые с числом p.

3. Разработайте динамическую структуру для решения задачи. Дана последовательность из n целых чисел. Получите количество чисел последовательности, которые встречаются в ней ровно один раз. Распечатайте найденные числа.

4. Разработайте динамическую структуру для решения задачи. На шахматной доске каждая клетка описывается двумя координатами: номером строки и номером столбца. Ферзь ставиться на одну из клеток. Найдите количество и координаты всех клеток, которые «бьет» ферзь.

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384с.

2. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004. – 600 с.

3. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

4. Топп Уильям, Форд Уильям. Структуры данных в С++. Пер. с англ. - М.: БИНОМ, 2000. – 816 с.

5. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. - М.: Финансы и статистика, 2004. – 464 с.

Краткая аннотация лекции.

В лекции рассматриваются определения и виды списков, структура, способы объявления однонаправленных и двунаправленных списков, основные операции над элементами списков, приводятся примеры решения задач с использованием однонаправленных и двунаправленных списков.

Цель лекции: изучить понятия, классификацию и объявления списков, особенности доступа к данным и работу с памятью при использовании однонаправленных и двунаправленных списков, научиться решать задачи с использованием списков на языке C++.

Дата добавления: 2014-01-04