Лабораторна робота №20. Тема: Покажчики

Мета: Навчитися працювати із покажчиками.

Хід роботи

У програмі Операції & і * над вказівником показано виконання операцій над покажчиками. Специфікатор формату % р функції рrintf виводить вміст елементу пам'яті як шістнадцятиричне ціле число (детальніше відносно шістнадцятиричних цілих чисел див. додаток Д, "Системи числення"). Зверніть увагу на те, що адреса змінної а і значення аPtr при виводі співпадають, з чого можна зробити висновок, що адреса змінної а дійсно присвоєний змінній-покажчику аРtr. Операції & і * взаємно доповнюють один одного, і коли вони обоє застосовуються послідовно до аРtr, то порядок їх дотримання ролі не грає - результат буде тим же. В таблиці 2 показані відомі нам на даний момент операції, їх пріоритет і асоціативність.

Таблиця 2

Старшинство операцій

Операції	Асоціативність	Опис
( ) [ ]	зліва направо	вищий пріоритет
+ - + + -- ! * & (тип)	справа наліво	унарні
* / %	зліва направо	мультиплікативні
+ -	зліва направо	аддитивні
< <= > >=	зліва направо	стосунки
= = !=	зліва направо	порівняння
&&	зліва направо	логічне І
| |	зліва направо	логічне АБО
?:	справа наліво	умовна
= += -= *= /= % =	справа наліво	привласнення
,	зліва направо	кома

1. Напишіть дану програму, проаналізуйте її. Присвойте значенню а свій номер за списком.

/* Використання операцій & і * */

#іпсlude <stdio.h>

main ()

{

int a; /* a - змінна цілого типу */

int *aPtr; /* aPtr - покажчик на ціле */

a = 7;

aPtr = &a; /* Покажчику aPtr привласнюється адреса змінної a */

printf("The address of a is %p\n"

"The value of aPtr is %p\n\n", &a, aPtr);

printf("The value of a is %d\n"

"The value of *aPtr is %d\n\n", a, *aPtr);

printf("Proving that * and & are complements of each oter. "

"\n&*aPtr = %p\n*&aPtr = %p\n"

&*aPtr, *&aPtr);

return 0;

}

The address of a is FFF4

The value of aPtr is FFF4

The value of a is 7

The value of *aPtr is 7

Proving that * and & are complements of eachr oter.

&*aPtr = FFF4

*&aPtr = FFF4

Операції & і * над вказівником

2. Напишіть дану програму, проаналізуйте її. Присвойте значенню int number свій номер за списком.

Програми що нижче, є два варіанти функції, що обчислює куб цілого числа - cubeByValue і cubeByReference. Програма на лістингу 7.6 передає змінну number функції cubeByValue за значенням. У функції cubeByValue обчислюється третя міра аргументу функції, і набутого значення повертається у функцію main за допомогою оператора return. Потім це нове значення привласнюється змінній number у функції main.

/* Обчислення куба числа з використанням виклику за значенням */

#include <stdio.h>

int cubeByValue (int);

main ()

