Головна

Тема 1. Структури даних і алгоритми

  1.  A) Структури пакетів прикладних програм
  2.  A. Для остаточного висновку не вистачає даних.
  3.  Системи управління базами даних наступного покоління
  4.  I Створення таблиць бази даних
  5.  III. Опис зовнішніх схем баз даних
  6.  IV. АНАЛІЗ СКЛАДУ І СТРУКТУРИ пасивів балансу.
  7.  SKIP-технологія і криптопротоколів SSL, S-HTTP як основний засіб захисту з'єднання та даних, що передаються в мережі Internet

Розглянуті на лекції матриці є зручним інструментом для запису різних математичних перетворень і широко використовується в науково-технічній літературі. Метод Гаусса дозволяє вирішувати будь-які лінійні системи, він знаходить широке застосування і міститься в пакетах стандартних програм для ЕОМ.

доцент Смирнова А. І.

А. С. Дерев'янко

Опорний конспект лекцій

По курсу

"Організація і структури даних"

Тема 1. Структури даних і алгоритми

1.1. Основні поняття

Структури даних і алгоритми служать тими матеріалами, з яких будуються програми. Сам комп'ютер складається з структур даних і алгоритмів. Вбудовані структури даних представлені тими регістрами і словами пам'яті, де зберігаються виконавчі величини. Закладені в конструкцію апаратури алгоритми - це втілені в електронних логічних ланцюгах жорсткі правила, за якими занесені в пам'ять дані інтерпретуються як команди, що підлягають виконанню. Тому в основі роботи будь-якого комп'ютера лежить вміння оперувати тільки з одним видом даних - з окремими бітами, або двійковими цифрами. Працює ж з цими даними комп'ютер тільки відповідно до незмінним набором алгоритмів, які визначаються системою команд центрального процесора.

Для точного опису абстрактних структур даних і алгоритмів програм використовуються системи формальних позначень, звані мовами програмування, в яких сенс будь-якого пропозиції визначається точно і однозначно. Серед засобів, які подаються майже всіма мовами програмування, є можливість посилатися на елемент даних, користуючись присвоєним йому ім'ям, або, інакше, ідентифікатором. Одні іменовані величини є константами, які зберігають постійне значення в тій частині програми, де вони визначені, інші - змінними, яким за допомогою оператора в програмі може бути присвоєно будь-яке нове значення. Але до тих пір, поки програма не почала виконуватися, значення змінних не визначено. Компілятор, що транслює текст програми в двійковий код, пов'язує кожен ідентифікатор з певною адресою пам'яті. Але для того щоб компілятор зміг це виконати, потрібно повідомити про "типі" кожної іменованої величини. Людина, вирішальний якусь задачу "вручну", володіє інтуїтивною здатністю швидко розібратися в типах даних та тих операціях, які для кожного типу справедливі. Для комп'ютера ж всі типи даних зводяться в кінцевому рахунку до послідовності бітів, тому відмінність в типах слід робити явним.

Типи даних, прийняті в мовах програмування, включають натуральні і цілі числа, речові (дійсні) числа (у вигляді наближених десяткових дробів), літери, рядки і т. П У деяких мовах програмування тип кожної константи змінної визначається компілятором по формі запису присвоюється значення. У більшості ж мов потрібно, щоб програміст явно поставив тип кожної змінної. Хоча при виконанні програми значення змінної може багаторазово змінюватися, тип її змінюватися не повинен ніколи; це означає, що компілятор може перевірити операції, що виконуються над цієї змінної, і переконатися в тому, що всі вони узгоджуються з описом типу змінної. Залежно від призначення мови програмування захист типів, здійснювана на етапі компіляції, може бути більш-менш жорсткою.

Структура даних відноситься, по суті, до "просторовим" поняттями: її можна звести до схеми організації інформації в пам'яті комп'ютера. Алгоритм же є відповідним процедурним елементом в структурі програми - він служить рецептом розрахунку.

Структури даних, що застосовуються в алгоритмах, можуть бути надзвичайно складними. Вибір правильного уявлення даних часто служить ключем до успішного програмування і може більшою мірою позначатися на продуктивності програми, ніж деталі використовуваного алгоритму.

1.2. зберігання інформації

У ЦВМ можна виділити три основні види запам'ятовуючих пристроїв: сверхоперативная, оперативна і зовнішня пам'ять.

Надоперативна пам'ять будується на регістрах. Регістри використовуються для тимчасового зберігання і перетворення інформації. Деякі з найбільш важливих регістрів містяться в центральному процесорі комп'ютера. Центральний процесор містить регістри, в які поміщаються операнди арифметичних та інших операцій. Додавання, віднімання і т. Д. занесеної в регістри інформації виконується за допомогою дуже складних логічних схем. Крім запам'ятовування операндів і результатів арифметичних операцій, регістри використовуються також для тимчасового зберігання команд програми і керуючої інформації.

