Уроци по С++

**ivakavlad** · 10-20-2010, 23:03

Някои приложения на структурата от данни масив

Търсене на елемент в редица

Нека са дадени редица от елементи a0, a1, …, an-1, елемент x и релация r. Могат да се формулират две основни зaдачи, свързани с търсене на елемент в редицата, който да е в релация r с елемента x.
a) Да се намерят всички елементи на редицата, които са в релация r с елемента x.
б) Да се установи, съществува ли елемент от редицата, който е в релация r с елемента x.
Съществуват редица методи, които решават едната, другата или и двете задачи. Ще разгледаме метода на последователното търсене, чрез който магат да се решат и двете задачи. Методът се състои в следното: последователно се обхождат елементите на редицата и за всеки елемент се проверява дали е в релация r с елемента x. При първата задача процесът продължава до изчерпване на редицата, а при втората – до намиране на първия елемент ak (k = 0, 1, …, n-1), който е в релация r с x, или до изчерпване на редицата без да е намерен елемент с търсеното свойство.
Следващите четири задачи илюстрират този метод.

Задача 49. Дадени са редицата от цели числа a0, a1, …, an-1 (n ≥ 1) и цялото число x. Да се напише програма, която намира колко пъти x се съдържа в редицата.

В случая релацията r е операцията ==. Налага се всеки елемент на редицата да бъде сравнен с x, т.е. имаме задача от първия вид. Тя описва индуктивен цикличен процес.
Програма Zad49.cpp решава задачата.

Program Zad49.cpp
#include <iostream.h>
int main()
{int a[20];
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 20)
{cout << "Incorrect input! \n";
return 1;
}
int i;
for (i = 0; i <= n-1; i++)
{cout << "a[" <> a[i];
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
}
int x;
cout << "x= ";
cin >> x;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
int br = 0;
for (i = 0; i <= n-1; i++)
if (a[i] == x) br++;
cout << "number = " << br << "\n";
return 0;
}

Задача 50. Дадени са редицата от цели числа a0, a1, …, an-1 (n ≥ 1) и цялото число x. Да се напише програма, която проверява дали x се съдържа в редицата.

В този случай се изисква при първото срещане на елемент от редицата, който е равен на x, да се преустанови работата с подходящо съобщение. Броят на сравненията на x с елементите от редицата е ограничен отгоре от n, но не е известен.
Програма Zad50.cpp решава задачата. Фрагментът, реализиращ входа е същия като в Zad49.cpp и затова е пропуснат.

Program Zad50.cpp
#include <iostream.h>
int main()
{int a[20];
…
i = 0;
while (a[i] != x && i < n-1)
i++;
if (a[i] == x) cout << "yes \n";
else cout << "no \n";
return 0;
}

Обхождането на редицата става чрез промяна на стойностите на индекса i - започват от 0 и на всяка стъпка от изпълнението на тялото на цикъла се увеличават с 1. Максималната им стойност е n-1. При излизането от цикъла ще е в сила отрицанието на условието (a[i] != x && i < n-1), т.е. (a[i] == x || i == n-1). Ако е в сила a[i] == x, тъй като сме осигурили a[i] да е елемент на редицата, отговорът “yes” е коректен. В противен случай е в сила i == n-1, т.е. сканиран е и последният елемент на редицата и за него не е вярно a[i] == x. Това е реализирано чрез отговора “no” от алтернативата на условния оператор.
Фрагментът
i = -1;
do
i++;
while (a[i] != x && i < n-1);
if (a[i] == x) cout << "yes \n";
else cout << "no \n";
реализира търсенето чрез използване на оператора do/while.

Задача 51. Да се напише програма, която установява, дали редицата от цели числа a0, a1, ..., an-1 е монотонно намаляваща.

a) За решаването на задачата е необходимо да се установи, дали за всяко i (0 ≤ i ≤ n-2) е в сила релацията a[i] >= a[i+1]. Това може да се реализира като се провери дали броят на целите числа i (0≤i≤n-2), за които е в сила релацията a[i] ≥ a[i+1], е равен на n-1.
Програмата Zad51_1.cpp реализира този начин за проверка дали редица е монотонно намаляваща. Фрагментите, реализиращи въвеждането на n и масива a, са известни вече и затова са пропуснати.

Program Zad51_1.cpp
#include <iostream.h>
int main()
{int a[100];
// дефиниране и въвеждане на стойност на n
…
// въвеждане на масива а
…
int br = 0;
for (i = 0; i <= n-2; i++)
if (a[i] >= a[i+1]) br++;
if (br == n-1) cout << "yes \n";
else cout << "no \n";
return 0;
}

б) Задачата може да се сведе до търсене на i (i = 0, 1,..., n-2), така че ai < ai+1, т.е. до задача за съществуване.
Програма Zad51_2.cpp реализира този начин за проверка дали редица е монотонно намаляваща. Фрагментите, реализиращи въвеждането на n и масива a отново са пропуснати.

Program Zad51_2.cpp;
#include <iostream.h>
int main()
{int a[100];
//въвеждане на размерността n и масива a
…
i = 0;
while (a[i] >= a[i+1] && i < n-2) i++;
if (a[i] >= a[i+1]) cout << "yes \n";
else cout << "no \n";
return 0;
}
Решение б) е по-ефективно, тъй като при първото срещане на a[i], така че релацията a[i] < a[i+1] е в сила, изпълнението на цикъла завършва. Решение а) реализира последователно търсене е пълно изчерпване, а решение б) – задача за съществуване на елемент в редица, който е в определена релация с друг елемент (в случая съседния му).

Задача 52. Да се напише програма, която установява, дали редицата от цели числа a0, a1, ..., an-1 се състои от различни елементи.

a) За решаването на задачата е необходимо да се установи, дали за всяка двойка (i, j): 0 ≤ i ≤ n-2 и i+1 ≤ j ≤ n-1 е в сила релацията a[i] != a[j]. Това може да се постигне като се провери дали броят на двойките (i, j): 0 ≤ i ≤ n-2 и i+1 ≤ j ≤ n-1, за които е в сила релацията a[i] != a[j], е равен на n*(n-1)/2.
Програма Zad52_1.cpp реализира горната формулировка на задачата – търсене с пълно изчерпване. Фрагментите, реализиращи въвеждането на n и масива a отново са пропуснати.

Program Zad52_1.cpp
#include <iostream.h>
int main()
{int a[100];
//въвеждане на размерността n и масива a
…
int br = 0;
for (i = 0; i <= n-2; i++)
for (int j = i+1; j <= n-1; j++)
if (a[i] != a[j]) br++;
if (br == n*(n-1)/2) cout << "yes \n";
else cout << "no \n";
return 0;
}
б) Задачата може да се сведе до проверка за съществуване на двойка индекси (i, j): 0 ≤ i ≤ n-2 и i+1 ≤ j ≤ n-1, за които не е в сила релацията a[i] != a[j]. Програма Zad52_2.cpp решава задачата.

Program Zad52_2.cpp
#include <iostream.h>
int main()
{int a[100];
// въвеждане стойности на размерността n и масива a
…
i = -1;
int j;
do
{i++;
j = i+1;
while (a[i] != a[j] && j < n-1) j++;
} while (a[i] != a[j] && i < n-2);
if (a[i] != a[i+1]) cout << "yes \n";
else cout << "no \n";
return 0;
}
Решение б) е по-ефективно, тъй като при първото срещане на a[i] и a[j], така че релацията a[i] == a[j] е в сила, изпълнението на операторите за цикъл завършва. То реализира задача за съществуване на метода за търсене.

Сортиране на редица

Съществуват много методи за сортиране на редици от елементи. В тази глава ще разгледаме метода на пряката селекция и чрез него ще реализираме възходяща сортировка на редица.

Метод на пряката селекция

Разглежда се редицата a0, a1, …, an-1 и се извършват следните действия:
Намира се k, така че ak = min{a0, a1, …, an-1}.
Разменят се стойностите на ak и a0.
Така на първо място в редицата се установява най-малкият й елемент.
Разглежда се редицата a1, a2, …, an-1 и се извършват действията:
Намира се k, така че ak = min{a1, a2, …, an-1}.
Разменят се стойностите на ak и a1.
Така на второ място в редицата се установява следващият по големина елемент на редицата и т.н.
Разглежда се редицата an-2, an-1 и се извършват действията:
Намира се k, така че ak = min{an-2, an-1}.
Разменят се стойностите на ak и an-2.
Получената редица е сортирана във възходящ ред.

Задача 53. Да се сортира във възходящ ред по метода на пряката селекция числовата редица a0, a1, …, an-1 (n ≥ 1).

Програма Zad53.cpp решава задачата. Фрагментът за въвеждане стойности на размерността n и масива a отново е пропуснат.

Program Zad53.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[100];
...
int i;
for (i = 0; i <= n-2; i++)
{int min = a[i];
int k = i;
for (int j = i+1; j <= n-1; j++)
if (a[j] < min)
{min = a[j];
k = j;
}
int x = a[i]; a[i] = a[k]; a[k] = x;
}
for (i = 0; i <= n-1; i++)
cout << setw(10) << a[i];
cout << '\n';
return 0;
}

Сливане на редици

Сливането е вид сортиране. Нека са дадени сортираните във възходящ ред редици:
a0, a1, …, an-1
b0, b1, …, bn-1
Да се слеят редиците означава да се конструира нова, сортирана във възходящ ред редица, съставена от елементите на дадените редици. Осъществява се по следния начин:
- Поставят се “указатели” към първите елементи на редиците {ai} и {bj}.
- Докато има елементи и в двете редици, се сравняват елементите, сочени от “указателите”. По-малкият елемент се записва в новата редица, след което се прескача.
- След изчерпване на елементите на едната от дадените редици, елементите на другата от “указателя” (включително) се прехвърлят в новата редица.

Задача 54. Дадени са сортираните във възходящ ред редици:
a0, a1, …, an-1
b0, b1, …, bm-1
(n ≥ 1, m ≥ 1). Да се напише програма, която слива двете редици в редицата
c0, c1, …, ck-1.

Програма Zad54.cpp решава задачата.
Program Zad54.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[20];
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 20)
{cout << "Incorrect input! \n";
return 1;
}
int i;
for (i = 0; i <= n-1; i++)
{cout << "a[" <> a[i];
}
int b[10];
cout << "m= ";
int m;
cin >> m;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (m < 1 || m > 10)
{cout << "Incorrect input! \n";
return 1;
}
for (i = 0; i <= m-1; i++)
{cout << "b[" <> b[i];
}
int p1 = 0, p2 = 0;
int c[30];
int p3 = -1;
while (p1 <= n-1 && p2 <= m-1)
if (a[p1] <= b[p2])
{p3++;
c[p3] = a[p1];
p1++;
}
else
{p3++;
c[p3] = b[p2];
p2++;
}
if (p1 > n-1)
for (i = p2; i <= m-1; i++)
{p3++;
c[p3] = b[i];
}
else
for (i = p1; i <= n-1; i++)
{p3++;
c[p3] = a[i];
} // извеждане на редицата
for (i=0; i<=p3; i++)
cout << setw(10) << c[i];
cout << '\n';
return 0;
}

Разглежданите досега масиви се наричат едномерни. Те реализират крайни редици от елементи от скаларен тип. Възможно е обаче типът на елементите да е масив. В този случай се говори за многомерни масиви.

**ivakavlad** · 10-20-2010, 23:05

Многомерни масиви

Масив, базовият тип на който е едномерен масив, се нарича двумерен. Масив, базовият тип на който е двумерен масив, се нарича тримерен и т.н. На практика се използват масиви с размерност най-много 3.

Задаване на многомерни масиви

Нека Т e име или дефиниция на произволен тип, различен от псевдоним, void и функционален, size1, size2, …, sizen (n>1 е дадено цяло число) са константни изрази от интегрален или изброен тип с положителни стойности. T[size1][size2] … [sizen] е тип n-мерен масив от тип T. T се нарича базов тип за типа масив.
Примери:
int [5][3] е двумерен масив от тип int;
double [4][5][3] е тримерен масив от тип double;

Множество от стойности

Множеството от стойности на типа T[size1][size2] … [sizen] се състои от всички редици от по size1 елемента, които са произволни константи от тип T[size2] … [sizen]. Достъпът до елементите на редиците е пряк и се осъществява с помощта на индекс, като достъпът до първия елемент се осъществява с индекс със стойност 0, до последния – с индекс със стойност size1-1, а до всеки от останалите елементи – с индекс със стойност с 1 по-голяма от тази на индекса на предишния елемент. Елементите от множеството от стойности на даден тип многомерен масив са константите на този тип масив.
Примери:
1. Множеството от стойности на типа int[5][3] се състои от всички редици от по 5 елемента, които са едномерни масиви от тип int[3]. Достъпът до елементите на редиците се осъществява с индекс със стойности 0, 1, 2, 3 и 4.

0 1 2 0 1 2 0 1 2

int[5][3]

0 1 4

2. Множеството от стойности на типа double[4][5][3] се състои от всички редици от по 4 константи от тип double[5][3]. Достъпът до елементите на редиците се осъществява с индекс със стойности 0, 1, 2 и 3.

double[4][5][3]

0 1 2 3
където с констi (i = 0, 1, 2, 3) е означена произволна константа от тип double[5][3].
Променлива величина, множеството от допустимите стойности на която съвпада с множеството от стойности на даден тип масив, се нарича променлива от дадения тип масив или само масив. Фиг. 3 дава обобщение на синтаксиса на дефиницията на променлива от тип масив.

<дефиниция_на_променлива_от _тип_многомерен_масив> ::=
T <променлива>[size1][size2] … [sizen]; |
T <променлива>[size1][size2]…[sizen]
= {<редица_от_константи_от_ти� � T1>};|
T <променлива>[size1][size2]…[sizen]
= {<редица_от_константи_от_ти� � T>};

където
Т e име или дефиниция на произволен тип, различен от псевдоним, void и функционален;
Т1 е име на типа T[size2]…[sizen];
size1, size2, …sizen са константни изрази от интегрален или изброен тип със положителни стойности;
<променлива> ::= <идентификатор>
<редица_от_константи_от_ти� � T1> ::= <константa_от_тип Т1>|
<константа_от_тип Т1>, <редица_от_константи_от_ти� � Т1>
а <редица_от_константи_от_ти� � Т> се определя по аналогичен начин.

Фиг. 3.

Примери:
int x[10][20];
double y[20][10][5];
int z[3][2] = {{1, 3},
{5, 7},
{2, 9}};
int t[2][3][2] = {{{1, 3}, {5, 7}, {6, 9}},
{{7, 8}, {1, 8}, {-1, -4}};

Фрагментите
<променлива>[size1][size2] … [sizen],
<променлива>[size1][size2]…[sizen] ={<редица_от_константи_от_ти� � T1>}
<променлива>[size1][size2]…[sizen] ={<редица_от_константи_от_ти� � T>};
от дефиницията от Фиг. 3, могат да се повтарят. За разделител се използва символът запетая.
Примери:
int a[3][4], b[2][3][2] = {{{1, 2}, {3, 4}, {5, 6}},
{{7, 8}, {9, 0}, {1, 2}}};
double c[2][3] = {1, 2, 3, 4, 5, 6}, d[3][4][5][6];

При дефиницията с инициализация, от Фиг. 3., е възможно size1 да се пропусне. Тогава за стойност на size1 се подразбира броят на редиците от константи на най-външно ниво, изброени при инициализацията.
Пример: Дефиницията
int s[][2][3] = {{{1,2,3}, {4, 5, 6}},
{{7, 8, 9}, {10, 11, 12}},
{{13, 14, 15}, {16, 17, 18}}};
е еквивалентна на
int s[3][2][3] = {{{1,2,3}, {4, 5, 6}},
{{7, 8, 9}, {10, 11, 12}},
{{13, 14, 15}, {16, 17, 18}}};
Ако изброените константни изрази в инициализацията на ниво i са по-малко от sizei, останалите се инициализират с нулеви стойности.
Примери: Дефиницията
int fi[5][6] = {{1, 2}, {5}, {3, 4, 5},
{2, 3, 4, 5}, {2, 0, 4}};
е еквивалентна на
int fi[5][6] = { {1, 2, 0, 0, 0, 0},
{5, 0, 0, 0, 0, 0},
{3, 4, 5, 0, 0, 0},
{2, 3, 4, 5, 0, 0},
{2, 0, 4, 0, 0, 0}};
Вложените фигурни скобки не са задължителни. Следното инициализиране
int ma[4][3] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
е еквивалентно на
int ma[4][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}};
но е по-неясно.
Следващата дефиниция
int ma[4][3] = {{0}, {1}, {2}, {3}};
е еквивалентна на
int ma[4][3] = {{0, 0, 0 }, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}};
и е различна от
int ma[4][3] = {0, 1, 2, 3};
която пък е еквивалентна на
int ma[4][3] = {{0, 1, 2}, {3, 0, 0}, {0, 0, 0}, {0, 0, 0}};

Инициализацията е един начин за свързване на променлива от тип масив с конкретна константа от множеството от стойности на този тип масив. Друг начин предоставят т.нар. индексирани променливи. С всяка променлива от тип масив е свързан набор от индексирани променливи. Фиг. 4. обобщава техния синтаксис.

<индексирана_променлива> ::=
<променлива_от_тип_масив>[<индекс1>][<индекс2>][<индексn>]
където
<индексi> e израз от интегрален или изброен тип.
Всяка индексирана променлива е от базовия тип.