{

int number = 5;

printf("The original value of number is %d\n", number);

number = cubeByValue(number);

printf("The new value of number is %d\n", number);

return 0;

int cubeByValue(int n)

{

return n * n * n; /* підносимо в куб локальну змінну n */

}

The original value of number is 5

The new value of number is 125

3. Напишіть дану програму, проаналізуйте її. Присвойте значенню int number свій номер за списком.

Обчислення куба змінною з викликом за значенням

/* Обчислення куба змінною за допомогою виклику по посиланню */

#include <stdio.h>

void cubeByReference (int *);

main ( )

{

int number = 5;

printf ("The original value of number is %d\n", number);

cubeByReference(&number);

printf("The new value of number is %d\n", number);

return 0;

}

void cubeByReference(int *nPtr)

{

**nPtr = *nPtr * *nPtr * *nPtr; /* обчислення куба змінною

number функції main */

The original value of number is 5

The new value of number is 125

Обчислення куба змінною з викликом по посиланню

4. Прочитайте теоретичні положення. Напишіть програму, на лістингу 7.10. проаналізуйте її. Змініть значення *s -= 32 на ваш номер за списком.

У програмі Обчислення куба змінною з викликом по посиланню, змінна number передається по посиланню, тобто функція cubeByReference отримує адресу number. Функція cubeByReference поміщає цю адресу у свій параметр nPtr, змінну-покажчик на ціле. Далі функція разыменовывает покажчик і обчислює кубічне значення числа, на яке вказує nPtr. В результаті значення змінної number у функції main змінюється. На малюнку в лекції (7.8 і 7.9) графічно зображені етапи виконання програм, приведених відповідно у програмах Обчислення куба змінною з викликом за значенням і Обчислення куба змінною з викликом по посиланню

Функція, одержуюча як аргумент адресу, повинна мати відповідний параметр-покажчик для розміщення адреси. Наприклад, заголовок функції cubeByReference має вигляд

void cubeByReference (int *nPtr)

Заголовок функції показує, що cubeByReference отримує як аргумент адресу цілої змінної, поміщає його в локальну змінну nPtr і не повертає значення.

Прототип функції cubeByReference містить в круглих дужках int *. Включати імена покажчиків, як і імена змінних інших типів, в прототипи функції необов'язково. Імена включаються як коментарі і ігноруються компілятором.

Якщо функція може отримати як аргумент одновимірний масив, то у функціональному заголовку і в прототипі функції відповідний параметр може бути визначений як покажчик. Компілятор не робить відмінності між функцією, що має параметром покажчик, і функцією, яка отримує як аргумент одновимірний масив. Проте зрозуміло, що функція повинна "знати", коли вона отримує масив і коли посилання на поодиноку змінну. Коли компілятор зустрічає одновимірний масив як параметр функції, заданий у формі int b[], компілятор перетворить цей параметр до виду int *b. Ці дві форми є взаємозамінними.

Найвищий рівень доступу надається не-константним покажчикам на не-константні дані. В цьому випадку дані можуть змінюватися через разыменование покажчика, а сам покажчик може змінюватися і посилатися на інші елементи даних. Оголошення покажчика - не константи на неконстантні дані не містить ключового слова const. Такий покажчик міг би використовуватися, наприклад, при передачі рядка як параметра функції, в якій використовуються арифметичні операції над покажчиком при обробці (і, можливо, зміні) кожного окремого символу в рядку. Функція convertToUppercase, приведена на лістингу 7.10, оголошує параметром покажчик - не константу на не-константні дані (char * s). Функція обробляє рядок s посимвольний, використовуючи арифметичні операції над покажчиком. Якщо символ знаходиться в діапазоні від а до z, то він перетвориться у відповідний символ верхнього регістра від А до Z за допомогою обчислень, заснованих на ASCII -кодах символів; інакше символ не змінюється і обробляється наступний символ в рядку. Помітимо, що усі символи верхнього регістра мають ASCII -код, рівний ASCII -коду відповідного символу нижнього регістра мінус 32. Далі ми представимо вам функцію toupper із стандартної бібліотеки С, використовувану для перетворення символів в символи верхнього регістра.

/* Перетворення символів нижнього регістра в символи верхнього */

/* регістра з використанням вказівника-не константи на дані, */

/* які можуть модифікуватися */

#include <stdio.h>

void convertToUppercase(char *);

main ( )

{

char string[] = "characters";

printf("The string before conversion is: %s\n", string);

convertToUppercase (string);

printf("The string after conversion is: %s\n", string);

return 0;

}

void convertToUppercase(char *s)

{

while (* s ! = '\0' ){

if (*s >= 'a' && *s <= 'z')

*s -= 32; /* Перетворення до верхнього регістра */

++s; /* збільшення s для переходу до наступного символу */

}

}

The string before conversion is: characters

The string after conversion is: CHARACTERS

Лістинг 7.10. Перетворення рядка до верхнього регістра з використанням не константного покажчика на не константні дані

5. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

Покажчик - не константа на дані-константи - це покажчик, який може змінюватися і посилатися на будь-який об'єкт даних відповідного типу, але елемент даних, на які він вказує, не може змінюватися. Такий покажчик міг би використовуватися для передачі масиву як аргументу функції, яка обробляє кожен елемент масиву і при цьому не змінює дані. Наприклад, приведена в програмі, що нижче функція printCharac - ters оголошує параметр s, типу const char *. Оголошення читається справа наліво, і звучить як "s - покажчик на символ-константу". У тілі функції для виведення символів рядка використовується цикл for, який завершується досягши кінця рядка. Після виведення чергового символу виробляється збільшення покажчика для переходу до наступного символу в рядку.

/* Посимвольне виведення рядка, що використовує */

/ * не-константний покажчик на константні дані * /

#include <stdio.h>

void printCharacters (const char *);

main ( )

{

char string [ ] = "print characters of a string";

printf ("The string is:\n");

printCharacters (string);

putchar ('\n');

return 0;

}

void printCharacters (const char *s)

{

for ( ; *s != ' \0' ; s++) /* цикл не ініціалізувався */

putchar(*s);

}

The string is:

print characters of a string

Посимвольне виведення рядка з використанням покажчика - не константи на константні дані

В програмі, Спроба змінити дані, використовуючи неконстантний покажчик на константні дані приведені повідомлення про помилки, які видає компілятор Borland C ++ - при спробі компілювати функцію, одержуючу покажчик - не константу на дані-константи і що намагається за допомогою покажчика змінити ці дані.

6. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її. Змініть значення *x = 100 на ваш номер за списком.

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

/* Спроба зміни даних за допомогою */

/* неконстантного покажчика на дані-константи */

#include <stdio.h>

void f (const int *);

main ( )

{

int y;

f(&y); /* функція f намагається виконати зміну даних */

return 0;

}

void f (const int *x)

{

*x = 100; /* не можна модифікувати об'єкт даних типу const */

}

Compiling FIG7_12.C:

Error FIG7_12.C 17: Cannot modify a const object

Warning FIG7_12.C 18: Parameter 'x' is never used

Спроба змінити дані, використовуючи неконстантний покажчик на константні дані

7. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

Програма що нижче, робить спробу змінити покажчик-константу. Покажчик ptr оголошений як int * const. Оголошення повинне читатися справа наліво і в даному випадку звучатиме як "ptr - покажчик-константа на ціле число". Покажчик ініціалізував адресою змінної х цілого типу. Програма намагається присвоїти покажчику ptr адресу, внаслідок чого видається повідомлення про помилку.

/* Спроба зміни покажчика-константи на */

/* не-константних даних */

#include <stdio.h>

main ( )

{

int x, у;

int * const ptr = &x;

ptr = &y;

return 0;

}

Compiling FIG7_13.C:

Error FIG7_13.C 10: Cannot modify a const object

Warning FIG7_13.C 12: 'ptr' is assigned a value that is

never used

Warning FIG7_13.C 12: 'у' is declared but never used

Спроба зміни покажчика-константи, що посилається на не-константні дані

8. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її. Змініть значення int x = 5, на ваш номер за списком.

Мінімальні права доступу надає покажчик-константа на константні дані. Такий покажчик завжди вказує на те ж саме місце в пам'яті, а розташовані за цією адресою дані не можуть модифікуватися. Цьому варіанту відповідає передача масиву функції, яка тільки переглядає масив за допомогою індексу і не змінює його елементи. У програмі що наведена нижче, оголошується змінна-покажчик ptr типу const int * const. Оголошення читається справа наліво і звучить так: "ptr - указатель-кон- станта на цілу константу". На малюнку показані повідомлення про помилки, отримані в результаті спроби змінити дані, на які вказує ptr, і змінити присвоєний покажчику адреса.

/* Спроба модифікації покажчика-константи на */

/* дані-констант */

#include <stdio.h>

main ( )

{

int x = 5, у;

const int *const ptr = &x;

*ptr = 7;

ptr = &y;

return 0;

}

Compiling FIG7_14.C:

Error FIG7_14.C 10: Cannot modify a const object

Error FIG7_14.C 11: Cannot modify a const object

Warning FIG7_14.C 13: 'ptr' is assigned a value that is

never used

Warning FIG7_14.C 13: 'y' is declared but never used

Спроба змінити константний вказівник на константні дані

9. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її. Змініть значення SIZE 10, на ваш номер за списком.

Програма бульбашкового сортування, що використовує виклик по посиланню

Давайте змінимо програму бульбашкового сортування, і введемо дві функції - bubbleSort і swap. Функція bubbleSort виконує сортування масиву. Вона викликає функцію swap для перестановки елементів масиву array[j] і array[j + 1].

Як відомо, функції в С приховують свої дані один від одного, тому swap не має доступу до елементів масиву у функції bubbleSort. Але оскільки bubbleSort зацікавлена в тому, щоб функція swap мала доступ до масиву, bubbleSort передає їй потрібні елементи по посиланню, тобто явно передає адреси елементів масиву. При використанні імені масиву як аргументу передається по посиланню увесь масив цілком, індивідуальні ж елементи масиву є скалярами і передаються за значенням. Тому bubbleSort при зверненні до функції swap використовує операцію узяття адреси (&) кожного з елементів:

swap (&array[j], &array[j + 1]);

щоб передати їх по посиланню. Функція swap поміщає адресу &array[j] у змінну-покажчик element1Ptr. І тепер, хоча swap і не має доступу до елементів масиву array[j], унаслідок приховання інформації, swap може використовувати разыменованный покажчик *element1Ptr як синонім array[j]. Отже, коли swap звертається до *element1Ptr, вона отримує елемент array[j] з bubbleSort.

Аналогічно, коли swap посилається на *element2Ptr, то отримує array[j + 1] з bubbleSort.

І хоча swap не може виконати наступні оператори,

temp = array[ j ] ;

array [j] = array[j + 1];

array[j +1] = temp;

вона отримає той же самий результат за допомогою операторів

temp = *elementlPtr;

**elementlPtr = *element2Ptr;

**eiement2Ptr = temp;

у своєму тілі - див. програму заповнює масив, сортує значення в порядку

зростання і виводить відсортований масив

Відмітимо декілька особливостей функції bubbleSort. Її заголовок оголошує масив array як int *array, а не як int array[], оскільки ці способи запису параметра-масиву взаємозамінні. Відповідно до принципу мінімуму привілеїв, параметр size оголошується з модифікатором const. І хоча параметр size містить копію значення з функції main, зміна якої ніяк не може змінити значення змінної в main, функції bubbleSort не вимагається змінювати величину size для виконання свого завдання. Розмір масиву залишається величиною, постійною під час виконання bubbleSort. Тому параметр size і оголошений константним, щоб гарантувати його незмінність. Якби в процесі сортування розмір масиву змінився, то, можливо, алгоритм виконувався б неправильно.

Прототип функції swap включений в тіло функції, тому що bubbleSort - єдина функція, яка викликає swap. Розміщення прототипу в bubbleSort обмежує правильні виклики swap тільки тими, що були зроблені з bubbleSort. Інші функції, які, не маючи доступу до відповідного функціонального прототипу, спробують викликати swap, використовуватимуть прототип за умовчанням. Зазвичай цей прототип не відповідає

заголовку функції (що призводить до помилки компіляції), оскільки компілятор за умовчанням припускає тип int для повертаного значення і параметрів функції.

/* Ця програма заповнює масив, сортує значення в порядку

зростання і виводить відсортований масив */

#include <stdio.h>

#define SIZE 10

void bubbleSort (int *, int);

main ( )

(

int i, a [SIZE] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };

printf ("Data items in original order \n");

for (i = 0; i <= SIZE - 1; i++)

printf ("%4d", a[i]);

bubbleSort (a, SIZE); /* сортування массива.*/

printf("\n Data items in ascending order\n");

for (i = 0; i <= SIZE - 1; i++)

printf("%4d", a[i] );

printf ("\n");

return 0;

}

void bubbleSort(int *array, int size)

{

int pass, j;

void swap(int *, int *);

for (pass = 1; pass <= size - 1; pass++)

for (j = 0; j <= size - 2; j + + )

if (array[j] > array[j + 1])

swap(sarray[j], &array[j + 1]);

}

void swap(int *element1Ptr, int *element2Ptr)

{

int temp;

temp = *elementlPtr;

**elementlPtr = *element2Ptr;

**element2Ptr = temp;

}

Data items in original order

2 6 4 8 10 12 89 68 45 37

Data items in ascending order

4 6 8 10 12 37 45 68 89

Програма заповнює масив, сортує значення в порядку зростання і виводить відсортований масив

10. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її. Змініть значення float array[20], на ваш номер за списком.

У C є спеціальна унарна операція sizeof, за допомогою якої можна визначити розмір масиву (чи будь-якого іншого типу даних) в байтах під час компіляції програми. Якщо цю операцію застосувати до імені маесива, то sizeof поверне загальну кількість байт, займане масивом, у вигляді цілого числа. Наприклад, змінна типу float зазвичай займає 4 байти пам'яті, а масив оголошений двадцятиелементним. Отже, загальна кількість байт в масиві рівне 80.

/* застосування операції sizeof до масиву */

/* повертається число байт в масиві */

#include <stdio.h>

main ()

{

float array[20];

printf("The number of bytes in the array is %d\n",

sizeof(array));

return 0;

}

The number of bytes in the array is 80

Операція sizeof, що застосовується до імені масиву, повертає його розмір в байтах

11. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

Число елементів в масиві також може бути визначене під час компіляції. Наприклад, розглянемо наступне оголошення масиву :

double real [22];

Змінні типу double зазвичай займають 8 байт пам'яті. Таким чином, масив real містить 176 байт. Для того, щоб визначити число елементів в масиві, можна використовувати наступне вираження:

sizeof(real) / sizeof(double)

У вираженні визначається число байт в масиві real і набутого значення ділиться потім на число байт, використовуваних для представлення типу double.

Програма що нижче обчислює число байт, використовуваних для представлення стандартних типів даних сумісного з PC комп'ютера.

Операція sizeof може застосовуватися до будь-якої змінної, типу даних або константи. При визначенні розміру змінною або константи (але не масиву) повертається число байт, що відводяться під тип змінної або константи. Зверніть увагу, що дужки з sizeof обов'язкові, якщо як операнд використовується ім'я типу. Відсутність дужок в цьому випадку призводить до повідомлення про помилку. Дужки не потрібно, якщо операнд є ім'ям змінної.

/* Використання операції sizeof * /

#include <stdio.h>

main ()

{

printf(" sizeof(char) = %d\n"

" " sizeof(short) = %d\n"

" " sizeof (int) = %d\n"

" " sizeof(long) = %d\n"

" " sizeof (float) = %d\n"

" " sizeof(double) = %d\n"

""sizeof(long double) = %d\n",

sizeof(char), sizeof (short), sizeof (int),

sizeof(long), sizeof (float), sizeof(double),

sizeof(long double));

return 0;

}

sizeof(char) = 1

sizeof(short) = 2

sizeof(int) = 2

sizeof(long) = 4

sizeof(float) = 4

sizeof(double) = 8

sizeof(long double) = 10

Використання операції sizeof для визначення розміру стандартних типів даних

12. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

У програмі що нижче, використовуються чотири методи посилання на елементи масиву, які ми обговорили, - ім'я масиву і індекс, покажчик/зміщення з ім'ям масиву, покажчик і індекс і покажчик/зміщення, - для виведення чотирьох елементів цілочисельного масиву b.

Як ще один приклад взаємозамінюваності масивів і покажчиків розглянемо дві функції копіювання рядків - сору1 і сору2 - в програмі копіювання рядка за допомогою індексів і покажчиків. Обидві функції копіюють рядок символів (можливо, символьний масив) в масив символів. Прототипи функцій сору1 і сору2 абсолютно ідентичні. І дійсно, вони виконують одне і те ж завдання, але роблять це по-різному.

/* Використання індексів і покажчиків при роботі з масивами */

#include <stdio.h>

main ( )

{

int i, offset, b[ ] = {10, 20, 30, 40)};

int *bPtr = b; /* покажчику bPtr привласнюється початкова адреса масиву b */

printf("Array b is printed with:\n"

"Array subscript notation\n");

for (i = 0; i <= 3; i++)

printf ("b[%d] = %d\n", i, b[i] );

printf ( "\nPointer/offset notation where \n"

"the pointer is the array name\n");

for (offset = 0; offset <= 3; offset++)

printf("*(b + %d) = %d\n", offset * (b + offset));

printf ("\nPointer subscript notation\n");

for (i = 0; i <= 3; i++)

printf ( bPtr[%d] = %d\n, i, bPtr[i]);

printf("\nPointer/offset notation\n");

for (offset = 0; offset <= 3; offset++)

printf("*(bPtr + %d) = %d\n", offset *(bPtr + offset));

return 0;

}

Array b is printed with:

Array subscript notation

b[0] = 10

b[l] = 20

b[2] = 30

b[3] = 40

Pointer/offset notation where

the pointer is the array name

*(b + 0) =10

*(b + 1) =20

*(b + 2) =30

*(b + 3) =40

Pointer subscript notation

bPtr[0] = 10

bPtr[1] = 20

bPtr[2] = 30

bPtr[3] = 40

Pointer/offset notation

*(bPtr + 0) = 10

*(bPtr + 1) = 20

*(bPtr + 2) = 30

*(bPtr + 3) = 40

Використання чотирьох методів посилання на елементи масиву

13. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

/* Копіювання рядка з використанням індексів з ім'ям масиву і арифметики покажчиків */

#include <stdio.h>

void copy1(char *, const char *);

void copy2(char *, const char *);

main ( )

{

char string1[10], *string2 = "Hello"

string3[10], string4[] = "Good bye";

copy1(string1, string2);

printf ("string 1 = %s\n", string1);

copy2(string3, string4);

printf ( "string 3 = %s\n", string3);

return 0;

}

/* /* копіювання s2 в s1 за допомогою індексної нотації */

void copy1(char *s1, const char *s2)

{

int i;

for (i = 0; s1 [i] = s2 [i] ; i + +);

/* тіло циклу порожнє */

}

