Доброго времени суток. В последнее время, я обратил внимание на то, что большинство моих знакомых, вне зависимости от образования, предыдущей квалификации и прочего, медленно но уверенно обращают свои стопы в сторону сферы ИТ. Занятно, но химики, биологи, врачи и даже сотрудники фин. учреждений переквалифицируются в ИТ-специалистов. Скорее всего это связано с тем, что в странах СНГ эта индустрия процветает более других, поскольку практически полностью ориентирована на западные компании.



Но суть не в этом. Основная мысль которую я из этого вынес - на данный момент существует большое количество людей, которые хотят обучится ИТ-специальностям, в частности программированию, при чем начиная с самого начала. Соответственно, мной было принято решение опубликовать небольшой курс обучения программированию. Я ни в коем случаи не претендую на исчерпывающий, фундаментальный труд. Это скорее "каркас", который позволит продолжить обучение по другим материалам.

Зачем нужен этот "каркас"? За последние несколько лет, я провел очень много собеседований, на различные позиции в различные компании, и что занимательно, везде мне попадались люди не имеющие целостного понимания программирования, как такового. То есть их подход к программированию - эмпирический, а не теоретический. Кто-то может сказать "Ну и что? Главное что они делают свою работу, ведь деньги платят именно за это." И в целом будет прав, ровно до того момента пока не возникнет новая для человека задача. Опыт безусловно важный аспект, но имея целостное понимание программирования значительно легче решать нестандартные задачи.



Что ж с мотивацией понятно, перейдем к более предметной части. Излагаемые концепции будут насколько это возможно отвязаны от конкретного языка программирования, но примеры будут все же на вполне конкретном языке - C++. Почему? Я не считаю правильным подход "научитесь плавать - пустим воду", то есть написание программ на псевдоязыке. Причины по которым был выбран именно C++, следующие. Во-первых, этот язык (если быть совсем точным, то его прародитель C, хотя от части и C++) является источником возникновения практически всех современных языков программирования. В том числе Java, JavaScript, Perl, PHP, Groovy, Python, Objective-C, C# и прочих. Потому изучение C++ заметно упрощает в будущем изучение любого из вышеперечисленных языков (и многих других). Во-вторых, это один из классически выбираемых языков для обучения, а я не ставлю себе цель быть оригинальным, скорее для меня важнее быть доступным, потому я не выбираю Erlang или Lisp.

Типы данных




Теперь можно перейти и к сути. Как гласит заголовок этой статьи речь здесь пойдет о типах и структурах данных. Зачастую в программировании выделяют следующие типы данных: "натуральное число"(в отличии от математического определения включает ноль, в остальном идентично), целое число, рациональное число с фиксированной точностью, символ(буква, спец. символ, цифра и т.д.) и логическая величина(принимает значения "истина", "ложь"). В многих языках так же существует понятие перечислимого типа(программист сам задает перечень значений, при описании данного типа), а в некоторых даже функция лишь еще один тип данных(о функциях подробнее будет рассказано в следующем посте), но это уже языковые тонкости, основных типов все же пять.



Вот как они выглядят в C++:

unsigned int n;
int z;
float r;
char s;
//логического типа в C++, в отличии от большинства других языков нет. Почему? Расскажу в следующей статье


В предыдущих четырех строчках кода(последняя - комментарий) на C++ мы ввели "натуральную" переменную n, целую z, и так далее. Теперь мы можем использовать эти переменные, для того чтобы записывать в них значения либо считывать его. Например, так:

cin>>s;


Приведенный выше фрагмент кода считывает введенный пользователем символ и записывает его в переменную s. Далее мы можем использовать это значение, обращаясь к переменной s. Поскольку память компьютера ограничена, все типы данных имеют свои ограничения зависящий от языка, платформы и многого другого. В частности в C++, int и unsigned intимеют размер 4 байта и находятся в диапазоне от -2147483648 до 2147483647 и от 0 до 4294967295 соответственно. Зачастую этого вполне достаточно. Основное тут то, что у типов есть ограничения и это следует учитывать.



