Процедуры и функции для работы с динамической памятью

Приведем краткие сведения о процедурах и функциях. которые могут пригодиться при использовании динамической памяти.

2.5.1. Функция Addr.Возвращает адрес переменной, процедуры или функции, указанной в качестве параметра. Заголовок функции:

Function Addr(x) : Pointer;

Здесь X – идентификатор переменной, процедуры или функции. Функция возвращает нетипизированный указатель, ссылающийся на X. Поскольку он принадлежит типу Pointer, результат, возвращаемый функциейAddr, совместим со всеми типами указателей.

Вот пример программы, в которой используется функция Addr:

program PAddr;

type

b=char;

var

vb:b ;

pvb:Pointer ;

begin

pvb :=addr(vb);

if pvb=addr(vb) then WriteLn('равно')

else Write ('не равно')

end.

Вместо функции Addr возможно использование оператора @. Так, вместо оператора pvb:=addr(vb) в программе выше можно использовать его эквивалент pvb:=@vb.

2.5.2. Процедура Dispose.Освобождает место, занятое в памяти динамической переменной, на которую ссылается типизированный указатель. Вот как выглядит заголовок этой процедуры:

Procedure Dispose(Var P : Pointer[, Destructor ]);

где P – типизированный указатель.

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

Dispose(P, Done);

После обращения к процедуре Dispose, значение указателя Р становится неопределенным. Поэтому повторное обращение к этой процедуре с Р в качестве параметра приведет к ошибке периода исполнения.

2.5.3. Процедура FreeMem.Освобождает память, занятую динамической переменной данного размера, зарезервированную за нетипизированным указателем (с помощью процедуры GetMem). Вот как выглядит заголовок этой процедуры:

Procedure FreeMem(Var p : Pointer; Size : Word);

Здесь Р – нетипизированный указатель, для которого раньше была выделена память (процедурой GetMem);

Size – выражение, определяющее размер освобождаемой динамической переменной в байтах. Это значение должно совпадать с числом байтов, выделенных для этой переменной процедурой GetMem.

Процедура FreeMem ликвидирует переменную, на которую ссылается указатель Р, и освобождает память, занимаемую этой переменной. После обращения к FreeMem значение указателя Р становится неопределенным и при повторном обращении к FreeMem имеет место ошибка времени исполнения. Ошибка также будет иметь место при попытке сослаться на P^.

2.5.4. Процедура GetMem. Создает динамическую переменную определенного размера, на которую ссылается нетипизированный указатель. Вот как выглядит заголовок этой процедуры:

Procedure GetMem (Var Р : Pointer; Size : Word);

Самый большой блок, который может быть зарезервирован за один раз, равен 65 520 байт. Если в куче для размещения динамической переменной недостаточно свободного пространства, имеет место ошибка времени исполнения.

Вот пример программы (собственно, это только схема программы), в которой используются процедуры FreeMem и GetMem, а также функция SizeOf:

program GetFreeMem;

type

ar =array[1..10] of integer;

var

P : Pointer;

begin

GetMem(p, SizeOf(ar)); {Выделение памяти}

{...}

{Использование памяти}

{ ...}

FreeMem(P, SizeOf(ar)); {Освобождение памяти}

end .

Использованная здесь функция SizeOf возвращает число байтов, занимаемых объектом, указанным в качестве параметра функции.

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

Procedure Mark(Var p : Pointer);

где Р – нетипизированный указатель.

Процедура Mark часто используется совместно с процедурой Release и не должна использоваться с процедурой FreeMem или Dispose.

2.5.6. Функция MaxAvail.Возвращает размер самого большого непрерывного свободного участка в куче. Возвращаемый функцией результат представляет собой значение, принадлежащее типу LongInt. Заголовок функции:

Function MaxAvail : Longint;