Фиг. 4.

Примери:
1. С променливата x, дефинирана по-горе, са свързани индексираните променливи
x[0][0], x[0][1], …, x[0][19],
x[1][0], x[1][1], …, x[1][19],
…
x[9][0], x[9][1], …, x[9][19],
които са от тип int.
2. С променливата y са свързани следните реални индексирани променливи:
y[i][0][0], y[i][0][1], …, y[i][0][4],
y[i][1][0], y[i][1][1], …, y[i][1][4],
…
y[i][9][0], y[i][9][1], …, y[i][9][4],
за i = 0, 1, …, 19.
Дефиницията на променлива от тип многомерен масив не само свързва променливата с множеството от стойности на указания тип, но и отделя 4B памет, в която записва адреса на първата индексирана променлива на масива. Останалите индексирани променливи се разполагат последователно след първата по по-бързото нарастване на по-далечните си индекси. За всяка индексирана променлива се отделя толкова памет, колкото базовият тип изисква. Следващият пример илюстрира по-подробно представянето.
Пример:
ОП
x

x[0] x[0][0] x[0][1] … x[0][19]
- - -

x[1] x[1][0] x[1][1] … x[1][19] …
- - -

x[9] x[9][0] x[9][1] … x[9][19]
- - -
като за всяка индексирана променлива са отделени 4B ОП, които са с неопределено съдържание, тъй като x не е дефинирана с инициализация. Освен това, чрез индексираните променливи x[0], x[1], ..., x[9] могат да се намерят адресите на x[0][0], x[1][0], ..., x[9][0] съответно, т.е.
cout << x[0] << x[1] << ... << x[9];
ще изведе адресите на x[0][0], x[1][0], ... и x[9][0].

Забележка: Двумерните масиви разполагат в ОП индексираните си променливи по по-бързото нарастване на втория индекс. Това физическо представяне се нарича представяне по редове. Тези масиви могат да бъдат използвани за реализация и работа с матрици и др. правоъгълни таблици.
Важно допълнение: При работа с масиви трябва да се има предвид, че повечето реализации не проверяват дали стойностите на индексите са в рамките на границите, зададени при техните дефиниции. Тази особеност крие опасност от допускане на труднооткриваеми грешки.

Често допускана грешка: В Паскал, Ада и др. процедурни езици, индексите на индексираните променливи се ограждат само в една двойка квадратни скобки и се отделят със запетаи. По навик, при програмиране на C++, често се използва същото означение. Това е неправилно, но за съжаление не винаги е съпроводено със съобщение за грешка, тъй като в езика C++ съществуват т.нар. comma-изрази. Използвахме ги вече в заглавните части на оператора за цикъл for. Comma-изразите са изрази, отделени със запетаи. Стойността на най-десния израз е стойността на comma-израза. Операцията за последователно изпълнение запетая е лявоасоциативна. Така 1+3, 8, 21-15 е comma-израз със стойност 6, а [1, 2] е comma-израз със стойност [2]. В C++ ma[1,2] означава адреса на индексираната променлива ma[2][0] (индексът [0] се добавя автоматично).

Задачи върху многомерни масиви

Задача 55. Да се напише програма, която въвежда елементите на правоъгълна матрица a[nxм] и намира и извежда матрицата, получена от дадената като всеки от нейните елементи е увеличен с 1.

Програма Zad55.cpp решава задачата.
Program Zad55.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[10][20];
// въвеждане на броя на редовете на матрицата
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 10)
{cout << "Incorrect input! \n";
return 1;
}
// въвеждане на броя на стълбовете на матрицата
cout << "m= ";
int m;
cin >> m;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (m < 1 || m > 20)
{cout << "Incorrect input! \n";
return 1;
}
// въвеждане на матрицата по редове
int i, j;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= m-1; j++)
{cout << "a[" <> a[i][j];
if (!cin)
{cout << "Error, Bad Input! \n";
return 1;
}
}
// конструиране на нова матрица b
int b[10][20];
for (i = 0; i <= n-1; i++)
for (j = 0; j <= m-1; j++)
b[i][j] = a[i][j] + 1;
// извеждане на матрицата b по редове
for (i = 0; i <= n-1; i++)
{for (j = 0; j <= m-1; j++)
cout << setw(6) << b[i][j];
cout << '\n';
}
return 0;
}

Забележка: За реализиране на операциите извеждане и конструиране се извърши обхождане на елементите на двумерен масив по редове.

Задача 56. Да се напише програма, която намира и извежда сумата от елементите на всеки стълб на квадратната матрица a[nxn].

Програма Zad56.cpp решава задачата. В нея въвеждането на матрицата и нейната размерност са пропуснати, тъй като са аналогични на тези от Zad55.cpp.
Program Zad56.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[10][10];
int n;
…
int i, j;
for (j = 0; j <= n-1; j++)
{int s = 0;
for (i = 0; i <= n-1; i++)
s += a[i][j]; // s = s + a[I][j]
cout << setw(10) << j << setw(10) << s << "\n";
}
return 0;
}
Реализирано е обхождане на масива по стълбове (първият индекс се изменя по-бързо).

Задача 57. Да се напише програмен фрагмент, който намира номерата на редовете на целочислената квадратна матрица a[nxn], в които има елемент, равен на цялото число x.
…
for (i = 0; i <= n-1; i++)
{j = -1;
do
j++;
while (a[i][j] != x && j < n-1);
if (a[i][j] == x) cout << setw(5) << i << '\n';
}
…
Фрагментът реализира последователно обхождане на всички редове на матрицата и за всеки ред проверява дали съществува елемент, равен на дадения елемент x.

Задача 58. Да се напише програмен фрагмент, който обхожда кватратната матрица a[nxn] по диагонали, започвайки от елемента a00, както е показано по-долу:
a00 a01 a02 … a0,n-1
a10 a11 a12 … a1,n-1
…
an-1,0 an-1,1 an-1,2 … an-1,n-1

…
int k;
for (k = 0; k <= n-1; k++)
{for (i = k; i >= 0; i--)
cout << "(" <= k-n+1; i--)
cout << "(" << i << ", "<< k-i << ") ";
cout << '\n';
}
…

Задача 59. Да се напише програмен фрагмент, който обхожда кватратната матрица a[nxn] по диагонали, започвайки от елемента an-1,0, както е показано по-долу:

a00 a01 a02 … a0,n-1
a10 a11 a12 … a1,n-1
…
an-2,0 an-2,1 an-2,2 … an-2,n-1
an-1,0 an-1,1 an-1,2 … an-1,n-1

…
int k;
for (k = n-1; k >= 0; k--)
{for (i = k; i <= n-1; i++)
cout << "(" <= 1-n; k--)
{for (i = 0; i <= n+k-1; i++)
cout << "(" << i << ", "<< i-k << ") ";
cout << '\n';
}
…

Задача 60. Да се напише програма, която:
а) въвежда по редове елементите на квадратната реална матрица A с размерност n x n;
б) от матрицата A конструира редицата B: b0, b2,..., bm-1, където m = n.n, при което първите n елемента на B съвпадат с елементите на първия стълб на A, вторите n елемента на B съвпадат с елементите на втория стълб на A и т.н., последните n елемента на B съвпадат с елементите на последния стълб на A;
в) сортира във възходящ ред елементите на редицата B;
г) образува нова квадратна матрица A с размерност n x n, като елементите от първия ред на A съвпадат с първите n елемента на B, елементите от втория ред на A съвпадат с вторите n елемента на B и т.н. елементите от n - тия ред на A съвпадат с последните n елемента на B;
д) извежда по редове новата матрица A.

Програма Zad60.cpp решава задачата.

Program Zad60.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[10][10];
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 10)
{cout << "Incorrect input! \n";
return 1;
}
// въвеждане на масива a
int i, j;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= n-1; j++)
{cout << "a[" << i<< "][" << j << "]= ";
cin >> a[i][j];
}
// извеждане на елементите на a по редове
for (i = 0; i <= n-1; i++)
{for (j = 0; j <= n-1; j++)
cout << setw(5) << a[i][j];
cout << "\n";
}
// развиване на матрицата a по стълбове
int b[100];
int m = -1;
for (j = 0; j <= n-1; j++)
for (i = 0; i <= n-1; i++)
{m++;
b[m] = a[i][j];
}
m++; // m е броя на елементите на редицата b
// извеждане на редицата b
for (i = 0; i <= m-1; i++)
cout << setw(5) << b[i];
cout << '\n';
// сортиране на b по метода на пряката селекция
for (i = 0; i <= m-2; i++)
{int k = i;
int min = b[i];
for (j = i+1; j <= m-1; j++)
if (b[j] < min)
{min = b[j];
k = j;
}
int x = b[i]; b[i] = b[k]; b[k] = x;
}
// извеждане на сортираната b
for (i = 0; i <= m-1; i++)
cout << setw(5) << b[i];
cout << '\n';
// конструиране на новата матрица a
m = -1;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= n-1; j++)
{m++;
a[i][j] = b[m];
}
// извеждане на матрицата a
for (i = 0; i <= n-1; i++)
{for (j = 0; j <= n-1; j++)
cout << setw(10) << a[i][j];
cout << '\n';
}
return 0;
}

**ivakavlad** · 10-20-2010, 23:07

Символни низове

Структура от данни низ

Логическо описание
Редица от краен брой символи, заградени в кавички, се нарича символен низ или само низ.
Броят на символите в редицата се нарича дължина на низа.
Примери: “xyz” е символен низ с дължина 3,
“This is a string.” е символен низ с дължина 17, а
“” е символен низ с дължина 0. Нарича се празен низ.
Низ, който се съдържа в даден низ се нарича негов подниз.
Пример: Низът “ is a s “ е подниз на низа “This is a string.”, а низът “ is a sing” не е негов подниз.
Конкатенация на два низа е низ, получен като в края на първия низ се запише вторият. Нарича се още слепване на низове.
Пример: Конкатенацията на низовете “a+b” и “=b+a” е низът “a+b=b+a”, а конкатенацията на “=b+a” с “a+b” е низът “=b+aa+b”. Забелязваме, че редът на аргументите е от значение.
Два символни низа се сравняват по следния начин: Сравнява се всеки символ от първия низ със символа от съответната позиция на втория низ. Сравнението продължава до намиране на два различни символа или до края на поне един от символните низове. Ако кодът на символ от първия низ е по-малък от кода на съответния символ от втория низ, или първият низ е изчерпен, приема се, че първият низ е по-малък от втория. Ако пък е по-голям или вторият низ е изчерпен – приема се, че първият низ е по-голям от втория. Ако в процеса на сравнение и двата низа едновременно са изчерпени, те са развни. Това сравнение се нарича лексикографско.
Примери: “abbc” е равен на “abbc”
“abbc” е по-малък от “abbcaaa”
“abbc” е по-голям от “aa”
“abbcc” е по-голям от “abbc”.

Физическо представяне
В ОП низовете се представят последователно.
Символни низове в езика C++

Съществуват два начина за разглеждане на низовете в езика C++:
като масиви от символи и
като указатели към тип char.
За щастие, те са семантично еквивалентни.
В тази част ще разгледаме символните низове като масиви от символи.
Дефиницията
char str1[100];
определя променливата str1 за масив от 100 символа, а
char str2[5] = {‘a’, ‘b’, ‘c’};
дефинира масива от символи str2 и го инициализира. Тъй като при инициализацията са указани по-малко от 5 символа, останалите се допълват с нулевия символ, който се означава със символа \0, а понякога и само с 0. Така последната дефиниция е еквивалентна на дефиниците:
char str2[5] = ‘a’, ‘b’, ‘c’, ‘\0’, ‘\0’};
char str2[5] = ‘a’, ‘b’, ‘c’, 0, 0};
Всички действия, които описахме, за работа с едномерни масиви, са валидни и за масиви от символи с изключение на извеждането. Операторът
cout << str2;
няма да изведе адреса на str2 (както беше при масивите от друг тип), а текста
abc
Има обаче една особеност. Ако инициализацията на променливата str2 е пълна и не завършва със символа \0, т.е. има вида
char str2[5] = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’};
операторът
cout << str2;
извежда текста
abcde<неопределено>

Имайки пред вид всичко това, бихме могли да напишем подходящи програмни фрагменти, които въвеждат, извеждат, копират, сравняват, извличат части, конкатенират низове. Тъй като операциите се извършват над индексираните променливи, налага се да се поддържа целочислена променлива, съдържаща дължината на низа.
В езика са дадени средства, реализиращи низа като скаларна структура. За целта низът се разглежда като редица от символи, завършваща с нулевия символ \0, наречен още знак за край на низ. Тази организация има предимството, че не е необходимо с всеки низ да се пази в променлива дължината му, тъй като знакът за край на низ позволява да се определи краят му.
Примери: Дефинициите
char m[5] = {‘a, ‘b’, ‘b’, ‘a’, ‘\0’};
char n[10] = {‘x’, ‘y’, ‘z’, ‘1’, ‘2’, ‘+’, ‘\0’};
свързват променливте от тип масив от символи m и n с низовете “abba” и “xyz12+” съответно. Знакът за край на низ ‘\0’ не се включва явно в низа.
Този начин за инициализация не е много удобен. Следните дефиниции са еквивалентни на горните.
char m[5] = “abba”;
char n[10] = “xyz12+”;
Забелязваме, че ако низ съдържащ n символа трябва да се свърже с масив от символи, минималната дължина на масива трябва да бъде n+1, за да се поберат n-те символа плюс символът \0.

Задаване на низове

Типът char[size], където size е константен израз от интегрален или изброен тип, може да бъде използван за задаване на тип низ с максимална дължина size-1.
Пример:
char[5] може да се използва за задаване на тип низ с максимална дължина 4.

Множество от стойности

Множеството от стойности на типа низ, зададен чрез char[size], се състои от всички низове с дължина 0, 1, 2, ..., size-1
Примери:
Множеството от стойности на типа низ, зададен чрез char[5] се състои от всички низове с дължина 0, 1, 2, 3 и 4.

множество от стойности
на тип низ, зададен чрез char[5]

2. Множеството от стойности на типа char[10] се състои от всички низове с дължина 0, 1, 2, ..., 9.
множество от стойности
на тип низ, зададен чрез char[10]

Елементите от множеството от стойности на даден тип низ са неговите константи. Например, “a+b=c-a*e” е константа от тип char[10].
Променлива величина, множеството от допустимите стойности на която съвпада с множеството от стойности на даден тип низ, се нарича променлива от този тип низ. Понякога ще я наричаме само низ.
Фиг. 5 определя дефиницията на променлива от тип низ.

<дефиниция_на_променлива_от _тип_низ> ::=
char <променлива>[size]; |
char <променлива>[size] = “<редица_от_символи>”;
char <променлива>[size] = {<редица_от_константни_изра� �и>};|
където
<променлива> ::= <идентификатор>
size е константен израз от интегрален или изброен тип със положителна стойност;
<редица_от_константни_израз и> ::= <константен_израз>|
<константен_израз>, <редица_от_константни_израз и>
като константните изрази са от тип char.
<редица_от_символи> ::= <празно>| <символ> |
<символ><редица_от_символи>
с максимална дължина size-1.

Фиг. 5.

Примери:
char s1[5];
char s2[10] = “x+y”;
char s3[8] = {‘1’, ‘2’, ‘3’, ‘\0’};

Ако редицата от константни изрази съдържа по-малко от size израза, може да не завършва със знака за край на низ. Системата автоматично го добавя. А ако съдържа точно size константни израза, задължително трябва да завършва със знака за край на низ \0, или само 0.
При дефиниция на низ с инициализация е възможно size да се пропусне. Тогава инициализацията трябва да съдържа символа ‘\0’ и за стойност на size се подразбира броят на константните изрази, изброени при инициализацията, включително ‘\0’. Ако size е указано и изброените константни изрази в инициализацията са по-малко от size, останалите се инициализират с ‘\0’.

Примери:
Дефиницията
char q[5] = {‘a’, ‘b’};
е еквивалентна на
char q[5] = {‘a’, ‘b’, ‘\0’, ‘\0’, ‘\0’};
и на
char q[5] = “ab”;
а
char r[] = {‘a’, ‘b’, ‘\0’}; или
char r[] = “ab”;
са еквивалентни на
char r[3] = {‘a’, ‘b’, ‘\0’}; или
char r[3] = “ab”;
Забележка: Не са възможни конструкции от вида:
char q[5];
q = {‘a’, ‘v’, ‘s’}; или
char r[5];
r = “avs”;
т.е. на променлива от тип низ не може да бъде присвоявана константа от тип низ.
Недопустими са също дефиниции от вида:
char q[4] = {‘a’, ‘s’, ‘d’, ‘f’, ‘g’, ‘h’}; или
char q[];

Инициализацията е един начин за свързване на променлива от тип низ с конкретна константа от множеството от стойности на този тип низ. Друг начин предоставят индексираните променливи.
Примери:
q[0] = ‘a’; q[1] = ‘s’; q[2] = ‘d’;
Дефиницията на променлива от тип низ не само свързва променливата с множеството от стойности на указания тип, но и отделя определено количество памет (обикновено 4B), в която записва адреса на първата индексирана променлива, свързана с променливата от тип низ. Останалите индексирани променливи се разполагат последователно след първата. За всяка индексирана променлива се отделя по 1B ОП. Съдържанието на отделената за индексираните променливи памет е неопределено освен ако не е зададена дефиниция с инициализация. Тогава в клетките се записват инициализиращите стойности, допълнени със знака за край на низ.
Пример: След дефиницията
char s[4];
char w[10] = “abba”;
разпределението на паметта има вида:
ОП
s s[0] s[1] s[2] s[3]
- - - -

