Цикл жизни программного обеспечения

Цикл жизни программного обеспечения

Одним из базовых понятий методологии проектирования информационных систем (ИС) является понятие жизненного цикла ее программного обеспечения, что представляет собой непрерывный процесс, который начинается с момента принятия решения о необходимости его создания и заканчивается в момент его полного изъятия из эксплуатации. Основным нормативным документом [1], регламентирующим жизненный цикл ПО, является международный стандарт ISO/IEC 12207 (ISO - International Organization of Standardization - Международная организация по стандартизации, IEC - International Electrotechnical Commission - Международная комиссия по электротехнике). Он определяет структуру жизненного цикла, содержащую процессы, действия и задачи, которые должны быть выполнены во время создания программного обеспечения. Структура жизненного цикла по стандарту ISO/IEC 12207 базируется на трех группах процессов:

· основные процессы: приобретение, поставка, разработка, эксплуатация, сопровождение;

· вспомогательные процессы: документирование, управление конфигурацией,

· обеспечение качества, верификация, аттестация, оценка, аудит, решение проблем;

· организационные процессы (управление проектами, создание инфраструктуры проекта, определение, оценка и улучшение самого жизненного цикла, обучение).

Разработка включает в себя все работы по созданию ПО и его компонент в соответствии с заданными требованиями. Она включает оформление проектной и эксплуатационной документации, подготовку материалов, необходимых для проверки работоспособности и соответствующего качества программных продуктов, материалов, необходимых для организации обучения персонала и т.д. Разработка программного обеспечения включает в себя, как правило, анализ, проектирование и реализацию (программирование).

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

Управление проектом связано с вопросами планирования и организации работ, создания коллективов разработчиков, контроля за сроками и качеством выполняемых работ.

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

Обеспечение качества проекта связано с проблемами верификации, проверки и тестирования ПО. Верификация - это процесс определения того, отвечает ли текущее состояние разработки, достигнутое на данном этапе, требованиям этого этапа. Проверка позволяет оценить соответствие параметров разработки исходным требованиям. Проверка частично совпадает с тестированием, которое связано с идентификацией различий между действительными и ожидаемыми результатами и оценкой соответствия характеристик ПО исходным требованиям. В процессе реализации проекта важное место занимают вопросы идентификации, описания и контроля конфигурации отдельных компонентов и всей системы в целом.

Жизненный цикл программного обеспечения носит итерационный характер. Результаты очередного этапа часто вызывают изменения в проектных решениях, выработанных на более ранних этапах.

 

Показатели качества

 

Критерии качества программного обеспечения [2] представляют собой измеряемые численные показатели в виде показателей целевой функции, характеризующие степень выполнения программами своего назначения. Принципиальной особенностью требований качества комплекса программ является невозможность выделения единственного критерия качества. В ходе анализа выделяется приоритетный критерий, удовлетворяющий следующим требованиям:

 

· он должен численно характеризовать степень выполнения основной целевой функции системы наиболее важной для этапа анализа программного обеспечения;

· критерий должен обеспечивать возможность определения затрат, необходимых для достижения его значений, а также степени влияния на показатель качества различных внешних факторов и параметров;

· он должен быть по возможности простым по содержанию, хорошо измеряемым и слабо зависеть от множества неконтролируемых факторов.

 

Наиболее широко в информационных системах применяются экономические критерии. Эти критерии представляют собой эффективность в виде повышения производительности труда, снижения потребления, увеличения объема выполнения работ, качества, надежности и т.д. Выделение и измерение показателей характеризующих качество программ необходимо, прежде всего, для целевого управления разработкой ПО. Показатели качества подлежат измерению и численной оценке, для чего осуществляется их формализация вводом так называемых метрик. Применение метрик (числовых оценок параметров) к комплексам программ позволяет упорядочить их разработку, испытания, эксплуатацию и сопровождение. Качество ПО при этом может оцениваться количественно. На практике применяют следующие виды метрик и шкал для измерения показателей:

 

· первый вид числовых параметров - метрик характеризуется относительными величинами или реально измеряемыми физическими показателями, например временем наработки на отказ, вероятностью ошибки, числом маршрутов в программе и т.д.

· второй вид метрик - порядковая шкала позволяет ранжировать некоторые характеристики путем сравнения с опорными значениями. При этом устанавливается приоритетность признаков.

