Списки
СТРУКТУРЫ ДАННЫХ .
Под структурами данных (далее с/д) понимают элементы данных и связи между
ними.Каждая с/д характеризуется типовым набором операций с элементом :
- поиска (доступа)
- записи (включения)
- выборки (удаления)
Элементы могут быть либо простые ,либо составные.
Из изученных нами с/д являются :
1) одиночное значение (переменная) ;
2) вектор (одномерный массив) ;
3) матрица (двумерный массив) ;
4) линейные списки ;
5) деревья ;
6) графы .
Список в памяти компьютера может быть представлен одним из двух способов :
1) последовательное представление ;
2) связанное представление .
1 Последовательное представление
В этом случае соседние элементы списка физически следуют друг за другом,
распологаясь в соседних элементах массива.
е(i-1) e(i) e(i+1)
──┬─────────────┬─────────────┬──────────────┬────
│ U(i-1) │ U(i) │ U(i+1) │
──┴─────────────┴─────────────┴──────────────┴────
2 Связанное представление
Каждый элемент содержит ссылочную часть на соседний элемент.
е(i-1) e(i) e(i+1)
┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐
──── │ U │ Y │ ──── │ U │ Y │ ──── │ U │ Y │ ────
│(i-1)│(i-1)│ │ (i) │ (i) │ │(i+1)│(i+1)│
└─────┴─────┘ └─────┴─────┘ └─────┴─────┘
Простейшие разновидности списков :
1) Стек (Stack);
2) Очередь (Queue);
3) Дек (Double Extended Queue - DEQ).
СТЕК .
Стек - это список ,в котором включение и выключение элементов произво-
дится только с одного конца ,называемого вершиной стека (физический пример -
стопка книг).Стек также называют LIFO-списком ,от англ. -
Last In First Out
Для стека существуют две операции :
PUSH - поместить в стек ;
POP - взять из стека .
Стек широко используется в программировании , в частности - в вызове п/п .
* П. работы со стеком:
┌───┬───┬───┬───┬───┬───┐
Stack │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Top Maxpos=6
PUSH (10)
┌───┬───┬───┬───┬───┬───┐
Stack │ 10│ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Top Maxpos=6
PUSH (20)
┌───┬───┬───┬───┬───┬───┐
Stack │ 10│ 20│ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Top Maxpos=6
POP (k) k=20
┌───┬───┬───┬───┬───┬───┐
Stack │ 10│ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Top Maxpos=6
При работе со стеком возможны две ошибочные ситуации :
1) переполнение ;
┌───┬───┬───┬───┬───┬───┐
Stack │ 10│ 20│ 30│ 40│ 50│ 60│
└───┴───┴───┴───┴───┴───┘
Top
2) недостаток стека
┌───┬───┬───┬───┬───┬───┐
Stack │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Top Maxpos=6
РОР (к) ;
* П.:
Program List1;
Const
MaxPos = 4;
Var
Stack:array[1..MaxPos] of byte;
top:byte;
k:byte;
Procedure Initstack;
begin
top:=1;
end;
Procedure Push (el:byte);
begin
if top>MaxPos
then writeln(#7,'Error')
else begin
Stack[top]:=el;
inc(top);
end;
end;
Procedure Pop (var el:byte);
begin
if top = 1
then writeln(#7,'Error')
else begin
dec(top);
el:=Stack[top];
end;
end;
Procedure Printstack;
var
i:integer;
begin
for i:=top-1 downto 1 do
write(Stack[i],' ');
writeln;
end;
Begin
Initstack;
Push(10);
Push(20);
Push(30);
Push(40);
Push(50);
Pop(k);
k:=40;
Push(60);
Pop(k);
k:=60;
Printstack; { 30 20 10 }
End.
ОЧЕРЕДЬ .
Очередь - структура данных ,в кот. элементы добавляются с одного края ,
а удаляются с другого .
Край , в кот. выполняется включение - конец очереди (Tail) .
Край , с кот. выполняется извлечеие - голова (Head) .
Другое название очереди - FIFO , от англ. -
First In First Out .
* П. работы с очередью :
1) Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Head Maxpos=6
Insert(10);
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ 10│ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Head Maxpos=6
Insert(20);
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ 10│ 20│ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Head Maxpos=6
Extract(k); k = 10
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ 20│ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Head Maxpos=6
Extract(k); k = 20
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Head Maxpos=6
2)
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘
Head
Insert(100)
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │100│
└───┴───┴───┴───┴───┴───┘
Head
Когда Tail достигнет позиции MaxPos ,впереди элементы иссякнут . В этом
случае Tail необходимо переместиьть на первую позицию .
1 Условия переполнения списка
1) Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │ │ Head = 1
└───┴───┴───┴───┴───┴───┘ Tail = MaxPos
Head Maxpos=6
2) Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┘ Head-1 = Tail
Head Maxpos=6
2 Условие пустоты массива
Tail
¬
┌───┬───┬───┬───┬───┬───┐
Queue │ │ │ │ │ │ │ Head = Tail
└───┴───┴───┴───┴───┴───┘
Head Maxpos=6
Список также широко используется в программировании .
* П.:
Клавиатура
Program List2;
Const
MaxPos = 4;
Var
Queue:array [1..MaxPos] of word;
Head,Tail:byte;
Procedure InitQueue;
begin
Head:=1;
Tail:=1;
end;
Procedure Insert(var el:word);
begin
if ((Head = 1) and (Tail = MaxPos))
or (Tail+1 = Head)
then writeln(#7,' Error ')
else begin
Queue[Tail]:=el;
inc(Tail);
if Tail>MaxPos
then Head:=1;
end;
end;
Procedure Extract(var k:word);
begin
if Head = Tail
then writeln(#7,' Error ')
else begin
k:=Queue[Head];
inc(Head);
if Head>MaxPos
then Head:=1;
end;
end;
Procedure PrintQueue(var i:byte);
begin
if Tail>Head
then
for i:=Head to Tail-1 do
write(Queue[i])
else
if Tail<Head
then begin
for i:=Head to MaxPos do
write(Queue[i]);
for i:=1 to Tail do
write(Queue[i]);
end;
end;
Begin
InitQueue;
Insert(10);
Insert(20);
Insert(30);
Extract(k);
k:=30;
PrintQueue;
End.
Двусторонняя очередь .
Двусторонняя очередь - очередь ,в кот. вставлять и извлекать элементы
из кот. можно из любого конца .
Набор типовых операций с двусторонней очередьювключает в себя :
1) вставка элемента в голову , в хвост ;
2) извлечение элемента из головы , из хвоста .
СВЯЗАННОЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ .
* П.:
Для последующих примеров
type type
TPTR = ^Tel ; PItem = ^Item ;
Tel = record Item = record
Inf:integer; el:byte;
Next:TPTR; Next:PItem
end; end;
По количеству указателей списки разделяют на односвязные и двусвязные .
* П.:
Реализация связанного стека
Var
top:PItem;
Procedure Initstack;
begin
top:=nil;
end;
Procedure Push(var el:byte);
var
p:Item;
begin
New(p);
p^.el:=el;
p^.next:=top;
top:=p^;
end;
Procedure Pop(var el:byte);
var
p:PItem;
begin
if top=nil
then writeln(#7,' Error ')
else begin
el:=top^.el;
p:=top;
top:=p^.next;
dispose(p);
end;
end;
Procedure Printstack;
var
p:PItem;
begin
p:=top;
while p<>nil do
begin
write(p^.el,' ');
p:=p^.next;
end;
writeln;
end;
Begin
Initstack;
Push(10);
Push(20);
Push(30);
Push(40);
Push(50);
Pop(k);
k:=40;
Push(60);
Pop(k);
k:=60;
Printstack; { 30 20 10 }
End.
Разработаем набор процедур ,обеспечиваюших работу с универсальным спис-
ком.Под универсальным списком будем понимать список ,с кот. можно произвести
следующие операции :
1) Вставка в начало ;
в конец ;
в произвольное место ;
2) Извлечение из начала ;
из конца ;
из любого места ;
3) Чтение значения элемента
из начала ;
из конца ;
из любого места ;
4) Изменение значения любого элемента ;
5) Инициализация списка ;
Очистка списка ;
Печать списка .
* П.:
Type
PItem = ^Item;
Item = record
el:byte;
next:PItem;
end;
Var
Head,
Tail:PItem;
Инициализация списка.
Procedure InitList;
begin
Head:=nil;
Tail:=nil;
end;
Очистка списка.
Procedure ClearList;
var
p:PItem;
begin
while Head<>nil do
begin
p:=Head;
Head:=Head^.next;
dispose(p);
end;
Tail:=nil;
end;
Вставка в голову.
Procedure InsertToHead(el:byte);
var
p:PItem;
begin
New(p);
p^.el:=el;
p^.next:=Head;
Head:=p;
if Tail=nil
thenTail:=p;
end;
Вставка в хвост.
Procedure InsertInTail(el:byte);
var
p:PItem;
begin
New(p);
p^.el:=el;
p^.next:=nil;
if Tail=nil
then HEad:=p;
else Tail^.next:=p;
Tail:=p;
end;
Извлечение из головы.
Procedure ExtractFromHead(var el:byte);
var
p:PItem;
begin
if Head<>nil
then begin
el:=Head^.el;
p:=Head;
Head:=Head^.next;
dispose(p);
if Head=nil
then Tail:=nil;
end
else writeln(p^.el,' ');
end;
Извлечение из конца списка.
Procedure ExtractFromTail(var el:byte);
var
p:PItem;
begin
if Tail<>nil {если список не пустой}
then begin
el:=Tail^.el;
if Tail=Head
then begin
dispose(Tail);
Head:=nil;
Tail:=nil;
end
else begin
p:=Head;
whilep^.next<>Tail do
begin
p:=p^.next;
p^.next:=nil;
dispose(Tail);
Tail:=p;
end;
end
else writeln(p^.el,' ');
end;
Вставка элемента в произвольное место списка.
Procedure InsertEl(el:byte;i:word);
{i-перед каким элементом вставлять}
var
n:word; {индекс элемента списка}
p:PItem; {вставляемый элемент}
pnext,pprev:PItem; {следующий и предыдущий элементы}
begin
pnext:=Head;
pprev:=nil;
n:=1;
{ищем местоположение вставл. эл.}
while pnext<>nil do
begin
if i=n
then break;
pprev:=pnext;
pnext:=pnext^.next;
inc(n);
end;
New(p);
p^.el:=el;
p^.next:=pnext;
end;
Односвязные списки такого вида называются циклическими .
┌────┬────┐ ┌────┬────┐
│ │ │ │ │ │
┌── │ │ │ ──────────── │ │ │ ───┐
│ │ │ │ │ │ │ │
│ └────┴────┘ └────┴────┘ │
│ │
└─────────────────────────────────────────────┘
Двусвязные списки .
* П.:
Type
PDItem = ^DItem;
DItem = record
el:byte;
next:PDItem;
prev:PDItem;
end;
Var
Head,Tail:PDItem;
num:word; {кол-во элементов в списке}
Вставка в голову списка .
Procedure InsertToHead;
var
p:PDItem;
begin
New(p);
p^.el:=el;
p^.prev:=nil;
if Head=nil
then begin
p^.next:=Head;
Head^.prev:=p;
Head:=p;
end;
inc(num);
end;
Извлечение из хвоста.
Procedure ExtractFromTail(var el:byte;i:word);
var
p:PDItem;
begin
if Tail<>nil
then begin
el:=Tail^.el;
p:=Tail;
Tail:=Tail^.prev;
dispose(p);
if Tail=nil
then Head:=nil
else Tail^.next:=nil;
dec(num);
end
else write(#7,' Error ');
end;
Извлечение из головы.
Procedure ExtractFromHead(var el:byte);
begin
el:=Head^.el;
end;
Вставка в конец .
Procedure WriteTail(var el:byte);
begin
Tail^.el:=el;
end;
Вставка элемента в произвольное место списка .
Procedure InsertEl(var el:byte;i:word);
var
n:word;
p:PDItem;
pnext,pprev:PDItem;
begin
New(p);
p^.el:=el;
if Head = nil
then begin
p^.next:=nil;
p^.prev:=nil;
Head:=p;
Tail:=p;
end
else if i<=1
then begin
p^.next:=Head;
p^prev:=nil;
Head^.prev:=p;
Head:=p;
end
else if i>=num
then begin
p^.next:=nil;
p^prev:=Tail;
Tail^.prev:=p;
Tail:=p;
end
else begin
pnext:=Head;
n:=1;
while n<>i do
begin
pnext:=pnext^.next;
inc(n);
end;
p^.prev:=pnext;
pnext:=pnext^.next;
pnext^.next^.prev:=p;
pnext^.next:=p;
end;
inc(num);
end;
Печать списка .
Procedure PrintList;
var
p:PDItem;
begin
p:=Head;
while p<>nil do
begin
write(p^.el:3,' ');
p^:=p^.next;
end;
writeln;
end;
Динамическая память
Указатели. Работа с указателями.
Указатели позволяют работать с данными через их адреса.
В Turbo Pascalе имеется стандартный указательный тип Pointer и существует возможность определить пользовательский указательный тип для любого указанного типа.
Пользовательский указательный тип PSomeType для типа SomeType определяется следующим образом:
type
PSomeType = ^ SomeType;
Пример:
Задача.
Определим тип записи TWorker (работник), содержащей поля ФИО, должность и зарплата. После чего определим указательный тип PWorker для типа TWorker, и, заодно, указательные типы PInteger для Integer и PChar для Char.
Решение:
Type
TWorker = record {запись Работник}
Fio:string[60]; {поле ФИО}
Post:string[60]; {поле Должность}
Wages:Integer; {поле Заработная плата}
end;
PWorker = ^ TWorker; {указатель на TWorker}
PInteger = ^ Integer; {указатель на Integer}
PChar = ^ Char; {указатель на Char}
Несложно заметить, что все указательные типы в данном примере начинаются с буквы P. Буква P означает, что данный тип - указательный (P от Pointer). Указательный тип не обязательно должен начинаться на букву P, его можно обзывать любым другим именем, но лучше все-таки придерживаться именно такого правила - имя любого указательного типа начинать с буквы P - в этом случае создаваемая программа будет легче читаться и пониматься (а следовательно и легче отлаживаться).
Значениями переменных и констант указательного типа являются адреса оперативной памяти. Значение переменной указательного типа можно задать одним из четырех следующих способов:
1) Используя операцию взятия адреса @.
Пример:
Объявим несколько переменных указательного типа и несколько переменных базовых типов (базовым типом по отношению к указательному типу называется тот тип от которого произведен указательный, например базовым для типа PWorker является тип TWorker, а базовым типом для PChar - Char).
Var
{указатели}
pw:PWorker;
pi:PInteger;
pc: PChar;
p : Pointer;
{переменные базовых типов}
w:TWorker;
i:Integer;
c: Char;
Заметим, что все указатели в Turbo Pascalе занимают 4 байта памяти. После несложных вычислений выясним, что одна переменная типа TWorker занимает 124 байта памяти. Вспомним, что переменные типа Integer и Char занимают соответственно 2 и 1 байт.
Зная размеры каждой переменной, и зная адрес первой из объявленных переменных, можно вычислить адреса оперативной памяти по которым расположены все остальные объявленные переменные. Дело в том, что компилятор располагает все объявленные переменные друг за другом, сначала первую, затем вторую и так далее. Пусть адрес первой из объявленных переменных - переменной pw равен $561F005E (значение взято реальное).
Тогда адреса всех остальных переменных будут следующими:
имя переменной длина переменной адрес
pw 4 $561F005E
pi 4 $561F0062
pc 4 $561F0066
p 4 $561F006A
w 124 (127=$7C) $561F006E
i 2 $561F00EA
c 1 $561F00EC
Теперь зная адреса переменных можно продемонстрировать получение этих самых адресов:
begin
p:=@p; {в переменную p заноситься адрес переменной p - т.е. число $561F006A}
p:=@c; {в переменную p заноситься адрес переменной c - т.е. число $561F00EC}
pc:=@c; {в переменную pc заноситься адрес переменной c - т.е. число $561F00EC}
pi:=@i; {в переменную pi заноситься адрес переменной i - т.е. число $561F00EA}
pw:=@w; {в переменную pw заноситься адрес переменной w - т.е. число $561F006E}
p:=@pw; {в переменную p заноситься адрес переменной pw - т.е. число $561F005E}
end.
2) Присвоение элементу указательного типа значения другого элемента указательного типа:
2.1) Присваивание элементу типа Pointer значение другого элемента любого
указательного типа
Пример:
begin
pw:=@w; {в переменную pw заноситься адрес переменной w - т.е. число $561F006E}
pc:=@c; {в переменную pc заноситься адрес переменной c - т.е. число $561F00EC}
p:=pw; {в переменную p заноситься адрес переменной w - т.е. число $561F006E}
p:=pc; {в переменную p заноситься адрес переменной c - т.е. число $561F00EC}
end.
2.2) Присваивание элементу любого указательного типа значение элемента типа Pointer
Пример:
begin
p:=@w; {в переменную p заноситься адрес переменной w - т.е. число $561F006E}
pw:=p; {в переменную pw заноситься адрес переменной w - т.е. число $561F006E}
pc:=p; {в переменную pc заноситься адрес переменной w - т.е. число $561F006E}
end.
2.3) Присваивание элементу любого указательного типа значение элемента того же указательного типа
Пример:
var
i:integer;
c:char;
pc1,pc2:PChar;
pi1,pi2: PInteger;
begin
pc1:=@c; {в переменную pc1 заноситься адрес переменной c}
pc2:=pc1; {в переменную pc2 заноситься адрес переменной c}
pi2:=@i; {в переменную pi2 заноситься адрес переменной i}
pi1:=pi2; {в переменную pi1 заноситься адрес переменной i}
end.
3) Присвоение элементу любого указательного типа значения nil
Замечание: nil - это специальное значение указателя - "указатель в никуда". Определен он следующим образом:
const
nil : longint = 0;
Nil используют в тех случаях, когда необходимо явно указать, что данный указатель никуда не указывает.
Пример:
var
p:Pointer;
pi: PInteger;
pc:PChar;
begin
p:=nil;
pi:=nil;
pc:=nil;
end.
4) Значение указателя можно задавать процедурами New и Getmem.
Все вышерассмотренные примеры демонстрировали работу со статически выделяемой памятью - если какая-то переменная объявляется в программе, то память для ее размещения выделяется компилятором, и в процессе работы программы месторасполажение переменной изменить нельзя - оно статично.
Кроме такого - статического - способа выделения памяти, существует и другой способ - динамический. При динамическом способе выделения памяти в программе объявляют не сами переменные, а только указатели на них, а память для размещения переменных выделяют при помощи процедур New и Getmem.
Процедура New:
procedure New(var P:Pointer) - создает новую динамическую переменную и заносит в P адрес созданной переменной.
Пример 1:
var
pi: Integer; {указатель на динамически создаваемую переменную}
begin
New(pi); {создали динамическую переменную целого типа}
pi^:=100; {присвоили ей значение 100}
writeln(pi^); {вывели на экран ее значение =100}
Dispose(pi); {уничтожили созданную динамическую переменную}
end.
Пример 2:
var
pw: PWorker; {указатель на динамически создаваемую переменную}
begin
New(pw); {создали динамическую переменную типа TWorker}
pw^.Fio:='Иванов'; {присвоили полю Fio строку 'Иванов'}
pw^.Post:='директор'; {присвоили полю Post строку 'директор'}
pw^.Wages:=2500; {присвоили полю Wages значение 2500}
writeln(pw^.Fio); {вывели на экран строку 'Иванов'}
writeln(pw^.Post); {вывели на экран строку 'директор'}
writeln(pw^.Wages); {вывели на экран значение 2500}
Dispose(pw); {уничтожили созданную динамическую переменную}
end.
Замечание 1:
Доступ к динамически создаваемой переменной производиться через указатель на нее, после которого ставится значок ^.
Замечание 2:
После окончания работы с динамически выделяемой переменной, ее необходимо уничтожить. Для этого используется процедура Dispose (если переменная была создана при помощи New), или процедура FreeMem (если переменная была создана при помощи GetMem (описаны ниже)).
Замечание 3:
Ни в коем случае нельзя обращаться к памяти по адресу хранящемся в неиницилизированном указателе (т.е. в указателе, которому не присвоили значение адреса какой-то конкретной переменной).
Пример:
var
pi:PInteger;
i:integer;
begin
pi^:=100; {Грубая ошибка, весьма часто приводящая к зависанию компьютера}
{Дело в том, что неинициализированный указатель pi все равно хранит
какое-то значение, которое при выполнении оператора pi^:=100;
интерпретируется как адрес переменной целого типа. Именно по
этому НЕОПРЕДЕЛЕННОМУ адресу и будет записано число 100.
Таким образом, число 100 может быть записано в любую ячейку
памяти компьютера. Это, в некоторых случаях, будет приводить
к зависанию вашей программы или даже компьютера, а в некоторых
случаях никакими "спецэффектами" выдавать себя не будет.
Чем очень сильно затруднит поиск ошибки}
pi:=@i;
pi^:=200; {А вот так можно. В этом случае число 200 будет занесено
в переменную i}
New(pi);
pi^:=300; {И так можно. В этом случае число 300 будет занесено в динамически
созданную переменную целого типа, адрес которой храниться в pi}
Dispose(pi); {Нельзя забывать уничтожать динамически создаваемые переменные
после окончания их использования.
При создании динамической переменной под ее размещение
выделяется некоторый объем памяти компьютера. Поскольку
общий объем памяти не бесконечен, то становиться понятным,
что если насоздавать много динамических переменных, то память
рано или поздно кончится.
Чтобы этого не случилось, память расходуют экономно, уничтожая
все динамические переменные сразу после того, как они стали
ненужными.
При уничтожении динамически созданной переменной, память
выделенная под ее размещение освобождается, и может быть
использована для размещения других динамических переменных}
end.
Замечание 4:
Ни в коем случае нельзя обращаться к уничтоженной динамической переменной.
Пример:
var
pi:PInteger;
begin
New(pi); {создали динамическую переменную}
pi^:=10; {присвоили ей значение 10}
writeln('pi^=', pi^ ); {вывели на экран 10}
Dispose(pi); {уничтожили динамическую переменную}
pi^:=20; {ОШИБКА!!! Динамической переменной уже не существует,
а мы записываем в нее 20}
end.
Процедура GetMem:
procedure GetMem(var P:Pointer; Size:Word) - создает новую динамическую переменную заданного размера Size, и помещает ее адрес в указатель P.
Пример:
var
pi: Integer; {указатель на динамически создаваемую переменную}
begin
GetMem(pi,sizeof(integer)); {создали динамическую переменную целого типа}
pi^:=1000; {присвоили ей значение 1000}
writeln(pi^); {вывели на экран ее значение =1000}
FreeMem(pi,sizeof(integer)); {уничтожили созданную динамическую переменную}
end.
Замечание:
Динамическую переменную, созданную процедурой GetMem, после окончания использования необходимо уничтожить процедурой FreeMem.
Процедура FreeMem:
procedure FreeMem(var P:Pointer; Size:Word) - уничтожает динамическую переменную заданного размера Size.
Последнее, что стоит упоминуть о работе с указателями, это то, что к указателям можно применить две операции сравнения: = и <>.Заметим, что сравнивать можно указатели следующих типов:
1) pointer с pointer
2) pointer с любым указательным типом
3) любой указательный тип с pointer
4) любой указательный тип с тем же самым указательным типом
Пример:
var
p,p1:pointer;
pi,pi1:PInteger;
pc,pc1: PChar;
pw,pw1:PWorker;
b: Boolean;
begin
...
if p = p1 ... {pointer и pointer - сравнивать можно}
while p <> pi ... {pointer и PInteger - сравнивать можно}
while pi = pi1 ... {PInteger и PInteger - сравнивать можно}
b:= pc = p; ... {PInteger и pointer - сравнивать можно}
until pw <> pw1 ... {PWorker и PWorker - сравнивать можно}
until pc = pi ... {PChar и PInteger - сравнивать НЕЛЬЗЯ!!!}
if pw <> pi1 ... {PWorker и PInteger - сравнивать НЕЛЬЗЯ!!!}
...
end.
Работа с динамической памятью
Динамическая память - эта та часть оперативной памяти компьютера, в которой располагаются динамически создаваемые переменные. В Turbo Pascalе динамическая память имеет размер порядка 300-500 Кб. При этом стоит отметить, что любая переменная, как статическая так и динамическая не может превышать размер 64 Кб.
Использование динамической памяти позволяет расходовать память компьютера более эффективно. Продемонстрируем это на примере.
Пример:
Задача. Ввести массив А целых чисел . Сформировать массив В из элементов массива А имеющих четное значение.
Решение:
Для наглядности приведем два решения этой задачи - одно (слева) с использованием динамической памяти, второе (справа) - без динамической памяти - массивы статические.
Program DynamicMemoryExample; Program StaticMemoryExample;
const const
maxN = 100; {максимально возможное maxN = 100;
количество элементов
в массивах A и B}
type type
Arr = array[1..maxN] of integer;{массив} Arr = array[1..maxN] of integer;
PArr = ^Arr; {указатель на массив}
var var
a,b:PArr; {a,b -массивы} a,b:Arr;
n,m:integer; {n,m - кол-во элементов} n,m:integer;
i:integer; {i - счетчик} i:integer;
begin begin
{Ввод n}
repeat repeat
read(n); read(n);
until (n>=1) and (n<=maxN); until (n>=1) and (n<=maxN);
{Выделение памяти под массив A}
GetMem(a,sizeof(integer)*n);
{Ввод массива A}
for i:=1 to n do for i:=1 to n do
read(a^[i]); read(a[i]);
{Подсчет четных элементов в массиве A}
m:=0;
for i:=1 to n do
if a^[i] mod 2 = 0
then inc(m);
{Выделение памяти под массив B}
GetMem(b,sizeof(integer)*m);
{Заполнение массива B четными
элементами массива A}
m:=0; m:=0;
for i:=1 to n do for i:=1 to n do
if a^[i] mod 2 = 0 if a[i] mod 2 = 0
then then
begin begin
inc(m); inc(m);
b^[m]:=a^[i]; b[m]:=a[i];
end; end;
{Вывод массива B}
for i:=1 to m do for i:=1 to m do
write(b^[i],' '); write(b[i],' ');
{Уничтожение массивов A и B -
освобождение занятой динамической
памяти}
Freemem(a,sizeof(integer)*n);
Freemem(b,sizeof(integer)*m);
end. end.
С первого взгляда в глаза бросается то, что решение с использованием динамической памяти более длинное, а значит и более сложное. Более длинная программа имеет больший размер исполняемого кода, и медленнее работает.
Получается, что использование динамической памяти приводит только к ухудшению характеристик программы?
На самом деле это далеко не так.
Если проанализировать наш пример, то мы увидим, что в решении с использованием динамической памяти, памяти под массивы A и B выделяется РОВНО СТОЛЬКО, СКОЛЬКО НЕОБХОДИМО ДЛЯ РАБОТЫ программы. В решении же без динамической памяти массивы A и B в любом случае занимают по 200 байт каждый.
Таким образом можно сделать следующие выводы:
1. Использование динамической памяти в программах приводит к уменьшению объема используемой памяти - это плюс.
2. Использование динамической памяти ведет к увеличению размера программы - это минус.
3. Использование динамической памяти чревато множеством сложнообнаруживаемых ошибок связанных с работой с указателями - это минус.
4. Динамическую память необходимо использовать лишь в том случае, когда это принесет явную выгоду, или же когда без нее просто невозможно обойтись.
Замечание:
Работа с динамической памятью является одной из сложнейших тем в программировании. Поэтому, если Вы разберетесь в ней и научитесь на практике использовать динамическую память, то этим Вы сделаете весьма большой шаг к профессиональному уровню программирования.
В заключении описания работы с динамической памятью перечислим типичные ошибки:
1) Потеря динамической памяти. Может произойти в том случае,когда память была выделена, но не была освобождена.
var
P:Pointer;
begin
GetMem(P,100); {выделили 100 байт}
GetMem(P,200); {выделили еще 200 байт}
FreeMem(P,200); {освободили 200 байт - 100 байт освободить уже не удастся... - ОШИБКА}
end.
2) Многократное освобождение одной и той же динамической памяти.
var
pw:PWorker;
begin
New(pw); {выделили память под переменную типа TWorker}
Dispose(pw); {освободили память из-под переменной типа TWorker}
Dispose(pw); {попытались еще раз освободить эту же память}
end.
3) Память не выделялась, но освобождается.
var
PL:^LongInt;
L:LongInt;
begin
PL:=@L; {PL указывает на переменную L}
L:=100000;
writeln(PL^); {выводится число 100000}
Dispose(PL); {пытаемся освободить память, которую не выделяли - ОШИБКА}
end.
Записи и тип.файлы
ОБЪЯВЛЕНИЕ И ИСПОЛЬЗОВАНИЕ ЗАПИСЕЙ
Объявление типа записи
Запись объединяет в единое целое произвольное число элементов любых типов. Как правило, каждая запись объединяет в себе параметры, описывающие какой-то реальный объект. Например, объявим тип записи, хранящей информацию о точке двумерного пространства:
Type
TPoint2D = record
X,Y: Real; {координаты точки}
End;
В примере объявлен тип записи TPoint2D. Каждая запись этого типа содержит 2 поля – X и Y – оба вещественного типа.
Расшифруем название типа TPoint2D:
T – общепринятый префикс (приставка) имени типа в Turbo Pascal’е (T – сокращение от Type).
Point – точка.
2D – общепринятая в информатике запись двухмерного пространства (2 direction).
Этот пример показывает, что имя типа записи должно быть смысловым – оно должно говорить само за себя.
Создадим еще один тип записи – на этот раз в записи будем хранить координаты точки на экране в графическом режиме.
Type
TPoint = record
X,Y:Integer; {координаты точки}
End;
В типе TPoint поля X и Y целого типа, потому что координаты точки на экране – это целые числа.
Используя тип записи TPoint определим записи, хранящие информацию о примитивных геометрических фигурах:
Type
TLine = record {Линия}
P1,p2:TPoint; {координаты точек начала и конца линии}
Color: Byte; {цвет линии}
End;
TCircle = record {Окружность}
Center:TPoint; {координаты центра окружности}
R:Integer; {радиус окружности}
Color: Byte; {цвет линии}
End;
Объявление и использование переменных типа записи
Как и переменные любых других типов, переменные типа запись объявляются в разделе Var.
Пример:
Var
P1,p2:TPoint2D; {переменные типа TPoint2D}
X,y:TPoint; {переменные типа TPoint}
L1,L2:TLine; {переменные типа TLine}
C1,C2:TCircle; {переменные типа TCircle}
A:array[1..10] of TLine; {массив из 10 линий}
F: File of TCircle; {типизированный файл окружностей}
Использование переменных типа запись очень похоже на использование массивов. Как и массивы записи нельзя целиком вводить с клавиатуры и выводить на экран – ввод и вывод осуществляется поэлементно (по полям):
Пример: Ввод/вывод массива целых чисел, и ввод/вывод записи TPoint.
Ввод/вывод массива:
Var
A:Array[1..10] of integer;
N,i:Byte
Begin
{ввод массива}
Read(N);
For i:=1 to N do
Read(a[i]);
{вывод массива}
For i:=1 to N do
Write(a[i],’ ‘);
End.
Ввод/вывод записи:
Var
L:TPoint;
Begin
{ввод записи}
Read(L.X); {ввод поля X}
Read(L.Y); {ввод поля Y}
{вывод записи}
Write(L.X,’ ‘);{вывод поля X}
Write(L.Y,’ ‘);{вывод поля Y}
End.
Как видно из этого примера, для обращения к полю записи надо сначала указать имя записи, а затем, через точку, имя поля. Здесь тоже есть сходство с массивами - для того чтобы обратиться к элементу массива сначала указывается имя массива, затем, в квадратных скобках, индекс элемента.
Пример:
Вывод элемента массива: Вывод поля записи:
Write(a[i],’ ‘); Write(L.Y,’ ‘);{вывод поля Y}
Если в качестве поля записи используется другая запись (как в типе TLine или TCircle), то при обращении к такому полю сначала указывается имя записи, затем через точку - имя поля этой записи, а затем через вторую точку - имя поля для поля типа запись.
Пример: Введем и выведем запись типа TLine
Var
LL:TLine;
Begin
{Ввод записи}
Read(LL.p1.X); {ввод X координаты первой точки p1}
Read(LL.p1.Y); {ввод Y координаты первой точки p1}
Read(LL.p2.X); {ввод X координаты второй точки p2}
Read(LL.p2.Y); {ввод Y координаты второй точки p2}
Read(LL.Color); {ввод цвета }
{Вывод записи}
Writeln(LL.p1.X); {вывод X координаты первой точки p1}
Writeln (LL.p1.Y); {вывод Y координаты первой точки p1}
Writeln (LL.p2.X); {вывод X координаты второй точки p2}
Writeln (LL.p2.Y); {вывод Y координаты второй точки p2}
Writeln (LL.Color); {вывод цвета }
End.
И здесь есть сходство с массивами, на этот раз с двумерными – для обращением к элементу двумерного массива сначала указывается имя массива, затем, в квадратных скобках, два индекса элемента.
Пример:
Ввод элемента массива: Ввод поля записи:
Read(kk[1,4]); Read(LL.p1.X);
Работа с массивом записей
Если записи объединены в массив, то обращение к каждой из них производится как и к обычному элементу массива (указанием имени массива и индекса в квадратных скобках), а к полям записи – через точку и имя поля.
Пример: Введем с клавиатуры массив окружностей
Var
N: Byte;
A:Array[1..10] of Tcircle;
I:Byte;
begin
Read(n);
For i:=1 to n do
Begin
Read(a[i].Center.X);
Read(a[i].Center.Y);
Read(a[i].R);
Read(a[i].Color);
End;
Работа с файлом записей
Как уже было сказано выше, записи невозможно целиком (не по полям) ввести с клавиатуры и вывести на экран. Зато записи можно целиком писать в типизированный файл записей и читать из него.
Пример 1: Сохраним введенный массив окружностей A (смотри пример выше) в файле с именем “circles.dat”
Var
…
F:file of TCircle;
…
Begin
…
assign(F,'Circles.dat'); {связываем файловую переменную F
с именем файла}
rewrite(f); {открываем файл для записи}
for i:=1 to n do {сохраняем записи в файле}
write(f , a[i]);
close(f); {закрываем файл}
…
Пример 2: Загрузим массив окружностей A из файла с именем “circles.dat”
…
assign(F,'Circles.dat'); {связываем файловую переменную F
с именем файла}
reset(f); {открываем файл для чтения}
n:=FileSize(f); {определяем количество записей в файле}
for i:=1 to n do {загружаем записи из файла}
read(f , a[i]);
close(f); {закрываем файл}
…
Оператор With
Оператор With позволяет упростить обращение к полям записи.
Общий вид оператора следующий: With X do Y;
где X – имя переменной типа запись
Y – любой оператор
В операторе Y при обращении к полям записи X имя X указывать не нужно.
Пример: Выведем A - массив записей типа TCircle на экран (смотри примеры выше)
For i:=1 to n do
With a[i] do
Begin
Write(‘ a[’,i,’].Center.X=’,Center.X); {Вывод поля a[i].Center.X}
Write(‘ a[’,i,’].Center.Y=’,Center.Y); {Вывод поля a[i].Center.Y}
Write(‘ a[’,i,’].R=’, R); {Вывод поля a[i].R}
Write(‘ a[’,i,’].Color=’, Color); {Вывод поля a[i].Color}
End;
Из примера видно, что за счет использования оператора With сокращается и упрощается текст программы – внутри оператора With не нужно писать имя записи “a[i]” перед именами полей записи.
Хранение записей в памяти компьютера
Как вы знаете, все переменные, объявленные в программе, во время работы программы располагаются в оперативной памяти компьютера. Также вы знаете, что Turbo Pascal, накладывает некоторые ограничения на размер каждой из переменных и на суммарный объем занимаемой памяти – в частности любая переменная не может занимать больше чем примерно 64 килобайта памяти, и все глобальные переменные в сумме не могут занимать больше чем все те же 64 килобайта памяти. Чтобы соблюдать эти условия, нужно уметь рассчитывать объем памяти занимаемой любой переменной в отдельности и всеми переменными в сумме. Заметим, что значение размера памяти занимаемой переменной легко узнать при помощи вызова функции sizeof(имя_переменной) или sizeof(имя_типа).
Объем памяти занимаемый одной переменной типа запись рассчитать очень легко, для этого необходимо сложить объемы, занимаемые каждым полем в отдельности. Например, объем занимаемый записью типа TPoint объявленной так
Type
TPoint = record
X,Y:Integer; {координаты точки}
End;
вычисляется так:
sizeof(TPoint) = sizeof(integer)+sizeof(integer) = 2 + 2 = 4 байта
а объем занимаемый записью типа TCircle, объявленной так
Type
TCircle = record {Окружность}
Center:TPoint; {координаты центра окружности}
R:Integer; {радиус окружности}
Color: Byte; {цвет линии}
End;
вычисляется так:
sizeof(TCircle)=sizeof(TPoint)+sizeof(integer)+sizeof(byte) = 4+2+1 =
= 7 байт
Объем памяти, занимаемый массивом записей рассчитать также очень просто – для этого необходимо умножить объем памяти, занимаемый одним элементом (одной записью) на количество элементов в массиве. Например, если массив TArrayCircles объявлен так:
Type
TArrayCircles = array[1..10] of TCircles;
то объем памяти, занимаемой одним массивом этого типа вычисляется так:
sizeof(TArrayCircles) = sizeof( TCircles)*10 = 7 * 10 = 70 байт
Замечание:
Объемы памяти, занимаемые переменными стандартных типов Turbo Pascal составляют:
Byte, ShortInt, Char, Boolean – 1 байт
Word, Integer - 2 байта
LongInt, Single - 4 байта
Real – 6 байт
Double, Comp – 8 байт
Extended – 10 байт
Каждое множество занимает от 1 до 32 байт (в зависимости от диапазона значений элементов множества)
Файлы - в зависимости от типа.
Строки string – с длиной заданной по умолчанию -
Var
s:string;
занимает 256 байт.
С длиной заданной явно –
Var
s1:string[20];
занимает на один байт больше указанного в квадратных скобках. В нашем случае 20+1 = 21 байт.
Вариантные записи
В ряде случаев необходимо хранить информацию об объектах, которые различаются лишь небольшим количеством характеристик. В этом случае для хранения информации можно использовать:
а) несколько разных типов записи,
б) вариантную запись.
Каждый из этих вариантов имеет свои плюсы и свои минусы. Но мы не будем их сравнивать, нас интересует лишь КАК реализуется вариант с вариантной записью.
Варинтная запись состоит из двух частей – фиксированной и вариантной. В начале записи размещается фиксированная часть записи – поля, которые присутствуют во всех вариантах. В конце записи находится вариантная часть записи. Вариантная часть начинается со слова case, непосредственно за которым располагается поле-признак. Затем стоит слово of, между которым, и словом end, завершающим запись, перечисляются альтернативные группы полей.
Замечание: При использовании вариантной записи одновременно может быть использована только одна из альтернативных групп.
Рассмотрим объявление и использование вариантных записей на примере:
Разработаем тип вариантной записи для хранения прямоугольников следующих типов:
1. Пустой прямоугольник.
2. Прямоугольник с заливкой.
3. Прямоугольник с размещенным в нем тексте.
Используя этот тип создадим массив, хранящий информацию о разных прямоугольниках, и используя полученный массив выведем прямоугольники на экран.
Сначала создадим тип вариантной записи.
Проанализируем, какие поля необходимы для разных вариантов прямоугольника.
Для пустого прямоугольника необходимо четыре поля для хранения координат углов прямоугольника и одно поле для хранения цвета рамки.
Для заполненного прямоугольника необходимо 4 поля для координат углов прямоугольника, поле для хранения цвета рамки, поле для хранения цвета заливки и поле для хранения стиля заливки.
Для прямоугольника с текстом необходимо 4 поля для координат углов прямоугольника, поле для хранения цвета рамки, поле для хранения цвета текста и поле для хранения самого текста.
Получается, что во всех трех вариантах присутствуют 4 координаты углов прямоугольника и цвет рамки. Следовательно эти 5 полей составляют фиксированную часть записи. Остальные поля нужны лишь в разных вариантах. Следовательно из них будут составлены альтернативные группы вариантной части записи. Для идентификации использования той или иной альтернативной группы нужно еще одно поле – поле-признак варианта. Поле-признак лучше всего делать перечисляемого типа. В нашем случае поле-признак будет иметь такой тип:
FigureType = {тип фигур}
( FTRect, {пустой прямоугольник}
FTFillRect, {заполненный прямоугольник}
FTTextInRect {текст в прямоугольнике}
);
Для определения полей нашей записи будем использовать тип TColor, который определим так:
TColor = 0..15; {Цвет}
Теперь создадим тип нашей записи:
TRect = record {Запись, хранящая информацию о прямоугольнике}
{Фиксированная часть записи}
Left,Top,Width,Height:Word; {координаты прямоугольника}
ClBorder:TColor; {Цвет рамки}
{Вариантная часть записи}
case fig:FigureType of {тип прямоугольника – поле-признак}
{ниже перечислены три альтернативные группы полей}
FTRect: (); {пустой прямоугольник не имеет
дополнительных полей}
FTFillRect: {заполненный прямоугольник имеет
два дополнительных поля}
( ClFill:TColor; {цвет заполнения}
StyleFill:Byte {стиль заполнения}
);
FTTextInRect: {текст в прямоугольнике имеет
два дополнительных поля}
( ClText:TColor; {цвет текста}
Str:String[20] {текст}
);
end;
Напишем процедуру ввода вариантной записи с клавиатуры.
{Чтение записи Rect типа TRect с клавиатуры}
procedure ReadRect(var Rect:TRect);
var
case_type :Byte; {переменная для выбора типа}
begin
With Rect do
begin
writeln;
writeln;
writeln('Введите информацию о прямоугольнике:');
{Ввод фиксированной части записи}
writeln(' Координаты верхней левой точки:');
write (' X ='); readln(Left);
write (' Y ='); readln(Top);
write (' Ширину='); readln(Width);
write (' Высоту='); readln(Height);
write (' Цвет рамки='); readln(ClBorder);
writeln;
{Ввод вариантной части записи}
writeln('Введите тип прямоугольника:');
writeln(' 1 - пустой прямоугольник');
writeln(' 2 - прямоугольник с заполнением');
writeln(' 3 - прямоугольник с текстом');
readln(case_type); {ввод номера типа}
{в зависимости от типа вводим дополнительные поля}
case case_type of
2: {прямоугольник с заполнением}
begin
fig:=FTFillRect;
write('Введите цвет заливки :'); readln(ClFill);
write('Введите стиль заливки:'); readln(StyleFill);
end;
3: {прямоугольник с текстом}
begin
fig:=FTTextInRect;
write('Введите цвет текста :'); readln(ClText);
write('Введите текст :'); readln(Str);
end;
else {пустой прямоугольник}
fig:=FTRect;
end;{case ... end}
end; {With ... end}
end; {Procedure ... end}
Напишем процедуру вывода прямоугольника на экран:
{Показ на экране прямоугольника, задаваемого записью Rect типа TRect}
procedure ShowRect(Rect:TRect);
begin
With Rect do
begin
{рисуем рамку прямоугольника}
setcolor(ClBorder);
rectangle(Left,Top,Left+Width-1,Top+Height-1);
{в зависимости от типа фигуры выводим дополнительно:}
case fig of
FTFillRect: {заполненный прямоугольник}
begin
{делаем заливку прямоугольника}
setfillstyle(StyleFill,ClFill);
bar(Left+1,Top+1,Left+Width-2,Top+Height-2);
end;
FTTextInRect: {текст в прямоугольнике}
begin
{печатаем текст в прямоугольнике}
setcolor(ClText);
OutTextXY(Left+2,Top+2,Str);
end;
end;{case ... end}
end; {With ... end}
end; {Procedure ... end}
Теперь напишем фрагмент программы с вводом и выводом массива вариантных записей:
var
r: array[1..10] of TRect;
n,i:Integer;
begin
{ввод массива записей прямоугольников}
write('Введите количество прямоугольников n=');
readln(n);
for i:=1 to n do
ReadRect(r[i]);
...
{Включение графического режима}
...
{показ массива прямоугольников}
for i:=1 to n do
ShowRect(r[i]);
...
Хранение вариантных записей в памяти компьютера
Объем памяти, занимаемый вариантной записью можно вычислить по формуле:
sizeof(вариантная_запись) = sizeof(фиксированная_часть) + sizeof(поле-признак) + Max{sizeof(альтернативная_группа1), sizeof(альтернативная_группа2) .. sizeof(альтернативная_группаN)}
то есть, объем занимаемый вариантной записью вычисляется как сумма всех объемов, занимаемых полями фиксированной части, плюс объем, занимаемый полем-признаком и плюс максимальный из объемов занимаемых полями альтернативных групп.
Для примера рассчитаем объем, занимаемый одной записью типа TRect. Сначала рассчитаем объем, занимамый всеми полями фиксированной части:
sizeof(фиксированная_часть)= sizeof(Word)*4 + sizeof(TColor) =
= 2*4+1 = 9 байт
Рассчитаем объем, занимаемый полем-признаком:
sizeof(поле-признак) = sizeof(FigureType) = 1 байт
Рассчитаем объемы, занимаемые альтернативными группами:
sizeof(альтернативная_группа FTRect) = 0
sizeof(альтернативная_группа FTFillRect) = sizeof(TColor) +
+ sizeof(Byte) = 1+1 = 2 байта
sizeof(альтернативная_группа FTTextInRect) = sizeof(TColor) +
+ sizeof(string[20]) = 1+21 = 22 байта
Максимальный объем среди альтернативных групп – у группы FTTextInRect – 22 байта.
Теперь сведем все объемы в формулу:
sizeof(вариантная_запись) =
= sizeof(фиксированная_часть) + sizeof(поле-признак) +
+ Max{sizeof(альтернативная_группа1),
sizeof(альтернативная_группа2)
...
sizeof(альтернативная_группаN)} =
= 9 + 1 + 22 = 32 байта
ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
Цель работы:
Изучить работу с массивами и файлами записей.
Общее задание:
Разработать программу, обеспечивающую ввод, хранение, обработку и вывод информации о множестве объектов заданного типа.
Информация о каждом объекте однотипная, хранится в записи. Тип объекта задается вариантом.
Размер множества объектов ограничен 20 экземплярами.
Во время работы программы множество должно хранится в виде списка, с произвольным доступом. Список необходимо реализовать при помощи одномерного массива записей (array[1..20] of Тип_записи).
Между запусками программы множество должно хранится в виде типизированного файла (File of Тип_записи).
Описание пользовательского интерфейса:
Выбор операций осуществляется пользователем при помощи меню. В меню необходимо включить следующие пункты:
1. Очистка списка
2. Просмотр списка
3. Просмотр списка по запросу
4. Загрузка данных из файла в список
5. Сохранение данных из списка в файл
6. Добавление записи в список
7. Удаление записи из списка
8. Сортировка списка
9. Выход из программы
Замечание: Пункты выделенные желтым цветом должны быть реализованы в лабораторной работе №7, а пункты выделенные голубым цветом должны быть реализованы в лабораторной работе №8.
Сдавать лабы нужно обязательно ОТДЕЛЬНО.
Тип меню задается вариантом.
Описание модульной структуры:
Программа должна содержать минимум 3 программных модуля:
1. Модуль работы с меню
2. Модуль работы со списком
3. Главный модуль
Можно из главного модуля вынести процедуры ввода/вывода записей и другие процедуры в четвертый модуль.
Задание по вариантам:
Варианты меню:
1. Способ перемещения по меню.
а) Перемещение по пунктам меню осуществляется с помощью навигационных клавиш ( и других);
б) Перемещение по пунктам меню осуществляется с помощью функциональных клавиш (в этом случае каждому пункту соответствует своя собственная функциональная клавиша);
в) Перемещение по пунктам меню осуществляется с помощью буквенных клавиш (для каждой строки клавиша своя).
2. Размещение пунктов меню
а) Вертикальное меню
б) Горизонтальное меню
Задание по вариантам по пользовательскому интерфейсу:
номер варианта Способ перемещения по меню Размещение пунктов меню
1 с помощью навигационных клавиш Вертикальное меню
2 с помощью функциональных клавиш Вертикальное меню
3 с помощью буквенных клавиш Вертикальное меню
4 с помощью навигационных клавиш Горизонтальное меню
5 с помощью функциональных клавиш Горизонтальное меню
6 с помощью буквенных клавиш Горизонтальное меню
7 с помощью навигационных клавиш Вертикальное меню
8 с помощью функциональных клавиш Вертикальное меню
9 с помощью буквенных клавиш Вертикальное меню
10 с помощью навигационных клавиш Горизонтальное меню
11 с помощью функциональных клавиш Горизонтальное меню
12 с помощью буквенных клавиш Горизонтальное меню
13 с помощью навигационных клавиш Вертикальное меню
14 с помощью функциональных клавиш Вертикальное меню
15 с помощью буквенных клавиш Вертикальное меню
16 с помощью навигационных клавиш Горизонтальное меню
17 с помощью функциональных клавиш Горизонтальное меню
18 с помощью буквенных клавиш Горизонтальное меню
19 с помощью навигационных клавиш Вертикальное меню
20 с помощью функциональных клавиш Вертикальное меню
21 с помощью буквенных клавиш Вертикальное меню
22 с помощью навигационных клавиш Горизонтальное меню
23 с помощью функциональных клавиш Горизонтальное меню
24 с помощью буквенных клавиш Горизонтальное меню
25 с помощью навигационных клавиш Горизонтальное меню
Варианты объектов, информацию о которых необходимо хранить в списке:
В каждом варианте задается тип объекта и перечень полей объекта, которые необходимо хранить в записи. Также задается тип запроса, по которому надо выводить часть списка (выводятся лишь те записи, которые удовлетворяют условию запроса):
Номер варианта Название объекта Поля объекта Тип запроса к списку записей
1 Автобус - Номер маршрута
- Количество остановок
- Названия конечных остановок Количество остановок больше 6, но меньше 12
2 Животное - Вид животного
- Место обитания
- Хищное / травоядное
- Количество особей в дикой природе Травоядные
Количество особей менее 10000
3 Фермер - ФИО фермера
- Засеваемая площадь
- Количество работников Засеваемая площадь более 100,
Количество работников более 5
4 Книга - Название книги
- ФИО автора
- Издательство
- Количество страниц Количество страниц более 300,
Издательство “Диалог-МИФИ”
5 Файл - Имя файла
- Время создания
- Дата создания
- Размер файла Размер файла больше 100 Кб,
Дата создания
10 апреля 2001 г.
6 Футболист - ФИО спортсмена
- Название клуба
- Состав (основной / запасной)
- Зарплата Название клуба “Спартак”
Состав основной
7 Трамвай - Номер трамвая
- ФИО водителя
- Номер маршрута
- Год последнего капитального ремонта Номер трамвая “4”
Год кап.ремонта – не позже 1995
8 Жилец - Адрес
- ФИО жильца
- Число членов семьи
- Занимаемая жилая площадь Занимаемая площадь менее 30 кв.метров
Число членов семьи не менее 7
9 Программист - ФИО программиста
- Языки программирования
- Стаж работы Язык программи-рования С++
Стаж работы не менее трех лет
10 Абонент - ФИО абонента
- Адрес
- Телефон
- Количество междугородных разговоров
- Сумма оплаты Сумма оплаты не менее 300 рублей
Количество звонков не более трех
11 Студент - ФИО студента
- Группа
- Средний балл за сессию
- Размер стипендии Средний балл выше 4,5
Стипендия более 150 рублей
12 Мужчина - ФИО мужчины
- Возраст
- Образование
- Среднемесячный доход
- Имеет машину (да/нет) Возраст не старше 30 лет
Среднемесячный доход не меньше 10000 рублей
13 Чемпион - ФИО чемпиона
- Страна
- В каком году был завоеван титул
- Вид спорта Страна “Россия”
Вид спорта – плавание
14 Фирма - Название фирмы
- Вид услуг
- Годовой оборот Вид услуг – торговля
Оборот – не менее 5 млн. рублей
15 Спорт - Вид спорта
- Стоимость одного комплекта инвентаря
- Количество занимающихся Количество занимающихся не менее 100000 человек
Стоимость инвентаря не более 2000 руб.
16 Оружие - Вид оружия
- Фирма-изготовитель
- Страна изготовитель Страна изготовитель – “Россия”
Вид оружия – пулемет
17 Компьютер - Марка компьютера
- Страна-изготовитель
- Фирма-изготовитель
- Себестоимость
- Цена Себестоимость не более 300 долларов
Цена – не менее 700 долларов
18 Завод - Название завода
- Выпускаемая продукция
- Адрес
- Стоимость основных фондов
- Долг перед государством Стоимость основных фондов не более 100 млн. рублей
Долг перед государством не менее 10 млн. рублей
19 Студент - ФИО студента
- Группа
- Число пропусков занятий в год по болезни
- По другим причинам Число пропусков по болезни не менее 10
Группа “ЭВМд-12”
20 Сотрудник - ФИО сотрудника
- Год рождения
- Домашний адрес
- Специальность
- Стаж работы Специальность “Программист”
Стаж – не менее 5 лет
21 Автомобиль - Марка
- Фирма-производитель
- Класс автомобиля
- Год запуска в производство Фирма-производитель “Mersedes”
Год запуска – 2000
22 Сотрудник - ФИО сотрудника
- Подразделение
- Должность
- E-mail
- Объем почты в месяц Должность – “секретарь”
Объем почты – не менее 100 Мб
23 Болезнь
- Вид болезни
- Основные симптомы
- Инкубационный период Основные симптомы – высокая температура
Период – 3 дня
24 Музыкант
- ФИО музыканта
- Жанр
- Музыкальный инструмент
- Музыкальное образование Образование – отсутсвует
Инструмент – барабан
25 Статья - Название статьи
- ФИО автора
- Название журнала
- Номер журнала
- Год издания Номер журнала – не меньше 5
Год издания - 2000
ПРИМЕР ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ
Задание:
В программе реализована лабораторная работа, задание на которую представлено выше. Вариантная часть работы имеет следующие параметры:
Задание по пользовательскому интерфейсу:
- Размещение пунктов меню - вертикальное меню
- Перемещение по пунктам меню осуществляется с помощью навигационных клавиш
Тип объекта, информацию о которых необходимо хранить в списке:
-Человек, медицинская информация о человеке
- Поля объекта:
- фамилия
- имя
- отчество
- год рождения
- группа крови
- рост
- вес
Тип запроса к списку:
– вывести список тех людей, у кого четвертая группа крови, и кто родился не раньше 1970 года.
Модульная структура:
Представленная программа содержит 3 модуля:
- Модуль Menu_Txt (файл Menu_Txt.pas) – работа с меню
- Модуль Info (файл Info.pas)- работа со списком
- Главный модуль (файл LabRec.pas).
Текст программы
Модуль Menu_Txt
Файл Menu_Txt.pas содержит модуль Menu_Txt
{Файл Menu_Txt.pas
Модуль Menu_Txt
Организация меню в текстовом режиме}
unit menu_txt;
interface
type
{пункт меню}
TItemMenu = record
str:string[76]; {строка пункта меню}
x,y:byte; {координаты начала строки внутри окна меню}
res:byte; {значение, возвращаемое при выборе пункта}
end;
{полная информация о меню}
TMenu = record
nItems:Byte; {количество пунктов}
item:array[1..10] of TItemMenu; {пункты меню}
Left,Top:integer; {координаты левого верхнего угла окна меню}
Width,Height:integer; {ширина и высота меню}
clMenu,clText:byte; {цвет меню и цвет текста}
clMarkedItem,clMarkedText:Byte; {цвет выделенного пункта
меню и цвет текста в выделенном пункте}
MarkedItem:byte; {номер выделенного пункта меню}
end;
{Очистка ВСЕГО экрана черным цветом}
procedure BlackScreen;
{создание цветного окна
Left,Top - координаты левого верхнего угла окна
Width - ширина окна
Height - высота окна
BckColor - цвет фона (цвет окна)
}
procedure ColorWindow(Left,Top,Width,Height,BckColor:Byte);
{Меню
озвращаемое значение:
0 - в случае отказа от выбора
menu.item[menu.markedItem].res - в случае выбора пункта меню
}
function MenuVert(var menu:TMenu):byte;
{показ строки текста в текущем активном окне
str - строка
x,y - координаты начала строки
TxtColor - цвет текста
BckColor - цвет фона
ЗАМЕЧАНИЕ: после вывода строки курсор перемещается в начало
выведенной строки
}
procedure ShowText(const str:string; x,y,TxtColor,BckColor:byte);
implementation
uses crt;
const
{константы кодов клавиш}
keyUp = #72; {стрелка вверх}
keyDown = #80; {стрелка вниз}
keyLeft = #75; {стрелка влево}
keyRight = #77; {стрелка вправо}
keyEnd = #79; {клавиша End}
keyHome = #71; {клавиша Home}
keyEnter = #13; {клавиша Enter}
keyEsc = #27; {клавиша Esc}
{Очистка ВСЕГО экрана черным цветом}
procedure BlackScreen;
begin
window(1,1,80,25);
TextBackground(0);
TextColor(7);
clrscr;
end;
{создание цветного окна
Left,Top - координаты левого верхнего угла окна
Width - ширина окна
Height - высота окна
BckColor - цвет фона (цвет окна)
}
procedure ColorWindow(Left,Top,Width,Height,BckColor:Byte);
begin
window(Left,Top,Left+Width-1,Top+Height-1);
TextBackground(BckColor);
clrscr;
end;
{показ строки текста в текущем активном окне
str - строка
x,y - координаты начала строки
TxtColor - цвет текста
BckColor - цвет фона
ЗАМЕЧАНИЕ: после вывода строки курсор перемещается в начало
выведенной строки
}
procedure ShowText(const str:string; x,y,TxtColor,BckColor:byte);
begin
TextBackground(BckColor); {установка цвета фона}
textcolor(txtcolor); {установка цвета текста}
gotoxy(x,y); {перемещаем курсор в позицию начало строки меню}
write(str); {выводим строку меню}
gotoxy(x,y); {перемещаем курсор в позицию начало строки меню}
end;
{Меню
Возвращаемое значение:
0 - в случае отказа от выбора
menu.item[menu.markedItem].res - в случае выбора пункта меню
}
function MenuVert(var menu:TMenu):byte;
var
c:char; {код нажатой клавиши}
i:byte; {счетчик}
begin
with menu do
begin
{готовим окно, в которое будем выводить}
ColorWindow(Left,Top,Width,Height,clMenu);
{выводим все пункты}
for i:=1 to nItems do
ShowText(item[i].str, item[i].x,item[i].y, clText,clMenu);
while true do
begin
ShowText(item[markedItem].str,
item[markedItem].x,item[markedItem].y,
clMarkedText, clMarkedItem);
{ждем нажатия, какой либо клавиши}
c:=readkey;
if c=#0 then c:=readkey;
{выделенный пункт меню делаем того же цвета что и остальные}
ShowText(item[markedItem].str,
item[markedItem].x,item[markedItem].y,
clText,clMenu);
{обработка нажатия клавиши}
case c of
keyUp: dec(markedItem);
keyDown: inc(markedItem);
keyHome: markedItem:=1;
keyEnd: markedItem:=nItems;
keyEnter: begin {нажата клавиша Enter}
MenuVert:=item[markedItem].res; {возвращается из
функции Menu код возврата выделенного
пункта }
exit; {выход из функции}
end;
keyEsc: begin {нажата клавиша Esc}
MenuVert:=0; {возвращается из функции Menu
0 - сообщение о том, что от выбора отказались}
exit; {выход из функции}
end;
end;
{Обработка особых случаев}
if markedItem<1 then markedItem:=nItems;
if markedItem>nItems then markedItem:=1;
end;
end;
end;
begin
end.
Модуль Info
Файл Info.pas содержит модуль Info
{Файл Info.pas
Модуль Info
Работа со списком записей "Медицинская информация"
}
unit Info;
interface
const
maxNInfo = 20; {максимально возможное количество записей в списке}
type
{Запись "Медицинская информация"}
MedicalInfo = record
familia : string[30]; {фамилия}
imja : string[20]; {имя}
otchestvo : string[25]; {отчество}
YearBirth : integer; {год рождения}
GroupBlood: string[5]; {группа крови}
Height : byte; {рост}
Weight : byte; {вес}
end;
{Список записей "Медицинская информация"}
ListOfPerson = record
n:byte; {количество записей в списке}
person:array [1..maxNInfo] of MedicalInfo; {массив записей}
end;
{Очистить список записей list}
procedure Clear ( var list:ListOfPerson);
{Добавить в конец списка list запись person
Возвращается true - если запись была вставлена
false - если запись не была вставлена
}
function AddPerson ( var list:ListOfPerson;
const person:MedicalInfo):boolean;
{Удалить запись номер del из списка list
Возвращается true - если запись была удалена
false - если запись не была удалена
}
function DelPerson ( var list:ListOfPerson;
const del:byte):boolean;
{Сортировка списка записей list}
procedure SortList ( var list:ListOfPerson);
{Сохранение списка записей list в файле с именем filename
Возвращается true - если список сохранен
false - если была ошибка записи в файл
}
function SaveList ( var list:ListOfPerson;
const filename:string):boolean;
{Загрузка списка записей list из файла с именем filename
Возвращается true - если список загружен
false - если была ошибка чтения
}
function LoadList ( var list:ListOfPerson;
const filename:string):boolean;
implementation
{Очистить список записей list}
procedure Clear(var list:ListOfPerson);
begin
list.n:=0;
end;
{Перестановка в списке list элементов с индексами i и j}
procedure Exchange(var list:ListOfPerson; const i,j:byte);
var
tmp:MedicalInfo;
begin
if i<>j then
begin
tmp := list.person[i];
list.person[i] := list.person[j];
list.person[j] := tmp;
end;
end;
{Добавить в конец списка list запись person
Возвращается true - если запись была вставлена
false - если запись не была вставлена
}
function AddPerson(var list:ListOfPerson;
const person:MedicalInfo):boolean;
begin
if list.n=maxNInfo then
AddPerson:=false
else
begin
inc(list.n);
list.person[list.n]:=person;
AddPerson:=true;
end;
end;
{Удалить запись номер del из списка list
Возвращается true - если запись была удалена
false - если запись не была удалена
}
function DelPerson(var list:ListOfPerson;
const del:byte):boolean;
begin
if (del<1) or (del>list.n) then
DelPerson:=false
else
begin
list.person[del]:=list.person[list.n];
dec(list.n);
DelPerson:=true;
end;
end;
{Сортировка списка записей list}
procedure SortList(var list:ListOfPerson);
var
imin:byte;
i,j:byte;
begin
with list do
begin
if list.n<2 then exit;
for i:=1 to n-1 do
begin
imin:=i;
for j:=i+1 to n do
if person[j].familia<person[imin].familia
then
imin:=j;
Exchange(list,i,imin);
end;
end;
end;
{Сохранение списка записей list в файле с именем filename
Возвращается true - если список сохранен
false - если была ошибка записи в файл
}
function SaveList(var list:ListOfPerson; const filename:string):boolean;
var
f:file of MedicalInfo;
i:byte;
begin
assign(f,filename);
{$I-}
rewrite(f);
{$I+}
if ioresult<>0
then
begin
SaveList:=false;
exit;
end;
for i:=1 to list.n do
write(f,list.person[i]);
close(f);
SaveList:=true;
end;
{Загрузка списка записей list из файла с именем filename
Возвращается true - если список загружен
false - если была ошибка чтения
}
function LoadList(var list:ListOfPerson; const filename:string):boolean;
var
f:file of MedicalInfo;
n,i:byte;
begin
assign(f,filename);
{$I-}
reset(f);
{$I+}
if ioresult<>0
then
begin
LoadList:=false;
exit;
end;
n:=FileSize(f);
if (n<0) or (n>maxNInfo)
then
begin
close(f);
LoadList:=false;
exit;
end;
Clear(list);
for i:=1 to n do
read(f,list.person[i]);
close(f);
list.n:=n;
LoadList:=true;
end;
begin
end.
Главный модуль
Файл LabRec.pas содержит главный модуль - тело программы.
{Файл LabRec.pas
Дисциплина "Программирование на языке высокого уровня"
Лабораторная работа
тема "Обработка записей"
Образец программы
Программа обеспечивает работу с записями "Медицинская
информация",
содержащими следующие поля
1. Фамилия
2. Имя
3. Отчество
4. Год рождения
5. Группа крови
6. Рост
7. Вес
Записи хранятся в списке. Список реализован через массив.
В программе предусмотрены следующие операции над списком
записей:
- Очистка массива записей
- Добавление записи в конец массива
- Удаление записи по номеру
- Сортировка записей по фамилии
- Вывод массива записей на экран
- Вывод на экран части списка
- Сохранение массива записей в файле
- Загрузка массива записей из файла
}
uses crt,menu_txt,info; {в программе кроме стандартного модуля Crt
используются наши собственные модули Menu_Txt и Info}
const
{Главное меню программы}
MainMenu: TMenu=( nItems:9; {количество пунктов}
item:( {пункты меню}
(str:' Очистка массива записей '; x:2; y:2; res:1), {1-й пункт}
(str:' Добавление записи в конец массива '; x:2; y:3; res:2), {2-й
пункт}
(str:' Удаление записи по номеру '; x:2; y:4; res:3), {3-й пункт}
(str:' Сортировка записей по фамилии '; x:2; y:5; res:4), {4-й
пункт}
(str:' Вывод массива записей на экран '; x:2; y:6; res:5), {5-й пункт}
(str:' Вывод на экран части списка '; x:2; y:7; res:8), {6-й пункт}
(str:' Сохранение массива записей в файле '; x:2; y:8; res:6), {7-й
пункт}
(str:' Загрузка массива записей из файла '; x:2; y:9; res:7), {8-й
пункт}
(str:' Выход из программы '; x:2; y:10; res:100), {9-й пункт}
(str:''; x:0; y:0; res:0) {10-й пункт}
);
Left:20; Top:5; {координаты меню}
Width:40; Height:11; {размеры окна меню}
clMenu:2; clText:14; {цвет меню и цвет текста меню}
clMarkedItem:4; clMarkedText:15; {цвет выделенного
пункта}
MarkedItem:1 {номер выделенного пункта}
);
var
persons: ListOfPerson; {список записей}
{очистка списка}
procedure ClearArray;
begin
Clear(persons);
ColorWindow(20,1,40,3,1);
ShowText('Массив очищен!',13,2,14,1);
readkey;
end;
{Вставка записи в массив записей}
procedure InsertToArray;
var
person:MedicalInfo; {вводимая запись}
begin
{вывод приглашения}
ColorWindow(1,16,80,10,3);
ShowText('Введите поля записи:',20,1,14,3);
ShowText('Фамилия : ',3,3,15,3);
ShowText('Имя : ',3,4,15,3);
ShowText('Отчество : ',3,5,15,3);
ShowText('Год рождения : ',3,6,15,3);
ShowText('Группа крови : ',3,7,15,3);
ShowText('Рост : ',3,8,15,3);
ShowText('Вес : ',3,9,15,3);
{ввод всех полей}
gotoxy(20,3);
readln(person.familia);
gotoxy(20,4);
readln(person.imja);
gotoxy(20,5);
readln(person.otchestvo);
gotoxy(20,6);
readln(person.yearbirth);
gotoxy(20,7);
readln(person.groupblood);
gotoxy(20,8);
readln(person.Height);
gotoxy(20,9);
readln(person.Weight);
if AddPerson(persons,person) {дабавляем запись в список}
then
begin {если запись добавлена}
ColorWindow(20,1,40,3,1);
ShowText('Запись в массив добавлена!',6,2,14,1);
end
else
begin {если запись не добавлена}
ColorWindow(20,1,40,3,4);
ShowText('Массив полон - добавлять некуда!',3,2,15,1);
end;
readkey;
end;
{Удалить запись из массива}
procedure DeleteFromArray;
var
del:byte; {индекс удаляемого элемента массива}
begin
{вывод приглашения}
ColorWindow(1,16,80,10,3);
ShowText('Введите индекс удаляемой записи:',10,3,14,3);
gotoxy(45,3);
readln(del);
if DelPerson(persons,del)
then
begin {если запись удалена}
ColorWindow(20,1,40,3,1);
ShowText('Запись из массива удалена!',6,2,14,1);
end
else
begin {если запись не удалена}
ColorWindow(15,1,50,3,4);
ShowText('Неверный индекс записи - запись не удалена!',3,2,15,4);
end;
readkey;
end;
{Сортировка записей в списке по фамилиям}
procedure SortArray;
begin
SortList(persons);
ColorWindow(20,1,40,3,1);
ShowText('Массив отсортирован!',13,2,14,1);
readkey;
end;
{Просмотр массива}
procedure ViewArray;
var
i:byte;{счетчик}
begin
BlackScreen;
ColorWindow(1,1,80,23,1);
{вывод шапки}
gotoxy(1,1);
write('|Фамилия |Имя |Отчество |',
'Год_рождения|Группа_крови|Рост|Вес');
gotoxy(1,2);
write('+-----------------+--------------+-----------+',
'------------+------------+----+---');
{вывод всех записей}
for i:=1 to persons.n do
begin
gotoxy(1,i+2);
write('|',persons.person[i].familia);
gotoxy(19,i+2);
write('|',persons.person[i].imja );
gotoxy(34,i+2);
write('|',persons.person[i].otchestvo );
gotoxy(46,i+2);
write('|',persons.person[i].YearBirth );
gotoxy(59,i+2);
write('|',persons.person[i].GroupBlood );
gotoxy(72,i+2);
write('|',persons.person[i].Height);
gotoxy(77,i+2);
write('|',persons.person[i].Weight);
end;
ShowText('Нажмите любую клавишу для продолжения работы!',15,23,15,4);
readkey;
end;
{Просмотр части массива - показ только тех людей,
кто родился не раньше 1970 года
и имеет 4 группу крови
}
procedure ViewPartArray;
var
i:byte;{счетчик}
begin
BlackScreen;
ColorWindow(1,1,80,23,1);
{вывод шапки}
ShowText('Список людей, имеющих 4 группу крови, '+
'родившихся не раньше 1970 года',5,1,14,1);
textcolor(15);
gotoxy(1,2);
write('|Фамилия |Имя |Отчество |Год_рождения|');
gotoxy(1,3);
write('+-----------------+--------------+-----------+------------+');
{просмотр всех записей}
for i:=1 to persons.n do
with persons.person[i] do
if (YearBirth>=1970) and (GroupBlood='4') {вывод лишь тех записей}
then {год рождения у которых <=1970, а группа крови =4}
begin
gotoxy(1,i+3);
write('|',familia);
gotoxy(19,i+3);
write('|',imja );
gotoxy(34,i+3);
write('|',otchestvo );
gotoxy(46,i+3);
write('|',YearBirth );
end;
ShowText('Нажмите любую клавишу для продолжения работы!',15,23,15,4);
readkey;
end;
{сохранение списка в файле}
procedure SaveArray;
var
filename: string;{имя файла}
begin
{ввод имени файла}
ColorWindow(1,16,80,10,3);
ShowText('Введите имя файла для записи массива:',10,3,14,3);
gotoxy(50,3);
readln(filename);
if SaveList(persons,filename) {сохранение}
then
begin {если список сохранен в файле}
ColorWindow(20,1,40,3,1);
ShowText('Массив сохранен в файле '+filename,2,2,14,1);
end
else
begin {если была ошибка сохранения}
ColorWindow(15,1,50,3,4);
ShowText('Ошибка записи в файл '+filename,3,2,15,4);
end;
readkey;
end;
{загрузка списка из файла}
procedure LoadArray;
var
filename: string;
begin
{ввод имени файла}
ColorWindow(1,16,80,10,3);
ShowText('Введите имя файла для чтения массива:',10,3,14,3);
gotoxy(50,3);
readln(filename);
if LoadList(persons,filename) {загрузка}
then
begin {если список загружен}
ColorWindow(20,1,40,3,1);
ShowText('Массив загружен из файла '+filename,2,2,14,1);
end
else
begin {если список не загружен}
ColorWindow(15,1,50,3,4);
ShowText('Ошибка при чтении из файла '+filename,3,2,15,4);
end;
readkey;
end;
{Тело программы}
begin
Clear(persons); {инициализация списка - очистка}
repeat
BlackScreen; {очистка экрана}
case MenuVert(MainMenu) of {Вызываем меню
и в зависимости от выбранного пункта выполняем
соответствующее действие}
1: ClearArray;
2: InsertToArray;
3: DeleteFromArray;
4: SortArray;
5: ViewArray;
6: SaveArray;
7: LoadArray;
8: ViewPartArray;
0,100: Exit; {выход, если выбран пункт "Выход из программы"}
{или нажат Esc}
end;
until false;
end.
Модули и текстовые файлы
Модули в Turbo Pascal
В Turbo Pascal каждый модуль представляет собой отдельный файл (один файл!), который имеет расширение .pas.
Исходный текст модуля имеет следующую структуру:
1. Заголовок
2. Интерфейсная часть
3. Исполнительная часть
4. Секция инициализации
Заголовок
Заголовок модуля состоит из ключевого слова UNIT и идентификатора – имени модуля. Модуль должен быть сохранен в файле, имя которого совпадает с именем модуля. Например, если модуль начинается со строки
Unit MyUnit;
тогда этот модуль должен быть сохранен в файле с именем MyUnit.pas
Интерфейсная часть
Дадим краткое определение:
интерфейс – это способ взаимодействия.
В данном случае интерфейс – способ взаимодействие основной программы (или другого модуля) с нашим модулем. Взаимодействие с модулем производится через использование определенных в модуле констант, типов, глобальных переменных (чего делать не надо!!!), и через вызов определенных в модуле процедур и функций.
Модульный подход подразумевает, что не все константы, типы, переменные, процедуры и функции, определенные в модуле, могут быть использованы вне модуля. Могут быть использованы лишь те из них, которые объявлены в интерфейсной части. Если в интерфейсной части нет упоминания – то такую константу, тип, переменную, процедуру или функцию можно использовать только внутри модуля – извне она недоступна.
Интерфейсная часть модуля начинается с ключевого слова interface и заканчивается перед ключевым словом implementation. Интерфейсная часть модуля содержит почти те же разделы что и основная программа:
- раздел объявления используемых модулей
- раздел объявления констант
- раздел объявления типов
- раздел объявления переменных
- раздел объявления процедур и функций
Как и в основной программе, эти разделы могут идти в любом порядке (за исключением первого), каждый из них (опять же, за исключением первого) может встречаться несколько раз, либо вообще не разу.
Заметим, что в разделе объявления процедур и функций указываются только заголовки подпрограмм.
Исполнительная часть
Если в интерфейсной части указываются только заголовки подпрограмм, (подпрограммы объявляются), то в исполнительную часть модуля включаются тела подпрограмм, (подпрограммы определяются). Исполнительная часть модуля начинается с ключевого слова implementation и заканчивается началом секции инициализации, если она есть, либо словом end с точкой. Исполнительная часть модуля содержит те же разделы что и основная программа:
- раздел объявления используемых модулей
- раздел объявления констант
- раздел объявления типов
- раздел объявления переменных
- раздел определения процедур и функций
Как и в основной программе и интерфейсной части эти разделы могут идти в любом порядке, каждый из них может встречаться несколько раз, либо вообще не разу (раздел объявления используемых модулей всегда идет первым, и встречается только один раз).
Все что объявлено в исполнительной части может быть использовано только внутри исполнительной части (!!! Обратите на это внимание !!!). С другой стороны в исполнительной части может быть использовано все, что объявлено в интерфейсной части.
Секция инициализации
Иногда перед использованием подпрограмм, включенных в модуль, требуется произвести инициализацию некоторых глобальных переменных этого модуля. Необходимые действия можно произвести в секции инициализации модуля. Операторы этой секции выполняются единственный раз в момент запуска программы. Секция инициализации размещается в самом конце модуля, начинается она словом begin, заканчивается end (с точкой). Если инициализация в модуле не требуется, то в секции помещается только end (с точкой).
Пользовательские модули для работы с текстом
Рассмотрим использование модулей в задачах обработки текстов.
Разработаем модуль, в котором соберем функции и процедуры, используемые в двух задачах:
Задача 1.
Переписать входной файл в выходной файл. При этом самое длинное слово в каждой строке выделить угловыми скобками.
Ограничение: считаем, что строки в файле не превышают нормальной длины в 70-80 символов.
Задача 2.
Дан исходный файл с текстом на русском языке. Вывести на экран содержимое исходного файла постранично. При выводе на экран выделить цветом все слова, в которых чередуются гласные/согласные.
Переписать содержимое исходного файла в выходной файл, выделяя БОЛЬШИМИ буквами все выделенные при выводе на экран слова.
Примечание: Имя входного файла вводится с клавиатуры. Имя выходного файла отличается от имени исходного файла только расширением.
Создадим модуль, в котором соберем функции по работе со словами: поиск слова в строке, поиск самого длинного слова в строке, определение, состоит ли слово из чередующихся гласных и согласных букв.
Вот этот модуль:
{Модуль Words.
Содержит функции поиска и анализа слов в строке.
}
unit Words;
interface {интерфейсная часть модуля}
{Функция FindNextWord.
Ищет в строке S следующее слово начиная с символа Start.
Если слово найдено, то возвращается True,
и возвращается индекс первого символа слова (через BeginWord)
и его длина (через LengthWord).
Если слово не найдено, возвращается False.}
function FindNextWord( const S : String;
Start : Integer;
var BeginWord : Byte;
var LengthWord : Byte) : Boolean;
{Функция FindMaxLenWord.
Ищет в строке S самое длинное слово.
Если ни одного слова в строке S не найдено, то возвращается False.
В противном случае возвращается True,
при этом через BeginMaxWord возвращается индекс
первого символа самого длинного слова,
а через LengthMaxWord - его длина.}
function FindMaxLenWord( const S : String;
var BeginMaxWord : Byte;
var LengthMaxWord : Byte
) : Boolean;
{Функция IsChereda.
Возвращает True, если S содержит строку, состоящую только
из чередующихся русских согласных и русских гласных букв.
Возвращает False в противном случае. }
function IsChereda(const S:string):Boolean;
implementation {Исполнительная часть модуля}
const
{множества символов}
SmallRusLetters : set of char = ['а'..'п','р'..'я','ё'];
BigRusLetters : set of char = ['А'..'Я','Ё'];
SmallLatLetters : set of char = ['a'..'z'];
BigLatLetters : set of char = ['A'..'Z'];
Digits : set of char = ['0'..'9'];
RusGlasn : set of char = ['а','е','ё','и','о',
'у','ы','э','ю','я',
'А','Е','Ё','И','О',
'У','Ы','Э','Ю','Я'];
var
RusLetters : set of char; {все русские буквы}
LatLetters : set of char; {все латинские буквы}
Letters : set of char; {все буквы и цифры,
т.е. те символы, из которых
могут состоять слова}
RusSoglasn : set of char; {русские согласные буквы}
{=====================================================}
{Функция IsLetter.
Возвращает True, если C является символом слова.
Возвращает False, если C является разделителем. }
function isLetter(c: char): boolean;
begin
isLetter:=c in Letters;
end;
{=====================================================}
{Функция IsRusGlasn.
Возвращает True, если C является русской гласной буквой.
Возвращает False в противном случае. }
function isRusGlasn(c: char): boolean;
begin
isRusGlasn := c in RusGlasn;
end;
{=====================================================}
{Функция IsRusSoglasn.
Возвращает True, если C является русской согласной буквой.
Возвращает False в противном случае. }
function isRusSoglasn(c: char): boolean;
begin
isRusSoglasn := c in RusSoglasn;
end;
{=====================================================}
{Функция IsChereda.
Возвращает True, если S содержит строку, состоящую только
из чередующихся русских согласных и русских гласных букв.
Возвращает False в противном случае. }
function IsChereda(const S:string):Boolean;
var
IsSogl : Boolean; {текущая буква является согласной}
IsPrevSogl : Boolean; {предыдущая буква является согласной}
i : Byte; {счетчик цикла}
len : Byte; {длина строки}
begin
len := length(S); {вычисляем длину строки}
{проверяем, состоит ли строка только из русских гласных
и согласных букв}
for i := 1 to len do
if not IsRusGlasn(s[i]) and not IsRusSoglasn(s[i]) then
begin
{если нет, то завершаем работу функции}
IsChereda := false;
exit;
end;
{начиная со второго символа слова, и до конца слова}
for i := 2 to len do
{ЭТОТ символ должен быть НЕ ТАКИМ как ПРЕДЫДУЩИЙ}
if IsRusSoglasn(s[i-1]) <> IsRusGlasn(s[i]) then
begin
{если нет, то завершаем работу функции}
IsChereda := false;
exit;
end;
IsChereda := true; {все символы чередуются}
end;
{=====================================================}
{Функция FindNextWord.
Ищет в строке S следующее слово начиная с символа Start.
Если слово найдено, то возвращается True,
и возвращается индекс первого символа слова (через BeginWord)
и его длина (через LengthWord).
Если слово не найдено, возвращается False.}
function FindNextWord( const S : String;
Start : Integer;
var BeginWord : Byte;
var LengthWord : Byte) : Boolean;
var
i : Integer; {индекс может выйти за границы 255 - поэтому Byte
использовать нельзя!!!}
Len : Byte; {длина строки}
Begin
{вычисляем длину строки}
Len := length(s);
{ищем начало слова, начиная со стартового символа строки}
i := Start;
{в цикле продвигаем i вперед по строке, до тех пор
пока не встретиться буква, или пока не кончится строка }
while not isLetter(S[i]) and (i <= Len ) do
i := i + 1;
{сейчас i указывает на первый символ найденного слова}
BeginWord := i;
{ищем конец слова}
{для этого продвигаем i вперед, до тех пор пока не встретиться
НЕ БУКВА, или пока i не выйдет за пределы строки}
while isLetter(S[i]) and ( i <= Len ) do
i := i + 1;
{сейчас i указывает на первый символ-разделитель, следующий
за словом (или i указывает на символ за пределами границ
строки).
Длину слова вычисляем как разность между индексами его
последнего и первого символов }
LengthWord := i - BeginWord;
{Если вычисленная длина слова больше 0, значит слово в строке
найдено - возвращаем True.
Иначе - слова в строке нет - возвращаем False }
if LengthWord > 0
then FindNextWord := true
else FindNextWord := false;
end;
{=====================================================}
{Функция FindMaxLenWord.
Ищет в строке S самое длинное слово.
Если ни одного слова в строке S не найдено, то возвращается False.
В противном случае возвращается True,
при этом через BeginMaxWord возвращается индекс
первого символа самого длинного слова,
а через LengthMaxWord - его длина.}
function FindMaxLenWord( const S : String;
var BeginMaxWord : Byte;
var LengthMaxWord : Byte
) : Boolean;
var
i : Integer; {индекс может выйти за границы 255 - поэтому Byte
использовать нельзя!!!}
Beg : Byte; {начало строки}
Len : Byte; {длина строки}
begin
I := 1; {начинаем поиск слов с начала строки}
LengthMaxWord := 0; {длина самого длинного слова в строке =0,
потому что еще не одного слова не нашли }
{ищем все слова в строке}
while FindNextWord(S,i,Beg,Len) do
begin
{Если найденное слово длиннее всех ранее найденных}
if len>lengthMaxWord then
begin {запоминаем начало и длину найденного слова}
lengthMaxWord:=len;
BeginMaxWord:=beg;
end;
i:=beg+len; {продолжаем поиск с символа, следующего за
концом последнего найденного слова}
end;
{если не одного слова в строке не найдено,
то длина самого длинного слова будет равна 0.
В этом случае возвращаем False.
В противном случае возвращаем True.}
if lengthMaxWord=0
then findMaxLenWord:=False
else findMaxLenWord:=True;
end;
begin {Секция инициализации}
{"собираем" множества из подмножеств }
RusLetters := smallRusLetters + bigRusLetters;
LatLetters := smallLatLetters + bigLatLetters;
Letters := RusLetters + LatLetters + Digits;
RusSoglasn := RusLetters - RusGlasn;
end.
Теперь приведем текст программы – решение первой задачи:
{
Задача 1.
Переписать входной файл в выходной файл.
При этом самое длинное слово в каждой строке
выделить угловыми скобками.
Ограничение: считаем, что строки в файле не превышают
нормальной длины в 70-80 символов.
}
uses Words; {В программе используется функция findMaxLenWord}
var
inFileName : string; {имя входного файла}
outFileName : string; {имя выходного файла}
inFile : text; {входной файл}
outFile : text; {выходной файл}
S : string; {строка, читаемая из файла}
beg : Byte; {начало самого длинного слова}
len : Byte; {длина самого длинного слова}
begin
{Ввод имен входного и выходного файлов}
write('Введите имя входного текстового файла : ');
readln(inFileName);
write('Введите имя выходного текстового файла : ');
readln(outFileName);
{Открытие входного файла на чтение}
assign(inFile, inFileName);
reset(inFile);
{Открытие выходного файла на запись}
assign(outFile, outFileName);
rewrite(outFile);
{пока не кончится входной файл}
while not eof(inFile) do
begin
{читаем из входного файла строку}
readln(inFile, s);
{если в строке найдено хоть одно слово}
if findMaxLenWord(s, beg, len) then
begin
{самое длинное слово выделяем угловыми скобками}
Insert('<',S,beg);
Insert('>',S,beg+len+1);
end;
{выводим в выходной файл измененную строку S}
writeln(outFile, s);
end;
{Закрываем входной и выходной файлы}
close(inFile);
close(outFile);
end.
Как мы видим, в этой программе используется наш модуль Words. За счет этого текст программы достаточно краток.
Теперь решим вторую задачу. В ней кроме всего прочего нужно слово переписать большими буквами. Сделаем для этого функцию и поместим эту функцию и вспомогательные функции в модуль Chars:
{Модуль Chars.
Содержит функции конверсии символов и строк.}
unit chars;
interface
{превратить маленькие буквы в большие}
function ToUpper(ch: char): char;
{превратить большие буквы в маленькие}
function ToLower(ch: char): char;
{превратить маленькие буквы в большие для строки S}
function StringToUpper(const S: string): string;
implementation
{превратить маленькие буквы в большие}
function ToUpper(ch:char):char;
begin
{Для понимания алгоритма загляни в таблицу ASCII кодов}
{Общая схема такая :
ord(ch)-ord('x') - вычисление "расстояния"
до опорного символа
+ ord('X') - вычисленное расстояние прибавляется
к новому опорному символу
chr(...) - превращения порядкового номера символа в символ
}
if ch in ['а'..'п'] then
ToUpper := chr(ord(ch) - ord('а') + ord('А'))
else if ch in ['р'..'я'] then
ToUpper := chr(ord(ch) - ord('р') + ord('Р'))
else if ch = 'ё' then
ToUpper := 'Ё'
else if ch in ['a'..'z'] then
ToUpper := chr(ord(ch) - ord('a') + ord('A'))
else
ToUpper := ch;
end;
{превратить большие буквы в маленькие}
function ToLower(ch:char):char;
begin
if ch in ['А'..'П'] then
ToLower := chr(ord(ch) - ord('А') + ord('а'))
else if ch in ['Р'..'Я'] then
ToLower := chr(ord(ch) - ord('Р') + ord('р'))
else if ch = 'Ё' then
ToLower := 'ё'
else if ch in ['A'..'Z'] then
ToLower := chr(ord(ch) - ord('A') + ord('a'))
else
ToLower := ch;
end;
{превратить маленькие буквы в большие для строки S}
function StringToUpper(const S:string):string;
var
i : Byte;
resString: string;
begin
{результат заносится в строку resString}
resString:='';
{по очереди все символы исходной строки S превращаются
в большие}
for i := 1 to length(s) do
resString := resString + ToUpper(s[i]);
{получившаяся строка возвращается}
StringToUpper := resString;
end;
begin
end.
И наконец, текст программы – решение второй задачи:
{
Задача 2.
Дан исходный файл с текстом на русском языке.
Вывести на экран содержимое исходного файла постранично.
При выводе на экран выделить цветом все слова, в которых
чередуются гласные/согласные.
Переписать содержимое исходного файла в выходной файл,
выделяя БОЛЬШИМИ буквами все выделенные при выводе на экран
слова.
Примечание: Имя входного файла вводится с клавиатуры. Имя
выходного файла отличается от имени исходного файла только
расширением.
}
uses Words, {В программе используется функция FindNextWord
и IsChereda}
Chars, {используется StringToUpper}
Crt; {используется ReadKey и др.}
{Процедура PrintFile.
Вывод содержимого файла FileName на экран постранично.
Одна страница - 20 строк.
При выводе на экран выделяются цветом все слова, в которых
чередуются гласные/согласные.}
procedure PrintFile(const FileName:string);
var
InFile : text; {входной файл}
S : string; {строка, читаемая из файла}
NumLines : LongInt; {номер строки, читаемой из файла}
NumPages : LongInt; {номер страницы, выводимой на экран}
i : Integer; {счетчик}
beg, len : byte; {начало и длина слова}
w : string; {слово}
begin
{Открытие входного файла на чтение}
assign(inFile, FileName);
reset(inFile);
{Инициализация количества прочитанных строк
и выведенных страниц}
NumLines := 0;
NumPages := 0;
{пока не кончится входной файл}
while not eof(inFile) do
begin
readln(inFile, s); {читаем из входного файла строку}
inc(NumLines); {увеличиваем номер прочитанной строки}
write(NumLines:3,'> '); {выводим номер строки на экран}
{ищем по очереди все слова}
i:=1;
while FindNextWord(s,i,beg,len) do
begin
{серым цветом выводим все разделители
перед очередным словом}
textcolor(lightgray);
write( copy(s, i, beg-i) );
{в W заносим найденное слово}
w:=copy(s,beg,len);
{если в слове W чередуются гласные и согласные}
{тогда устанавливаем ДРУГОЙ цвет вывода}
if IsChereda(w) then textcolor(yellow);
{выводим слово}
write(w);
{продолжать поиск слов...}
i:=beg+len;
end;
{разделители за последим словом выводим серым цветом}
textcolor(lightgray);
writeln(copy(s,i,length(s)-i+1));
{Если очередные 20 строк выведены - страница}
if NumLines mod 20 = 0 then
begin
{увеличиваем номер страницы}
inc(NumPages);
{выводим номер страницы }
write('======================= ');
write('Страница ', NumPages:4);
write(' =======================');
{выводим пустые строки}
writeln;
writeln;
writeln;
writeln;
{ждем нажатия какой-нибудь клавиши}
ReadKey;
end;
end;
{после последней страницы выводим сообщение
об окончании вывода}
inc(NumPages);
write('=======================');
write('Страница ', NumPages:4);
writeln('=======================');
writeln('Весь текст выведен!');
ReadKey;
{Закрываем входной файл}
close(inFile);
end;
{
Функция CreateOutFileName.
Создает и возвращает имя выходного файла путем
замены расширения в имени входного файла InFileName.}
function CreateOutFileName( const InFileName : string
) : string;
var
OutFileName: string; {имя выходного файла}
PosPoint: Byte; {позиция точки в имени входного файла}
begin
{ищем точку в имени входного файла}
PosPoint := Pos('.', InFileName);
if PosPoint = 0 then {точки в имени нет}
OutFileName := InFileName + '.'
else {точка в имени файла есть}
OutFileName := Copy(InFileName, 1, PosPoint);
{считаем, что входной файл имеет расширение отличное от OUT!!!}
OutFileName := OutFileName + 'out';
CreateOutFileName := OutFileName;
end;
{Процедура CopyText.
Копирует содержимое исходного файла InFileName
в выходной файл, выделяя БОЛЬШИМИ буквами все слова,
в которых чередуются гласные/согласные.}
procedure CopyText(const InFileName: string);
var
InFile : text; {входной файл}
OutFileName : string; {имя выходного файла}
OutFile : Text; {выходной файл}
S : string; {строка, читаемая из файла}
i : Integer; {счетчик}
beg, len : byte; {начало и длина слова}
w : string; {слово}
begin
{создаем имя выходного файла на основании имени входного}
OutFileName := CreateOutFileName(InFileName);
{Открытие входного файла на чтение}
assign(inFile, InFileName);
reset(inFile);
{Открытие выходного файла на запись}
assign(outFile, OutFileName);
rewrite(outFile);
{пока не кончится входной файл}
while not eof(inFile) do
begin
readln(inFile, s); {читаем из входного файла строку}
{ищем в строке по очереди все слова}
i:=1;
while FindNextWord(s,i,beg,len) do
begin
{выводим все разделители перед очередным словом}
write(outFile, copy(s,i,beg-i));
{в W заносим найденное слово}
w:=copy(s,beg,len);
{если в слове W чередуются гласные и согласные}
{тогда делаем все буквы этого слова большими}
if IsChereda(w) then W:=StringToUpper(W);
{выводим слово}
write(outFile, w);
{продолжать поиск слов...}
i:=beg+len;
end;
{выводим разделители за последним словом}
writeln(outFile, copy(s,i,length(s)-i+1));
end;
{закрытие файлов}
close(inFile);
close(outFile);
end;
var
inFileName : string; {имя входного файла}
begin
{Ввод имени входного файла}
write('Введите имя входного текстового файла : ');
readln(inFileName);
{Печатаем входной файл (на экране, постранично)}
PrintFile(inFileName);
{Копируем входной файл в выходной}
CopyText(InFileName);
end.
ЗАМЕЧАНИЯ:
Использование модулей позволяет улучшить качество программы, уменьшить затраты на ее разработку лишь в том случае, когда соблюдаются следующие принципы:
1. Пользователь модуля имеет полную информацию об использовании подпрограмм модуля. И при этом он не имеет никакой информации о способе реализации подпрограмм.
2. Модули должны быть, как можно меньше зависимы друг от друга (в идеале модули должны быть полностью независимы друг от друга)
Первый принцип реализуется за счет:
- разбиения констант, типов, переменных и подпрограмм модуля на те, которые необходимо открыть пользователям (их надо разместить в интерфейсной части), и на те, которые должны быть закрыты от пользователя (их надо разместить в исполнительной части);
- наиподробнейшего комментирования интерфейсной части модуля
- использование смысловых имен для констант, типов, переменных и подпрограмм.
Второй принцип реализуется за счет отказа от использования глобальных переменных – все данные, обрабатываемые в подпрограмме, должны передаваться через параметры.
Процедуры и функции
ПРОЦЕДУРЫ И ФУНКЦИИ БЕЗ ПАРАМЕТРОВ
Процедуры и функции
В языке Turbo Pascal, как и во всех других современных языках программирования, имеется возможность разбиения программы на относительно независимые части, называемые подпрограммами. Разбивают программы на подпрограммы для того, чтобы:
1. Облегчить создание и отладку программы (маленькие независимые куски программы легче создавать и отлаживать, чем одну большую программу).
2. Сократить размер исходного текста и кода программы (в программе часто имеются повторяющиеся части, и если их вынести в подпрограммы, то размер исходного текста программы уменьшится).
В разных языках программирования существуют разные правила работы с подпрограммами. Нас с вами интересует только Turbo Pascal версии 7.0. В этом языке существует два вида подпрограмм. Первый - это процедуры, второй - функции. Процедура – это подпрограмма, в которой выполняются определенные действия. Функция – это подпрограмма, в которой также выполняются определенные действия, но, в отличие от процедуры, в функции вычисляется и возвращается значение функции. Определения процедур и функций в Turbo Pascal очень похожи. Определение функций немного сложнее, чем определение процедур, поэтому мы начнем изучать работу с подпрограммами в Turbo Pascal именно с процедур.
Простейшие процедуры
Возьмем такую задачу. Необходимо ввести массив целых чисел, удалить из него минимальный элемент, вывести получившийся массив.
Данная задача имеет следующий общий алгоритм решения:
1. Ввести массив.
2. Найти индекс минимального элемента.
3. Удалить элемент с найденным индексом.
4. Вывести массив.
Таким образом, наша программа должна будет состоять из четырех относительно независимых кусков: 1-й кусок – ввод массива, 2-й кусок – поиск минимального элемента, 3-й кусок – удаление элемента, 4-й кусок – вывод массива. Сначала реализуем эту программу без использования подпрограмм:
{ Задание: ввести массив целых чисел, удалить из него минимальный элемент, вывести получившийся массив.
Реализация программы без подпрограмм.
}
Program WithoutProcedureExample;
Const {Определение констант}
maxN = 20; {Максимально возможное количество элементов
в массиве}
Type {Определение типов}
IndexEl = 1 .. maxN; {Индексы массива лежат в интервале
от 1 до maxN}
arrInt = array[IndexEl] of integer; {Массив целых чисел,
содержащий до maxN элементов}
Var {Объявление переменных}
A : arrInt; {Массив}
N : integer; {Количество элементов в массиве}
I : IndexEl; {Переменная для сканирования массива}
IndMin : IndexEl; {Номер минимального элемента массива}
begin
{1 – ввод массива}
{1.1 - ввод количества элементов}
repeat
write('Введите n:');
readln(n);
until (n >= 1) and (n <= maxN); {Из цикла выйти возможно
только тогда, когда 1<=N<=maxN}
{1.2 - ввод элементов массива поодиночке}
for i := 1 to n do
begin
write('a[', i, ']=');
readln(a[i]);
end;
{2 – поиск индекса минимального элемента}
indMin := 1;
for i := 2 to n do
if A[i] < A[indMin] then IndMin := i;
{3 - удаление элемента массива с индексом indMin}
for i := indMin to n-1 do
A[i] := A[i+1];
dec(n);
{4 – вывод массива}
writeln;
for i := 1 to n do
write(A[i]:3);
writeln;
end. {Конец программы WithoutProcedureExample}
Теперь продемонстрируем на этой же задаче решение с использованием подпрограмм.
Напрашивается мысль, а не разбить ли нашу программу на подпрограммы таким образом: 1-я подпрограмма – ввод массива, 2-я подпрограмма – поиск минимального элемента, 3-я подпрограмма – удаление элемента, 4-я подпрограмма – вывод массива. Сделаем это, причем будем использовать в программе простейшие подпрограммы-процедуры – так называемые процедуры без параметров.
{ Задание: ввести массив целых чисел, удалить из него минимальный элемент, вывести получившийся массив.
Реализация с использованием процедур без параметров.
}
Program SimpleProcedureExample;
Const {Определение констант}
maxN = 20; {Максимально возможное количество элементов
в массиве}
Type {Определение типов}
IndexEl = 1 .. maxN; {Индексы массива лежат в интервале
от 1 до maxN}
arrInt = array[IndexEl] of integer; {Массив целых чисел,
содержащий до maxN элементов}
Var {Объявление переменных}
A : arrInt; {Массив}
N : integer; {Количество элементов в массиве}
I : IndexEl; {Переменная для сканирования массива}
IndMin : IndexEl; {Номер минимального элемента массива}
{Определение процедур}
{==========================================}
{ReadArray - процедура ввода массива с клавиатуры}
procedure ReadArray;
begin
{1 - ввод количества элементов}
repeat
write('Введите n:');
readln(n);
until (n >= 1) and (n <= maxN);
{2 - ввод элементов массива поодиночке}
for i := 1 to n do
begin
write('a[', i, ']=');
readln(a[i]);
end;
end; {Конец процедуры ReadArray}
{==========================================}
{FindIndMin – процедура поиска индекса минимального элемента}
procedure FindIndMin;
begin
{Ищем индекс min элемента}
indMin := 1;
for i := 2 to n do
if A[i] < A[indMin] then IndMin := i;
end; {Конец процедуры FindIndMin}
{==========================================}
{DeleteMin – процедура удаления минимального элемента}
procedure DeleteMin;
begin
{ Удаляем элемент массива с индексом indMin}
for i := indMin to n-1 do
A[i] := A[i+1];
dec(n);
end; {Конец процедуры DeleteMin}
{==========================================}
{PrintArray – процедура вывода массива на экран}
procedure PrintArray;
begin
{ Выводим массив}
writeln;
for i := 1 to n do
write(A[i]:3);
writeln;
end; {Конец процедуры PrintArray}
{Основная часть программы}
begin
{1 – ввод массива}
ReadArray;
{2 – поиск индекса минимального элемента}
FindIndMin;
{3 – удаление элемента}
DeleteMin;
{4 – вывод массива}
PrintArray;
end. {Конец программы SimpleProcedureExample}
Этот пример показывает, как сделать программу с использованием процедур без параметров. Для этого необходимо задачу разбить на относительно независимые куски. Затем каждый из этих кусков оформить в виде отдельной процедуры, а из основной части программы эти процедуры необходимо вызвать. Заметим, что все используемые в процедурах переменные и типы должны быть определены и объявлены выше определения процедур.
Правила определения процедуры без параметров:
1. Из текста программы вырезается нужный кусок и переносится выше основной части программы (выше первого Begin).
2. Этот кусок текста программы заключается в операторные скобки Begin … End;.
3. Перед этим куском вставляется строка:
procedure имя_процедуры; ,
где имя_процедуры – это идентификатор.
Замечания:
1. Правила структурного программирования требуют, чтобы каждая процедура (и функция) была пояснена достаточным (ясным и полным) комментарием, который ставится перед самой процедурой.
2. Имя процедуры (и функции) должно быть смысловым. Заметим, что по отношению к процедурам (и функциям) это требование необходимо выполнять всегда (имеется в виду, что по отношению к именам переменных это требование иногда можно игнорировать, а вот по отношению к именам процедур и функций это требование игнорировать нельзя никогда).
3. Программу разбивают на подпрограммы в первую очередь для того, чтобы облегчить ее разработку и отладку. Облегчение основывается на том, что во время разработки и отладки приходится иметь дело не с “монстром” длиной в сотни и тысячи строк, а с набором независимых подпрограмм небольшого объема. Подпрограмму можно считать небольшой, если ее исходный текст не превышает 40-60 строк. В этом случае подпрограмма целиком помещается на одной странице распечатки. Еще лучше, если подпрограмма целиком помещается на экране компьютера - в этом случае ее текст не должен превышать 20 строк.
4. В тексте программы подпрограммы должны быть отделены друг от друга визуально. Обычно для этой цели между двумя подпрограммами вставляют не меньше двух пустых строк. Иногда к пустым строкам добавляют строки комментариев, подобных таким {=========================================}.
Вызов процедур
Для того чтобы процедура выполнила определенные в ней действия, ее нужно вызвать. Для вызова процедуры используется оператор процедуры. Оператор процедуры представляет собой имя вызываемой процедуры или функции.
Выполнение оператора процедуры приводит к передаче управления на первую строку тела процедуры.
После этого выполняются операторы, составляющие тело процедуры. Когда будет выполнен последний оператор тела подпрограммы, управление возвращается в точку вызова подпрограммы - на оператор, следующий за оператором процедуры.
Пример:
{1 } program CallProcedure;
{2 } procedure HiWorld;
{3 } begin
{4 } Writeln('Привет,мир!');
{5 } Writeln('Hi World!');
{6 } end;
{7 }
{8 } begin
{9 } Writeln('Это начало');
{10 } HiWorld;
{11 } Writeln('Это конец');
{12 } end.
После запуска этой программы управление передается на строку
{8 } begin – начало программы.
Затем выполняется оператор процедуры
{9 } Writeln('Это начало'); - выводится строка ‘Это начало!’
Затем выполняется оператор процедуры
{10 } HiWorld; - управление передается в процедуру HiWorld на строку
{3 } begin – начало процедуры HiWorld.
Затем выполняется оператор процедуры
{4 } Writeln('Привет,мир!'); - выводится строка ‘Привет, мир!’
Затем выполняется оператор процедуры
{5 } Writeln('Hi World!'); - выводится строка ‘Hi, World!’
Следующая строка
{6 } end; - возвращает управление из процедуры HiWorld.
Управление передается в точку вызова процедуры, на следующую за оператором процедуры строку
{11 } Writeln('Это конец'); - выводится строка ‘Это конец!’
Следующая строка
{12 } end. – возвращает управление из программы – программа завершает свою работу.
Глобальные и локальные переменные
Процедуры используются для борьбы со сложностью программ. Разбиение программы на процедуры позволяет разрабатывать (и отлаживать) программу по частям. В единое целое программа связывается двумя механизмами: вызовом процедур и общими переменными. Через вызов процедур производится передача управления в процедуры, а через общие переменные производится передача данных. Общие переменные называют глобальными переменными. Полувековая практика программирования показала, что сложность программы в целом зависит не только от сложности используемых алгоритмов и количества строк в тексте программы, от количества процедур и функций, но и от количества глобальных переменных. Чем больше глобальных переменных, тем более связанными являются процедуры: в одних процедурах значения инициализируются, в других изменяются, в третьих - используются. Причем любая глобальная переменная может быть модифицирована или использована в любой процедуре. Поэтому со временем (в 60-70 гг.) пришли к идее сократить до минимума, в идеале до 0, количество глобальных переменных. Первой альтернативой глобальным переменным являются локальные переменные.
Локальные переменные объявляются, инициализируются и используются только в пределах одной процедуры или функции.
Рассмотрим ранее приведенный пример. В нем используется 4 глобальные переменные:
Var {Объявление глобальных переменных}
A : arrInt; {Массив}
N : integer; {Количество элементов в массиве}
I : IndexEl; {Переменная для сканирования массива}
IndMin : IndexEl; {Номер минимального элемента массива}
В программе определено 4 процедуры:
{1 – ввод массива}
ReadArray;
{2 – поиск индекса минимального элемента}
FindIndMin;
{3 – удаление элемента}
DeleteMin;
{4 – вывод массива}
PrintArray;
Рассмотрим использование всех глобальных переменных.
Переменная A – массив. Элементы массива вводятся в процедуре ReadArray, массив используется в процедурах FindIndMin и PrintArray и изменяется в процедуре DeleteMin. То есть можно сказать, что значение массива A передается из процедуры ReadArray в процедуру FindIndMin, затем в DeleteMin, где он изменяется, и измененное значение передается в PrintArray. Следовательно, переменную A сделать локальной нельзя – она должна быть глобальной.
Переменная N – количество элементов в массиве. Значение переменной вводится в процедуре ReadArray, используется в процедурах FindIndMin и PrintArray и изменяется в процедуре DeleteMin. Следовательно, переменную N, так же, как и массив A, сделать локальной нельзя – она должна быть глобальной.
Переменная I – переменная для сканирования массива. Эта переменная инициализируется, изменяется и используется в каждой из четырех процедур. Между процедурами значение этой переменной не передается. Следовательно, переменную N можно сделать локальной.
Переменная IndMin – индекс минимального элемента массива. Эта переменная получает значение в процедуре FindIndMin и используется в процедуре DeleteMin. Следовательно, ее нельзя сделать локальной – она должна быть глобальной.
Таким образом, из четырех переменных одну можно (и нужно) сделать локальной.
Объявление глобальных и локальных переменных
Глобальные переменные объявляются, вне какой либо процедуры, в разделе VAR. После объявления глобальная переменная доступна (то есть может быть использована) во всех процедурах, описанных ниже.
В нашем примере все четыре переменные объявлены как глобальные, они доступны во всех четырех процедурах.
Локальные переменные объявляются внутри процедуры (или функции), в разделе VAR.
Замечание: если в подпрограмме объявлена локальная переменная, имя которой совпадает с именем глобальной переменной, то внутри этой подпрограммы глобальная переменная будет недоступна. Говорят, что локальная переменная перекрывает одноименную глобальную переменную.
Для примера объявим переменную I как локальную переменную внутри процедуры PrintArray:
{PrintArray – процедура вывода массива на экран}
procedure PrintArray;
Var {Объявление локальных переменных}
I : IndexEl; {Счетчик цикла – локальная переменная}
begin
{ Выводим массив}
writeln;
for i := 1 to n do
write(A[i]:3);
writeln;
end; {Конец процедуры PrintArray}
Функции без параметров
Как говорилось ранее, в Turbo Pascal существует два вида подпрограмм – процедуры и функции. Функции отличаются от процедур тем, что в них вычисляется и возвращается значение. Процедуру можно превратить в функцию, если в ней вычисляется какое-то (желательно одно единственное) значение. При этом превращении сокращается количество глобальных переменных, через которые передаются данные из процедуры (и это очень хорошо).
Проанализируем ранее рассмотренную задачу. В ней имеется 4 процедуры:
{1 – ввод массива}
ReadArray;
{2 – поиск индекса минимального элемента}
FindIndMin;
{3 – удаление элемента}
DeleteMin;
{4 – вывод массива}
PrintArray;
В функцию можно (и нужно) переделать процедуру FindIndMin – единственным действием в этой процедуре является вычисление индекса минимального элемента массива.
После превращения процедуры в функцию эта подпрограмма примет такой вид:
{FindIndMin –функция поиска индекса минимального элемента}
{Возвращаемое значение – индекс минимального элемента}
Function FindIndMin:IndexEl;
Var
Ind : IndexEl; {Локальная переменная, в которой хранится
индекс минимального элемента массива
до возвращения из функции}
I : IndexEl; {Локальная переменная, счетчик цикла}
begin
{Ищем индекс минимального элемента}
Ind := 1;
for i := 2 to n do
if A[i] < A[ind] then Ind := i;
FindIndMin := Ind; {Функция возвращает
найденный индекс}
end; {Конец функции FindIndMin}
Правила определения функций без параметров (из процедуры без параметров):
1. В процедуре определяется локальная переменная, в которой хранится вычисляемый в этой процедуре параметр. Эта переменная в процедуре заменяет соответствующую ей глобальную переменную.
2. Слово Procedure заменяется словом Function.
3. После имени функции вставляется двоеточие и тип возвращаемого значения.
4. В конце тела функции необходимо присвоить имени функции значение локальной переменной, хранящей вычисленный параметр (смотри пункт 1).
Вызов функции
Для того чтобы функция выполнила определенные в ней действия, ее нужно вызвать. Для вызова функции используется оператор процедуры, в тексте программы пишется имя этой функции.
Если мы хотим сохранить значение, возвращаемое функцией, то при ее вызове мы должны присвоить возвращенное из функции значение какой-нибудь переменной.
Пример:
Выведем индекс минимального элемента массива. Для этого воспользуемся определенной выше функцией FindIndMin.
…
Var
IndexMinEl : IndexEl; {Локальная переменная, в которую
занесем возвращенное из функции FindIndMin значение}
…
begin
…
{Ищем индекс минимального элемента}
IndexMinEl := FindIndMin;
{Выводим на экран индекс минимального элемента массива}
Writeln(‘Минимальный элемент массива имеет индекс = ’,
IndexMinEl);
…
Предположим, что значение, возвращенное функцией, нужно использовать только один раз, для вывода его на экран. Тогда можно обойтись и без переменной IndexMinEl. Тогда текст примера сократится до такого куска:
…
begin
…
{Ищем индекс минимального элемента и выводим его на экран}
Writeln(‘Минимальный элемент массива имеет индекс = ’,
FindMinEl);
…
Выполнение функций от выполнения процедур отличается только тем, что после окончания работы функции ее результат заносится в соответствующую переменную.
Пример: Вычислим значение тангенса по введенному значению угла в градусах.
{1 } program CallFunction;
{2 } var
{3 } x : real; {Значение введенного угла в градусах}
{4 }
{5 } function tg:real;
{6 } var
{7 } xRad : Real; {Значение угла в радианах}
{8 } begin
{9 } xRad := x * Pi / 180.0; {Перевод градусов в радианы}
{10 } tg := sin(xRad) / cos(xRad);
{11 } end;
{12 }
{13 } var
{14 } y : real;
{15 } begin
{16 } Write('Введите x = ');
{17 } Read(x);
{18 } y := tg;
{19 } Writeln( 'tg(', x:0:2, ')=', y:0:4);
{20 } end.
Эта программа начинает свою работу со строки
{15 } begin
Затем выполняется
{16 } Write('Введите x = ');
и
{17 } Read(x);
Затем в строке
{18 } y := tg; - вызывается функция tg, в результате чего управление передается на строку
{8 } begin
Затем выполняется
{9 } xRad := x * Pi / 180.0; {Перевод градусов в радианы}
Затем в строке
{10 } tg := sin(xRad) / cos(xRad); - вычисляется значение тангенса, которое в строке
{11 } end; - возвращается в точку вызова функции tg – в строку
{18 } y:=tg; -где переменной Y присваивается возвращаемое из функции значение тангенса.
Следующей строкой выполняется
{19 } Writeln( 'tg(', x:0:2, ')=', y:0:4);
И, наконец, в строке
{20 } end. - управление из программы возвращается операционной системе – программа завершает свою работу.
Пример использования процедур и функций без параметров
Мы рассмотрели правила оформления и использования подпрограмм (т.е. процедур и функций) без параметров. Теперь используем выше полученные знания для решения следующей задачи.
Необходимо посчитать, сколько разных элементов хранится в массиве.
Пример: массив 1 4 3 2 4 3 1 3 5
разные элементы 1 4 3 2 5
всего их 5
Вот текст программы:
{Подсчитать, сколько разных элементов хранится в массиве.
Одномерный массив целых чисел. Количество элементов от 1 до 20.
В программе использовать процедуры и функции без параметров.
До минимума постараться сократить использование глобальных переменных.
}
Program SimpleFunctionExample;
Const
maxNumEl = 20; {Максимально возможное количество
элементов в массиве}
Type
IndexElement = 1 .. maxNumEl; {Индексы массива}
ArrayInteger = array[IndexElement] of integer; {Массив
целых чисел}
Var {*** Объявление глобальных переменных ***}
Arr : ArrayInteger; {Обрабатываемый массив}
NumEl : integer; {Количество элементов в обрабатываемом
массиве}
{*** Определение процедур и функций: ***}
{==========================================}
{ReadArray - процедура ввода массива с клавиатуры}
{Данные вводятся в массив Arr. В переменную NumEl заносится количество элементов в массиве Arr}
procedure ReadArray;
var
i : IndexElement; {*Счетчик цикла*}
begin
writeln;
{*Ввод количества элементов*}
repeat
write('Введите количество элементов в массиве:');
readln(NumEl);
until (NumEl >= 1) and (NumEl <= maxNumEl);
{*Ввод элементов массива*}
write('Введите элементы массива : ');
for i := 1 to NumEl do
read(Arr[i]);
end; {*Конец процедуры ReadArray*}
{==========================================}
{PrintArray - процедура вывода массива на экран}
{Данные берутся из массива Arr. В переменной NumEl хранится количество элементов в массиве Arr}
procedure PrintArray;
var
i : IndexElement; {*Счетчик цикла*}
begin
writeln;
write('Массив : ');
for i := 1 to NumEl do
write(Arr[i]:3);
writeln;
end; {*Конец процедур PrintArray*}
{==========================================}
{NumberOfDifferentElements - функция, вычисляющая количество различных элементов в массиве.}
{Данные берутся из массива Arr. В переменной NumEl хранится количество элементов в массиве Arr}
Function NumberOfDifferentElements:integer;
var
i, j : IndexElement; {*Счетчики циклов*}
num : integer; {Количество разных элементов}
isDifferent : boolean; {Элемент является отличным
от все предыдущих}
begin
{Для подсчета количества разных элементов массива используется
следующий алгоритм:
- количество различных элементов обнуляем;
- начиная с первого элемента, по очереди берем все элементы
и сравниваем их со всеми предшествующими. Если взятый
элемент равен хотя бы одному из предшествующих, то этот
элемент не является новым - мы такой уже учли;
- если же он ни одному из предшествующих не равен, то
увеличиваем количество РАЗЛИЧНЫХ элементов на 1.}
num := 0;
for i := 1 to NumEl do
begin
isDifferent := true; {i-ый элемент является отличным
от предыдущих}
for j := i - 1 downto 1 do
if Arr[i] = Arr[j] then
begin
isDifferent := false; {i-ый элемент совпадает}
break; {с одним из предыдущих}
end;
if isDifferent then num := num + 1;
end;
NumberOfDifferentElements := num; {*Возвращаем
вычисленное количество разных элементов*}
end; {*Конец функции NumberOfDifferentElements*}
{*Тело программы*}
begin
{*Вводим массив Arr*}
ReadArray;
{*Выводим массив Arr*}
PrintArray;
{*Вычисление и вывод количества различных элементов массива*}
Write('В введенном массиве различных элементов : ');
writeln(NumberOfDifferentElements);
end. {*Конец программы *}
В данном примере показан более-менее “правильный” стиль оформления исходного текста программы и его комментирования.
Комментарии, помеченные символами *** ***, в реальной программе не пишутся. Здесь они вставлены по причине того, что этот текст - учебный пример.
Комментарии, помеченные символами * * , в реальной программе могут писаться или не писаться, в зависимости от требований к качеству и количеству комментариев.
Комментарии, не помеченные никакими значками, писать нужно ОБЯЗАТЕЛЬНО, если этот исходный текст программы в дальнейшем (спустя какое-то время) кто-то будет читать.
Одномерные Массивы. Операции с Массивами
ВВЕДЕНИЕ В МАССИВЫ
Понятие массива
Чтобы определить понятие “массив”, сначала необходимо обратиться к понятию “простая переменная”.
Простая переменная - это одно значение, имеющее имя и занимающее одну ячейку памяти. Размер этой ячейки зависит от типа переменной.
Например:
Var
X : Real; {Простая переменная X, занимает 6 байт памяти}
N : Integer; {Простая переменная N, занимает 2 байта памяти}
Обращение к простой переменной производится через ее имя.
Например:
X := 10.4; {X присвоили значение 10.4}
N := round(X) + 5; {N присвоили значение округленного
до целого X (а это 10) + 5= 10+5=15}
Массив, в отличие от простой переменной, представляет собой не одно значение, а множество значений, объединенных одним именем. В языке Turbo Pascal все значения из этого множества должны иметь один и тот же тип.
Каждое из значений массива называется элементом массива.
Доступ к элементам массива производится посредством указания имени массива и номера элемента массива, заключенного в квадратные скобки.
Номер элемента массива называется индексом элемента массива.
Использование элемента массива не отличается от использования простой переменной, имеющей тот же тип, что и элемент массива.
В Turbo Pascal массив объявляется при помощи ключевого слова array, после которого в квадратных скобках указываются границы индексов: верхняя, а после двух точек нижняя. После ключевого слова of, стоящего за квадратными скобками, указывается тип элементов массива.
Пример определения массивов:
Var
A : Array [1..10] of integer; {Массив A, состоящий
из 10 элементов целого типа
с индексами от 1 до 10}
B : Array [5..8] of real; {Массив B, состоящий
из 4 элементов вещественного
типа с индексами от 5 до 8}
Пример работы с массивами:
Begin
A[1] := 3; {В элемент массива A с индексом 1 записали число 3}
A[4] := A[1] + 1; {В элемент массива A с индексом 4 записали
число 3+1=4}
B[5] := 0.111; {В элемент массива B с индексом 5 записали
число 0.111}
B[ A[1] + A[4] ] := B[5] * 2; {В элемент массива B
с индексом 7 (A[1]+A[4]=3+4=7) записали число 0.222}
End.
Индексы массива
В качестве индекса массива можно использовать любой порядковый тип, кроме типа Longint. Напомним, что порядковый тип – это тип, все значения которого можно перечислить. К таким типам относятся все целые типы (integer, shortint, longint, byte, word), все логические (boolean, wordbool, longbool, bytebool), символьный тип (char), перечисляемые типы и типы-диапазоны.
Примеры использования в качестве индексов порядковых типов:
Var {Примеры объявления массивов}
A : Array [Byte] of integer; {Массив A, состоящий из 256
элементов, нижняя граница индекса 0, верхняя 255}
B : Array [Char] of real; {Массив B, состоящий из 256
элементов, нижняя граница индекса #0(символ с кодом 0),
верхняя граница индекса #255(символ с кодом 255)}
I : Byte; {Переменная, используемая как индекс массива A}
C : Char; {Переменная, используемая как индекс массива B}
Begin {Примеры обращения к элементам массива}
A[45] := 0; {В элемент массива A, имеющий индекс 45,
записали 0 }
B[‘t’] := 2.4; {В элемент массива B, имеющий индекс ‘t’,
записали 2.4}
I := 200; {i присвоили значение 200 }
C := ’#’; {c присвоили значение ‘#’ }
A[i] := 23400; {В элемент массива A, имеющий индекс i=200,
записали 23400}
B[c] := 123.456; {В элемент массива B, имеющий индекс c=’#’,
записали 123.456}
End.
Обычно в качестве индекса используют диапазон значений какого-либо перечисляемого типа.
Например:
Var {Примеры объявления массивов}
C : Array [-10..5] of integer; {Массив C, состоящий из
16 элементов, нижняя граница индекса -10, верхняя 5}
D : Array [‘A’..’Z’] of char; {Массив D, состоящий из
26 элементов, нижняя граница индекса ’A’,
верхняя граница индекса ‘Z’}
j : -10..5; {Переменная, используемая как индекс массива C}
c1 : ‘A’..’Z’; {Переменная, используемая как индекс
массива D}
k : integer; {Эту переменную можно использовать в качестве
индекса массива C, т.к. –10..5 – это диапазон
значений целого типа}
c2 : char; {Эту переменную можно использовать в качестве
индекса массива D, т.к.’A’..’Z’ – это диапазон
значений символьного типа}
begin {Примеры обращения к элементам массивов}
C[-4] := 3;
D[‘F’] := ’%’;
J := 4; C[j] := -10;
c1 := ’R’; D[c1] := ’q’;
K := -3; C[k] := 80;
c2 := ’G’; D[c2] := ’Й’;
end.
Чаще же всего используют диапазон значений целого типа, причем нижний индекс обычно берут равным 1.
Например:
Var
E: Array [1..10] of integer; {Массив E, состоящий
из 10 элементов, нижняя граница индекса 1,
верхняя 10}
Представление массива в памяти
Элементы массива размещаются в памяти в последовательных ячейках. Массив занимает количество байт, равное произведению количества элементов массива на размер одного элемента:
SizeOfArray = NumElement * SizeOfElement
где SizeOfArray – размер массива
NumElement – количество элементов в массиве
SizeOfElement – размер одного элемента
Адрес первого (по порядку) элемента массива является адресом массива (будем обозначать его AdrArray). Адрес i-го элемента массива (его будем обозначать AdrI) можно вычислить по формуле:
AdrI = AdrArray + (i – нижняя_граница_индекса) * SizeOfElement
Для примера рассмотрим массив A, определенный ниже:
A : Array [5..8] of Real;
Нижняя граница индекса этого массива 5. Первый (по порядку) элемент массива - A[5]. Допустим, его адрес 100. ( Adr5 = 100 )
Поскольку элементы имеют тип Real, то каждый элемент занимает 6 байт памяти. Вычислим адреса остальных элементов массива
Adr6 = 100 + (6-5)*6 = 100 + 1*6 = 106
Adr7 = 100 + (7-5)*6 = 100 + 2*6 = 112
Adr8 = 100 + (8-5)*6 = 100 + 3*6 = 118
Графически покажем взаимное расположение элементов этого массива:
Адрес элемента Элемент
100 A[5]
106 A[6]
112 A[7]
118 A[8]
Замечание: один массив может занимать в памяти не более 65520 байт. Нельзя, например, определить такой массив C:
Var
C: array[1..50000] of integer;
- каждый элемент этого массива занимает в памяти 2 байта, элементов 50000, значит, весь массив занимает 100000 байт > 65520 байт.
Пользовательский тип - массив
В программе можно определить тип массива, с тем чтобы в дальнейшем использовать его для определения переменных типа массива.
Пример:
Type
Arr = array[1..20] of integer; {Определили тип массива
целых чисел, содержащего 20 элементов}
Var
A, B : Arr; {A и B – массивы целых чисел, содержащие
по 20 элементов}
Дальше с массивами A и B можно работать, как с обычными массивами:
A[3] := 2;
B[4] := A[3];
и т.д.
Кроме типа массива, в программе можно определить и специальный тип для индексов. Этот тип должен быть интервальным.
Пример:
Type
IndexEl = 1 .. 20; {Тип индекса элемента}
Arr = array[IndexEl] of integer; {Тип массива целых чисел,
содержащего 20 элементов}
Var
A, B : Arr; {A и B – массивы целых чисел, содержащие
по 20 элементов}
i, j : IndexEl; {Переменные, используемые для указания
индекса элемента}
ОСНОВНЫЕ АЛГОРИТМЫ
Общие замечания
Алгоритмы обработки массивов включают в себя, как правило, последовательную обработку каждого из элементов массива. Такая последовательная обработка называется сканированием массива, и для ее реализации удобнее всего использовать цикл for. Например, фрагмент программы, выполняющий подсчет суммы элементов массива, имеет такой вид:
S := 0; {Значение суммы S обнуляем}
For I := 1 to N do {Проходим по всем N элементам массива}
S := S + a[i]; {Прибавляя к сумме S значение i-го элемента}
По сложившейся традиции, переменная, используемая в качестве счетчика цикла сканирования элементов массива, называется I (Index). Если в программе требуется не одна, а две переменные-счетчики, то им дают имена i и j. Если же требуется более двух переменных-счетчиков, то первым двум дают имена i и j, а остальным, как правило, дают тоже однобуквенные имена (например, k, l, z и т.д.). Все эти переменные должны иметь тип, совместимый с типом индекса элемента массива.
В целом же при работе с одномерными массивами нужны:
а) константы:
Const
maxN = 20; {Максимальное количество элементов в массиве}
б) типы:
Type
IndexEl = 1 .. maxN; {Тип индекса элемента}
arrInt = array[IndexEl] of integer; {Тип массива
целых чисел}
в) переменные:
Var
A : arrInt; {Обрабатываемый массив}
N : integer; {Количество используемых элементов в массиве}
I : IndexEl; {Счетчик, используемый для сканирования}
Замечание:
1. Знаком … будем обозначать, что некоторая часть исходного текста программы пропущена.
2. Если в алгоритме будут нужны еще какие-то переменные, то они будут указаны дополнительно.
Ввод/вывод массива
Задача 1: Ввод массива с клавиатуры.
Алгоритм состоит из двух пунктов:
1 . Ввод количества элементов.
2 . Ввод элементов массива поодиночке в цикле.
Фрагмент программы:
…
{1 - ввод количества элементов}
repeat
write('Введите n:');
readln(n);
until ( n >= 1 ) and ( n <= maxN );
{2 - ввод элементов массива поодиночке}
for I := 1 to n do
begin
write('a[', i, ']');
readln(a[i]);
end;
…
Задача 2: Заполнение массива случайными числами.
Алгоритм состоит из трех пунктов:
1 . Перезапустить генератор случайных чисел.
2 . Ввести количество элементов n (или сгенерировать
случайное значение n).
3 . Сгенерировать значения для всех элементов.
Фрагмент программы:
…
{1 - перезапускаем генератор случайных чисел}
randomize;
{2 - генерируем случайное значение n}
n := random(maxN);
{3 - генерируем n элементов массива}
for I := 1 to n do
a[i] := random(100); {Каждый элемент примет значение
из интервала 0..99}
…
Задача 3: Вывод массива.
Алгоритм состоит из двух пунктов:
1. Вывод имени массива.
2. Вывод массива по элементам.
Фрагмент программы:
…
{1 - вывод имени массива}
writeln('Массив А[', n, ']');
{2 - вывод элементов массива}
for I := 1 to n do
writeln('A[', i, ']=', a[i]);
…
Использование генератора псевдослучайных чисел
Если в программе требуется использовать случайную последовательность чисел, тогда используют генератор псевдослучайных чисел. Перед использованием генератора псевдослучайных чисел его рекомендуется запустить – для этого используется Randomize. Для получения очередного случайного числа используется Random.
Randomize - инициализирует (запускает) генератор случайных чисел случайным значением (случайное значение зависит от момента перезапуска, т.е. от времени).
Random(Num) - возвращает случайное целое число, находящееся в интервале 0 .. (Num-1). (Например, если Num=100, то Random возвращает числа в интервале от 0 до 99).
Если Num<=0, то Random всегда будет возвращать 0.
Чтобы получить значения в интервале, отличном от [0..Num-1], необходимо к значению, возвращаемому Random, прибавить смещение начала интервала.
Пример 1: необходим интервал [-50 .. 50].
Длина интервала 101, смещение начала интервала –50.
random(101) - 50
Пример 2: необходим интервал [20 .. 30].
Длина интервала 11, смещение начала интервала 20.
random(11) + 20
Пример 3: необходим интервал [-1000 .. -500]
Длина интервала 501, смещение начала интервала –1000.
random(501) - 1000
Вычисление суммы и среднего арифметического элементов массива
Задача 4: Подсчитать сумму элементов массива.
Алгоритм содержит два пункта:
1. Сумма S=0.
2. Проход по всем элементам массива и прибавление их значений к сумме S.
Приведем полный текст программы – решение этой задачи:
{Пример обработки одномерного массива}
{ Задание: Ввести массив. Подсчитать сумму элементов массива.}
Program SumExample;
Const {Определение констант}
maxN = 20; {Максимально возможное количество элементов
в массиве}
Type {Определение типов}
IndexEl = 1 .. maxN; {Индексы массива лежат в интервале
от 1 до maxN}
arrInt = array[interval] of integer; {Массив целых чисел,
содержащий до maxN элементов}
Var
A : arrInt; {Массив}
N : interval; {Размерность массива}
I : IndexEl; {Переменная для сканирования массива}
S : integer; {Сумма элементов массива}
Begin
{ Ввод массива с клавиатуры }
write(‘Введите n=’);
read(n); {Ввод количества элементов}
for I := 1 to n do
read(A[i]); {Ввод самих элементов}
{Подсчет суммы элементов массива}
{1} s:=0;
{2} for I := 1 to n do
s := s + A[i];
{Вывод полученного значения суммы}
writeln(‘сумма элементов массива S=’, S);
end. {Конец программы}
Задача 5: Вычислить среднее арифметическое элементов массива.
Алгоритм содержит три пункта. Первые два совпадают с предыдущей задачей:
1. Сумма S=0.
2. Проход по всем элементам массива и прибавление их значений к сумме S.
3. Сумму делим на количество элементов массива SA=S/N .
Фрагмент программы:
Var
S : integer; {Сумма элементов массива}
Sa : real; {Среднее арифметическое элементов массива}
…
Begin
…
{1} s := 0;
{2} for I := 1 to n do
s := s + A[i];
{3} sa := s / n;
…
Поиск максимального/минимального элемента массива
Задача 6: Найти значение максимального элемента массива.
Алгоритм содержит три пункта:
1. Максимальным элементом считаем первый элемент: max=A[1].
2. Начиная со второго элемента, сравниваем имеющийся максимальный элемент max с очередным элементом массива A[i].
3. Если очередной элемент массива больше имеющегося максимального элемента, то это и есть новый максимальный элемент max=A[i].
Фрагмент программы:
Var
Max : integer; {Значение максимального элемента массива}
…
Begin
…
{1} max := A[1];
{2} for I := 2 to n do
{3} if A[i] > max then max := A[i];
…
Задача 7: Найти min и max значения элементов массива.
Фрагмент программы:
Var
max,min:integer; {Значение максимального и минимального
элементов массива}
…
Begin
…
max := A[1];
min := A[1];
for i := 2 to n do
if A[i] > max then max := A[i]
else if A[i] < min then min := A[i];
…
Подсчет количества элементов, удовлетворяющих заданному условию
Задача 8: Подсчитать, сколько раз в массиве встречается элемент, равный 10.
Задача решается по следующему алгоритму:
1. Количество нужных элементов К=0.
2. Проходим по всем элементам массива.
3. Если очередной элемент массива равен 10,
4. Тогда увеличиваем К (количество элементов равных 10) на 1.
Фрагмент программы:
Var
k:integer; {Количество элементов, равных 10}
…
Begin
…
{1} k:=0;
{2} for I := 1 to n do
{3} if A[i] = 10
{4} then k := k+1;
…
Удаление элемента из массива
Задача 9: Удалить из массива первый элемент.
Удаление элемента заключается в:
1. Сдвиге элементов, стоящих правее удаляемого, влево.
2. Уменьшении количества элементов массива n на количество удаляемых элементов.
Сдвиг элементов выполняется так:
1. Начиная с удаляемого элемента, копируем содержимое элемента, стоящего правее в текущий элемент: A[i]:=A[i+1].
2. Переходим к следующему элементу вправо: i:=i+1.
3. Заканчиваем сдвиг, когда i=n-1, так как i+1 при i=n-1 равен n..
Фрагмент программы:
…
{1 - сдвигаем элементы на одну позицию вправо}
{Вначале i:=1, потому что надо удалить 1-ый элемент}
for I := 1 to n - 1 do
A[i] := A[i+1];
{2 - уменьшаем количество элементов в массиве}
n := n-1;
…
Задача 10: Удалить из массива максимальный элемент массива.
Для этого надо:
1. Найти индекс максимального элемента.
2. Удалить элемент с найденным индексом.
Фрагмент программы:
Var
imax:IndexEl; {Индекс максимального элемента}
…
Begin
…
{1 - ищем индекс максимального элемента массива}
imax := 1; {Вначале imax указывает на первый элемент}
{В цикле начиная со 2-го элемента}
for I := 2 to n do
{Сравниваем i-ый элемент с максимальным на текущий
момент времени, и если i-ый элемент больше
максимального, то максимальным становится
i-ый элемент}
if A[i] > A[imax] then imax := i;
{2 - удаляем элемент массива с индексом imax}
for I := imax to n - 1 do
A[i] := A[i+1];
dec(n); {Уменьшаем n на 1}
…
Замечание: в языке Тurbo Рascal имеются процедуры увеличения и уменьшения переменной целого типа.
Inc - увеличение значения переменной.
Вид вызова для целого X
Inc(x); X := x + 1;
Inc(x, n); X := x + n;
где x - переменная целого типа,
n - целочисленное выражение.
В первом случае переменной x присваивается следующее значение (например, x была равна 10, тогда после выполнения inc(x) x равна 11). Таким образом, можно сказать, что запись inc(x) эквивалентна записи x:=x+1.
Можно также сказать, что запись inc(x,n) эквивалентна записи x:=x+n.
Dec – уменьшение значения переменной.
Вид вызова для целого X
Dec(x); X := x - 1;
Dec(x, n); X := x - n;
Вставка новых элементов в массив
Задача 11: В массив после максимального элемента вставить элемент, равный 0.
Пример исходного массива A: 1 2 5 1 0 1 2 .
максимальный элемент A[3]=5
Массив после вставки элемента: 1 2 5 0 1 0 1 2.
Алгоритм вставки элемента в массив:
1. Сдвинуть элементы от позиции вставляемого элемента в конец.
2. В позицию вставляемого элемента вписать нужное значение.
3. Количество элементов n увеличить на 1 .
Общий алгоритм программы следующий:
1 . Введем массив А.
2 . Найдем индекс max элемента.
3 . Вставим после max 0.
4 . Выведем получившийся массив.
Приведем полный текст программы:
{Пример обработки одномерного массива
Задание: в массив после максимального элемента
вставить элемент, равный 0}
Program InsertExample;
Const {Определение констант}
maxN = 20; {Максимально возможное количество элементов
в массиве}
Type {Определение типов}
IndexEll = 1 .. maxN; {Индексы массива лежат в интервале
от 1 до maxN}
arrInt = array[interval] of integer; {Массив целых чисел,
содержащий до maxN элементов}
Var
A : arrInt; {Массив}
N : integer; {Количество элементов в массиве}
I : IndexEl; {Переменная для сканирования массива}
Max : IndexEl; {Номер max элемента массива}
Begin
{1 - ввод массива - генерируем случайные элементы}
randomize;
n := random(6) + 5; {n в интервале 5..10}
for I := 1 to n do
A[i] := random(19) - 9; {Генерируем элементы массива.
Каждый элемент имеет значение в интервале -9..9}
{2 - ищем индекс max элемента}
max := 1;
for I := 2 to n do
if A[i] > A[max] then max := i;
{3- вставляем 0 после максимального элемента.
Сначала сдвигаем “хвост” массива вправо}
for I := n downto max + 1 do
A[i+1] := A[i];
{Заносим в следующий за максимальным элемент 0}
A[max+1] := 0;
{Увеличиваем количество элементов массива}
Inc(n);
{4 - выводим массив}
writeln('Массив А после вставки:');
for I := 1 to n do
write(A[i]:3);
readln; {Ждем нажатия клавиши Enter}
End.
Данная программа демонстрирует модульный подход к решению задач: задача разбивается на подзадачи, полученные подзадачи решаются отдельно. Если подзадача не решается непосредственно, то она снова разбивается на подзадачи и т.д. Такой подход называется "программирование сверху вниз".
Замечание: данная программа таит в себе ошибку. Если n=20, то после вставки еще одного элемента n станет равной 21, и, скорее всего, программа повиснет (потому что элементов в массиве может быть НЕ БОЛЬШЕ 20). Следовательно, при вставке элементов необходимо следить, чтобы было n<=maxN.
Удаление нескольких элементов массива
Задача 12: Удалить из массива все элементы между k-м и z-м элементами.
Рассмотрим задачу на примере при количестве элементов в массиве n=10, k=3, z=7 (т.е. надо удалить элементы между третьим и седьмым).
Будем использовать переменную d - количество удаляемых элементов. Значение d можно вычислить по формуле: d = z - k – 1 (в нашем примере получится d = 7 - 3 - 1 = 3).
Массив A до удаления:
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
1 3 9 1 0 1 3 2 7 2
^ ^ ^
a[k] a[z] a[n]
Массив A после удаления:
a[1] a[2] a[3] a[4] a[5] a[6] a[7]
1 3 9 3 2 7 2
^ ^ ^
a[k] a[z] a[n]
После удаления n стало меньше на d (в нашем примере на 3).
Общий алгоритм решения:
1 . Сдвинуть элементы вперед на d элементов, начиная с z-го.
2 . Уменьшить n на d.
Фрагмент программы:
Var
K : integer; {Индекс элемента, после которого удаляем}
Z : integer; {Индекс элемента, до которого удаляем}
D : integer; {Количество удаляемых элементов}
…
Begin
…
{Вычисляем количество удаляемых элементов}
d := z - k - 1;
{1 - сдвигаем элементы}
for I := z to n do
A[ I – d ] := A[i];
{2 - уменьшаем n на d}
Dec(n, d);
…
Задача 13: Из массива удалить все элементы, которые меньше 0.
Рассмотрим два решения этой задачи.
Алгоритм первого решения:
1. Просматриваем массив .
2. Если элемент<0, то удаляем его и n уменьшаем.
3. Если элемент>=0, то переходим к следующему.
Фрагмент программы:
…
{В цикле просматриваем элементы массива}
I := 1;
while I <= n do
begin
{Проверяем, не нужно ли i-ый элемент удалять}
if A[i] < 0 then
begin
{Если нужно – удаляем i-ый элемент}
for j := i to n - 1 do {Сдвигаем}
A[j] := A[j+1];
Dec(n); {Уменьшаем количество элементов}
end
else Inc(i); {Если удалять не нужно, то переходим
к следующему элементу}
end;
…
Пример прогона алгоритма:
Исходный массив:
0: i=1, n=6: -1 -2 2 -3 -4 3
Состояния массива после обработки очередного элемента массива:
1: i=1, n=5: -2 2 -3 -4 3 (удален -1)
2: i=1, n=4: 2 -3 -4 3 (удален -2)
3: i=2, n=4: 2 -1 -2 3 (перешли на следующий)
4: i=2, n=3: 2 -4 3 (удален -3)
5: i=2, n=2: 2 3 (удален -4)
6: i=3, n=2: 2 3 (перешли на следующий)
Алгоритм второго решения:
1. Счетчик переписанных элементов k=0.
2. Просматриваем элементы массива.
3. Если элемент A[i] не меньше 0, k увеличиваем на 1 и переписываем элемент A[i] на k-ое место.
4. После просмотра всего массива количество переписанных элементов k заносим в n.
Фрагмент программы:
Var
K : IndexEl; {Количество переписанных элементов}
…
Begin
…
{1 - переписанных элементов пока не было}
k := 0;
{2 - в цикле просматриваем элементы массива}
for I := 1 to n do
{3 - если A[i] не <0}
if not( A[i] < 0) then
begin
Inc(k); {Увеличиваем значение k на 1}
A[k] := A[i]; {Переписываем i-ый элемент в позицию k}
end;
{4 - в массиве оставляем k элементов}
n := k;
…
Пример прогона программы:
Исходный массив: -1 -2 2 -3 -4 3
Состояния массива после просмотра очередного элемента массива:
0: k=0, i=1, n=6: -1 -2 2 -3 -4 3 {не переписываем}
1: k=0, i=2, n=6; -1 -2 2 -3 -4 3 {не переписываем}
2: k=1, i=3, n=6; 2 -2 2 -3 -4 3 {переписываем
a[1]:=a[3]}
3: k=1, i=4, n=6; 2 -2 2 -3 -4 3 {не переписываем}
4: k=1, i=5, n=6; 2 -2 2 -3 -4 3 {не переписываем}
5: k=2, i=6, n=6; 2 3 2 -3 -4 3 {переписываем
a[2]:=a[6]}
6: k=2, i=7, n=6: 2 3 2 -3 -4 3 {выход из цикла}
7: n=2: 2 3 {значение k переписываем в n}
Обработка нескольких массивов
Задача 14: Массивы А и В имеют одинаковую длину. Массив С необходимо заполнить суммами соответствующих элементов массивов А и В. n - длина массивов А и В (и С тоже).
Фрагмент программы:
…
{Проходим по всем элементам массивов}
for I := 1 to n do
{Сумму i-ых элементов массивов A и B заносим в i-ый элемент C}
C[i] := A[i] + B[i];
…
Задача 15: В конец массива А[n] приписать все элементы массива В[m].
Фрагмент программы:
…
{Проходим в цикле по массиву B}
for I := 1 to m do
A[n + i] := B[i]; {Дописываем элементы в “хвост” A}
Inc(n, m); {Увеличиваем значение n (длину массива A) на
m (длину массива B)}
…
Замечание: необходимо следить, чтобы n не превысило значение maxN.
Например, так:
…
if n + m > maxN
then writeln('В массив А все элементы массива В ‘,
’не поместятся')
else … {А вот здесь выполняем добавление элементов}
…
Задача 16: Сформировать массив В из отрицательных элементов массива А. Массив А не изменять.
Фрагмент программы:
…
m := 0; {m - количество элементов в массиве В -
вначале массив B пустой}
{Проходим по всем элементам массива A}
for I := 1 to n do
if A[i] < 0 then {Если i-ый элемент массива A
отрицательный}
begin
{То копируем его в массив B}
Inc(m); {В B добавляется еще один элемент -
увеличиваем m на 1}
B[m] := A[i]; {Копируем i-ый элемент массива A
в m-ый элемент массива B}
end;
…
Задача 17: Подсчитать, сколько элементов массива А совпадают с элементами массива В.
Алгоритм программы:
1. Ввести массив А[n].
2. Ввести массив В[m] .
3. Счетчик совпадений cnt обнулить.
4. Пройти по всем элементам массива A.
5. Сравнить i-ый элемент массива А со всеми элементами
массива В.
6. Если А[i] совпадает хотя бы с одним элементом массива B,
то счетчик повторений увеличить на 1.
7. Вывести количество совпадений.
Текст программы:
{Подсчитать, сколько элементов массива А совпадают с элементами массива В}
Program TwoArrayExample;
Const
maxN = 20; {Максимальное количество элементов массива}
Type
IndexEl = 1 .. maxN; {Индексы массива лежат в интервале
от 1 до maxN}
arrInt = array[IndexEl] of integer; {Массив целых чисел,
содержащий до maxN элементов}
Var
a, b: arrInt; {Массивы A и B}
n : integer; {Количество элементов массива A}
m : integer; {Количество элементов массива B}
i, j : IndexEl; {Переменные для сканирования массивов}
cnt : integer; {Количество совпадений элементов A
с элементами B}
k: integer; {Количество совпадений элемента A[i]
с элементами B}
Begin
{1 - ввод массива A}
{Ввод количества элементов}
repeat
write('Введите n:');
readln(n);
until ( n >= 1 ) and ( n <= maxN ); {Выйдем из цикла лишь
тогда, когда n будет принадлежать интервалу [1..maxN]}
{Ввод элементов массива A поодиночке}
for I := 1 to n do
begin
write('a[', i, ']');
readln(a[i]);
end;
{2 - ввод массива B}
{ Ввод количества элементов}
repeat
write('Введите m:');
readln(m);
until (m >= 1) and (m <= maxN);
{ Ввод элементов массива B поодиночке}
for I := 1 to m do
begin
write('b[', i, ']');
readln(b[i]);
end;
{3 - счетчик повторений обнуляем}
cnt := 0;
{4 - проходим по всем элементам массива A}
for I := 1 to n do
begin
{5 - сравниваем i-ый элемент массива А со всеми
элементами массива В}
k := 0; {k - количество совпадений i-го элемента массива A
с элементами массива В}
{Считаем количество совпадений A[i] с элементами
массива B}
for j := 1 to m do
if A[i] = B[j] then Inc(k);
{6 - если А[i] совпадает хотя бы с одним элементом массива B,
счетчик повторений увеличить на 1}
if k > 0 then Inc(cnt);
end;
{7 - выводим количество повторений}
writeln('Количество совпадений cnt=', cnt);
readln; {Ждем нажатия клавиши Enter}
End.
Проверка соседних элементов массива
Задача 18: Подсчитать, сколько в массиве элементов, равных 0, справа и слева от которых стоят отрицательные элементы.
Фрагмент программы:
…
k := 0; {Количество таких элементов}
{Проходим по всем элементам массива A. Начинаем не
с первого элемента, а со второго, потому что у первого элемента
нет стоящего слева от него. Заканчиваем на n-1 элементе, а не
на n, потому что у последнего n-го элемента нет элемента,
стоящего от него справа}
for I := 2 to n - 1 do
{Если i-ый элемент равен 0 и элемент слева от него и
элемент справа от него отрицательные}
if ( A[i] = 0 ) and ( A[i-1] < 0 ) and ( A[i+1] < 0 )
then Inc(k); {Тогда увеличиваем счетчик}
…
Задача 19: Найти номер первого элемента массива, который находится между двумя положительными элементами.
Фрагмент программы:
…
k := 0; {k - номер искомого элемента}
I := 2; {начинаем со второго элемента}
{Пока не нашли искомый элемент и не просмотрели
все элементы массива}
while (I <= n - 1) and (k = 0) do
begin
{Если элемент тот, что надо, то запоминаем его индекс}
if (A[i-1] > 0) and (A[i+1] > 0) then k := i;
Inc(i); {Переходим к следующему элементу}
end;
{Выводим позицию искомого элемента}
if k = 0
then writeln('искомых элементов в массиве нет')
else writeln('искомый элемент занимает позицию ', k);
…
Сортировка массива и работа с отсортированным массивом
Задача 20: Отсортировать массив по возрастанию.
Массив A является отсортированным (упорядоченным) по возрастанию, если для всех i из интервала [1..n-1] выполняется условие A[i]<=A[i+1].
Существует множество методов сортировки, мы же воспользуемся одним из самых простых - методом сортировки выбором (поиском минимального элемента).
Суть этого метода сортировки заключается в следующем:
1. В массиве находим минимальный элемент.
2. Меняем минимальный элемент с первым.
3. В усеченном (исключая первый элемент) массиве находим
минимальный элемент.
4. Ставим его на второе место.
И так далее n-1 раз.
Пример:
Массив A, исходное состояние 1 3 0 9 2.
Процесс сортировки
0: 1 3 0 9 2 min=a[3]=0 Переставляем a[1]<->a[3]
1: 0|3 1 9 2 min=a[3]=1 Переставляем a[2]<->a[3]
2: 0 1|3 9 2 min=a[5]=2 Переставляем a[3]<->a[5]
3: 0 1 2|9 3 min=a[5]=3 Переставляем a[4]<->a[5]
4: 0 1 2 3 9 Готово
Здесь знак | отделяет уже отсортированную часть массива от еще не отсортированной.
На Turbo Pascal этот алгоритм будет выглядеть следующим образом:
Var
Buf : integer; {Через buf будем менять значения двух
элементов массива}
imin : IndexEl; {Индекс минимального элемента
неотсортированной части массива}
…
Begin
…
{n-1 раз ищем минимальный элемент массива}
for I := 1 to n - 1 do
begin
{Ищем минимальный элемент в несортированной
части массива (от i-го элемента)}
imin := i;
for j := I + 1 to n do
if A[j] < A[imin] then imin := j;
{Переставляем i-ый и imin-ый элементы}
buf := A[i];
A[i] := A[imin];
A[imin] := buf;
End;
…
Задача 21. Вставить в упорядоченный по возрастанию массив новый элемент таким образом, чтобы сохранилась упорядоченность.
Алгоритм решения задачи следующий:
1. Ищем в массиве тот элемент, который больше вставляемого. Для этого последовательно просматриваем все элементы, начиная с первого.
2. Увеличиваем длину массива на 1.
3. После этого все элементы, стоящие правее от найденного, включая сам найденный элемент, сдвигаются вправо.
4. На освободившуюся позицию вставляется искомый элемент.
Замечание: если все элементы массива меньше вставлямого, то новый элемент надо вставить в конец массива. Если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.
Пример: Надо вставить 5 в массив A: 3 4 7 9.
1. Ищем элемент, больший вставляемого. Это элемент A[3]=7.
2. Увеличиваем длину массива на 1.
Получаем массив A: 3 4 7 9 X.
3. Сдвигаем элементы, начиная с 3-го, вправо.
Получаем массив A: 3 4 7 7 9.
4. В элемент A[3] заносим 5.
Получаем массив: 3 4 5 7 9.
Фрагмент программы, реализующей данный алгоритм:
…
{Считываем число, которое надо вставить в массив}
read(g);
{1. Ищем элемент больше вставляемого }
k := 1; {k – индекс сравниваемого элемента}
{Ищем в массиве первый из элементов, которые больше
вставляемого элемента}
while (k <= n) and (a[k] <= g) do
k := k + 1;
{2. Увеличиваем длину массива на 1}
n := n + 1;
{3. Сдвигаем элементы начиная с k-го вправо}
for I := n downto k + 1 do
a[i] := a[i-1];
{4. В A[k] заносим g}
a[k] := g;
…