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

іnt digit (unsіgned char r); або digit (unsіgned char);

У програмах мовою Сі широко використовуються, так звані, бібліотечні функції, тобто функції попередньо розроблені й записані у бібліотеки. Прототипи бібліотечних функцій перебувають у спеціальних заголовних файлах, що поставляються разом з бібліотеками в складі систем програмування, і включаються в програму за допомогою директиви #іnclude.

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

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

іnt digit (r)

unsіgned char r;

{ ... /* тіло функції */ ... }

Відповідно до синтаксису мови Сі визначення функції має наступну форму:

[ специфікатор - класу - пам'яті] [ специфікатор - типу] ім'я - функції

([ список-формальних-параметрів])

{ тіло функції }

Необов'язковий специфікатор -класу- пам' яті задає клас пам' яті функції, що може бути statіc або extern. Доповідний класи пам' яті будуть розглянуті далі.

Специфікатор -Типу функції задає тип значення, що повертається, і може задавати будь-який тип. Якщо специфікатор - типу не завдань, то передбачається, що функція повертає значення типу іnt.

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

Функція повертає значення якщо її виконання закінчується оператором return, що містить деяке вираження. Зазначене вираження обчислюється, перетвориться, якщо необхідно, до типу значення, що повертається, і вертається в місце виклику функції як результат. Якщо оператор return не містить вираження або виконання функції завершується після виконання останнього її оператора (без виконання оператора return), то повертається значення, що, не визначено. Для функцій, що не використовують значення, що повертається, повинний бути використаний тип voіd, що вказує на відсутність значення, що повертається. Якщо функція визначена як функція, що повертає деяке значення, а в операторі return при виході з неї відсутнє вираження, то поводження функції після передачі їй керування може бути непередбаченим.

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

Якщо функція не використовує параметрів, то наявність круглих дужок обов'язково, а замість списку параметрів рекомендується вказати слово voіd.

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

Для формального параметра можна задавати клас пам'яті regіster, при цьому для величин типу іnt специфікатор типу можна опустити.

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

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

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

Тіло функції - це складений оператор, що містить оператори, що визначають дію функції.

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

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

Практика

Описати функцію Sign(X) цілого типу, що повертає для дійсного числа X наступні значення:

-1, якщо X < 0; 0, якщо X = 0; 1, якщо X > 0.

За допомогою цієї функції знайти значення вираження Sign(A) + Sign(B) для цих дійсних чисел A і B.

Описати функцію SumRange(A, B) цілого типу, суму усіх цілих чисел, що знаходить, від A до B включно (A і B -- цілі). Якщо A > B, то функція повертає 0. За допомогою цієї функції знайти суми чисел від A до B і від B до C, якщо дані числа A, B, C.

Описати функцію MinElem(A, N) цілого типу, що знаходить мінімальний елемент цілочисельного масиву A розміру N. За допомогою цієї функції знайти мінімальні елементи масивів A, B, C розміру NA, NB, NC відповідно.

Даний масив A розміру N. Описати функцію, яка, не змінюючи цей масив, виводить номери його елементів в тому порядку, в якому відповідні ним елементи утворюють зростаючу послідовність.

Описати функцію IsPowerN(K, N) логічного типу, повертаючу TRUE, якщо цілий параметр K (> 0) є мірою числа N (> 1), і FALSE інакше. Дано число N (> 1) і набір з 10 цілих позитивних чисел. За допомогою функції IsPowerN знайти кількість мір числа N в цьому наборі.



Лекція 11. "Покажчики і Рекурсія"

Рекурсія

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

Прямою (безпосередньої) рекурсією є виклик функції усередині тіла цієї функції.

іnt a()

{.....a()....}

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

Наприклад:

a(){....b()....}

b(){....c()....}

c(){....a()....} .

Всі функції a, b, c є рекурсивними, тому що при виклику однієї з них, здійснюється виклик інших і самої собі.

Розглянемо завдання про Ханойські вежі.

Ханойські вежі (рекурсивні алгоритми)

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

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

Правила гри

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

за одну дію можна переносити тільки одне кільце;

кільце можна укладати або на вільний стержень, або на більше кільце.

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

Позначимо стержні номерами:

1 лівий стержень, на якому знаходиться пірамідка на початку гри

2 середній стержень, допоміжний

3 правий стержень, на нього потрібно перенести пірамідку

Размещено на http://www.allbest.ru/



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

Размещено на http://www.allbest.ru/

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

Размещено на http://www.allbest.ru/

У цьому алгоритмі ми двічі використовували алгоритм Ханой-2, але при цьому різні стержні виступали кінцевим і допоміжним.

Ханой-4 {

/* переносимо три кільця на другий стержень */

Ханой-3 (1,2,3);

/* переносимо нижнє кільце на третій стержень */

1 3;

/* переносимо три кільця з другого на третій */

Ханой-3 (2,3,1);

}

Загальний алгоритм для n кілець.

1. Переносимо n - 1 кілець на другий стержень

2. Переносимо нижнє кільце на третій стержень

3.Переносимо n - 1 кілець з другого на третій

Рішення для піраміди з n кілець можна записати у такому вигляді:

Ханой ( n, nach, kon, vspom)

{

якщо n > 1, то

Ханой ( n - 1, 1, 2, 3 );

початковий ( кінцевий;

якщо n > 1, то

Ханой ( n - 1, 2, 3, 1 );

}

Тут в якості початкового, кінцевого і допоміжного можна використовувати будь-які стержні. Алгоритм Ханойфактично пропонує вирішувати задачу дляnкілець через два завдання для меншого числа кілець (n - 1). Такий прийом в програмуванні називаєтьсярекурсія.

Що таке рекурсія?

Рекурсія - спеціальний прийом в програмуванні, коли алгоритм рішення задачі містить алгоритм рішення подібної задачі, але з іншими початковими даними.

Тепер ми познайомилися з четвертим видом алгоритмів - рекурсивним алгоритмом. Помітимо, що для перенесення пірамідки з двохкілець потрібно всього 3 ходи, для трьох кілець - вже 3+1+3=7 ходів, для чотирьох - 15 і так далі. Можна показати, що для перенесення пірамідки з n кілець нам буде потрібно ходів. У ченців древнього Ханоя була пірамідка з 64 кілець і вони вірили, що коли вдасться перенести усю пірамідку на третій стержень, настане кінець світу. Отже, це легенда, але число насправді дуже велике і для того, щоб зробити стільки ходів, не вистачить декількох людських життів.

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

Нижче наведена програма, що вводити число n і друкує список переміщень, що вирішує завдання про Ханойські вежі при кількості дисків n. Використовується внутрішня рекурсивна процедура tn(n, і, j, w), що друкує переміщення, необхідні для перенесенню n дисків зі стрижня й на стрижень j з використанням допоміжного стрижня w при {і, j, w} = {1,3,2}.

/* ханойські вежі */

#include

main() /* що викликає */

{ void tn(int, int, int, int); /* функція */

int n;

scanf(" %d",&n);

tn(n, 1,3,2);

}

void tn(int n, int nach, int kon, int w) /* рекурсивна */

{ if (n>1) /* функція */

{ tn (n - 1, nach, w, kon);

tn (1, nach, kon, w);

tn (n - 1, w, kon, nach);

}

else printf(" %d -> %d", nach, kon);

return ;

}

Послідовність викликів процедури tn при m=3 ілюструється деревоподібною структурою на рис.33. Щораз при виклику процедури tn під параметри n, nach, kon, w виділяється пам'ять і запам'ятовується місце повернення. При поверненні із процедури tn пам'ять, виділене під параметри n, nach, kon, w, звільняється й стає доступної пам'ять, виділена під параметри n, nach, kon, w попереднім викликом, а керування передається в місце повернення.

Рис.33. Послідовність викликів процедури tn

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

Припустимо, що є ситуація:

main() /* зухвала функція */

{ ... f()...}

f() /* рекурсивна функція */

{ ... f()...}

Тут у функції maіn викликається рекурсивна функція f. Потрібно замінити опис функції f і її виклику на еквівалентний фрагмент програми, тобто видалити функцію f.

Нехай рекурсивна функція f має параметри Р1, Р2,...,Рs, внутрішні змінні V1, V2,...,Vt і у функціях maіn і f є k звертань до функції f. Для видалення такої функції потрібні наступні додаткові об'єкти :

- змінні AR1, AR2,...,ARs, що містять значення фактичних параметрів при виклику функції f (типи змінних повинні відповідати типам параметрів Р1, Р2,...,Рs);

- змінна rz для результату, що обчислюється функцією f (тип змінних збігається з типом значення функції, що повертається, f);

- стік, що містить у собі всі параметри й всі внутрішні змінні функції f, а також змінну lr типу іnt, для зберігання крапки повернення, і змінну pst типу покажчик, для зберігання адреси попереднього елемента стека;

- покажчик dl для зберігання адреси вершин стека;

- проміжний покажчик u для операцій над стеком;

- k нових міток L1,...,Lk для позначених крапок повернення;

- мітка jf, використовувана для обходу модифікованого тіла функції f;

- проміжна змінна l типу іnt для передачі номера крапки повернення.

Щоб одержати еквівалентну не рекурсивну програму без функції f, необхідно виконати наступні дії:

1. Забрати оголошення функції f у функцію maіn;

2. Додати у функції maіn оголошення змінних AR1, AR2,...,ARs, RZ, оголошення стека ST і покажчиків dl і u:

typedef struct st { P1;P2;...;Ps;V1;V2;...;Vt;

int lr; struct st *pst } ST;

ST *dl=NULL, *u;

3. Модифікувати тіло функції f у фрагмент програми. Для цього треба:

а) видалити заголовок функції f;

б) оголошення параметрів і внутрішні змінних і замінити фрагментом:

goto jf;

f: a=malloc(sizeof(ST));

a ->P1=AR1; a ->P2=AR2; ... ;a ->Ps=ARs;

a ->lr=l; a ->pst=dl; dl=a;

в) наприкінці функції f поставити мітку JF, а всі звертання до формальних аргументів замінити обігом, до відповідних елементів стека;

г) замість кожного оператора return(y) у функції f записати фрагмент:

RZ=y; l=dl ->lr;

a=dl; dl=a ->pst; free(a);

switch(l)

{ case 1: goto L1;

case 2: goto L2;

...

case k: goto Lk;

}

4. Кожний і виклик функції f (як у зухвалій функції, так і в тілі функції f) виду V=f(A1, A2,...,As) замінити фрагментом програми :

AR1=A1; AR2=A2; ... ; ARs=As; l=i; goto f;

Li: V=RZ;

де l=і позначає l=1 при першому звертанні до функції f, l=2 при іншому обігу й т.д. Нумерація обігів може бути виконана в довільному порядку й потрібно для повернення в крапку виклику за допомогою операторів swіtch і goto Lі; (де Lі є L1 при першій заміні, Lі є L2 при другій заміні й т.д.)

5. Вставити модифіковане тіло функції f наприкінці функції maіn.

Для ілюстрації викладеного розглянемо кілька варіантів реалізації програми що обчислює функцію Акермана, що визначається так:

+ X+1, якщо N=0

| X, якщо N=1, Y=0

| 0, якщо N=2, Y=0

A(N, X, Y)= | 1, якщо N=3, Y=0

| 2, якщо N=>4, Y=0

+ A(N - 1, A(N, X, Y - 1), X), якщо N#0, Y#0;

де N, X, Y - цілі ненегативні числа.

Наступна програма обчислює функцію Акермана з використанням рекурсивної функції ackr і допоміжної функції smacc:

/* рекурсивне обчислення функції Аккермана */

# include

main () /* що викликає */

{ int x, y, n, t; /* функція */

int ackr(int, int, int);

scanf("%d %d %d",&n,&x,&y);

t=ackr(n, x, y);

printf("%d", t);

}

int smacc( int n, int x ) /* допоміжна */

{ switch (n) /* функція */

{ case 0: return(x+1);

case 1: return (x);

case 2: return (0);

case 3: return (1);

default: return (2);

}

}

int ackr( int n, int x, int y) /* рекурсивна */

{ int z; /* функція */

int smacc( int, int);

if(n==0 || y==0) z=smacc(n, x);

else { z=ackr(n, x, y - 1); /* рекурсивних */

z=ackr(n - 1, z, x); } /* викликів ackr(...) */

return z;

}

Модифікуючи функції maіn і ackr відповідно до викладеного методу одержимо наступну програму:

/* Еквівалентна нерекурсивна програма */

/* для обчислення функції Аккермана */

#include

#include

int main()

{ typedef struct st

{ int i, j, k, z, lr;

struct st *pst;

} ST;

ST *u, *dl=NULL;

int l, x, y, n;

int smacc(int, int);

int an, ax, ay, rz, t;

scanf("%i %i %i",&n,&x,&y);

an=n;ax=x;ay=y;l=1; /* - заміна виклику - */

goto ackr; /* t=ackr(n, x, y); */

l1: t=rz; /* - - - - - - - - */

printf("%d ", t);

goto jackr;

/* початок фрагмента замінюючого функцію ackr */

ackr:

u=( ST *) malloc( sizeof (ST));

u ->i=an;

u ->j=ax;

u ->k=ay;

u ->lr=l;

u ->pst=dl;

dl=u;

if (an==0||ay==0)

dl ->z=smacc(an, ax);

else

{

an=dl ->i; /* - заміна виклику - */

ax=dl ->j; /* */

ay=dl ->k - 1; /* z=ackr(n, x, y - 1); */

l=2; /* */

goto ackr; /* */

l2: dl ->z=rz; /* - - - - - - - - */

an=dl ->i - 1; /* - заміна виклику - */

ax=rz; /* */

ay=dl ->j; /* z=ackr(n - 1, z, x); */

l=3; /* */

goto ackr; /* */

l3: dl ->z=rz; /* - - - - - - - - */

}

rz=dl ->z; /* - - - - - - - - */

an=dl ->i; /* */

ax=dl ->j; /* заміна */

ay=dl ->k; /* */

l=dl ->lr; /* оператора */

u=dl; /* */

dl=u ->pst; /* return z ; */

free(u); /* */

switch(l) /* */

{ case 1: goto l1; /* */

case 2: goto l2; /* */

case 3: goto l3; /* */

} /* - - - - - - - - */

jackr:

}

int smacc( int n, int x ) /* допоміжна функція */

{ switch (n)

{ case 0: return(x+1);

case 1: return (x);

case 2: return (0);

case 3: return (1);

default: return (2);

}

}



Лекція 12. Покажчики в C

Що таке покажчики?

Покажчики -- це ті ж змінні. Різниця в тому, що замість того, щоб зберігати певні дані, вони зберігають адресу (покажчик), де дані можуть бути знайдені. Концептуально це дуже важливо. Багато програм і ідей залежать від покажчиків, як від основи їх архітектури, наприклад, пов'язані списки (linked lists).

Вступ

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

int *pNumberOne;

int *pNumberTwo;

Звернули увагу на префікс "p" в обох іменах змінних? Це прийнятий спосіб позначити, що змінна є покажчиком. Так звана угорська нотація. Тепер давайте зробимо так, щоб покажчики на що-небудь вказували:

pNumberOne = &some_number;

pNumberTwo = &some_other_number;ц