· третий вид метрик (категорийная шкала) характеризует только наличие рассматриваемого свойства или признака у объекта. Фиксируется есть или нет данное качество в зависимости от наличия рассматриваемого показателя у комплекса программ (например, наличие структурирования, гибкости, простоты освоения и т.д.).

 

Реальные значения показателей качества могут поэтапно уточняться в процессе создания и эксплуатации программ. На первом этапе формирования технического задания и спецификаций на ПО выявляются доминирующие показатели, устанавливается относительная важность каждого из показателей и строится обобщенная функция качества.

По мере создания комплекса программ после завершения отладки и проведения испытаний уточняется достигнутое реальное значение каждого из показателей и обобщенной функции качества всего комплекса. Показатели качества могут определяться в процессе эксплуатации, в результате чего обеспечивается долгосрочная перспектива объективного измерения и повышения качества программ. В течение жизненного цикла ПО возможно изменение удельного веса и роли анализируемых критериев. На каждом этапе жизненного цикла можно выделить важнейший доминирующий критерий качества и основные потребляемые ресурсы, которые значительно отличаются от соответствующих показателей на других этапах. Существует несколько моделей выборок критериев качества и их связей с различными факторами. Анализ качества ПО проводится с использованием деления критериев качества на функциональные и конструктивные. Выделены также факторы, влияющие на основные показатели, которые иногда рассматриваются как частные критерии качества программ.

Функциональные критерии отражают основную специфику применения и степень соответствия программ их целевому назначению. Для программ управления в них входят показатели точности выходных данных, диапазон изменения параметров, время реакции, адаптивность к внешним воздействиям и т.д. В системах обработки информации функциональные показатели отражают номенклатуру исходных данных, достоверность результатов, разнообразие функций редактирования и др. При анализе и выборе функциональных критериев качества необходимо учитывать совокупную эффективность комплекса программ на всем жизненном цикле программного обеспечения с учетом затрат на проектирование, эксплуатацию и сопровождение.

Конструктивные критерии качества ПО более или менее инвариантны (независимы) к их целевому назначению и основным функциям. К ним относятся сложность программ, надежность функционирования, используемые ресурсы ЭВМ и т.д.

 

 

Таблица 2.1. Критерии качества и определяющие их факторы

Проектирование	Эксплуатация	Сопровождение
ОСНОВНЫЕ КРИТЕРИИ КАЧЕСТВА КОМПЛЕКСА ПРОГРАММ
1. Сложность создания ПО	1. Функциональная сложность ПО	1. Способность к модернизации программ
2. Корректность программ	2. Надежность функционирования	2. Мобильность программ относительно типов ЭВМ
3. Трудоемкость разработки ПО	3. Эффективность использования ресурсов	3. Трудоемкость обучения и модернизации ПО
	4. Объем исходных и результирующих данных
ОСНОВНЫЕ ФАКТОРЫ, ОПРЕДЕЛЯЮЩИЕ КАЧЕСТВО
1. Структурная упорядоченность программ и данных	1. Корректность постановки задачи		1. Структурная упорядоченность комплекса программ и данных
2. Степень стандартизации структуры модулей и переменных	2. Полнота и точность спецификаций		2. Степень стандартизации структуры модулей и переменных
3. Документированность компонент и комплекса	3. Уровень языков программирования		3. Документированность для модификаций
4. Методическая обеспеченность технологии проектирования	4. Полнота тестирования программ		4. Уровень языков программирования
5. Степень комплексной автоматизации технологии проектирования	5. Степень помехозащищенности программ		5. Степень комплексной автоматизации технологии проектирования
6. Уровень языков спецификаций, программирования и отладки	6. Документированность для эксплуатации		6. Обеспеченность контроля изменений версий и распространения копий
7. Квалификация специалистов и методы организации работ

 

 

Выделенные факторы, определяющие качество проектирования программ, можно разделить на группы структурного проектирования (п. 1-3), технологического обеспечения (п. 4-6) и организационно- человеческие факторы (п. 7). В заключение следует особо выделить временные показатели жизненного цикла ПО:

 

· длительность проектирования;

· продолжительность эксплуатации очередной версии и длительность проведения каждой модификации.

 

Продолжительность проведения этих работ в ряде случаев может быть более важным критерием, чем трудоемкость. В некоторых случаях суммарная длительность эффективной эксплуатации является доминирующим критерием качества программ.

