Компьютерные науки. Деревья, операционные системы, сети

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

И.Ф. Астахова, И.К. Астанин,
И.Б. Крыжко, Е.А. Кубряков

КОМПЬЮТЕРНЫЕ НАУКИ. 

ДЕРЕВЬЯ, 

ОПЕРАЦИОННЫЕ СИСТЕМЫ, СЕТИ

Учебное пособие

Допущено УМО по классическому университетскому образованию 

в качестве учебного пособия для студентов высших учебных заведений, 

обучающихся по направлению подготовки 010800
 «Механика и математическое моделирование»

2013

УДК 004.066
ББК 32.973
А 91
Ас т а х о в а И. Ф., Ас т а н и н И. К., Кр ы ж к о И. Б., Ку б р я к о в Е. А.
Компьютерные
науки.
Деревья,
операционные
системы,
сети.
—
М.: ФИЗМАТЛИТ, 2013. — 88 с. — ISBN 978-5-9221-1449-3.

В книге содержатся теоретический материал и практические задания по
разделам: деревья, стеки, очереди, модульное программирование. Описываются основные задачи, решаемые операционными системами, алгоритмы их
реализации. Представлена классификация современных средств аппаратной
поддержки операционных систем. Рассматриваются устройство и принципы
работы сетевого аппаратного и программного обеспечения. Основное внимание
уделено стеку протоколов TCP/IP.
Книга предназначена студентам вузов, углубленно изучающим информатику, преподавателям информатики, а также специалистам в области информационных технологий.

Учебное издание

АСТАХОВА Ирина Федоровна
АСТАНИН Иван Константинович
КРЫЖКО Игорь Борисович
КУБРЯКОВ Евгений Анатольевич

КОМПЬЮТЕРНЫЕ НАУКИ.

ДЕРЕВЬЯ, ОПЕРАЦИОННЫЕ СИСТЕМЫ, СЕТИ

Редактор В.Р. Игнатова
Оригинал-макет: Е.В. Сабаева
Оформление обложки: Н.Л. Лисицына

Подписано в печать 25.02.2013. Формат 6090/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 5,5. Уч.-изд. л. 5,5. Тираж 500 экз. Заказ №

Издательская фирма «Физико-математическая литература»
МАИК «Наука/Интерпериодика»
117997, Москва, ул. Профсоюзная, 90
E-mail: fizmat@maik.ru, fmlsale@maik.ru;
http://www.fml.ru

Отпечатано в ГУП
«ИПК Чувашия», 428019
г. Чебоксары, пр-т И.Яковлева, 13

ISBN 978-5-9221-1449-3

ISBN 978-5-9221-1449-3

c⃝ ФИЗМАТЛИТ, 2013

c⃝ И. Ф. Астахова, И. К. Астанин,
И. Б. Крыжко, Е. А. Кубряков, 2013

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Г л а в а 1.
Стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.1. Основные понятия . .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .
6
1.2. Способы реализации. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3. Задачи для самостоятельного решения . .. . . . . . . . . . . . . . . . . .
11

Г л а в а 2.
Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.1. Основные понятия . .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.2. Способы реализации. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.3. Задачи для самостоятельного решения . .. . . . . . . . . . . . . . . . . .
18

Г л а в а 3.
Программирование на языке Паскаль с помощью модулей . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .
19

Г л а в а 4.
Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.1. Основные понятия и определения . .. . . . . . . . . . . . . . . . . . . . . .
23
4.2. Способы представления деревьев . .. . . . . . . . . . . . . . . . . . . . . .
27
4.3. Способы обхода деревьев . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
30
4.4. Рекурсивные алгоритмы работы с деревьями . .. . . . . . . . . . . . . .
32
4.4.1. Построение (32).
4.4.2. Поиск по дереву (35).
4.4.3. Удаление вершины из дерева (38).
4.4.4. Обработка значений в
вершинах деревьев (41).
4.4.5. Работа с деревьями-формулами (42).
4.4.6. Построение дерева-формулы, соответствующего
выражению (43). 4.4.7. Вывод дерева-формулы, соответствующего
выражению (47).
4.4.8. Вычисление значения выражения по дереву-формуле (48).
4.5. Нерекурсивные алгоритмы работы с деревьями. .. . . . . . . . . . . . .
49
4.6. Программа работы с деревьями . .. . . . . . . . . . . . . . . . . . . . . . .
52
4.7. Задачи для самостоятельного решения . .. . . . . . . . . . . . . . . . . .
54

Г л а в а 5.
Операционные системы . . . . . . . . . . . . . . . . . . . . . . . .
57
5.1. Классификация ОС . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
5.2. Управление процессами. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.3. Потоки . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .
64
5.4. Синхронизация процессов и потоков . .. . . . . . . . . . . . . . . . . . . .
64
5.5. Тупики. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66

Оглавление

5.6. Управление памятью. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.7. Иерархия запоминающих устройств и кэширование данных . .. . . .
71
5.8. Файловая система . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72

Г л а в а 6.
Сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .
75
6.1. Классификация сетей . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
6.2. Коммуникационное оборудование . .. . . . . . . . . . . . . . . . . . . . . .
76
6.3. Модель межсетевого взаимодействия ISO/OSI . .. . . . . . . . . . . . .
77
6.4. Стек протоколов TCP/IP. .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
6.5. Протокол IP . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
6.6. Некоторые распространенные технологии. .. . . . . . . . . . . . . . . . .
85

Введение

Компьютерные науки в настоящее время представляют собой одну из важнейших областей современных технологий. С этой сферой
связана большая часть современного рынка программных продуктов.
В настоящее время такие курсы входят в учебные планы ряда университетских специальностей.
Авторы затронули наиболее трудные разделы курса, по которым существует мало учебного материала. При этом считается, что читатель
знаком с разделами, посвященными стекам и очередям, так как в этом
издании эти структуры рассматриваются в недостаточном объеме.
Авторы надеются, что пособие окажется полезным не только преподавателям и студентам, но и другим читателям, заинтересованным
в получении начальных навыков по компьютерным наукам.
Авторы с благодарностью примут любые замечания, пожелания,
исправления, которые будут способствовать улучшению качества пособия, по адресу: 394693, Университетская пл., 1, Воронеж, Россия;
e-mail: astachova@list.ru.

Г л а в а 1

СТЕКИ

1.1. Основные понятия

При программировании следует учитывать, в каком порядке поступают и обрабатываются данные. Одним из способов организации
обработки данных является стек.
Стеком называется такой способ организации обработки данных,
при котором элемент, попавший в структуру последним, будет обработан первым. Говорят, что стек работает по принципу LIFO (Last In —
First Out) (последним пришел — первым ушел). Стек — это структура
с единственной точкой входа–выхода, которая называется вершиной
стека (рис. 1.1) [3].

Рис. 1.1. Принципиальная схема работы стека

Такой способ организации может быть проиллюстрирован бытовым
примером, когда, например, книги складываются на столе друг на
друга. Положить книгу можно только сверху на стопку, а взять можно
только верхнюю книгу.
Укажем типичные операции при работе со стеком:
• инициализация стека;
• добавление элемента в стек;
• исключение элемента из стека;
• проверка стека на наличие в нем элементов.

1.2. Способы реализации
7

Для удобства работы, особенно отладки программ, полезными могут быть операции:
• просмотр элементов стека (например, для вывода стека на экран
без его разрушения);
• очистка стека.

1.2. Способы реализации

Структура стека может быть реализована двумя способами [3, 5]:
• с использованием массивов;
• с использованием динамических структур (линейных списков).
Рассмотрим реализацию стека на основе массива. Отметим, что
кроме непосредственно элементов, хранящихся в стеке (для этого используется необходимое количество первых элементов массива), необходимо иметь указатель на вершину стека. Поэтому целесообразно
объединить эти данные в одну структуру. Таким образом, описание
стека имеет вид:
CONST MAXN=10; {МАКСИМАЛЬНОЕ КОЛ-ВО ЭЛ-ТОВ СТЕКА}
TYPE STEK=RECORD
INF: ARRAY [1..MAXN] OF STRING; {ЭЛЕМЕНТЫ СТЕКА}
TOP: 0..MAXN; {УКАЗАТЕЛЬ НА ВЕРШИНУ СТЕКА}
END.
Отметим, что поле TOP хранит индекс верхнего элемента стека,
а одновременно с этим и количество элементов в стеке. Поэтому если
TOP=0, то стек пуст.
Схематичное изображение такого
представления приведено на
рис. 1.2. Вершина стека TOP содержит значение 3, т. е. стек состоит
из 3 элементов: 7, 2 и 13. Если из этого стека будет считан элемент,
то получится значение 13, а значение TOP сократится до 2. Если
же необходимо добавить элемент в стек, то сначала будет увеличено
значение TOP, а затем на соответствующее место в массиве будет
записан новый элемент.

Рис. 1.2. Представление стека с помощью массива

Приведем подпрограммы, реализующие основные и дополнительные
операции работы со стеком на основе массива.
PROCEDURE INIT_ST(VAR A:STEK);
{ПРОЦЕДУРА ИНИЦИАЛИЗАЦИИ СТЕКА}

Гл. 1. Стеки

BEGIN
A.TOP:=0;
END;

PROCEDURE PUSH(VAR A:STEK; X:STRING);
{ПРОЦЕДУРА ДОБАВЛЕНИЯ ЭЛЕМЕНТА Х В СТЕК А}
BEGIN
INC(A.TOP);
A.INF[A.TOP]:=X;
END;

FUNCTION POP(VAR A:STEK):STRING;
{ФУНКЦИЯ ИЗВЛЕЧЕНИЯ ЭЛЕМЕНТА ИЗ СТЕКА А}
BEGIN
IF A.TOP=0 THEN
BEGIN
WRITELN(’ЧТЕНИЕ ЭЛЕМЕНТА ИЗ ПУСТОГО СТЕКА!’);
HALT;
END
ELSE
BEGIN
POP:=A.INF[A.TOP];
DEC(A.TOP);
END;
END;

FUNCTION EMPTY(A:STEK):BOOLEAN;
{ПРОВЕРКА СТЕКА НА ПУСТОТУ:
TRUE — ПУСТ, FALSE — СОДЕРЖИТ ЭЛЕМЕНТЫ}
BEGIN
EMPTY:=A.TOP=0;
END;

PROCEDURE PRINT_STEK(A:STEK);
{ПРОЦЕДУРА ВЫВОДА СТЕКА НА ЭКРАН — В ТОМ ПОРЯДКЕ,
КАК БУДУТ ИЗВЛЕКАТЬСЯ ЭЛЕМЕНТЫ}
VAR X:1..NMAX;
BEGIN
WRITE(’STEK: ’);
FOR X:=A.TOP DOWNTO 1 DO
WRITE(A.INF[X],’ ’);
WRITELN;
END;
PROCEDURE CLEAR_ST(VAR A:STEK);
{ПРОЦЕДУРА ОЧИСТКИ СТЕКА}
BEGIN
A.TOP:=0;
END.
Рассмотрим реализацию стека на основе динамических структур.
В этом случае описание стека имеет вид:

1.2. Способы реализации
9

TYPE STEK=^ELEMENT;
ELEMENT=RECORD
INF: STRING; {ЭЛЕМЕНТ СТЕКА}
NEXT: STEK; {УКАЗАТЕЛЬ НА СЛЕДУЮЩИЙ ЭЛЕМЕНТ}
END;
VAR TOP:STEK.
Схематичное представление стека на основе линейного списка приведено на рис. 1.3.

Рис. 1.3. Представление стека с помощью списка

При извлечении элемента из списка, представленного на рис. 1.3,
будет получено число 13; указатель TOP будет перенастроен на следующий элемент стека (2); а память, отведенная под хранение элемента 13, будет освобождена. Если же к списку необходимо добавить
элемент, то будет создано новое звено списка, в которое будет помещен добавляемый элемент. Затем будет организована ссылка с нового
элемента списка на текущую вершину стека, а сам указатель TOP
будет перенастроен на новый элемент. При сравнении рис. 1.2 и рис. 1.3
видно, что в случае реализации стека на основе динамических структур память расходуется существенно эффективнее, так как выделяется и освобождается по мере необходимости. Поэтому при решении
практических задач обычно используется реализация стека на основе
списка [3].
Рассмотрим подпрограммы работы со стеком на основе линейных
списков.
PROCEDURE INIT_ST(VAR TOP:STEK);
{ПРОЦЕДУРА ИНИЦИАЛИЗАЦИИ СТЕКА}
BEGIN
TOP:=NIL;
END;
FUNCTION EMPTY(TOP:STEK):BOOLEAN;
{ПРОВЕРКА СТЕКА НА ПУСТОТУ:
TRUE — ПУСТ, FALSE — СОДЕРЖИТ ЭЛЕМЕНТЫ}
BEGIN
EMPTY:=TOP=NIL;
END;

PROCEDURE PUSH(VAR TOP:STEK; X:STRING);
{ПРОЦЕДУРА ДОБАВЛЕНИЯ ЭЛЕМЕНТА Х В ВЕРШИНУ СТЕКА TOP}
VAR TMP:STEK;
BEGIN
NEW(TMP); TMP^.INF:=X; TMP^.NEXT:=TOP;