w w[0] w[1] w[2] w[3] w[4] w[5] ... w[9] …
97 98 98 97 0 0 0

Операции и вградени функции

Въвеждане на стойност

Реализира се по стандартния начин - чрез оператора cin.
Пример:
char s[5], t[3];
cin >> s >> t;
Настъпва пауза в очакване да се въведат два низа с дължина не по-голяма от 4 в първия и не по-голяма от 2 във втория случай. Водещите интервали, табулации и преминаване на нов ред се пренебрегват. За разделител на низовете се използват интервалът, табулациите и знака за преминаване на нов ред. Знакът за край на низ автоматично се добавя в края на всяка от въведените знакови комбинации. При въвеждане на низовете не се извършва проверка за достигане на указаната горна граница. Това може да доведе до труднооткриваеми грешки.

Извеждане на низ

Реализира се също по стандарния начин.
Пример:
Операторът
cout << s;
извежда низа, който е стойност на s. Не е нужно да се грижим за дължината му. Знакът за край на низ идентифицира края на му.

Дължина на низ

Намира се чрез функцията strlen.
Синтаксис
strlen(<str>)
където
<str> е произволен низ.
Семантика
Намира дължината на <str>.
Пример:
strlen(“abc”) намира 3, strlen(“”) намира 0.
За използване на тази функция е необходимо да се включи заглавният файл string.h.

Конкатенация на низове

Реализира се чрез функцията strcat.
Синтаксис
strcat(<var_str>, <str>)
където
<var_str> е променлива от тип низ, а
<str> е низ (константа, променлива или по-общо израз).
Семантика
Конкатенира низа, който е стойност на <var_str> с низа <str>. Резултатът от конкатенацията се връща от функцията, а също се съдържа в променливата <var_str>. За използване на тази функция е необходимо да се включи заглавният файл string.h.

Пример:
#include <iostream.h>
#include <string.h>
int main()
{char a[10];
cout << "a= ";
cin >> a; // въвеждане на стойност на a
char b[4];
cout << "b= ";
cin >> b; // въвеждане на стойност на b
strcat(a, b); // конкатениране на a и b, резултатът е в a
cout << a << ‘\n’; // извеждане на a
cout << strlen(strcat(a, b)) << '\n'; //повторна конкатенация
return 0;
}
Забележка: Функцията strcat може да се използва и като оператор, и като израз.

Сравняване на низове

Реализира се чрез функцията strcmp.
Синтаксис
strcmp(<str1>, <str2>)
където
<str1> и <str2> са низове (константи, променливи или по-общо изрази).
Семантика
Низовете <str1> и <str2> се сравняват лексикографски. Функцията strcmp е целочислена. Резултатът от обръщение към нея е цяло число с отрицателна стойност (-1 за реализацията Visual C++ 6.0), ако <str1> е по-малък от <str2>, 0 – ако <str1> е равен на <str2> и с положителна стойност (1 за реализацията Visual C++ 6.0), ако <str1> е по-голям от <str2>.
За използване на strcmp е необходимо да се включи заглавният файл string.h.

Примери:
1. char a[10] = “qwerty”, b[15] = “qwerty”;
if (!strcmp(a, b)) cout << “yes \n”; else cout << “no \n”;
извежда yes, тъй като strcpm(a, b) връща 0 (низовете са равни), !strcmp(a, b) e 1 (true).
2. char a[10] = “qwe”, b[15] = “qwerty”;
if (strcmp(a, b)) cout << “yes \n”; else cout << “no \n”;
извежда yes, тъй като strcpm(a, b) връща -1 (a е по-малък от b).
3. char a[10] = “qwerty”, b[15] = “qwer”;
if (strcmp(a, b)) cout << “yes \n”; else cout << “no \n”;
извежда yes, тъй като strcpm(a, b) връща 1 (a е по-голям от b).

Копиране на низ

Реализира се чрез функцията strcpy.
Синтаксис
strcpy(<var_str>, <str>)
където
<var_str> е променлива от тип низ, а
<str> е низ (константа, променлива или по-общо израз).
Семантика
Копира <str1> в <var_str>. Ако <str1> е по-дълъг от допустимата за <val_str> дължина, са възможни труднооткриваеми грешки. Резултатът от копирането се връща от функцията, а също се съдържа в <var_str>.
За използване на тази функция е необходимо да се включи заглавният файл string.h.
Пример: Програмният фрагмент
char a[10];
strcpy(a, "1234567");
cout << a << "\n";
извежда
1234567

Търсене на низ в друг низ

Реализира се чрез функцията strstr.
Синтаксис
strstr(<str1>, <str2>)
където
<str1> и <str2> са произволни низове (константи, променливи или по-общо изрази).
Семантика
Търси <str2> в <str1>. Ако <str2> се съдържа в <str1>, strstr връща подниза на <str1> започващ от първото срещане на <str2> до края на <str1>. Ако <str2> не се съдържа в <str1>, strstr връща “нулев указател”. Последното означава, че в позиция на условие, функционалното обръщение ще има стойност false, но при опит за извеждане, ще предизвиква грешка.
За използване на тази функция е необходимо да се включи заглавният файл string.h.
Примери: Програмният фрагмент
char str1[15] = "asemadaemada", str2[10]= "ema";
cout << strstr(str1, str2) << "\n";
извежда
emadaemada
а
char str1[15] = "asemadaemada", str2[10]= "ema";
cout << strstr(str2, str1) << "\n";
предизвиква съобщение за грешка по време на изпълнение.

Преобразуване на низ в цяло число

Реализира се чрез функцията atoi.
Синтаксис
atoi(<str>)
където <str> е произволен низ (константа, променлива или по-общо израз от тип низ).
Семантика
Преобразува символния низ в число от тип int. Водещите интервали, табулации и знака за преминаване на нов ред се пренебрегват. Символният низ се сканира до първия символ различен от цифра. Ако низът започва със символ различен от цифра и знак, функцията връща 0.
За използване на тази функция е необходимо да се включи заглавният файл stdlib.h.

Примери:
Програмният фрагмент
char s[15] = "-123a45";
cout << atoi(s) << "\n";
извежда –123, а
char s[15] = "b123a45";
cout << atoi(s) << "\n";
извежда 0.

Преобразуване на низ в реално число

Реализира се чрез функцията atof.
Синтаксис
atof(<str>)
където <str> е произволен низ (константа, променлива или по-общо израз от тип низ).
Семантика
Преобразува символния низ в число от тип double. Водещите интервали, табулации и знака за преминаване на нов ред се пренебрегват. Символният низ се сканира до първия символ различен от цифра. Ако низът започва със символ различен от цифра, знак или точка, функцията връща 0.
За използване на тази функция е необходимо да се включи заглавният файл stdlib.h.

Примери:
Програмният фрагмент
char s[15] = "-123.35a45";
cout << atof(st) << "\n";
извежда –123.35, а
char st[15] = ".123.34c35a45";
cout << atof(st) << "\n";
извежда 0.123.

Допълнение:

Конкатенация на n символа от низ с друг низ

Реализира се чрез функцията strncat.
Синтаксис
strncat(<var_str>, <str>, n)
където
<var_str> е променлива от тип низ,
<str> е низ (константа, променлива или по-общо израз), а
n е цял израз с неотрицателна стойност.
Семантика
Копира първите n символа от <str> в края на низа, който е стойност на <var_str>. Копирането завършва когато са прехвърлени n символа, или е достигнат краят на <str>. Резултатът е в променливата <var_str>. За използване на тази функция е необходимо да се включи заглавният файл string.h.

Пример: Резултатът от изпълнението на фрагмента:
chat a[10] = “aaaaa”;
strncat(a, “qwertyqwerty”, 5);
cout << a;
е
aaaaaqwert
а на
strncat(a, “qwertyqwerty”, -5);
cout << a;
предизвиква съобщение за грешка.

Копиране на n символа в символен низ

Реализира се чрез функцията strncpy.
Синтаксис
strncpy(<var_str>, <str>, n)
където
<var_str> е променлива от тип низ,
<str> е низ (константа, променлива или по-общо израз), а
n е цял израз с неотрицателна стойност.
Семантика
Копира първите n символа на <str1> в <var_str>. Ако <str> има по-малко от n символа, ‘\0’ се копира до тогава докато не се запишат n символа. Параметърът <var_str> трябва да е от вида char[n] и съдържа резултатния низ. За използване на тази функция е необходимо да се включи заглавният файл string.h.
Примери: 1. Програмният фрагмент
char a[10];
strncpy(a, "1234567",

;
cout << a << "\n";
извежда
1234567
Изпълнява се по следния начин: тъй като дължината на низа “1234567” е по-малка от 8, допълва се с един знак ‘\0’ и се свързва с променливата a.
2. Програмният фрагмент
char a[10];
strncpy(a, "123456789", 5);
cout << a << "\n";
извежда
12345<неопределено>
Изпълнява се по следния начин: тъй като дължината на низа “123456789” е по-голяма от 5, низът “12345” се свързва с променливата a, но не става допълване с ‘\0’, което личи по резултата.

Сравняване на n символа на низове

Реализира се чрез функцията strncmp.
Синтаксис
strncmp(<str1>, <str2>, n)
където
<str1> и <str2> са низове (константи, променливи или по-общо изрази), а
n е цял израз с неотрицателна стойност.
Семантика
Сравнява първите n символа на <str1> със символите от съответната позиция на <str2>. Сравнението продължава до намиране на два различни символа или до края на един от символните низове.
Резултатът от функцията strncmp е цяло число с отрицателна стойност, ако <str1> е по-малък от <str2>, 0 – ако <str1> е равен на <str2> и с положителна стойност, ако <str1> е по-голям от <str2>.
За използване на strncmp е необходимо да се включи заглавният файл string.h.

Примери:
1. char a[10] = “qwer”, b[15] = “qwerty”;
if (!strncmp(a, b, 3)) cout << “yes \n”;
else cout << “no \n”;
извежда yes, тъй като strncpm(a, b) връща 0 (низовете са равни), !strncmp(a, b) e 1 (true).
2. char a[10] = “qwer”, b[15] = “qwerty”;
if (strncmp(a, b, 5)) cout << “yes \n”;
else cout << “no \n”;
извежда yes, тъй като strncpm(a, b) връща -1 (a е по-малък от b).
3. char a[10] = “qwerty”, b[15] = “qwer”;
if (strncmp(a, b, 5)) cout << “yes \n”;
else cout << “no \n”;
извежда yes, тъй като strncpm(a, b) връща 1 (a е по-голям от b).

Търсене на символ в низ

Реализира се чрез функцията strchr, съдържаща се в string.h.
Синтаксис
strchr(<str>, <expr>)
където
<str> е произволен низ, а
<expr> e израз от интегрален или изброен тип с положителна стойност, означаваща ASCII код на символ.
Семантика
Търси първото срещане на символа, чийто ASCII код е равен на стойността на <expr>. Ако символът се среща, функцията връща подниза на <str> започващ от първото срещане на символа и продължаващ до края му. Ако символът не се среща - връща “нулев указател”. “нулев указател”. Последното означава, че в позиция на условие, функционялното обръщение ще има стойност false, но при опит за извеждане, ще предизвика грешка.
Примери: Операторът
cout << strchr(“qwerty”, ‘e’);
извежда
erty
Операторът
cout << strchr(“qwerty”, ‘p’);
извежда съобщение за грешка, а
if (strchr(“qwerty”, ‘p’)) cout << “yes \n”; else cout << “no \n”;
извежда no, тъй като ‘p’ не се среща в низа “qwerty”.

Търсене на първата разлика

Реализира се чрез функцията strspn.
Синтаксис
strspn(<str1>, <str2>)
където
<str1> и <str2> са произволни низове (константи, променливи или по-общо изрази).
Семантика
Проверява до коя позиция <str1> и <str2> съвпадат. Връща дължината на префикса до първия различен символ. За използване на тази функция е необходимо да се включи заглавният файл string.h.
Пример: Програмният фрагмент
char a[10]= "asdndf", b[15] = "asdsdfdhf";
cout << strspn(a, b) << "\n";
извежда 3 тъй като първият символ, по който се различават a и b е в позиция 4.

**ivakavlad** · 10-20-2010, 23:07

Задачи

Задача 1. Да се напише програма, която намира скаларното произведение на реалните вектори a = (a0, a1, ..., an-1) и b = (b0, b1,..., bn-1), (1 ≤ n ≤ 50).
Задача 2. Да се напише програма, която въвежда n символа и намира и извежда минималния (максималния) от тях.
Задача 3. Да се напише програма, която:
а) въвежда редицата от n цели числа a0, a1, ..., an-1,
б) намира и извежда сумата на тези елементи на редицата, които се явяват удвоени нечетни числа.
Задача 4. Да се напише програма, която намира и извежда сумата от положителните и броя на отрицателните елементи на редицата от реални числа a0, a1, ..., an-1 (1 ≤ n ≤ 30).
Задача 5. Да се напише програма, която изчислява реципрочното число на произведението на тези елементи на редицата a0, a1, ..., an-1 (1 ≤ n ≤ 50), за които е в сила релацията 2 < аi < i!.
Задача 6. Да се напише програма, която изяснява, има ли в редицата от цели числа a0, a1, ..., an-1 (1 ≤ n ≤ 100) два последователни нулеви елемента.
Задача 7. Дадени са сортираните във възходящ ред числови редици a0, a1, ..., ak-1 и b0, b1, ..., bk-1 (1 ≤ k ≤ 40). Да се напише програма, която намира броя на равенствата от вида ai = bj (i = 0, ..., k-1, j = 0, ..., k-1).
Задача 8. Дадени са две редици от числа. Да се напише програма, която определя колко пъти първата редица се съдържа във втората.
Задача 9. Всяка редица от равни числа в едномерен сортиран масив, се нарича площадка. Да се напише програма, която намира началото и дължината на най-дългата площадка в даден сортиран във възходящ ред едномерен масив.
Задача 10. Да се напише програма, която по дадена числова редица a0, a1, ..., an-1 (1 ≤ n ≤ 20) намира дължината на максималната й ненамаляваща подредица ai1, ai2, ..., aiк (ai1 <= ai2 <= ... <= aiк, i1 < i2 < ... < iк).
Задача 11. Дадена е редицата от символи s0, s1, ..., sn-1 (1 ≤ n ≤ 15). Да се напише програма, която извежда отначало всички символи, които изобразяват цифри, след това всички символи, които изобразяват малки латински букви и накрая всички останали символи от редицата, запазвайки реда им в редицата.
Задача 12. Дадени са две цели числа, представени с масиви от символи. Да се напише програма, която установява дали първото от двете числа е по-голямо от второто.
Задача 13. Да се напише програма, която определя дали редицата от символи s0, s1, ..., sn-1 (1 ≤ n ≤ 45) е симетрична, т.е. четена отляво надясно и отдясно наляво е една и съща.
Задача 14. Дадена е редицата от естествени числа a0, a1, ..., an-1 (1 ≤ n ≤ 30). Да се напише програма, която установява има ли сред елементите на редицата не по-малко от два елемента, които са степени на 2.
Задача 15. Дадени са полиномите Pn(x) и Qm(x). Да се напише програма, която намира:
а) сумата им
б) произведението им.
Задача 16. За векторите a = (a0, a1, ..., an-1) и b = (b0, b1, ..., bn-1) (1 ≤ n ≤ 20), да се определи дали са линейно зависими.
Задача 17. Дадена е квадратна целочислена матрица A с размерност nxn, елементите на която са естествени числа. Да се напише програма, която намира:
а) сумата от елементите под главния диагонал, които са прости числа;
б) произведението от елементите над главния диагонал, в записа на цифрите на които се среща цифрата 5;
в) номера на първия неотрицателен елемент върху главния диагонал.
Задача 18. Дадена е квадратната реална матрица A с размерност nxn. Да се напише програма, която намира:
а) сумата от елементите върху вторичния главен диагонал;
б) произведението от елементите под (над) вторичния главен диагонал.
Задача 19. Дадена е реална правоъгълна матрица A с размерност nxm. Да се напише програма, която изтрива k-ти ред (стълб) на A. Изтриването означава да се преместят редовете (стълбовете) с един нагоре (наляво) и намаляване броя на редовете (стълбовете) с един.

Задача 20. Върху равнина са дадени n точки чрез матрицата

така, че (x0,i, x1,i) са координатите на i-тата точка. Точките по двойки са съединени с отсечки. Да се напише програма, която намира дължината на най-дългата отсечка.

Задача 21. Дадена е матрицата от цели числа

Да се напише програма, която намира сумата на тези елементи a1,i, (0 ≤ i ≤ n-1), за които a0,i имат стойността на най-голямото сред елементите от първия ред на матрицата.
Задача 22. Дадено е множеството M от двойки
M = {<x0, y0>, <x1, y1>, ..., <xn-1, yn-1>},
като xi и yi (0 ≤ i ≤ n-1) са цели числа. Да се напише програма, която проверява дали множеството M дефинира функция.
Упътване: Множеството M дефинира функция, ако от xi = xj следва yi = yj.

Задача 23. Да се напишат програми, която конструират матриците:

Задача 24. Дадена е целочислената квадратна матрица A от n-ти ред. Да се напише програма, която намира максималното от простите числа на А.
Задача 25. Казваме, че два стълба на една матрица си приличат, ако съвпадат множествата от числата, съставящи стълбовете. Да се напише програма, която намира номерата на всички стълбове на матрицата Anxm, които си приличат.
Задача 26. Матрицата А има седлова точка в a[i, j], ако a[i, j] е минимален елемент в i-я ред и максимален елемент в j-я стълб на A. Да се напише програма, която намира всички седлови точки на дадена матрица А.
Задача 27. Матрицата А има седлова точка в a[i, j], ако a[i, j] е минимален елемент в i-я ред и максимален елемент в j-я стълб на A. Да се напише програма, която установява дали съществува седлова точка в дадена матрица A.
Задача 28. Дадена е квадратна матрица A от n-ти ред. Да се напише програма, която установява дали съществува k (0 ≤ k ≤ n-1), така че k-я стълб на А да съвпада с k-я й ред.
Задача 29. Дадена е реалната квадратна матрица Anxn. Да се напише програма, която намира:
а) max { min {aij}} в) min{ max {aij}}
0≤i≤n-1 0≤j≤n-1 0≤i≤n-1 0≤j≤n-1
б) max{ min {aij}} г) min{ max {aij}}
0≤j≤n-1 0≤i≤n-1 0≤j≤n-1 0≤i≤n-1
Задача 30. Дадена е квадратната матрица Anxn (2 ≤ n ≤ 10). Да се напише програма, която определя явява ли се A ортонормирана, т.е. такава, че скаларното произведение на всеки два различни реда на A е равно на 0, а скаларното произведение на всеки ред на себе си е равно на 1?
Задача 31. Да се напише програма, която определя явява ли се квадратната матрица Anxn магически квадрат, т.е. такава, че сумата от елементите от всички редове и стълбове е еднаква.
Задача 32. Дадена е система от линейни уравнения от n-ти ред. Да се напише програма, която я решава.
Задача 33. С тройката (i, j, v) се представя елемента v от i-я ред и j-я стълб на матрица. Две матрици с размерност nxn са представени като редици от тройки. Тройките са подредени по редове. Ако тройката (i, j, v) отсъства, приема се, че v = 0. Да се напише програма, която събира матриците и представя резултата като редица от тройки.

Допълнителна литература

1. Ст. Липман, Езикът C++ в примери, “КОЛХИДА ТРЕЙД” КООП, С. 1993.
2. К. Хорстман, Принципи на програмирането със C++, С., СОФТЕХ, 2000.
3. B. Stroustrup, C++ Programming Language. Third Edition, Addison – Wesley, 1997.

**ivakavlad** · 10-20-2010, 23:20

Глава 6

Типове указател и псевдоним

1. Тип указател

Променлива, това е място за съхранение на данни, което може да съдържа различни стойности. Идентифицира се с дадено от потребителя име (идентификатор). Има си и тип. Дефинира се като се указват задължително типът и името й. Типът определя броя на байтовете, в които ще се съхранява променливата, а също и множеството от операциите, които могат да се изпълняват над нея. Освен това, с променливата е свързана и стойност – неопределена или константа от типа, от който е тя. Нарича се още rvalue. Мястото в паметта, в което е записана rvalue се нарича адрес на променливата или lvalue. По-точно адресът е адреса на първия байт от множеството байтове, отделени за променливата.
Пример: Фрагментът
int i = 1024;
дефинира променлива с име i и тип int. Стойността й (rvalue) е 1024. i именува място от паметта (lvalue) с размери 4 байта, като lvalue е адреса на първия байт.

Намирането на адреса на дефинирана променлива става чрез унарния префиксен дясноасоциативен оператор & (амперсанд). Приоритетът му е същия като на унарните оператори +, -, !, ++, -- и др. Фиг. 1 описва оператора.

Синтаксис
&<променлива>
където <променлива> е вече дефинирана променлива.
Семантика
Намира адреса на <променлива>.

Фиг. 1.

Пример: &i е адреса на променливата i и може да се изведе чрез оператора cout << &i;
Операторът & не може да се прилага върху константи и изрази, т.е. &100 и &(i+5) са недопустими обръщения. Не е възможно също прилагането му и върху променливи от тип масив, тъй като те имат и смисъла на константни указатели.
Адресите могат да се присвояват на специален тип променливи, наречени променливи от тип указател или само указатели.

Задаване на тип указател

Нека T е име или дефиниция на тип. За типа T, T* е тип, наречен указател към T. T се нарича указван тип или тип на указателя.
Примери:
int* е тип указател към int;
enum {a, b, c}* е тип указател към enum {a, b, c}.

Множество от стойности

Състои се от адресите на данните от тип T, дефинирани в програмата, преди използването на T*. Те са константите на типа T*. Освен тях съществува специална константа с име NULL, наречена нулев указател. Тя може да бъде свързвана с всеки указател независимо от неговия тип. Тази константа се интерпретира като “сочи към никъде”, а в позиция на предикат е false.

Променлива величина, множеството от допустимите стойности, на която съвпада с множеството от стойности на типа T*, се нарича променлива от тип T* или променлива от тип указател към тип T. Дефинира се по стандартния начин. Фиг. 2 показва синтаксиса на дефиниция на променлива от тип указател.

Дефиниция на променлива от тип указател

T* <променлива> [= <стойност>]; |
T *<променлива> [= <стойност>];
където
T е име или дефиниция на тип;
<променлива> ::= <идентификатор>
<стойност> е шестнадесетично цяло число, представляващо адрес на данна от тип T или NULL.

Фиг. 2.

T определя типа на данните, които указателят адресира, а също и начина на интерпретацията им.
Възможно е фрагментите
<променлива> [=<стойност>] и
*<променлива>[=<стойност>]
да се повтарят. За разделител се използва запетаята. В първия случай обаче има особеност. Дефиницията
T* a, b;
е еквивалентна на
T* a;
T b;
т.е. само променливата a е указател.
Примери: Дефиницията
int *pint1, *pint2;
задава два указателя към тип int, а
int *pint1, pint2;
- указател pint1 към int и променлива pint2 от тип int.

Дефиницията на променлива от тип указател предизвиква в ОП да се отделят 4B, в които се записва някакъв адрес от множеството от стойности на съответния тип, ако дефиницията е с инициализация и неопределено или NULL, ако дефиницията не е с инициализация. (За реализацията Visual C++ 6.0 е неопределено). Този адрес е стойността на променливата от тип указател, а записаното на този адрес е съдържанието й.
Пример: Дефинициите
int i = 12;
int* p = &i; // p е инициализирано с адреса на i
double *q = NULL; // q е инициализирано с нулевия указтел
double x = 1.56;
double *r = &x; // r е инициализирано с адреса на x
предизвикват следното разпределение на паметта
ОП
i p q x r
12 0x00000000 1.56

Съвет: Всеки указател, който не сочи към конкретен адрес, е добре да се свърже с константата NULL. Ако по невнимание се опитате да използвате нулев указател, програмата ви може да извърши нарушение при достъп и да блокира, но това е по-добре, отколкото указателят да сочи към кой знай къде.

Операции и вградени функции

Извличане на съдържанието на указател

Осъществява се чрез префиксния, дясноасоциативен унарен оператор * (Фиг. 3).

Синтаксис
*<променлива_от_тип_указате� �>
Семантика
Извлича стойността на адреса, записан в <променлива_от_тип_ указател>, т.е. съдържанието на <променлива_от_тип_ указател>.

Фиг. 3.

Като използваме дефинициите от примера по-горе, имаме:
*p e 12 // 12 е съдържанието на p
*r е 1.56 // 1.56 е съдържанието на r
Освен, че намира съдържанието на променлива от тип указател, обръщението
*<променлива_от_тип_указате� �>
е данна от тип T (променлива или константа). Всички операции, допустими за типа T, са допустими и за нея.
Като използваме дефинициите от примера по-горе, *p и *r са цяла и реална променливи, съответно. След изпълнение на операторите за присвояване
*p = 20;
*r = 2.18;
стойността на i се променя на 20, а тази на r – на 2.18.

Аритметични и логически операции

Променливите от тип указател могат да участват като операнди в следните аритметични и логически операции +, -, ++, --, ==, !=, >, >=, < и <=. Изпълнението на аритметични операции върху указатели е свързано с някои особености, заради което аритметиката с указатели се нарича още адресна аритметика. Особеноста се изразява в т. нар. мащабиране. Ще го изясним чрез пример.
Да разгледаме фрагмента
int *p;
double *q;
...
p = p + 1;
q = q + 1;
Операторът p = p + 1; свързва p не със стойността на p, увеличена с 1, а с p + 1*4, където 4 е броя на байтовете, необходими за записване на данна от тип int (p е указател към int). Аналогично, q = q + 1; увеличава стойността на q не с 1, а с 8, тъй като q е указател към double (8 байта са необходими за записване на данна от този тип).
Общото правило е следното: Ако p е указател от тип T*, p+i е съкратен запис на p + i*sizeof(T), където sizeof(T) е функция, която намира броя на байтовете, необходими за записване на данна от тип Т.

Въвеждане

Не е възможно въвеждане на данни от тип указател чрез оператора cin. Свързването на указател със стойност става чрез инициализация или оператора за присвояване.

Извеждане

Осъществява се по стандартния начин - чрез оператора cout.

Допълнение
Типът, който се задава в дефиницията на променлива от тип указател, е информация за компилатора относно начина, по който да се интерпретира съдържанието на указателя. В контекста на горния пример *p са четири байта, които ще се интерпретират като цяло число от тип int. Аналогично, *q са осем байта, които ще се интерпретират като реално число от тип double.

Следващата програма илюстрира дефинирането и операциите за работа с указатели.
#include <iostream.h>
int main()
{int n = 10; // дефинира и инициализира цяла променлива
int* pn = &n; // дефинира и инициализира указател pn към n
// показва, че указателят сочи към n
cout << "n= " << n << " *pn= " << *pn << '\n';
// показва, че адресът на n е равен на стойността на pn
cout << "&n= "<< &n << " pn= " << pn << '\n';
// намиране на стойността на n чрез pn
int m = *pn; // == 10
// промяна на стойността на n чрез pn
*pn = 20;
// извеждане на стойността на n
cout << "n= " << n << '\n'; // n == 20
return 0;
}

В някои случаи е важна стойността на променливата от тип указател (адресът), а не нейното съдържание. Тогава тя се дефинира като указател към тип void. Този тип указатели са предвидени с цел една и съща променлива - указател да може в различни моменти да сочи към данни от различен тип. В този случай, при опит да се използва съдържанието на променливата от тип указател, ще се предизвика грешка. Съдържанието на променлива - указател към тип void може да се извлече само след привеждане на типа на указателя (void*) до типа на съдържанието. Това може да се осъществи чрез операторите за преобразуване на типове.
Пример:
int a = 100;
void* p; // дефинира указател към void
p = &a; // инициализира p
cout << *p; // грешка
cout << *((int*) p); // преобразува p в указател към int
// и тогава извлича съдържанието му.

В C++ е възможно да се дефинират указатели, които са константи, а също и указатели, които сочат към константи. И в двата случая се използва запазената дума const, която се поставя пред съответните елементи от дефинициите на указателите. Стойността на елемента, дефиниран като const (указателя или обекта, към който сочи) не може да бъде променяна.
Пример:
int i, j = 5;
int *pi; // pi е указател към int
int * const b = &i; // b е константен - указател към int
const int *c = &j; // c е указател към цяла константа.
b = &j; // грешка, b е константен указател
*c = 15; // грешка, *c е константа

**ivakavlad** · 10-20-2010, 23:21

2. Указатели и масиви

В C++ има интересна и полезна връзка между указателите и масивите. Тя се състои в това, че имената на масивите са указатели към техните “първи” елементи. Това позволява указателите да се разглеждат като алтернативен начин за обхождане на елементите на даден масив.

Указатели и едномерни масиви

Нека a е масив, дефиниран по следния начин:
int a[100];
Тъй като a е указател към а[0], *a е стойността на a[0], т.е. *a и a[0] са два различни записа на стойността на първия елемент на масива. Тъй като елементите на масива са разположени последователно в паметта, a + 1 е адреса на a[1], a + 2 е адреса на a[2] и т.н. a + n-1 е адреса на a[n-1]. Тогава *(a+i) е друг запис на a[i] (i = 0, 1, ..., n-1).
Има обаче една особеност. Имената на масивите са константни указатели. Заради това, някои от аритметичните операции, приложими над указатели, не могат да се приложат над масиви. Такива са ++, -- и присвояването на стойност.

Следващата програма показва два начина за извеждане на елементите на масив.
#include <iostream.h>
int main()
{int a[] = {1, 2, 3, 4, 5, 6};
for (int i = 0; i <= 5; i++)
cout << a[i] << '\n';
for (i = 0; i <= 5; i++)
cout << *(a+i) << '\n';
return 0;
}
Фрагментът
for (i = 0; i <= 5; i++)
{cout << *a << '\n';
a++;
}
съобщава за грешка заради оператора a++ (a е константен указател и не може да бъде променян). Може да се поправи като се използва помощна променлива от тип указател към int, инициализирана с масива a, т.е.
int* p = a;
for (i = 0; i <= 5; i++)
{cout << *p << '\n';
p++;
}
Използването на указатели е по-бърз начин за достъп до елементите на масива и заради това се предпочита. Индексираните променливи правят кода по-ясен и разбираем. В процеса на компилация всички конструкции от вида a[i] се преобразуват в *(a+i), т.е. операторът за индексиране [...] се обработва от компилатора чрез адресна аритметика. Полезно е да отбележим, че операторът [] е лявоасоциативен и с по-висок приоритет от унарните оператори (в частност от оператора за извличане на съдържание *).

Указатели и двумерни масиви

Името на двумерен масив е константен указател към първия елемент на едномерен масив от константни указатели. Ще изясним с пример казаното.
Нека a е двумерен масив, дефиниран по следния начин:
int a[10][20];
Променливата a е константен указател към първия елемент на едномерния масив a[0], a[1], ..., a[9], като всяко a[i] е константен указател към a[i][0] (i = 0,1, ..., 9), т.е.
a

a[0] a[0][0] a[0][1] … a[0][19]

a[1] a[1][0] a[1][1] … a[1][19] …

a[9] a[9][0] a[9][1] … a[9][19]

Тогава
**a == a[0][0]
a[0] == *a a[1] == a[0]+1 ... a[9] == a[0]+9,
т.е.
a[i] == a[0] + i == *a + i
Като използваме, че операторът за индексиране е лявоасоциативен, получаваме:
a[i][j] == (*a + i) [j] == *((*a + i) + j).

Задача 67. Да се напише програма, която въвежда по редове правоъгълна матрица Anxk от реални числа и извежда матрицата, образувана от редовете на A от в четна позиция, като всеки елемент е увеличен с 1, след което извежда матрицата, образувана от редовете от нечетна позиция, като всеки елемент е увеличен с 2 и накрая, ако n е четно, извежда сумата на матриците от редовете от четните и нечетните позиции на A.

Програма Zad67.cpp решава задачата.
Program Zad67.cpp
#include <iostream.h>
#include <iomanip.h>
int main()
{int a[20][100];
int* p[20];
int* q[20];
cout << "n, k = ";
int n, k;
cin >> n >> k;
if (!cin)
{cout << "Error! \n";
return 0;
}
int i, j;
for (i = 0; i <= n-1; i++)
for (j = 0; j <= k-1; j++)
{cout << "a[" <> *(*(a+i)+j);
}
for (i = 0; i <= n-1; i++)
{for(j = 0; j <= k-1; j++)
cout << setw(10) << *(*(a+i)+j);
cout << '\n';
}
cout << "\n\n first new array\n";

int m = -1;
for (i = 0; i <= n-1; i = i+2)
{m++;
*(p+m) = *(a+i);
}
for (i = 0; i <= m; i++)
{for(j = 0; j <= k-1; j++)
cout << setw(10) << *(*(p+i)+j)+1;
cout << '\n';
}
int l = -1;
for (i = 1; i <= n-1; i = i+2)
{l++;
q[l] = a[i];
}
cout << "\n\n second new array \n";
for (i = 0; i <= l; i++)
{for(j = 0; j <= k-1; j++)
cout << setw(10) << *(*(q+i)+j)+2;
cout << '\n';
}
cout << "\n\n third new array \n";
if (n%2 == 0)
for (i = 0; i <= m; i++)
{for (j = 0; j <= k-1; j++)
cout << setw(10) << *(*(p+i)+j) + *(*(q+i)+j);
cout << '\n';
}
return 0;
}

**ivakavlad** · 10-20-2010, 23:21

3. Указатели и низове

Низовете са масиви от символи. Името на променлива от тип низ е константен указател, както и името на всеки друг масив. Така всичко, което казахме за връзката между масив и указател е в сила и за низ – указател.
Следващият пример илюстрира обхождане на низ чрез използване на указател към char. Обхождането продължава до достигане на знака за край на низ.
#include <iostream.h>
int main()
{char str[] = "C++Language"; // str е константен указател
char* pstr = str;
while (*pstr)
{cout << *pstr << '\n';
pstr++;
}// pstr вече не е свързан с низа “C++Language”.
return 0;
}
Тъй като низът е зададен чрез масива от символи str, str е константен указател и не може да бъде променяна стойността му. Затова се налага използването на помощната променлива pstr.
Ако низът е зададен чрез указател към char, както е в следващата програма, не се налага използването на такава.
#include <iostream.h>
int main()
{char* str = "C++Language"; // str е променлива
while (*str)
{cout << *str << '\n';
str++;
}
return 0;
}
Примерите показват, че задаването на низ като указател към char има предимство пред задаването като масив от символи. Ще отбележим обаче, че дефиницията
char* str = "C++Language";
не може да бъде заменена с
char* str;
cin >> str;
следвани с въвеждане на низа “C++Language”, докато дефиницията
char str[20];
позволява въвеждането му чрез cin, т.е.
cin >> str;