Рассмотрим управление качеством ПО. Такое управление включает:

 

· анализ системных требований к ПО и ранжирование показателей качества с выделением обязательных и желательных значений характеристик;

· разработку методик и стандартов контроля степени выполнения заданной технологии модульно-иерархического проектирования комплекса программ и его компонент;

· создание методов, средств, технологии объективного измерения и поэтапного контроля степени выполнения заданных требований к качеству программ;

· создание средств инструментальной технологической поддержки автоматизации программирования, отладки, испытаний, обеспечивающих создание комплекса программ с заданными показателями качества;

· организацию коллектива специалистов и организацию процесса проектирования с целевой задачей максимального удовлетворения требований заказчика к качеству комплекса программ.

 

Управление качеством можно разделить на подготовительную фазу и фазу активного контроля и управления. На подготовительной фазе разрабатываются стандарты, методы и средства, потенциально способствующие созданию комплекса программ с заданными характеристиками качества. Выбор и подготовка технологии проектирования в значительной мере определяют последующее качество программ.

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

 

Критерии надежности

 

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

Вероятностью безотказной работы P (t) называется вероятность того, что при заданных условиях эксплуатации в течени интервала времени t не возникнет отказ.

Вероятностью отказа Q (t) = 1 - P (t) является вероятность того, что в течение заданного времени произойдет хотя бы один отказ.

Интегральным критерием является интенсивность отказов (t), которая характеризует плотность распределения наработки до первого отказа, рассчитанную при условии, что до рассмотренного момента времени система проработала безотказно:

 

                             (t) =  , t  0.

 

Для оценки надежности восстанавливаемых систем используют характеристики: H(t) - среднее количество отказов за время t; Т (t) - наработка на отказ

                                   Т (t) = .

Процесс восстановления достаточно полно описывается показателями: вероятностью восстановления за время t, плотностью распределения времени восстановления и средним временем восстановления. Кроме того, используются показатели среднего числа восстановлений за некоторое время и параметр потока восстановлений. В перечисленных показателях процессы отказов и восстановлений могут рассматриваться как независимые. Объединение характеристик отказов и восстановлений производится в критерий - коэффициент готовности K (t). Этот показатель характеризует вероятность застать в заданный момент времени восстанавливаемую систему в работоспособном состоянии. Значение коэффициента готовности соответствует доле времени полезной работы системы на достаточно большом интервале, содержащем отказы и восстановления.

 

Сбой, отказ, восстановление

 

Чтобы глубже понять проблемы надежности функционирования комплексов программ остановимся на уточнении фундаментальных понятий, таких как сбой, отказ, восстановление.

Отказ при функционировании комплекса программ может проявляться как следствие нарушения кодов записи программ в памяти команд, стирания или искажения данных в оперативной или долговременной памяти ЭВМ, нарушения нормального хода вычислительного процесса. Отказ может проявляться в виде программного останова или зацикливания, систематического пропуска исполнения некоторой группы программ, однократного или систематического искажения накопленных данных и т.д. Первопричиной нарушения работоспособности программ при безотказности вычислительных средств, всегда является конфликт между реальными исходными данными, подлежащими обработке, и программой, осуществляющей эту обработку. При этом под исходными данными понимается вновь поступившие сообщения или вся информация, накопленная за время предыдущего функционирования программ.

Сбой - это самоустраняющийся отказ, не требующий внешнего вмешательства. Основным принципом классификации сбоев и отказов в программе является разделение по временному показателю длительности восстановления после любого искажения программ, данных или вычислительного процесса, регистрируемого как нарушение работоспособности. При длительности восстановления меньшей порога, аномалии при функционировании программ следует относить к сбоям, а при восстановлении, превышающем по длительности пороговое значение, происходящие искажения соответствуют отказу.

Сделаем следующее важное замечание. Между понятиями правильная и надежная программа отсутствует тождественность. Понятие правильной или корректной программы может рассматриваться статически вне временного функционирования. Корректная программа должна обеспечивать выходные данные соответствующие эталонным в области изменения исходных данных, заданных требованиями технического задания или спецификации. Надежная программа, прежде всего, должна обеспечивать низкую вероятность отказа в процессе функционирования. Быстрое реагирование на искажение программ, данных или вычислительного процесса и восстановление работоспособности за время меньшее, чем порог, позволяют обеспечить высокую надежность программ. При этом некорректная программа может функционировать в принципе абсолютно надежно.