Оперативна пам'ять призначена для запам'ятовування більш постійної за своєю природою інформації. Під час виконання програми її команди і дані в основному розміщуються в осередках оперативної пам'яті. Найважливішим властивістю оперативної пам'яті є адресується. Це означає, що кожна комірка пам'яті має свою ідентифікатор-адреса, однозначно ідентифікує її в загальному масиві осередків пам'яті. Адреси осередків є операндами тих машинних команд, які звертаються до оперативної пам'яті. У переважній більшості сучасних обчислювальних систем одиницею адресації є байт - осередок, що складається з 8 двійкових розрядів. Певна осередок оперативної пам'яті або безліч осередків може бути пов'язано з конкретною змінної в програмі. Однак для виконання обчислень, в яких бере участь змінна, необхідно, щоб до початку обчислень значення змінної було перенесено з комірки пам'яті в регістр. Якщо результат обчислення повинен бути присвоєний змінної, то результуюча величина знову повинна бути перенесена з відповідного реєстру в пов'язану з цієї змінної осередок оперативної пам'яті.

Зовнішня пам'ять служить перш за все для довготривалого зберігання даних. Характерним для даних на зовнішній пам'яті є те, що вони можуть зберігатися там навіть після завершення створила їх програми, і можуть бути згодом багаторазово використані тією ж програмою при повторних її запусках або іншими програмами. Зовнішня пам'ять використовується також для зберігання самих програм, коли вони не виконуються. Оскільки вартість зовнішньої пам'яті значно менше оперативної, а обсяг значно більше, то ще одне призначення зовнішньої пам'яті - тимчасове зберігання тих кодів і даних виконуваної програми, які не використовуються на даному етапі її виконання. Активні коди виконуваної програми і оброблювані нею на даному етапі дані повинні обов'язково бути розміщені в оперативній пам'яті, так як прямий обмін між зовнішньою пам'яттю і регістрами неможливий.

Як сховище даних, зовнішня пам'ять має в основному ті ж властивості, що й оперативна, в тому числі і властивістю адресованих. Тому в принципі структури даних на зовнішній пам'яті можуть бути тими ж, що і в оперативній, і алгоритми їх обробки можуть бути однаковими. Але зовнішня пам'ять має зовсім іншу фізичну природу, для неї застосовуються (на фізичному рівні) інші методи доступу, і цей доступ має інші тимчасові характеристики. Це призводить до того, що структури і алгоритми, ефективні для оперативної пам'яті, не надаються такими для зовнішньої пам'яті. Тому структури і алгоритми для зовнішньої пам'яті звичайно виділяють в окремий розділ курсу.

1.3. Класифікація структур даних

Дані, що розглядаються у вигляді послідовності бітів, мають дуже просту організацію або, іншими словами, слабо структуровані.

 Під СТРУКТУРОЮ ДАНИХ в загальному випадку розуміють безліч елементів даних і безліч зв'язків між ними.

Вводиться додаткова класифікація структур даних, напрямки якої відповідають різним аспектам їх розгляду. Перш ніж приступати до вивчення конкретних структур даних, дамо їх загальну класифікацію за кількома ознаками.

Поняття ФІЗИЧНОЇ структури даних відображає спосіб фізичного представлення даних в пам'яті машини. Розгляд же структури даних без урахування її подання в машинної пам'яті називається абстрактною або ЛОГІЧНОЇ структурою. Існують процедури, які здійснюють відображення логічної структури в фізичну і, навпаки. Ці процедури забезпечують, крім того, доступ до фізичних структурам і виконання над ними різних операцій, причому кожна операція розглядається стосовно логічної або фізичної структурі даних.

ПРОСТИМИ (базовими, примітивними) структурами (типами) даних називаються такі, які не можуть бути розчленовані на складові частини, великі, ніж біти. Інтегровані (структурованими, композитними, складними) називаються такі структури даних, складовими частинами яких є інші структури - прості або в свою чергу інтегровані.

Залежно від відсутності або наявності явно заданих зв'язків між елементами даних прийнято розрізняти незв'язні і зв'язкових структури.

Вельми важлива ознака структури даних - її мінливість - зміна числа елементів і (або) зв'язків між елементами структури. У визначенні мінливості структури не відображений факт зміни значень елементів даних, оскільки в цьому випадку все структури даних мали б властивість мінливості. За ознакою мінливості розрізняють структури статичних, ПОЛУСТАТІЧЕСКІЕ і динамічні.

