Полустатіческіе структури даних

4.1. Характерні особливості полустатіческіх структур

Полустатіческіе структури даних характеризуються такими ознаками:

мають змінну довжину і прості процедури її зміни;

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

Якщо полустатіческую структуру розглядати на логічному рівні, то про неї можна сказати, що це послідовність даних, пов'язана відносинами лінійного списку. Доступ до елементу може здійснюватися по його порядковому номеру.

4.2. рядки

4.2.1. Логічна структура рядка

Рядок - це лінійно впорядкована послідовність символів, що належать кінцевому безлічі символів, званого алфавітом. Рядки мають наступні важливими властивостями:

їх довжина, як правило, змінна, хоча алфавіт фіксований;

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

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

Говорячи про рядках, зазвичай мають на увазі текстові рядки - рядки, що складаються з символів, що входять в алфавіт будь-якого обраного мови, чисел, знаків пунктуації та інших службових символів. Дійсно, текстовий рядок є найбільш універсальною формою подання будь-якої інформації: на сьогоднішній день вся сума інформації, накопиченої людством - від Старого Завіту до даного навчального посібника, - представлена ​​саме в вигляді текстових рядків. У подальших прикладах цього розділу будемо працювати саме з текстовими рядками. Однак, слід мати на увазі, що символи, що входять в рядок, можуть належати будь-якій алфавітом. Так, в мові PL / 1 поряд з типом даних "символьний рядок" - CHAR (n) - існує тип даних "битовая рядок" - BIT (n). Бітові рядки складаються з 1-бітових символів, що належать алфавітом:. Всі рядкові операції з рівним успіхом можна застосувати як до символьних, так і до бітових рядків.

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

Хоча рядки розглядаються в розділі, присвяченому полустатіческім структурам даних, в тих чи інших конкретних завданнях мінливість рядків може варіюватися від повної її відсутності до практично необмежених можливостей зміни. Орієнтація на ту чи іншу ступінь мінливості рядків визначає і фізичне уявлення їх в пам'яті і особливості виконання операцій над ними. У більшості мов програмування (C, PASCASL, PL / 1 і ін.) Рядки представляються саме як полустатіческіе структури.

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

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

У мовах універсального призначення зазвичай строковий тип є базовим в мові: STRING у PASCAL, CHAR (n) в PL / 1. (В PASCAL довжина рядка, оголошеної таким чином, може змінюватися від 0 до n. В PL / 1, щоб довжина рядка могла змінюватися, вона повинна бути оголошена з описателем VARING.) Основні операції над рядками реалізовані як прості операції або вбудовані функції. Можливі також бібліотеки, що забезпечують розширений набір строкових операцій.

Мова REXX орієнтований насамперед на обробку текстової інформації. Тому в REXX немає коштів опису типів даних: всі дані представляються у вигляді символьних рядків. Операції над даними, не властиві символьним рядках, або виконуються спеціальними функціями, або призводять до прозорого для програміста перетворенню типів. Так, наприклад, інтерпретатор REXX, зустрівши оператор, що містить арифметичний вираз, сам перекладає його операнди в числовий тип, обчислює вираз і перетворює результат в символьний рядок. Цілий ряд строкових операцій є простими операціями мови, а вбудованих функцій обробки рядків в REXX кілька десятків.