Променливи, масиви и структури
Variables, arrays and structures
Какво са променливи и масиви? Какво са структури и за какво ще ги ползваме?
Автор: Александър Георгиев
Тази тема
няма за цел да ви научи какво са променливи и масиви. В нея искаме да преговорим какво са те и да ви запознаем с някои често срещани грешки, свързани с тях. Също искаме да ви покажем какво са структурите и колко по-красив (и четим) може да стане кодът ни с тяхна помощ.
Променливи и масиви
Всеки от вас трябва вече да знае какво са променливи и масиви (ако не знаете - може би все още ви е твърде рано да четете нататък). Все пак накратко, кои бяха основните променливи и за какво се ползваха те? В тази статия ще считаме, че работим на 32 битов компилатор (което е най-честият случай в наши дни, макар и да има изгледи скоро това да се промени).
int
Най-често ползваната променлива - 32 битово цяло число със знак. Името ѝ идва от "integer", тоест "цяло число". Много честа грешка с него е така нареченият "oвърфлоу" (overflow) - след дадена операция резултатът да надхвърля поддържаните стойности на типа. Като заговорихме за тях - числата, които
int поддържа, са в интервала [-2147483648, 2147483647].
| ! | Внимавайте много за овърфлоу! Това е една от грешките, които дори най-опитните състезатели понякога допускат. |
Разбира се, това лесно може да си го сметнете по време на състезанието, вместо да го помните - тъй като типът е 32 битов, за положителни и отрицателни има по 2
31 стойности. Тъй като, обаче, има и 0 между тях, положителните са с една по-малко, като така интервалът е [-2
31, 2
31-1].
Имаме K кошари, всяка с по M места в нея. Можем ли да поберем N овце в тях, ако всяка овчица заема по едно място? Знаем, че 1 ≤ N, M, K ≤ 100,000.
Тази изключително проста задача може да ни подведе. Очевидно, трябва просто да проверим дали общият брой места е по-малък от броя овце (в който случай не можем). Тоест
K *
M <
N. Допълнително подвеждащо в случая е, че броят овце може да е само до 100,000 (сравнително малко число, в света на състезателната информатика). Това само "приспива" вниманието ни към overflow. Както се оказва, ако
K = 33333 и
M = 99999, то резултатът от умножението е 3,333,266,667, тоест малко над 2
31. И получихме овърфлоу. Нещо повече, тъй като това число е между 2
31 и 2
32, то то ще е отрицателно и със сигурност по-малко от
N. И бихме върнали, че няма да можем да съберем овчиците, докато всъщност можем и ще ни остане мнооооого място :) Та, внимавайте. You've been warned.
Аа, преди да продължим нататък. Какво все пак е решението? Ами, когато пресметнем (или подозираме), че може да се получи овърфлоу, просто кастваме променливите към някой достатъчно голям тип. В случая, това би било
long long или
double.
unsigned int
Или също познат като само
unsigned. Това е тип, който го няма в Java. Странно, нали? С него можем да представяме 32-битови цели числа без знак. По всички свои характеристики той е точно като
int, само че няма отрицателни числа. Тоест всичките му стойности са неотрицателни. Тоест покриваният от него интервал е [0, 2
32-1]. Тоест [0, 4294967295]. И също може да овърфлоуне!
short
Това е малкото братче на
int. Той е само 16 бита (тоест половината от
int). И вече би трябвало да можете сами да му сметнете границите, нали? Все пак: [-2
15, 2
15-1] или [-32768, 32767]. Някои хора твърдят, че в днешно време не се ползва - ами що-годе са прави, с изключение на много специфични задачи, където ни трябва страшно много памет, а отговорът е малък. В този случай можем да намалим паметта си на половина ако ползваме
short вместо
int.
unsigned short
Погледнете
unsigned int. Еми същото е, само че 16 битово.
char
Най-малкото братче на целите числа - само 8 бита. Сметки, сметки и стигаме до [-128, 127]. Но това е твърде малко! За какво бихме го ползвали? Ами, примерно, за символи. И името му оттам си идва - "char" от "character".
На входа ви е даден текст с N символа. От вас се иска да изпечатате отново N символа, които са 0 при срещане на "non-printable" символ на входа, и 1 за всеки "printable" такъв. Non-printable (тоест "невидими") символи са, например, шпация, табулация, нов ред и др. Известно ви е, че всички non-printable characters са с ASCII кодове от 0 до 32, включително.
Решението е доста просто - четем в масив текста, и после за всеки символ проверяваме дали е non-printable или printable, като печатаме съответно 0 или 1.
void
eval(char
*
text,
int
textLen) {
for
(int
i =
0
;
i <
textLen;
i+
+
) {
if
(text[i] <
=
32
) // Символът е non-printable
fprintf(stdout
,
"0"
);
else
// В противен случай символът е printable
fprintf(stdout
,
"1"
);
}
}Тук приемаме, че четенето на входа и изчисляването на дължината са верни. Все пак, тази функция не би печатала правилния резултат. Защо?
This is the input, which will break the solution.
Това е входът, който би счупил решението.
В този вход няма никакви твърде специални символи освен букви, шпации, нов ред и препинателни знаци. Това, което има, обаче, е кирилишки символи. А те имат стойности, по-големи от 128. Масивът ни с текста, обаче е от тип
char, който е тип със знак. Тоест кирилишките символи ще станат отрицателни числа. Във функцията ние проверяваме дали символите са ≤ 32 и тъй като те са отрицателни ще ги счетем за non-printable. Уф, пак тоя овърфлоу. Много е досаден, нали? Решението е да четем входа в unsigned char, при което това решение би работило.
long long
| ! | Освен за вече многократно споменатия overflow, също така е хубаво да внимавате и за деление на нула. Не го правете. Не е хубаво. Само Чък Норис може да дели на нула.
|
Това е един не особено стандартен тип, но се поддържа от повечето модерни компилатори (в "новия стандарт" C++11 вече е стандартен тип). Той е точно като
int, но е 64-битов. Поддържа интервала [-9223372036854775808, 9223372036854775807].
Всъщност никой от състезателите не помни какви
точно са границите. Аз, примерно, помня само, че 2
32 е около 4 милярда (тоест лимитът на
int е малко повече от 2 милярда). За long long помня, че е около 10
18 и е достатъчно да се съберат две такива числа (тоест е повече от 2 * 10
18) без да овърфлоуне. И става за кастване ако умножаваме два инта.
Значи, ако имаме
long long longVar = 12345 * 678910;, то няма да имаме проблеми, тъй като резултатът от умножението се събира в 64-битово (signed) число?
Не! Това е
ужасно честа грешка, запомнете я!
| ! | Забележете, че тъй като резултатът от дадена аритметична операция се пази в променливата с "най-голям" тип, то не е нужно да кастваме всички участващи в умножението променливи и/или константи.
|
Независимо, че числото от лявата част на знака равно е от тип
long long, по default целочислените константи в кода на C/C++ са от тип
int. А при 32-битов компилатор умножаваните числа ще бъдат от 32-битов тип, като тяхното произведение ще бъде от типа на най-голямата от тях. Но тъй като и 12345 и 678910 са 32-битови числа, то и резултатът ще бъде 32-битов и
чак после ще бъде конвертиран към 64-битов (но вече ще е грешен). Тоест
ще се получи овърфлоу, въпреки достатъчно голямата променлива от лявата страна. За да се справите с това трябва да кастнете поне едно от числата към
long long, което може да стане по един от следните два начина:
long long longVar = (long long)12345 * 678910;long long longVar = 12345LL * 678910;
double
Число с плаваща запетая (floating point) в своя 64-битов вариант. Най-вече ще го ползвате в геометрични задачи, но от време на време и за други неща. За сега може да считате, че то поддържа от много големи числа до много малки такива. Но не винаги е напълно прецизно. Например
1.0 / 3.0 не е точно една трета. Поради не толкова простото му устройство и многото трикове, които трябва да знаем, за да не допускаме грешки при ползването на дабъли, ще посветим цяла
тема за тях.
double
one =
0
;
for
(int
i =
0
;
i <
31
;
i+
+
)
one +
=
1.0
/
31.0
;
if
(one =
=
1.0
)
fprintf(stdout
,
"Yeah!\n"
);
else
fprintf(stdout
,
"Noooooo!\n"
);
Кое от двете ще се изпечата? Мислите си, че 31 * (1.0 / 31.0) == 1? Неее...
long double
Същото като
double, но с малко по-голяма точност и малко по-бавно. Ползвайте го ако правите някакви сметки, в които ви трябва много голяма прецизност. Отново не е стандартен тип, но все пак се поддържа почти навсякъде. В повечето компилатори представлява 80-битово число с плаваща запетая, с изключение на Майкрософтския компилатор, където е просто синоним на
double.
float
Не го ползвайте. Ползвайте
double.
bool
Булев тип. На теория трябва да е само един бит (
0 за
false и
1 за
true). На практика компютърът има големи затруднения с индексирането на единичен бит, та променлива от тип
bool би заемала цели 8 бита. В C++ няма проблем с ползване на цели числа в логически изрази (тъй като 0 се евалюира до
false, а всяко друго число до
true), така че можете спокойно да не го ползвате. Въпреки това, употребата му води до по-ясен код, затова е хубаво ако имате булев флаг то той да е от тип
bool.
Допълнително в
тази тема са показани няколко много често ползвани класа (string, vector) от стандартната библиотека на C++, които до голяма степен се ползват като стандартни типове. Тя, обаче, за сега няма да ви трябва твърде много, и ще я разгледаме задълбочено по-нататък.
Преди да приключим с променливите отново ще натъртим, че това са размерите, които
обикновено приемат те в популярните 32-битови компилатори днес. По стандарт обаче те не са
длъжни да са толкова големи. Всъщност стандартът ги определя като "поне толкова големи". Тоест
short може спокойно да е 32 битов, например. Но за сега това не трябва да е нещо, което да ви засяга.
Масиви
| ? | Двумерните масиви понякога биват наричани "матрици". Тъй като обаче този термин се ползва и в математиката за нещо различно, ние ще го избягваме. |
Също така се очаква от вас да знаете какво са масиви. Просто лесен начин да пазим много променливи от еднакъв тип.
Това, което може би
не знаете, обаче, е как се пазят в паметта те. Очевидно, едномерните масиви са просто последователност от елементи, заделени в последователен блок от паметта. Една от причините за бързината на C++ е, че двумерни и многомерни масиви като цяло също се заделят като един блок памет.
| ? | В други езици, като Java например, многомерните масиви не винаги са последователно парче памет. Например int a[N][M] може да са N парчета памет, всяко с размер M * 4 байта. Това съответно забавя програмата, тъй като за да се вземе дадена клетка от масива трябва да се направят две индексации, а не само една. |
Така, например, ако имате масив
int a[N][M][K], то той ще представлява указател към
N*M*K клетки от тип
int. В случая с повечето 32-битови компилатори днес, това би било парче памет с размер
N*M*K*4 байта. И тъй като паметта е едномерна, тоест последователна, реално този тримерен масив вътрешно се представя като едномерен. Така компилаторът работи с масив
int a[N*M*K]. Когато индексираме
a[x][y][z], той всъщност взима
int[x * M * K + y * K + z]. Това рядко ще ви трябва на практика, но го споменаваме за да знаете две неща:
| ? | Всъщност ползването на едномерен и петмерен масив не е напълно еднакво бързо, тъй като трябва да се изчисли индекса (тоест да се направят известен брой умножения и събирания). Тъй като, обаче, адресирането в паметта обикновено е много по-бавна операция от умножението и събирането, то можем да ги пренебрегнем. |
Поради този начин на представяне на масивите, взимането на дадена клетка в многомерен (например петмерен) масив е също толкова бързо, колкото и в едномерен. За разлика от Java, можете спокойно да ползвате многомерни масиви без да се притеснявате за проблеми със скоростта.| ? | По-нови езици като Java имат така наречения "array bounds checking", тоест проверка дали индекса, който ползваме, е валиден. Това прави работата с масиви по-бавна, но пък ни предупреждава веднага, когато объркаме нещо. |
Може да имате грешна индексация, но това да не доведе до излизане извън масива. Например ако имате int a[20][10] и индексирате a[10][15] = 42;, това ще е вътре в масива, но реално ще е клетката на позиция a[11][5]. Така програмата ви няма да крашне, но най-вероятно няма да работи правилно.
Структури
Структурите са нещо много красиво за ползване, и в същото време много рядко ползвани по състезания. Те могат да допринесат значително за четливостта на кода ни, като в същото време не го правят ни най-малко по-бавен (даже, понякога, го правят по-бърз).
| ? | Структурите, до голяма степен, са едно и също нещо с класовете в C++, с няколко дребни разлики. Може би най-основната от тях е, че всичко в структурата е по подразбиране public, докато в класовете е private. За това ще учите повече в университета. |
Но първо да видим - какво всъщност е структура? Това е специален тип, който ние създаваме, като специфицираме точно каква информация (какви типове данни и колко на брой променливи) да съдържа той.
Например, често в геометрични задачи се налага да пазим точки (да кажем в тримерното пространство). За да пазят
N такива точки, много състезатели биха ползвали три масива
double x[N], y[N], z[N], като във всеки масив те биха пазили по една от координатите на точките. Има много ситуации, в които този лесен начин би довел до по-неудобен код. Например, за да подадем точка на дадена функция, то трябва да подадем всяка от координатите ѝ поотделно. Друг вариант е да подадем индекса й, като тогава масивите пък трябва да са глобални. Още по-голям проблем става ако искаме да преподредим точките.
| ? | Обикновено ползваме структура, когато искаме просто да енкапсулираме по-сложна информация, а клас - когато искаме да имаме допълнителни методи, които вършат някакви действия върху тези данни.
|
Вместо това, обаче, можем да създадем структура, която да ни представлява една точка. Тя би била
struct Point {double x, y, z;};, като би ни трябвал само един масив (вместо три):
Point points[N];. Подаването на точка на дадена функция става чрез подаването на една единствена променлива от тип Point. Разместването на точките (примерно при сортиране) става значително по-лесно, но за това ще говорим по-късно в
тази тема.
Структурите предоставят много повече свобода. Например, няма проблем в нея да пазим различни типове променливи. Ако искаме да имаме тип, който представлява ученик, то може би бихме искали да знаем за него име, фамилия, ЕГН, среден успех, и номер в класа. Няма проблем!
struct
Student {
string
firstName;
string
lastName;
char
egn[11
];
double
averageGpa;
int
number;
};
След дефиницията можем да го ползваме както всеки друг тип. Например, за да имаме променлива
student, която съдържа информация за един ученик, бихме ползвали:
| ? | Елементите от даден композитен тип (структура или клас) наричаме "обекти". От там произлиза и името "Обектно-ориентирано програмиране", с което ще се запознаете в университета. |
Достъпването на данните в структура става с точка. Например за да променим името на ученикa бихме ползвали:
student.firstName =
"Alexander"
;
Ако искаме да изпечатаме номера му в класа, бихме направили:
fprintf(stdout
,
"%d\n"
,
student.number);
Ако имахме масив от точки и искаме да изпечатаме координатите на
i-тата точка, то бихме ползвали:
fprintf(stdout
,
"%lf %lf %lf\n"
,
points[i].x,
points[i].y,
points[i].z);
Като цяло ще ползваме структури за много неща из темите, така че ще имате възможност с времето да ги опознаете в по-големи детайли. Дадената тук информация е много повърхностна. Например изобщо не споменахме как да изчисляваме какъв е размерът на дадена структура (и че има нетривиални правила, по които да го изчислим), както и за функции (наричани "методи") в самата структура. Малко повече информация за класове ще разгледаме в
тази тема. Ако ви е интересно, можете да намерите по-подробна информация
тук.
Много състезатели (включително голяма част от добрите състезатели) рядко ползват структури, тъй като тяхната употреба изисква малко повече код и съответно повече време. Аз лично считам, че малкото загубено време в дефинирането на структурата се отплаща многократно в по-дълги задачи (когато се налага да представяте по-сложни структури) и
особено в геометрични задачи. Все пак, ползването им на състезания е напълно optional.
Допълнителни материали
- Обща информация какво е променлива в Wikipedia
- Подробна статия за променливите в C++ в cplusplus.com
- Статия за структурите в C++ в Wikipedia
- Подробна статия за структурите в C++ в cplusplus.com
Страницата е посетена 11444 пъти.