2.5.7. Функция MemAvail.Возвращает количество всей свободной памяти в куче. Свободная память обычно представляет собой не единый блок, а множество разрозненных участков, что объясняется фрагментацией кучи. Возвращаемый функцией результат представляет собой значение типа Longint. Заголовок функции:

Function MemAvail : Longint;

Программа, в которой используются функции MemAvail и MaxAvail, a также функция SizeOf , содержится в примере 2.

Пример 2

program Mem_Max_Avail;

type

ar =array[1..10] of integer;

var

p : Pointer;

begin

writeln('Свободная память= ', memavail,

'; наибольший участок= ', maxavail);

GetMem(p , SizeOf(ar));

writeln('Свободная память= ', memavail,

'; наибольший участок= ', maxavail);

end .

Здесь на экран выводятся сведения об общем объеме свободной динамической памяти и наибольшем свободном участке. Соответствующие значения возвращаются функциями MemAvail и MaxAvail до и после выделения памяти (процедурой GetMem). Можно поэкспериментировать – попробовать изменять количество элементов в массиве AR (ar=array[ 1.. 10 ] of integer) или тип элементов (Integer на иной), чтобы выяснить, как это влияет на объем свободной памяти.

Использованная здесь функция SizeOf возвращает число байтов занимаемых, объектом, указанным в качестве параметра функции.

2.5.8. Процедура New. Создает новую динамическую переменную, на которую ссылается типизированный указатель. Вот как выглядит заголовок этой процедуры:

Procedure New(Var P : Pointer [, Init : Constructor ]);

где P – типизированный указатель.

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

New(p , Init(420, 252));

где Init(420, 252) – метод-конструктор, задающий для объекта некоторые начальные значения (т. е. выполняющий его инициализацию).

Процедура New может также вызываться как функция, возвращающая значение указателя. При этом параметр функции представляет собой не указатель, а тип указателя на объект. Например:

type

Pchar=^char ; {объявление типа указателя}

var

p:PChar ; {объявление указателя}

begin

p:=New(PChar);{вызов New как функции}

…

end .

При использовании New в виде функции, как и при традиционном использовании этой процедуры, можно указывать второй параметр, представляющий собой конструктор объектного типа.

Программа, в которой используются процедуры New и Dispose, a также функция MemAvail, содержится в примере 3.

Пример 3

Program New_Disp;

type

ar = array[1..10] of integer;

var

P : ^ar;

begin

writeln ;

writeln('Свободно (до выделения памяти) ', memavail,' байт');

New(p);

writeln('Свободно (после выделения памяти) ', memavail,

'байт');

Dispose(p);

writeln('Свободно (после освобождения памяти) ', memavail,

'байт');

end .

Здесь на экран выводятся сведения об общем объеме свободной динамической памяти, возвращаемые функцией MemAvail до и после выделения памяти (процедурой New), а также после освобождения памяти (процедурой Dispose).

2.5.9. Процедура Release.Освобождает часть кучи. Заголовок процедуры:

Procedure Release(Var p : Pointer);

где P – указатель любого типа, ранее определенный процедурой Mark.

При обращении к процедуре Release освобождается часть кучи от адреса, на который указывает Р, до конца кучи.

Программа, в которой используются процедуры Mark , Release, New, a также функция MemAvail , содержится в примере 4.

Пример 4

program MarkRelease;

var

p1, p2 : ^Real;

p3, p4 : ^Integer;

begin

WriteLn ;

WriteLn('Свободно (до выделения памяти) ',

MemAvail,' байт');

New(p1); {Выделяем память для р1}

New(p2); {Выделяем память для p2}

Mark(p2);{Сохраняем состояние кучи}

WriteLn('Свободно (после первого выделения памяти)',

MemAvail,' байт');

New(p3); {Выделяем память для р3}

New(p4); {Выделяем память для р4}

WriteLn('Свободно (после второго выделения памяти)',

MemAvail ,' байт');

Release(p2);

WriteLn('Свободно (после освобождения памяти) ',

MemAvail,' байт');