Гл. 1. Стеки

TOP:=TMP;
END;

FUNCTION POP(VAR TOP:STEK):STRING;
{ФУНКЦИЯ ИЗВЛЕЧЕНИЯ ЭЛЕМЕНТА ИЗ ВЕРШИНЫ СТЕКА TOP}
VAR TMP:STEK;
BEGIN
IF EMPTY(TOP) THEN
BEGIN
WRITELN(’ЧТЕНИЕ ЭЛЕМЕНТА ИЗ ПУСТОГО СТЕКА!’);
HALT;
END
ELSE
BEGIN
POP:=TOP^.INF;
TMP:=TOP;
TOP:=TOP^.NEXT;
DISPOSE(TMP);
END;
END;

PROCEDURE PRINT_STEK(TOP:STEK);
{ПРОЦЕДУРА ВЫВОДА СТЕКА НА ЭКРАН — В ТОМ ПОРЯДКЕ,
КАК БУДУТ ИЗВЛЕКАТЬСЯ ЭЛЕМЕНТЫ}
VAR TMP:STEK;
BEGIN
WRITE(’STEK: ’);
TMP:=TOP;
WHILE TMP<>NIL DO
BEGIN
WRITE(TMP^.INF,’ ’);
TMP:=TMP^.NEXT;
END;
WRITELN;
END;

PROCEDURE CLEAR_ST(VAR TOP:STEK);
{ПРОЦЕДУРА ОЧИСТКИ СТЕКА}
VAR TMP:STEK;
BEGIN
WHILE TOP<>NIL DO
BEGIN
TMP:=TOP;
TOP:=TOP^.NEXT;
DISPOSE(TMP);
END;
END.

1.3. Задачи для самостоятельного решения
11

1.3. Задачи для самостоятельного решения

1. Создать 2 стека и проверить их на равенство.
2. Создать 2 стека и проверить, входит ли стек h1 в стек h2.
3. Создать стек и проверить, есть ли в нем хотя бы 2 одинаковых
элемента.
4. Создать стек и проверить, есть ли в нем элемент, совпадающий
с первым.
5. Создать стек и проверить, есть ли в нем элемент, совпадающий
с последним.
6. Вставить в стек h1 за первым вхождением элемента Е все элементы стека h2.
7. В текстовом файле каждую строку распечатать следующим образом: сначала все цифры в обратном порядке, затем остальные символы
в обратном порядке.
8. В текстовом файле каждую строку распечатать следующим образом: сначала все латинские буквы в обратном порядке, затем все цифры
в обратном порядке, а затем остальные символы в обратном порядке.
9. Из данного текстового файла создать новый, каждая строка которого формируется следующим образом: сначала все символы, отличные
от букв и цифр, в прямом порядке, затем буквы в обратном порядке,
а затем цифры в обратном порядке.
10. Из данного текстового файла создать новый, каждая строка которого формируется следующим образом: сначала все символы, отличные от латинских букв и цифр, затем латинские буквы, а затем цифры.
При этом в каждой группе изменить взаимный порядок следования.
11. Из данного текстового файла создать новый. Сначала в него записать все цифры в том порядке, в каком они расположены в текстовом
файле, затем латинские буквы в обратном порядке и, наконец, русские
буквы в порядке следования в исходном файле.
12. Из данного текстового файла создать новый, в который записать
только буквы русского алфавита в обратном порядке.
13. В строке проверить правильность расстановки скобок 3 типов:
’{’, ’}’, ’[’, ’]’, ’(’, ’)’.

Г л а в а 2

ОЧЕРЕДИ

2.1. Основные понятия

Следующим типовым способом организации обработки данных является очередь.
Очередью называется такой способ организации обработки данных,
при котором элементы обрабатываются в том порядке, в каком они
попадали в структуру. Говорят, что очередь работает по принципу FIFO
(First In — First Out) (первым пришел — первым ушел). В отличие от
стека, где имеется единственная точка входа–выхода, очередь содержит две активные точки: начало, из которого берутся элементы для
обработки, и конец, в который добавляются поступающие в структуру
элементы (рис. 2.1) [3–5].

Рис. 2.1. Принципиальная схема работы очереди

Такой способ организации иллюстрируется бытовыми очередями.
Например, очередь в кассу в супермаркете. Покупатели обслуживаются в том порядке, в каком они встали в очередь.
Основные операции над очередью аналогичны операциям над стеком:
• инициализация очереди;