Практикум для изучения дисциплины «Основы программирования»

64 
 
Иногда на основе списков строятся такие структуры данных, как стеки и 
очереди. 
Весьма  важным  при  ручной  реализации  динамических  структур  данных 
является  следующее  обстоятельство.  При  добавлении  элемента  в 
динамическую  структуру  данных  необходимо  выделить  необходимую 
память,  а  при  удалении —  освободить  ее.  При  этом  в  процессе  работы  с 
динамическими  типами  данных  в  языках  программирования  память 
выделяется  из  специального  пула,  называемого  кучей.  Если  в  языке 
программирования  отсутствует  механизм  автоматического  управления 
памятью при удалении — так называемая сборка мусора, ответственность 
за  очистку  памяти  возлагается  на  программиста,  который  должен 
проделать это явным образом. 
Сборщик  мусора  периодически  освобождает  память,  удаляя  объекты, 
которые уже не будут востребованы приложением. Изначально он имеется 
в таких языках, как Лисп и Java. Однако при выполнении программ на этих 
языках  наличие  автоматической  сборки  мусора  может  приводить  к 
непредсказуемым задержкам в заранее не известные моменты времени. В 
связи  с  этим  на  Си,  например,  управление  памятью  осуществляется 
вручную  с  использованием  библиотечных  функций.  Ниже  приводится 
возможный  вариант  программирования  динамического  массива  на  языке 
Си: 
#include  
#define N 10  
int main()  
{  
  
double* ptd; // объявляем указатель на массив 
 
  
/* запрос выделения памяти из «кучи» */ 
  ptd = (double*)malloc(N * sizeof(double));  
  
if(ptd != NULL)  /* если памяти нет, malloc возвращает NULL*/ 
  {  
    for(int i = 0;i   
} else printf("Не удалось выделить память.");  
   
  
free(ptd); /* Освобождение памяти */  
 
  return 0;  
} 
Контрольные вопросы 
1. 
Что такое список в языках программирования? 

65 
 
2. 
Каковы основные операции над списками? 
3. 
Является ли список рекурсивной структурой данных? Почему? 
4. 
В  чем  заключается  принцип  низкоуровневой  реализации  списков  в 
программах на языках, не содержащих встроенной поддержки списков? 
5. 
В  чем  заключается  разница  между  линейным  односвязным  и 
многосвязными списками? 
6. 
Что  такое  дерево  в  языках  программирования?  Перечислите  основные 
операции над деревьями. 
7. 
Каковы особенности ручного управления динамической памятью? Что 
такое сборщик мусора в языках программирования? В чем заключаются 
недостатки  и  достоинства  механизма  автоматического  управления 
памятью? 
Очереди 
Очередь представляет собой линейный упорядоченный набор, как правило, 
однотипных  элементов,  доступ  к  которому  возможен  лишь  с  конца. 
Очередь,  как  и  линейный  список, —  динамическая  структура  данных, 
напоминающая  очередь  за  продуктами  в  магазине.  Работа  с  ней 
интуитивно понятна из ее названия. Имеется лишь два базовых действия: 
 
добавление элемента в конец очереди; 
 
взятие элемента с начала (головы) очереди. 
В очереди реализуется принцип «первым пришел — первый на обработку» 
(FIFO — First Input — 
First Output) (рис. 12). 
 

жүктеу/скачать 1,55 Mb.

Достарыңызбен бөлісу: