Лекція 6. Керуючі структури

1. Різновиди керуючих структур

Визначають, які операнди необхідно виконувати і в якому порядку. Інакше визначають потік управління у програмі. Як зазначалось, Бьом та Яконіні показали, що будь-який алгоритм може бути реалізований за допомогою трьох керуючих структур:

1.         послідовне виконання; 

2.            умовне виконання;

3.         цикл.

У мові С  будь-який вираз стає оператором, якщо за ним поставити; наприклад: a = 0; i++; printf (“%d\n”, x);

Послідовність операторів, обмежена { } є складеним оператором, або блоком. При цьому після правої дужки ; не вживається.

2. Умовний оператор if

Умовний оператор if має вигляд:

if (вираз) оператор 1; else оператор2;

3. Перемикач switch

Перемикач switch. У тих випадках, коли виникає вибір з багатьма можливими результатами, доцільно використовувати перемикач.

Цикл с передумовою while. 

Оператор має структуру:

while (умова) оператор;

Виконується доти , поки умова є істиною. Ясно, що замість одного оператора може бути складений оператор або блок.

Якщо необхідно перервати цикл до його завершення, то можна використовувати оператор break.

Цикл с післяумовою do-while

Якщо оператори циклу повинні виконуватися принаймні один раз, то можна використовувати інший варіант do оператор while (условие);

do { оператор} while (умова).

Оператор циклу for

Має вигляд: 

for (вираз 1; вираз 2; вираз 3) оператор.

Швидке сортування Шела (1959)

Масив розбивається на групи, кожна з яких складається із двох елементів. Відстань між парами елементів d=n/2, де n - кількість елементів масиву. Елементи- Пари рівняються між собою і якщо потрібно, то міняються місцями. Потім групи попарно зливаються. Кожна нова група має 4 елемента, відстань між елементами d=d/2. У середині групи виконується сортування, потім групи зливаються. Процес триває доти , поки відстань між елементами не стане 1. На цьому етапі масив сортується методом вставки (пухирця).

Конструкції gap/=2 і j/=gap значить відповідно gap=gap/2 і j=j-gap. Зовнішній цикл змінює зрушення між парою елементів, які рівняються, від n/2, n/4 до 1. Наступний внутрішній цикл забезпечує перегляд масиву, починаючи з n/2, n/4 і 1- го до кінця.

Третій цикл (по j) до деякої міри є фіктивним: у ньому для певної пари для випадку, коли перший елемент більше другого, вони переставляються. Після цього j-=gap, тобто стає менше нуля й відбувається вихід із циклу.

Іноді в циклі for можна відразу використовувати два індекси. У цьому випадку одне вираз поєднує два за допомогою оператора ",": вираз 1, вираз 2. Кома розділяє два вирази, які виконуються зліва направо. Значення й тип операнду визначається правим виразом. Лівий вираз є ніби другорядним.

4. Цикл с передумовою while

Цикл с передумовою while має вигляд. 

Оператор має структуру:

while (умова) оператор;

Виконується доти , поки умова є істиною. Ясно, що замість одного оператора може бути складений оператор або блок.

Якщо необхідно перервати цикл до його завершення, то можна використовувати оператор break.

5. Цикл с післяумовою do-while

Цикл с післяумовою do-while має вигляд

6. Оператори циклу виконується принаймні один раз

Якщо оператори циклу повинні виконуватися принаймні один раз, то можна використовувати інший варіант do оператор while (условие);

do { оператор} while (умова).

Оператор циклу for

Має вигляд: 

for (вираз 1; вираз 2; вираз 3) оператор.

7. Швидке сортування

Швидке сортування Шела (1959)

Масив розбивається на групи, кожна з яких складається із двох елементів. Відстань між парами елементів d=n/2, де n - кількість елементів масиву. Елементи- Пари рівняються між собою і якщо потрібно, то міняються місцями. Потім групи попарно зливаються. Кожна нова група має 4 елемента, відстань між елементами d=d/2. У середині групи виконується сортування, потім групи зливаються. Процес триває доти , поки відстань між елементами не стане 1. На цьому етапі масив сортується методом вставки (пухирця).

Конструкції gap/=2 і j/=gap значить відповідно gap=gap/2 і j=j-gap. Зовнішній цикл змінює зрушення між парою елементів, які рівняються, від n/2, n/4 до 1. Наступний внутрішній цикл забезпечує перегляд масиву, починаючи з n/2, n/4 і 1- го до кінця.

Третій цикл (по j) до деякої міри є фіктивним: у ньому для певної пари для випадку, коли перший елемент більше другого, вони переставляються. Після цього j-=gap, тобто стає менше нуля й відбувається вихід із циклу.

Іноді в циклі for можна відразу використовувати два індекси. У цьому випадку одне вираз поєднує два за допомогою оператора ",": вираз 1, вираз 2. Кома розділяє два вирази, які виконуються зліва направо. Значення й тип операнду визначається правим виразом. Лівий вираз є ніби другорядним.