Для зберігання списку покажчиків на розміщені в адресному просторі структури (об'єкти, динамічні масиви, змінні) призначено клас TList. Як і список рядків TstringList, список покажчиків забезпечує ефективну роботуз списку елементів.
Клас TList
Основою класу TList є перелік покажчиків. Сам список є динамічним масивом покажчиків, до якого можна звернутися через індексовану властивість
property Items: Pointer;
Нумерація елементів починається із нуля.
Прямий доступ до елементів масиву можливий через властивість
type
PPointerList = ^TPointerList;
TPointerList = array of Pointer;
property List: PPointerList;
що має атрибут "тільки для читання".
Оскільки елементи списку є вказівниками на деякі структури, пряме звернення до складовим частинамцих структур через властивість елементів неможливо. Як це можна зробити, розповідається нижче у прикладі.
Примітка
У списку можуть бути вказівники на різнорідні структури. Не обов'язково зберігати у списку лише вказівники на об'єкти або вказівники на запис.
Реалізовані у класі TList операції зі списком забезпечують потреби розробника та збігаються з операціями списку рядків.
Для додавання до кінця списку нового покажчика використовується метод
function Add(Item: Pointer): Integer;
Пряме надання значення елементу, який ще не створений за допомогою методу Add, викликає помилку часу виконання.
Новий покажчик можна додати до потрібного місця списку. Для цього використовується метод
procedure Insert(Index: Integer; Item: Pointer);
У index вказується необхідний порядковий номер у списку.
Перенесення існуючого елемента на нове місце здійснюється методом
procedure Move (Curlndex, Newlndex: Integer);
Параметр CurIndex визначає старе положення покажчика. Параметр NewIndex задає нове положення.
Також можна поміняти місцями два елементи, що визначаються параметрами Indexl та Index2:
procedure Exchange(Indexl, Index2: Integer);
Для видалення покажчиків із списку використовуються два методи. Якщо відомий індекс, застосовується метод
procedure Delete(Index: Integer);
Якщо відомий сам покажчик, використовується метод
function Remove(Item: Pointer): Integer;
Ці методи не зменшують обсягу пам'яті, виділеної під список. При необхідності зробити це слід використовувати якість capacity. Також існує метод Expand, який збільшує відведену пам'ять автоматично, залежно від поточного розміру списку.
функція Expand: TList;
Щоб метод спрацював, необхідно, щоб count = Capacity.
Метод
procedure Clear; dynamic;
використовується для видалення всіх елементів списку одразу. Для пошуку вказівника за його значенням використовується метод
функція IndexOf(Item: Pointer): Integer;
Метод повертає індекс знайденого елемента у списку. При невдалому пошуку повертається – 1.
Для сортування елементів списку застосовується метод
procedure Sort(Compare: TListSortCompare);
Оскільки склад структури, яку вказує елемент списку, неможливо заздалегідь узагальнити, розробка процедури, яка здійснює сортування, доручається програміста. Метод Sort лише забезпечує попарне порівняння покажчиків на основі створеного програмістом алгоритму (приклад сортування див. вище в розд. "Клас TStringList").
Цілком всі властивості та методи класу TList представлені в табл. 7.2.
Таблиця 7.2. Властивості та методи класу TList
Оголошення
Опис
property Capacity: Integer;
Визначає кількість рядків, для яких виділено пам'ять
property Count: Integer;
Повертає кількість рядків у списку
property Items : Pointer;
Список покажчиків
type
TPointerList = array of Pointer;
PPointerList = ATPointerList; property List: PPointerList;
Динамічний масивпокажчиків
function Add (Item: Pointer): Integer;
Додає до списку новий покажчик
procedure Clear; dynamic;
Повністю очищає список
procedure Delete (Index: Integer:;
Видаляє вказівник з індексом
Index
class procedure Error (const Ksg: string; Data: Integer); virtual;
Генерує виняткову
Ситуація EListError.
Повідомлення про помилку створюється з форматуючого рядка Msg та числового параметра Data
procedure Exchange (Indexl, Index2: Integer);
Змінює місцями покажчики з індексами Indexl та Index2
функція Expand: TList;
Збільшує розмір пам'яті, відведеної під список
function First: Pointer;
Повертає перший покажчик зі списку
функція IndexOf (Item: Pointer): Integer;
Повертає індекс покажчика, заданого параметром Item
procedure Insert (Index: Integer; Item: Pointer) ;
Вставляє новий елемент Items позицію Index
функція Last: Pointer;
Повертає останній покажчик у списку
procedure Move (Curlndex, Newlndex: Integer);
Переміщує елемент списку на нове місце
procedure Pack;
Видаляє зі списку всі порожні (Nil) покажчики
function Remove (Item: Pointer): Integer;
Видаляє зі списку вказівник
Item
type TListSortCompare = функція (Iteml, Item2: Pointer): Integer;
procedure Sort (Compare: TListSortCompare);
Сортує елементи списку
Приклад використання списку покажчиків
Розглянемо використання списків покажчиків з прикладу програми DemoList. При натисканні мишею на формі програми відображається точка, якій надається порядковий номер. Одночасно координати та номер точки записуються у відповідні властивості створюваного екземпляра класу TMypixel. Вказівник на цей об'єкт передається до нового елемента списку pixList.
Через війну після очищення форми всю послідовність точок можна відновити, використовуючи покажчики на об'єкти точок зі списку.
Список точок можна відсортувати за координатою X у порядку зростання.
Лістинг. Модуль головної форми проекту DemoList
Unit Main;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Buttons;
type
TMainForm = class(TForm)
ListBtn: TBitBtn;
ClearBtn: TBitBtn;
DelBtn: TBitBtn;
SortBtn: TBitBtn;
procedure FormCreate(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure FormMouseDown(Sender: TObject; Button: TMouseButton;
procedure ListBtnClick(Sender: TObject);
procedure ClearBtnClick(Sender: TObject);
procedure DelBtnClick(Sender: TObject);
procedure SortBtnClick(Sender: TObject);
private
PixList: TList;
PixNum: Integer; public
(Public declarations)
end;
TMyPixel = class(TObject)
FX: Integer;
FY: Integer;
FText: Integer;
constructor Create (X, Y, Num: Integer);
procedure SetPixel;
end;
var
MainForm: TMainForm;
implementation
($ R *.DFM)
const PixColor = clRed;
var CurPixel: TMyPixel;
constructor TMyPixel.Create(X, Y, Num: Integer);
begin
inherited Create;
FX: = X;
FY: = Y;
FText:= Num;
SetPixel;
end;
procedure TMyPixel.SetPixel;
begin
MainForm.Canvas.PolyLine();
MainForm.Canvas.TextOut(FX +1, FY + 1, IntToStr(FText));
end;
функція PixCompare (Iteml, Item2: Pointer): Integer;
var Pixl, Pix2: TMyPixel;
begin
Pixl: = Iteml;
Pix2: = Item2;
Result:= Pixl.FX - Pix2.FX;
end;
procedure TMainForm.FormCreate(Sender: TObject);
begin
PixList: = TList.Create;
PixNum: = 1; (лічильник точок)
Canvas.Pen.Color: = PixColor; (Колір точки)
Canvas.Pen.Width: = 3; (Розмір точки)
Canvas.Brush.Color:= Color; (Колір фону тексту дорівнює кольору форми)
end;
procedure TMainForm.FormClose(Sender: TObject; var Action: TCloseAction);
begin
PixList.Free;
end;
procedure TMainForm.FormMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
PixList.Add(TMyPixel.Create(X, Y, PixNum));
Inc(PixNum);
end;
procedure TMainForm.ListBtnClick(Sender: TObject);
var i: Integer;
begin
with PixList do
for i:= 0 to Count - 1 do
begin
CurPixel:= Items[i]; CurPixel.SetPixel;
end; end;
procedure TMainForm.ClearBtnClick(Sender: TObject);
begin
Canvas.FillRect(Rect(0, 0, Width, Height));
end;
procedure TMainForm.DelBtnClick(Sender: TObject);
begin
PixList.Clear;
PixNum: = 1;
end;
procedure TMainForm.SortBtnClick(Sender: TObject);
var i: Integer;
begin
PixList.Sort(PixCompare);
with PixList do
for i:= 0 to Count - 1 do TMyPixel(Items[i]).FText:= i + 1;
end;
end.
Клас TMyPixel забезпечує зберігання координат точки та її порядковий номер у серії. Ці параметри передаються конструктор класу. Метод setPixel забезпечує відображення точки на канві форми.
Примірник класу створюється для кожної нової точкипри натисканні кнопкою миші в методі-обробнику FormMouseDown. Тут же вказівник на новий об'єктзберігається у створюваному за допомогою методу Add елемент списку PixList. Таким чином, програма "запам'ятовує" розташування та порядок проходження точок.
Метод-обробник ListBtnClick забезпечує відображення точок. Для цього в циклі поточний покажчик списку передається до змінної об'єктного типу curPixel, тобто в цій змінній по черзі "побувають" усі створені об'єкти, покажчики на які зберігаються у списку.
Це зроблено для того, щоб отримати доступ до властивостей об'єктів (безпосередньо через покажчик цього не можна зробити). Другий спосіб приведення типу розглянутий метод-обробнику SortBtnClick.
Перед вторинним відображенням крапок необхідно очистити поверхню форми. Цю операцію виконує метод-обробник clearBtnClick.
Список точок можна відсортувати за координатою X у порядку зростання. Для цього в методі-обробнику SortBtnClick викликається метод Sort списку PixList. У параметрі методу (змінна процедурного типу) передається функція PixCompare, яка забезпечує інкапсульований у методі Sort механізм перебору елементів списку алгоритмом прийняття рішення про старшість двох сусідніх елементів.
Якщо функція повертає додатне число, то елемент item1 більше елемента item2. Якщо результат негативний, то item1 менше, ніж item2. Якщо елементи дорівнюють, функція повинна повертати нуль.
У разі порівнювалися координати X двох точок. В результаті такого сортування за зростанням об'єкти виявилися розташовані так, що перший елемент списку вказує на об'єкт з мінімальною координатою X, а останній на об'єкт з максимальною координатою X.
Після сортування залишилося знову пронумерувати всі точки. Це робить цикл у методі-обробнику SortBtnclick. Зверніть увагу на застосований у цьому випадку спосіб приведення типу, що забезпечує звернення до властивостей екземплярів класу TMypixel.
Метод-обробник DeiBtnClick забезпечує повне очищеннясписок pixList.
Вступ
1. Визначення АТД
3. Опис операцій
3.1 Операція додавання елемента
3.2 Операція додавання елемента після вказаного
3.3 Операція видалення вказаного елемента
3.4 Операція роздруківки записів списку
4. Реалізація АТД-список
4.1 Головна функція
4.2 Інтерфейс
4.3 Реалізація методів
Висновок
Список літератури
Додаток A: граф-схеми алгоритмів
Вступ
Незалежно від типу розв'язуваних завдань, будь-яка програма оперує якимись даними, а сама програма є методами управління та обробки цих даних. Швидкість виконання програмою поставленого завдання залежить тільки від алгоритмів, використаних у ній для обробки та управління даними, але й від самої організації даних. Таким чином, ми приходимо до поняття структур даних.
Пряма взаємодія між програмою через користувача та структурами даних залишає відкритими безліч даних, модифікація яких нелегітимним способом (минаючи інтерфейс) може призвести до небажаних наслідків. Щоб уникнути цю проблемунеобхідно "звести стіни" між даними та програмою, залишивши лише "віконце" у вигляді інтерфейсу. Для цього необхідно визначити абстрактні типи даних, за допомогою яких ці стіни споруджуються.
У роботі розробляється абстрактний тип даних (АТД) – список, який згодом реалізується як зв'язкового списку, реалізованого з допомогою непрямої адресації, заснованої на покажчиках. Докладніше питання розробки АТД розглядаються у .
1. Визначення АТД
Абстракція даних визначає, що можна робити з набором даних, ігноруючи питання "як це робиться?". Абстракція даних – це спосіб розробляти окремі компонентипрограми, незалежно від решти її частини (інших компонентів). Таким чином, абстракція даних - природне розширення функціональної абстракції, що дозволяє розробляти функції відносної ізоляції один від одного. Набір даних у поєднанні із сукупністю операцій з них називається абстрактним типом даних. Опис операцій, які входять у АТД, має бути досить суворим, щоб точно вказати їх вплив на дані. Але в ньому не повинен вказуватись спосіб зберігання даних або деталі виконання операцій. Конкретний спосібзберігання даних (структура даних) вибирається лише за реалізації АТД. Структура даних – конструкція, визначена у мові програмування зберігання набору даних. Згідно з варіантом завдання, визначено такі дані:
1. Найменування мікросхеми
2. Вартість
3. Кількість
Над ними визначено такі операції:
1.Додавання елемента в невпорядкований список
2.Видалення елемента із заданим полем з невпорядкованого списку
3.Додавання елемента після зазначеного
4.Видалення всіх елементів із заданим полем
5. Роздруківка списку
Цей набірвизначає безліч допустимих операцій над випередженими завданням даними, тобто. нам заданий абстрактний тип даних.
2. Загальні положення
Абстрактний список можна реалізувати у вигляді масиву – на перший погляд очевидний крок. Масив має фіксований розмір(у більшості мов програмування), тоді як довжина абстрактного списку необмежена. Таким чином, структура даних стає статичною, що є недоліком.
Інший істотний недолікє продовженням гідності масивів – послідовне розташування даних у суміжних осередках, інакше кажучи, що так часто виробляються, отже, вимагають максимальної швидкостівиконання, операції як вставка та видалення елемента призводять до необхідності зрушувати елементи масиву, витрачаючи додатковий час.
Принцип реалізації списку, який не використовує здиг елементів, заснований на непрямій адресації. Про інші способи реалізації абстарктних списків докладно розповідається у .
Кожен вузол пов'язаного спискускладається з двох частин: безпосередньо даних та покажчика на наступний елемент – такий самий вузол або константу NULL.
Оскільки згідно з принципом інкапсуляції доступ до даних повинен здійснюватися тільки за допомогою методів, визначених для цієї мети, для даних визначено специфікатор доступу private.
Механізм виділення пам'яті під елементи списку, що базується на покажчиках, передбачає динамічне виділенняпам'яті за допомогою операторів newта delete. Таким чином, при створенні нового елемента має сенс виділяти пам'ять тільки під нові дані, а не під уже певні методи- Операції списку. Отже, необхідно винести методи із структури даних. У цьому роботі, була застосована методика розширення інтерфейсу створенням структури методів – дружнього класу, методи якого мають доступом до закритим членам класу вузла.
Докладніше про принципи об'єктно-орієнтованого програмування можна дізнатись з .
Покажчики на голову і хвіст списку оголошені в класі List, оскільки по суті необхідні для реалізації методів АТД, тоді як для самої структури даних вони не мають жодного сенсу.
Методи, які не повинні жодним чином модифікувати дані, оголошені з використанням ключового слова const.
водити всі події, що з звичайними змінними. Для роботи з динамічним розподіломпам'яті дуже зручно використовувати пов'язані структуриданих, наприклад, однозв'язкові списки. Найпростішим прикладом списку є масив, у якому послідовно розташовані його елементи. Але таке уявлення має суттєвий недолік – потрібно заздалегідь точно вказати кількість елементів...
Підхід до розробки ефективного алгоритмудля вирішення будь-якого завдання – вивчити її суть. Часто завдання можна сформулювати мовою теорії множин, що відноситься до фундаментальних розділів математики. У цьому випадку алгоритм її розв'язання можна викласти в термінах основних операцій над безліччю. До таких завдань належать і завдання інформаційного пошуку, у яких вирішуються проблеми, ...
Даних нестиме більше сенсу, якщо його відсортувати якимось чином. Часто потрібно сортувати дані кількома у різний спосіб. По-друге, багато алгоритмів сортування є цікавими прикладамипрограмування. Вони демонструють важливі методи, такі як часткове впорядкування, рекурсія, злиття списків та зберігання двійкових дерев у масиві. Зрештою, сортування...
Потужність (замінювати процесори), розширювати ємність оперативної пам'яті, додавати зовнішні пристрої. Машини мають великі набори команд, розвинене системне програмне забезпечення, що включає транслятори мов програмування Асемблер, ФОРТРАН, ПЛ/1, КОБОЛ, АЛГОЛ, ПАСКАЛЬ, Операційні системиз різними функціональними можливостями. Основна особливість керуючих обчислювальних машин.
перелік являє собою сукупність динамічних об'єктіводного типу, упорядкованих за допомогою посилань.
Об'єкти називають елементами списку. Елементом списку зазвичай є запис, який містить, за Крайній мірідва поля (рис. 2.13):
інформаційне;
Покажчик.
Сам список представляється як рис. 2.14.
Кожен елемент списку має покажчикна сусіда. У останнього елемента покажчик – Nil. Елементи списку та покажчики описуються так:
Покажчик = ^ Ел_Списку;(Випереджальний опис)
(допускається тільки в цьому випадку)
Ел_Списку = Record
Інф_ поле: Тип_Інф_поля;
Поле_покажчика: Покажчик; (Цей тип вже визначено вище)
Тип інформаційного елемента – будь-який (скалярний, рядок, масив тощо).
приклад. Тype
Ptr = ^El;
El = Record
Buk: Char;
Ukaz: Ptr;
tuk, PrUk, NUk, Q: Ptr;(Покажчики на елемент списку)
ElSp : El; ( Елемент списку (запис типу El) }
За допомогою списків досить просто видаються черги.
Черга- Це поняття, яке широко використовується в обчислювальній техніці. Список дозволяє моделювати операції додавання елементів у чергу та вибірки з неї.
Основні операції над списками:
1) перехід від одного елемента до іншого (наступного);
2) включення нового елемента до списку;
3) видалення елемента зі списку.
1) Перша операція виконується просто: значення змінної-покажчика, яка зараз вказує на певний елемент, необхідно присвоїти значення, що знаходиться в полі покажчика цього елемента (див. рис. 2.15):
tuk := tuk^. Ukaz
У 
результаті tukстане посиланням на наступний елемент або Nilякщо елемент останній.
2) Вилученняелемента зі списку виконується найбільш просто, якщо є посилання (покажчик) на елемент, попередній що видаляється. При цьому спочатку переносяться посилання, а потім видаляється елемент (звільняється динамічна пам'ять, яку він займає). Посилання на елемент, що видаляється, не повинно губитися, поки він не буде знищений або включений в інший список, інакше з нього вийде "сміття".
Процес видалення елемента, розташованого у списку після елемента, який вказує посилання PrUkілюструється рис. 2.16 а фрагмент відповідної програми може мати вигляд, наведений далі.
{
Запам'ятаємо покажчик на елемент, що видаляється)
tUk:= PrUk^.Ukaz;
(Полю покажчика елемента, що стоїть перед видаленим, привласним)
( значення поля покажчика елемента , що видаляється )
PrUk^.Ukaz:= PrUk^.Ukaz^.Ukaz;
На цьому видаленняелемента з спискузакінчено: зв'язок цього елемента з попереднім розірвано. Але елемент продовжує займати пам'ять і для його фізичного видалення потрібно виконати процедуру:
Dispose (tUk); (Фізично видалили елемент)
Якщо немає необхідності звільняти пам'ять, іноді корисно записати в поле покажчика віддаленого елемента Nil:
tUk^.Ukaz:=Nil.
3
)Увімкненнядо списку елемента, на який є вказівник NUk, після елемента, на який є покажчик PrUkілюструє рис. 2.17. Для виконання цієї операції потрібно задати посилання з елемента, що вставляється на наступний (вона дорівнює посиланню з попереднього елемента на наступний - див. рис. 2.17, а), а потім - змінити посилання з попереднього елемента на вставляється (див. рис. 2.17, б) . Існуючий зв'язок розривається останнім, щоб не втратити елемент.
Фрагмент програми матиме вигляд
New (NUk); (Створили елемент, що вставляється)
Readln (NUk ^. Buk);