End .

В этой программе сначала выделяется память для двух переменных типа Real, затем запоминается текущий адрес начала свободного участка динамической памяти (с помощью процедуры Mark), после этого снова выделяется память – на этот раз для двух переменных типа Integer, наконец память освобождается (с помощью процедуры Release) от адреса, запомненного с помощью процедуры Mark, и до конца кучи. Во всех ключевых точках программы на экран выводится информация о количестве свободной динамической памяти. Программа демонстрирует, что память, занятая переменными Р3 и Р4 при этом освобождается, а переменные Р1 и P2 по-прежнему могут использоваться.

2.5.10. Функция SizeOf. Возвращает число байтов, занимаемых объектом, указанным в качестве параметра функции. Заголовок функции:

Function SizeOf(x) ; Integer ;

где Х – идентификатор типа или переменной.

Например, выражение SizeOf (Integer) имеет значение 2. Это же значение имеет выражение SizeOf (х), если Х – переменная (но не выражение) типа Integer.

Работа с обширным массивом

Сейчас самое подходящее время вернуться к массиву, с которым мы пытались работать в начале. Помните, массив, содержащий 15 тысяч элементов типа Longint, мы смогли обработать, а 20 тысяч – уже нет? Поскольку максимальная размерность для структурированных типов составляет всего 65 520 байт, а объем динамической памяти (или кучи) приблизительно 300 000 байт, почему бы не воспользоваться этой памятью для обработки обширных массивов? Однако и при использовании динамической памяти сохраняется ограничение на максимальную размерность для структурированных типов (65 520 байт). Поэтому не удастся, выделив предварительно динамическую память (с помощью процедуры NEW), просто объявить наш массив в разделе описания переменных. Однако, для того чтобы преодолеть барьер в 65 520 байт, можно создать массив из 9 элементов, представляющих собой нетипизированые указатели на участки в памяти (или на блоки). При этом каждый из таких блоков предназначен для 8 000 элементов типа Longint. (Другими словами, мы попытаемся работать с массивом из 72 тысяч элементов – это приблизительно соответствует возможностям динамической памяти.) Почему для ссылок на участки памяти, в которых будут храниться блоки (по 8 000 элементов) нашего обширного массива, используются именно нетипизированные указатели? Дело в том, что для резервирования памяти под динамическую переменную, на которую ссылается нетипизированный указатель, используется процедура GetMem. А эта процедура, в отличие от процедуры New, используемой для типизированных указателей, имеет параметр, позволяющий указать объем резервируемой памяти. Иными словами, данный прием позволяет определить указатель на первый элемент блока из 8 000 элементов и одновременно зарезервировать память для остальных 7 999 элементов блока.

Как может выглядеть соответствующая программа, демонстрирует пример 5.

Пример 5

program array2;

const number=8000; {число элементов в одном блоке}

type

ab =array[0..0] of longint;

pab =^ab;

var

ch:array[0..8] of pointer;

total, i:longint;

begin

total:=number*9; {число элементов в 9-ти блоках}

writeln('Свободная память=',memavail,

';наибольший участок= ', maxavail);

for i:=0 to 8 do

getmem (ch[i], number*sizeof(longint)); {резервир. памяти}

for i:=0 to total-1 do

pab(ch[i div number])^[i mod number]:=i; {Присвоение

порядкового номера}

for i:=0 to total-1 do

if (i mod 1000=0) or (i =total) then

write(i:10, pab(ch[i div number])^[i mod number]:6);

writeln ;

writeln('Свободная память= '.memavail,

'; наибольший участок= ', maxavail);

readln

End .

Здесь константа Number задает количество элементов в блоке. Переменная CH (ch:array[0. .8] of pointer) описывает массив нетипизированных указателей на первые элементы в каждом блоке. Переменная Totalсодержит общее число элементов во всех блоках (total:=number *9).

