Променливи, масиви и структури

Variables, arrays and structures

Какво са променливи и масиви? Какво са структури и за какво ще ги ползваме?

Автор: Александър Георгиев

Тази тема няма за цел да ви научи какво са променливи и масиви. В нея искаме да преговорим какво са те и да ви запознаем с някои често срещани грешки, свързани с тях. Също искаме да ви покажем какво са структурите и колко по-красив (и четим) може да стане кодът ни с тяхна помощ.

Променливи и масиви

Всеки от вас трябва вече да знае какво са променливи и масиви (ако не знаете - може би все още ви е твърде рано да четете нататък). Все пак накратко, кои бяха основните променливи и за какво се ползваха те? В тази статия ще считаме, че работим на 32 битов компилатор (което е най-честият случай в наши дни, макар и да има изгледи скоро това да се промени).

int

Най-често ползваната променлива - 32 битово цяло число със знак. Името ѝ идва от "integer", тоест "цяло число". Много честа грешка с него е така нареченият "oвърфлоу" (overflow) - след дадена операция резултатът да надхвърля поддържаните стойности на типа. Като заговорихме за тях - числата, които int поддържа, са в интервала [-2147483648, 2147483647].

!	Внимавайте много за овърфлоу! Това е една от грешките, които дори най-опитните състезатели понякога допускат.

Разбира се, това лесно може да си го сметнете по време на състезанието, вместо да го помните - тъй като типът е 32 битов, за положителни и отрицателни има по 2³¹ стойности. Тъй като, обаче, има и 0 между тях, положителните са с една по-малко, като така интервалът е [-2³¹, 2³¹-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³¹. И получихме овърфлоу. Нещо повече, тъй като това число е между 2³¹ и 2³², то то ще е отрицателно и със сигурност по-малко от N. И бихме върнали, че няма да можем да съберем овчиците, докато всъщност можем и ще ни остане мнооооого място :) Та, внимавайте. You've been warned.

Аа, преди да продължим нататък. Какво все пак е решението? Ами, когато пресметнем (или подозираме), че може да се получи овърфлоу, просто кастваме променливите към някой достатъчно голям тип. В случая, това би било long long или double.

unsigned int

Или също познат като само unsigned. Това е тип, който го няма в Java. Странно, нали? С него можем да представяме 32-битови цели числа без знак. По всички свои характеристики той е точно като int, само че няма отрицателни числа. Тоест всичките му стойности са неотрицателни. Тоест покриваният от него интервал е [0, 2³²-1]. Тоест [0, 4294967295]. И също може да овърфлоуне!

short

Това е малкото братче на int. Той е само 16 бита (тоест половината от int). И вече би трябвало да можете сами да му сметнете границите, нали? Все пак: [-2¹⁵, 2¹⁵-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³² е около 4 милярда (тоест лимитът на int е малко повече от 2 милярда). За long long помня, че е около 10¹⁸ и е достатъчно да се съберат две такива числа (тоест е повече от 2 * 10¹⁸) без да овърфлоуне. И става за кастване ако умножаваме два инта.

Значи, ако имаме 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, която съдържа информация за един ученик, бихме ползвали:

Student 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.

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

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 13371 пъти.