Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Лекція
Предмет:
Об’єктно-орієнтоване програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
НУ „Львівська політехніка”
Лекція №11
з курсу: «Застосування засобів об’єктно-орієнтованого програмування в лінгвістичних задачах»
Львів - 2010
Розділ 9. Символьні типи даних.
Символьні дані можуть зберігати текст, наприклад, для виводу на
екран або у вікно діалогу. Символьні дані – це простий ланцюжок з чисел.
Кожне число – це порядковий номер символу в таблиці символів.
Наприклад, якщо представити наш алфавіт у вигляді таблиці символів
(тільки представити), то число 0 означатиме букву А, число 1 означатиме
букву Б, і так далі.
У Delphi використовується 8-бітова розширена таблиця символів, де
задіяні всі 8 бітів (ASCII - American Standard Code for Information
Interchange – таблиця, 0-255 символів). Ця таблиця береться з самої
операційної системи - Windows. Отже кількість символів і їх розташування
залежить від ОС. Для того, щоб задовольнити всі національності, вже
давно ввели підтримку UNICODE (16-бітова таблиця, 65536 символів). У
ній перші 8 біт співпадають з таблицею ANSI, а інші є специфічними.
Починаючи з Windows 2000, це кодування починає використовуватися
все ширше і ширше.
Рис. 1.1. Розкладка UNICODe кодування для BMP-Basic Multilingual Plane
(Plane 0)
У Delphi присутні наступні основні типи символів і стрічок:
ASCIIU+0000LatinGreekCyrillicHebrewArabicIndicThaiFuture usePunctuationSymbolsU+FFFFKanaOther CJKIdeographsHangulSurrogatesPrivate useCompatibility
Тип
Максимальна
довжина рядка
Пам'ять що
відводиться для
збереження рядка
Примітка
AnsiChar
1 байт
ANSI
WideChar
2 байт
UNICODE
Char
1 байт
Родовий символьний
тип
ShortString
255 символів
Від 2 до 256 байт
AnsiString
231
Від 4 байтів до
2 Гбайт
8 бітові
WideString
230
Від 4 байтів до
2 Гбайт
UNICODE
( вказівних типа Pointer, Pchar , Text )
В ShortString – стрічках текуча довжина вказується в нульовому
(індекс нуль) елементі стрічки. В цьому елементі записується символ, код
якого дорівнює значенню текучої довжини. Нульовий елемент стрічки при
цьому зроблений невидимим для користувача. Оскільки кожен символ
займає один байт пам’яті, то при такому способі способі вказання довжини,
максимально допустима довжина стрічки буде обмежена максимальним
значенням, яке можна записати в один байт пам’яті, не більше 255
символів.
n – фіксована загальна довжина стрічки;
p – текуча довжина стрічки.
var
Smax2: ShortString;
На відміну від ShortString – стрічок, пам’ять під довгі стрічки
AnsiString виділяються не статично а динамічно. Крім того, AnsiString –
стрічка не має максимальної довжини, що встановлюеться при оголошенні,
а тільки динамічну текучу довжину. Спільним для обох типів стрічок є
наявність дескриптора. Однак якщо для коротких стрічок дескриптор має
простий вид додаткового нульового елемента, в якому зберігається текуча
довжина стрічки, то у довгих стрічок дескриптор предсталяє собою більш
складну структуру довжиною 8 байтів яка має наступний вид:
012345111012761398BADRLNOСимвол, код якого дорівнює 7.14p = 7n = 14
Текуча довжина стрічки(4 байта)
Лічильник посилань на стрічку(4 байта)
Змінна типу AnsiString представляє собою 4-х байтовий вказівник на
дескриптор наведеної структури, безпосередньо за яким в пам’яті
розмішається символи стрічки. Якщо довжина стрічки має нульову
довжину, то пам’ять під неї і під дескриптор не виділяється, а відповідна
змінна має значення nil.
Внутрішня будова довгої стрічки в пам’яті можна представити як
представлено на малюнку.
var
LongStr1, LongStr2: AnsiString;
// Після обробки оголошення значення вказівника на стрічку
// AnsiString встановлюється в nil
begin
LongStr1 := ’Дуже довга стрічка ..........Дуже довга стрічка’;
// Після такого присвоення структура стрічки AnsiString буде мати
//наступний вигляд
Рис. Внутрішня будова довгої стрічки в пам’яті
Стрічки типу AnsiString мають ще одну особливість, яка пов’язана з
лічильником посилань на стрічку, що входять в дескріптор стрічки, та з
принципом розподілу пам’яті для змінних цього типу. Якщо декільком
змінним типа AnsiString присвоюється одна і тама сама стрічка, то пам’ять
багаторазово не виділяється, а ці змінні будуть просто вказувати на
дескриптор даної стрічки. Наприклад якщо після описаних вишче операцій
виконати оператор
nilLongStr1
Адреса стрічкиLongStr1Текуча довжинастрічкиЛічильник
посилань на
стрічкуДуже довга стрічка
..........Дуже довга стрічка\04 байти4 байти4 байтиНульсимвол
LongStr2 := LongStr1;
То схема розподілу пам’яті буде мати наступний вигляд, що
представлений малюнком:
Таким чином при виконанні присвоєння виконується копіювання тільки
4-х байтового значення вказівника на стрічку, в результаті чого оператори
присвоєння стрічок типа AnsiString виконуються значно швидше, ніж
стрічки типу ShortString, і оперативна пам’ять використовуєть
економніше.
Значення лічильна посилань завжди дорівнює числу змінних довгого
стрічкового типу, яким відповідає данна стрічка.
Якщо ця стрічка буде присвоєна ще одній змінній
LongStr3 := LongStr1;
То лічильник посилань буде дорівнювати 3. Якщо після цього деяка
змінна, наприклад LongStr1, отримає нове значення, то лічильник посилань
стрічки ’Дуже довга стрічка ..........Дуже довга стрічка’; буде зменшений на
одиницю, а лічильник посилань нової стрічки, LongStr1 буде збільшений на
одиницю. Якщо значення нової стрічки в пам’яті ше не існує, то для неї
виділяється пам’ять в динамічній області. Якщо після чергового оператора
лічильник посилань стає рівним нулю, то ця стрічка видаляється з пам’яті.
Адреса стрічкиLongStr1ДовжинастрічкиЛічильник
посилань = 2Дуже довга стрічка
..........Дуже довга стрічка\04 байти4 байти4 байтиНульсимволАдреса стрічкиLongStr2
Показати або проглянути таблицю символів ANSI
unit Unit2;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
st:string; // таблиця формується як стрічка символів
dec: byte; // код символа
i,j:integer; // номер стрічки і стовпчика таблиці
begin
st:='';
dec:=0;
for i:=0 to 15 do // шестнадцать стрічок
begin
dec:=i + 192;
for j:=1 to 4 do // чотири стовпчики
begin
st:=st+chr(dec)+'-'+IntToStr(dec)+' ';
dec:=dec + 16;
end;
st:=st + #13; // перехід до нової стрічки екрану
end;
Label1.caption:=st;
end;
end.
9.1. Представлення текстових стрічок в пам'яті
комп’ютера.
Представлення стрічок в пам'яті залежить від того, наскільки
мінливими є стрічки в кожному конкретному завданні, і засоби такого
представлення варіюються від абсолютно статичного до динамічного.
Універсальні мови програмування в основному забезпечують роботу з
рядками змінної довжини, але максимальна довжина рядка повинна бути
вказана при її створенні. Якщо програміста не влаштовують можливості
або ефективність тих засобів роботи з рядками, які надає йому мову
програмування, то він може або визначити свій тип даних "рядок" і
використовувати для його представлення засобу динамічної роботи з
пам'яттю, або змінити мову програмування на спеціально орієнтовану на
обробку тексту (CNOBOL, REXX), в яких представлення рядків базується на
динамічному управлінні пам'яттю.
9.1.1. ВЕКТОРНЕ ПРЕДСТАВЛЕННЯ СТРІЧОК.
Представлення стрічок у вигляді векторів, прийняте в більшості
універсальних мов програмування, дозволяє працювати з стрічками,
розміщеними в статичній пам'яті. Крім того, векторне представлення
дозволяє легко звертатися до окремих символів стрічки як до елементів
вектора - по індексу.
Найпростішим способом є представлення стрічки у вигляді вектора
постійною довжени. При цьому в пам'яті відводиться фіксована кількість
байт, в які записуються символи рядка. Якщо рядок менше вектора, що
відводиться під неї, то зайві місця заповнюються пропусками, а якщо рядок
виходить за межі вектора, то зайві (звичайно справа рядки) символи
повинні бути відкинуті.
На рис. 1. приведена схема, на якій показане представлення двох
рядків: 'ABCD' і 'PQRSTUVW' у вигляді вектора постійної довжини на шість
символів.
Рис. 1. Представлення стрічок векторами постійної довжини
9.1.2. ПРЕДСТАВЛЕННЯ СТРІЧОК ВЕКТОРОМ ЗМІННОЇ ДОВЖИНИ
З ОЗНАКОЮ КІНЦЯ.
Цей і все подальші за ним методи враховують змінну довжину стрічок.
Ознака кінця - це особливий символ, що належить алфавіту (таким чином,
корисний алфавіт виявляється меншим на один символ), і займає ту ж
кількість розрядів, що і вся решта символів. Витрати пам'яті при цьому
способі складають 1 символ на рядок. Таке представлення рядка показане
на рис. 2. Спеціальний символ-маркер кінця рядка позначений тут 'eos'. У
мові C, наприклад, як маркер кінця рядка використовується символ з кодом
0.
Рис. 2. Представлення стрічок змінної довжини з ознакою кінця
9.1.3. ПРЕДСТАВЛЕННЯ СТРІЧОК ВЕКТОРОМ ЗМІННОЇ ДОВЖИНИ
З ЛІЧИЛЬНИКОМ.
Лічильник символів - це ціле число, і для нього відводиться достатня
кількість бітів, щоб їх з лишком вистачало для представлення довжини
щонайдовшого рядка, яку тільки можна представити в даній машині.
Звичайно для лічильника відводять від 8 до 16 бітів. Тоді при такому
представленні витрата пам'яті з розрахунку на один рядок складають 1-2
символи. При використанні лічильника символів можливий довільний
доступ до символів в межах рядка, оскільки можна легко перевірити, що
звернення не виходить за межі рядка. Лічильник розміщується в такому
місці, де він може бути легко доступний - початку рядка або в дескрипторі
рядка. Максимально можлива довжина рядка, таким чином, обмежена
розрядністю лічильника. У PASCAL, наприклад, рядок представляється у
вигляді масиву символів, індексація в якому починається з 0; однобайтний
лічильник числа символів в рядку є нульовим елементом цього масиву.
Таке представлення рядків показане на рис. 3. І лічильнику символів, і
ознаці кінця у попередньому випадку можуть бути доступні для програміста
як елементи вектора.
Рис. 3. Представлення стрічок змінної довжини з лічильником
У двох попередніх варіантах забезпечувалося максимально ефективне
витрачання пам'яті (1-2 "зайвих" символу на рядок), але мінливість рядка
забезпечувалася украй неефективно. Оскільки вектор - статична
структура, кожна зміна довжини рядка вимагає створення нового вектора,
пересилки в нього незмінної частини рядка і знищення старого вектора. Це
зводить нанівець всі переваги роботи із статичною пам'яттю. Тому найбільш
популярним способом представлення рядків в пам'яті, вектор з керованою
довжиною.
9.1.4. ВЕКТОР З КЕРОВАНОЮ ДОВЖИНОЮ.
Пам'ять під вектор з керованою довжиною відводиться при створенні
стрічки і її розмір і розміщення залишаються незмінними весь час існування
стрічки. У дескрипторі такого вектора-рядка може бути відсутнім
початковий індекс, оскільки він може бути зафіксований раз назавжди
встановленими угодами, але з'являється поле поточної довжини рядка.
Розмір рядка, таким чином, може змінюватися від 0 до значення
максимального індексу вектора. "Зайва" частина пам'яті, що відводиться,
може бути заповнена будь-якими кодами - вона не береться до уваги при
операції з рядком. Поле кінцевого індексу може бути використано для
контролю перевищення завдовжки рядки об'єму відведеної пам'яті.
Представлення рядків у вигляді вектора з керованою довжиною (при
максимальній довжині 10) показане на рис. 4.
Хоча таке представлення рядків не забезпечує економії пам'яті,
проектувальники систем програмування, як видно, вважають це
прийнятною платнею за можливість працювати з мінливими рядками в
статичній пам'яті.
Рис. 4. Представлення стрічки вектором з керованою довжиною
У програмному прикладі 1. приведений модуль, що реалізовує
представлення рядків вектором з керованою довжиною і деякі операції над
такими рядками. Для зменшення об'єму в прикладі в секції Implementation
визначені не всі процедури/функції. Надаємо читачу самостійно розробити
інші оголошені в секції Interface підпрограми. Дескриптор рядка
описується типом _strdescr, який в точності повторює структуру, показану
на рис. 4. Функція NewStr виділяє дві області пам'яті: для дескриптора
рядка і для області даних рядка. Адреса дескриптора рядка, що
повертається функцією NewStr - тип varstr - є тією змінною, значення якої
указується користувачем модуля для ідентифікації конкретного рядка при
всіх подальших операціях з нею. Область даних, покажчик на яку
заноситься в дескрипторі рядка - тип _dat_area - описана як масив
символів максимального можливого об'єму - 64 Кбайт. Проте, об'єм пам'яті,
що виділяється під область даних функцією NewStr, як правило, менший -
він задається параметром функції. Хоча індекси в масиві символів рядка
теоретично можуть змінюватися від 1 до 65535, значення індексу в
кожному конкретному рядку при її обробці обмежується полем maxlen
дескриптора даного рядка. Всі процедури/функції обробки рядків
працюють з символами рядка як з елементами вектора, звертаючись до них
по індексу. Адресу вектора процедури одержують з дескриптора рядка.
Зверніть увагу на те, що в процедурі CopyStr довжина результату
обмежується максимальною довжиною цільового рядка.
{==== Програмний приклад 1. ====}
{ Представлення рядків вектором з керованою довжиною }
Unit Vstr;
103*
ABD???????
108*
PQRSTUVW??
Максимальна довжинаВказівник на даніТекуча довжина
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. Представлення стрічки ланками керованої довжини
1111888627Представленнястрічки8анцюг1ламизкеро8аноювдо1вжиноюnil50
У програмному прикладі 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.
17.02.2013 23:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора