Лекция 2. Основные определения языка высокого уровня (стр. 17 )

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

long int Hash(char * s)

{
int i;

if (strlen(s)==0) return 0;
  else  return (s[1] % 26);
}

Эта хеш-функция неудачна по двум причинам. Во-первых, количество слов, начинающихся на разные буквы, существенно различается, т. е. не соблюдается основной принцип хеширования — перемешивание. Во-вторых, при хранении большого количества строк в хеш-таблице значения N=26 уже недостаточно. Более удачной является хеш-функция, учитывающая все символы строки, например, такая:

long int Hash(char * s)

{
int i;

long int Result=0;
  for (i=0;i<strlen(s);i++)
  Result:=(Result*17+s[i]) % N;

return Result;
}

Лекция 9. Модульное программирование. Файловые модули

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

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

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

Модульное программирование предполагает выделение групп подпрограмм, использующих одни и те же глобальные данные в отдельно компилируемые модули (библиотеки подпрограмм), например, модуль решения системы уравнений, модуль ввода и вывода (рис. 1.5). Связи между модулями при использовании данной технологии осуществляются через специальный интерфейс, в то время как доступ к реализации модуля (телам подпрограмм и «внутренним» переменным) запрещен. Эту технологию поддерживают современные версии языков Pascal и С (C++), языки Ада и Modula.

Рис. 1.5. Архитектура программы, состоящей из модулей

Основная причина, по которой разрабатываемое ПО разбивается на модули — борьба со сложностью ПО.

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

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

Пользователь модуля (программист) имеет доступ только к процедурам и через них управляет данными. То есть пользователь (программист) не имеет доступа к структурам данных модуля.

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

Например, для работы со стеком необходимо:

поместить в стек;

извлечь из стека.

Значит, интерфейс будет включать функции:

— помещения в стек Push;

— извлечения Pop.

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

Интерфейс следующий:

void Push(T a);

T Pop(void);

где T - тип элемента стека.

Принципы модульного программирования позволяют получать программные комплексы минимальной сложности. Эти принципы следующие:

а) усиление внутренних связей в каждом модуле (иначе принцип называется повышением прочности модуля);

б) ослабление взаимосвязи между модулями (иначе этот принцип называется ослаблением сцепления модулей).

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

Для качественной характеристики модулей введены 7 классов прочности (связности) модулей и 5 видов сцепления модулей.

Класс прочности является мерой связи предложений внутри модуля.

Сцепление модулей – это мера зависимости между модулями.

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

Практика показала, что чем выше степень независимости модулей, тем

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

— меньше вероятность появления новых ошибок при исправлении старых или внесении изменений в программу, т. е. вероятность появления “волнового” эффекта;

— проще организовать разработку программного обеспечения группой программистов, легче управлять процессом разработки и сопровождать такое ПО.

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

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

A. cpp A. h iostream. h B. h B. cpp

 

Препроцессор

 

A. tmp B. tmp

Компилятор

Стандартные библиотеки

a. obj b. obj afx. lib io. lib....

A. exe

Скрытие деталей реализации называется инкапсуляцией. Инкапсуляция - основная идея модульного и объектно-ориентированного программирования.

Модульность в языке c++ поддерживается с помощью директив препроцессора, пространств имен, классов памяти, исключений и раздельной компиляции.

Препроцессор

Препроцессор - первая фаза компилятора. Инструкции препроцессора называются директивами.

Директивы препроцессора представляют собой инструкции, записанные в тексте программы на СИ, и выполняемые до трансляции программы. Директивы препроцессора позволяют изменить текст программы, например, заменить некоторые лексемы в тексте, вставить текст из другого файла, запретить трансляцию части текста и т. п. Все директивы препроцессора начинаются со знака #. После директив препроцессора точка с запятой не ставятся.

#include "имя файла"

#include <имя файла>

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

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

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

Директива #include является простейшим средством обеспечения согласованности объявлений в различных файлах, она включает в них информацию об интерфейсе из заголовочных файлов. Заголовочные файлы обычно имеют расширение *.h и могут содержать:

— определения типов, встроенных функций, шаблонов, перечислений;

— объявления функций, данных, констант, имен, шаблонов;