ВЕКТОР З КЕРОВАНОЮ ДОВЖИНОЮ.
Пам'ять під вектор з керованою довжиною відводиться при створенні стрічки і її розмір і розміщення залишаються незмінними весь час існування стрічки. У дескрипторі такого вектора-рядка може бути відсутнім початковий індекс, оскільки він може бути зафіксований раз назавжди встановленими угодами, але з'являється поле поточної довжини рядка. Розмір рядка, таким чином, може змінюватися від 0 до значення максимального індексу вектора. "Зайва" частина пам'яті, що відводиться, може бути заповнена будь-якими кодами - вона не береться до уваги при операції з рядком. Поле кінцевого індексу може бути використано для контролю перевищення завдовжки рядки об'єму відведеної пам'яті. Представлення рядків у вигляді вектора з керованою довжиною (при максимальній довжині 10) показане на рис. 4.
Хоча таке представлення рядків не забезпечує економії пам'яті, проектувальники систем програмування, як видно, вважають це прийнятною платнею за можливість працювати з мінливими рядками в статичній пам'яті.
Рис. 4. Представлення стрічки вектором з керованою довжиною
У програмному прикладі 1. приведений модуль, що реалізовує представлення рядків вектором з керованою довжиною і деякі операції над такими рядками. Для зменшення об'єму в прикладі в секції Implementation визначені не всі процедури/функції. Надаємо читачу самостійно розробити інші оголошені в секції Interface підпрограми. Дескриптор рядка описується типом _strdescr, який в точності повторює структуру, показану на рис. 4. Функція NewStr виділяє дві області пам'яті: для дескриптора рядка і для області даних рядка. Адреса дескриптора рядка, що повертається функцією NewStr - тип varstr - є тією змінною, значення якої указується користувачем модуля для ідентифікації конкретного рядка при всіх подальших операціях з нею. Область даних, покажчик на яку заноситься в дескрипторі рядка - тип _dat_area - описана як масив символів максимального можливого об'єму - 64 Кбайт. Проте, об'єм пам'яті, що виділяється під область даних функцією NewStr, як правило, менший - він задається параметром функції. Хоча індекси в масиві символів рядка теоретично можуть змінюватися від 1 до 65535, значення індексу в кожному конкретному рядку при її обробці обмежується полем maxlen дескриптора даного рядка. Всі процедури/функції обробки рядків працюють з символами рядка як з елементами вектора, звертаючись до них по індексу. Адресу вектора процедури одержують з дескриптора рядка. Зверніть увагу на те, що в процедурі CopyStr довжина результату обмежується максимальною довжиною цільового рядка.
{==== Програмний приклад 1. ====} { Представлення рядків вектором з керованою довжиною } Unit Vstr; Interface type _dat_area = array[1..65535] of char; type _strdescr = record { дескриптор рядка } maxlen, curlen : word; { максимальна і поточна довжини } strdata : ^_dat_area; { покажчик на дані рядки } end; type varstr = ^_strdescr; { тип - РЯДОК ЗМІННОЇ ДОВЖИНИ } Function NewStr(len : word): varstr; Procedure DispStr(s : varstr); Function LenStr(s : varstr): word; Procedure CopyStr(s1, s2 : varstr); Function CompStr(s1, s2 : varstr): integer; Function PosStr(s1, s2 : varstr): word; Procedure ConcatStr(var s1: varstr; s2 : varstr); Procedure SubStr(var s1 : varstr; n, l : word); Implementation {** Створення рядка; len - максимальна довжина рядка; ф-ция повертає покажчик на дескриптор рядка } Function NewStr(len : word): varstr; var addr : varstr; daddr : pointer; begin New(addr); { виділення пам'яті для дескриптора } Getmem(daddr,len); { виділення пам'яті для даних } { занесення в дескриптор початкових значень } addr^.strdata:=daddr; addr^.maxlen:=len; addr^.curlen:=0; Newstr:=addr; end; { Function NewStr } Procedure DispStr(s : varstr); {** Знищення рядка } begin FreeMem(s^.strdata,s^.maxlen); { знищення даних } Dispose(s); { знищення дескриптора } end; { Procedure DispStr } {** Визначення довжини рядка, довжина вибирається з дескриптора } Function LenStr(s : varstr): word; begin LenStr:=s^.curlen; end; { Function LenStr } Procedure CopyStr(s1, s2 : varstr); { Присвоення рядків s1:=s2} var i, len : word; begin { довжина рядка-результату м.б. обмежена її макс. завдовжки } if s1^.maxlen s2; -1 - якщо s1 < s2 } Function CompStr(s1, s2 : varstr): integer; var i : integer; begin i:=1; { індекс поточного символу } { цикл, поки не буде досягнутий кінець одного з рядків } while (i <= s1^.curlen) and (i <= s2^.curlen) do { якщо i-ые символи не рівні, функція закінчується } begin if s1^.strdata^[i] > s2^.strdata^[i] then begin CompStr:=1; Exit; end; if s1^.strdata^[i] < s2^.strdata^[i] then begin CompStr:=-1; Exit; end; i:=i+1; { перехід до наступного символу } end;{ якщо виконання дійшле до цієї крапки, то знайдений кінець одного з рядків, і всі порівняні дотепер символи були рівні; рядок меншої довжини вважається меншим }
if s1^.curlens2^.curlen then CompStr:=1 else CompStr:=0; end; { Function CompStr } . . END.9.1.5. Спискове - зв'язане представлення стрічок.
Представлення стрічок у вигляді списку в пам'яті забезпечує гнучкість у виконанні різноманітних операцій над рядками (зокрема, операцій включення і виключення окремих символів і цілих ланцюжків) і використання системних засобів управління пам'яттю при виділенні необхідного об'єму пам'яті для рядка. Проте, при цьому виникають додаткові витрати пам'яті. Іншим недоліком спискового представлення рядка є те, що логічно сусідні елементи рядка не є фізично сусідніми в пам'яті. Це ускладнює доступ до груп елементів рядка в порівнянні з доступом у векторному представленні рядка.
9.1.6. Однонаправлений лінійний список.
Кожен символ стрічки представляється у вигляді елементу зв'язного списку; елемент містить код символу і покажчик на наступний елемент, як показано на рис. 5. Одностороннє зчеплення представляє доступ тільки в одному напрямі уздовж стрічки. На кожен символ стрічки необхідний один покажчик, який звичайно займає 2-4 байти.
Рис. 5. Представлення стрічки однонаправленим зв'язним списком
9.1.7. Двонаправлений лінійний список.
У кожен елемент списку додається також покажчик на попередній елемент, як показано на рис. 6. Двостороннє зчеплення допускає двосторонній рух уздовж списку, що може значно підвищити ефективність виконання деяких рядкових операція. При цьому на кожен символ рядка необхідно два покажчики, тобто 4-8 байт.
Рис. 6. Представлення стрічки двонаправленим зв'язним списком
9.1.8. Блочно - зв'язане представлення стрічки.
Це представлення дозволяє в більшості операцій уникнути витрат, пов'язаних з управлінням динамічною пам'яттю, але в той же час забезпечує достатньо ефективне використання пам'яті при роботі з стрічками змінної довжини.
9.1.9. Блочно - зв'язане представлення стрічки.
Багатосимвольні ланки організовуються в список, так що кожен елемент списку, окрім останнього, містить групу елементів стрічки і вказівник на наступний елемент списку. Поле вказівника останнього елементу списку зберігає ознаку кінця - порожній вказівник. В процесі обробки стрычки з будь-якої її позиції можуть бути виключені або в будь-якому місці вставлені елементи, внаслідок чого ланки можуть містити менше число елементів, чим було первинне. З цієї причини необхідний спеціальний символ, який означав би відсутність елементу у відповідній позиції стрічки. Позначимо такий символ 'emp', він не повинен входити в безліч символів, з яких організовується рядок. Приклад багатосимвольних ланок фіксованою довжени по 4 символи в ланці показаний на рис.7.
Рис. 7. Представлення стрічки багатосимвольними ланками постійної довжини
Таке представлення забезпечує ефективніше використання пам'яті, чим символьно-зв'язне. Операції вставки/видалення у деяких випадках можуть зводитися до вставки/видалення цілих блоків. Проте, при видаленні одиночних символів в блоках можуть накопичуватися порожні символи emp, що може привести навіть до гіршого використання пам'яті, чим в символьно-зв'язному представленні.
9.1.10. Багатосимвольні ланки змінної довжини.
Змінна довжина блоку дає можливість позбавитися порожніх символів і тим самим економити пам'ять для стрічки. Проте з'являється потреба в спеціальному символі - ознаці вказівника, на рис.8. він позначений символом 'ptr'.
Із збільшенням довжини груп символом, що зберігаються в блоках, ефективність використання пам'яті підвищується. Проте негативною характеристикою даного методу є ускладнення операцій по резервуванню пам'яті для елементів списку і поверненню елементів, що звільнилися, в загальний список доступної пам'яті.
Рис. 8. Представлення стрічки багатосимвольними ланками змінної довжини
Такий метод спискового представлення стрічок особливо зручний в завданнях редагування тексту, коли велика частина операцій доводиться на зміну, вставку і видалення цілих слів. Тому в цих завданнях доцільно список організувати так, щоб кожен його елемент містив одне слово тексту. Символи пропуску між словами в пам'яті можуть не представлятися.
9.1.11. Багатосимвольні ланки з керованою довжиною.
Пам'ять виділяється блоками фіксованої довжини. У кожному блоці крім символів стрічки і вказівника на наступний блок міститься номера першого і останнього символів в блоці. При обробці рядка в кожному блоці обробляються тільки символи, розташовані між цими номерами. Ознака порожнього символу не використовується: при видаленні символу з рядка символи, що залишилися в блоці, ущільнюються і коректуються граничні номери. Вставка символу може бути виконана за рахунок наявного в блоці вільного місця, а за відсутності такого - виділенням нового блоку. Хоча операції вставки/видалення вимагають пересилки символів, діапазон пересилок обмежується одним блоком. При кожній операції зміни може бути проаналізована заповнена сусідніх блоків і два напівпорожні сусідні блоки можуть бути переформовані в один блок. Для визначення кінця рядка може використовуватися як порожній покажчик в останньому блоці, так і покажчик на останній блок в дескрипторі рядка. Останнє може бути досить корисним при виконанні деяких операцій, наприклад, зчеплення. У дескрипторі може зберігатися також і довжина рядка: прочитувати її з дескриптора зручніше, ніж підраховувати її перебором всіх блоків рядка.
Приклад представлення рядка у вигляді ланок з керованою довжиною 8 показаний на рис. 9.
Рис. 9. Представлення стрічки ланками керованої довжини
У програмному прикладі 2 приведений модуль, що реалізовує представлення рядків ланками з керованою довжиною. Навіть з першого погляду видно, що він значно складніше, ніж приклад 1. Це пояснюється тим, що тут вимушені обробляти як зв'язкові (списки блоків), так і векторні (масив символів в кожному блоці) структури. Тому при послідовній обробці символів рядка процедура повинна зберігати як адресу поточного блоку, так і номер поточного символу в блоці. Для цих цілей у всіх процедурах/функціях використовуються змінні cp і bi відповідно. (Процедури і функції, оброблювальні два рядки - cp1, bi1, cp2, bi2.) Дескриптор рядка - тип _strdescr - і блок - тип _block - в точності повторюють структуру, показану на рис.8. Функція NewStr виділяє пам'ять тільки для дескриптора рядка і повертає адресу дескриптора - тип varstr - він служить ідентифікатором рядка при подальших операціях з нею. Пам'ять для зберігання даних рядка виділяється тільки в міру необхідності. У всіх процедурах/функціях прийняті такі правила роботи з пам'яттю:
· якщо вихідному рядку вже виділені блоки, використовуються ці вже виділені блоки;
· якщо блоки, виділені вихідному рядку вичерпані, виділяються нові блоки - в міру необхідності;
· якщо результуюче значення вихідного рядка не використовує всі виділені рядку блоки, зайві блоки звільняються.
Для звільнення блоків визначена спеціальна внутрішня функція FreeBlock, що звільняє весь список блоків, голова якого задається її параметром.
Зверніть увагу на те, що ні в яких процедурах не контролюється максимальний об'єм рядка результату - він може бути скільки завгодно великим, а поле довжини в дескрипторі рядка має тип longint. (Додаток 2).
Щоб не перенавантажувати програмний приклад, в нього не включені засоби підвищення ефективності роботи з пам'яттю. Такі засоби включаються в операції по вибору програміста. Зверніть увагу, наприклад, що в процедурі, пов'язаній з копіюванням даних (CopyStr) у нас копіюються відразу цілі блоки. Якщо в блоці початкового рядка були невживані місця, то вони будуть і в блоці результуючого рядка. Посимвольне копіювання дозволило б усунути надлишок пам'яті в рядку-результаті. Оптимізація пам'яті, займаного даними рядка може проводиться як злиттям сусідніх напівпорожніх блоків, так і повним ущільненням даних. У дескриптор рядка може бути введене поле - кількість блоків в рядку. Знаючи загальну кількість блоків і довжину рядка можна при виконанні деяких операцій оцінювати втрати пам'яті і виконувати ущільнення, якщо ці втрати перевершують якийсь встановлений відсоток.
{==== Програмний приклад 2. ====} { Представлення стрічки ланками керованої довжини } Unit Vstr; Interface const BLKSIZE = 8; { число символів в блоці } type _bptr = ^_block; { покажчик на блок } _block = record { блок } i1, i2 : byte; { номера 1-го і останнього символів } strdata : array [1..BLKSIZE] of char; { символи } next : _bptr; { вказівник на наступний блок } end; type _strdescr = record { дескриптор рядка } len : longint; { довжина рядка } first, last : _bptr; { указ.на 1-ої і останній блоки } end; type varstr = ^_strdescr; { тип - стрічка ЗМІННОЇ ДОВЖИНИ } Function NewStr : varstr; Procedure DispStr(s : varstr); Function LenStr(s : varstr): longint; Procedure CopyStr(s1, s2 : varstr); Function CompStr(s1, s2 : varstr): integer; Function PosStr(s1, s2 : varstr): word; Procedure ConcatStr(var s1: varstr; s2 : varstr); Procedure SubStr(var s : varstr; n, l : word); Implementation Function NewBlock :_bptr; { Внутр.функция-выделение нового блоку} var n : _bptr; i : integer; begin New(n); { виділення пам'яті } n^.next:=nil; n^.i1:=0; n^.i2:=0; { початкові значення } NewBlock:=n; end; { NewBlock } {*** Внутр.функція - звільнення ланцюжка блоку, починаючи із с } Function FreeBlock(с : _bptr): _bptr; var x : _bptr; begin { рух по ланцюжку із звільненням пам'яті } while c<>nil do begin x:=c; c:=c^.next; Dispose(x); end; FreeBlock:=nil; { завжди повертає nil } end; { FreeBlock }Function NewStr : varstr; {** Створення рядка } var addr : varstr; begin New(addr); { виділення пам'яті для дескриптора } {занесення в дескриптор початкових значень} addr^.len:=0; addr^.first:=nil; addr^.last:=nil; Newstr:=addr; end; { Function NewStr } Procedure DispStr(s : varstr); {** Знищення рядка } begin s^.first:=FreeBlock(s^.first); { знищення блоків } Dispose(s); { знищення дескриптора } end; { Procedure DispStr } {** Визначення довжини стрічки, довжина вибирається з дескриптора } Function LenStr(s : varstr): longint; begin LenStr:=s^.len; end; { Function LenStr } {** Присвоення рядків s1:=s2 } Procedure CopyStr(s1, s2 : varstr); var bi1, bi2 : word; { індекси символів в блоках для s1 і s2 } cp1, cp2 : _bptr; { адреси поточних блоків для s1 і s2 } pp : _bptr; { адреса попереднього блоку для s1 } begin cp1:=s1^.first; pp:=nil; cp2:=s2^.first; if s2^.len=0 then begin { якщо s2 порожня, звільняється вся s1 } s1^.first:=FreeBlock(s1^.first); s1^.last:=nil; end else begin while cp2<>nil do begin { перебір блоків s2 } if cp1=nil then begin { якщо в s1 більше немає блоків } { виділяється новий блок для s1 } cp1:=NewBlock; if s1^.first=nil then s1^.first:=cp1 else if pp<>nil then pp^.next:=cp1; end; cp1^:=cp2^; { копіювання блоку } { до наступного блоку } pp:=cp1; cp1:=cp1^.next; cp2:=cp2^.next; end; { while } s1^.last:=pp; { останній блок } {якщо в s1 залишилися зайві блоки - звільнити їх} pp^.next:=FreeBlock(pp^.next); end; { else } s1^.len:=s2^.len; end; { Procedure CopyStr } {** Порівняння рядків - повертає: 0, якщо s1=s2; 1 - якщо s1 > s2; -1 - якщо s1 < s2 } Function CompStr(s1, s2 : varstr): integer; var bi1, bi2 : word; cp1, cp2 : _bptr; begin cp1:=s1^.first; cp2:=s2^.first; bi1:=cp1^.i1; bi2:=cp2^.i1; // цикл, поки не буде досягнутий кінець одного з рядків while (cp1<>nil) and (cp2<>nil) do begin // якщо соответств.символы не рівні, ф-ция закінчується if cp1^.strdata[bi1] > cp2^.strdata[bi2] then begin CompStr:=1; Exit; end; if cp1^.strdata[bi1] < cp2^.strdata[bi2] then begin CompStr:=-1; Exit; end; bi1:=bi1+1; { до наступного символу в s1 } if bi1 > cp1^.i2 then begin cp1:=cp1^.next; bi1:=cp1^.i1; end; bi2:=bi2+1; { до наступного символу в s2 } if bi2 > cp2^.i2 then begin cp2:=cp2^.next; bi2:=cp2^.i1; end; end; {ми дійшли до кінця одного з рядків рядок меншої довжини вважається меншим } if s1^.len < s2^.len then CompStr:=-1 else if s1^.len > s2^.len then CompStr:=1 else CompStr:=0; end; { Function CompStr } . .end.Питання:
1. Що таке вказівник.
2. Що таке список даних.
3. Що таке однонаправлений список.
4. Що таке двонаправлений список.
Література: