Модуль для работы с динамическими массивами
Автор:
Разместил: Amro   Дата: 2006-06-01 21:42
Комментарии: (0)   Рейтинг:
Пока комментариев нет

Материал подготовил(и): Altair

Модуль для работы с динамическими массивами.
Модуль позволяет работать с массивами с динамической длинной

Constructor INIT;
Инициализирует массив. Требуется запустить лишь один раз - в начале работы с массивом, но после определения начальной длины

Procedure SetSizeArray(_Size:word);
Устанавливает длинну массива равную _Size. При первом запуске, после нее требуется запустить конструктор.

Function GetSizeArray:Word;
Возвращает текущую длинну массива. Лучше использовать ее и не открывать доступ к переменной sizeofarray, т.к. последствия могут быть непредсказуемые.

Procedure EnteringArray(visible:Byte;VideoMode:Byte);
Процедура ввода массива.
Не очень надежна, т.к. нет поддержки backspace, но зато возможен ввод в графическом режиме и возможно управлять отображением вводимых чисел. (Для вывода, скажем звездочек вместо вводимых символов, ставим параметр visible=<код звездочки>
Videomode может иметь RText или RGraph - соответственно ввод в текстовом и ввод в графическом режиме.
Внимание: если тип режима указан неверно, произойдет ошибка периода исполнения.

Procedure PrintCRTarray(Videomode:byte);
Вывод на экран массива. Возможны 2 режима как и у метода для ввода массива.

Procedure QSort(left,right:integer);
Быстрая сортировка массива.

Procedure HSort;
Пирамидальная сортировка массива. Полезна если вы уверены что массив почти или полностью отсортирован.

Function GetMaxElem:Telem;
Возвращает максимальный элемент массива.

Function GetMinElem:Telem;
Возвращает мимнимальный элемент массива.

Function GetNumMaxElem:Word;
Возвращает номер максимального элемента в массиве. (Первого, если таких элементов несколько)

Function GetNumMinElem:Word;
Возвращает номер минимального элемента.

Function ElemInArray(T:Telem):Word;
Проверяет вхождение элемента в массив. 0 - если не найдено, иначе индекс элемента.

Procedure InvertArray;
Инвертирует массив.

Вот программа демонстрирующая возможности модуля.
Код
Program TEST_UNIT_ARRAYS;
Uses CRT,Arrays;
var
a:TArrayWork;
i,c:integer;
dlinna:word;
poisk:Telem;
begin
CLRSCR;
Writeln('Введите длинну:');
readln(dlinna);
a.SetSizeArray(dlinna);
a.Init; {теперь можно работать}
writeln;
a.EnteringArray(RealkeyV,RText);
writeln('Введенный массив:');
A.PrintCRTArray(RText);
writeln;
a.hsort;
writeln('Отсортированный массив:');
a.printcrtarray(RText);
writeln; writeln('Инвертированный:');
a.InvertArray;
a.printcrtarray(rtext);
writeln;
writeln('максимальный элемент: ',a.GetMaxElem);
Writeln('минимальный элемент: ',a.GetMinElem);
writeln('Номер Макс. элемента: ',a.getnummaxelem);
writeln('номер минимального элемента :',a.getnumminelem);
write('введите искомый элемент: '); readln(Poisk);
if a.eleminarray(poisk)=0 then
writeln('не найден!') else
Writeln('номер искомого элемента: ',a.eleminarray(poisk));

write('Введите новую длинну: ');readln(dlinna);
If dlinna<=a.GetSizeArray then a.SetSizeArray(dlinna) else
begin
a.setsizearray(dlinna);
{a.init;}
end;
writeln('Элементы массива: ');
a.printcrtarray(rtext);
readln(a.arr^[dlinna-1]);
a.printcrtarray(rtext);
end.

В присоединенном файле сам модуль. (исходник).

ЗЫ: при реализации динамического массива, использовался алгоритм, предложенный volvo

Материал подготовил(и): volvo

Работа с динамическими массивами
Для того, чтобы работать с динамическими массивами, необходимо перед началом работы выделить память под такой массив, а после использования массива - освободить выделенную память:
[PASCODE]{
Обязательно отключить проверку индексов,
иначе возникнет ошибка времени исполнения
}
{$R-}
Type
TType = Integer; { Или любой другой тип }

{ Указатель на динамический массив }
PDynArray = ^TDynArray;
TDynArray = array[1 .. 1] 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.[/PASCODE]


Еще один модуль для работы с динамическими массивами (ООП).
Модуль позволяет работать с массивами с переменной длиной (допускается создание массивов, использующих любые типы данных - встроенные типы Паскаля, перечисления и записи - в качестве базового типа).
Дополнительная информация


Использование процедур и функций модуля:
  • 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.


Исходники модуля вместе с текстовой программой:
[attachmentid=1632] Скачать: [attachmentid=1630]

Данный модуль можно адаптировать для работы с любым встроеннымтипом данных Турбо Паскаля. Все, что потребуется изменить - это:
  1. Код
    Type TType = Integer; { изменить на название другого типа}
    
    и
  2. Код
    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;
Для работы с пользовательскими типами можно использовать вот этот модуль, (который несколько отличается от приведенного выше):
[attachmentid=1633] Скачать: [attachmentid=1631]
  1. В нем содержатся тип и функция сравнения переменных пользовательского типа (т.к. основной сложностью и является то, что для типов, НЕопределенных в языке отсутствуют операции сравнения):
    Код
    { Допустим, тип пользователя выглядит так: }
    Type
    TRec = Record
    X, Y: Integer;
    End;

    Type
    {
    Определяем, каким может быть результат сравнения
    двух переменных такого типа:
    }
    cmType = (cmLow, cmEqual, cmHigh);

    const { Для удобства дальнейшей работы }
    cmLowEq = [cmLow, cmEqual];
    cmHighEq = [cmHigh, cmEqual];
    {
    И сама функция сравнения, которая возвращает:
    cmHigh (A > B), cmLow (A < B) и cmEqual (A = B)
    }
    Function _compare_(a, b: TType): cmtype;
    (*
    Пример функции для типа TRec (допустим, что нужно
    сравнить записи только по значению первого поля)
    *)
    begin
    _compare_ := cmEqual;
    if a.X > b.X then _compare_ := cmHigh
    else if a.X < b.X then _compare_ := cmLow
    end;
  2. ВСЕ операции сравнения, в которых участвуют переменные типа TType заменены на вызовы функции _compare_, т.е.
    Код
    If arr^[i] > arr^[max_ix] ...
    { Заменено на: }
    If _compare_(arr^[i], arr^[max_ix]) = cmHigh ...

    (* также как *)
    While (arr^[l] <= B) ...
    { заменено на: }
    While (_compare_(arr^[l], B) In cmLowEq) ...
  3. Ну и , естественно, при смене типа TType не забываем изменять процедуры _print_ и _input_, как и для модуля, приведенного выше...


Материал подготовил(и): volvo

Работа с динамическими матрицами
Для того, чтобы работать с динамическими матрицами, проще всего представить матрицу, как массив векторов (массив, содержащий указатели на строки матрицы). Перед началом работы с такой матрицей нужно сначала выделить память под массив указателей на строки, и только потом выделять память для хранения самих данных. После использования матрицы выделенная память освобождается в обратной последовательности:

[PASCODE]{
Обязательно отключить проверку индексов,
иначе возникнет ошибка времени исполнения
}
{$R-}
Type
TType = Word; { Или любой другой тип }
Type
PVector = ^TVector;
{ Это - одна "строка" динамической матрицы }
TVector = Array[1 .. 1] of TType;

PDynMatrix = ^TDynMatrix;
{ Сама матрица - представляется как массив указателей на "строки" }
TDynMatrix = Array[1 .. 1] 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.[/PASCODE]

Модуль для работы с динамическими матрицами

В этом модуле для работы с матрицами вводится тип:
CODE

Type
 TType = Double;
 PTRows = ^TRows;
 TRows = Array[1 .. (2 * maxInt) Div SizeOf(TType)] Of TType;

 PTCol = ^TCol;
 TCol = Array[1 .. (2 * maxInt) Div SizeOf(PTRows)] Of PTRows;

 PTMatrix = ^TMatrix;
 TMatrix =
   Record
     nRow, nCol: Integer;
     matrix: PTCol;
   End;


При таком представлении матрицы к каждому ее элементу нельзя обращаться как к элементу обычного двумерного массива (т.е. так: arr[i, j] := 0). Для того, чтобы работать с TMatrix нужно изменить вызов на: arr.matrix^[i]^[j] := 0.
Поля nRow, nCol содержат количество строк и столбцов соответственно.

Прилагаемый модуль содержит основные функции для работы с матрицами:

Function mxO(size: Integer): PTMatrix;
Создание в динамической памяти "нулевой" матрицы, т.е. такой, что:
A+O = O+A = A

Function mxE(size: Integer): PTMatrix;
Создание в динамической памяти "единичной" матрицы (элементы главной диагонали равны единице, все остальные - нули), т.е. такой, что:
A*E = E*A = A

Function mxCreate(pRows, pCols: Integer): PTMatrix;
Функция возвращает указатель на созданную в динамической памяти матрицу (или nil при невозможности выделения памяти)

Procedure mxDispose(Var p: PTMatrix);
Процедура освобождает динамическую память, занятую матрицей p^, и устанавливает значение p в nil.

Procedure mxInput(Var a: TMatrix);
Процедура поэлементно вводит с клавиатуры матрицу, переданную ей в качестве параметра.

Procedure mxPrint(a: TMatrix);
Процедура выводит на экран матрицу, переданную ей в качестве параметра.

Function matrixAdd(a, b: TMatrix): PTMatrix;
Функция возвращает указатель на созданную в динамической памяти матрицу, являющуюся суммой матриц a и b, передаваемых как параметры (или nil при невозможности выделения памяти или при несоответствии размеров матриц A и B)
Function matrixSub(a, b: TMatrix): PTMatrix;
Функция аналогична matrixAdd, но возвращает разность матриц A и B

Function matrixMult(a, b: TMatrix): PTMatrix;
Функция возвращает указатель на созданную в динамической памяти матрицу, являющуюся произведением матриц a и b, передаваемых как параметры (или nil при невозможности выделения памяти или если матрицы a и b не являются "сцепленными", т.е. число столбцов A не равно числу строк B)

Function matrixScale(a: TMatrix; f: Double): PTMatrix;
Функция возвращает указатель на созданную в динамической памяти матрицу, являющуюся произведением матрицы A на число f (или nil при невозможности выделения памяти)

Function matrixDet(a: TMatrix): Double;
Возвращает значение определителя квадратной матрицы A (при передаче матрицы, не являющейся квадратной, функция вернет 0)

Function matrixEqual(a, b: TMatrix): Boolean;
Функция поэлементного сравнения матриц. Если матрицы имеют разный размер или не эквивалентны, функция возвращает False.

Function matrixTranspose(a: TMatrix): PTMatrix;
Функция возвращает указатель на созданную в динамической памяти матрицу, являющуюся транспонированной матрицей A, т.е. строки исходной матрицы становятся столбцами и наоборот (или nil при невозможности выделения памяти)

Function matrixInvert(a: TMatrix; Var multBy: Double): PTMatrix;
Функция возвращает указатель на созданную в динамической памяти матрицу, являющуюся инверсной (обратной) по отношению к A, то есть матрицей, результатом умножения которой на A является единичная матрица (или nil при невозможности выделения памяти).
(В переменной multBy возвращается значение 1/det(A))

Пример использования модуля:

CODE

Uses crt, matrixUnit;

Const
 size = 3;

Var
 mxCheck, mxA, invA: PTMatrix;
 mx1, mx2: PTMatrix;

 i, j: integer;
 ToMult: Double;
Begin
 clrscr;
 { Проверка умножения матриц }
 mx1 := mxCreate(2, 3);
 mxInput(mx1^); mxPrint(mx1^);
 mx2 := mxCreate(3, 3);
 mxInput(mx2^); mxPrint(mx2^);

 mxCheck := matrixMult(mx1^, mx2^);
 mxPrint(mxCheck^);

 { Проверка создания обратной матрицы }
 mxA := mxCreate(size, size);
 mxInput(mxA^); mxPrint(mxA^);

 invA := matrixInvert(mxA^, ToMult);
 WriteLn(ToMult:5:2);
 mxPrint(invA^);

 { Не забываем освобождать память }
 mxDispose(invA);
 mxDispose(mxA);
 mxDispose(mxCheck);

 mxDispose(mx2);
 mxDispose(mx1)
End.

Материал взят с сайта Всё о Паскале