Има още една особеност при дефинирането на низ като указател към char за реализацията Visual C++ 6.0. Ще я илюстрираме с пример.
Нека дефинираме променлива от тип низ по следния начин:
char s[] = “abba”;
Операторът
*s = ‘A’;
е еквивалентен на s[0] = ‘A’ и ще замени първото срещане на символа ‘a’ в s с ‘A’. Така
cout << s;
извежда низа
Abba
Да разгледаме съответната дефиницията на s чрез указател към char
char* s = “abba”;
Операторът
*s = ‘A’;
би трябвало да замени първото срещане на символа ‘a’ в s с ‘A’, тъй като s съдържа адреса на първото ‘a’. Тук обаче реализацията на Visual C++ съобщава за грешка – нарушение на достъпа. Последното може да се избегне като опцията на компилатора /ZI се замени с /Zi. Това се реализира като в менюто Project се избере Settings, след това C/C++, където Category трябва да има опция General. Накрая, в Project Options се промени /ZI на /Zi. Опцията /Zi се грижи за проблемите при нарушаване на достъпа, едно неудобство, което трябва да се има предвид.

**ivakavlad** · 10-20-2010, 23:22

4. Тип псевдоним

Чрез псевдонимите се задават алтернативни имена на обекти в общия смисъл на думата (променливи, константи и др.). В тази част ще ги разгледаме малко ограничено (псевдоними само за променливи).

Задаване на тип псевдоним

Нека T е име на тип. Типът T& е тип псевдоним на T. T се нарича базов тип на типа псевдоним.

Множество от стойности

Състои се от всички имена на дефинирани вече променливи от тип T.

Пример: Нека програмата съдържа следните дефиниции
int a, b = 5;
...
int x, y = 9, z = 8;
...
Множеството от стойности на типа int& съдържа имената a, b, x, y, z. Променлива величина, множеството от допустимите стойности на която съвпада с множеството от стойности на даден тип псевдоним, се нарича променлива от този тип псевдоним. Фиг. 4 илюстрира дефиницията.

<дефиниция_на_променлива_от _тип_псевдоним> ::=
T& <var> = <defined_var_of_T>; |
T &<var> = <defined_var_of_T>;
където
T е име тип, а
<defined_var_of_T> е име на вече дефинирана променлива от тип T.
Нарича се инициализатор.

Фиг. 4.

Възможно е фрагментите
<var> = <defined_var_of_T> и
&<var> = <defined_var_of_T>
да се повтарят многократно. За разделител се използва символът запетая. Има обаче една особеност. Дефиницията
Т& а = b, c = d;
е еквивалентна на
Т& а = b;
Т c = d;
Пример: Дефинициите
int a = 5;
int& syna = a;
double r = 1.85;
double &syn1 = r, &syn2 = r;
int& syn3 = a, syn4 = a;
определят syna и syn3 за псевдоними на a, syn1 и syn2 за псевдоними на r и syn4 за променлива от тип int.
Дефинициите задължително са с инициализация – променлива от същия тип като на базовия тип на типа псевдоним. Освен това, след инициализацията, променливата псевдоним не може да се променя като й се присвоява нова променлива или чрез повторна дефиниция. Затова тя е “най-константната” променлива, която може да съществува.
Пример:
...
int a = 5;
int &syn = a; // syn е псевдоним на a
int b = 10;
int& syn = b; // error, повторна дефиниция
...

Операции и вградени функции

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

Примери:
1. int ii = 0;
int& rr = ii;
rr++;
int* pp = &rr;
Резултатът от изпълнението на първите два оператора е следния:
ii, rr

... 0 ...

Операторът rr++; не променя адреса на rr, а стойността на ii и тя от 0 става 1. В случая rr++ е еквивалентен на ii++. Адресът на rr е адреса на ii. Намира се чрез &rr. Чрез дефиницията
int* pp = &rr;
pp е определена като указател към int, инициализирана с адреса на rr.
2. int a = 5;
int &syn = a;
cout << syn << " " << a << '\n';
int b = 10;
syn = b;
cout << b << " " << a << “ “ << syn << '\n';
извежда
5
10 10
Операторът syn = b; е еквивалентен на a = b;.
3. int i = 1;
int& r = i; // r и i са свързани с едно и също цяло число
cout << r; // извежда 1
int x = r; // x има стойност 1
r = 2; // еквивалентно е на i = 2;
Допълнение: Възможно е типът на инициализатора да е различен от този на псевдонима. В този случай се създава нова, наречена временна, променлива от типа на псевдонима, която се инициализира със зададената от инициализатора стойност, преобразувана до типа на псевдонима.
Например, след дефиницията
double x = 12.56;
int& synx = x;
имаме
x synx

12.56 ... 12

8B 4B

Сега x и псевдонимът й synx са различни променливи и промяната на x няма да влияе на synx и обратно.

Константни псевдоними
В C++ е възможно да се дефинират псевдоними, които са константи. За целта се използва запазената дума const, която се поставя пред дефиницията на променливата от тип псевдоним. По такъв начин псевдонимът не може да променя стойността си, но ако е псевдоним на променлива, промяната на стойността му може да стане чрез промяна на променливата.
Пример: Фрагментът
int i = 125;
const int& syni = i;
cout << i << " " << syni << '\n';
syni = 25;
cout << i << " " << syni << '\n';
ще съобщи за грешка (syni е константа и не може да е лява страна на оператор за присвояване), но фрагментът
int i = 125;
const int& syni = i;
cout << i << " " << syni << '\n';
i = i + 25;
cout << i << " " << syni << '\n';
ще изведе
125 125
150 150
Последното показва, че константен псевдоним на променлива защитава промяната на стойността на променливата чрез псевдонима.

Допълнителна литература

1. Ст. Липман, Езикът C++ в примери, “КОЛХИДА ТРЕЙД” КООП, С. 1993.
2. B. Stroustrup, C++ Programming Language. Third Edition, Addison – Wesley, 1997.

**ivakavlad** · 10-20-2010, 23:24

Глава 7

Функции

Добавянето на нови оператори и функции в приложенията, реализирани на езика C++, се осъществява чрез функциите. Те са основни структурни единици, от които се изграждат програмите на езика. Всяка функция се състои от множество от оператори, оформени подходящо за да се използват като обобщено действие или операция. След като една функция бъде дефинирана, тя може да бъде изпълнявана многократно за различни входни данни.
Програмите на езика C++ се състоят от една или повече функции. Сред тях задължително трябва да има точно една с име main и наречена главна функция. Тя е първата функция, която се изпълнява при стартиране на програмата. Главната функция от своя страна може да се обръща към други функции. Нормалното изпълнение на програмата завършва с изпълнението на главната функция (Възможно е изпълнението да завърши принудително с изпълнението на функция, различна от главната).
Използването на функции има следните предимства:
- Програмите стават ясни и лесни за тестване и модифициране.
- Избягва се многократното повтаряне на едни и същи програмни фрагменти. Те се дефинират еднократно като функции, след което могат да бъдат изпълнявани произволен брой пъти.
- Постига се икономия на памет, тъй като кодът на функцията се съхранява само на едно място в паметта, независимо от броя на нейните изпълнения.

Ще разгледаме най-общо разпределението на оперативната памет за изпълнима програма на C++. Чрез няколко примерни програми ще покажем дефинирането, обръщението и изпълнението на функции, след което ще направим съответните обобщения.

**ivakavlad** · 10-20-2010, 23:26

1. Разпределение на ОП за изпълнима програма

Разпределението на ОП зависи от изчислителната система, от типа на операционната система, а също от модела памет. Най-общо се състои от: програмен код, област на статичните данни, област на динамичните данни и програмен стек (Фиг. 1).
краен адрес на ОП

указател на стека
(запълване в посока
към малките адреси)
О

начален адрес на ОП

Фиг. 1.

Програмен код

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

Област на динамичните данни
За реализиране на динамични структури от данни (списъци, дървета, графи, ...) се използват средства за динамично разпределение на паметта. Чрез тях се заделя и освобождава памет в процеса на изпълнение на програмата, а не преди това (при компилирането й). Тази памет е от областта на динамичните данни.

Програмен стек
Този вид памет съхранява данните на функциите на програмата. Стекът е динамична структура, организирана по правилото “последен влязъл – пръв излязъл”. Той е редица от елементи с пряк достъп до елементите от единия си край, наречен връх. Достъпът се реализира чрез указател. Операцията включване се осъществява само пред елемента от върха, а операцията изключване – само за елемента от върха.
Елементите на програмния стек са “блокове” от памет, съхраняващи данни, дефинирани в някаква функция. Наричат се стекови рамки.

**ivakavlad** · 10-20-2010, 23:28

2. Примери за програми, които дефинират и използват функции

Задача 68. Да се напише програма, която въвежда стойности на естествените числа a, b, c и d и намира и извежда най-големият общ делител на числата a и b, след това на c и d и накрая на a, b, c и d.

Програма Zad68.cpp решава задачата. Тя се състои от две функции: gcd и main. Функцията gcd(x, y) намира най-големия общ делител на естествените числа x и y. Тъй като main се обръща към (извиква) gcd, функцията gcd трябва да бъде известна преди функцията main. Най-лесният начин да се постигне това е във файла, съдържащ програмата, първо да се постави дефиницията на gcd, а след това тази на main. Ще бъде показан алтернативен начин по-късно.
Описанието на функцията gcd прилича на това на функцията main. Състои се от заглавие
int gcd(int x, int y)
и тяло
{while (x != y)
if (x >= y) x = x-y; else y = y-x;
return x;
}
Заглавието определя, че gcd е име на двуаргументна целочислена функция с цели аргументи, т.е.

gcd: int x int int

Името е произволен идентификатор. В случая е направен мнемонически избор. Запазената дума int пред името на функцията е типа й (по-точно е типа на резултата на функцията). В кръгли сkобки и отделени със запетая са описани параметрите x и y на gcd. Те са различни идентификатори. Предшестват се от типовете си. Наричат се формални параметри за функцията.
Тялото на функцията е блок, реализиращ алгоритъма на Евклид за намиране на най-големия общ делител на естествените числа x и y. Завършва с оператора
return x;
чрез който се прекратява изпълнението на функцията като стойността на израза след return се връща като стойност на gcd в мястото, в случая в main, в което е направено обръщението към нея.

Program Zad68.cpp
#include <iostream.h>
int gcd(int x, int y)
{while (x != y)
if (x >= y) x = x-y; else y = y-x;
return x;
}
int main()
{cout << "a, b, c, d= ";
int a, b, c, d;
cin >> a >> b >> c >> d;
if (!cin || a < 1 || b < 1 || c < 1 || d < 1)
{cout << "Error \n";
return 1;
}
int r = gcd(a, b);
cout << "gcd{" << a << ", " << b << "}= " << r << "\n";
int s = gcd(c, d);
cout << "gcd{" << c << ", " << d << "}= " << s << "\n";
cout << "gcd{" << a << ", " << b << ", " << c << ", "
<< d << "}= " << gcd(r, s) << "\n";
return 0;
}

Изпълнение на програма Zad68.cpp

Дефинициите на функциите main и gcd се записват в областта на паметта, определена за програмния код. Изпълнението на програмата започва с изпълнение на функцията main. Фрагментът
cout << "a, b, c, d= ";
int a, b, c, d;
cin >> a >> b >> c >> d;
if (!cin || a < 1 || b < 1 || c < 1 || d < 1)
{cout << "Error \n";
return 1;
}
дефинира и въвежда стойности на целите променливи a, b, c и d като осигурява да са естествени числа. Нека за a, b, c и d са въведени 14, 21, 42 и 7 съответно. В тази последователност те се записват в дъното на програмния стек (Фиг. 2.). Така на дъното на стека се оформя “блок” от памет за main с достатъчно големи размери, който освен променливите от main съдържа и някои “вътрешни” данни. Този блок се нарича стекова рамка на main.
Операторът
int r = gcd(a, b);
дефинира цялата променлива r като в стековата рамка на main, веднага след променливата d отделя 4B, в които ще запише резултатът от обръщението gcd(a, b) към функцията gcd. Променливите a и b се наричат фактически параметри за това обръщение. Забелязваме, че типът им е същия като на съответните им формални параметри x и y.

a a 0x0066FDF4
b 0x0066FDF0
c 0x0066FDEC
d 0x0066FDE8 стекова рамка
r на main
0x0066FDE4

указател на стека
main ... 0x0040100F

gcd 0x0040100A програмен код

Фиг. 2.

Обръщение към gcd(a, b)
В програмния стек се генерира нов блок памет – стекова рамка за функцията gcd. В него се записват формалните и локалните параметри на gcd, а също и някои “вътрешни” данни като return-адреса и адреса на стековата рамка на main.
Обръщението се осъществява на два етапа:

а) Свързване на формалните с фактическите параметри
В стековата рамка на gcd, се отделят по 4 байта за формалните параметри x и y в обратен ред на реда, в които са записани в заглавието. В тази памет се откопирват стойностите на съответните им фактически параметри. Отделят се също 4B за т. нар. return-адрес, адреса на мястото в main, където ще се върне резултатът, а също се отделя памет, в която се записва адресът на предишната стекова рамка, т.е.

памет за gcd (I-во обръщение към него)

y 0x0066FD90
x 0x0066FD8C
0x0066FD88

return-адрес

адрес на предишната
стекова рамка
указател на стека

б) Изпълнение на тялото на gcd
Тъй като е в сила y > x, стойността на y се променя на 7, т.е.

памет в стека за gcd

y 0x0066FD90
x 0x0066FD8C
0x0066FD88

return-адрес

адрес на предишната
стекова рамка
указател на стека

Сега пък е в сила x > y, което води до промяна стойността му на 7, т.е.

памет в стека за gcd

y 0x0066FD90
x 0x0066FD8C
0x0066FD88

return-адрес

адрес на предишната
стекова рамка
указател на стека

Операторът за цикъл завършва изпълнението си. Изпълнението на оператора
return x;
преустановява изпълнението на gcd като връща в main в мястото на прекъсването (return-адреса) стойността 7 на обръщението gcd(a, b). Отделената за gcd стекова рамка се освобождава. Указателят на стека сочи края на стековата рамка на main. Изпълнението на програмата продължава с инициализацията на r. Резултатът от обръщението gcd(14, 21) се записва в отделената за r памет.
Операторът
cout << "gcd{" << a << ", " << b << "}= " << r << "\n";
извежда получения резултат.
Изпълнението на останалите обръщения към gcd се реализира по същия начин. При обръщението към всяко от тях в стека се създава стекова рамка на gcd, а след завършване на обръщението, рамката се освобождава. При достигане до оператора return 0; от main, се освобождава и стековата рамка на main.

Функцията gcd реализира най-простото и “чисто” дефиниране и използване на функции – получава входните си стойности единствено чрез формалните си параметри и връща резултата си чрез оператора return. Забелязваме, че обръщението gcd(a, b) работи с копия на стойностите на а и b, запомнени в x и y, а не със самите a и b. В процеса на изпълнение на тялото на gcd, стойностите на x и y се променят, но това не оказва влияние на стойностите на фактическите параметри a и b.
Такова свързване на формалните с фактическите параметри се нарича свързване по стойност или още предаване на параметрите по стойност. При него фактическите параметри магат да бъдат не само променливи, но и изрази от типове, съвместими с типовете на съответните формални параметри. Обръщението gcd(gcd(a, b), gcd(c, d)) е коректно и намира най-големия общ делител на a, b, c и d.

В редица случаи се налага функцията да получи входа си чрез някои от формалните си параметри и да върне резултат не по обичайния начин – чрез оператора return, а чрез същите или други параметри. Задача 69 дава пример за това.

Задача 69. Да се напише програма, която въвежда стойности на реалните числа a, b, c и d, след което разменя стойностите на a и b и на c и d съответно.

Ако дефинираме функция swapi(double* x, double* y), която разменя стойностите на реалните числа към които сочат указателите x и y, обръщението swapi(&a, &b) ще размени стойностите на a и b, а обръщението swapi(&c, &d) ще размени стойностите на c и d. Програма Zad69.cpp решава задачата. Тя се състои от функциите: swapi и main. Тъ0й като main се обръща към (извиква) swapi, функцията swapi трябва да бъде известна преди функцията main. Затова във файла, съдържащ програмата, първо се поставя swapi, а след това main.

Program Zad69.cpp
#include <iostream.h>
#include <iomanip.h>
void swapi(double* x, double* y)
{double work = *x;
*x = *y;
*y = work;
return;
}
0int main()
{cout << "a, b, c, d= ";
double a, b, c, d;
cin >> a >> b >> c >> d;
cout << setprecision(2) << setiosflags(ios :: fixed);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
swapi(&a, &b);
swapi(&c, &d);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
return 0;
}

Функцията swapi има подобна структура като на gcd. Но и заглавието, и тялото й са по-различни. Типът на swapi е указан чрез запазената дума void. Това означава, че функцията не връща стойност чрез оператора return. Затова в тялото на swapi е пропуснат изразът след return. Формалните параметри x и y са указатели към double, а в тялото се работи със съдържанията на указателите.
Забелязваме също, че обръщенията към swapi в main
swapi(&a, &b);
swapi(&c, &d);
не участват като аргументи на операции, а са оператори.