До начала выделения динамической памяти и после (в конце программы) на экран выводятся значения общего свободного пространства кучи и ее наибольшего непрерывного свободного участка (функцииMemAvail и MaxAvail соответственно). Наконец, для обрабатываемого нами массива выделяется динамическая память:

for i:=0 to 8 do getmem(ch[i], number*sizeof(longint))

Здесь значение переменной I соответствует номеру очередного блока, под который выделяется память. Процедура GetMem (резервирующая за нетипизированным указателем фрагмент динамической памяти) имеет два параметра. Первый из них (ch[i]) – нетипизированный указатель, ссылающийся на область в динамической памяти, предназначенную для первого элемента блока. Второй элемент процедуры (number *SizeOf (longint)) определяет размер динамической переменной в байтах. В нашем случае Number – это число элементов в блоке (8 000). Функция SizeOf возвращает длину внутреннего представления указанного объекта (для типа Longint – 4 байта). Теперь можно вычислить, сколько всего байт памяти резервируется – 9 блоков умножить на 8 000 элементов в блоке, умножить на 4 байта для каждого элемента – итого 288 тыс. байт. Именно такой должна быть разница между значениями, возвращаемыми функцией MemAvail вначале и в конце программы.

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

for i:=0 to total–1 do

pab(ch[i div number ])^[i mod number]:=i

Этот оператор, собственно вторая его половина, требует более пристального внимания. С первой половиной все ясно – оператор цикла с параметром for i:=0 to total–1 do организует обращение к каждому из элементов, содержащихся в девяти блоках, созданных нами в динамической памяти. Но каким образом совершается само обращение? Для того чтобы это понять лучше, взглянем на рис.5.

Очевидно, что в строке программы, представленной на рис.5, выражение i div number определяет номер блока, а выражение i mod number – номер каждого элемента в блоке. (Результат операции деления DIV –целое число без остатка. Результат операции MOD – остаток от деления двух целых чисел.) Вспомним, что СН – это массив из девяти указателей на первые элементы блоков, поэтому выражение ch[i div number] представляет собой обращение к первым элементам девяти блоков.