/* копіювання s2 в s1 з використанням арифметики покажчиків */

void сору2(char *s1, const char *s2)

{

for (; *s1 = *s2; s1++, s2++);

/* тіло циклу порожнє */

}

string1 = "Hello",

string3 = "Good bye";

Копіювання рядка за допомогою індексів і покажчиків

Функція copy1 застосовує для копіювання рядки s2 в масив s1 індексну нотацію. Функція оголошує цілую змінну-лічильник i, використовувану як індекс масиву. У заголовку циклу for виконується уся робота із створення копії, при цьому тіло циклу порожнє. У заголовку циклу i ініціалізувався нулем і збільшується на одиницю на кожному кроці циклу. Умова циклу for, sl[i] = s2[i], виконує посимвольне копіювання рядка s2 в s1. Коли в s2 зустрічається нуль-символ, він привласнюється s1, і цикл завершується, тому що цілочисельне значення нуль-символа дорівнює нулю (а значення вираження - false). Нагадаємо, що значенням оператора привласнення є значення, що отримується лівим операндом.

Функція сору2 при копіюванні рядка s2 в символьний масив s1 використовує покажчики і арифметику покажчиків. Тут також усі операції копіювання виробляються в заголовку циклу for. У циклі не використовується змінна, що управляє. Як і у функції copy1, копіювання символів рядка виконується у вираженні умови циклу (*s1 = *s2). Покажчик s2 разыменовывается і отриманий символ привласнюється разыменованному покажчику s1. Після виконання привласнення у вираженні умови циклу покажчики збільшуються для переходу відповідно до наступного елементу масиву s1 і наступному символу рядка s2. Коли в рядку s2 зустрічається нуль-символ, він привласнюється разыменованному покажчику s1 і цикл завершується.

Зверніть увагу на те, що перший параметр функцій copy1 і сору2 має бути масивом досить великого розміру, щоб вмістити рядок, що передається другим параметром. Інакше станеться помилка при записі в область пам'яті, яка не є частиною масиву. Зверніть увагу також, що другий параметр кожної функції оголошений як const char * (рядок-константа). У обох функціях другий аргумент копіюється в перший аргумент, при цьому символи з другого аргументу читаються по одному і не змінюються. Тому, відповідно до принципу мінімуму привілеїв, другий параметр оголошується покажчиком на значення-константу.

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

Приклад: програма тасування і здачі колоди карт

У цьому розділі, використовуючи генератор випадкових чисел, ми складемо програму, що моделює тасування і здачу карт. Цю програму можна буде потім використовувати при написанні ігрових карткових програм. Ми навмисно використовували неоптимальні алгоритми тасування і здачі, щоб таким чином познайомити вас з деякими тонкими проблемами ефективності. Далі ми розробимо ефективніші алгоритми.

Діючи методом низхідного послідовного уточнення, ми розробимо програму, яка перетасує колоду з 52 гральних карт і потім усе їх роздасть. Низхідний метод особливо корисний при рішенні великих і складних проблем, а не таких простих, як ті, з якими ми мали справу.

Для представлення колоди ми використовуємо двовимірний масив deck розміром 4 на 13 (див. табл.3.). Рядки масиву відповідають мастям; рядок 0 - чирва, рядок 1 - бубни, рядок 2 - трефи, і рядок 3 представляє списи. По стовпцях записані номінали карт, стовпці з індексом від 0 до 9 відповідають картам відповідно від туза до десятки, а стовпці з 10-го по 12-ій відповідають вальту, пані і королеві. Ми заповнимо масив suit рядками - іменами чотирьох мастей, а масив face - рядками, відповідними тринадцяти картковим номіналам.