Изпълнение на програма Zad69.cpp

Дефинициите на функциите main и swapi се записват в областта на паметта, определена за програмния код. Изпълнението на програмата започва с изпълнение на функцията main. Фрагментът
cout << "a, b, c, d= ";
double a, b, c, d;
cin >> a >> b >> c >> d;
cout << setprecision(2) << setiosflags(ios :: fixed);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
дефинира и въвежда стойности за реалните променливи a, b, c и d и ги извежда върху екрана според дефинираното форматиране. Нека за стойности на a, b, c и d са въведени 1.5, 2.75, 3.25 и 8.2 съответно (Фиг. 3).

a a 0x0066FDF0
b 0x0066FDE8
c 0x0066FDE0 стекова рамка
на main
d 0x0066FDD8

указател на стека

main ... 0x00401046

swapi 0x00401019 програмен код

Фиг. 3.
Обръщението
swapi(&a, &b);
се изпълнява на два етапа по следния начин:

а) Свързване на формалните с фактическите параметри
В стека се конструира нова рамка – рамката на swapi. Oтделят се по 4 байта за формалните параметри x и y, в която памет се записват адресите на съответните им фактически параметри, още 4B, в които се записва адресът на swapi(c, d), от където трябва да се продължи изпълнението на main (return-адреса), а също и памет, в която се записва адресът на предишната стекова рамка (в случая на main).

y 0x0066FD38

x 0x0066FD34

return- стекова рамка
адрес (адрес от main) на swapi

адрес на
предишна стекова рамка

указател на стека
б) Изпълнение на тялото на swapi
Изпълнява се като блок. За реалната променлива work се отделят 8 байта в стековата рамка на swapi, в които се записва съдържанието на x, в случая 1.5, т.е.

y 0x0066FD38
x 0x0066FD34

return- 0x0066FD.. стекова рамка
адрес адрес от main на swapi

адрес на предишната
стекова рамка
work 0x0066FD24

указател на стека
Oператорът
*x = *y;
променя съдържанието на x с това на y, а операторът
*y = work;
променя съдържанието на y като го свързва със стойността на work, т.е.

стекова рамка на main

a a 0x0066FDF0
b 0x0066FDE8
c 0x0066FDE0
d 0x0066FDD8

Операторът return; прекъсва работа на на swapi и предава управлението в точката на извикването му в главната функция (return-адреса). Стековата рамка, отделена за swapi се освобождава. Указателят на стека сочи стековата рамка на main. В резултат стойностите на променливите a и b са разменени.
Обръщението swapi(c, d) се изпълнява по аналогичен начин. За нея се генерира нова стекова рамка (на същите адреси), която се освобождава когато изпълнението на swapi завърши.

Функцията swapi получава входните си стойности чрез формалните си параметри и връща резултата си чрез тях. Забелязваме, че обръщението swapi(&a, &b) работи не с копия на стойностите на а и b, а с адресите им. В процеса на изпълнение на тялото се променят стойностите на фактическите параметри a и b при първото обръщение към нея и на c и d – при второто.
Такова свързване на формалните с фактическите параметри се нарича свързване на параметрите по указател или още предаване на параметрите по указател или свързване по адрес. При този вид предаване на параметрите, фактическите параметри задължително са променливи или адреси на променливи.

Освен тези два начина на предаване на параметри, в езика C++ има още един – предаване на параметри по псевдоним. Той е сравнително по-удобен от предаването по указател и се предпочита от програмистите.
Ще го илюстрираме чрез същата задача. Програма Zad69_1.cpp реализира функция swapi, в която предаването на параметрите е по псевдоним.

Program Zad69_1.cpp
#include <iostream.h>
#include <iomanip.h>
void swapi(double& x, double& y)
{double work = x;
x = y;
y = work;
return;
}
int main()
{cout << "a, b, c, d= ";
double a, b, c, d;
cin >> a >> b >> c >> d;
cout << setprecision(2) << setiosflags(ios :: fixed);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
swapi(a, b);
swapi(c, d);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
return 0;
}

Ще проследим изпълнението и на тази модификация.
Изпълнението на програмата започва с изпълнение на функцията main. Фрагментът
cout << "a, b, c, d= ";
double a, b, c, d;
cin >> a >> b >> c >> d;
cout << setprecision(2) << setiosflags(ios :: fixed);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
дефинира и въвежда стойности за реалните променливи a, b, c и d и ги извежда върху екрана според дефинираното форматиране. Нека за стойности на a, b, c и d отново са въведени 1.5, 2.75, 3.25 и 8.2 съответно. След обработката му в стека се конструира стековата рамка на main.

памет на main

x a a 0x0066FDF0
y b 0x0066FDE8
c 0x0066FDE0
d 0x0066FDD8

Обръщението
swapi(a, b);
се изпълнява на два етапа по следния начин:

а) Свързване на формалните с фактическите параметри
За целта се генерира нова стекова рамка – рамката на swapi. Указателят на стека сочи тази рамка. Тъй като формалните параметри x и y са псевдоними на променливите a и b, за тях памет в стековата рамка на swapi не се отделя. Параметърът x “прелита” и се “закачва” за фактическия параметър a и аналогично y “прелита” и се “закачва” за фактическия параметър b от стековата рамка на main. Така всички действия с x и y в swapi се изпълняват с фактическите параметри a и b от main съответно.
б) Изпълнение на тялото на swapi
Изпълнява се като блок. В рамката на swapi, за реалната променлива work се отделят 8 байта, в които се записва стойността на x, в случая 1.5, т.е.

стекова рамка на swapi

return-
адрес (адрес от main) стекова рамка
на swapi
адрес на последната
стекова рамка
work 0x0066FD24
указател на стека

Oператорът
x = y;
присвоява на a стойността на b, а операторът
y = work;
променя стойността на променливата b като й присвоява стойността на work, т.е.

x a a 0x0066FDF0
y b 0x0066FDE8
c 0x0066FDE0
d 0x0066FDD8

Операторът return; прекъсва работа на на swapi и предава управлението на return-адреса от главната функция. Стековата рамка на swapi се освобождава. Указателят на стека сочи стековата рамка на main. В резултат, стойностите на променливите a и b са разменени. Променливите a и b са “освободени от“ x и y. Следва изпълнение на обръщението
swapi(c, d);
което се реализира по същия начин (даже на същите адреси в стека).
Забелязваме, че фактическите параметри, съответстващи на формални параметри-псевдоними са променливи.
Тази реализация на swapi е по-ясна от съответната с указатели. Тялото й реализира размяна на стойностите на две реални променливи без да се налага използването на адреси.
Нека в тялото на main на Zad69_1.cpp преди оператора return; включим фрагмента:
int m, n;
cin >> m >> n;
swapi(m, n);
cout << setw(10) << m << setw(10) << n << "\n";
Някои реализации (visual C++ 6.0) ще сигнализират грешка на третата линия – невъзможност за преобразуване на параметър от int в double &, други обаче ще имат нормално поведение, но няма да разменят стойностите на m и n. Последното е така, тъй като при несъответствие на типа на псевдонима с типа на инициализатора, в стековата рамка на swapi, се създават “временни” променливи x и y, в които се запомнят конвертираните стойности на инициализаторите. Извършва се размяната, но само в стековата рамка на swapi.

При предаване на параметрите по указател или по псевдоним, фактическите параметри са променливи, за разлика от предаването на параметри по стойност, когато фактическите параметри могат да са изрази в общия случай.
Възможно е някои параметри да се подават по стойност, други по псевдоним или указател, а също функцията да връща резултат и чрез оператора return. Примери ще бъдат дадени в следващите части на изложението. Ще бъдат обсъдени също предимствата и недостатъците на всеки от начините за предаване на параметрите.
Ако функция не връща резултат чрез return (типът й е void), се нарича още процедура.
Разгледаните програми се състояха от две функции. По-сериозните приложения съдържат повече функции. Подредбата им може да започва с main, след която в произволен ред да се дефинират останалите функции. В този случай, дефиницията на main трябва да се предшества от декларациите на останалите функции. Декларацията на една функция се състои от заглавието й, следвано от ;. Имената на формалните параметри могат да се пропуснат. Например, програмата от Zad69_1.cpp може да се запише във вида:
Program Zad69_1.cpp
#include <iostream.h>
#include <iomanip.h>
void swapi(double&, double&); // декларация на swapi
int main()
{cout << "a, b, c, d= ";
double a, b, c, d;
cin >> a >> b >> c >> d;
cout << setprecision(2) << setiosflags(ios :: fixed);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
swapi(a, b);
swapi(c, d);
cout << setw(10) << a << setw(10) << b
<< setw(10) << c << setw(10) << d << ‘\n’;
return 0;
}
void swapi(double& x, double& y) // дефиниция на swapi
{double work = x;
x = y;
y = work;
return;
}

**ivakavlad** · 10-20-2010, 23:29

3. Дефиниране на функции

Синтаксис на дефиницията
Дефиницията на функция се състои от две части: заглавие (прототип) и тяло. Синтаксисът й е показан на Фиг. 4.

[<модификатор>][<тип_на_функцията>]<име_на_функция>
(<формални_параметри>)
{<тяло>
}
където
<модификатор>::= inline|static| ...
<тип_на_резултата> ::= <име_на_тип> | <дефиниция_на_тип>
<име_на_функция> ::= <идентификатор>
<формални_параметри> :: <празно> | void |
<параметър> {, <параметър>}
<параметър> ::= <тип>[ & |opc * [const]opc] opc <име_на_параметър>
<тип> ::= <име_на_тип>
<име_на_параметър> ::= <идентификатор>
<тяло> ::= <редица_от_оператори_и_дефи� �иции>

Фиг. 4.

Модификаторите са спецификатори, които задават препоръка за компилатора (inline), класа памет (extern или static) и др. Ще дадем примери в следващите разглеждания. Ако е пропуснат, подразбира се extern.
Типът на функцията е произволен без масив и функционален, но се допуска да е указател към такива обекти. Ако е пропуснат, подразбира се int.
Името на функцията е произволен идентификатор. Допуска се нееднозначност.
Списъкът от формални параметри (нарича се още сигнатура) може да е празен или void. Например, следната функция извежда текст:
void printtext(void)
{cout << “This is text!!!\n”
cout << “ .....”;
return;
}
В случай, че е непразен, имената на параметрите трябва да са различни. Те заедно с името определят еднозначно функцията. Формалните параметри са: параметри – стойности, параметри – указатели и параметри – псевдоними. Името на параметъра се предшества от тип.
Примери:
int a, int const& b, double& x, int const * y, const int* a
Засега няма да използваме параметри, специфицирани със const.

Тялото на функцията е редица от дефиниции и оператори. Тя описва алгоритъма, реализиращ функцията. Може да съдържа един или повече оператора return.
Операторът return (Фиг. 5) връща резултата на функцията в мястото на извикването.

Синтаксис
return [<израз>]
където
return е запазена дума
<израз> е произволен израз от тип <тип_на_функцията> или съвместим с него. Ако типът на функцията е void, <израз> се пропуска.
Семантика
Пресмята се стойността на <израз>, конвертира се до типа на функцията (ако е възможно) и връщайки получената стойност в мястото на извикването на функцията, прекратява изпълнението й.

Фиг. 5.

Забележка: Ако функцията не е от тип void, тя задължително трябва да върне стойност. Това означава, че операторът return трябва да се намира във всички клонове на тялото. В противен случай, повечето компилатори ще изведат съобщение или предупреждение за грешка. Възможно е обаче функцията да върне случайна стойност, което е лошо. По-добре е функцията да върне някаква безобидна стойност, отколкото случайна.

Функциите могат да се дефинират в произволно място на програмата, но не и в други функции. Преди да се извика една функция, тя трябва да е “позната” на компилатора. Това става, като дефиницията на функцията се постави пред main или когато функцията се дефинира на произволно място в частта за дефиниране на функции, а преди дефинициите на функциите се постави само нейната декларация.

<декларация_на_функция> ::=
[<модификатор>][<тип_на_резултата>]<име_на_функция>
([<формални_параметри>]);

Възможно е имената на параметрите във <формални_параметри> да се пропуснат.

Семантика на дефиницията
Описанието на функция задава параметрите, които носят входа и изхода, типа на резултата, а също и алгоритъма, за реализиране на действието, което функцията дефинира. Параметрите-стойности най-често задават входа на функцията. Параметрите-указатели и псевдоними са входно-изходните параметри за нея. Алгоритъмът се описва в тялото на функцията. Изпълнението на функцията завършва при достигане на края на тялото или след изпълнение на оператор return [<израз>];.

**ivakavlad** · 10-20-2010, 23:29

4. Обръщение към функция

Синтаксис
<обръщение_към_функция> ::=
<име_на_функция>() |
<име_на_функция>(void) |
<име_на_функция>(<фактически _параметри>)
където <фактически_параметри> са толкова на брой, колкото са формалните параметри. Освен по брой, формалните и фактическите параметри трябра да си съответстват по тип, по вид и по смисъл.
Съответствието по тип означава, че типът на i-тия фактически параметър трябва да съвпада (да е съвместим) с типа на i-тия формален параметър. Съответствието по вид се състои в следното: ако формалният параметър е параметър-указател, съответният му фактически параметър задължително е променлива или адрес на променлива, ако е параметър-псевдоним, съответният му фактически параметър задължително е променлива (за реализацията Visual C++, 6.0 от същия тип) и ако е параметър-стойност – съответният му фактически параметър е израз.

Семантика
Обръщението към функция е унарна операция с най-висок приоритет и с операнд - името на функцията. Последното пък е указател със стойност адреса на мястото в паметта където е записан програмният код на функцията. Ако функцията определя процедура, обръщението към нея се оформя като оператор (завършва с

. Опитът за използването й като израз предизвиква грешка. Ако функцията връща резултат както чрез return, така и чрез някой от формалните си параметри, обръщението към нея може да се разглежда и като оператор, и като израз. И ако функцията връща резултат единствено чрез оператора return, обръщението към нея има единствено смисъла на израз. Използването му като оператор не води до грешка, но не предизвиква видим резултат.

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

1. Свързване на формалните с фактическите параметри

За целта първият формален параметър се свързва с първия фактически, вторият формален параметър се свързва с втория фактически и т.н. последният формален параметър се свързва с последния фактически параметър. Свързването се реализира по различни начини в зависимост от вида на формалния параметър.
а) формален параметър – стойност
В този случай се намира стойността на съответния му фактически параметър. В стековата рамка на функцията за формалния параметър се отделя толкова памет, колкото типът му изисква и в нея се откопирва стойността на фактическия параметър.
б) формален параметър – указател
В този случай в стековата рамка на функцията за формалния параметър се отделят 4B, в които се записва стойността на фактическия параметър, която е адрес на променлива. Действията, описани в тялото се изпълняват със съдържанието на формалния параметър - указател. По такъв начин е възможна промяна на стойността на променливата, чийто адреа е предаден като фактически параметър.
в) формален параметър – псевдоним
Формалният параметър-псевдоним се свързва с адреса на фактическия. За него в стековата рамка на функцията памет не се отделя. Той просто “прелита” и се “закачва” за фактическия си параметър. Действията с него се извършват над фактическия параметър.

2. Изпълнение на тялото на функцията

Аналогично е на изпълнението на блок.

При всяко обръщение към функция в програмния стек се включва нов “блок” от данни. В него се съхраняват формалните параметри на функцията, нейните локални променливи, а също и някои “вътрешни” данни като return-адреса и др. Този блок се нарича стекова рамка на функцията.
В дъното на стека е стековата рамка на main. На върха на стека е стековата рамка на функцията, която се обработва в момента. Под нея е стековата рамка на функцията, извикала функцията, обработваща се в момента. Ако изпълнението на една функция завършва, нейната стекова рамка се отстранява от стека.
Видът на стековата рамка зависи от реализацията. С точност до наредба, тя има вида:

Област на идентификаторите в програмата на C++

Идентификаторите означават имена на константи, променливи, формални параметри, функции, класове. Най-общо казано, има три вида области на идентификаторите: глобална, локална и област за клас. Областите се задават неявно – чрез позицията на идентификатора в програмата и явно – чрез декларация. Отново разглеждането ще е непълно, заради пропускането на класовете и явното задаване на област.
Глобални идентификатори
Дефинираните пред всички функции константи и променливи могат да се използват във всички функции на модула, освен ако не е дефиниран локален идентификатор със същото име в някоя функция на модула. Наричат се глобални идентификатори, а областта им – глобална.
Локални идентификатори
Повечето константи и променливи имат локална област. Те са дефинирани вътре във функциите и не са достъпни за кода в другите функции на модула. Областта им се определя според общото правило – започва от мястото на дефинирането и завършва в края на оператора (блока), в който идентификаторът е дефиниран. Формалните параметри на функциите също имат локална видимост. Областта им е тялото на функцията.
В различните области могат да се използват еднакви идентификатори. Ако областта на един идентификатор се съдържа в областта на друг, последният се нарича нелокален за първоначалния. В този случай е в сила правилото: Локалният идентификатор “скрива” нелокалния в областта си.
Областта на функция започва от нейното дефиниране и продължава до края на модула, в който функцията е дефинирана. Ако дефинициите на функциите са предшествани от тяхните декларации, редът на дефиниране на функциите в модула не е от значение – функциите са видими в целия модул. Препоръчва се също дефинирането на заглавен файл с прототипите (декларациите) на функциите.