Знак & (амперсанд) слід читати як "адреса змінної .". і означає адресу змінної в пам'яті, який буде повернений замість значення самій змінній. Отже, в даному прикладі pNumberOne встановлений і містить адресу змінної some_number, також pNumberOne вказує на some_number.

Таким чином, якщо ми хочемо отримати адресу змінної some_number, ми можемо використовувати pNumberOne. Якщо ми хочемо отримати значення змінної some_number через pNumberOne, треба додати зірочку (*) перед pNumberOne (*pNumberOne). Зірочка (*) розіменовує (перетворює на саму змінну) покажчик і повинна читатися як "місце в пам'яті, яке вказується через ."., окрім оголошень, як в рядку int *pNumber.

Приклад:

#include <stdio.h>

void main()

{

// оголошуємо змінні:

int nNumber;

int *pPointer;

// ініціалізували оголошені змінні:

nNumber = 15;

pPointer = &nNumber;

// виводимо значення змінної nNumber :

printf("nNumber is equal to: %d", nNumber);

// тепер змінюваний nNumber через pPointer:

*pPointer = 25;

// переконаємося що nNumber змінив своє значення в результаті попередньої дії

// вивівши значення змінної ще раз

printf("nNumber is equal to: %d", nNumber);

}

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

Пастка!

Спробуйте знайти помилку в цій програмі:

#include <stdio.h>

int *pPointer;

void SomeFunction()

{

int nNumber;

nNumber = 25;

// робимо так, щоб pPointer вказував на nNumber

pPointer = &nNumber;

}

void main()

{

SomeFunction(); // зробіть щоб pPointer вказував на що не-будь

// чому це не працює?

printf("Value of *pPointer: %d", *pPointer);

}

Програма спочатку викликає функцію SomeFunction, яка створює змінну nNumber, а потім ініціалізує pPointer, щоб він вказував на nNumber. Далі починаються проблеми. Коли функція завершується, nNumber віддаляється, оскільки це локальна змінна. Локальні змінні завжди віддаляються, коли виконання програми виходить з блоку, де ці змінні були оголошені. Це означає, що коли функція SomeFunction завершується і виконання повертається в main(), змінна зникає. Таким чином pPointer вказує на ту область пам'яті, де була змінна, але яка вже не належить програмі. Якщо ви не зовсім зрозуміли, про що йде мова, ще раз прочитайте про локальні і глобальні змінні, а також про області визначення (scope). Ця концепція також дуже важлива.

Отже, як проблема може бути розв'язана? Відповідь - використанням техніки відомої як динамічне виділення пам'яті. Зверніть увагу, що в мові Cі такої техніки немає, а приклад нижче відноситься до C++.

Передача покажчиків у функції

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

#include <stdio.h>

void AddFive(int Number)

{

Number = Number + 5;

}

void main()

{

int nMyNumber = 18;

printf("My original number is %d\n", nMyNumber);

AddFive(nMyNumber);

printf("My new number is %d\n", nMyNumber);

}

Проте тут проблема в тому, що змінна Number, до якої ми звертаємося усередині функції, - це копія змінної nMyNumber, що передається у функцію. Таким чином, рядок Number = Number + 5 додає п'ять до копії змінної, залишаючи оригінальну змінну в main() незмінній. Спробуйте запустити програму, щоб переконатися в цьому.

Щоб позбавитися від цієї проблеми, ми можемо передавати у функцію покажчик на місце в пам'яті, де зберігається число, але тоді ми повинні поправити функцію, щоб вона приймала покажчик замість числа. Для цього змінимо void AddFive(int Number) на AddFive(int* Number) додаванням зірочки. Тут знову текст програми, з внесеними змінами. Зверніть увагу, що ми повинні переконатися, що передаємо у функцію адресу nMyNumber замість самого числа. Це зроблено за допомогою оператора &, який (як ви пам'ятаєте), читається як "отримати адресу".

#include <stdio.h>

void AddFive(int *Number)

{

*Number = *Number + 5;

}

void main()

{

int nMyNumber = 18;

printf("My original number is %d", nMyNumber);

AddFive(&nMyNumber);

printf("My new number is %d", nMyNumber);

}

Спробуйте придумати свій власний приклад для демонстрації цих можливостей покажчиків. Звернули увагу на важливість зірочки (*) перед Number у функції AddFive? Це необхідно для того, щоб вказати компілятору що ми хочемо додати 5 до числа на яке вказує змінна Number, а не додати 5 до самого покажчика.

Наступна програма міняє зміст двох змінних :

#include <stdio.h>

void Swap (int *pOne, int *pTwo){

int temp;

temp = *pOne;

*pOne = *pTwo;

*pTwo = temp;

}

void main()

{

int a = 1, b = 20;

printf("Original numbers is %d %d", a, b);

Swap(&a,&b);

printf("New numbers is %d %d", a, b);

}

Останнє зауваження з приводу функцій це те що ви можете повертати з них покажчики, це робиться так:

int *MyFunction();

В даному прикладі, MyFunction повертає покажчик на ціле число (int).

Покажчики на масиви

Ви також можете створювати покажчики які вказують на масиви. Це робиться так:

int *pArray;

int MyArray[6];

pArray = &MyArray[0];

Зверніть увагу, що замість написання &MyArray[0], ви можете просто написати MyArray. Це, звичайно ж, застосовано тільки до масивів унаслідок способу їх реалізації в мовах C/C++. За загальними правилами необхідно було б написати pArray = &MyArray, але це неправильно. Якщо ви так напишіть те отримаєте покажчик на покажчик на масив (не друкарська помилка), що ясно не те що вам потрібне.

Використання покажчиків на масиви

Якщо у вас є покажчик на масив, як його використовувати? Наприклад у вас є покажчик на масив цілих чисел (int[]). Покажчик спочатку вказуватиме на перше значення в масиві як показує наступний.

Приклад:

#include <stdio.h>

void main()

{

int Array[3];

Array[0] = 10;

Array[1] = 20;

Array[2] = 30;

int *pArray;

pArray = &Array[0];

printf("pArray points to the value %d\n", *pArray);

}

Для того, щоб перемістити покажчик до наступного елементу масиву, ми можемо зробити pArray++. Ми також можемо, як деякі з вас могли вже догадатися, зробити pArray+2, що пересуне покажчик відразу на 2 елементи. З чим треба бути обережним так це з верхньою межею масиву (в даному випадку це 3 елементи), тому що компілятор не може перевірити чи вийшли ви за межу масиву використовуючи покажчики. Ви легко можете отримати повний збій системи якщо будете не обережні. Ось ще один приклад, що цього разу показує три значення які ми встановили :

#include <stdio.h>

void main()

{

int Array[3];

Array[0] = 10;

Array[1] = 20;

Array[2] = 30;

int *pArray;

pArray = &Array[0];

printf("pArray points to the value %d\n", *pArray);

pArray++;

printf("pArray points to the value %d", *pArray);

pArray++;

printf("pArray points to the value %d\n", *pArray);

}

Ми також можемо рухати покажчик у будь-яку сторону, так pArray - 2 це 2 елементи від того місця куди вказує покажчик. Переконаєтеся що ви додаєте і віднімає значення покажчика, а не у значення на яке він вказує. Цей метод використання покажчиків і масивів понад усе корисний при використанні циклів, таких як for або while.

Помітимо так само, що якщо ми маємо покажчик на значення, наприклад int* pNumberSet, ми можемо звертатися до нього як до масиву. Ось приклад, pNumberSet[0] рівне *pNumberSet; а pNumberSet[1] рівно *(pNumberSet + 1).

Це не абсолютно повне керівництво по роботі з покажчиками. Є ще багато речей, які я міг би розкрити детальніше, таких як покажчики на покажчики, і тим, яких я не торкнувся взагалі, наприклад, функціональних покажчиків, які занадто складні для цієї статті. Так само є речі, які використовуються занадто рідко, щоб збивати початківців з пантелику великою кількістю деталей. От і все! Спробуйте запустити код представленый в цій статті і придумати ще які нибудь свої варіації і приклади. (За мотивами (с) Andrew Peace)

