Вектор з керованою довжиною.

9.1.5. Спискове - зв'язане представлення стрічок.

9.1.6. Однонаправлений лінійний список.

9.1.7. Двонаправлений лінійний список.

9.1.8. Блочно - зв'язане представлення стрічки.

9.1.10. Багатосимвольні ланки змінної довжини.

9.1.11. Багатосимвольні ланки з керованою довжиною.

 

Питання

Література

Додаток 1

 

Розділ 9. Символьні типи даних.

 

Символьні дані можуть зберігати текст, наприклад, для виводу на екран або у вікно діалогу. Символьні дані – це простий ланцюжок з чисел. Кожне число – це порядковий номер символу в таблиці символів. Наприклад, якщо представити наш алфавіт у вигляді таблиці символів (тільки представити), то число 0 означатиме букву А, число 1 означатиме букву Б, і так далі.

У Delphi використовується 8-бітова розширена таблиця символів, де задіяні всі 8 бітів (ASCII - American Standard Code for InformationInterchange – таблиця, 0-255 символів). Ця таблиця береться з самої операційної системи - Windows. Отже кількість символів і їх розташування залежить від ОС. Для того, щоб задовольнити всі національності, вже давно ввели підтримку UNICODE (16-бітова таблиця, 65536 символів). У ній перші 8 біт співпадають з таблицею ANSI, а інші є специфічними. Починаючи з Windows 2000, це кодування починає використовуватися все ширше і ширше.

 

Рис. 1.1. Розкладка UNICODe кодування для BMP-Basic Multilingual Plane (Plane 0)

 

У Delphi присутні наступні основні типи символів і стрічок:

Тип	Максимальна довжина рядка	Пам'ять що відводиться для збереження рядка	Примітка
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 байтів яка має наступний вид:

 

 

Змінна типу AnsiString представляє собою 4-х байтовий вказівник на дескриптор наведеної структури, безпосередньо за яким в пам’яті розмішається символи стрічки. Якщо довжина стрічки має нульову довжину, то пам’ять під неї і під дескриптор не виділяється, а відповідна змінна має значення nil.

Внутрішня будова довгої стрічки в пам’яті можна представити як представлено на малюнку.

 

var

LongStr1, LongStr2: AnsiString;

// Після обробки оголошення значення вказівника на стрічку

// AnsiString встановлюється в nil

 

begin

LongStr1:= ’Дуже довга стрічка..........Дуже довга стрічка’;

// Після такого присвоення структура стрічки AnsiString буде мати

//наступний вигляд

Рис. Внутрішня будова довгої стрічки в пам’яті

 

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

 

LongStr2:= LongStr1;

 

То схема розподілу пам’яті буде мати наступний вигляд, що представлений малюнком:

Таким чином при виконанні присвоєння виконується копіювання тільки 4-х байтового значення вказівника на стрічку, в результаті чого оператори присвоєння стрічок типа AnsiString виконуються значно швидше, ніж стрічки типу ShortString, і оперативна пам’ять використовуєть економніше.

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

Якщо ця стрічка буде присвоєна ще одній змінній

 

LongStr3:= LongStr1;

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

Показати або проглянути таблицю символів 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 "зайвих" символу на рядок), але мінливість рядка забезпечувалася украй неефективно. Оскільки вектор - статична структура, кожна зміна довжини рядка вимагає створення нового вектора, пересилки в нього незмінної частини рядка і знищення старого вектора. Це зводить нанівець всі переваги роботи із статичною пам'яттю. Тому найбільш популярним способом представлення рядків в пам'яті, вектор з керованою довжиною.