Для решения задачи восстановления в комплексе программ должны быть средства, позволяющие:

 

· проводить систематический контроль и оперативно обнаруживать аномалии процесса функционирования или состояния программ и данных;

· диагностировать обнаруженные искажения;

· вырабатывать решения и выбирать методы и средства восстановления;

· реализовывать оперативное восстановление нормальной работоспособности;

· регистрировать каждый сбой или отказ и обобщать с данными предыдущих искажений для выявления систематических случаев, требующих доработки программ или аппаратуры.

 

Таблица 2.3.

Факторы, определяющие надежность программ	Методы проектирования корректных программ	Методы контроля
Особенности внешних абонентов и пользователей:   · требования к показателям надежности; · инерционность внешних абонентов; · необходимое время отклика на входные данные.   Искажения исходных данных: · искажения данных, поступающих от человека; · искажение данных, поступающих по телекодовым каналам связи; · искажение данных в процессе накопления и хранения в ЭВМ.   Ошибки в программах и их проявление:   · статистические характеристики ошибок и искажений: · программ; · массивов данных; · вычислительного процесса.	Структурное проектирование программ и данных:   · структурное проектирование программных модулей; · структурное проектирование взаимодействия модулей; · структурирование данных   Тестирование программ:   · детерминированное тестирование; · статистическое тестирование; · динамическое тестирование и контроль пропускной способности в реальном времени.	Методы использования  избыточности: · временной; · информационной; · программной.   Методы контроля программ, данных и вычислительного процесса: · предпусковой контроль; · оперативный контроль. Методы программного восстановления: · восстановление текстов программ; · исправление данных; · корректировка вычислительного процесса. Методы испытаний на  надежность: · испытания в нормальных условиях эксплуатации; · форсированные испытания; · расчетно-экспериментальные методы определения надежности. Методы обеспечения надежности при сопровождении: · обеспечение сохранности программ эталонных версий; · обеспечение корректности внесения изменений и развитии версий.

Алгоритмы сортировки

Введение

 

Почти во всех машинных приложениях множество объектов должно быть размещено в соответствии с некоторым заранее определенным порядком. Например, расположить данные по алфавиту или по возрастанию номеров.

Пусть имена x ₁, …, x_n заданы в виде таблицы. Каждое имя x_i принимает значение из пространства имен, на котором определен линейный порядок. Далее мы считаем, что никакие 2 имени не имеют одинаковых значений, т.е. любые x_i, x_j обладают тем свойством, что если i ¹ j, то либо x_i предшествует x_j, либо наоборот [3].

Ограничение x_i ¹ x_j при i ¹ j упрощает анализ без потери общности, т.е. корректность идей и алгоритмов не нарушается. Цель сортировки состоит в том, чтобы выполнить перестановку , для которой .

В задачах частичной сортировки требуется извлечь либо частичную информацию о П (например, p_i для нескольких значений i), либо полностью определить П по заданной частичной информации о ней (так обстоит дело при слиянии двух упорядоченных таблиц).С каждой записью x_i в последовательности x ₁, …, x_n сопоставим некоторый ключ ‘ k ’. Ключом обычно является некоторое поле внутри записи. Говорят, что файл отсортирован по ключу, если для i < j следует, что k_i предшествует k_j при некоторой упорядоченной последовательности по ключам. В качестве примера рассмотрим телефонный справочник. Файл состоит из всех строчек этого справочника. Каждая строчка является записью. Ключом, по которому отсортирован этот файл, является поле фамилия в записи. Каждая запись содержит также поле для адреса и номера телефона.

Сортировка может быть классифицирована как внутренняя, если записи, которые сортируются, находятся в оперативной памяти, или как внешняя, если некоторые из записей, которые сортируются, находятся во вспомогательной внешней памяти.

Вполне возможно, что две записи в некотором файле имеют одинаковый ключ. Метод сортировки называется устойчивым, если для всех записей i и j таких, что k (i) = k (j), выполняется условие, что в отсортированном файле x_i предшествует x_j, если x_i предшествует x_j в первоначальном файле.

Сортировка выполняется или над самими записями или над указателями этих записей, которые содержатся во вспомогательной таблице.

 

Пример.

а) первоначальный файл               б) отсортированный файл

 

