Для работы с очередью, т. е. последовательностью элементов, в которую элементы всегда…
- User
Для работы с очередью, т. е. последовательностью элементов, в которую элементы всегда добавляются в конец, а удаляются из начала («первым пришел—первым ушел»), нужны обычно следующие операции:
ОЧИСТОЧ(Q)—создать пустую очередь Q (очистить очередь);
ПУСТОЧ(Q)—проверить, является ли очередь Q пустой;
ВОЧЕРЕДЬ(Q,х)—добавить в конец очереди Q элемент х;
ИЗОЧЕРЕДИ(Q,х)— удалить из очереди © первый элемент, присвоив его параметру х.
Требуется для каждого из указанных ниже представлений очереди описать на Паскале соответствующий тип очередь, считая, что все элементы очереди имеют некото- рый тип ТЭО, н реализовать в виде процедур или функ- ций перечисленные операции над очередью (если операция по тем или иным причинам не может быть выполнена, следует передать управление некоторой процедуре ОШИБКА(K), считая ее уже описанной, где K — номер ошибки: 1—переполнение очереди, 2— исчерпание очереди).
Представление очереди (n — целая константа >1):
а)* для каждой очереди ОТВОДИТСЯ свой массив из n компонент типа ТЭО, в котором элементы очереди зани- мают группу соседних компонент, индексы первой и по- следней из которых запоминаются; при этом, когда очередь достигает правого края массива, все ее эле- менты сдвигаются к левому краю;
б) аналогичное представление, но массив как бы склеивается в кольцо, поэтому если очередь достигает правого края массива, то новые элементы записываются в начало массива;
в) для каждой очереди создается свой однонаправлен- ный список из элементов типа ТЭО, при этом запомина- ются ссылки на первое и последнее звенья списка.
- Assistant
а) Определение типа очереди:
type TQueue = record items: array[1..n] of TEO; first, last: integer; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin Q.first := 0; Q.last := 0; end;
function ПУСТОЙ(Q: TQueue): boolean; begin ПУСТОЙ := Q.first = 0; end;
procedure ВОЧЕРЕДЬ(var Q: TQueue; x: TEO); begin if Q.last = n then if Q.first = 1 then ОШИБКА(1) // переполнение очереди else begin for i := Q.first to Q.last do Q.items[i - Q.first + 1] := Q.items[i]; Q.last := Q.last - Q.first + 1; Q.first := 1; end; Q.last := Q.last + 1; Q.items[Q.last] := x; end;
procedure ИЗОЧЕРЕДИ(var Q: TQueue; var x: TEO); begin if Q.first = 0 then ОШИБКА(2) // исчерпание очереди else begin x := Q.items[Q.first]; if Q.first = Q.last then Q.first := 0 else Q.first := Q.first + 1; end; end;
б) Определение типа очереди:
type TQueue = record items: array[1..n] of TEO; first, last: integer; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin Q.first := 0; Q.last := 0; end;
function ПУСТОЙ(Q: TQueue): boolean; begin ПУСТОЙ := Q.first = 0; end;
procedure ВОЧЕРЕДЬ(var Q: TQueue; x: TEO); begin if Q.last = n then Q.last := 1 else Q.last := Q.last + 1; if Q.last = Q.first then ОШИБКА(1); // переполнение очереди Q.items[Q.last] := x; end;
procedure ИЗОЧЕРЕДИ(var Q: TQueue; var x: TEO); begin if Q.first = 0 then ОШИБКА(2) // исчерпание очереди else begin x := Q.items[Q.first]; if Q.first = Q.last then Q.first := 0 else if Q.first = n then Q.first := 1 else Q.first := Q.first + 1; end; end;
в) Определение типа очереди:
type TQueueItemPtr = ^TQueueItem; TQueueItem = record data: TEO; next: TQueueItemPtr; end; TQueue = record first, last: TQueueItemPtr; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin Q.first := nil; Q.last := nil; end;
function ПУСТОЙ(Q: TQueue): boolean; begin ПУСТОЙ := Q.first = nil; end;
procedure ВОЧЕРЕДЬ(var Q: TQueue; x: TEO); var newItem: TQueueItemPtr; begin newItem := new(TQueueItem); newItem^.data := x; newItem^.next := nil; if Q.first = nil then Q.first := newItem else Q.last^.next := newItem; Q.last := newItem; end;
procedure ИЗОЧЕРЕДИ(var Q: TQueue; var x: TEO); var firstItem: TQueueItemPtr; begin if Q.first = nil then ОШИБКА(2) // исчерпание очереди else begin x := Q.first^.data; firstItem := Q.first; Q.first := Q.first^.next; dispose(firstItem); end; end;
- User
Для работы с очередью, т. е. последовательностью элементов, в которую элементы всегда добавляются в конец, а удаляются из начала («первым пришел—первым ушел»), нужны обычно следующие операции:
ОЧИСТОЧ(Q)—создать пустую очередь Q (очистить очередь);
ПУСТОЧ(Q)—проверить, является ли очередь Q пустой;
ВОЧЕРЕДЬ(Q,х)—добавить в конец очереди Q элемент х;
ИЗОЧЕРЕДИ(Q,х)— удалить из очереди © первый элемент, присвоив его параметру х.
Требуется для каждого из указанных ниже представлений очереди описать на Паскале соответствующий тип очередь, считая, что все элементы очереди имеют некото- рый тип ТЭО, н реализовать в виде процедур или функ- ций перечисленные операции над очередью (если операция по тем или иным причинам не может быть выполнена, следует передать управление некоторой процедуре ОШИБКА(K), считая ее уже описанной, где K — номер ошибки: 1—переполнение очереди, 2— исчерпание очереди).
Представление очереди (n — целая константа >1):
а)* для каждой очереди ОТВОДИТСЯ свой массив из n компонент типа ТЭО, в котором элементы очереди зани- мают группу соседних компонент, индексы первой и по- следней из которых запоминаются; при этом, когда очередь достигает правого края массива, все ее эле- менты сдвигаются к левому краю;
б) аналогичное представление, но массив как бы склеивается в кольцо, поэтому если очередь достигает правого края массива, то новые элементы записываются в начало массива;
в) для каждой очереди создается свой однонаправлен- ный список из элементов типа ТЭО, при этом запомина- ются ссылки на первое и последнее звенья списка.
- Assistant
а) Определение типа очереди:
type TQueue = record items: array[1..n] of TEO; first, last: integer; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin Q.first := 0; Q.last := 0; end;
function ПУСТОЙ(Q: TQueue): boolean; begin ПУСТОЙ := Q.first = 0; end;
procedure ВОЧЕРЕДЬ(var Q: TQueue; x: TEO); begin if Q.last = n then if Q.first = 1 then ОШИБКА(1) // переполнение очереди else begin for i := Q.first to Q.last do Q.items[i - Q.first + 1] := Q.items[i]; Q.last := Q.last - Q.first + 1; Q.first := 1; end; Q.last := Q.last + 1; Q.items[Q.last] := x; end;
procedure ИЗОЧЕРЕДИ(var Q: TQueue; var x: TEO); begin if Q.first = 0 then ОШИБКА(2) // исчерпание очереди else begin x := Q.items[Q.first]; if Q.first = Q.last then Q.first := 0 else Q.first := Q.first + 1; end; end;
б) Определение типа очереди:
type TQueue = record items: array[1..n] of TEO; first, last: integer; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin Q.first := 0; Q.last := 0; end;
function ПУСТОЙ(Q: TQueue): boolean; begin ПУСТОЙ := Q.first = 0; end;
procedure ВОЧЕРЕДЬ(var Q: TQueue; x: TEO); begin if Q.last = n then Q.last := 1 else Q.last := Q.last + 1; if Q.last = Q.first then ОШИБКА(1); // переполнение очереди Q.items[Q.last] := x; end;
procedure ИЗОЧЕРЕДИ(var Q: TQueue; var x: TEO); begin if Q.first = 0 then ОШИБКА(2) // исчерпание очереди else begin x := Q.items[Q.first]; if Q.first = Q.last then Q.first := 0 else if Q.first = n then Q.first := 1 else Q.first := Q.first + 1; end; end;
в) Определение типа очереди:
type TQueueItemPtr = ^TQueueItem; TQueueItem = record data: TEO; next: TQueueItemPtr; end; TQueue = record first, last: TQueueItemPtr; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin Q.first := nil; Q.last := nil; end;
function ПУСТОЙ(Q: TQueue): boolean; begin ПУСТОЙ := Q.first = nil; end;
procedure ВОЧЕРЕДЬ(var Q: TQueue; x: TEO); var newItem: TQueueItemPtr; begin newItem := new(TQueueItem); newItem^.data := x; newItem^.next := nil; if Q.first = nil then Q.first := newItem else Q.last^.next := newItem; Q.last := newItem; end;
procedure ИЗОЧЕРЕДИ(var Q: TQueue; var x: TEO); var firstItem: TQueueItemPtr; begin if Q.first = nil then ОШИБКА(2) // исчерпание очереди else begin x := Q.first^.data; firstItem := Q.first; Q.first := Q.first^.next; dispose(firstItem); end; end;
- User
Для работы с очередью, т. е. последовательностью элементов, в которую элементы всегда добавляются в конец, а удаляются из начала («первым пришел—первым ушел»), нужны обычно следующие операции:
ОЧИСТОЧ(Q)—создать пустую очередь Q (очистить очередь);
ПУСТОЧ(Q)—проверить, является ли очередь Q пустой;
ВОЧЕРЕДЬ(Q,х)—добавить в конец очереди Q элемент х;
ИЗОЧЕРЕДИ(Q,х)— удалить из очереди © первый элемент, присвоив его параметру х.
Требуется для каждого из указанных ниже представлений очереди описать на Паскале соответствующий тип очередь, считая, что все элементы очереди имеют некото- рый тип ТЭО, и реализовать в виде процедур или функ- ций перечисленные операции над очередью (если операция по тем или иным причинам не может быть выполнена, следует передать управление некоторой процедуре ОШИБКА(K), считая ее уже описанной, где K — номер ошибки: 1—переполнение очереди, 2— исчерпание очереди).
Представление очереди (n — целая константа >1):
для каждой очереди ОТВОДИТСЯ свой массив из n компонент типа ТЭО, в котором элементы очереди зани- мают группу соседних компонент, индексы первой и по- следней из которых запоминаются; при этом, когда очередь достигает правого края массива, все ее эле- менты сдвигаются к левому краю; главное - реализовать операции, чтобы программа могла скомпилироваться и вывести какой-то результат
- Assistant
Определение типа очереди:
type TQueue = record items: array[1..n] of TEO; first, last: integer; end;
Операции над очередью:
procedure ОЧИСТКА(var Q: TQueue); begin