Ця уявна колода карт може бути перетасована таким чином. Спочатку масив deck заповнюється нулями. Потім випадковим чином вибирається номер рядка row (число від 0 до 3) і номер стовпця column (число в діапазоні 0-12). У вибраний таким чином елемент масиву deck[row][co - lumn] поміщається число 1, яке означає, що ця карта з "перетасованої" колоди буде здана першій. Цей процес триває далі для чисел 2, 3, .., 52, що вставляються випадковим чином в масив deck і що означають карти, які мають бути здані другій, третій і так далі до п'ятдесят другий. Як тільки масив deck починає заповнюватися числами, виникає ймовірність, що деякі карти будуть вибрані двічі, тобто при виборі деякого елементу deck[row][column] його значення буде відмінне від нуля. В цьому випадку випадковий вибір row і column повторюється до тих пір, поки не буде знайдена карта, яка ще не вибиралася. Кінець кінцем числа від 1 до 52 займуть усі 52 елементи масиву deck. Тим самим колода буде повністю перетасована

Таблиця 3

Представлення колоди карт у вигляді двовимірного масиву

	Туз	Двійка	Трійка	Четвірка	П′ятірка	Шестірка	Семірка	Восьмірка	Дев′ятка	Десятка	Валет	Дама	Король
	0	1	2	3	4	5	6	7	8	9	10	11	12
Чірви 0
Бубни 0
Крести 0
Піки 0

deck[2] [12] представляє короля треф

Крести Король

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

Щоб почати здачу колоди, ми повинні знайти елемент масиву deck[row][column], значення якого дорівнює 1. Це завдання виконують вкладені цикли for, в яких row змінюється від 0 до 3, а column - від 0 до 12. Як дізнатися, яка карта відповідає цьому елементу масиву? Оскільки масив мастей suit був вже нами визначений, для того, щоб дістати назву масті, треба вивести рядок suit[row]. Аналогічно, щоб дістати назву номінала карти, нам треба вивести рядок face[column]. Крім того, ми виводимо рядок " of ". Інформація відносно усіх зданих карт виводиться у формі "King of Clubs", "Асові of Diamonds" і так далі

Давайте приступимо до процесу низхідного проектування. Спочатку запишемо наше завдання в загальному вигляді

Тасування і роздача 52 карт

На першому кроці деталізації алгоритму його можна записати так:

Ініціалізація масиву suit

Ініціалізація масиву face

Ініціалізація масиву deck

Тасування колоди

Роздача 52 карт

Пункт "Тасування колоди" може бути деталізоване таким чином:

Для кожної з 52 карт

Записати номер карти у вибраний випадковим чином вільний елемент масиву deck

Пункт "Роздача 52 карт" може бути деталізована таким чином:

Для кожної з 52 карт

Знайти номер карти в масиві deck і вивести назву номінала і масті карти

З урахуванням зроблених розширень на другому кроці деталізації алгоритм виглядатиме так:

Ініціалізація масиву suit

Ініціалізація масиву face

Ініціалізація масиву deck

Для кожної з 52 карт

Записати номер карти у вибраний випадковим чином вільний елемент масиву deck

Для кожної з 52 карт

Знайти номер карти, в масиві deck і вивести назву номінала і масті карти

Пункт "Записати номер карти у вибраний випадковим чином вільний елемент масиву deck" може бути розширений таким чином:

Вибрати випадковим чином елемент масиву deck

Доки вибраний елемент вже вибирався раніше

Вибрати випадковим чином елемент масиву deck

Записати номер карти у вибраний елемент масиву deck

Пункт "Знайти номер карти в масиві deck і вивести назву номінала й масті карти" можна деталізувати як:

Для кожного елементу масиву

Якщо елемент містить шуканий номер карти.

Вивести назву номінала карти і її масть

В результаті на третьому кроці деталізації алгоритм набере вигляду:

Ініціалізація масиву suit

Ініціалізація масиву face

Ініціалізація масиву deck

Для кожної з 52 карт

Вибрати випадковим чином елемент масиву deck

Доки вибраний елемент вже вибирався раніше

Вибрати випадковим чином елемент масиву deck

Записати номер карти у вибраний елемент масиву deck

Для кожної з 52 карт

Для кожного елементу масиву

Якщо елемент містить шуканий номер карти

Вивести назву номінала карти і її масть

На цьому процес деталізації алгоритму можна завершити. Зверніть увагу на те, що цю програму можна зробити ефективнішою, якщо алгоритми тасування і роздачі об'єднати і відразу здавати поміщену в колоду карту. Ми вибрали роздільний варіант цих алгоритмів, оскільки він ближче до реальності: карти спочатку тасуються, а потім здаються.

Програма тасування і здачі колоди карт приведена нижче, а приклад її виконання – ще нижще, у вигляді результату. Зверніть увагу на використання специфікатора формату %s функції printf для виведення рядка символів. Відповідний цьому специфікатору аргумент функції printf має бути покажчиком на тип char (чи символьним масивом). У функції deal специфікація "%5s of %-8s" виводить символьний рядок, вирівняний по правому краю, в полі з п'яти символів, за якою йде рядок " of ", і рядок символів, вирівняний по лівому краю, в полі з восьми символів. Знак "мінус" в специфікації % - 8s якраз і означає вирівнювання по лівому краю в полі шириною 8 символів.

14. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

/* Програма, що здає колоду карт */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void shuffle(int [] [13]);

void deal(const int [][13], const char *[], const char *[]);

main()

{

char *suit [4] = {"Hearts", "Diamonds", "Clubs", "Spades"};

char *face[13] = {"Ace", "Deuce", "Three", "Four"

"Five", "Six", "Seven", "Eight"

"Nine", "Ten", "Jack", "Queen", "King"};

int deck[4][13] = {0};

srand(time(NULL));

shuffle(deck);

deal(deck, face, suit);

return 0;

}

void shuffle(int wDeck[][13])

{

int card, row, column;

for (card = 1; card <= 52; card++){

row = rand() % 4;

column = rand() % 13;

while (wDeck[row][column] != 0} {

row = rand() % 4;

column = rand() % 13;

}

wDeck[row][column] = card;

}

}

void deal(const int wDeck[] [13], const char *wFace[ ],

const char *wSuit [ ])

{

int card, row, column;

for (card = 1; card <= 52; card++)

for (row = 0; row <= 3; row++)

for (column = 0; column <= 12; column++)

if (wDeck[row][column] == card)

printf("%5s of %-8s% c"

wFace[column], wSuit[row],

card % 2 == 0 ? '\n' : '\t');

}

Програма роздачі колоди карт

Six	of	Clubs	Seven	of	Diamonds
Ace	of	Spades	Ace	of	Diamonds
Ace	of	Hearts	Queen	of	Diamonds
Queen	of	Clubs	Seven	of	Hearts
Ten	of	Hearts	Deuce	of	Clubs
Ten	of	Spades	Three	of	Spades
Ten	of	Diamonds	Four	of	Spades
Four	of	Diamonds	Ten	of	Clubs
Six	of	Diamonds	Six	of	Spades
Eight	of	Hearts	Three	of	Diamonds
Nine	of	Hearts	Three	of	Hearts
Deuce	of	Spades	Six	of	Hearts
Five	of	Clubs	Eight	of	Clubs
Deuce	of	Diamonds	Eight	of	Spades
Five	of	Spades	King	of	Clubs
King	of	Diamonds	Jack	of	Spades
Deuce	of	Hearts	Queen	of	Hearts
Ace	of	Clubs	King	of	Spades
Three	of	Clubs	King	of	Hearts
Nine	of	Clubs	Nine	of	Spades
Four	of	Hearts	Queen	of	Spades
Eight	of	Diamonds	Nine	of	Diamonds
Jack	of	Diamonds	Seven	of	Clubs
Five	of	Hearts	Five	of	Diamonds
Four	of	Clubs	Jack	of	Hearts
Jack	of	Clubs	Seven	of	Spades

(Результат) Приклад виконання програми роздачі колоди катр

У нашого алгоритму здачі карт є один недолік. Коли знайдена потрібна карта, іноді з першої спроби, два внутрішні цикли for продовжують пошук в частині масиву deck, що залишилася. Далі, в лекціїї 10, ми виправимо цей дефект.

Покажчики на функції

14. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її. Змініть значення SIZE 10 на ваш номер варіанту по списку.

Покажчик на функцію - це змінна, що містить адресу в пам'яті, по якій розташована функція. Ми знаємо, що ім'я масиву є адресою першого елементу масиву. Аналогічним чином ім'я функції - це адреса початку програмного коду функції. Покажчики на функції можуть бути передані функціям як аргументи, можуть повертатися функціями, зберігатися в масивах і привласнюватися іншим покажчикам на функції.

Щоб проілюструвати використання покажчиків на функції, ми візьмемо програму бульбашкового сортування, і створимо новий її варіант. Наша нова програма складається з функцій main, bubble, swap, ascending і descending. Функція bubble отримує покажчик на функцію - це може бути функція ascending або функція descending - на додаток до двох інших параметрів: цілочисельному масиву і розміру масиву. Під час виконання програма просить у користувача спосіб сортування - в порядку зростання або убування. Якщо користувач вводить число 1, функції bubble передається покажчик на функцію ascending і виробляється сортування переданого масиву за збільшенням. Якщо користувач вводить число 2, то у функцію bubble передається покажчик на функцію descending і виробляється сортування масиву по убуванню. Приклад двох сеансів роботи з програмою показаний на лістингу 7.27.

У заголовку функції bubble є наступний параметр:

int (* compare) (int, int)

Це означає, що функція bubble отримує аргумент, що є покажчиком на функцію, яка має два цілочисельні параметри і повертає результат цілого типу. Навкруги *compare потрібні круглі дужки, тому що операція * має нижчий пріоритет, ніж дужки, в які поміщені параметри функції. Якщо ми приберемо круглі дужки, то оголошення матиме вигляд

int * compare (int, int)

і означатиме функцію, яка отримує два цілі числа як параметри і повертає покажчик на ціле число.

Прототип функції bubble може бути оголошений і у такому вигляді:

Int (*) (int, int)

Зверніть увагу на те, що обов'язкові тільки оголошення типу даних. Програміст може включати в прототип імена, щоб текст програми був яснішим. Компілятор їх ігноруватиме.

Функція, передана функції bubble, викликається в операторові if таким чином:

if ((*compare) (work [count], work [count +1]))