**ivakavlad** · 10-20-2010, 23:31

5. Масивите като формални параметри

едномерни масиви
Съществуват различни начини за задаване на формални параметри от тип едномерен масив.
а) традиционен
Дефиницията
T a[]
където T е скаларен тип, задава параметър a от тип едномерен масив с базов тип T. Може да се укаже горна граница на масива, но компилаторът я пренебрегва.
Примери:
int a[] - a е параметър от тип масив от цели числа,
int a[10] - еквивалентна е на int a[],
double b[] - b е параметър от тип масив от реални числа,
char c[] - c е параметър от тип масив от символи.
б) чрез указател
Дефиницията
T* p
където T е скаларен тип, задава параметър p от тип указател към тип T. От връзката между масив и указател следва, че тази дефиниция може да се използва и за дефиниране на формален параметър от тип масив.
Примери: Следните дефиниции на формални параметри са еквивалентни на тези от примера по-горе:
int* a - a е параметър от тип указател към int
double* b - b е параметър от тип указател към double.
char* c - c е параметър от тип указател към char.
И в двата случая фактическият параметър се указва с името на едномерен масив от същия тип. Необходимо е също на функцията да се подаде като параметър и размерът на масива.

Задача 70. Да се напишат функции, които въвеждат и извеждат елементите на едномерен масив от цели числа. Като се използват тези функции да се напише програма, която въвежда редица от естествени числа, след което я извежда, а също извежда най-големия общ делител на елементите на редицата.

Програма Zad70.cpp решава задачата.
Program Zad70.cpp
#include <iostream.h>
int gcd(int, int);
void readarr(int, int[]);
void writearr(int, int[]);
int main()
{cout << "n= ";
int n;
cin >> n;
int a[20];
readarr(n, a);
writearr(n, a);
int x = a[0];
for (int i = 1; i <= n-1; i++)
x = gcd(x, a[i]);
cout << "gcd = " << x << '\n';
return 0;
}
int gcd(int a, int b)
{while (a != b)
if (a >= b) a = a-b; else b = b-a;
return a;
}
void readarr(int m, int arr[])
// m е размерността на масива
// arr е едномерен масив
{for (int i = 0; i <= m-1; i++)
{cout << "arr[" <> arr[i];
}
}
void writearr(int m, int arr[])
// m е размерността на масива
// arr е едномерен масив
{for (int i = 0; i <= m-1; i++)
cout << "arr[" <> n;
int a[20];
дефинира и въвежда стойност на n, а също дефинира променлива a от тип масив. Нека за n е въведено 5. В резултат е създадена стековата рамка на main. ОП до този момент има вида:

n 0x0066FDF4
a[19] 0x0066FDF0
a[18] 0x0066FDEC
a[17] 0x0066FDE8 стекова рамка
... на main

a[2] 0x0066FDAC
a[1] 0x0066FDA8
a[0] 0x0066FDA4

указател на стека

main ... 0x00401023

gcd 0x0040101E програмен код

readarr 0x00401019

writearr 0x00401014

Обръщението
readarr(n, a);
се реализира като се свързват формалните с фактическите параметри и се изпълни тялото. За целта се формира нова стекова рамка – тази на readarr, в която за формалния параметър arr се отделят 4B, в която памет се откопирва стойността на фактическия параметър a (адресът на a[0]), за m се отделят също 4B, в които се откопирва 5 – стойността на фактическия параметър n. Тялото на функцията се изпълнява като блок. Операторът за цикъл
for (int i = 0; i <= m-1; i++)
{cout << "arr[" <> arr[i];
}
е еквивалентен на
for (int i = 0; i <= m-1; i++)
{cout << "arr[" <> *(arr + i);
}
и се изпълнява по следния начин: За цялата променлива i се отделят 4B в стековата рамка на readarr. i последователно приема стойностите 0, 1, ..., 4 и за всяка стойност се изпълнява блокът
{cout << "arr[" <> *(arr + i);
}
Операторът
cin >> *(arr + i);
въвежда стойност на индексираната променлива a[i], тъй като arr + i е адреса на i-тия елемент на a, а *(arr+i) е неговата стойност. Така във функцията се работи с формалния параметър arr, а в действителност действията се изпълняват с фактическия параметър – едномерния масив a. Функцията readarr работи с масива a, а не с негово копие.

n 0x0066FDF4

a[19] 0x0066FDF0
... стекова рамка
a[0] 0x0066FDA4 на main

arr
m стекова рамка
на readarr
return - адрес

i указател на стека

След достигане на края на функцията изпълнението й завършва и се освобождава стековата й рамка. В резултат, първите 5 елемента на масива a получават текущи стойности. Операторът
writearr(n, a);
се изпълнява по аналогичен начин. Отново се работи с фактическия параметър - масива a, а не с негово копие. В този случай, елементите a[0], a[1], ..., a[n-1] на a само се сканират и извеждат. Не се извършват промени над тях. За да ги защитим от неправомерен достъп, е добре формалният параметър arr да дефинираме като указател към цяла константа, т.е. като const int arr[]. Тогава всеки опит да се променя arr[i] (i = 0, 1, ..., n-1) в writearr ще предизвика грешка.
Фрагментът
int x = a[0];
for (int i = 1; i <= n-1; i++)
x = gcd(x, a[i]);
намира най-големия общ делител на елементите на редицата.
В заглавията на последните две процедури горните граници на индексите могат явно да се укажат. Например
void writearr(int m, int arr[20])
и
void readarr(int m, int arr[20])
са валидни заглавия, но компилаторът не се нуждае от горната граница. Трябват му само скобките [], за да разпознае параметър от тип масив. Може също да се използва второто представяне на формален параметър от тип масив, т.е.
void writearr(int m, int* arr)
и
void readarr(int m, int* arr)
Тези представяния на формалните параметри са напълно еквивлентни.
Забележки:
Функциите readarr и writearr работят с направо с масива a, а не с негови копия. Промените на елементите на масива се запазват след излизане от функцията.
Размерът на масивът не може да се разбере от неговото описание. Затова се налага използването на допълнителния параметър m в списъка от аргументи на функциите. Последното не се отнася за масивите, представляващи символни низове, тъй като те завършват със знака за край на низ ‘\0’.

Задача 71. Да се напише функция len(char* s), която намира дължината на символен низ, а също функция eqstrs(char*, char*), която сравнява два символни низа за лексикографско равно.

Функциите Function Zad71_1 и Function Zad71_2 решават задачата.
Function Zad71_1
int len(char* s)
{int k = 0;
while(*s)
{k++;
s++;}
return k;
}

Function Zad71_2
bool eqstrs(char* str1, char* str2)
{while (*str1 == *str2 && * str1)
{str1++; str2++;}
return *str1 == *str2;
}
Обърнете внимание, че тъй като всеки низ завършва със символа ‘\0’, който се интерпретира като false, изразът *s в оператора за цикъл while на функцията len, ще бъде истина и тялото ще се изпълнява до достигане на края на низа. Аналогична конструкция имаме и при дефиницията на функцията eqstrs.

Задача 72. Да се напише булева функция, която проверява дали цялото число x е елемент на редицата от цели числа a0, a1, ..., an-1.

Функцията Zad72.cpp решава задачата.

Function Zad72
bool search(int n, int a[], int x)
{int i = 0;
while (a[i] != x && i < n-1)i++;
return a[i]==x;
}

Обръщението
search(m, b, y)
проверява дали елементът y се съдържа в редицата b0, b1, ..., bm-1, а
search(k, b + m, y)
проверява дали y се съдържа в подредицата bm, bm+1, ..., bm+k-1.
Еквивалентна дефиниция на тази функция е:
bool search(int n, int* a, int x)
{int i = 0;
while (*(a+i) != x && i < n-1)i++;
return *(a+i)==x;
}

Задача 73. Да се напише функция, която проверява дали редицата от цели числа a0, a1, ..., an-1 е монотонно намаляваща.

Функцията Zad73 решава задачата.

Function Zad73
bool monnam(int n, int a[])
{int i = 0;
while (a[i] >= a[i+1] && i < n-2)i++;
return a[i] >= a[i+1];
}
или
bool monnam(int n, int* a)
{int i = 0;
while (*(a+i) >= *(a+i+1) && i < n-2)i++;
return *(a+i) >= *(a+i+1);
}
Обръщението
monnam(m, b)
проберява дали редицата b0, b1, ..., bm-1 е монотонно намаляваща, а
monnam(k, b + m)
- дали подредицата bm, bm+1, ..., bm+k-1 на b0, b1, ..., bm-1 е монотонно намаляваща.

Задача 74. Да се напише функция, която проверява дали редицата от цели числа a0, a1, ..., an-1 се състои от различни елементи.

Функцията Zad74 решава задачата.

Function Zad74
bool differ(int n, int a[])
{int i = -1;
bool b; int j;
do
{i++; j = i;
do
{j++;
b = a[i] != a[j];
}while (b && j < n-1);
}while (b && i < n-2);
return b;
}

Обръщението
differ(m, b, y)
проберява дали редицата b0, b1, ..., bm-1 се състои от различни елементи, а
differ(k, b + m)
- дали подредицата bm, bm+1, ..., bm+k-1 на b0, b1, ..., bm-1 се състои от различни елементи.

Задача 75. Да се напише програма, която въвежда две числови редици, сортира ги във възходящ ред, слива ги и извежда получената редица.

Програма Zad75.cpp решава задачата. За целта са дефинирани следните функции:
readarr – въвежда числова редица
writearr – извежда числова редица върху екрана
sortarr - сортира във възходящ ред елементите на числова редица
mergearrs - слива числови редици.

Program Zad75.cpp
#include <iostream.h>
#include <iomanip.h>
void writearr(int, double[]);
void readarr(int, double[]);
void sortarr(int, double[]);
void mergearrs(int, double[], int, double[], int&, double[]);

int main()
{cout << "n= ";
int n;
cin >> n;
double a[20];
readarr(n, a);
cout << endl;
writearr(n, a);
cout << endl;
sortarr(n, a);
cout << endl;
writearr(n, a);
cout << "m= ";
int m;
cin >> m;
double b[30];
readarr(m, b);
cout << endl;
writearr(m, b);
cout << endl;
sortarr(m, b);
cout << endl;
writearr(m, b);
cout << endl;
int p;
double c[50];
mergearrs(n, a, m, b, p, c);
writearr(p, c);
return 0;
}
void writearr(int m, double arr[])
{cout << setprecision(3) << setiosflags(ios::fixed);
for (int i = 0; i <= m-1; i++)
cout << setw(10) << arr[i];
cout << "\n";
}
void readarr(int m, double arr[])
{for (int i = 0; i <= m-1; i++)
{cout << "arr[" <> arr[i];
}
}
void sortarr(int n, double a[])
{for (int i = 0; i <= n-2; i++)
{int k = i;
double min = a[i];
for (int j = i+1; j <= n-1; j++)
if (a[j] < min)
{min = a[j];
k = j;
}
double x = a[i]; a[i] = a[k]; a[k] = x;
}
}
void mergearrs(int n, double a[], int m, double b[],
int& k, double c[])
{int i = 0, j = 0;
k = -1;
while (i <= n-1 && j <= m-1)
if (a[i] <= b[j])
{k++;
c[k] = a[i];
i++;
}
else
{k++;
c[k] = b[j];
j++;
}
int l;
if (i > n-1)
for (l = j; l <= m-1; l++)
{k++;
c[k] = b[l];
}
else
for (l = i; l <= n-1; l++)
{k++;
c[k] = a[l];
}
k++;
}

многомерни масиви
Когато многомерен масив трябва да е формален параметър на функция, в описанието му трябва да присъстват като константи всички размери с изключение на първият. Например, декларацията
void readarr2(int n, int matr[][20]);
определя matr като двумерен масив (редица от двадесеторки от цели числа). Описанието
int (*matr)[20]
е еквивалентно на
int matr[][20]
Скобките, ограждащи *matr, са задължителни. В противен случай, тъй като [] е с по-висок приоритет от *, int *matr[20] ще се интерпретира като “matr е масив с 20 елемента от тип *int”.

Задача 76. Да се напише програма, която въвежда квадратна матрица от цели числа, след което я извежда като увеличава всеки от елементите на матрицата над главния диагонал с 5 и намалява всеки от елементите под главния диагонал с 5.

Програма Zad76.cpp решава задачата. Тя дефинира функциите:
readarr2 – въвежда квадратна матрица
writearr2 – извежда квадратна матрица
transff - увеличава всеки от елементите на матрицата над главния диагонал с 5 и намалява всеки от елементите под главния диагонал с 5.

Program Zad76.cpp
#include <iostream.h>
#include <iomanip.h>
void readarr2(int, int[][10]);
void writearr2(int, int[][10]);
void transff(int, int[][10]);
int main()
{int a[10][10];
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 10)
{cout << "Incorrect input! \n";
return 1;
}
readarr2(n, a);
cout << '\n';
writearr2(n, a);
cout << '\n';
transff(n, a);
writearr2(n, a);
return 0;
}
void readarr2(int n, int arr[][10])
{for (int i = 0; i <= n-1; i++)
for (int j = 0; j <= n-1; j++)
cin >> arr[i][j];
}
void writearr2(int n, int arr[][10])
{for (int i = 0; i <= n-1; i++)
{for (int j = 0; j <= n-1; j++)
cout << setw(5) << arr[i][j];
cout << "\n";
}
}
void transff(int n, int arr[][10])
{int i, j;
for (i = 1; i <= n-1; i++)
for (j = 0; j <= i-1; j++)
arr[i][j] = arr[i][j] - 5;
for(i = 0; i <= n-2; i++)
for(j = i+1; j <= n-1; j++)
arr[i][j] = arr[i][j] + 5;
}
Обръщението
transff(k, a + m);

ще извърши същото действие над квадратната подматрица на дадената матрица:

Задача 77. Да се напише програма, която въвежда редица от думи не по-дълги от 14 знака и дума, също не по-дълга от 14 знака. Програмата да проверява дали думата се среща в редицата. За целта да се оформят подходящи функции.

Програма Zad77.cpp решава задачата. В нея са дефинирани функциите:
void readarrstr(int n, char s[][15]); - въвежда редица от n думи,
bool search(int n, char s[][15], char* x); - търси думата x в редицата s от n думи. За целта използва помощната функция
bool eqstrs(char* str1, char* str2);
от Задача 71.

Program Zad77.cpp
#include <iostream.h>
#include <string.h>
void readarrstr(int, char [][15]);
bool eqstrs(char*, char*);
bool search(int, char [][15], char*);
int main()
{char a[20][15];
cout << "n= ";
int n;
cin >> n;
readarrstr(n, a);
cout << "word: ";
char word[15];
cin >> word;
if (search(n, a, word)) cout << "yes \n";
else cout << "no \n";
return 0;
}
void readarrstr(int n, char s[][15])
{for(int i = 0; i <= n-1; i++)
{cout << "s[" <> s[i];
}
}
bool eqstrs(char* str1, char* str2)
{while (*str1 && *str1 == *str2)
{str1++; str2++;}
if(*str1 != *str2) return false;
else return true;
}
bool search(int n, char s[][15], char* x)
{int i = 0;
while (!eqstrs(s[i], x) && i < n-1) i++;
return eqstrs(s[i], x);
}

Задача 78. Да се напише програма, която умножава две матрици.

Програма Zad78.cpp решава задачата. Тя дефинира следните функции:
readarr2 – въвежда матрица,
writearr2 – извежда матрица,
multmatr – умножава матрици.

Program Zad78.cpp
#include <iostream.h>
#include <iomanip.h>
void readarr2(int n, int m, double [][30]);
void writearr2(int n, int m, double [][30]);
void multmatr(int, int, int, double [][30],
double [][30], double [][30]);

int main()
{double a[10][30], b[20][30], c[10][30];
cout << "n= ";
int n;
cin >> n;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (n < 1 || n > 10)
{cout << "Incorrect input! \n";
return 1;
}
cout << "m= ";
int m;
cin >> m;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (m < 1 || m > 30)
{cout << "Incorrect input! \n";
return 1;
}
cout << "k= ";
int k;
cin >> k;
if (!cin)
{cout << "Error, Bad input! \n";
return 1;
}
if (k < 1 || k > 30)
{cout << "Incorrect input! \n";
return 1;
}
readarr2(n, m, a);
writearr2(n, m, a);
cout << "\n";
readarr2(m, k, b);
cout << "\n";
writearr2(m, k, b);
cout << "\n";
multmatr(n, m, k, a, b, c);
writearr2(n, k, c);
return 0;
}
void readarr2(int n, int m, double arr [][30])
{for (int i = 0; i <= n-1; i++)
for (int j = 0; j <= m-1; j++)
cin >> arr[i][j];
return;
}
void writearr2(int n, int m, double arr[][30])
{cout << setprecision(3) << setiosflags(ios::fixed);
for (int i = 0; i <= n-1; i++)
{for (int j = 0; j <= m-1; j++)
cout << setw(10) << arr[i][j];
cout << "\n";
}
return;
}
void multmatr(int n, int m, int k, double a[][30],
double b[][30], double c[][30])
{for (int i = 0; i <= n-1; i++)
for (int j = 0; j <= m-1; j++)
{c[i][j] = 0;
for (int p = 0; p <= m-1; p++)
c[i][j] += a[i][p] * b[p][j];

//c[I][j] = c[I][j]+a[I][j]* b[p][j]
}
}

