МИНОБРНАУКИ РОССИИ

САНКТ-ПЕТЕРБУРГСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ПЕТРА ВЕЛИКОГО

Институт энергетики и транспортных систем

Центр заочного обучения

Курсовая работа

на темы:Подбильский В.В. "Язык С++

Д.Кнут "Искусство программирования для ЭВМ " том 3"Сортировка и поиск"

Хеширование

по дисциплине: Информатика

Выполнил: студент гр. З13532/1 ________________/ Шпионов / (И. О. Фамилия)

Проверил: _________/Иванов / (И. О. Фамилия)

Санкт-Петербург

2017г.

Оглавление

Подбильский В.В. "Язык С++" 3

ОПЕРАТОРЫ ЯЗЫКА СИ++ 3

Операторы управления 3

СТРУКТУРЫ И ОБЪЕДИНЕНИЯ 6

Структуры данных С++ 6

Д. Кнут "Искусство программирования для ЭВМ " том 3 "Сортировка и поиск" 18

ПУЗЫРЬКОВАЯ СОРТИРОВКА 18

СОРТИРОВКА ВСТАВКАМИ 23

СОРТИРОВКА ШЕЛЛА 25

БЫСТРАЯ СОРТИРОВКА 28

Хеширование 31

Определение хэша и его вычисление 31

Пример задачи. Поиск одинаковых строк 32

Хэш подстроки и его быстрое вычисление 33

Применение хэширования 34

Определение количества различных подстрок 34

Подбильский В.В. "Язык С++"

ОПЕРАТОРЫ ЯЗЫКА СИ++

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

Операторы управления

К операторам передачи управления относят оператор безусловного перехода, иначе - оператор безусловной передачи управления (go to), оператор возврата из функции (return), оператор выхода из цикла или переключателя (break) и оператор перехода к следующей итерации цикла (continue).

Оператор безусловного перехода имеет вид:

Go to идентификатор;

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

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

gо to B;                    // Ошибочный переход, минуя описание float х = 0.0;            // Инициализация не будет выполнена go to B;                   // Допустимый переход, минуя блок { int n = 10;             // Внутри блока определена переменная х = n * х + х; } В: соut << "\tx = " << х;

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

{ ... // Внешний блок gо tо AВС; // Во внутренний блок, минуя описание ii ... { int ii = 15; // Внутренний блок ... AВС: ... gо tо ХУZ; // Обход описания СС сhаг СС = ' '; ... ХУZ: ... } ... }

Принятая в настоящее время дисциплина программирования рекомендует либо вовсе отказаться от оператора gо tо, либо свести его применение к минимуму и строго придерживаться следующих рекомендаций:

• не входить внутрь блока извне;

• не входить внутрь условного оператора, т.е. не передавать управление операторам, размещенным после служебных слов if или еlsе;

• не входить извне внутрь переключателя (switch);

• не передавать управление внутрь цикла.

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

Оператор возврата из функции имеет вид:

return выражение; или просто return;

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

float cube(float х)       {return z * z * z;}

Выражение в операторе rеturn не может присутствовать в том случае, если возвращаемое функцией значение имеет тип void. Например, следующая функция выводит на экран дисплея, связанный с потоком cout, значение третьей степени своего аргумента и не возвращает в точку вызова никакого значения:

void cube_print (float z) } cout << "\t сubе = " << z * z * z; return; }

В данном примере оператор возврата из функции не содержит выражения.

Оператор brеаk служит для принудительного выхода из цикла или переключателя. Определение "принудительный" подчеркивает безусловность перехода. Например, в случае цикла не проверяются и не учитываются условия дальнейшего продолжения итераций. Оператор break. прекращает выполнение оператора цикла или переключателя и осуществляет передачу управления (переход) к следующему за циклом или переключателем оператору. При этом в отличие от перехода с помощью goto оператор, к которому выполняется передача управления, не должен быть помечен. Оператор break нельзя использовать нигде, кроме циклов и переключателей.

Необходимость в использовании оператора brеаk в теле цикла возникает, когда условия продолжения итераций нужно проверять не в начале итерации (циклы fог, whi1е), не в конце итерации (цикл dо), а в середине тела цикла. В этом случае тело цикла может иметь такую структуру:

{операторы if (условие) brеаk; операторы}

Например, если начальные значения целых переменных i, j таковы, что i < j, то следующий цикл определяет наименьшее целое, не меньшее их среднего арифметического:

while (i < j) {i++; if (i == j) brеаk; j - -; }

Для i == 0, j == 3 результат i == j == 2 достигается при выходе из цикла с помощью оператора brеаk. (Запись i == j == 2 не в тексте программы означает равенство значений переменных х, j и константы 2.) Для i == о, j == 2 результат i == j == 1 будет получен при естественном завершении цикла.

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

//Р4-04.СРР - оператор brеаk в переключателе #include < iostream. h > void main () { int iс; cout << "\n Введите восьмеричную цифру: "; cin >> iс; соut << "\n" << iс; switch (iс) { саsе 0: соut << " - нуль"; brеаk; case 1: соut << " - один"; brеаk; саsе 2: соut << " - два"; brеаk; саsе 3: соut << " - три"; brеаk; саsе 4: соut << " - четыре"; brеаk; саsе 5: соut << " - пять"; brеаk; саsе 6: соut << " - шесть"; brеаk; саsе 7: соut << " - семь"; brеаk; defaul t: соut << " - это не восьмеричная цифра!"; } соut << "\nКонец выполнения программы."; }

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

Циклы и переключатели могут быть многократно вложенными. Однако следует помнить, что оператор brеаk позволяет выйти только из самого внутреннего цикла или переключателя. Например, в следующей программе, которая в символьном массиве подсчитывает количество нулей (lс0) и единиц (0с1), в цикл вложен переключатель:

//Р4-05.СРР - brеаk при вложении переключателя в цикл #include < iostream.h > void main(void) { сhar с[] - "АВС100111"; int k0 = 0, k1 = 0; fоr (int i = 0; с[i]!= '\0'; i++) switch (с [i]) { саsе '0': k0++; brеаk; case '1': k1++; brеаk; default: brеаk; } соut << "\nВ строкe " << k0 << "нуля," << k1 << "единицы"; }