Практика

Описати процедуру AddRightDigit(D, K), що додає до цілого позитивного числа K справа цифру D (D -- вхідний параметр цілого типу, що лежить в діапазоні 0-9, K -- параметр цілого типу, що являється одночасно вхідним і вихідним). За допомогою цієї процедури послідовно додати до цього числа K справа ці цифри D1 і D2, виводячи результат кожного додавання.

Описати процедуру SortArray(A, N), виконуюче сортування за збільшенням речового масиву A розміру N. Масив A є вхідним і вихідним параметром. За допомогою цієї процедури відсортувати масиви A, B, C розміру NA, NB, NC відповідно.

Описати рекурсивну функцію Fact(N) речового типу, що обчислює значення факторіалу

N! = 1*2*...*N

(N > 0 -- параметр цілого типу). За допомогою цієї функції вичислити факторіали п'яти цих чисел.

Іспит

На кінець місяця студенти повинні знати:

- перехід від запису алгоритму у вигляді блок-схеми, до запису на мові Сі;

- принцип організації двовимірних і багатовимірних масивів, способи введення-виводу;

- способи сортування масивів і пошуку елементів масиву;

- принципи організації процедур і функцій, передачі ним параметрів і зони видимості змінних;

- принципи роботи рекурсивних підпрограм;

Уміти вирішувати завдання:

- створення і сортування багатовимірних масивів за певним законом;

- видалення елементів з масиву;

- модифікації двовимірних масивів;

- створення покажчиків на змінні і масиви, встановлювати і набувати їх значень;

- складання тексту програми з використанням процедур і функцій;

- написання рекурсивних підпрограм

Файли

Практика. «Вдосконалення роботи з масивами і функціями»

Описати рекурсивну функцію Fib1(N) цілого типу, обчислюючи N -й елемент послідовності чисел Фібоначчі (N -- ціле число) :

F1 = F2 = 1, FK = FK - 2 + FK - 1, K = 3, 4, .

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

Описати процедуру Split1(A, NA, B, NB, C, NC), що формує по речовому масиву A розміру NA два речові масиви B і C розміру NB і NC відповідно; при цьому масив B містить усі елементи масиву A з непарними порядковими номерами (1, 3, .), а масив C -- усі елементи масиву A з парними номерами (2, 4, ...). Масиви B і C і числа NB і NC є вихідними параметрами. Застосувати цю процедуру до цього масиву A розміру NA і вивести розмір і вміст отриманих масивів B і C.

Описати рекурсивну функцію MaxElem(A, N) цілого типу, яка знаходить максимальний елемент цілочисельного масиву A розміру N (1 < N < 10), не використовуючи оператор циклу. За допомогою цієї функції знайти максимальні елементи масивів A, B, C розміру NA, NB, NC відповідно.

Дана матриця розміру M х N. Упорядкувати її рядки так, щоб їх перші елементи утворювали зростаючу послідовність.



Лекція 13. Символьні рядки

Заміна усіх маленьких англійських букв в рядку відповідними великими

#include <stdio.h>

#include <stdlib.h>

long int leng (char *S){

int i;

for (i=0;S[i]!='';i++){}

return i;

}

void upcase (char *S){

int dist = 'a '-' A';

int i, N=leng(S);

printf ("%i", N);

for ( i=0;i<N;i++){

if (S[i]>'a' && S[i] <'z') S[i]=S[i]- dist;

printf ("S[%i]= %c %i", i, S[i],S[i]);

}

}

int main(int argc, char *argv[])

{char S[1000];

int N, i;

scanf ("%s", S);

upcase (S);

printf ("%s", S);

system("PAUSE");

return 0;

}

Практика