Еще одна важная особенность, в отличии от целых чисел, рациональные с фиксированной точностью имеют два вида ограничений. Это следует из представления в котором задаются эти числа: мантиссы и порядка. Соответственно ограничения накладываются и на мантиссу, и на порядок. То есть(на этот раз обойдемся без точных цифр их всегда можно найти в интернете) либо мы задаем большие числа, но не очень точно, либо очень точно, но маленькие, либо какие-то промежуточные варианты.

Структуры данных




Вообще в программировании возникает множество различных структур данных, но наиболее распространенные из них(и предоставляемые большинством языков) это массив, запись и объект. Об объектах я расскажу в одном из следующих постов, а пока рассмотрим детальнее две другие структуры.

Массив




Массив - упорядоченная структура данных состоящая из элементов одного типа. Хорошим примером массива является строка, которая по сути своей массив символов. Кстати, в программировании строкой зачастую называют любой фрагмент текста. Упорядоченность в случаи строки, означает, что каждый символ находится на некотором месте. Это место называется индексом элемента массива. Массив имеет длину, то есть общее количество элементов входящих в массив.



В языке C++ массивы обозначаются следующим образом:

int[] array ={1,2,3};


или

int[3] array;


В первом случаи мы определили массив из трех элементов 1, 2 и 3, во втором просто массив из трех элементов, без указания того какие именно это элементы. Во втором случаи значения элементов массива не определены, соответственно прежде чем считывать их значение, его необходимо сначала присвоить. Например, так

array[0]=5;


Тут важно отметить, что индексация в C++, как и большинстве других языков начинается с нуля, то есть первый элемент массива будет иметь индекс 0, соответственно последний элемент будет иметь индекс length-1, где length - длинна массива. Как мы видим, в C++ длинна массива задается при его определении, однако многие другие языки позволяют изменять длину массива динамически.

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




Эта структура данных является производной от массива. По сути если мы будем рассматривать массив массивов, то есть такой массив, элементами которого являются не числа или символы, а массивы, то это и будет многомерный массив. Для закрепления этой концепции, рассмотрим пример: Скажем мы хотим реализовать игру в шахматы, на каждом ходу нам необходимо хранить состояние доски, для этого отлично подойдет двухмерный массив 8x8, где элементами этого массива будут фигуры находящиеся на соответствующих клетках. Будем обозначать пешку числом 1, коня - 2, слона - 3 и так далее(для белых фигур, для черных будем использовать те же числа, только со знаком минус). Соответственно в клетке в которой фигура отсутствует будет число 0. Давайте теперь запишем начальное положение доски на языке C++.

int[8][8] board = {{4, 2, 3, 5, 6, 3, 2, 4},
{1, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{-1, -1, -1, -1, -1, -1, -1, -1},
{-4, -2, -3, -5, -6, -3, -2, -4}};


Примерно так выглядит начальное положение шахматной доски. Для того, чтоб получить значение находящееся в пятой строке в седьмом столбце необходимо обратится к элементу board[4][6](еще раз напоминаю, что считаем мы с нуля, это немного непривычно, но что делать).



Таким же точно образом можно описать трех-, четырех- и даже восьмимерный массив, если это вдруг зачем-то понадобилось.



Понятие многомерного массива показывает очень важное свойство структур данных - композицию. То есть что элементами структуры могут быть не только "простые типы"(рассмотренные в разделе "Типы данных"), но и другие структуры.

Записи




Вообще термин "запись" относится скорее к языку Pascal, в C++ это понятие именуется "структура", но я решил использовать термин "запись" во избежание терминологических коллизий. Так вот, если мы говорим, что массив это набор однородных данных, то запись, в общем случаи, наоборот набор разнотипных данных. Запись имеет некоторый набор полей, каждое со своим уникальным именем и своего типа(хотя типы могут и повторятся). Рассмотрим несколько примеров:



1) Запись о человеке в базе данных. Она состоит, например из его ФИО, идентификационного кода и номера и серии паспорта. Итого, три поля(хотя может быть и 6 смотря как мы хотим хранить эти данные, например ФИО может быть как одним полем так и тремя).

