Динамические массивы и матрицы |
|
|
Реализация динамических массивов / матриц |
|
Модули для работы с динамическими массивами: №1 |
|
Модули для работы с динамическими матрицами: №1 |
|
|
|
Реализация динамических массивов
Для того, чтобы работать с динамическими массивами, необходимо перед началом работы выделить память
под такой массив, а после использования массива - освободить выделенную память:Type
TType = Integer; { Или любой другой тип }
{ Указатель на динамический массив }
PDynArray = ^TDynArray;
TDynArray = array[1 .. maxint div sizeof(TType)] of TType;
Var
{ Через эту переменную будет осуществляться вся работа с массивом }
arr: PDynArray;
n, i: integer;
Begin
Write('n = '); ReadLn(n); { Вводится размер массива }
{
В "куче" запрашивается блок памяти с размером,
достаточным для хранения N элементов типа TType
}
GetMem(arr, n * SizeOf(TType));
(*** Начало работы с массивом ***)
{
Обращение к элементу динамического массива - почти такое же,
как и к элементу обычного (статического) массива,
за исключением операции "^" - разыменования ...
Пример:
}
For i := 1 To n Do arr^[i] := 2 * i;
For i := 1 To n Do
Write(arr^[i]:4);
(*** Закончили работу с массивом - уничтожаем его ***)
{ Возвращаем память назад в "кучу" }
FreeMem(arr, n * SizeOf(TType));
End.
Реализация динамических матриц
Для того, чтобы работать с динамическими матрицами, проще всего представить матрицу, как массив векторов
(массив, содержащий указатели на строки матрицы). Перед началом работы с такой матрицей нужно сначала выделить
память под массив указателей на строки, и только потом выделять память для хранения самих данных. После
использования матрицы выделенная память освобождается в обратной последовательности:Type
TType = Word; { Или любой другой тип }
Type
PVector = ^TVector;
{ Это - одна "строка" динамической матрицы }
TVector = Array[1 .. maxint div sizeof(TType)] of TType;
PDynMatrix = ^TDynMatrix;
{ Сама матрица - представляется как массив указателей на "строки" }
TDynMatrix = Array[1 .. maxint div sizeof(PVector)] of PVector;
Var
{ Через эту переменную будет осуществляться вся работа с матрицей }
mxDynamic: PDynMatrix;
n, i, j: Word;
Begin
Write('n = '); ReadLn(n);
{ Выделяем память под указатели на "строки" }
GetMem(mxDynamic, n * SizeOf(PVector));
{ И для каждой "строки" - выделяем память для хранения данных }
For i := 1 To n Do
GetMem(mxDynamic^[i], n * SizeOf(TType));
(*** Работаем с матрицей ***)
{
Динамическая матрица представлена немного иначе,
чем динамический массив, поэтому для того, чтобы обратиться
к ее элементу, необходимы 2 операции разыменования указателей.
Пример:
}
For i := 1 To n Do { Строки }
For j := 1 To n Do { Столбцы (элементы строки) }
mxDynamic^[I]^[J]:=I*J;
For i := 1 To n Do Begin
WriteLn;
For j := 1 To n Do
Write(mxDynamic^[I]^[J]:4);
End;
(*** Закончили работу с матрицей - уничтожаем ее ***)
{ Освобождаем память в обратном порядке: }
{ Сначала - удаляем все "строки" }
For i := 1 To n Do
FreeMem(mxDynamic^[i], n * SizeOf(TType));
{ А теперь и указатели на них ... }
FreeMem(mxDynamic, n * SizeOf(PVector));
End.
Модуль для работы с дин. массивом
ООП-реализация.
Модуль позволяет работать с массивами с переменной длиной (допускается создание массивов, использующих любые
типы данных - встроенные типы Паскаля, перечисления и записи - в качестве базового типа).
Использование процедур и функций модуля:
- Constructor Init(sz: Word);
Инициализирует массив. Требуется запустить его лишь один раз - в начале работы с массивом.
- Destructor Done;
Удаляет массив. Вызывается по окончании работы с массивом для освобождения динамической памяти.
- Procedure Resize(sz: Word);
Процедура для увеличения размера массива (новый размер определяется значением sz).
Если sz меньше текущей длины массива, размер меняться не будет. После изменения размера все
предыдущие значения остаются на своих местах, новые - заполняются нулями.
- Function GetSize: Word;
Возвращает текущую длину массива. Используется для упрятывания переменной SizeOfArray, т.к.
последствия доступа к SizeOfArray напрямую могут быть непредсказуемые.
- Function Get(i: Word): PTType;
Функция, возвращающая адрес i-го элемента массива.
Если значение i больше максимальной длины массива, возвращается nil.
- Procedure Put(i: Word; T: TType);
Процедура для записи элемента T в i-ю позицию массива.
Если значение i больше максимальной длины массива, никаких действий не производится.
- Function Input(n: Integer; s: String): Integer;
Процедура ввода первых N элементов массива. S - имя текстового файла, из которого нужно прочитать эти элементы.
Для ввода с клавиатуры пользуемся std_in. Функция возвращает (-1) если файла с указанным именем не существует.
- Function Print(s: String): Integer;
Функция выводит массив в текстовый файл. S - имя файла, в который будет осуществляться вывод.
Для вывода на экран пользуемся std_out. Функция возвращает (-1) если не может создать файл с указанным именем.
- Procedure qSort(Left,Right:integer);
Быстрая сортировка массива.
- Procedure hSort;
Пирамидальная сортировка массива. Полезна если Вы уверены что массив почти или полностью отсортирован.
- Function max: PTType;
Возвращает указатель на максимальный элемент массива.
- Function min: PTType;
Возвращает указатель на минимальный элемент массива.
- Function maxIndex: Word;
Возвращает индекс максимального элемента в массиве.
(Если элементов с таким значением несколько - возвращается первый из них)
- Function minIndex: Word;
Возвращает индекс минимального элемента в массиве.
(Если элементов с таким значением несколько - возвращается первый из них)
- Function IndexOf(T: TType): Word;
Проверяет вхождение элемента T в массив. Возвращает 0, если элемент не был найден, иначе возвращается индекс элемента.
- Procedure Invert;
Инвертирует массив.
- Function Concat(Var a: TArray): Boolean;
Используется для "слияния" двух динамических массивов. Возвращает True в случае успеха. Иначе - False.
Внимание !!! При успешном завершении Concat массив,
передаваемый как параметр А удаляется.
Ниже приведена программа, демонстрирующая основные возможности модуля.Program TestArray;
Uses CRT, DynArr;
Var
inArr, secondArr: TArray;
begin
ClrScr;
inArr.Init(6);
WriteLn('Enter 6 Integers');
inArr.Input(6, StdIn);
inArr.Print(StdOut);
inArr.hSort;
inArr.Print(StdOut);
secondArr.Init(8);
WriteLn('Enter 8 Integers');
secondArr.Input(8, StdIn);
secondArr.Concat(inArr);
secondArr.Print(StdOut);
secondArr.hSort;
secondArr.Print(StdOut);
secondArr.Done;
end.
Исходники модуля вместе с текстовой программой: Array.rar
Данный модуль можно адаптировать для работы с любым встроенным типом данных Турбо Паскаля.
Все, что потребуется изменить - это:
Type TType = Integer; { изменить на название другого типа}
Procedure _print_(Var f: Text; Var T: TType);
{
Изменить на процедуру, выводящую переменную
заданного типа в текстовый фаил
}
Begin
Write(f, T)
End;
Procedure _input_(Var f: Text; Var T: TType);
{
Изменить на процедуру, вводящую переменную
заданного типа из текстового файла
}
Begin
ReadLn(f, T)
End;
Модуль для работы с дин. матрицей
ООП-реализация.
Реализация этого модуля гораздо сложнее, чем реализация Объектно-Ориентированного модуля, приведенного здесь:
Работа с динамическими матрицами.
Это связано с тем, что в данном модуле каждая строка матрицы представляет собой объект, над которым можно производить
те или иные операции.
Например,
Для достижения такой функциональности в модуле вводятся типы:Type
arrTType =
Array[1 .. maxint div SizeOf(TType)] Of TType;
PTVc_arr = ^TVc_arr;
TVc_arr = arrTType;
PTVector = ^TVector;
TVector = Object
size: Word; { размер строки матрицы }
{ ... методы объекта }
Private
vc: PTVc_arr; { указатель на собственно элементы строки }
{ ... методы объекта }
End;
PTmx_arr = ^Tmx_arr;
Tmx_arr =
Array[1 .. maxInt div SizeOf(PTVector)] Of PTVector;
Tmatrix = Object
num_rows: Word; { количество строк матрицы }
{ ... методы объекта }
Private
mx: PTmx_arr; { указатель на массив строк }
{ ... методы объекта }
End;
Для работы со строками матрицы в объекте TVector присутствуют следующие методы:
- Constructor copy_arr(Var arr: Array Of TType; Const sz: Word);
Создание строки из sz элементов и ее инициализация элементами массива arr
- Constructor zero(sz: Word);
Создание строки из sz элементов и ее инициализация нулями
- Constructor copy(Var vect: TVector);
Создание новой строки матрицы путем полного копирования уже существующей строки vect
- Constructor value(sz: Word; t: TType);
Создание новой строки из sz элементов и заполнение всех их значением T
- Destructor done;
Удаление строки матрицы
- Function get(i: Word): PTType;
Функция возвращает указатель на i-ый элемент строки
- Procedure put(i: Word; t: TType);
Устанавливает i-ый элемент строки равным T
- Procedure print(Var os: Text);
Распечатывает содержимое строки в файл, дескриптор которого os передается в качестве параметра процедуры
- Procedure sort(style: sorting; dir: direction);
Процедура сортировки строки матрицы методом style (bubble_sort, quick_sort или heap_sort) в порядке,
задаваемом параметром dir (dir_ascend или dir_descend)
- Procedure allocate(sz: Word);
Приватный метод, реализующий собственно выделение памяти под строку, и заполняющий поле size объекта...
Переходим к описанию методов объекта TMatrix:
- Constructor zero(n_rows, n_cols: Word);
Создание матрицы из n_rows строк и n_cols столбцов и ее инициализация нулями
- Constructor copy(Var mtrx: Tmatrix);
Создание новой матрицы путем полного копирования уже существующей mtrx
- Constructor init(n_rows, n_cols: Word; t: TType);
Создание матрицы из n_rows строк и n_cols столбцов и ее инициализация значением T
- Constructor duplicate(n_rows: Word; Var vect: tvector);
Создание матрицы из n_rows строк и заполнение каждой строки копией вектора vect
- Constructor mxO(sz: Word);
Создание "нулевой" квадратной матрицы порядка sz
- Constructor mxE(sz: Word);
Создание "единичной" квадратной матрицы порядка sz
- Constructor mxTriUp(sz: Word);
Создание и обнуление "верхнетреугольной" квадратной матрицы порядка sz
- Constructor mxTriDn(sz: Word);
Создание и обнуление "нижнетреугольной" квадратной матрицы порядка sz
- Destructor done;
Удаление матрицы
- Function get_row_count: Word;
Эта функция возвращает количество строк в матрице, и используется для сокрытия переменной num_rows
- Function get_vector(i: Word): PTVector;
Функция, возвращающая указатель на i-ую строку матрицы
- Procedure print(Var os: Text);
Распечатывает содержимое матрицы в файл, дескриптор которого os передается в качестве параметра процедуры
- Procedure allocate(sz: Word);
Приватный метод, реализующий собственно выделение памяти под матрицу, и заполняющий поле num_rows объекта...
Для удобства использования все процедуры, связанные с сортировкой, вынесены в отдельный файл...
Несколько примеров использования модуля динамических матриц:
const
my_vals: array[1 .. 7] of ttype =
(7, 6, 5, 4, 3, 2, 1);
var
std_out: text;
m: tmatrix;
tv: tvector;
begin
assigncrt(std_out); { Связываем файл std_out с консолью ... }
rewrite(std_out); { ... и подготавливаем его для записи }
tv.copy_arr(my_vals, 7); { Создаем вектор, содержащий значения из массива my_vals }
m.duplicate(5, tv); { Создаем матрицу из 5 строк, все они будут одинаковыми }
m.print(std_out); { Распечатываем матрицу }
m.get_vector(1)^.sort(heap_sort, dir_ascend); { Первую строку матрицы отсортировать по возрастанию }
m.print(std_out); { Распечатываем матрицу }
m.get_vector(1)^.sort(heap_sort, dir_descend); { Первую строку матрицы отсортировать по убыванию }
m.print(std_out); { Распечатываем матрицу }
m.done; { Удаляем матрицу }
close(std_out); { Закрываем файл... }
end.
Вышеприведенный код выдает такой разультат:mx <5>
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
mx <5>
vec < 7> 1 2 3 4 5 6 7
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
mx <5>
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
vec < 7> 7 6 5 4 3 2 1
var
std_out: text;
m: tmatrix;
begin
assigncrt(std_out);
rewrite(std_out);
m.mxE(5); { Создаем "единичную" матрицу 5 x 5 ... }
m.print(std_out); { ... и распечатываем ее }
m.done;
close(std_out);
end.
Результат работы:mx <5>
vec < 5> 1 0 0 0 0
vec < 5> 0 1 0 0 0
vec < 5> 0 0 1 0 0
vec < 5> 0 0 0 1 0
vec < 5> 0 0 0 0 1
var
std_out: text;
m: tmatrix;
begin
assigncrt(std_out);
rewrite(std_out);
m.mxTriUp(6); { Создаем "верхнетреугольную" матрицу размерностью 6 ... }
m.print(std_out); { ... и распечатываем ее }
m.done;
close(std_out);
end.
Результат работы:mx <6>
vec < 6> 0 0 0 0 0 0
vec < 5> 0 0 0 0 0
vec < 4> 0 0 0 0
vec < 3> 0 0 0
vec < 2> 0 0
vec < 1> 0
Исходники программы: Dyna.rar