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

66 
 
стеке реализуется принцип «последним пришел — первым на обработку» 
(LIFO, Last Input — First O
utput). Базовые действия над стеком: 
 
добавление элемента на вершину стека; 
 
взятие элемента с вершины. 
Это может быть проиллюстрировано рис. 13. 
 
Рис. 13 
Стек, как и очередь, может быть пуст. Популярное называние действия по 
помещению элемента на вершину стека — PUSH, а извлечения из стека — 
POP
. Со стеком, как и очередью, можно выполнить популярные операции: 
 
проверку на пустоту; 
 
подсчет количества элементов; 
 
копирование значения на вершине с оставлением элемента в стеке. 
Стек  работает  по  принципу  магазина  пистолета  или  стопки  книг.  Книга, 
находящаяся  на  вершине  стопки,  снимается  с  нее  первой.  А  до  книги, 
лежащей в самом низу, читатель добирается позже. 
Стеки  и  очереди  поддерживаются  во  многих  языках  программирования 
специальными библиотеками, например, в С++ — библиотекой STL. 
Контрольные вопросы 
8. 
Что  такое  стек  в  языках  программирования?  Каковы  области 
использования стека? Каковы основные операции со стеком? 
9. 
В чем заключаются особенности структуры данных «очередь»? Каковы 
основные операции над очередями? 
Кортежи 
В некоторых языках программирования, например Питон и русскоязычная 
РАПИРА,  имеется  такая  встроенная  структура  данных,  как  кортеж. 
Кортеж —  динамическая  структура  данных,  представляющая  собой 
упорядоченную совокупность разнотипных элементов: 
("a", "b", "mpilgrim", "z", "example") # 
язык Питон 
<"Я",7,"Вася",<1,"Осень">,-25> (* язык программирования РАПИРА *) 

67 
 
Как видно из примера, кортеж может входить в состав другого кортежа — 
допустима вложенность кортежей. 
К основным операциям над кортежами относятся: 
 
взятие элемента по его порядковому номеру; 
 
проверка на вхождение элемента; 
 
вырезка подкортежа; 
 
конкатенация; 
 
подсчет количества элементов. 
Кортеж — структура с произвольным доступом за счет наличия операции 
взятия  элемента  по  номеру.  Кортеж  похож  на  список,  массив  и  строку 
одновременно и представляет собой весьма мощную структуру данных. 
В кортеж, в отличие от множества, один элемент может входить несколько 
раз. 
Множества 
В  Паскале,  Модуле  и  некоторых  других  языках  программирования 
возможно использование так называемых множеств. Понятие множества, 
вероятно,  известно  читателю  из  математики,  где  так  называется 
совокупность  элементов  произвольной  природы.  Понятие  множества  в 
программировании 
значительно  ýже 
математического  понятия. 
Множество —  динамическая  структура  данных,  представляющая  собой 
неупорядоченную совокупность элементов, как правило, однотипных. 
Базовые операции над множествами: 
 
проверка вхождения элемента в множество; 
 
теоретико-множественные  операции —  объединение,  пересечение, 
вычитание; 
 
сравнение множеств на эквивалентность; 
 
проверка вхождения подмножества в множество; 
 
удаление и/или добавление элемента. 
Далее  приводится  ряд  примеров,  иллюстрирующих  использование 
множеств: 
set s; // объявление множества целых в С++, библиотека STL 
 
(*язык программирования Паскаль*) 
Type symbol= set of char; (* объявление типа symbol -множества*) 
Var small, capital, latin: symbol; (* 
три множества *) 
… 

68 
 
small:= ['a' .. 'z']; (* строчные латинские буквы *) 
capital:= ['A' .. 'Z']; (* прописные латинские буквы *) 
latin:= small + capital; (*
объединение множеств small и capital *) 
 
small:= small + ['a'] +['b']; (* добавление поэлементно*) 
 
z:= x*y; (* если x,y,z — множества — пересечение *) 
 
letter:= ['a' .. 'z']; (*множество букв латинского алфавита*) 
glasn:= ['a', 'e', 'o', 'u', 'i', 'y']; (*множества гласных букв*) 
soglasn:= letter-
glasn; (* вычитание множеств*) 
После  приведенного  задания  множеств  glasn  и  soglasn  операция 
проверки  вхождения  элемента  'a' in  glasn  возвразщает  значение 
true
, 
а 'o' in soglasn — false. 
Для  сравнения  множеств  на  равенство  или  неравенство  в  Паскале 
используются символы = и <>: 
A:= [2,1,3]; 
D:= [1,3,2]; 
В этом случае A=D возвращает значение true, а A<>D — значение false. 
Операции проверки включения обозначаются <= и >=, после приведенного 
будет соблюдаться letter >= glasn и soglasn <= letter. 
В  множество,  в  отличие  от  кортежа,  элемент  может  входить  лишь 
единожды. 
Контрольные вопросы 
10. 
Что  такое  кортеж  в  языках  программирования?  Каковы  основные 
операции с кортежами? Сравните списки и кортежи. 
11. 
Что  такое  множества  в  языках  программирования?  Каковы  операции 
над множествами? Сравните массивы, кортежи и множества. 
Записи 
Весьма  важной  и  популярной  структурой  данных  в  языках 
программирования  являются  записи  (иногда  запись  называется 

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

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