struct Person {
char[50] name;
int inn;
char[8] passport;
};


Как я уже писал, строки в С++(как вобщем-то и везде) - ни что иное как массив символов. Есть библиотека, которая позволяют использовать тип string, для обозначения строк, это несколько упрощает работу с ними, но обзор данной библиотеки выходит за рамки этой статьи, потому будем пока пользоваться символьными массивами.



2) Координаты точки. В задачах связанных с графикой невозможно обойтись без задания положения точки в системе координат. Для простоты, рассмотрим задание координат точки в двухмерном пространстве(например, на экране монитора). Итак, точка в двухмерном пространстве задается координатами x и y. Создадим соответствующую запись:

struct Point {
int x;
int y;
};


У записи Point оба поля имеют один и тот же тип, однако использование такой записи значительно удобнее, чем массива из двух элементов, хотя по сути пользоваться им можно с тем же успехом.



Теперь когда у нас сформирована запись, мы можем объявить переменную которая будет иметь соответствующую структуру, в C++ это можно сделать так:

struct Person Alex;


Или же можно определить переменную вместе с определением типа:

struct Point {
int x;
int y;
} axis;


Далее с определенной переменной можно работать, записывая и считывая данные из ее полей:

axis.x = 10;
axis.y = axis.x + 5;


Пара слов об объектах, раз уж мы их упомянули. По-сути объект не что иное как запись, содержащая, кроме полей еще и функции(детально функции будут рассмотрены в следующем посте), так же именуемые, в контексте объекта, его методами. Хотя из данного определения совершенно не ясно зачем вообще нужны объекты и чем они полезны. О них я расскажу в последующих постах.

Устройство памяти




По моему глубокому убеждению, фундаментальное понимание устройства различных механизмов, позволяет применять эти механизмы максимально эффективно. Так, например, понимание работы различных алгоритмов и некоторых свойств входящих данных может помочь выбрать наиболее подходящий(быстрый, менее затратный) из алгоритмов приводящих к одному результату. По этой причине, я решил рассказать об аппаратном устройстве памяти.



Как мы уже могли убедится, программист может создавать весьма сложные структуры данных. Путем комбинации массивов и записей, можно создавать сколь угодно разветвленные структуры. Однако стоит учитывать, что память по природе своей линейна. Как же тогда в ней хранятся эти структуры? Начнем с самого начала. Когда мы объявляем переменную типа int выделяется, как уже упоминалось, 4 байта памяти. То есть, в памяти происходит поиск промежутка, размером по крайней мере 4 байта, и когда промежуток найден, это место помещается, как занимаемое объявленной переменной. Для одномерного массива, например, процесс примерно такой же: для int[10] выделяется 4x10=40 байт и хранится он последовательно, сначала элемент с индексом 0, потом с индексом 1 и т.д. Что же происходит с многомерный массивом? Вобщем-то все довольно логично, массив int[2][5], как мы уже упоминали - массив массивов, под него опять же выделяется 4x5x2=40 байт, и хранится он, соответственно, как два пятиэлементных массива подряд. Для массивов с большим количеством измерений схема полностью аналогична. Эта особенность хранения массивов, хотя на первый взгляд лишь забавный факт, является довольно полезным с точки зрения оптимизации обхода многомерный массивов. Объявлении переменной типа записи, выделяется место равное сумме всех объемов занимаемых каждым полем. При этом поля записи хранятся в том порядке, в котором они описаны при задании записи.

В заключение




В данной статье я кратко рассказал про типы данных, их структуры и то зачем это все надо. Это, безусловно, не исчерпывающая информация, но здесь максимально сжато изложены основные идеи. Надеюсь эта информация была полезна. Если возникли какие-то вопросы или что-то было непонятно - добро пожаловать в комментарии. Спасибо за внимание.
2

Комментарии

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