Подібно до того, як разыменовывают покажчик на змінну, щоб набути її значення, покажчик на функцію разыменовывают, щоб виробити виклик цієї функції.

/* Багатоцільова програма сортування, що використовує покажчики на функцію */

#include <stdio.h>

#define SIZE 10

void bubble (int *, const int, int (*) (int, int));

int ascending(const int, const int);

int descending(const int, const int);

main ()

{

int a[SIZE] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37);.

int counter, order;

printf("Enter 1 to sort in ascending order, \n");

printf ("Enter 2 to sort in descending order: ");

scanf("%d", &order);

printf("\nData items in original order\n");

for (counter = 0; counter <= SIZE - 1; counter++)

printf("%4d", a[counter]);

if (order == 1){

bubble (a, SIZE, ascending);

printf("\nData items in ascending order\n");

}

else {

bubble (a, SIZE, descending);

printf ("\nData items in descending order\n");

}

for (counter = 0; counter <= SIZE - 1; counter++)

printf("%4d", a[counter]);

printf ("\n" );

return 0;

}

void bubble (int *work, const int size, int (*compare) (int, int))

{

int pass, count;

void swap(int *, int *);

for (pass = 1; pass <= size - 1; pass++)

for (count = 0; count <= size - 2; count++)

if ((*compare)(work[count], work[count + 1]))

swap(&work[count], &work[count + 1]);

}

void swap(int *elementlPtr, int *element2Ptr)

{

int temp;

temp = *element1Ptr;

*element1Ptr = *element2Ptr;

*element2Ptr = temp;

}

int ascending (const int a, const int b)

return b < a;

}

int descending(const int a, const int b)

return b > a;

Лістинг 7.26. Багатоцільова програма сортування, що використовує покажчики на функцію

Enter 1 to sort in ascending order,

Enter 2 to sort in descending order: 1

Data items in original order

2 6 4 8 10 12 89 68 45 37

Data items in ascending order

4 6 8 10 12 37 45 68 89

Enter 1 to sort in ascending order,

Enter 2 to sort in descending order: 2

Data items in original order

6 4 8 10 12 89 68 45 37

Data items in descending order

89 68 45 37 12 10 8 6 4 2

Лістинг 7.27. Результати роботи програми бульбашкового сортування, приведеного на лістингу 7.26

Функцію можна викликати і без разыменования покажчика, як це зроблено в наступному рядку:

if (compare(work[count], work[count +1]))

Тут покажчик використовується безпосередньо, як ім'я функції. Ми віддаємо перевагу першому методу виклику - з разыменованием покажчика, тому що в цьому варіанті явно видно, що compare є покажчиком на функцію. При другому методі виклику функції через покажчик може створитися враження, що compare - це ім'я функції. В результаті користувач програми може заплутатися, якщо спробує знайти визначення функції compare і виявить, що вона ніде у файлі не визначена.

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

15. Прочитайте теоретичні положення. Напишіть програму, на лістингу що нижче, проаналізуйте її.

Програма на лістингу 7.28 показує типовий приклад оголошення і використання масиву покажчиків на функцію. Визначаються три функції - function1, function2 і function3, - кожна з яких має цілочисельний параметр і не повертає значення. Покажчики на ці три функції знаходяться в масиві f, який оголошується так:

void {* f[3] ) (int) = (function1, function2, function3);

Оголошення читається, починаючи з найлівішої дужки і звучить як: "f - масив з трьох покажчиків на функцію, яка має параметр цілого типу і не повертає значення". Масив ініціалізувався іменами трьох функцій. Коли користувач вводить значення від 0 до 2, це значення використовується як індекс масиву покажчиків на функцію. Виклик функції виконується таким чином:

(*f[choice]) (choice);

/*Пример використання масиву покажчиків на функцію */

#include <stdio.h>

void function1 (int);

void function2 (int);

void function3 (int);

main ()

{

void(function1, function2, function3);

int choice;

printf("Enter a number between 0 and 2, 3 to end: ");

scanf("%d", &choice);

while (choice >= 0 && choice < 3){

(*f[choice]) (choice);

printf("Enter a number between 0 and 2, 3 to end: ");

scanf("%d", &choice);

}

printf("You entered 3 to end\n");

return 0;

}

void function1(int a)

{

printf("You entered %d so function1 was called\n\n", a);

}

void function2(int b)

{

printf ("You entered %d so function2 was called\n\n", b);

{

void function3(int c)

{

printf ("You entered %d so function3 was called\n\n", c);

}

Enter a number between 0 and 2, 3 to end: 0

You entered 0 so function1 was called

Enter a number between 0 and 2, 3 to end: 1

You entered 1 so function2 was called

Enter a number between 0 and 2, 3 to end: 2

You entered 2 so function3 was called

Enter a number between 0 and 2, 3 to end: 3

You entered 3 to end

Лістингу 7.28. Приклад масиву покажчиків на функцію

У цьому виклику f[choice] вибирає покажчик по індексу choice. Для виклику функції покажчик разыменовывается, а змінна choice передається функції як аргумент. Кожна функція виводить значення отриманого аргументу і своє ім'я, що дозволяє переконатися в правильності виклику функції. У вправах ви розробите програму, керовану за допомогою меню.