ключ	информация		ключ	информация
4	DDD		1	AAA
2	BBB		2	BBB
1	AAA		3	CCC
5	EEE		4	DDD
3	CCC		5	EEE

                                                              

Рис. 3.1. Сортировка записей

 

 

Предположим, что объем данных, помещенных в каждую из записей файла, такой большой, что перемещение самих записей является нецелесообразным. В этом случае может быть использована вспомогательная

 

Рис. 3.2. Сортировка, использующая вспомогательную таблицу указателей

 

 таблица указателей, так что вместо перемещения самих данных перемещаются эти указатели. Это называется сортировкой таблицы адресов.

 

Из-за взаимосвязи между сортировкой и поиском первым вопросом, который стоит, является вопрос о необходимости сортировки. Иногда при непосредственном поиске конкретного элемента в некотором множестве элементов затрачивается меньше работы, чем при сортировке данного множества и извлечении из него после сортировки необходимого элемента. С другой стороны, если в целях извлечения конкретных элементов требуется частое использование данного файла, то сортировка целесообразна. Она дает эффективность за счет того, что расходы (ресурсы, время) на следующие один за другим поиски могут существенно превысить расходы на выполнение разовой сортировки файла и последующего извлечения элементов из него. Программист должен принять соответствующее решение — выполнять сортировку или нет. Кроме того, программист помимо решения, что сортировать, должен выбрать как сортировать, т.е. метод сортировки. В настоящее время не существует метода сортировки, который бы во всем превосходил остальные.

 

Внутренняя сортировка

 

Существует, по крайней мере, пять широко известных способов, применяемых в алгоритмах внутренней сортировки.

1. Вставка. На i -м этапе i -е имя помещается на надлежащее место c i -1 уже отсортированными именами.

2. Обмен. Два имени, расположение которых не соответствует порядку, меняются местами (обмен). Эта процедура повторяется, пока существуют такие пары.

3. Выбор. На i -м этапе из неотсортированных имен выбирается i -е наибольшее (наименьшее) имя и помещается на соответствующее место.

4. Распределение. Имена распределяются по группам, и содержимое групп затем объединяется таким образом, чтобы частично отсортировать таблицу; процесс повторяется до тех пор, пока таблица не будет отсортирована полностью.

5. Слияние. Таблица делится на подтаблицы, которые сортируются по отдельности и затем сливаются в одну.

Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающими. Они

удобны для классификации алгоритмов сортировки. В рассматриваемых алгоритмах имена образуют последовательность x ₁, …, x_n. Значением x_i является любое текущее имя i позиции последовательности. В каждом из рассматриваемых алгоритмов будем считать, что имена нужно сортировать на месте, т.е. перемещение имен должно происходить внутри последовательности x ₁, …, x_n. При этом существует одна или две дополнительные ячейки, в которых временно размещается значение имени.

Ограничение «сортировка на месте» основано на предположении, что число имен настолько велико, что во время сортировки не допускается перенос их в другую область памяти.

 

3.3. Сравнение эффективности алгоритмов сортировки

Чтобы получить некоторое представление об ожидаемой эффективности, рассмотрим задачу сортировки с теоретической точки зрения.

Один из способов оценки эффективности алгоритмов сортировки состоит в подсчете числа сравнений имен ‘ x_i: x_j ’ за время сортировки. Эта характеристика не всегда является определяющей, но для большинства алгоритмов она является хорошей мерой производимой работы. Будем рассматривать алгоритмы, основанные на абстрактном линейном упорядочении пространства имен: для любой пары имен x_i, x_j при i ¹ j либо x_i < x_j, либо x_i > x_j.

Любой такой алгоритм можно представить в виде расширенного бинарного дерева решений, в котором каждый внутренний узел соответствует сравнению имен, и каждый лист (внешний узел) — исходу алгоритма. Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором все циклы «размотаны» и показаны только сравнения имен.

Пример. Рассмотрим сортировку элементов массива { x ₁, x ₂, x ₃ } с использованием бинарного дерева.

Рис. 3.3. Бинарное дерево решений для сортировки трех имен

В любом таком дереве решений каждая перестановка определяет единственный путь от корня к листу. Листья, соответствующие разным перестановкам, должны быть разными. Тогда ясно, что в дереве решений для сортировки n имен должно быть по крайней мере n! листьев (n! — количество перестановок из n).

