Основні структури даних

Кодування звукової інформації

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

Метод FM {Frequency Modulation) заснований на тому, що теоретично будь-який складний звук можна розкласти на послідовність простих гармонійних сигналів кратних частот, кожен з яких є правильною синусоїдою, а отже, може бути описаний числовими параметрами, тобто кодом. У природі звукові сигнали мають безперервний спектр, тобто є аналоговими. Їх ложение в гармонійні ряди і уявлення у вигляді дискретних цифрових сигналів виконують спеціальні пристрої — аналогово-цифрові перетворювачі (АЦП). Зворотне перетворення для відтворення звуку, закодованого числовим кодом, виконують цифро-аналогові перетворювачі (ЦАП). При їх перетвореннях неминучі втрати інформації, пов'язані з методом кодування, тому якість звукозапису зазвичай виходить не цілком задовільною і відповідає якості звучання простих електромузичних інструментів із забарвленням, характерним для електронної музики. В той же час метод кодування забезпечує вельми компактний код, і тому він знайшов застосування ще в ті роки, коли ресурси засобів обчислювальної техніки були недостатні.

Метод табличний - хвилевого (Wave-Table) синтезу краще відповідає сучасному розвитку техніки. Якщо говорити спрощено, то можна сказати, що в заздалегідь підготовлених таблицях зберігаються зразки звуків для безлічі різних музичних інструментів (хоча не тільки для них). У техніці такі зразки називають сэмплами. Числові коди виражають тип інструменту, номер його моделі, стільнику тону, тривалість і інтенсивність звуку, динаміку його зміни, деякі параметри середовища, в якому відбувається звучання, а також інші параметри, що характеризують особливості звуку. Оскільки як зразки використовуються «реальні» звуки, та якість звуку, отриманого в результаті синтезу, виходить дуже високим і наближається до якості звучання реальних музичних інструментів.

Робота з великими наборами даних автоматизується простіше, коли дані упорядо­чены, тобто утворюють задану структуру. Існує три основні типи структур даних: лінійна, ієрархічна і таблична. Їх можна розглянути на прикладі звичайної книги.

Якщо розібрати книгу на окремі листи і перемішати їх, книга втратить своє призначення. Вона як і раніше представлятиме набір даних, але підібрати адекват­ный метод для отримання з неї інформації вельми непросто. (Ще гірше справа йтиме, якщо з книги вирізувати кожну букву окремо — в цьому випадку навряд чи взагалі знайдеться адекватний метод для її прочитання.)

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

Для швидкого пошуку даних існує ієрархічна структура. Так, наприклад, книги розбивають на частини, розділи, розділи, параграфи і тому подібне Елементи структури нижчого рівня входять в елементи структури більш високого рівня: розділи складаються з глав, глави з параграфів і так далі

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

Лінійні структури (списки даних, вектори даних)

Лінійні структури — це добре знайомі нам списки. Список — це проста структура даних, що відрізняється тим, що кожен елемент даних однозначно визначається своїм номером в масиві. Проставляючи номери на окремих сторінках розсипаної книги, ми створюємо структуру списку. Звичайний журнал відвідуваності занять, наприклад, має структуру списку, оскільки всі студенти групи зарегист­рированы в нім під своїми унікальними номерами. Ми називаємо номери уникаль­ными тому, що в одній групі не можуть бути зареєстровані два студенти з одним і тим же номером.

При створенні будь-якої структури даних треба вирішити два питання: як розділяти елементи даних між собою і як розшукувати потрібні елементи. У журналі відвідуваності, наприклад, це вирішується так: кожен новий елемент списку зано­сится з нового рядка, тобто роздільником є кінець рядка. Тоді потрібний елемент можна розшукати по номеру рядка.

N п/п Прізвище, Ім'я, По батькові

1 Лелек Олександр Олексійович

2 Бобрів Борис Борисович

3 Воробйова Валентина Владиславівна

27 Сорокин Сергій Семенович

Роздільником може бути і який-небудь спеціальний символ. Нам добре відомі роздільники між словами — це пропуски. У російському і в багатьох європейських мовах загальноприйнятим роздільником пропозицій є крапка. У розглянутому наами класному журналі як роздільник можна використовувати будь-який символ, який не зустрічається в самих даних, наприклад символ «*». Тоді наш список ыглядел би так:

Лелек Олександр Олексійович * Бобрів Борис Борисович * Воробйова Валентина Владиславівна *... * Сорокин Сергій Семенович

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

ще простіше можна діяти, якщо всі елементи списку мають рівну довжину. В цьому випадку роздільники в списку взагалі не потрібні. Для розшуку елементу з номером п треба проглянути список із самого початку і відлічити а(п—1) символ, де а — довжина одного елементу. З наступного символу почнеться потрібний елемент, довжина теж рівна а, тому його кінець визначити неважко. Такі спрощені списки, що складаються з елементів рівної довжини, називають векторами даних. Працювати з ними особливо зручно.

Таким чином, лінійні структури даних (списки) — це впорядковані струк­туры, в яких адреса елементу однозначно визначається його номером.