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

60 
 
недопустимо.  Некоторые  языки  программирования,  такие  как  APL  и  его 
потомки  K  и  J,  изначально ориентированы  на обработку  массивов,  в  них 
операции  применимы  к  целому  массиву  (ко  всем  элементам).  Например, 
можно  сложить  два  массива  или  найти  сумму  элементов  с  помощью 
операции, записываемой одним знаком. 
В  некоторых  языках  программирования  помимо  обычных  массивов 
применяются  так  называемые  ассоциативные  массивы,  в  которых  в 
качестве  индекса  может  использоваться  не  только  целое  число,  но  и 
значение  произвольного  типа  данных.  Точнее  говоря,  ассоциативный 
массив  представляет  собой  набор  пар  вида 
(ключ,  значение)  и 
поддерживает  операции  добавления  пары,  а  также  поиска  и  удаления  по 
ключу (индексу). В некоторых языках поддержка ассоциативных массивов 
встроена в язык, в других — нужно использовать стандартную библиотеку. 
Примеры описаний ассоциативных массивов: 
map book; //объявление язык С++, библиотека STL 
$names["Петров"]="Петр"; // обращение в языке PHP, фамилия — ключ 
print $hash{'cat'}; # язык Perl  
Ассоциативный  массив  может  быть  и  многомерным.  Многомерные 
ассоциативные  массивы  могут  содержать  несколько  ключей, 
соответствующих конкретному индексу ассоциативного массива. 
Пример многомерного ассоциативного массива на языке PHP: 
// Многомерный массив 
$
A["Ivanov"] = array("name"=>"Иванов И.И.", "age"=>"25", 
"email"=>"ivanov@mail.ru"); 
$A["Petrov"] = array("name"=>"
Петров П.П.", "age"=>"34", 
"email"=>"petrov@mail.ru"); 
$A["Sidorov"] = array("name"=>"
Сидоров С.С.", "age"=>"47", 
"email"=>"sidorov@mail.ru"); 
?> 
Контрольные вопросы 
1. 
Что  такое  массив?  Приведите  примеры  объявления  в  языках 
программирования. 
2. 
Что  такое  одномерный  и  многомерный  массивы?  Приведите  примеры 
использования. 
3. 
Что такое статический и динамический массивы? Какие преимущества 
и недостатки имеют динамические структуры данных? 
4. 
В  чем  заключаются  особенности  структуры  данных  с  произвольным 
доступом? 

61 
 
5. 
Что такое ассоциативный массив? Приведите пример использования. 
Списки 
Следующей важнейшей структурой данных являются списки. Такого рода 
структуры в языках программирования весьма разнообразны. Простейшей 
является линейный односвязный список, реализованный на базовом уровне 
в таких языках программирования, как Питон, Лисп и Пролог. 
Линейный  список  представляет  собой  набор  идущих  друг  за  другом 
элементов, при записи разделяемых пробелом, запятой или иным знаком, 
например: 
(Чайник Кастрюля Самовар) 
[a,b,c,d,e]  
В отличие от массивов, список, как правило, не предполагает возможности 
взятия  элемента  по  его  номеру.  Для  взятия  элемента  из  середины  можно 
начать  последовательно  перебирать  их  с  первого,  пока  не  будет  найден 
искомый.  В  этом  смысле  список  представляет  собой  структуру 
с 
последовательным  доступом.  Для  полноты  вводится  также  понятие 
пустого  списка,  или  списка,  не  содержащего  элементов,  для  которого 
используется специальное обозначение: 
 
NIL
 — 
в языке Лисп; 
 
[]
 — 
одно из обозначений в языке Пролог. 
Основными операциями над списками служат: 
 
взятие первого элемента — так называемой головы списка; 
 
взятие остатка списка, также являющегося списком, или его хвоста; 
 
добавление элемента в список; 
 
удаление заданного элемента из списка; 
 
проверка на вхождение элемента в список; 
 
приписывание списка к списку; 
 
подсчет количества элементов списка. 
В некоторых языках списки можно сравнивать одной операцией. 
Список  является  динамической  структурой  данных —  его  размер  может 
меняться  в  ходе  исполнения  программы.  Список  является  также  так 
называемой  рекурсивной  структурой —  его  понятие  может  быть 
определено  рекурсивно  следующим  образом:  пустой  список  является 
списком,  кроме  этого  список —  это  элемент-голова,  за  которым  идет, 
возможно  пустой  хвост-список.  В  силу  этого  для  обработки  списков 
хорошо подходят рекурсивные программы. 

62 
 
Во  многих  языках  программирования  списки  не  являются  встроенной 
структурой  (хотя  могут  быть  частью  библиотеки,  например,  для  С++ 
существует  мощная  библиотека  STL),  и  их  поддержка  требует 
конструирования на основе записей и ссылок (указателей). Это упражнение 
весьма  популярно  при  изучении  Паскаля  или  Си.  Такую  реализацию 
списка иллюстрирует рис. 9. 
 
 
 
 
 
 
 
 
 
Рис. 9 
Элементы  подобного  списка  иногда  называют  вершинами.  Каждая 
вершина здесь представляет собой элемент однотипных данных, хотя это 
могут быть и данные составного типа, и указатель на следующий элемент 
списка. Последний элемент списка содержит пустую ссылку. 
В языках программирования, поддерживающих списки на базовом уровне, 
часто  допускается  наличие  в  списке  в  качестве  элементов  данных 
различающихся типов. Элементом списка может быть и список — в этом 
случае говорят о вложенных списках. 
Другие виды списков 
Нетрудно  заметить,  что  в  линейном  односвязном  списке  возможно  лишь 
движение  от  головы  к  хвосту.  Иногда  удобно  иметь  возможность 
обратного продвижения по списку. Для этого достаточно налачия в каждой 
вершине  двух  указателей —  на  предшествующий  и  последующий 
элементы. Графически реализацию двусвязного списка можно представить 
следующим образом (рис. 10). 
Д
 

63 
 
 
 

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

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