Лекции по увод в програмирането



Изтегляне 0.96 Mb.
страница16/16
Дата25.07.2016
Размер0.96 Mb.
#5224
ТипЛекции
1   ...   8   9   10   11   12   13   14   15   16

19 декември

Пример:


Да се определи броя на символите, различни от ‘ ‘ и ‘\t’ в един низ;

int length (char *p)

{ int i; char c;

for (i=0, (c=*p)!=’\0’, p++)

if (c!=’ ‘ && c!= ‘\t’) i++;

return i;

}

Функция, която сравнява два низа сочени от p и q по брой на непразни символи и връща указател към по-дългия;


char *compare (char *p, char *q)

{ return ( ( length(p)>length(q) ) ? p : q ); }


32. Формални параметри и масиви.
float maxi (float c[], int n)

{ int i; float m = c[0];

for (i=1;i

if (m

return m;

}

void main ()



{ float mas[100], x;

int broi;

…

x = maxi (mas, broi);



…

}
указвайки името на масива в обръщението ние всъщност задаваме адреса към първия елемент на масива;

за масива c във функцията maxi ще се разпредели точно тази памет, където се намира адреса на първия елемент на mas;

когато ползваме c във функцията, то все едно работим с mas; ако вътре във функцията променяме c, то ние променяме и mas, т.е. имаме предаване по име;

вграденият начин за заместване на формални с фактически параметри масиви не предполага, че целият масив ще се запише в стека, а само адресът на първия елемент;
ние можем да запишем по друг начин функцията
float maxi (float *p, int n)

{ int i; float m = *p;

for (i=1;i

if (m<*++p) m = *p;

return m;

}

това е така, защото името на масива е указател към първия елемент и елементите на масива са разположени последователно в паметта;


и в двете реализации можем да запишем

int i = 4;

x = maxi (&mas[i], broi – i);

тогава на c[0] се съпоставя mas[i];


за двумерни и тримерни масиви:

функция за транспониране на матрици


#define DIM = 10 //дефиниране на константа със средствата на

//препроцесора

void trans (float [][DIM], float [][DIM]);

void main ()

{ float u[DIM][DIM], v[DIM][DIM];

…

trans (u, v);



…

}

void trans (float a[][DIM], float b[][DIM])



{ int m, n;

for (m=0;m

for (n=0;n

b[n][m] = a[m][n];

}
важното е, че формалните параметри са двумерни масиви, а фактическият параметър е името на съответния двумерен масив или указател към указател към началото на масива;

вместо двумерен масив, можем да използваме указател към указател;

например:

void fun (int i, int **p)

{ …

}

void main ()



{ int *a[10], k;

…

fun (k, a);



…

}
ако във функцията fun използваме **p – това е стойността, записана в адреса към който сочи първия указател в масива а (указателят а[0]);



7 януари

В двумерен масив от символен тип се записва текст; всеки ред е съобщение; да се преобразува към lowcase;

ще използваме функция tolower:

int tolower (int ch); нейният прототип се намира в заглавния файл ctype.h; функцията преобразува големи букви към малки, ако ch не е голяма буква нищо не се променя;


#include

#include

#define ROW 100

#define COL 200

void trans (char *p);

void main ()

{ char str[ROW][COL];

… //вход


for (int i = 0; i < ROW; i++)

trans (str[i]);

… //изход

}

void trans (char *p)



{ for (; *p != ‘\0’; p++)

*p = tolower (*p);

}
33. Указатели към функции.
Указателят към функция е променлива, която съдържа адреса на началото на кода на функцията (на машинен език); само такива стойности могат да се присвояват на указатели към функции;

пример:


int (*pf)();

по този начин дефинираме променливата pf като указател към функция, която няма параметри и връща резултат от тип int;

char (*qf)(int);

по този начин дефинираме променливата qf като указател към функция, която има един параметър от тип int и връща резултат от тип char;

double (*sf)(int, char);

по този начин дефинираме променливата sf като указател към функция, която има първи параметър от тип int, втори параметът от тип char и връща резултат от тип double;


скобите, които заграждат указателя са задължителни; иначе например

int *pf();

ще се разбере като прототип на функция с име pf без параметри, която връща резултат от тип указател към int;

когато прилагаме операция * към указател към функция, това значи да се предаде управлението към функцията (да се направи обръщение към нея);

пример:

int k, x;



int func ();

int (*pf)();

pf = func;

//името на функцията се разглежда като константен указател към //тази функция (то съдържа адреса на началото на функцията);

k = (*pf)(); //косвено обръщение към функцията;

x = func();//пряко обръщение към функцията;

//чрез указател към функция може да се извършва и директно //обръщение

k = pf();

//чрез името на функцията може да се извършва и косвено //обръщение

x = (*func)();


кръглите скоби отново са задължителни; иначе

например


k = *pf ();

ще се интерпретира по следния начин: резултатът от pf () ще се разгледа като адрес и на k ще се присвои стойността, записана в този адрес;


за указатели към функции няма смислено тълкуване да се прилага адресна аритметика;
Примерна програма:
#include

int suma (int, int);

int razlika (int, int);

void main ()

{ int (*funcptr)(int, int);

int var1 = 5, var2 = 20, ret;

funcptr = (var1 < var2)? suma: razlika;

ret = (*funcptr)(var1*var2, var2);

printf (“%d\n”, ret);

}

int suma (int a, int b)



{ return a+b; }

int razlika (int a, int b)

{ return a-b; }
Указатели към функции могат да бъдат елементи на съставни обекти, каквито са масивите;

например:

int (*array[])(int, int) = { suma, razlika } ;

можем да използваме този масив в горната програма:

ret = (*array[ (var1 < var2)? 0 : 1 ])(var1*var2, var2);

това е косвено обръщение;

ret = array[ (var1 < var2)? 0 : 1 ](var1*var2, var2);

това е пряко обръщение;


Едно важно приложение на указателите към функции – те позволяват функция да се предава като параметър;

например:

void fun (int a, int b, (*sfun)(int, int) )

{ int ret;

ret = (*sfun)(a, b);

printf (“%d\n”, ret);

}

void main ()



{ int var1 = 5, var2 = 20;

fun (var1*var2, var2, (var1

}
типични случаи на използване на указатели към функции:


    • таблица на преходи (елемент от ООП);

    • обработване на прекъсвания;

    • реализиране на менюта;

    • при приложения за избиране на различни алгоритми;

някои стандартни функции имат параметър указател към функция; например функцията qsort приема четвърти параметър указател към функция, която извършва сравнение на два елемента;


34. Функции с променлив брой параметри.
Езика C допуска да се използват променлив брой фактически параметри при обръщение към функция; признак за това, че една функция е с променлив брой параметри е многоточие в списъка на формалните параметри или в прототипа;

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

Пример:

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



#include

void example (int, …);

void main ()

{ int var1 = 5, var2 = 6, var3 = 7,

var4 = 8, var5 = 9;

example(2, var1);

example(3, var1, var2);

example(6, var1, var2, var3, var4, var5);

}

void example (int arg1, …)



{ int *ptr = &arg1;

printf (“Брой на параметрите: %d\n”, arg1);

for (; arg1; arg1--)

printf (“%d “, *ptr++);

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

9 януари

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

#include

void example (int, …);

void main ()

{ int var1 = 5, var2 = 6, var3 = 7,

var4 = 8, var5 = 9;

example (var1, 0);

example (var1, var2, 0);

example (var1, var2, var3, var4, var5, 0);

}

void example (int arg1, …)



{ int number = 1;

int *ptr = &arg1;

while (*ptr!=0)

{ printf (“%d “, *ptr++);

number++;

}

printf (“\nБроят е: %d\n”, number); }



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

в езика C има средства, които позволяват да се пропуснат тези особености; за да се използват трябва да се включи заглавният файл stdarg.h;


тип va_list – тип на указател към стека (дефиниран в stdarg.h);
макрос va_start (va_list ap, lastfix) – първият аргумент ap е от тип va_list, а вторият аргумент lastfix е името на последния фиксиран формален параметър; va_start дава начална стойност на указателя ap като адреса на първия формален параметър след последния фиксиран (lastfix);
макрос va_arg (va_list ap, type) – първият аргумент ap е указател към стека, а вторият аргумент type е типа на формалния параметър, към който сочи ap; този макрос връща като резултат стойността на съответния фактически параметър от тип type и увеличава ap да сочи към следващия формален параметър;
макрос va_end (va_list ap) – за извършване на завършителни действия по използването на указателя ap;
Важно: За да можем да работим с функции с променлив брой параметри, задължително трябва да има най-малко един фиксиран формален параметър;
#include

#include

void example (int, …);

#define EOL 0

void main ()

{ int var1 = 5, var2 = 6, var3 = 7,

var4 = 8, var5 = 9;

example (var1, EOL);

example (var1, var2, EOL);

example (var1, var2, var3, var4, var5, EOL);

}

void example (int arg1, …)



{ int number = 2, value;

printf (“%d “, arg1);

va_list ptr;

va_start (ptr, arg1);

while ( (value = va_arg (ptr, int)) != EOL )

{ printf (“%d “, value);

number++;

}

printf (“\nБроят е: %d\n”, number);



}
35. Рекурсивни функции.
Функция, която се обръща пряко или косвено към себе си се нарича рекурсивна; под косвено обръщение разбираме следното: една функция F1 се обръща към функция F2, която се обръща към F1;

при всяко рекурсивно обръщение в програмния стек се разпределя памет за параметрите и локалните променливи на функцията;

по-общо един обект е рекурсивен, ако частично се съдържа в себе си или е дефиниран с помощта на себе си; езика C поддържа две езикови конструкции, които позволяват да се реализират рекурсивни алгоритми – това са рекурсивни функции и структури с рекурсия;

Пример:


n! = 1. 2. … .n, n > 0,

n! = 1, n = 0; - итеративна дефиниция (не съдържа рекурсия);


n! = n*(n-1)!, n > 0

n! = 1, n = 0; - рекурсивна дефиниция;


long fact (int n)

{ if (n==0) return 1;

else return n*fact(n-1);

}
в общия случай рекурсията позволява да се пишат по-елегантни алгоритми и позволява лесно решаване на по-сложни задачи; рекурсията повишава ефективността на програмисткия труд;


обикновено рекурсивните програми са по-неефективни, изискват повече ресурси (памет, време); от итерация към рекурсия се преминава лесно, обратното е доста сложно (но винаги е възможно);
реализиране на обръщението fact (3);

при това обръщение рекурсивно се извършват обръщенията fact(2), fact(1), fact (0);

при изпълнението на fact (0) няма да последва рекурсивно задълбочаване, тъй като n става равно на 0; функцията ще върне стойност 1, след което ще приключи изпълнението на fact (0) и паметта разпределена в стека за n при това изпълнение ще се освободи;

след това се връщаме на обръщението fact (1), което връща стойност 1, паметта за n за това обръщение се изтрива от стека и отново се връщаме на по-горното обръщение и т.н. fact (3) връща стойност 6;


общо правило: когато реализираме рекурсия трябва да има гранични условия (условия за излизане от рекурсията), които задължително се достигат; в противен случай се получава зацикляне и програмата обикновено завършва с препълване на програмния стек;
рекурсивна функция за xn;
double sqr_or_pow (double x, int k = 2)

{ if (k==2) return x*x;

else return x*sqr_or_pow(x, k-1);

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

по този начин получаваме още един начин за използване на функция с променлив брой параметри;
проблем при реализацията на рекурсията в горната програма – губи се ефективност от това, че променливата x не се променя, но влиза в стека при всяко рекурсивно обръщение;

обикновено всички вътрешни променливи, които се използват само преди рекурсивното обръщение могат да се направят външни с цел да се повиши ефективността на програмата;



16 януари

Друг пример за рекурсия: рекурсивна програма, която чете низ от символи (до натискане на Enter) и го извежда в обратен ред;

#include

void niz()

{ int ch;

if ( (ch = getchar ()) != ‘\n’ )

{ niz();

putchar (ch);

}

}
при първото обръщение към niz в програмния стек ще се разпредели памет за локалната променлива ch; ако въведем низ ‘abc’ и натиснем Enter, на ch ще се присвои ‘a’, ‘a’  ‘\n’ и след това рекурсивно ще се извърши второ обръщение; при второто обръщение отново ще се разпредели памет за ch и ще му се присвои стойност ‘b’  ‘\n’; след това ще последва трето рекурсивно обръщение, при което на новата ch ще се присвои стойност ‘c’  ‘\n’ и ще последва рекурсивно четвърто обръщение; тук вече на новата ch ще се присвои стойност ‘\n’ и обръщението ще приключи, като се освободи паметта за ch; след това се връщаме на третото обръщение, където ch е ‘c’ и я отпечатваме, след което освобождаваме паметта за ch и приключваме третото обръщение; връщаме се на второто обръщение, отпечатваме ‘b’, след това на първото обръщение, отпечатваме ‘a’ и изпълнението на функцията приключва;



36. Стандартни функции за обработка на низове.

В езика C няма голям набор от средства за обработване на низове и обикновено обработката става със стандартните функции; техните прототипи са описани в заглавния файл string.h;

при работа с тези функции, задължение на програмиста е да задели достатъчно памет за обработваните низове;
по-често използвани функции:
char *strcat (char *str1, const char *str2);

функцията strcat добавя копие на низа, сочен от str2, в края на низа, сочен от str1 и връща указател към конкатенирания низ (str1);

тя реализира конкатенация на низове; функцията не променя str2, тъй като той е описан като константен формален параметър;

тази функция се използва и в следната модификация:

char *strncat(char *str1, const char *str2, size_t n);

в този случай функцията копира не повече от n символа от низа, сочен от str2 в края на низа, сочен от str1 и добавя нулев байт; тя отново връща указател към получения низ (str1);


int strcmp (const char *str1, const char *str2);

функцията strcmp сравнява два низа посимволно и връща цяло число число: 0 – ако съвпадат, < 0 – ако низът сочен от str1 е по-малък от низа сочен от str2, > 0 – ако низът сочен от str1 е по-голям от низа сочен от str2; сравняването на низовете започва с първия символ от двата низа и продължава със следващите съответни символи, докато те станат различни или докато не се стигне до края и на двата низа;

тази функция също има модификация:

int strncmp (const char *str1, const char *str2, size_t n);

тя сравнява не повече от n символа от двата низа;
Пример: Имаме масив от указатели към редове с текст; нека броят на редовете е n; трябва да се сортират по азбучен ред;
void sort ( char *str[], int n)

{ int i, change;

char *temp;

do {


change = 0;

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

if ( strcmp (s[i], s[i+1]) > 0 )

{ temp = s[i];

s[i] = s[i+1];

s[i+1] = temp;

change = 1;

}

} while (change);



}
char *strcpy (char *str1, const char *str2);

функцията strcpy копира низа, сочен от str2 в str1 включително и нулевия байт; функцията връща резултат указателя str1;

тази функция може има модификация:

char *strncpy (char *str1, const char *str2, size_t n);

тя копира не повече от n символа от низа, сочен от str2 в str1 и връща указателят str1; низа str1 може да не завършва с нулевия байт, ако дължината на str2 е по-голяма или равна на n;

Пример:


char str1[10];

char *str2 = “abcdefghi”;

strncopy (str1, str2, 3);\\str1 няма да завършва с нулев байт и той str1[3] = ‘\0’; \\трябва да се добави

*str2 = “ab”;

strncopy (str1, str2, 3); \\str1 ще завършва с нулев байт;
char *strchr (const char *str, int ch);

тази функция преглежда низа от ляво надясно и връща указател към първия срещнат символ ch; ако не открие такъв символ връща нулев указател; може да се търси и нулев байт;


size_t strlen (const char *str);

тази функция връща цяло число без знак, което е броят на символите в низа, сочен от str без да се брои нулевия байт в края на низа;

char *strstr (const char *str1, const char *str2);

тази функция връща указател към първото срещане на подниза, сочен от str2 в низа сочен от str1; ако низът сочен от str2 не е подниз на низа сочен от str1, функцията връща нулев указател;


Край

17.01.2002 г.

Изтегляне 0.96 Mb.

Сподели с приятели:
1   ...   8   9   10   11   12   13   14   15   16



©obuch.info 2024
отнасят до администрацията
    Начална страница
Автореферат
Анализ
Бизнес-план
Биография
Глава
Диплом
Доклад
Задача
Закон
Занятие
Заседание