Лекция 2. Организация данных ####################################################################################### Данные и память =========================================================== Роль данных ----------------------------------------------------------- * **Программа** - текст, включающий процесс конструирования и обработки **данных**. * **Данные** на вход могут поступать с внешних источников (устройств), а также присутствовать в программе в виде **констант**. * Все данные относятся к определенному **типу**. * Существуют **встроенные** (стандартные) и **пользовательские** типы данных. * В языке имеются механизмы конструирования **сложных** типов данных из более **простых**. * Данные для своего размещения требуют **памяти**. Модель памяти и ее распределение ----------------------------------------------------------- Виртуальная машина `````````````````````````````````````````````````````````` **Виртуальная Машина (ВМ)** представляет собой программную модель некоего идеализированного компьютера, архитектура которого адекватна соответствующему языку программирования. Для понимания работы программы необходимо разобраться в устройстве такого идеализированного компьютера. .. image:: _static/02/beamer-g4.png Необходимо разработать модель памяти ВМ. Модель памяти `````````````````````````````````````````````````````````` .. image:: _static/02/mem1.png .. image:: _static/02/mem2.png .. image:: _static/02/mem3.png * память не может быть пуста; * деление памяти на области (ячейки) условно; * в зависимости от способа представления могут быть разные значения. Типы распределения памяти `````````````````````````````````````````````````````````` .. admonition:: Статическое Происходит во время построения программы .. admonition:: Динамическое Происходит во время выполнения программы по запросу программы. Освобождение по явной инициативе программы. .. admonition:: Автоматическое Происходит во время выполнения. Память автоматически выделяется и освобождается без явного участия программы. Классификация памяти `````````````````````````````````````````````````````````` * **Статическая** (глобальные объекты, статические переменные): - выделяется на этапе построения (build-time); - размер фиксирован и ограничен; - размер не может быть изменен во время выполнения; - обнуляется. * **Динамическая** ("куча", heap): - выделяется во время выполнения (run-time); - размер может меняться. * **Стековая** (локальные объекты, параметры функций, возвращаемые значения ): - содержит произвольные значения; - может быть "коррумпирована" (повреждена); - время жизни ограничено. Типы данных =========================================================== Классификация типов данных `````````````````````````````````````````````````````````` * Стандартные (встроенные). * Нестандартные (пользовательские). * Простые (переменные, константы). * Составные (массивы, структуры, объединения). * Целочисленные. - Со знаком. - Без знака. * Вещественные. - Одинарной точности. - Удвоенной точности. * Адресные. Стандартные типы языка С `````````````````````````````````````````````````````````` .. list-table:: * - *Тип* - *Диапазон значений* - *Бт* * - char - -128 .. 127 - 1 * - short int (short) - -32 768 .. 32 767 - 2 * - long int (long) - -2 147 483 648 .. 2 147 483 647 - 4 * - **long long int (long long)** ``[C99]`` - -9 223 372 036 854 775 808 .. 9 223 372 036 854 775 807 - 8 * - unsigned char - 0..255 - 1 * - unsigned short - 0..65535 - 2 * - unsigned long - 0..4 294 967 295 - 4 * - **unsigned long long** ``[C99]`` - 0..18 446 744 073 709 551 615 - 8 * - float - 3.4e-38..3.4e+38 - 4 * - double - 1.7e-308..1.7e+308 - 8 * - long double - 3.4e-4932..3.4e+4932 - ? * - int - ? - ? * - **_Bool** ``[C99]`` - true,false ``[При использовании stdbool.h]`` - 1 * - **_Complex,_Imaginary** ``[C99]`` - как float или double - 4,8 Переменные и константы ----------------------------------------------------------- Объявление переменных `````````````````````````````````````````````````````````` * **sc-specifier** - спецификатор класса памяти *(static, extern, auto, register)*. * **const** - фиксатор. * **type-specifier** - спецификатор типа. * **declarator** - имя переменной (идентификатор). * **value** - начальное значение переменной (инициализация). .. admonition:: Примеры .. code-block:: c char ch; int value; unsigned long x,y,z; Объявление переменных и их размещение `````````````````````````````````````````````````````````` .. code-block:: c /* объявление файловых переменных размещение - в статической области */ char ch; float fVal; int main() { /* объявление локальных (автоматических) переменных размещение в стеке */ int iVal; double dVal; ... return 0; } Константы и переменные `````````````````````````````````````````````````````````` * Константы заносятся в программу в **build-time**. * Переменные, объявленные с **инициализацией**, получают значение в **run-time**. * Ключевое слово **const** выполняет фиксацию: запрет менять значение объекта. .. admonition:: Пример объявления с инициализацией .. code-block:: c int val=0; float val1=0.23, val2=0.9; .. admonition:: Пример объявления с фиксацией .. code-block:: c const char a='\n'; const int b=0,c=1; const double d=2.121; Атрибуты переменной `````````````````````````````````````````````````````````` Пусть объявлена переменная .. code-block:: c double val=4.567; .. admonition:: Получение адреса .. code-block:: c &val .. admonition:: Получение размера .. code-block:: c sizeof(val) .. admonition:: Доступ к значению .. code-block:: c val Массивы ----------------------------------------------------------- Объявление массивов `````````````````````````````````````````````````````````` * **declarator** - имя массива (идентификатор). * **number** - количество элементов. * **v1,v2,...** - значения при инициализации. .. admonition:: Объявление целочисленного массива из 7 элементов .. code-block:: c int arr[7]; .. image:: _static/02/arr1.png * :math:`A_1=A_0+1*sizeof(int)` :math:`A_0=&arr[0]=arr` * :math:`A_2=A_0+2*sizeof(int)` :math:`A_1=&arr[1]` * :math:`A_n=A_0+n*sizeof(int)` :math:`A_n=&arr[n]` .. image:: _static/02/arr1.png .. math:: A_0=& arr[0]=arr .. math:: A_1=& arr[1] .. math:: A_n=& arr[n] .. math:: A_1=A_0+1*sizeof(int) .. math:: A_2=A_0+2*sizeof(int) .. math:: A_n=A_0+n*sizeof(int) Инициализация массивов `````````````````````````````````````````````````````````` .. code-block:: c int arr[10]={0,1,2,3,4,5,6,7,8,9}; .. code-block:: c int arr[10]={0,1,2}; Многомерные массивы `````````````````````````````````````````````````````````` .. admonition:: Объявление двумерного массива 5x2 .. code-block:: c int arr[5][2]={{1,2},{3,4},{5,6},{7,8},{9,10}}; .. image:: _static/02/arr4.png Символьный тип ----------------------------------------------------------- Представление текста `````````````````````````````````````````````````````````` Основной способ представления текста - ``строка символов``. Каждый символ представлен в памяти целым числом. В настоящее время широко распространен ``ASCII``-код, в котором символ кодируется однобайтным значением. Набирает популярность другой способ кодирования - **Unicode**, в котором с каждым символом ассоциируется двухбайтное значение. ``По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, вкокам пряокде рсапожолена бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы не чиатем кдаужю бкуву по отдльенотси, а все солво цликеом.`` ASCII `````````````````````````````````````````````````````````` .. image:: _static/02/ascii1.png .. image:: _static/02/ascii2.png Символьный тип `````````````````````````````````````````````````````````` Тип **char** используется для хранения кода символа в диапазоне от 0 до 255 Существует два способа задать символ: #. числовой константой **char ch=33;** #. символьной константой **char ch='!';** Оба способа РАВНОЗНАЧНЫ, но второй более НАГЛЯДЕН! Специальные символы `````````````````````````````````````````````````````````` .. list-table:: * - *Символ* - *Название* * - :math:`\a` - сигнал * - :math:`\b` - возврат на одну позицию * - :math:`\n` - перевод строки * - :math:`\r` - возврат каретки * - :math:`\t` - горизонтальная табуляция * - :math:`\\backslash` - обратный слэш * - :math:`\0` - конец строки Строки `````````````````````````````````````````````````````````` **Строка** - это массив символов, завершающийся :math:`\0` (код - 0) .. code-block:: c char greet[6]={'H','E','L','L','O','\0'}; char greet[6]="HELLO"; char greet[9]="HELLO"; Ввод/вывод =========================================================== Устройства ----------------------------------------------------------- Устройства ввода/вывода `````````````````````````````````````````````````````````` #. В языке С нет встроенных средств ввода/ вывода. #. Ввод/вывод осуществляется через функции стандартных библиотек. #. Стандартное устройство вывода - **терминал**. #. Стандартное устройство ввода - **клавиатура**. Терминал `````````````````````````````````````````````````````````` .. image:: _static/02/term.png .. image:: _static/02/term1.png Функции ----------------------------------------------------------- Потоки ввода/вывода `````````````````````````````````````````````````````````` В языке Си с каждым устройством ассоциируется поток ввода/вывода: * **stdin** - стандартный поток ввода (клавиатура) * **stdout** - стандартный поток вывода (терминал) * **stdprn** - стандартный поток печати (принтер) * **stderr** - стандартный поток ошибок (терминал) Доступ к потокам унифицирован. Функции потокового ввода/вывода `````````````````````````````````````````````````````````` *Функции вывода* * **fprintf(поток,шаблон,данные)** - форматированный вывод * **fputs(строка,поток)** - строковый вывод * **fputс(символ,поток)** - символьный вывод *Функции ввода* * **fscanf(поток,шаблон,адреса)** - форматированный ввод * **fgets(адрес,размер,поток)** - строковый ввод * **fgetс(поток)** - символьный ввод Функции стандартного ввода/вывода `````````````````````````````````````````````````````````` *Функции вывода* * **printf(шаблон,данные)** - форматированный вывод * **puts(строка)** - строковый вывод * **putсhar(символ)** - символьный вывод *Функции ввода* * **scanf(шаблон,адреса)** - форматированный ввод * **gets(адрес)** - строковый ввод * **getсhar()** - символьный ввод Локализация ----------------------------------------------------------- Как научить программу писать по-русски? Существует несколько вариантов. *Вариант 1.* .. code-block:: cpp ... int main() { setlocale(LC_ALL,"rus"); ... return 0; } Недостатком этого варианта может явится корректное отображение строк в консоли, набранных в редакторе, но искажение введённых с клавиатуры русских символов. *Вариант 2.(Только в Windows)* .. code-block:: c int main() { char s[]="Привет всем!"; CharToOem(s,s); printf("%s\n", s); return 0; } Этот вариант подходит только для *Windows* и содержит вызов специальной функции **CharToOem**, преобразующей символы из кодировки редактора (1251) в кодировку консоли (866). Недостатком этого подхода является необходимость расположения строки в символьном массиве. А ещё необходимо в настройках (раздел *General*) проекта поменять **UNICODE** на **MULTIBYTE**. *Вариант 3.* .. code-block:: cpp char buf[256]; char* Rus(const char* s) { CharToOem(s,buf); return buf; } int main() { printf(Rus("Привет всем!"));; return 0; } Этот вариант удобен тем, что таким способом можно легко выводить на консоль строковые константы. *Вариант 4.* .. code-block:: cpp ... int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); ... return 0; } Этот вариант наиболее простой, но требует смены шрифта терминала (вместо **Точечный** - **Lucida**). Дополнительная информация =========================================================== Представление данных ----------------------------------------------------------- .. admonition:: Числа * Вычислительная машина оперирует **двоичными** числами. * В памяти специальным образом кодируются **целые** и **вещественные** числа (формат представления). * Самое важное число - **2**. * Самая важная операция - возведение в степень. .. admonition:: Computer .. image:: _static/02/beamer-g4.png Степени двойки `````````````````````````````````````````````````````````` .. list-table:: * - :math:`2^0` - :math:`1` * - :math:`2^1` - :math:`2` * - :math:`2^2` - :math:`4` * - :math:`2^3` - :math:`8` * - :math:`2^4` - :math:`16` * - :math:`2^5` - :math:`32` * - :math:`2^6` - :math:`64` * - :math:`2^7` - :math:`128` * - :math:`2^8` - :math:`256` * - :math:`2^9` - :math:`512` * - :math:`2^{10}` - :math:`1024` * - :math:`2^{11}` - :math:`2048` * - :math:`2^{12}` - :math:`4096` * - :math:`2^{13}` - :math:`8192` * - :math:`2^{14}` - :math:`16384` * - :math:`2^{15}` - :math:`32768` * - :math:`2^{16}` - :math:`65536` .. list-table:: * - :math:`2^{17}` - :math:`131,072` * - :math:`2^{18}` - :math:`262,144` * - :math:`2^{19}` - :math:`524,288` * - :math:`2^{20}` - :math:`1,048,576` * - :math:`2^{21}` - :math:`2,097,152` * - :math:`2^{22}` - :math:`4,194,304` * - :math:`2^{23}` - :math:`8,388,608` * - :math:`2^{24}` - :math:`16,777,216` * - :math:`2^{25}` - :math:`33,554,432` * - :math:`2^{26}` - :math:`67,108,864` * - :math:`2^{27}` - :math:`134,217,728` * - :math:`2^{28}` - :math:`268,435,456` * - :math:`2^{29}` - :math:`536,870,912` * - :math:`2^{30}` - :math:`1,073,741,824` * - :math:`2^{31}` - :math:`2,147,483,648` * - :math:`2^{32}` - :math:`4,294,967,296` Быстрая оценка больших чисел `````````````````````````````````````````````````````````` :math:`2^{24} = 2^{10} \times 2^{10} \times 2^4 \approx 1000 \times 1000 \times 16 = 16` млн. (ошибка 4.6%) :math:`2^{32} = 2^{10} \times 2^{10} \times 2^{10} \times 2^2 \approx 1000 \times 1000 \times 1000 \times 4 = 4` млрд. (ошибка 6.9%) Системы счисления ----------------------------------------------------------- Основные используемые системы счисления: Двоичная: .. math:: A_2={0,1} Десятичная .. math:: A_{10}={0,1,2,3,4,5,6,7,8,9} Шестнадцатеричная .. math:: A_{16}={0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f} Принцип формирования числа: :math:`n = a_{m-1}(o)^{m-1}+...+a_1(o)+a_0` *o* - основание системы счисления (2,10,16). *a* - значение разряда. *m* - номер разряда. Перевод из двоичной в десятичную `````````````````````````````````````````````````````````` Имеем двоичное число :math:`n_{2}=00101001` . :math:`o=2, m=8` Ему соответствует десятичное :math:`n_{10}=0*(2)^7+0*(2)^6+1*(2)^5+0*(2)^4+1*(2)^3+0*(2)^2+0*(2)^1+1*(2)^0=32+8+1=41` Перевод из десятичной в двоичную `````````````````````````````````````````````````````````` Пусть дано :math:`n_{10}=57` #. Разделить 57 на 2: 28 - 1 (с остатком) #. Разделить 28 на 2: 14 - 0 (без остатка) #. Разделить 14 на 2: 7 - 0 (без остатка) #. Разделить 7 на 2: 3 - 1 (с остатком) #. Разделить 3 на 2: 1 - 1 (с остатком) #. Разделить 1 на 2: 0 - 1 (с остатком) Пишем значения разрядов в обратном порядке. В результате получаем :math:`n_2=111001` . Терминология ----------------------------------------------------------- * **build-time** - время построения программы. Период работы компилятора и компоновщика; * **run-time** - время выполнения программы. Период от момента старта программы до ее завершения; * **объект в программе** - элемент программы, потребляющий ресурсы (память, процессорное время); * **объявление** - описание области действия объекта; * **инициализация** - присвоение начального значения объекту; * **фиксация** - запрет менять значение объекта; * **область видимости** - участок кода, в пределах которого можно обратиться к объекту; * **время жизни** - время жизни объекта в программе. Оболочка времени выполнения `````````````````````````````````````````````````````````` * После запуска на выполнение программа обладает оболочкой, которая обеспечивает ее **run-time** ресурсами. * **Run-time** ресурсы времени выполнения программы: процессорное время, память, дескрипторы файлов и системных устройств. * Во время выполнения программа использует как **build-time** ресурсы, так и **run-time** ресурсы. Массивы ----------------------------------------------------------- Инициализация массивов (С99) `````````````````````````````````````````````````````````` Стандарт **C99** предоставляет возможность использовать **обозначенные инициализаторы**. .. admonition:: Инициализация определённого элемента .. code-block:: c int arr[6]={[5]=333}; // остальные равны 0 Вопросы для самоконтроля ============================================= * Опишите роль данных при работе программы. * Как данные могут поступать в программу? * Как связаны между собой данные и память? * Как связаны между собой данные и типы? * Что такое виртуальная машина для языка Си? * Что представляет собой простейшая модель памяти? * Как происходит распределение памяти? Перечислите виды распределений. * Перечислите основные области памяти. Что для них характерно? * Как можно классифицировать типы данных? * Как объявить переменную? * Как объявить несколько однотипных переменных? * Как объявить локальную переменную? * Как объявить файловую переменную? * Что указывается при инициализации? При фиксации? * Какие атрибуты есть у переменной? * Как объявить одномерный массив? * Как инициализировать одномерный массив? * Как объявить многомерный массив? Как его инициализировать? * Как можно представить текст в программе? * Какими способами можно задать значение символьной переменной? * Какие символы мы относим к специальным? Как они задаются? * Что такое строка? * Какими способами можно задать строку в программе? * Какие устройства ввода/вывода считаются стандартными? * Что представляет собой терминал? * Перечислите стандартные потоки ввода/вывода. * Перечислите функции потокового ввода/вывода. * Перечислите функции стандартного ввода/вывода. * Как локализовать программу? * Как быстро оценить значение большого числа? * Опишите принцип формирования числа в позиционной системе счисления. * Перечислите наиболее распространенные системы счисления. * Как перевести число из двоичной системы в десятичную? * Как перевести число из десятичной системы в двоичную? * Что такое build-time? Run-time? * Что такое объявление? Инициализация? * Что такое фиксация? * В чем состоит назначение оболочки времени выполнения?