**ivakavlad** · 10-20-2010, 23:32

6. Масивите като върнати оценки

Въпреки, че масивите могат да са параметри на функции, функциите не могат да са от тип масив. Възможно е обаче да са от тип указател. Това позвлява дефинирането на функции, които връщват масиви.
Пример: В следващата програма е дефинирана функцията readarr, която въвежда стойности на едномерен масив. Тя връща резултат не само чрез променливата от тип масив arr, но и чрез оператора return. Това позволява обръщенията към нея да са както като оператор, така и като израз.

#include <iostream.h>
void writearr(int, int[]);
int* readarr(int, int[]);
int main()
{cout << "n= ";
int n;
cin >> n;
int a[20];
int* p = readarr(n, a);
writearr(n, p);
cout << endl;
return 0;
}
void writearr(int m, int arr[])
{for (int i = 0; i <= m-1; i++)
cout << "arr[" <> arr[i];
}
return arr;
}

Въпрос: Допустима ли е конструкцията: readarr(n, a)[i], където i е цяло число от 0 до n-1? Ако това е така, какъв е резултатът от изпълнението му?

Задача 79. Да се напише функция, която намира и връща като резултат конкатенацията на два низа. Функцията да променя първия си аргумент като в резултат той да съдържа конкатенацията на низовете.
Програма Zad79.cpp решава задачата.

Program Zad79.cpp
#include <iostream.h>
int len(char*);
char *cat(char*, char*);
int main()
{char s1[100];
cout << "s1= ";
cin >> s1;
cout << "s2= ";
char s2[100];
cin >> s2;
cout << cat(s1, s2) << " " << s1 << '\n';
return 0;
}
int len(char* s)
{int k = 0;
while (*s)
{k++; s++;
}
return k;
}
char* cat(char *s1, char *s2)
{int i = len(s1);
while (*s2)
{s1[i] = *s2;
i++;
s2++;
}
s1[i] = '\0';
return s1;
}

Задачи

Задача 1. Въпреки многото й недостатъци, следващата програма е доста поучителна. Тя дефинирана функцията readarr, която има за формален параметър броя на елементите на масива и връща едномерен масив, определен чрез указател към първия му елемент.
#include <iostream.h>
int a[20];
void writearr(int, int[]);
int* readarr(int);
int main()
{cout << "n= ";
int n;
cin >> n;
int* p = readarr(n);
writearr(n, p);
cout << ‘\n’;
return 0;
}
void writearr(int m, int arr[])
{for (int i = 0; i <= m-1; i++)
cout << "arr[" <> a[i];
}
return a;
}

извършете експерименти с тази програма.

Задача 2. Да се напише програма, която въвежда полиномите:

и реалната променлива x и намира и извежда стойностите на полиномите в x.
Задача 3. Да се напише програма, която въвежда стойности на редиците:
a0, a1, ..., an-1,
b0, b1, ..., bm-1,
c0, c1, ..., cp-1

и намира и извежда AR1, AR2, BR1, BR2, CR1 и CR2, където за дадена редица x0, x1, ..., xk-1

Задача 4. Да се напише функция, която намира разстоянието между две точки в равнината, зададени чрез координатите си (x1, y1) и (x2, y2). Като се използва тази функция да се напише програма, която чете координатите на n точки (n ≥ 1) от равнината и намира и извежда разстоянието между всеки две от тях.
Задача 5. да се напише функция, която връща стойност true, ако a, b и c са страни на триъгълник и false - в противен случай. Като се използва тази функция, да се напише програма, която въвежда стойности на елементите на матрицата A3xn и определя кои от тройките (a[0][i], a[1][i], a[2][i]), i = 0, 1, ..., n-1 могат да служат за страни на триъгълник.
Задача 6. Да се напише функция, която връща стойност true ако редицата от цели числа x0, x1, ..., xk-1 има поне два последователни нулеви елемента. Като се използва тази функция, да се напише програма, която намира и извежда номерата на редовете на матрицата A [n x n], от цели числа, които имат поне два последователни нулеви елемента.

Задача 7. Да се напише функция, която намира сумата на два полинома. Като се използва тази функция, да се напише програма, която намира сумата на всеки два от полиномите:

Задача 8. Даден е триъгълник със страни a, b и c. Да се напише програма, която намира медианите на триъгълник, страните на който са медианите на дадения триъгълник.

Упътване: Медианата към страната a на триъгълника е равна на

Задача 9. Дадени са координатите на върховете на n триъгълника. Да се напише програма, която определя, кой от триъгълниците е с по-голямо лице.

Задача 10. Дадени са естественото число p > 1 и реалните квадратни матрици с размерности n x n - A, B и C. Да се напише програма, която намира матрицата

Допълнителна литература

Ст. Липман, Езикът C++ в примери, “КОЛХИДА ТРЕЙД” КООП, С. 1993.
2. И. Момчев, К. Чакъров, Програмиране III, C и C++, ТУ, С. 1996.
3. Д. Луис, C/C++ бърз справочник, ИнфоДАР, С. 1998.
4. B. Stroustrup, C++ Programming Language. Third Edition, Addison – Wesley, 1997.

**ivakavlad** · 10-20-2010, 23:49

Глава 8

Програмиране от по-висок ред в C++

Функция, някои формални параметри на която са функции, се нарича функция от по-висок ред.
В езика C++ е възможно формален параметър на функция да е указател към функция, а също е възможно резултатът от изпълнението на функция да е указател към функция. Това позволява да се реализират функции от по-висок ред, а също такива които връщат функция.

**ivakavlad** · 10-20-2010, 23:51

1.Указател към функция

Името на функция е константен указател, сочещ към първата машинна инструкция от изпълнимия й машинен код. В езика C++ е възможно да се дефинират променливи, които са указатели към функции (Фиг. 1).

<дефиниция_на_променлива_ук азател_към_функция> ::=
<тип_на_функция>(*<указател_к ъм_функция>)(<формални_парам етри>)
[= <име_на_функция>];
където
- <указател_към_функция> е идентификатор;
- <име_на_функция> e идентификатор, означаващ име на функция от тип <тип_на_функция> и параметри - <формални_параметри>;
- <тип_на_функция> и <формални_параметри> са аналогични на съответните от заглавието на дефиниция функция. Имената на параметрите могат да се пропуснат.

Фиг. 1.

Забележка: Скобите, ограждащи *<указател_към_функция>, са задължителни. В противен случай дефиницията ще се изтълкува от компилатора като декларация на функция с име < указател_към_функция>, с параметри - <формални_параметри> и тип – указател към <тип_на_функция>.
В резултат на дефиницията на променлива от тип указател към функция, за променливата се отделят 4B ОП, която е с неопределена стойност, ако дефиницията е без инициализация, и съдържа адреса на първата машинна команда от изпълнимия код на функцията, чрез която е направена инициализацията, ако дефиницията е с инициализация.

Примери:
double (*p)(double, double);
е дефиниция на променлива p от тип указател към функция от тип double с два аргумента също от тип double. В резултат за p се отделят 4B ОП, които са с неопределена стойност.
int (*q)(int, int*);
дефинира променлива q от тип указател към функция от тип int, с два аргумента, единият от които цял, а другият – указател към int. За q се отделят 4B ОП, които са с неопределена стойност.
3. Нека са дефинирани следните функции за сортиране на числови редици:
void bubblesort(int, int*); // метод на мехурчето
void mergesort(int, int*); // сортиране чрез сливане
void heapsort(int, int*); // пирамидално сортиране
Променливата r може да е указател към тези функции ако е дефинирана по следния начин:
void (*r)(int, int*);
r не може да е указател към функциите:
int f1(int, int*);
int f2(int, int*);
Указател към последните може да е променливата s, където:
int (*s)(int, int*);
Горните дефиниции на p, q, r и s са без инициализации.
Дефиниците на променливите x и y
void (*x)(int, int*) = bubbesort;
int (*y)(int, int*) = f2;
са с инициализация. За всяка от тях се отделят 4B ОП, в която памет се записват адресите на първите команди на изпълнимите кодове на bubblesort и f2 съответно.
Присвояването се извършва по стандартния начин.
Пример:
r = mergesort;
x = heapsort;
След инициализация на променлива от тип указател към функция, чрез променливата може да се осъществи обръщение към конкретна функция. Така се предоставя ефективен способ за предаване на управлението към потребителски и библиотечни функции.
Обръщението към функция освен директно може да се осъществява и индиректно – чрез указател към нея.
Пример:
void (*r)(int, int*) = bubblesort;
bubblesort(n, a); // директно обръщение
(*r)(n, a); // индиректно обръщение, чрез r.

Забележка: Някой компилатори, в това число и на Visual C++ 6.0, допускат извикването на функция чрез указател да се осъществява и само чрез името на указателя.
Пример:
void (*r)(int, int*) = bubblesort;
r(n, a); // индиректно обръщение към bubblessort,
// чрез r.

**ivakavlad** · 10-20-2010, 23:51

2. Функциите като формални параметри

Указател към функция може да е формален параметър на функция. Ще илюстрираме тази възможност с няколко примери.

Задача 80. Да се напише функция, която реализира математическата абстракция:

където a и b са дадени реални числа (a ≤ b), f е реална едноаргументна функция, задаваща терма, а next е реална едноаргументна функция, задаваща стъпката за промяна на управляващия параметър на сумата.

За да решим задачата ще предложим няколко частни решения.
а) Да се дефинира функция, която намира стойността на сумата:
sin(a) + sin(a+1) + sin(a+2) + ... + sin(b),
където a и b са дадени реални числа. Функцията sum_sin решава задачата.

double sum_sin(double a, double b)
{double s = 0;
for (double i = a; i <= b + 1E-14; i = i + 1)
s = s + sin(i);
return s;
}

б) Да се дефинира функция, която намира стойността на сумата:
cos(a) + cos(a + 0.2) + cos(a + 0.4) + ... + sin(b)
където a и b са дадени реални числа. Функцията sum_cos решава задачата.

double sum_cos(double a, double b)
{double s = 0;
for (double i = a; i <= b + 1e-14; i = i + 0.2)
s = s + cos(i);
return s;
}
Забелязваме, че тези две функции се “приличат”. Написани са по следния общ шаблон:

double <name>(double a, double b)
{double s = 0;
for (double i = a; i <= b + 1e-14; i = <next>(i))
s = s + <f>(i);
return s;
}

Елементите, по които функциите sum_sin и sum_cos се различават са означени с <...> в шаблона. Това са две функции – f, означаваща терма и next - стъпката на сумата. Като използваме възможността формален параметър на функция да е указател към функция, можем да изнесем <f> и <next> като формални параметри на функцията и да обобщим тези частни случаи. Така стигаме до функцията sum:

Function Zad80.cpp
double sum(double a, double b, double (*f)(double),
double (*next)(double))
{double s = 0;
for (double i = a; i <= b + 1е-14; i = next(i))
s = s + f(i);
return s;
}

Обръщенията към sum:
sum(a, b, sin, next1)
sum(a, b, cos, next2)
където
int next1(double x)
{return x + 1;
}
int next2(double x)
{return x + 0.2;
}
реализират горните частни случаи.
sum е функция от по-висок ред. В нея третият и четвъртият параметри са указатели към функции.
Като използваме sum, може да дефинираме sum_sin и sum_cos по следния начин:

double sum_sin(double a, double b)
{return sum(a, b, sin, next1);
}
double sum_cos(double a, double b)
{return sum(a, b, cos, next2);
}

Задача 81. Да се напише функция, която реализира математическата абстракция:

където a и b са реални числа, f е реална едноаргументна функция, задаваща терма, а next - реална едноаргументна функция, задаваща стъпката за промяна на управляващия параметър на произведението. Да се включи тази функция в програма и се намерят:
tg(1) * tg(1.5) * tg(2) * tg(2.5) * tg(3)
и
arctg(1) * arctg(1.1) * arctg(1.2) * arctg(1.3).

Програма Zad81.cpp решава задачата.

Program Zad81.cpp
#include <iostream.h>
#include <math.h>
double prod(double, double, double (*)(double),
double (*) (double));
double next1(double);
double next2(double);
int main()
{cout << prod(1, 3, tan, next1) << '\n';
cout << prod(1, 1.3, atan, next2) << '\n';
return 0;
}
double prod(double a, double b, double (*f)(double),
double (*next)(double))
{double s = 1.0;
for (double i = a; i <= b + 1e-14; i = next(i))
s = s * f(i);
return s;
}
double next1(double x)
{return x + 0.5;
}
double next2(double x)
{return x + 0.1;
}

В тази програма е дефинирана функцията от по-висок ред prod, реализираща исканата абстракция. В нея третият и четвъртият параметри са указатели към функции. В главната програма са направени две обръщения към нея
prod(1, 3, tan, next1)
и
prod(1, 1.3, atan, next2),
намиращи търсените произведения.
Забелязваме, че функциите sum и prod си “приличат”. Написани са по следния общ шаблон.

double <name>(double a, double b, double (*f)(double),
double (*next)(double))
{double s = <null_val>;
for (double i = a; i <= b + 1е-14; i = next(i))
s = s <op> f(i);
return s;
}

И в този случай, елементите, по които sum и prod се различават са оградени с <...>. Това са операцията op и нулата на операцията - null_val. Отново ще изнесем op и null_val като формални параметри на функцията. Тъй като op е бинарна инфиксна операция, а не име на функция, ще дефинираме помощна реална функция с име op, с два реални параметъра и връщаща резултата от прилагането на операцията op към аргументите на функцията op. Така получаваме още едно обобщение на горните абстракции – функцията от по-висок ред accumulate (Задача 82).

Задача 82. Да се напише програма, която реализира следната математическа абстракция:

където с

**ivakavlad** · 10-20-2010, 23:52

3. Функциите като върнати оценки

Функция може да върне като резултат указател към друга функция. Например, декларацията
int (*fun(int, int))(int*, int);
определя функцията fun с два цели аргумента и връщаща указател към функция от тип
int (*)(int*, int).
Ако зададем име на този тип чрез typedef, този запис може да се опрости:
typedef int (*fun-point)(int*, int);
fun-point fun(int, int);

Задача 84. Да се напише програма, която по зададено реално число x и символ (a, b, c или d) избира за изпълнение функция, определена чрез зависимостта:

Програма Zad84.cpp решава задачата.

Program Zad84.cpp
#include <iostream.h>
#include <math.h>
typedef double (*f_type)(double);
f_type table(char ch)
{switch(ch)
{case 'a': return sin; break;
case 'b': return cos; break;
case 'c': return exp; break;
case 'd': return log; break;
default: cout << "Error \n"; return tan;
}}
int main()
{char ch;
cout << "ch= ";
cin >> ch;
if (ch < 'a' || ch >'d') cout << "Incorrect input! \n";
else
{double x;
cout << "x= ";
cin >> x;
cout << table(ch)(x) << '\n';
}
return 0;
}

Илюстрираните в тази част възможности на езика C++ показват, че данните от тип функции съществено не се отличават от другите видове данни. Това показва високата степен на унифицираност в езика и води до увеличаване на изразителната му сила.

Задачи

Задача 1. Като използвате функцията от по-висок ред sum, намерете:

Задача 2. Като използвате функцията от по-висок ред prod, намерете:
а) xn, където x е дадено реално, а n – дадено естествено число.
б) n!, където n е дадено естествено число.
в) броят на вариациите от n елемента от k-ти клас (n и k са дадени естествени числа, 0 ≤ k ≤ n).
г) броят на комбинациите от n елемента от k-ти клас (n и k са дадени естествени числа, 0 ≤ k ≤ n).

Допълнителна литература

1. Ст. Липман, Езикът C++ в примери, “КОЛХИДА ТРЕЙД” КООП, С. 1993.
2. Д. Луис, C/C++ бърз справочник, ИНФОДАР, С. 1998.
3. М. Тодорова, Езици за функционално и логическо програмиране – функционално програмиране, СОФТЕХ, С., 1998.
4. B. Stroustrup, C++ Programming Language. Third Edition, Addison – Wesley, 1997.

**ivakavlad** · 10-21-2010, 00:12

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

**Foreverbg** · 10-21-2010, 09:42

Защо си мисля, че това си го взел от един учебник?

**capslock** · 10-21-2010, 16:29

Първоначално написано от Foreverbg

Защо си мисля, че това си го взел от един учебник?

защото можеби и така

**GregoryHouse** · 10-21-2010, 17:36

Човека си играе да ви го дигитализира... Евала за усилията!

**Foreverbg** · 10-21-2010, 19:16

Първоначално написано от GregoryHouse

Човека си играе да ви го дигитализира... Евала за усилията!

Какво дигитализира?

Абсолютно същото го имам на компа.

Да не говорим, че човек,който никога не се е занимавал с програмиране нищо няма да разбере.

**GregoryHouse** · 10-22-2010, 03:31

Първоначално написано от Foreverbg

Първоначално написано от GregoryHouse

Човека си играе да ви го дигитализира... Евала за усилията!

Какво дигитализира?

Абсолютно същото го имам на компа.

Да не говорим, че човек,който никога не се е занимавал с програмиране нищо няма да разбере.

Не знаех, че C++ е за хора които не се занимават с програмиране...Ко лаеш ся? Ко ти пречи човека да си пише и да си прави тема, да си влага усилия някакви? Българска му работа...

Тема: Уроци по С++

Контрол над темата

Търси тема

Изглед

Правила за публикуване