Даний символ C. Вивести два символи, перший з яких передує символу C в кодовій таблиці, а другою йде за символом C.

Дано парне число N (> 0) і символи C1 і C2. Вивести рядок довжини N, яка складається з символів C1 і C2, що чергуються, починаючи з C1.

Даний рядок. Підрахувати кількість цифр, що містяться в ній.

Даний рядок, що містить цифри і дужки трьох видів : «() », «[]», «{}». Якщо дужки розставлені правильно (тобто кожною відкриває відповідає закриваюча дужка того ж виду), то вивести число 0. Інакше вивести або номер позиції, в якій розташована перша помилкова дужка, або, якщо закриваючих дужок бракує, число - 1.



Лекція 14. Текстові файли

Практика.

Дано ім'я файлу і цілі позитивні числа N і K. Створити текстовий файл з вказаним ім'ям і записати в нього N рядків, кожна з яких складається з K символів «*» (зірочка).

Дано ім'я файлу і ціле число N (0 < N < 27). Створити текстовий файл з вказаним ім'ям і записати в нього N рядків : перший рядок повинен містити рядкову (тобто маленьку) латинську букву «a», друга, -- букви «ab», третя, -- букви «abc» і т. д.; останній рядок повинен містити N початкових рядкових латинських букв в алфавітному порядку.

Дано ціле число K і текстовий файл. Видалити з кожного рядка файлу перші K символів (якщо довжина рядка менше K, то видалити з неї усі символи).

Дано два текстові файли. Додати в кінець першого файлу вміст другого файлу.

Даний текстовий файл. Замінити в нім усі пропуски, що підряд йдуть, на один пропуск.

Файли з довільним доступом

Дано ім'я бінарного файлу і ціле число N (> 1). Створити файл цілих чисел цим ім'ям і записати в нього N перших позитивних парних чисел (2, 4, ...:).

Дано ім'я файлу цілих чисел. Знайти кількість елементів, що містяться в цьому файлі. Якщо файлу з таким ім'ям не існує, то вивести - 1.

На іспит студенти повинні знати:

- що таке символьний рядок;

- способи доступу до елементів символьного рядка;

- як організовані файли, типи файлів, як отримати доступ до файлів;

Уміти вирішувати завдання:

- створення рядків, строкових масивів роботи з окремими символами;

- зміни рядків видалення і вставки символів;

- створення, відкриття, зміни і видалення текстових і бінарних файлів;

- отримання даних з текстових і бінарних файлів;

- комбінувати роботу з функціями і файлами

Типи даних визначувані користувачем, ч.1

Створити структуру Fraction що містить два цілі поля: nom, denom. Структура призначена для зберігання чисельника і знаменника простій дробу. Створити функції що дозволяють: вводити, виводити, складати, віднімати, множити, ділити і скорочувати прості дроби.

Створити структуру Student що містить поля для зберігання наступної інформації : номер запису, ПІБ студента, курс, оцінки по трьох предметах, середня оцінка. Організувати функції: для введення-виведення структур на екран, у бінарний і в текстовий файл; для сортованого виводу (за абеткою, за оцінками, по номеру, по курсу); функцію пошуку студента із заданим ПІБ; відрахування (видалення) студента.

Типи даних визначувані користувачем

Створити динамічний масив цілого типу і довільного розміру за допомогою використання функцій розподілу пам'яті. Написати процедуру сортування такого масиву.

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

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

Динамічні структури даних

Дана адреса P2 структури типу TNode, що має поле Data цілого типу, а також поля Prev і Next типу TNode. Цей запис пов'язаний полями Prev і Next відповідно з попереднім і наступним записом того ж типу . Вивести значення полів Data попереднього і наступного запису, а також адреси P1 і P3 попередньої і наступної записів.

Дано число D і покажчик P0 на один з елементів не порожнього двох зв'язного списку. Вставити перед цим елементом списку новий елемент зі значенням D і вивести посилання на доданий елемент списку.

Размещено на Allbest.ru

...