Заметим, что высота дерева решений h равна числу сравнений, требующихся алгоритму в наихудшем случае.

Поскольку бинарное дерево высоты h может иметь не больше 2 ^h листьев, заключаем что

  т.к.

Таким образом, любой алгоритм сортировки, основанный на сравнении имен, в наихудшем случае потребует не меньше n lg nсравнений.

Длина внешних путей дерева решений равна сумме всех расстояний от корня до листьев, деление ее на n! дает среднее число сравнений для соответствующего алгоритма.

 

 

Поиск данных

Введение в поиск данных

 

В программировании поиск является общеизвестной задачей в связи с часто возникающей проблемой поиска некоторой единицы информации в большом объеме данных. Прежде чем рассматривать конкретные методы поиска, определим некоторые термины.

Таблица или файл является некоторой группой элементов, каждый из которых представляется записью. С каждой записью ассоциируется некоторый ключ, который используется для того, чтобы отличить одну запись от другой. Соответствие между записью и ключом может быть простым или сложным. В простейшем случае ключ является некоторым полем внутри записи, располагающимся с некоторым конкретным сдвигом от начала записи. Такой ключ называется внутренним ключом или встроенным ключом. В других случаях ключом является относительная позиция записи внутри файла или имеется некоторая отдельная таблица ключей, которая содержит указатели на записи. Такие ключи называются внешними ключами. Для каждого файла имеется по крайней мере один набор ключей (возможно и несколько таких наборов), которые являются уникальными (т.е. никакие две записи в файле не имеют одинакового значения ключа). Такой ключ называется первичным ключом. Например, если файл хранится как некоторый массив, то индекс некоторого элемента в этом массиве является уникальным внешним ключом для этого элемента. Однако поскольку любое поле записи может служить в качестве ключа в каком-либо конкретном приложении, то ключи не всегда должны быть уникальными.

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

Алгоритмом поиска является такой алгоритм, который, воспринимая некоторый аргумент a, пытается локализовать некоторую запись, ключ которой равен а. Данный алгоритм может возвратить всю данную запись или чаще всего может возвратить некоторый указатель на эту запись. Успешный поиск называется извлечением. В противном случае алгоритм может возвратить некоторую специальную «пустую запис ь» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или установке во флаге некоторого конкретного значения, которое указывает, что данная запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с этим аргументом в качестве ключа. Алгоритм, который выполняет эту функцию, называется алгоритмом поиска и вставки [3].

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

 

Последовательный поиск

 

Простейшей формой поиска является последовательный поиск. Этот поиск применяется к таблице, которая организована или как массив, или как связанный список [3].

Предположим, что k есть некоторый массив из n ключей, а r — некоторый массив записей, такой, что k (i) является ключом для r (i). Предположим также, что key является некоторым аргументом поиска. Мы хотим установить в переменную search наименьшее целое число i, такое что k (i) = key, если такое i существует, и 0 в противном случае. Алгоритм выполнения этих действий следующий:

 

search =0;

for (i =1; i <= n; i + +)

{

  if(key = = k[i]) search = i;

}

 

Этот алгоритм может быть просто модифицирован для того, чтобы добавлять некоторую запись rec с ключом key в таблицу, если ключ key не находится в таблице. Следующие операторы добавляются в приведенные выше:

 

if (search = = 0)

{

n ++;    // увеличиваем размер таблицы

k [ n ] = key // вставляем новый ключ и запись

r[n]= rec;

search = n;

}

 

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

 

// key — искомый ключ записи

…

flag=false;

qq=q;    // q — указатель на начало списка

i=0;      // n — число элементов в списке

while((flag==false) && (i<=n))

{

i++;

if (qq->key==key)

{

q1=q; // q1 — указатель на искомый элемент

cout<<”Запись найдена\n”;

flag=true;

}

else

{

    q2=qq; // q2 – указатель, ссылающийся.ся на qq

    qq=qq->next; 

}

 

// вставка элемента zapis с заданным ключом key в начало списка

 

if (flag==false)

{

  item *kon=new kon(next,key,nam); // kon - указатель на ячейку

  kon->next=q;

  kon->key=key;

  kon->nam=zapis;

  q=kon;

}

 

// удаление элемента с ключом key из списка

else

  {

         q2.next=q1.next;

        delete q1;

}

}