Представление двумерного массива Паскаля в памяти

Элементы абстрактного массива в памяти машины физически располагаются последовательно, согласно описанию. При этом каждый элемент занимает в памяти количество байт, соответствующее его размеру. Например, если массив состоит из элементов типа integer, то каждый элемент будет занимать по два байта. А весь массив займет S^2 байта, где S – количество элементов в массиве.

А сколько места займет массив, состоящий из массивов, т.е. матрица? Очевидно: S i^S j, где S i - количество строк, а S j – количество элементов в каждой строке. Например, для массива типа

Matrix = array [1..3, 1..2] of integer;

потребуется 12 байт памяти.

Как будут располагаться в памяти элементы этого массива? Рассмотрим схему размещения массива M типа matrix в памяти.

Под каждый элемент M [i,j] типа integer выделяется две ячейки памяти. Размещение в памяти осуществляется «снизу вверх». Элементы размещаются в порядке изменения индекса, что соответствует схеме вложенных циклов: сначала размещается первая строка, затем вторая, третья... Внутри строки по порядку идут элементы: первый, второй и т.д.

Как мы знаем, доступ к любой переменной возможен, только если известен адрес ячейки памяти, в которой хранится переменная. Конкретная память выделяется для переменной при загрузке программы, то есть устанавливается взаимное соответствие между переменной и адресом ячейки. Но если мы объявили переменную как массив, то программа «знает» адрес начала массива, то есть первого его элемента. Как же происходит доступ ко всем другим элементам массива? При реальном доступе к ячейке памяти, в которой хранится элемент двумерного массива, система вычисляет ее адрес по формуле:

Addr + SizeElem * Cols *(I -1)+ SizeElem *(J -1),

где Addr – фактический начальный адрес, по которому массив располагается в памяти; I, J – индексы элемента в двумерном массиве; SizeElem – размер элемента массива (например, два байта для элементов типа integer); Cols – количество элементов в строке.

Выражение SizeElem * Cols *(I -1)+ SizeElem *(J -1) называют смещением относительно начала массива.

Сколько памяти выделяется для массива?

Рассмотрим не столько вопрос о том, сколько памяти выделяется под массив (это мы разобрали в предыдущем разделе), а о том, каков максимально допустимый размер массива, учитывая ограниченный объем памяти.

Для работы программы память выделяется сегментами по 64 Кбайт каждый, причем как минимум один из них определяется как сегмент данных. Вот в этом-то сегменте и располагаются те данные, которые будет обрабатывать программа. Ни одна переменная программы не может располагаться более чем в одном сегменте. Поэтому, даже если в сегменте находится только одна переменная, описанная как массив, то она не сможет получить более чем 65536 байт. Но почти наверняка, кроме массива в сегменте данных будут описаны еще некоторые переменные, поэтому реальный объем памяти, который может быть выделен под массив, находится по формуле: 65536- S, где S – объем памяти, уже выделенный под другие переменные.

Зачем нам это знать? Для того чтобы не удивляться, если при компиляции транслятор выдаст сообщение об ошибке объявления слишком длинного массива, когда в программе встретит описание (правильное с точки зрения синтаксиса):

Type myArray= array [1..50000] of integer;

Вы уже знаете, что, учитывая двухбайтовое представление целых чисел, реально можно объявить массив с количеством элементов равным 65536/2 –1=32767. И то лишь в том случае, если других переменных не будет. Двумерные массивы должны иметь еще меньшие границы индексов.

Примеры решения задач с двумерными массивами Паскаля

Задача: Найти произведение ненулевых элементов матрицы.

Решение:

· Для решения данной задачи нам потребуются переменные: матрица, состоящая, например, из целочисленных элементов; P – произведение элементов, отличных от 0; I, J – индексы массива; N, M – количество строк и столбцов в матрице.

· Входными данными являются N, M – их значения введем с клавиатуры; матрица – ввод матрицы оформим в виде процедуры, заполнение матрицы осуществим случайным образом, т.е. с помощью функции random ().

· Выходными данными будет являться значение переменной P (произведение).

· Чтобы проверить правильность выполнения программы, необходимо вывести матрицу на экран, для этого оформим процедуру вывода матрицы.

· Ход решения задачи:

обсудим сначала выполнение основной программы, реализацию процедур обговорим чуть позже:

· введем значения N и M;

· Введем двумерный массив Паскаля, для этого обращаемся к процедуре vvod (a), где а – матрица;

· Напечатаем полученную матрицу, для этого обращаемся к процедуре print (a);

· Присвоим начальное значение переменной P =1;

· Будем последовательно перебирать все строки I от 1-й до N -й, в каждой строке будем перебирать все столбцы J от 1-го до M -го, для каждого элемента матрицы будем проверять условие: если a ij? 0, то произведение P будем домножать на элемент a ij (P = P * a ij);

· Выведем на экран значение произведения ненулевых элементов матрицы – P;