Но каким образом можно обратиться к каждому элементу в каждом блоке? Для этого массив СН (массив нетипизированных указателей) приводится к типу Pab (pab(ch[i div number]). Мы помним, что Pab – это указатель на массив элементов Longint. Затем этот указатель разыменуется (т. е. преобразуется в обращение к самому массиву) и к выражению, представляющему идентификатор массива (pab(ch[i div number]^),добавляется индекс ([i mod number]). Таким образом, выражение pab(ch[i div number])^[i mod number] обеспечивает обращение к каждому из элементов массива из 72 000 (8 000×9) элементов Longint.

Рис.5. Обращение к каждому из элементов обширного массива

Затем на экран выводятся значения каждого тысячного, а также последнего элементов нашего массива:

for i:=1 to total do

if (i mod 1000=0) or (i =total–1) then

write(i:10, pab(ch[i div number])^[i mod number]:6);

Причем, как и в программе из начала главы, значение каждого элемента выводится (для контроля) в паре со значением параметра цикла I – эти значения должны совпадать.

Наконец, снова на экран выводится информация об общем свободном пространстве кучи и ее наибольшем непрерывном свободном участке (функции MemAvail и MaxAvail соответственно).

Последний оператор программы (функция ReadLn) присутствует здесь для того, чтобы приостановить работу программы и предоставить возможность спокойно рассмотреть экран вывода. Теперь, чтобы завершить программу, достаточно нажать клавишу <Enter>. Используя только статическую память, мы смогли обработать массив всего из 15 000 элементов Longint, однако, воспользовавшись динамической памятью, нам удалось справиться с массивом, включающим 72 000 таких же элементов.

Обратите внимание, что в программе Аrrау2 динамическая память выделяется (с помощью процедуры GetMem), однако затем не освобождается. Не противоречит ли это тому, о чем шла речь ранее (что зарезервированную ранее динамическую память всегда непременно следует освобождать)?

Дело в том, что освобождение памяти – не самоцель. Память следует освобождать тогда, когда ее затем требуется использовать для других переменных. В нашем случае в момент, когда динамическую память можно было бы освободить, программа уже завершается. Иными словами, бессмысленно освобождать память, которую затем не предполагается использовать. А при повторном запуске программы Аrrау2 экран вывода засвидетельствует, что динамическая память снова имеет исходный объем – 288 624 байта. Для того чтобы убедиться в этом, достаточно еще раз запустить программу.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Для выполнения работы необходимо:

1. Повторить правила техники безопасности при работе с вычислительной техникой.

2. Изучить раздел "Динамическая память и указатели" лекционного курса, а также теоретическую часть настоящих методических указаний.

3. Получить у преподавателя вариант задания (варианты заданий приведены в разделе 6 настоящих методических указаний).

4. Написать программу на Турбо Паскале (при необходимости используя предварительно разработанный алгоритм).

5. Ввести программу в компьютер, отладить и результаты выполнения показать преподавателю.

6. В соответствии с требованиями, приведенными в разделе 4, оформить отчет по лабораторной работе.

7. Защитить лабораторную работу, продемонстрировав преподавателю отчет по лабораторной работе+

теоретические знания.

При подготовке к защите для самопроверки рекомендуется ответить на контрольные вопросы, приведенные в разделе 5.

ТРЕБОВАНИЯ К ОТЧЕТУ

Отчет по выполненной лабораторной работе должен содержать:

условие задания;

текст программы на языке Турбо Паскаль.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое указатели?

2. Каким образом выделяется и освобождается динамическая память?

3. Какие возможны действия над указателями и динамическими переменными?

4. Что такое динамические данные без внутренних ссылок?

5. Что такое динамические данные с внутренними ссылками?

6. Каковы процедуры для работы с динамической памятью?

7. Каковы функции для работы с динамической памятью?

ВАРИАНТЫ ЗАДАНИЙ

Вариант 1

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая по списку L строит два новых списка: L1 – из положительных элементов и L2 – из остальных элементов списка L.

2. Используя очередь, за один просмотр файла f и без использования дополнительных файлов, напечатать элементы файла f в следующем порядке: сначала – все числа, меньше a, затем – все числа из отрезка [a,b], и наконец – все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (a и b – заданные числа, a <b).

3. Используя стек напечатать содержимое текстового файла t, выписывая литеры каждой его строки в обратном порядке.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая присваивает параметру E элемент из самого левого листа непустого дерева T (лист – вершина, из которой не выходит ни одной ветви).

Вариант 2

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу удаления из списка L одного элемента, следующего за элементом E, если такой есть и он отличен от E.

2. Используя очередь, содержимое текстового файла f, разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (с сохранением исходного взаимного порядка как среди цифр, так и среди остальных литер строки).

3. Постфиксной формой записи выражения aΔb называется запись, в которой знак операции размещен за операндами: abΔ. Примеры:

a–b → ab–

a*b+c → ab*c+ (т. е. (ab*)c+)

a*(b+c) → abc+* (т. е. a(bc+)*)

a+b2c2d*e → abc2d2e*+

Написать программу, которая вычисляет как целое число значение выражения (без переменных), записанное в постфиксной форме в текстовом файле postfix.

Использовать следующий алгоритм вычисления. Выражение просматривается слева направо. Если встречается операнд (число), то его значение (как целое) заносится в стек, а если встречается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция, и ее результат записывается в стек. В конце концов в стеке останется только одно число – значение всего выражения.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая определяет число вхождений элемента E в дерево T.

Вариант 3

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу добавления новых элементов E1 и E2 в список L перед его последним элементом.

2. Используем очередь.

type name=(Anna , …,Zeta);

child=packed array[name, name] of Boolean

next=file of name;

Считая заданными имя N и массив C типа child (C[x,y]=true, если человек по имени y является ребенком человека по имени x), записать в файл NE типа next имена всех потомков человека с именем N в следующем порядке: сначала – имена всех его детей, затем – всех его внуков, затем – всех правнуков и т. д.

a–b → ab–

a*b+c → ab*c+ (т. е. (ab*)c+)

a*(b+c) → abc+* (т. е. a(bc+)*)

a+b2c2d*e → abc2d2e*+

Написать программу, которая переводит выражение, записанное в обычной (инфиксной) форме в текстовом файле infix, в постфиксную форму и в таком виде записывает его в текстовый файл postfix.

Использовать следующий алгоритм перевода. В стек записывается открывающая скобка, и выражение просматривается слева направо. Если встречается операнд (число или переменная), то он сразу переносится в файл postfix. Если встречается открывающая скобка, то она заносится в стек, а если встречается закрывающая скобка, то из стека извлекаются находящиеся там знаки операций до ближайшей открывающей скобки, которая также удаляется из стека, и все эти знаки (в порядке их извлечения) записываются в файл postfix. Когда же встречается знак операции, то из конца стека извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшинство которых больше или равно старшинству данной операции, и они записываются в файл postfix, после чего рассматриваемый знак заносится в стек. В заключение выполняются такие же действия, как если бы встретилась закрывающая скобка.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая заменяет в дереве T все отрицательные элементы на их абсолютные величины.

Вариант 4

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая проверяет на равенство списки L1 и L2.

2. Используя очередь, решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров позиций закрывающих скобок. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

8 10; 12 16; 3 17.

a–b → ab–

a*b+c → ab*c+ (т. е. (ab*)c+)

a*(b+c) → abc+* (т. е. a(bc+)*)

a+b2c2d*e → abc2d2e*+

Написать программу, которая печатает в обычной (инфиксной) форме выражение, записанное в постфиксной форме в текстовом файле postfix. (Лишние скобки желательно не печатать).

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая вычисляет среднее арифметическое всех элементов непустого дерева T.

Вариант 5

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая переносит в конец непустого списка L его первый элемент.

2. Используя очередь, решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров позиций открывающих скобок. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

3 17; 8 10; 12 16.

3. Написать программу с использованием указателя на одномерный массив для работы с двумерным массивом. Для этого:

сформировать динамический массив записей из исходных данных, расположенных в текстовом файле;

для формирования использовать процедуру с параметром-переменной типа указателя на массив; функцию, возвращающую указатель на массив;

ввести из файла и вывести исходные данные;

для удаления пробелов в начале и в конце введенной строки использовать функцию с параметром;

обработать данные динамического массива с помощью процедур: с параметром – динамическим массивом – для поиска сведений и о студенте по его фамилии; без параметров – для поиска сведений о студентах по размеру стипендии не менее заданного.

Исходные данные для создания массива записей и поисков вводятся из файлов.

Сведения о студентах содержат: номер зачетной книжки, группу, фамилию и инициалы, размер стипендии.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, меняет местами максимальный и минимальный элементы непустого дерева T, все элементы которого различны.

Вариант 6

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая переворачивает список L, т. е. изменяет ссылки в этом списке так, чтобы его элементы оказались расположенными в обратном порядке.

2. Используя очередь, решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется напечатать в порядке возрастания номера позиций в тексте закрывающих скобок. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

10 16 17.

3. Написать программу с использованием указателя на одномерный динамический массив для работы с двумерным массивом. Для этого:

сформировать динамический массив арифметических данных из исходных данных, расположенных в текстовом файле;

ввести из файла и вывести исходные данные;

поменять местами максимальный и минимальный элементы массива с помощью процедуры с параметрами.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая печатает элементы всех листьев дерева T.

Вариант 7

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая заменяет в списке L все вхождения элемента E1 на элемент E2.

2. Используя очередь, решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется напечатать в порядке возрастания номеров позиций в тексте открывающих скобок. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

3 8 12.

3. Написать программу с использованием указателя на двумерный динамический массив. Для этого:

ввести из файла и вывести исходные данные;

найти максимальный и минимальный элементы массива с помощью процедуры с параметрами.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

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

Вариант 8

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая оставляет в списке L только первые вхождения одинаковых элементов.

2. Используя очередь, решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется напечатать в порядке убывания номеров позиций в тексте открывающих скобок. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

12 8 3.

сформировать динамический массив записей из исходных данных, расположенных в текстовом файле;

ввести из файла и вывести исходные данные;

для удаления пробелов в начале и в конце введенной строки использовать функцию с параметром;

Исходные данные для создания массива записей и поисков вводятся из файлов.

Сведения о студентах содержат: номер зачетной книжки, группу, фамилию и инициалы, размер стипендии.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая строит копию дерева T.

Вариант 9

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая определяет, входит ли список L1 в список L2.

2. Используя очередь решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется напечатать в порядке убывания номеров позиций в тексте закрывающих скобок. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

17 16 10.

3. Разработать программу для формирования и обработки свободного массива записей со сведениями о студентах ряда групп. В качестве исходных данных использовать сведения о студентах из файла исходных данных. В файле размещены сведения о студентах различных групп вперемежку по номерам групп. Номер группы – это 6-й символ в наименовании группы. Надо ввести исходные данные. Создать из них свободный динамический массив. В каждой строке этого двумерного динамического массива разместить сведения о студентах одной из групп.

Для формирования свободного динамического массива записей использовать 2 массива на N элементов:

K – массив на N элементов с количеством студентов в 1÷N группах;

Z – массив из N указателей на массивы записей в 1÷N группах.

Программу выполнить со статическими массивами K и N.

В программе надо:

сформировать динамический массив записей из исходных данных, расположенных в текстовом файле;

ввести из файла и вывести исходные данные;

для удаления пробелов в начале и в конце введенной строки использовать функцию с параметром;

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

Исходные данные для создания массива записей и поисков вводятся из файлов.

Сведения о студентах содержат: номер зачетной книжки, группу, фамилию и инициалы, размер стипендии.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая находит в непустом дереве T длину (число ветвей) пути от корня до ближайшей вершины с элементом E; если E не входит в T, за ответ принять –1.

Вариант 10

1. Имеются линейные однонаправленные списки:

type

p=^item;

item=record

data:real ;

reference:p

end ;

Написать программу, которая находит среднее арифметическое всех элементов непустого списка L.

2. Используя очередь, решить следующую задачу. В текстовом файле t записан текст, сбалансированный по круглым скобкам. Требуется напечатать в порядке возрастания номеров позиций в тексте операнды операций вычитания. Например, для текста A+(45–F(X)*(B–C)) надо напечатать:

45 F(X) B C.

Для формирования свободного динамического массива записей использовать 2 массива на N элементов:

K – массив на N элементов с количеством студентов в 1÷N группах;

Z – массив из N указателей на массивы записей в 1÷N группах.

Программу выполнить с динамическими массивами K и N.

В программе надо:

сформировать динамический массив записей из исходных данных, расположенных в текстовом файле;

ввести из файла и вывести исходные данные;

для удаления пробелов в начале и в конце введенной строки использовать функцию с параметром;

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

Исходные данные для создания массива записей и поисков вводятся из файлов.

Сведения о студентах содержат: номер зачетной книжки, группу, фамилию и инициалы, размер стипендии.

4. Имеются двоичные деревья:

type

tree=^item ;

item=record

data:real ;

right, left:tree

end ;

Написать программу, которая подсчитывает число вершин на n-м уровне непустого дерева T (корень считать вершиной 0-го уровня).

Дата добавления: 2019-02-26; просмотров: 715; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 23

Мы поможем в написании ваших работ!