Бублик Володимир Васильович Процедурне програмування C/C++ Лекція 7. Базові поняття програмування. Структури даних Лекції для студентів 2 курсу Консультації: середа, з 15 год., кімн. 204/1, к афедра мультимедійних систем Munich

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 2 (44) Роль структур даних Алгоритми + структури даних = програми Ніклаус Вірт Складність реалізації і якість програми істотно залежить від вибору правильної структури даних

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 3 (44) Структур даних і архітектура програм Структури даних, а не алгоритми визначають архітектуру програмної системи і, відповідно, навігацію користувача в системі. На рівні об'єктно-орієнтованого програмування це перш за все інтерфейси та ієрархії: меню, закладки, смуги прокрутки, налаштовування. Некоректні інтерфейси заблокують довершені алгоритми Приклад на рівні процедурного програмування пошук у словнику: невпрорядкований масив, впорядкований, дерево пошуку

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 4 (44) Фундаментальні структури даних 1.Масиви (указники) 2.Структури фундамент для визначення класів (місток до об'єктно-орієнтованого програмування) 3.Бітові поля (back to hardware) 4.Об'єднання (архаїзм економії пам'яті)

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 5 (44) Визначення структури в С++ Визначення структури це окремий оператор struct Point { double _x; double _y; }; _x, _y називаються членами структури (в Паскалі поля)

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 6 (44) Визначення структури в С // Старомодна структура typedef struct { double _x; double _y; } Point;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 7 (44) Визначення структурованих об'єктів C vs. C++ C: змінних struct Point u; struct Point { double _x; double _y; } u; C++: сталих і змінних Point u = {1,1}; Point v; const Point zero = {0, 0};

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 8 (44) Загадка Чому компілятор не пропустить визначення константи без ініціалізації const double pi;//ERROR та вимагатиме її значення const double pi= ; але дозволить неповне визначення сталої структури const Point zero; хоча воно мало б бути некоректним? Загадка...

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 9 (44) Визначення указників структурованих об'єктів C vs. C++ C: struct Point { double _x; double _y; } u, *pu; C++: Point * pu = &u; Point *p = new Point; Point *parr = new Point[n];

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 10 (44) Графічні зображення: діаграма об'єкту const Point zero = {0, 0}; Point u = {1,1};

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 11 (44) Графічні зображення: діаграма структури struct Point { double _x; double _y; };

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 12 (44) Розміщення в пам'яті Кожний член структури розміщується відповідно свого типу: short з границі півслова; int, float з границі слова; double з границі подвійного слова struct Collection { char _chr; double _d; short int _si; float _f; }; Адреси пам'яті

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 13 (44) Увага! Навіть у випадку однотипних членів структури не робимо жодних припущень про розміщення полів структури в пам'яті, наприклад, що &(Point::_x)+1 == &(Point::_y)

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 14 (44) Оптимізація Компілятор має право оптимізувати розміщення в памяті struct Collection { double _d; float _f; short int _si; char _chr; }; Адреси пам'яті

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 15 (44) Cтруктура vs. масив Point u = {1,1};

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 16 (44) Cтруктура vs. масив Point u = {1,1}; double *u = new double[2];

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 17 (44) Point u = {1,1}; double u[2] = {1,1}; Point *p = &u; Указник на структуру Point*

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 18 (44) Елемент масиву vs. член структури Для доступу до елементів масиву застосовується адресна арифметика; індекси елементів масиву можна обчислювати, за індексами можна організовувати цикли; Члени структури задаються оператором доступу до члена структури (крапка-оператор) Point u = {1, 1}; double u[2] = {1,1}; u._x; u[0] == *u; u._y; u[1] == *(u+1)

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 19 (44) Указник на член структури Point u = {1,1}; За допомогою указника структури (оператор доступу за указником -> ) Point *p = &u; p -> _x == (*p)._x За допомогою указників окремих членів double *px = &u._x; double *py = &u._y;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 20 (44) Проблема (для допитливих) Задача 1. Дано декілька масивів A[], B[],…,C[]. Як в сигнатурі функції, на вхід якої поступить довільний масив, позначити потрібний елемент? Відповідь: Вказати його номер: double f(double X[], size_t n, size_t i) Задача 2. а) Дана структура struct Point { double _x; double _y;}; б) дано набір екземплярів структури Point u,v,…,w. Як в сигнатурі функції, на вхід якої поступить довільний екземпляр структури, позначити її потрібний член?

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 21 (44) Відповідь (для допитливих) double select(const Point& u, const double Point::* coord) { return u.*coord; } double modify(Point& u, double Point::* coord, double a) { return (u.*coord=a); }

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 22 (44) Відповідь (для допитливих) Point u={1,2}, v={3,4}; // Вивести координати точок cout<<select(u, &Point::_x)<<':' <<select(u, &Point::_y)<<';' <<select(v, &Point::_x)<<':' <<select(v, &Point::_y)<<endl; // Модифікувати і вивести координати точок cout<<modify(u, &Point::_x, 10)<<':' <<modify(v, &Point::_y, 20)<<endl;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 23 (44) Присвоєння структур Присвоєння структур визначено; воно виконується поелементно: члени однієї структури переписуються до іншої Point u = {1, 1}; Point v = {2, 3}; u=v; cout<<u._x <<u._y<<endl;// 2 3 v._x = 10; v._y = 20; cout<<u._x <<u._y <<endl; // 2 3 Наступна зміна значення v на u не впливає

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 24 (44) Присвоєння структур vs. присвоєння масивів Присвоєння масивів не визначено. Чому? double x[2] = {1, 2}; double y[2] = {10, 20}; x = y;// ERROR! Приводить до помилки компіляції

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 25 (44) Присвоєння структур vs. присвоєння масивів Але присвоєння указників визначене double *x = new double[2]; double *y = new double[2]; y[0] = 10; y[1] = 20; x = y; out<<x[0]<<' '<<x[1]<<endl; // 10 20

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 26 (44) Присвоєння структур vs. присвоєння масивів Присвоєння указників визначене double *x = new double[2]; double *y = new double[2]; y[0] = 10; y[1] = 20; x = y; out<<x[0]<<' '<<x[1]<<endl; // Але y[1]=30; out<<x[0]<<' '<<x[1]<<endl; // Чому?

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 27 (44) Поверхневе присвоєння масивів double *x = new double[2]; double *y = new double[2]; y[0] = 10; y[1] = 20;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 28 (44) Поверхневе присвоєння масивів double *x = new double[2]; double *y = new double[2]; y[0] = 10; y[1] = 20; x = y; втрата пам'яті

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 29 (44) Поверхневе присвоєння масивів y[1]=30; сout<<x[0]<<' '<<x[1]<<endl; // 10 30

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 30 (44) Члени структур - указники struct BuiltInArray { int *_k; }; BuiltInArray a, b; a._k = new int[2]; a._k[0] = 1; a._k[1] = 2; b._k = new int[2]; b._k[0] = 10; b._k[1] = 20

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 31 (44) Члени структур - указники a = b; сout<<a._k[1]<<endl;//10

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 32 (44) Члени структур - указники a = b; out<<a._k[1]<<endl;//10 b._k[1] = 100; out<<a._k[1]; знову втрата пам'яті

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 33 (44) Члени структур - указники Елементи масиву b._k[i] не вдасться просто переписати на місце масиву a._k[2] через відмінність в розмірності BuiltInArray a, b; a._k = new int[2]; a._k[0] = 1; a._k[1] = 2; b._k = new int[100]; b._k[0] = 10; b._k[1] = 20 …………….

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 34 (44) Перший висновок Якщо структури служать фундаментом для переходу до класів шляхом сумісної інкапсуляції даних і дій і таким чином направлені догори в сенсі підвищення рівня абстракції, то бітові поля і об'єднання спрямовані донизу, до апаратного рівня представлення даних

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 35 (44) Приклад Учні одного класу занесені до класного журналу в алфавітному порядку. Щоденна присутність на уроці фіксується бульовим значенням: істина, якщо учень присутній, хиба, якщо відсутній struct Presence { bool Avdeev; ………………………….. bool Yanenko; }; Скільки місця займе структура?

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 36 (44) Бітові поля в структурах Учні одного класу занесені до класного журналу в алфавітному порядку. Щоденна присутність на уроці фіксується бульовим значенням: істина, якщо учень присутній, хиба, якщо відсутній struct Presence { bool Avdeev:1; ………………………….. bool Yanenko:1; }; Скільки місця займе ця структура тепер?

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 37 (44) Бітові поля struct StatusByte { unsigned clear_to_send: 1; unsigned data_ready: 1; unsigned record_end: 1; unsigned received_line: 1; unsigned trans_allowed: 1; unsigned line_ready: 1; unsigned ring_detected: 1; unsigned signal_accepted: 1; };

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 38 (44) Типи бітових полів Під кожне бітове поле виділяється задана кількість бітів, а саме поле може бути цілим переліком Розміщення в пам'яті і розміри залежать від реалізації і може змінюватися при зміні системи програмування Доступ до поля звичайний за допомогою крапка- операції

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 39 (44) Приклад enum Week { monday=1, tuesday, wednesday, thursday, friday, saturday, sunday }; struct DayStatus { unsigned _date:4; unsigned _month:4; Week _day:4; unsigned _holiday:1; }; Завдання. Перевірте розміщення структури DayStatus у пам'яті

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 40 (44) А тепер? enum Week { monday=1, tuesday, wednesday, thursday, friday, saturday, sunday }; struct DayStatusLong { unsigned _date; unsigned _month; Week _day; unsigned _holiday; }; Завдання. Перевірте розміщення структури DayStatusLong у пам'яті

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 41 (44) Невживані біти Можуть виявитися фікцією: struct AnotherStatusByte { unsigned : 4; unsigned _data_ready: 1; unsigned _record_end: 1; unsigned _line_ready: 1; unsigned _signal_accepted: 1; } status = {1, 0, 0, 1}; cout<<status._data_ready;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 42 (44) Невживані біти Порівняйте розмір: struct AnotherStatusByte { unsigned _data_ready: 1; unsigned _record_end: 1; unsigned _line_ready: 1; unsigned _signal_accepted: 1; } status = {1, 0, 0, 1}; cout<<status._data_ready;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 43 (44) Об'єднання Об'єднання це спосіб розміщення в одній області пам'яті різних типів даних або спосіб доступу до однієї і тієї ж області пам'яті через різні інтерфейси

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 44 (44) Приклад. Кодування дійсних чисел union Word { unsigned int _k; float _x; }; Word w; w._x = 1; out<<dec<<w._x<<' '<<hex<<w._k<<endl; //1 3f800000

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 45 (44) Приклад. Байтова структура слова union Word { unsigned int _k;//a1b1c1d1 struct Bytes4 { unsigned _byte1: 8;//d1 unsigned _byte2: 8;//c1 unsigned _byte3: 8;//b1 unsigned _byte4: 8;//a1 } _word; };

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 46 (44) Визначення типів Деякі стандартні типи typedef unsigned short wchar_t; typedef long time_t; typedef unsigned int size_t; Старомодне визначення структури typedef struct { char *a0;// pointer to the first argument int offset;// byte offset of next parameter } va_list_t;

© 2006 Бублик В.В. Процедурне програмування. 6. Структури даних 47 (44) Висновки 1.Масиви і структури дають принципово різні підходи до визначення агрегатів даних: масиви це набір однотипних елементів з доступом за індексом, доступ до членів структури за селекторами. 2.Бітові поля у структурі дозволяють компактно розміщувати малоформатні дані (двійкові біти, бульові значення). 3.Об'єднання служать для суміщення різнотипних даних 4.Як бітові поля, так і об'єднання служать засобами низького рівня і вони повинні застосовуватися дуже обережно