Важлива ознака структури даних - характер впорядкованості її елементів. За цією ознакою структури можна ділити на ЛІНІЙНІ І НЕЛІНІЙНІ структури.

У мовах програмування поняття "структури даних" тісно пов'язане з поняттям "типи даних". Будь-які дані, т. Е константи, змінні, значення функцій або виразу, характеризуються своїми типами. Інформація по кожному типу однозначно визначає:

1) структуру зберігання даних зазначеного типу, т. Е виділення пам'яті і уявлення даних в ній, з одного боку, і інтерпретацію двійкового представлення, з іншого;

2) безліч допустимих значень, які може мати той чи інший об'єкт описуваного типу;

3) безліч допустимих операцій, які застосовні до об'єкта описуваного типу.

1.4. Операції над структурами даних

Над усіма структурами даних можуть виконуватися чотири операції: створення, знищення, вибір (доступ), оновлення.

Операція створення полягає у виділенні пам'яті для структури даних. Пам'ять може виділятися в процесі виконання програми з першою появою імені змінної у вихідній програмі або на етапі компіляції.

Операція знищення структур даних протилежна за своєю дією операції створення.

Операція вибору використовується програмістами для доступу до даних всередині самої структури. Форма операції доступу залежить від типу структури даних, до якої здійснюється звернення.

Операція поновлення дозволяє змінити значення даних в структурі даних.

Вищевказані чотири операції є обов'язковими для всіх структур і типів даних. Крім цих загальних операцій для кожної структури даних можуть бути визначені операції специфічні, що працюють тільки з даними зазначеного типу (даної структури).

1.5 Структурно даних і технологія програмування

Знання структури даних дозволяє організувати їх зберігання і обробку максимально ефективним чином - з точки зору мінімізації витрат як пам'яті, так і процесорного часу. Іншим не менш важливим перевагою, яке забезпечується структурним підходом до даних, є можливість структурування складного програмного вироби.

При структуруванні великих програмних виробів можливе застосування підходу, заснованого на структуризації алгоритмів і відомого, як "спадний" проектування, "програмування зверху вниз", або підходу, заснованого на структуризації даних і відомого, як "висхідний" проектування, "програмування від низу до верху".

У першому випадку структурують насамперед дії, які повинна виконувати програма. Велику і складну задачу, що стоїть перед проектованим програмним виробом, представляють у вигляді декількох підзадач меншого обсягу.

Інший підхід до структуризації грунтується на даних. Інструментальні засоби програмування надають набір базових (простих, примітивних) типів даних і операції над ними. Інтегруючи базові типи, створюються більш складні типи даних і визначаються нові операції над складними типами. В ідеалі останній крок композиції дає типи даних, відповідні вхідним і вихідним даним завдання, а операції над цими типами реалізують в повному обсязі завдання проекту.

Ще одним надзвичайно продуктивним технологічним прийомом, пов'язаним зі структуризацією даних є інкапсуляція. Сенс її полягає в тому, що сконструйований новий тип даних оформляється таким чином, що його внутрішня структура стає недоступною для програміста - користувача цього типу. Інкапсуляція надзвичайно корисна і як засіб подолання складності, і як засіб захисту від помилок. Перша мета досягається за рахунок того, що складність внутрішньої структури нового типу даних і алгоритмів виконання операцій над ним виключається з поля зору програміста-користувача. Друга мета досягається тим, що можливості доступу користувача обмежуються лише свідомо коректними вхідними точками, отже, знижується і ймовірність помилок.

Технологія баз даних розвивалася паралельно з технологією мов програмування і не завжди узгоджено з нею. Почасти цим, а почасти й об'єктивними відмінностями в природі завдань, що вирішуються системами управління базами даних (СКБД) і системами програмування, викликані деякі термінологічні та понятійні відмінності в підході до даних в цих двох сферах. Ключовим поняттям в СУБД є поняття моделі даних, в основному тотожне поняттю логічної структури даних. Відзначимо, що фізична структура даних в СУБД не розглядається взагалі. Але самі СУБД є програмними пакетами, які виконують відображення фізичної структури в логічну (в модель даних). Для реалізації цих пакетів використовуються ті чи інші системи програмування, розробники СУБД, отже, мають справу зі структурами даних в термінах систем програмування. Для користувача ж внутрішня структура СУБД і фізична структура даних абсолютно прозора; він має справу тільки з моделлю даних і з іншими поняттями логічного рівня.




 Тема 3. Статичні структури даних |  Тема 4. Полустатіческіе структури даних |  Тема 5. Динамічні структури даних. зв'язкові списки |  Тема 6. Нелінійні структури даних |  Тема 7. Файлові структури даних |

© 2016-2022  um.co.ua - учбові матеріали та реферати