- •Оглавление
- •Введение
- •Основные понятия и определения
- •Встроенные структуры данных(Pascal/с)
- •Варианты индивидуальных заданий на Pascal
- •Варианты индивидуальных заданий на c
- •Простые типы данных в Pascal
- •Вещественные типы
- •Вещественные типы языка Pascal
- •Сложный тип
- •Простые типы данных в с Целые типы
- •Целые типы языка c
- •Диапазоны значений целых типов языка c
- •Символьный тип
- •Перечисляемый тип
- •Вещественные типы
- •Вещественные типы языка c
- •Структурированные типы данных в Pascal Массив
- •Структура данных типа «запись»
- •Структура данных типа «множество»
- •Структурированные типы данных в c Структура данных типа «массив»
- •Структура данных типа «структура»
- •Производные структуры данных. Структура данных «строка» (Pascal/c)
- •Задание
- •Варианты индивидуальных заданий
- •Варианты задач
- •Варианты форматов
- •Назначение процедур и функций в модулях реализации сд типа строка в Pascal
- •Назначение процедур и функций в модулях реализации сд типа «строка» в c
- •Сравнительный анализ методов сортировки (Pascal/c)
- •1. Изучить временные характеристики алгоритмов.
- •6. Выводы по работе.
- •1. Выбираем элемент массива в качестве разделителя (например, первый).
- •Массив м
- •Массив м
- •Примеры программной реализации алгоритмов сортировки на языке Pascal
- •Примеры программной реализации алгоритмов сортировки на языке c
- •Сравнительный анализ алгоритмов поиска (Pascal/c)
- •Максимальное количество операций сравнения
- •Среднее количество операций сравнения
- •Алгоритмы поиска в неупорядоченных массивах Алгоритм линейного поиска
- •Алгоритм быстрого линейного поиска
- •Анализ алгоритмов линейного поиска
- •Алгоритмы поиска в упорядоченных массивах Алгоритм быстрого линейного поиска
- •Алгоритм бинарного поиска
- •Анализ алгоритма бинарного поиска
- •Алгоритм блочного поиска
- •Анализ алгоритма блочного поиска
- •Структуры данных «линейные списки» (Pascal/с)
- •Варианты индивидуальных заданий
- •Назначение процедур и функций
- •Структуры данных «стек» и «очередь» (Pascal/с)
- •Результаты работы программы
- •Варианты индивидуальных заданий
- •Варианты задач
- •Модули для реализации стека
- •Модули для реализации очереди
- •Очередь
- •Структуры данных «дерево» (Pascal/с)
- •Варианты индивидуальных заданий
- •Варианты задач
- •Назначение процедур и функций:
- •Принципы размещения бинарного дерева в памяти эвм
- •Алгоритмы обхода бинарного дерева
- •Обход бинарного дерева «в глубину» (в прямом порядке)
- •Обход бинарного дерева «в ширину» (по уровням)
- •Обход бинарного дерева в симметричном порядке
- •Обход бинарного дерева в обратном порядке
- •Алгоритмы формирования бинарного дерева
- •Рекурсивный алгоритм формирования бинарного дерева «в глубину»
- •Итеративный алгоритм формирования бинарного дерева «в глубину»
- •Алгоритм формирования бинарного дерева «в ширину»
- •Алгоритм формирования бинарного дерева «снизу вверх»
- •Рекурсивный алгоритм формирования бинарного дерева
- •Итеративный алгоритм формирования бинарного дерева
- •Алгоритм формирования бинарного дерева минимальной высоты
- •Итеративный алгоритм формирования сбалансированного бинарного дерева
- •Представление алгебраических выражений бинарными деревьями
- •Алгоритм формирования бинарного дерева по прямой польской записи
- •Алгоритм формирования бинарного дерева по обратной польской записи
- •Структуры данных «таблица» (Pascal/с)
- •Варианты индивидуальных заданий
- •Библиографический список
Структуры данных «стек» и «очередь» (Pascal/с)
Цель работы: изучить СД «стек» и «очередь», научиться их программно реализовывать и использовать.
З а д а н и е
1. Для СД «стек» и «очередь» определить:
1.1. Абстрактный уровень представления СД:
1.1.1. Характер организованности и изменчивости.
1.1.2. Набор допустимых операций.
1.2. Физический уровень представления СД:
1.2.1. Схему хранения.
1.2.2. Объем памяти, занимаемый экземпляром СД.
1.2.3. Формат внутреннего представления СД и способ его интерпретации.
1.2.4. Характеристику допустимых значений.
1.2.5. Тип доступа к элементам.
1.3. Логический уровень представления СД.
Способ описания СД и экземпляра СД на языке программирования.
2. Реализовать СД «стек» и «очередь» в соответствии с вариантом индивидуального задания в виде модулей на языках Pascal и С.
3. Разработать программы на языках Pascal и С, моделирующие вычислительную систему с постоянным шагом по времени (дискретное время) в соответствии с вариантом индивидуального задания (табл.16) с использованием модулей, полученных в результате выполнения пункта 2. Результат работы программ представить в виде таблицы 15. В первом столбце указывается время моделирования 0, 1, 2, …, N. Во втором — для каждого момента времени указываются имена объектов (очереди — F1, F2, …, FN; стеки — S1, S2, …, SM; процессоры — P1, P2, …, PK), а в третьем — задачи (имя, время), находящиеся в объектах.
Таблица 15
Результаты работы программы
|
Время |
Объекты |
Задачи |
|
0 |
F1 |
(имя,время),(имя,время),. . .,(имя,время) |
|
: |
: : : | |
|
FN |
(имя,время),(имя,время),. . .,(имя,время) | |
|
S1 |
(имя,время),(имя,время),. . .,(имя,время) | |
|
: |
: : : | |
|
SM |
(имя,время),(имя,время),. . .,(имя,время) | |
|
P1 |
(имя,время) | |
|
: |
: | |
|
PK |
(имя,время) | |
|
1 |
F1 |
(имя,время),(имя,время),. . .,(имя,время) |
|
: |
: : : | |
|
FN |
(имя,время),(имя,время),. . .,(имя,время) | |
|
S1 |
(имя,время),(имя,время),. . .,(имя,время) | |
|
: |
: : : | |
|
SM |
(имя,время),(имя,время),. . ., (имя,время) | |
|
P1 |
(имя,время) | |
|
: |
: | |
|
PK |
(имя,время) | |
|
: |
: |
: : : |
Таблица 16
Варианты индивидуальных заданий
|
Номер варианта |
Номер модуля для стека |
Номер модуля для очереди |
Номер задачи |
|
1 |
1 |
1 |
1 |
|
2 |
2 |
2 |
2 |
|
3 |
3 |
3 |
3 |
|
4 |
4 |
4 |
4 |
|
5 |
5 |
5 |
5 |
|
6 |
6 |
6 |
6 |
|
7 |
7 |
7 |
7 |
|
8 |
8 |
8 |
8 |
|
9 |
9 |
9 |
9 |
|
10 |
10 |
10 |
10 |
|
11 |
11 |
10 |
11 |
|
12 |
1 |
2 |
4 |
|
13 |
2 |
3 |
5 |
Окончание табл.16
|
14 |
3 |
4 |
6 |
|
15 |
4 |
5 |
7 |
|
16 |
5 |
6 |
8 |
|
17 |
6 |
7 |
9 |
|
18 |
7 |
8 |
10 |
|
19 |
8 |
9 |
11 |
|
20 |
9 |
10 |
1 |
|
21 |
10 |
11 |
2 |
|
22 |
11 |
10 |
3 |
|
23 |
1 |
3 |
4 |
|
24 |
2 |
4 |
5 |
|
25 |
3 |
5 |
6 |
|
26 |
4 |
6 |
7 |
|
27 |
5 |
7 |
8 |
|
28 |
6 |
8 |
9 |
|
29 |
7 |
9 |
10 |
|
30 |
8 |
10 |
11 |