А теперь поговорим о процедурах.

Замечание (это важно!) Параметром процедуры может быть любая переменная предопределенного типа, это означает, что для передачи в процедуру массива в качестве параметра, тип его должен быть описан заранее. Например:

Type
Matrix=array [1..10, 1..10] of integer;
..............................
procedure primer (a: matrix);
..............................

Вернемся теперь к нашим процедурам.

Процедура ввода матрицы называется vvod, параметром процедуры является матрица, причем она должна быть, как результат, передана в основную программу, следовательно, параметр должен передаваться по ссылке. Тогда заголовок нашей процедуры будет выглядеть так:

Procedure vvod (var m: matrix);

Для реализации вложенных циклов в процедуре нам потребуются локальные переменные-счетчики, например, k и h. Алгоритм заполнения матрицы уже обсуждался, поэтому не будем его повторять.

Процедура вывода матрицы на экран называется print, параметром процедуры является матрица, но в этом случае она является входным параметром, следовательно, передается по значению. Заголовок этой процедуры будет выглядеть следующим образом:

Procedure print (m: matrix);

И вновь для реализации вложенных циклов внутри процедуры нам потребуются счетчики, пусть они называются так же – k и h. Алгоритм вывода матрицы на экран был описан выше, воспользуемся этим описанием.

План отладки

№	Проверяется	Исходные данные	Ожидаемый результат	Действительный результат	Ориентировочные причины ошибки
	Ввод размерносты матрицы	2;4.5	Ошибка из-за несовместимости типа данных	Ошибка из-за несовместимости типа данных	Попытка присвоить типу «byte» значение типа «real».
10;-15	Ошибка из-за несовместимости типа данных	Ошибка из-за несовместимости типа данных	Выход за границы диапазона типа byte при вводе.
12;12	12;12	12;12	Ошибка отсутствует.
	Ввод матрицы	1 2 3 4 5 6 7 8 9.2	Ошибка из-за несовместимости типа данных	Ошибка из-за несовместимости типа данных	Попытка присвоить типу «byte» значение типа «real».
-2 8 -10 54 87 -132 54 48 14у	Ошибка из-за несовместимости типа данных	Ошибка из-за несовместимости типа данных	Попытка присвоить типу «byte» значение типа «string».
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	Ошибка отсутствует.
	Нахождение строк матрицы в которых элементы расположены в порядке возрастания	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	Ошибка отсутствует.
1 3 5 1 1 5 7 8 1 1 1 0 2 4 8 9	1 5 7 8 2 4 8 9	1 5 7 8 2 4 8 9	Ошибка отсутствует.
-1 -2 -3 -4 -5 -6 -7 -8 15 -5 -9 -9 -9 -9 -9 -9	-	-	Ошибка отсутствует.
	Количество строк матрицы в которых элементы расположены в порядке возрастания	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16			Ошибка отсутствует.
1 -2 1 1 1 -1 1 1 1 -1 1 0 2 -5 1 1			Ошибка отсутствует.
-1 -2 -3 -4 -5 -6 -7 -8 15 -5 -9 -9 -9 -9 -9 -9			Ошибка отсутствует.

Код модуля

Unit Massiv;

interface

uses crt;

const q=30; w=30;

type Dv_Mas=array [1..Q,1..W] of integer;

type Massive=array [1..Q] of byte;

procedure OutputMas (var Mas:Dv_Mas; var mas2:massive; var n,m,k,l,http:byte);

procedure InputMas (var Mas:Dv_Mas; var n,m:byte);

procedure SizeOfMas(var n,m:byte);

procedure ReadFromATextFile(var Mas:dv_mas; var n,m:byte);

procedure WriteToATextFile(var Mas:dv_mas; Mas2:massive; var n,m,k,l,http:byte);

procedure ReadFromATypedFile(var Mas:dv_mas; var n,m:byte);

procedure WriteATypedFile(var Mas:dv_mas; Mas2:massive; var n,m,k,l,http:byte);

procedure ChoiceTypeOfInputMassiv(var Mas:dv_mas; var n,m:byte; var p:boolean);

procedure ChoiceTypeOfOutputMassiv(var Mas:dv_mas; var Mas2:Massive; var n,m,k,l,http:byte);

procedure FindStringWithOlolo(var mas:Dv_mas; var Mas2:massive; var n,m,http:byte);

implementation

procedure ReadFromATextFile(var Mas:dv_mas; var n,m:byte);

var f:text; i,j:byte;

begin

assign(f,'InputMassiv.txt');

reset(f);

read(f,n,m);

for i:=1 to n do

begin

for j:=1 to m do

read(f,Mas[i,j]);

readln(f);

end;

close(f);

end;

procedure WriteToATextFile(var Mas:dv_mas; Mas2:massive; var n,m,k,l,http:byte);

var f:text; i,j:byte;

begin

assign(f,'OutputMassiv.txt');

