Вставка в список элементов
.doc
Министерство образования Российской Федерации
Санкт–Петербургский Государственный
Электротехнический Университет
Кафедра МО ЭВМ
Дисциплина: Программирование
Отчет по лабораторной работе №6
Выполнил:
студент группы 3341, Худяков Я.Д.
Проверил:
Преподаватель Самойленко В. П.
Санкт-Петербург
2004
1) Задание
Вставить заданное число элементов перед элементом с заданным номером.
2) Постановка задачи
Решение задачи реализовано при помощи Л1 списка с указателем на голову cписка, текущий элемент и элемент, предшествующий текущему. Для решения задачи список просматривается до тех пор, пока указатель на текущий элемент не установлен на элемент, перед которым нужно осуществить вставку. Это производит процедура Go. Этот элемент назовём синим. Далее производится вставка новых элементов перед синим. Это осуществляет процедура InsBefore, вызваемая перед каждой вставкой. Основной же процедурой является процедура InsElems, которая и взывется из основной программы, и которая в зависимости от ситуации работает с процедурами Go и InsBefore.
Если список пуст, то при попытке вставки выводится соответствующее сообщение.
Если элемент, перед которым необходимо осуществить вставку не существует, то выводится соответствующее сообщение.
Проблемный тип принят за тип integer.
Спецификация функций и процедур:
|
Процедура |
Назначение |
|
InitList |
Инизиализация списка |
|
AddToList |
Добавление элемента в список |
|
ReleaseList |
Удаление списка |
|
InsElems |
Процедура удаления элемента |
|
|
Вывод списка на экран |
|
Null |
Проверка пуст ли список |
|
BOL |
Проверка в начале ли указатель |
|
EOL |
Проверка в конце ли указатель |
|
GoEOL |
Перемещение указателя в конец списка |
|
GoBOL |
Перемещение указателя в начало списка |
|
InsBefore |
Вставка элемента перед текущим элементом |
|
Go |
Перевод указателя на текущий элемент на элемент с указанным номером |
3) Текст программы
Units:
unit types;
interface
type tInfo = integer;
implementation
end.
unit MyList6;
interface
uses types;
type
tLink = ^tNode;
tNode = record
info : tInfo;
next : tLink;
end;
tMyList = record
pHead : tLink;
Cur : tLink;
PredCur : tLink;
end;
MyList = ^tMyList;
Function InitList : MyList;
Function Null(List : MyList):boolean;
procedure AddToList(List : Mylist; Elem : tInfo);
procedure ReleaseList(List : MyList);
procedure InsBefore(List : MyList; Elem : tInfo);{вставка элемента перед текущим}
procedure Go(List : MyList; num : integer); {переход к элементу с указанным номером}
procedure InsElems(List : MyList; K : integer; N : integer; var Elem : array of tInfo);
procedure Print(List : MyList);
procedure PrintN(List : MyList); {вывод текущего элемента}
function BOL(List : Mylist):boolean;
function EOL(List : Mylist):boolean;
procedure GoEOL(List : MyList);
procedure GoBOL(List : MyList);
implementation
procedure procMessage(N : integer);
begin
case N of
1 : writeln('Ошибка! Нет элементов в списке!');
2 : writeln ('Элемент, с заданным номером не существует. Список не изменился.');
3 : writeln('Ок.');
4 : writeln('Перемещены в начало списка...');
5 : writeln('Перемещены в конец списка...');
end;
end;
function InitList : MyList;
var p:MyList;
begin
new(p);
p^.pHead := nil;
p^.Cur := nil;
p^.PredCur := nil;
InitList := p;
procMessage(3);
end;
Function Null(List : MyList):boolean;
begin
Null := (List^.pHead = nil) and (List^.Cur = nil) and (List^.PredCur = nil);
end;
procedure GoBOL(List : MyList);
begin
List^.Cur := List^.pHead;
List^.PredCur := nil;
procMessage(4);
end;
procedure GoEOL(List : MyList);
begin
while (List^.Cur^.next <> nil) do
begin
List^.PredCur := List^.Cur;
List^.Cur := List^.Cur^.next;
procMessage(5);
end;
end;
function EOL(List : Mylist):boolean;
begin
EOL := (List^.Cur^.next = nil);
end;
function BOL(List : Mylist):boolean;
begin
BOL := (List^.PredCur = nil);
end;
procedure AddToList(List : Mylist; Elem : tInfo);
var temp : tLink;
begin
new(temp);
temp^.info := Elem;
temp^.next := nil;
if (List^.pHead = nil) then
begin
List^.pHead := temp;
List^.Cur:=temp;
end else
begin
if (not EOL(List)) then GoEOL(List);
List^.PredCur := List^.Cur;
List^.Cur^.next := temp;
List^.Cur := temp;
end;
end;
procedure ReleaseList(List : MyList);
var temp : tLink;
begin
temp := List^.pHead;
while (temp^.next <> nil) do
begin
List^.pHead := temp^.next;
dispose(temp);
temp := List^.pHead;
end;
List^.pHead := nil;
List^.Cur := nil;
List^.PredCur := nil;
dispose(List);
procMessage(3);
end;
procedure InsBefore(List : MyList; Elem : tInfo);
var elem2:tLink;
begin
if BOL(List) then
begin
new(elem2);
elem2^.info := Elem;
elem2^.next := List^.pHead;
List^.pHead := elem2;
List^.Cur := elem2;
List^.PredCur := nil;
end else
begin
new(elem2);
elem2^.info := Elem;
elem2^.next := List^.PredCur^.next;
List^.PredCur^.next := elem2;
List^.Cur := elem2;
end;
end;
procedure Go(List : MyList; num : integer);
var i : integer;
begin
if (not BOL(List)) then GoBOL(List);
if (num = 1) then
begin
List^.Cur := List^.pHead;
List^.PredCur := nil;
end else
begin
i := 1;
while (i < num ) and (List^.Cur <> nil) do
begin
List^.PredCur := List^.Cur;
List^.Cur := List^.Cur^.next;
inc(i);
end;
end;
end;
procedure InsElems(List : MyList; K : integer; N : integer; var Elem : array of tInfo);
var i : integer;
temp,p,elem2 : tLink;
j:tinfo;
t:integer;
begin
{K заданное число элементов N номер эл перед к-м вставлять}
if (n<1) then procMessage(2) else
begin
if (not BOL(List)) then GoBOL(List);
if (n=1) then begin if (k>0) then
begin
for i:=k-1 downto 0 do InsBefore(List,Elem[i]);
end
end else
begin
Go(List,N);
if (List^.cur = nil) then procMessage(2) else for i:=k-1 downto 0 do InsBefore(List,Elem[i]);
end;
end;
end;
procedure Print(List : MyList);
var temp : tLink;
begin
temp := List^.pHead;
if temp = nil then
begin
procMessage(1);
exit;
end;
while (temp <> nil) do
begin
write(temp^.info, ' ');
temp := temp^.next;
end;
writeln;
end;
procedure PrintN(List : MyList);
begin
writeln('Текущий элемент равен: ',List^.Cur^.info);
end;
end.
Сама программа:
{вставка заданных элементов перед элементов с указанным номером}
uses crt,types,MyList6;
const MaxElem = 100;
var N, K, i ,choose,init,zap : integer;
l,elem : tinfo;
MasElem : array[1..MaxElem] of tInfo;
ch:char;
qw:boolean;
L1List:MyList;
label 1;
begin
init:=0;
zap:=0;
1:clrscr;
ch:='q';
choose:=0;
{K заданное число элементов N номер эл перед к-м вставлять}
writeln('Меню программы:');
writeln('1 - Инициализация списка.');
writeln('2 - Заполнение списка.');
writeln('3 - Ввод количества элементов для вставки,');
writeln('перед которым осуществить вставку и');
writeln('элементы для вставки');
writeln('4 - Вывод списка.');
writeln('5 - В конце списка?');
writeln('6 - В начале списка?');
writeln('7 - В конец списка.');
writeln('8 - В начало списка.');
writeln('9 - Список пуст?');
writeln('10 - Удаление списка.');
writeln('11 - Выход.');
while (choose<>1) and (choose<>2) and (choose<>3) and (choose<>4) and (choose<>5) and (choose<>6)
and (choose<>7) and (choose<>8) and (choose<>9) and (choose<>10) and (choose<>11) do readln(choose);
case choose of
1: begin
if init=1 then writeln('Список уже иниацилизирован!') else
begin
write('Инициализация списка...');
L1List:=InitList;
init:=1;{список инициализирован}
end;
end;
2: begin
if init<>1 then write('Список не существует!') else
Begin
writeln('Добавление элементов в список...');
writeln('Введите количество элементов:');
readln(n);
writeln('Вводите элементы');
for i := 1 to N do
begin
Readln(elem);
AddToList(L1List,elem);
end;
Writeln('Всего было записано ', N,' элемента(ов):');
Zap:=1;
end;
end;
3: begin
if zap<>1 then writeln('Список не заполнен!') else
begin
writeln('Введите число элементов для вставки и номер э-та перед которым вставлять');
readln(K, N);
{K заданное число элементов N номер эл перед к-м вставлять}
writeln('Вводите элементы');
for i:= 1 to K do Readln(MasElem[i]);
Writeln('Осуществляется вставка...');
InsElems(L1List,K, N, MasElem);
end;
end;
4: begin
if init<>1 then writeln('Список не создан') else if zap<>1 then writeln('Список пуст') else print(L1List);
end;
5: begin
qw:=EOL(L1List);
if qw then writeln('Да, в конце списка.') else writeln('Нет, не в конце списка.');
end;
6: begin
qw:=BOL(L1List);
if qw then writeln('Да, в начале списка.') else writeln('Нет, не в начале списка.');
end;
7: begin
GoEOL(L1List);
writeln('Перемещены в конец списка.');
end;
8: begin
GoBOL(L1List);
writeln('Перемещены в начало списка.');
end;
9: begin
qw:=Null(L1List);
if qw then writeln('Да, спискок пуст.') else writeln('Нет, список не пуст.');
end;
10: begin
if init<>1 then writeln('Список не создан') else
begin
Write('Уничтожение списка...');
ReleaseList(L1List);
init:=0;
zap:=0;
end;
end;
11: begin
ch:='n';
end;
{Assign(inp,'list.in'); Reset(inp);
Assign(out, 'list.out'); Rewrite(out);}
end;
if (ch<>'n') then writeln('Продолжить работу? (y/n) ');
while (ch<>'y') and (ch<>'Y') and (ch<>'n') and (ch<>'N') do readln(ch);
if (ch='y') or (ch='Y') then goto 1;
end.
4) Тестирование
в тестировании использована последовательность команд
- кол-во элементов
- элементы
- количество вставляемых эл-в, перед которым вставлять
- вставляемые элементы
выходными данными является список после вставки.
|
Входные данные |
Выходные данные |
|
5 1 2 3 4 5 2 3 9 9 |
1 2 9 9 3 4 5 |
|
5 1 2 3 4 5 2 1 9 9 |
9 9 1 2 3 4 5 |
|
5 1 2 3 4 5 2 0 9 9 |
Элемент, перед которым осуществляется вставка отсутствует! Список не изменился. 1 2 3 4 5 |
|
5 1 2 3 4 5 2 7 9 9 |
Элемент, перед которым осуществляется вставка отсутствует! Список не изменился. 1 2 3 4 5 |