 |
Приложение 2. Код программы
|
|
|
|
Теоретические сведения
В простейшем случае семафор (S) представляет собой целочисленную переменную, принимающую неотрицательные значения. Над ней определены две атомарные операции (примитивы, которые нельзя прервать): P(S) и V(S). Операция P(S): уменьшение переменной S на 1 (декремент), если возможно. Если S = 0, то уменьшить S невозможно. Тогда процесс, вызывающий операцию P(S), ждёт, пока уменьшение станет возможно. Успешная проверка и уменьшение S – неделимая операция, т. е. она не может быть прервана, и в момент её выполнения другие процессы не имеют доступа к S. Операция V(S): увеличение переменной S на 1 (инкремент), это действие также неделимо. Стандартно эти две операции поддерживаются ядром операционной системы.
Использование семафорных операций заключается в следующем. Предположим, имеется некоторый вычислительный ресурс, к которому может быть предоставлен доступ лишь одному процессу единовременно. С каждым вычислительным ресурсом связывается индивидуальный семафор. Предполагается, что ресурс может быть после своего освобождения повторно использован. Пусть процесс А обращается к семафору ресурса и запрашивает выполнение операции P(S) (хочет получить доступ к ресурсу). Если S был в ненулевом состоянии, то он получит значение 0, и ресурс будет занят процессом А. Пусть через некоторое время процесс В обратится к тому же ресурсу с операцией P(S). Считаем, что семафор может иметь только два значения: 0 и 1. Следовательно, дальнейшее уменьшение для S невозможно. Ресурс считается занятым. Поэтому процесс В должен быть заблокирован. Для этого выполняется операция WAIT, которая переводит процесс в очередь приостановленных процессом к данному ресурсу (это очередь блокированных процессов). Когда процесс А освобождает ресурс, он выполняет операцию V(S). После этого выполняется функция SIGNAL, которая оповещает, что S > 0. Следовательно, можно выбрать с помощью диспетчера очереди один из процессов, ожидающих ресурс. Он может повторить операцию P(S) и получить ресурс.
|
|
|
Следует отметить, что семафорные операции используются не только для ограничения единовременного доступа. Например, семафоры находят широкое применение в области синхронизации процессов. Однако в данной работе мы сосредоточимся на разделении ресурсов.
С помощью структуры данных можно описать состояние большого числа классов ресурсов. Каждый класс ресурсов требует минимум 3 компоненты: опись, включающую число и идентификацию доступных единиц ресурсов; список (очередь) ожидания блокированных процессов с неудовлетворёнными запросами на ресурсы; диспетчер, ответственный за принятие решения, в каком порядке удовлетворять запросы.
В простейшем случае структура данных ресурса включает: семафор ресурса S; идентификатор ресурса ID[S]; список доступности Avail[S]; список ожидающих процессов Waiters[S]; точка входа в распределитель (диспетчер) Blocator[S]. Ссылка Avail[S] указывает на начало списка доступности или опись для семафора ресурса. Список в заголовке может содержать также указатели (точки входа) для двух стандартных программ. Одна – для вставки новых элементов (освобождённых ресурсов), другая – для удаления распределённых ресурсов. Таким образом, здесь предполагается, что список содержит несколько идентичных единиц ресурса. Список ожидающих процессов содержит все процессы, заблокированные на семафоре ресурса. Списки ожидания могут иметь различный вид. Запись о каждом процессе содержит его идентификатор и информацию о запросе на ресурс. В простейшем случае список содержит один элемент. Часто указатель на список в очереди Waiter[S] показывает на очередь (типа FIFO). Вид этой очереди содержит заголовок очереди с последующими элементами очереди.
|
|
|
Заголовок очереди: точка входа в стандартную программу вставки – Insert[q]; точка входа в стандартную программу удаления – Remove[q]; первый элемент – First[q]; последний элемент – Last[q].
Элемент очереди представляется в виде: идентификатор процесса – pi (часто указатель на дескриптор процесса); элемент di – дополнительные сведения о запросе; ячейка ai, куда должна быть помещена информация о распределении в момент, когда запрос будет удовлетворён.
В простейшем случае диспетчер процессов имеет форму Allocator(r, k, L), где k и L это выходные параметры со значениями: k – число незаблокированных процессов, которым распределены ресурсы, k > 0; L[i], i = 1, …, k – список процессов, которым распределены ресурсы (определён, когда k > 0); r – имя семафора ресурсов.
В явном виде диспетчер процессов может отсутствовать – это значит, что ресурс предоставляется процессам в том порядке, в котором они его запросили. Однако, в реальных операционных системах действует сложная система приоритетов, и место процесса в очереди за ресурсом определяется не только временем поступления запроса. Система учитывает множество иных факторов, таких, как текущая загрузка процессора, количество свободной памяти и т.д.
Исходные допущения: есть два процесса p1 и p2 и один ресурс R; процессы p1 и p2 обращаются к R раздельно. Обращение процессов к R и освобождение R моделируется пользователем с экрана в некоторой последовательности, определённой пользователем.
Алгоритмы
Алгоритм (А1) процедуры получения ресурса:
Шаг 1. Если значение семафора ресурса положительно, перейти к шагу 2, иначе перейти к шагу 3;
Шаг 2. Уменьшить значение семафора ресурса на 1 и выйти из процедуры;
Шаг 3. Добавить процесс в список ожидания ресурса.
Схема алгоритма изображена на рис. 1.
Алгоритм (А2) процедуры освобождения ресурса:
Шаг 1. Если очередь ожидания ресурса пуста, перейти к шагу 2, иначе перейти к шагу 3;
Шаг 2. Увеличить значение семафора ресурса на 1 и выйти из процедуры;
Шаг 3. Извлечь из очереди следующий процесс и передать ему ресурс.
Схема алгоритма изображена на рис. 2.
|
|
|
Рис. 1 Схема алгоритма А1 Рис. 2 Схема алгоритма А2
(процедура получения ресурса) (процедура освобождения ресурса)
Тестовый пример
Дано: 8 процессов, 3 ресурса.
Задание: требуется разработать:
1) Примитивы V(S), P(S), SIGNAL, WAIT, работающие в среде 8 процессов и 3 ресурсов;
2) Структуру данных ресурса R;
3) Структуру указателя описи ресурса;
4) Структуру очереди с её заголовком;
5) Программу вставки в очередь Insert[q];
6) Программу удаления Remove[q];
7) Распределитель Allocator;
8) Построить программу динамического моделирования.
Результат:
Результат работы программы приведёт в Приложении 1.
Код программы приведён в Приложении 2.
4. Контрольные вопросы
1. Что такое семафор?
2. Для чего применяются семафоры?
3. Что такое операции V(s) и P(s)?
4. Что такое операции SIGNAL и WAIT?
5. Что включает в себя опись ресурса?
6. Что такое список ожидающих процессов?
7. Что содержит заголовок очереди?
8. Что такое Allocator(r, k, L)?
9. Что значит «неделимая (атомарная) операция»?
10. Чем грозило бы «деление» V(s) или P(s)?
Варианты заданий
Таблица 1
| Вариант | Кол-во процессов | Кол-во ресурсов | Вариант | Кол-во процессов | Кол-во ресурсов |
Содержание отчёта
1. Наименование работы
2. Цель работы
3. Краткие теоретические сведения
4. Вариант задания
5. Код программы
6. Пример работы программы
7. Анализ полученных результатов и выводы
8. Подпись исполнителя
Приложение 1
Пример работы программы
В вашем распоряжении имеется 8 процессов и 3 ресурса.
Чтобы выйти, в любой момент введите 0.
Введите номер процесса (от 1 до 8): 1
Введите номер ресурса (от 1 до 3): 1
Ресурс #1 успешно занят процессом #1.
|
|
|
Введите номер процесса (от 1 до 8): 5
Введите номер ресурса (от 1 до 3): 1
Процесс #5 заблокирован в ожидании ресурса #1.
Введите номер процесса (от 1 до 8): 6
Введите номер ресурса (от 1 до 3): 1
Процесс #6 заблокирован в ожидании ресурса #1.
Введите номер процесса (от 1 до 8): 5
Процесс заблокирован в ожидании ресурса 1.
Введите номер процесса (от 1 до 8): 1
Введите номер ресурса (от 1 до 3): 1
Процесс #1 освободил ресурс #1.
Процесс #5 разблокирован и теперь занимает ресурс #1.
Введите номер процесса (от 1 до 8): 0
Программа динамического моделирования завершила работу.
Приложение 2. Код программы
#include <locale.h>
#include <math.h>
#include <cstdio>
#define NUM_PROC 8 // количество процессов
#define NUM_RES 3 // количество ресурсов
struct Resource // Структура данных ресурса (п. 2, 3)
{
int id, s; // идентификатор и семафор
int waiters[NUM_PROC]; // список ожидающих ресурс процессов (п. 4)
int owner; // текущий владелец ресурса
};
// Код получения ресурса:
bool P(int& s)
{
// Функция уменьшения значения семафора (п. 1)
// Возвращает true, если значение семафора уменьшено,
// и false, если уменьшение невозможно.
if (s > 0)
{
s -= 1;
return true;
}
else
return false;
}
void insert(int* arr, int val)
{
// Процедура добавления процесса в конец очереди (п. 5)
int i = 0;
while (arr[i]!= -1)
i++;
arr[i] = val;
arr[i+1] = -1; // в конце очереди всегда стоит -1
}
void wait(Resource& res, int proc)
{
// Процедура постановки в очередь на ресурс res процесса с номером proc (п. 1)
insert(res.waiters, proc);
}
bool seize(Resource& res, int proc)
{
// Процедура получения доступа к ресурсу res процессом с номером proc.
// Возвращает true, если доступ получен, и false, если процесс поставлен в очередь.
if (P(res.s)) // Шаг 1 алгоритма А1
{ // Шаг 2 алгоритма А1:
res.owner = proc;
return true;
}
else
{ // Шаг 3 алгоритма А1:
wait(res, proc);
return false;
}
}
// Код освобождения ресурса:
void V(int& s)
{
// Функция увеличения значения семафора (п. 1)
if (s == 0)
s += 1;
}
int allocator(Resource& res)
{
// Функция, возвращающая номер процесса, который получит доступ к ресурсу следующим (п. 7)
return res.waiters[0]; // в простейшем случае, возвращает следующий процесс в очереди
}
void remove(int* arr, int val)
{
// Процедура удаления процесса из очереди (п. 6)
int i = 0;
while (arr[i]!= val)
i++;
do
{
arr[i] = arr[i+1];
i++;
}
while (arr[i]!= -1);
}
void signal(Resource& res)
{
// Процедура оповещения о том, что ресурс res свободен (п. 1)
// Возвращает false, если ресурс теперь занят другим процессом,
// и true, если ресурс свободен.
int next = allocator(res);
remove(res.waiters, next);
res.owner = next;
}
void release(Resource& res)
{
// Процедура освобождения ресурса res.
if (res.waiters[0] == -1) // Шаг 1 алгоритма А2
{ // Шаг 2 алгоритма А2:
V(res.s);
res.owner = -1;
}
else
{ // Шаг 3 алгоритма А2:
signal(res);
|
|
|
}
}
// Код, реализующий пользовательский интерфейс:
int main()
{
Resource resource[NUM_RES]; // массив ресурсов
for (int i = 0; i < NUM_RES; i++)
{
resource[i].id = i;
resource[i].s = 1;
resource[i].waiters[0] = -1; // очередь пуста
resource[i].owner = -1; // ресурс свободен
}
int blocked[NUM_PROC]; // массив определает, какой ресурс сейчас ожидает процесс
for (int i = 0; i < NUM_PROC; i++)
blocked[i] = -1; // означает, что процесс не ожидает никакого ресурса
setlocale(LC_ALL, "rus");
printf("В вашем распоряжении имеется %d процессов и %d ресурса.\n", NUM_PROC, NUM_RES);
printf("Чтобы выйти, в любой момент введите 0.\n");
while (true)
{
printf("\n");
int proc, res;
do
{
printf("Введите номер процесса (от 1 до %d): ", NUM_PROC);
scanf("%d", &proc);
} while (proc < 0 || proc > NUM_PROC);
if (proc == 0)
{
printf("Программа динамического моделирования завершила работу.");
return 0;
}
else
proc -= 1; // делаем номер процесса индексом массива
if (blocked[proc]!= -1)
{
printf("Процесс заблокирован в ожидании ресурса %d.\n", blocked[proc]+1);
continue;
}
do
{
printf("Введите номер ресурса (от 1 до %d): ", NUM_RES);
scanf("%d", &res);
} while (res < 0 || res > NUM_RES);
if (res == 0)
{
printf("Программа динамического моделирования завершила работу.");
return 0;
}
else
res -= 1; // делаем номер ресурса индексом массива
if (resource[res].owner!= proc)
if (seize(resource[res], proc))
printf("Ресурс #%d успешно занят процессом #%d.\n", res+1, proc+1);
else
{
blocked[proc] = res;
printf("Процесс #%d заблокирован в ожидании ресурса #%d.\n", proc+1, res+1);
}
else
{
release(resource[res]);
printf("Процесс #%d освободил ресурс #%d.\n", proc+1, res+1);
if (resource[res].owner!= -1)
{
blocked[resource[res].owner] = -1;
printf("Процесс #%d разблокирован и теперь занимает ресурс #%d.\n", resource[res].owner+1, res+1);
}
}
}
}
Содержание
1. Теоретические сведения................................................................................... 1
2. Алгоритмы....................................................................................................... 2
3. Тестовый пример............................................................................................. 3
4. Контрольные вопросы..................................................................................... 3
5. Варианты заданий........................................................................................... 4
6. Содержание отчета......................................................................................... 4
Приложение 1. Пример работы программы...................................................... 4
Приложение 2. Код программы.......................................................................... 5
Лабораторная работа №2
«Интерпретатор командного языка (КЯ) операционной системы»
Цель работы: изучить принцип работы командного языка (КЯ).
Теоретические сведения
Основная связь между пользователем и ОС осуществляется посредства командного языка (КЯ), на котором пользователь обращается к системе и указывает выполняемую задачу. КЯ имеет свой синтаксис и семантику. Синтаксис определяет, какие операторы можно определять, а семантика указывает, что они означают.
Командная система является полным набором модулей, структур данных и утверждений, которые определяют интерфейс между пользователем и системой. Важный аспект КЯ – форма и содержание языка ответов, который сообщает информацию пользователю.
КЯ представляет полный набор обращений к операциям или функциями, которые являются системными (часто называемыми утилитами), которые определяют для пользователя возможности вычислительной системы при работе с терминалом. Он обеспечивает средства, с помощью которых пользователь задает выполнение работы, получает ресурсы для этого, связывается с системой. Обычно КЯ проектируется совместно с проектированием ОС.
Критерии при его проектировании: простота, выразительность и краткость, симметричность, легкость чтения, обнаружение и предотвращение ошибок, гибкость, подтверждение.
Интерпретатор командного языка (ИКЯ) получает запросы на выполнение команд через обращения к ОС(с использованием прерывания). Эти команды определяют обращения к функциям. Часть этих функций находится в системной области оперативно памяти. Другая часть – внешние, они размещаются на жёстком диске и вызываются на использование в транзитную часть системной области. В процессе выполнения этих функциональных модулей они также могут взаимодействовать с друг другом через прерывания, обрабатываемые ОС. Последнее часто не затрагивает работу ИКЯ. Работа ИКЯ базируется на использовании таблиц векторов прерывания.
Каждый элемент таблицы(вектор прерывания) содержит причину(номер прерывания и его уточнённые параметры) и адрес начала программы обработки этого прерывания. При обработке прерывание определяется отвечающим ему адресом программы прерывания и, если необходимо, после загрузки ее в транзитную область управление передается этой программе.
Алгоритм
Шаг 1. Задание количества запросов для каждого процесса
Шаг 2. Сброс флага свободный ресурсы
Шаг 3. Все процессы завершены? Если да то печатать таблицу (пункт 9), если нет то:
Шаг 4. Освободить ресурсы
Шаг 5. Найти число завершенных процессов
Шаг 6. Были выполнены все процессы? Если да то (пункт 9), если нет то:
Шаг 7. Активизировать ранее остановленный процесс
Шаг 8. Выделение ресурсов, вернуться в пункт 3.
Шаг 9. Печать таблицу
Алгоритм изображен на рисунке 1.
Рис 1 Схема алгоритма
Тестовый пример
Дано: команды «ERY, COPY, DATE, LADEL»
Задание: надо найти адреса размещения команд.
Запускаем приложение. Программа в приложении.
Результат работы программы:
> ladel
Адрес этой программы для данной команды 23281
> date
Адрес этой программы для данной команды 26962
> copy
Адрес этой программы для данной команды 29358
>ery
Такой команды нет.
>exit
PrintScreen результата работы программы Рис 2
Рис 2 Результат работы программы
4.Контрольные вопросы
1.Что такое командный язык операционной системы?
2. Критерии при его проектировании?
3. Важный аспект КЯ – форма и содержание языка ответов, который сообщает информацию о чем?
4.Что такое Интерпретатор командного языка?
5.Варианты заданий:
Варианты заданий представлены в таблице.
| № Варианта | Имена команд |
| № 1 | Attrib |
| Alias | |
| Backup | |
| № 2 | Break |
| Chdir | |
| Octave | |
| № 3 | Chkdsk |
| Cls | |
| Recode | |
| № 4 | Comp |
| Copy | |
| Pushd | |
| № 5 | Date |
| Del | |
| Sed | |
| № 6 | Echo |
| Find | |
| Rsync | |
| № 7 | Ladel |
| Attrib | |
| Fdisk |
Постановка задачи: необходимо найти адреса размещения данных команд, или же указать, что их не существует.
Содержание отчета
1. Наименование работы
2. Цель работы
3. Краткие теоритические сведения
4. Варианты заданий
5. Пример выполнения программ
6. Код программы
7. Анализ полученных результатов
8. Подпись исполнителя
Приложение.
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
const int n=13;
struct table //Объявили новую структуру table, создание структуры запроса.
{
char name[10];//Первый параметр
int adress;//Второй параметр};
void main()
{
setlocale(LC_ALL, "Russian"); // подключение русского языка
struct table tbl[n]; // Объявили массив переменных типа table
FILE *fin,*fout; //создаем указатели на переменную типа FILE
char e[]="exit"; // создаем строку содержащую слово "exit"
int i,j; //создаем 2 переменные типа int, для перебора
bool found; //создаем переменную типа bool, флаг
char buf[10]; //создание буфера
e[5]=0;
fopen_s(&fin,"input.txt","r"); //Открытие файла
fopen_s (&fout,"output.txt","w"); //Открытие файла
for(i=0;i<n;i++) //создание таблицы команд ШАГ1
{ fgets(tbl[i].name,10,fin); //считывание команды из файла
j=0;
while(tbl[i].name[j]!=10) // задание названия команды
j++;
tbl[i].name[j]=0;
tbl[i].adress=rand();// задание адреса команды ШАГ2
}
printf("Список команд\n");
fprintf(fout,"Список команд\n");
for(i=0;i<n;i++)// вывод таблицы на экран
{ printf("%s\n",tbl[i].name);
fprintf(fout,"%s\n",tbl[i].name);
}
do;// ШАГ3
{
found=false;//флаг выключен ШАГ4
printf(">");
fprintf(fout,">");
gets_s(buf);// считывание с экрана
fprintf(fout,"%s\n",buf);//запись в файл
for(i=0;i<n;i++)//поиск команды по таблице ШАГ5
{if(!strcmp(buf,tbl[i].name))
{
printf("Адрес этой подпрограммы для данной команды %d\n",tbl[i].adress);//вывод на экран полученного результата
fprintf(fout,"Адрес этой подпрограммы для данной команды %d\n",tbl[i].adress);// запись в файл полученного результата
found=true;// флаг включен
break;
}
}
if((!found)&&(strcmp(e,buf)))// ШАГ6
{
printf("Такой каманды нет.\n");//вывод на экран полученного результата ШАГ7
fprintf(fout,"Такой каманды нет.\n");// запись в файл полученного результата ШАГ8
}
}
while(strcmp(e,buf));//выход из программы
fclose(fin);//закрытие файла. Шаг 9
fclose(fout);//закрытие файла
}
Содержание
1. Теоретические сведения................................................................................. 11
2. Алгоритмы..................................................................................................... 11
3. Тестовый пример........................................................................................... 13
4. Контрольные вопросы................................................................................... 13
5. Варианты заданий......................................................................................... 13
6. Содержание отчета....................................................................................... 14
Приложение...................................................................................................... 14
Лабораторная работа №3
«Алгоритмы последовательного поиска в таблице записи данных»
Цель работы: изучение алгоритмов последовательного поиска (простого, быстрого и в упорядоченной таблице) с подсчетом числа сравнений.
Теоретические сведения
Поиск связан с накоплением информации в памяти компьютера и ее быстрым извлечением (нахождением одной из записей), причем каждая запись имеет конкретный идентификатор, то есть содержит специальное поле – ключ. Набор всех записей образует таблицу (файл, базу данных).
Алгоритм поиска использует аргумент K, и задача заключается в нахождении записи, для которой K служит ключом. Результат поиска: успешно (запись, содержащая K, найдена), либо неудачно. При неудачном поиске иногда вносят новую запись (содержащую K) в таблицу, называемую вставкой.
Цель поиска – нахождение информации, хранящейся в ассоциированной с K записи. Поиск является основополагающим действием многих программ и осуществляется над числовыми и символьными значениями.
Методы поиска классифицируются: внутренние и внешние; статические (содержание таблицы остается неименным и динамические (содержание таблицы изменяется вставкой или удалением элементов); на сравнении ключей или некоторых их числовых свойств; на использовании ключей действительных и преобразованных; простые и сложные. Существуют ситуации, когда поиск и сортировка взаимозаменяемы.
В лабораторной работе рассмотрен последовательный поиск, который начинается с начала и продолжается, пока не будет найден искомый ключ, после чего алгоритм останавливается. Последовательный поиск используется как отправная точка во многих более сложных алгоритмах поиска.
Алгоритмы поиска
Алгоритм S. Последовательный поиск
Последовательный поиск представляет собой самый простой и очевидный способ поиска записей по ключу в таблице. Программа, использующая этот алгоритм, последовательно проходит по таблице записей, начиная с самого начала и останавливается лишь в двух случаях: когда обнаруживается искомая запись, либо когда пройдена вся таблица, а искомая запись не найдена.
Простота алгоритма позволяет дорабатывать его, создавая более эффективные для конкретных ситуаций методы поиска. Сам по себе алгоритм очевиден (например, человек его использует, когда ищет нужную книгу на полке), однако неочевидно то, что его производительность можно значительно ускорить простыми операциями для таблицы, содержащей большое количество записей.
Имеется таблица записей R0 ,…, RN-1, N > 0, где каждая из записей снабжена ключом K0 ,…, KN-1. Переменная i – служебная, используется для указания индекса текущей записи. Алгоритм состоит из четырех шагов, связанных одним циклом.
Шаг 1. [Начальная установка]. Установить i = 0.
Шаг 2. [Сравнение]. Если K = Ki, то поиск завершен, вернуть Ri.
Шаг 3. [Продвижение]. Увеличить i на единицу, то есть i = i + 1.
Шаг 4. [Завершение]. Если i < N (то есть, пройдены не все записи), вернуться к шагу 2, в противном случае поиск заканчивается неудачно.
Схема алгоритма приведена на рис. 1.
Алгоритм Q. Быстрый последовательный поиск
Этот алгоритм представляет усовершенствованный алгоритм S. Имеется аналогичная алгоритму S таблица записей с аналогичным набором ключей, однако в отличие от простого последовательного алгоритма, здесь предполагается, что в конце таблицы помещается вставка RN, ключ которой KN = K.
Шаг 1. [Начальная установка]. Установить i = 0, KN = K.
Шаг 2. [Сравнение]. Если K = Ki, перейти к шагу 4.
Шаг 3. [Продвижение]. Увеличить i на единицу и перейти к шагу 2.
Шаг 4. [Завершение]. Если i < N, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно.
При переходе от алгоритма S к алгоритму Q использован важный ускоряющий принцип – при нескольких проверках во внутреннем цикле их сводят к одной. Таким образом, с ростом числа записей в таблице наблюдается прирост производительности этого алгоритма по сравнению с предыдущим.
Схема алгоритма приведена на рис. 2.
Алгоритм T. Последовательный поиск в упорядоченной таблице
Имеется таблица записей R0 ,…, RN-1, N > 0, где каждой записи сопоставлен ключ Ki, при этом каждый следующий ключ должен быть численно больше предыдущего, то есть Ki > Ki-1. Для ускорения работы предполагается, что в конце таблицы расположена вставка RN, ключ которой превышает значения всех остальных ключей: KN = ∞ > Ki, i = 1,..., N -1.
Шаг 1. [Начальная установка]. Установить i = 0.
Шаг 2. [Сравнение]. Если K < Ki, перейти к шагу 4.
Шаг 3. [Продвижение]. Увеличить i на единицу и перейти к шагу 2.
Шаг 4. [Завершение]. Если K = Ki, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно.
В предположении, что все входные аргументы-ключи равновероятны, алгоритм по скорости работы в случае успешного поиска аналогичен алгоритму Q; при неудачном же поиске отсутствие нужного ключа определяется примерно вдвое быстрее. Однако требование этого алгоритма – обязательное размещение ключей записей по возрастанию. Часто ключи в таблице так и располагаются, вследствие чего этот алгоритм является одним из наиболее востребованных.
Схема алгоритма приведена на рис. 3.
Тестовый пример
Дана таблица входных данных (таблица 1), каждой записи в которой сопоставлен определенный числовой ключ.
Таблица 1
| Ki | ||||||||||
| Ri | one | two | three | four | five | six | seven | eight | nine | ten |
| i < N? |
| alg_s(K) |
| i=0 |
ШАГ 1
| K = Ki? |
ШАГ 2
НЕТ ДА
| i = i + 1 |
| alg_s = Ri |
ШАГ 3
ШАГ 4
ДА НЕТ
| alg_s = NULL |
| Конец |
Рис 1. Схема алгоритма S
| alg_q(K) |
| i=0, KN = K |
ШАГ 1
| Ki = K? |
ШАГ 2
НЕТ ДА
ШАГ 3
| i = i + 1 |
| i < N? |
ШАГ 4
| alg_q = NULL |
| alg_q = Ri |
| Конец |
Рис 2. Схема алгоритма Q
| alg_t(K) |
| i=0 |
ШАГ 1
| K < Ki? |
ШАГ 2
НЕТ ДА
ШАГ 3
| i = i + 1 |
| Ki = K? |
ШАГ 4
| alg_t = NULL |
| alg_t = Ri |
| Конец |
Рис 3. Схема алгоритма T
Требуется показать работу алгоритмов поиска для двух ситуаций: когда ключ существует в таблице, и когда ключ не существует. Для каждого алгоритма отобразить результат (успешно или неудачно) и количество сравнений, а в случае, если успешно – дополнительно отобразить найденную запись.
Изначально считывается таблица записей из файла входных данных и помещается в массив. Затем пользователю программы предлагается ввести искомый ключ K, ассоциированную с которым запись требуется отыскать. После ввода пользователем K программа по очереди выполняет последовательный поиск тремя алгоритмами и по окончании работы каждого алгоритма выводит результат.
Выходные данные программы для ключей «3» и «27» представлены в таблице 2.
Таблица 2
| Выходные данные, если поле найдено | Выходные данные, если поле не найдено |
| Алгоритм S: Запись: "three", i=3 Алгоритм Q: Запись: "three", i=3 Алгоритм T: Запись: "three", i=3 | Алгоритм S: Запись не найдена, i=11 Алгоритм Q: Запись не найдена, i=11 Алгоритм T: Запись не найдена, i=11 |
Код программы на языке C приведен в Приложении.
4. Контрольные вопросы
11. Что такое ключ (в контексте поисковых алгоритмов)?
12. Как работает последовательный поиск?
13. Объясните причину сокращения времени поиска при использовании усовершенствованных алгоритмов последовательного поиска (быстрого и в упорядоченной таблице).
14. Где применяется каждый из описанных видов поиска и почему?
15. Какие из описанных алгоритмов поиска являются статическими, а какие динамическими? Почему?
Варианты заданий
Написать программу, в которой должны быть реализованы описанные алгоритмы последовательного поиска (простой, быстрый или в упорядоченной таблице). Необходимые для реализации алгоритмы выбрать из таблицы 3 согласно варианту, определенному преподавателем. Исходные (входные) данные придумать самостоятельно и разместить во внешнем текстовом файле.
Таблица 3
| Вариант | Алгоритм поиска | ||
| S | Q | T | |
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + | ||
| + | + |
Содержание отчёта
1. Наименование работы
2. Цель работы
3. Краткие теоретические сведения
4. Вариант задания
5. Код программы
6. Пример работы программы
7. Анализ полученных результатов и выводы
8. Ответы на контрольные вопросы
9. Подпись исполнителя
Приложение
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Прототипы функций, реализующих методы поиска
void * alg_s(int);
void * alg_q(int);
void * alg_t(int);
// Максимальное количество записей в таблице
#define max_N 15
int N = max_N;
int i;
// Структура, описывающая единичную запись с ключом
typedef struct {
int k;
void *field;
} item;
// Объект, представляющий собой таблицу записей с ключами
item items[max_N+1];
void main()
{
// Объявление переменных и чтение таблицы из файла
FILE *in;
int k;
void *data;
char buf[259];
char s[3];
char flag=0;
if((in = fopen("input.txt","rt")) == NULL)
{
printf("Невозможно открыть файл\n");
return;
}
i=0;
while(fgets(buf,255,in)!= NULL)
{
items[i].k = atoi(buf);
if(buf[strlen(buf)-1] == '\n')
buf[strlen(buf)-1] = '\0';
items[i].field = malloc(strlen(&buf[3]));
strcpy(items[i].field,&buf[3]);
i++;
}
N = i;
fclose(in);
// Конец чтения из файла
// Ввод ключа
printf("%s\n","Введите ключ:");
gets(s);
while((k = atoi(s)) < 0)
{
printf("%s\n","Ключ должен быть >0 и <32767");
printf("%s\n","Введите новый ключ:");
gets(s);
}
// Исполнение алгоритма S
data = alg_s(k);
// Вывод результатов
printf("Алгоритм S:\n");
if(data == NULL)
printf("Запись не найдена, i=%d\n",i+1);
else
printf("Запись: \"%s\", i=%d\n",data,i+1);
// Исполнение алгоритма Q
items[N].field = NULL; // фиктивная запись
data = alg_q(k);
// Вывод результатов
printf("Алгоритм Q:\n");
if(data == NULL)
printf("Запись не найдена, i=%d\n",i+1);
else
printf("Запись: \"%s\", i=%d\n",data,i+1);
// Исполнение алгоритма T
items[N].k = 32767; // Вставка Kn = ∞
items[N].field = NULL;
data = alg_t(k);
// Вывод результатов
printf("Алгоритм T:\n");
if(data == NULL)
printf("Запись не найдена, i=%d\n",i+1);
else
printf("Запись: \"%s\", i=%d\n",data,i+1);
// Освобождение памяти
for(i=0;i<N;i++)
free(items[i].field);
}
// Алгоритм S
void * alg_s(int key)
{
// Шаг 1. Начальная установка
i=0;
do
{
// Шаг 2. Сравнение
if(key == items[i].k)
return items[i].field;
// Шаг 3. Продвижение
i++;
}
// Шаг 4. Завершение
while(i<N);
return NULL;
}
// Алгоритм Q
void * alg_q(int key)
{
// Шаг 1. Начальная установка
i = 0;
items[N].k = k; // вставка Kn = K
// Шаг 2. Сравнение
while(!(key == items[i].k))
// Шаг 3. Продвижение
i++;
// Шаг 4. Завершение
if(i<N)
return items[i].field;
return NULL;
}
// Алгоритм T
void * alg_t(int key)
{
// Шаг 1. Начальная установка
i = 0;
// Шаг 2. Сравнение
while(!(key < items[i].k))
// Шаг 3. Продвижение
i++;