rewrite(f);

for i:=1 to n do

begin

for j:=1 to m do

write(f,Mas[i,j]:3);

writeln(f);

end;

writeln(f,'Строки, в которых элементы расположены по возрастанию:');

for i:=1 to http do

writeln(f,Mas2[i]:3);

close(f);

end;

procedure ReadFromATypedFile(var Mas:dv_mas; var n,m:byte);

var i,j:byte; f:file of integer; nn,mm:integer;

begin

assign(f,'InputMassiv');

reset(f);

read(f,nn,mm);

n:=abs(nn);

m:=abs(mm);

for i:=1 to n do

for j:=1 to m do

read(f,Mas[i,j]);

close(f);

end;

procedure WriteATypedFile(var Mas:dv_mas; Mas2:massive; var n,m,k,l,http:byte);

var i,j:byte; f:file of integer; nn,mm:integer;

begin

assign(f,'OutputMassiv');

rewrite(f);

nn:=k;

mm:=l;

write(f,nn,mm);

for i:=1 to http do

write(f,Mas2[http]);

close(f);

end;

procedure SizeOfMas(var n,m:byte);

begin

repeat

clrscr;

write(' Input Number Of String <30: '); readln(n);

until (n<=30) and (n>0);

repeat

clrscr;

write(' Input Number Of String <30: ',n); writeln;

write(' Input Number Of Column <30: '); readln(m);

until (m<=30) and (m>0);

end;

procedure InputMas (var Mas:Dv_Mas; var n,m:byte);

var i,j:byte;

begin

writeln(' Input Mas:');

for i:=1 to N do

for j:= 1 to M do

read(Mas[i,j]);

end;

procedure OutputMas (var Mas:Dv_Mas; var Mas2:massive; var n,m,k,l,http:byte);

var i,j:byte;

begin

writeln(' Massiv:');

for i:=1 to N do

begin

for j:= 1 to M do

write(Mas[i,j]:3);

writeln;

end;

writeln;

writeln('Строки, в которых элементы расположены по возрастанию:');

for i:=1 to http do

write(Mas2[i],' ');

writeln;

writeln;

end;

procedure ChoiceTypeOfInputMassiv(var Mas:dv_mas; var n,m:byte; var p:boolean);

var q:byte;

begin

p:=false;

repeat

writeln('1 - InputFromTheKeyboard');

writeln('2 - InputFromATextFile');

writeln('3 - InputFromATypedFile');

writeln('4 - Exit');

write('ChoiceTypeOfInputMassiv:');

readln(q);

until (q=3)or(q=2) or (q=1) or (q=4) or (q=5);

case q of

1: begin SizeOfMas(n,m); InputMas(Mas,n,m); end;

2:ReadFromATextFile(Mas,n,m);

3:ReadFromATypedFile(Mas,n,m);

4:p:=true;

end;

end;

procedure ChoiceTypeOfOutputMassiv(var Mas:dv_mas; var Mas2:massive; var n,m,k,l,http:byte);

var q:byte;

begin

writeln('1 - OutputOnTheDisplay');

writeln('2 - OutputInTheTextFile');

writeln('3 - BringInATypedFile');

write('ChoiceTypeOfInputMassiv:');

readln(q);

case q of

1:Outputmas(Mas,Mas2,n,m,k,l,http);

2:WriteToATextFile(Mas,Mas2,n,m,k,l,http);

3:WriteATypedFile(Mas,Mas2,n,m,k,l,http);

end;

end;

procedure FindStringWithOlolo(var mas:Dv_mas; var Mas2:massive; var n,m,http:byte);

var j,i:byte; bool:boolean; ad:integer;

begin

clrscr;

http:=0;

for i:=1 to n do

begin

j:=1;

Ad:=Mas[i,1];

Bool:=true;

while (bool) and (j<m) do

begin

if ad<mas[i,j+1] then

begin

ad:=mas[i,j+1];

end;

else bool:=false;

j:=j+1;

end;

if bool then begin http:=http+1; Mas2[http]:=i; end;

end;

writeln;

end;

end.

 

Код програми

uses crt,massiv;

var Mas:dv_mas; n,m,k,l:byte; p:boolean; Mas2:massive; http:byte;

begin

repeat

ChoiceTypeOfInputMassiv(Mas,n,m,p);

if not(p) then

begin

FindStringWithOlolo(Mas,Mas2,n,m,http);

ChoiceTypeOfOutputMassiv(Mas,Mas2,n,m,k,l,http);

end;

until p;

end.

 

 

Вывод: на данной лабораторной работе приобретались навыки работы с типом данных матрицы и усовершенствовались навыки разработки алгоритмов и отладки программ на примере решения задания, которое определяет количество строк матрицы в которых элементы расположены в порядке возрастания. Также был создан план отладки, где возникали такие ошибки как несовместимость типов, выход за границы диапазона и т.д.