Вставка в линейный список
.doc
Министерство образования Российской Федерации
Санкт–Петербургский Государственный
Электротехнический Университет
Кафедра МО ЭВМ
Дисциплина: Программирование
Отчет по лабораторной работе №4
Выполнил:
студент группы 3341, Худяков Я.Д.
Проверил:
Преподаватель Самойленко В. П.
Санкт-Петербург
2004
1) Задание
Вставить заданное число элементов перед элементов с заданным номером.
2) Постановка задачи
Решение задачи необходимо реализовать с помощью линейного списка. Таким образом в начале инициализируется массив (при помощи процедуры initlist). Затем этот список заполняется (процедура AddToList). Заполнение происходит созданием новой переменной-указателя и указанием на неё ссылкой из предыдущей переменной. Затем происходит чтение информации, необходимой для вставки и осуществляется вставка (процедура ReplaceElem). Для этого список читается до тех пор, пока мы не подходим к елементу, перед которым необходимо осуществить вставку (назовём его синим). Запоминается его адрес, и в список начинается добавление элементов после елемента, предшествующего синему. Затем из последнего вставленного элемента делается ссылка на синий елемент. Есть процедура вывода списка (Print). Естественно присутствует процедура удаления списка (ReleaseList). В драйвере тестирования реализован интерфейс для выполнения этих шагов в заданном пользователем порядке.
Проблемный тип принят за тип integer.
Спецификация функций и процедур:
|
Процедура |
Назначение |
|
InitList |
Инизиализация списка |
|
AddToList |
Добавление элемента в список |
|
ReleaseList |
Удаление списка |
|
ReplaceElem |
Процедура вставки |
|
|
Вывод списка на экран |
3) Текст программы
Юниты:
unit types;
interface
type tInfo = integer;
implementation
end.
unit MyList;
interface
uses types;
procedure InitList;
procedure AddToList(Elem : tInfo);
procedure ReleaseList;
procedure ReplaceElem(K : integer; N : integer; var Elem : array of tInfo);
procedure Print;
implementation
type
tLink = ^tNode;
tNode = record
info : tInfo;
next : tLink;
end;
tMyList = record
pHead : tLink;
pEnd : tLink;
end;
var List : tMyList;
procedure procMessage(N : integer);
begin
case N of
1 : writeln('Ошибка! Нет элементов в списке!');
2 : writeln ('Элемент, перед которым осуществляется замена отсутствует! Список не изменился.');
3 :
begin
writeln ('Длины списка не достаточна для замены данного числа элементов!');
writeln ('Изменена лишь чаcть элементов!');
end;
4 : writeln('Данного элемента нет в списке!');
5 : writeln('Ок.');
end;
end;
procedure InitList;
begin
List.pHead := nil;
List.pEnd := nil;
procMessage(5);
end;
procedure AddToList;
var temp : tLink;
begin
new(temp);
temp^.info := Elem;
temp^.next := nil;
if (List.pHead = nil) and (List.pEnd = nil) then
begin
List.pHead := temp;
List.pEnd := temp;
end
else
begin
List.pEnd^.next := temp;
List.pEnd := temp;
end;
end;
procedure ReleaseList;
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.pEnd := nil;
procMessage(5);
end;
procedure ReplaceElem(K : integer; N : integer; var Elem : array of tInfo);
var i : integer;
temp,p,elem2 : tLink;
j:tinfo;
t:integer;
begin
if (high(Elem) + 1 >= N + K - 1) then
begin
if (n<1) then procMessage(2) else
begin
if (n=1) then
begin
t:=1;
p:=List.pHead;
new(elem2);
List.pHead:=elem2;
for i:=1 to k do
begin
if (t<>1) then new(elem2);
t:=0;
elem2^.info := Elem[i-1];
elem2^.next := nil;
temp^.next := elem2;
temp := elem2;
end;
temp^.next:=p;
end else
begin
temp := List.pHead;
i := 1;
while (i < N - 1 ) and (temp <> nil) do
begin
temp := temp^.next;
inc(i);
end;
p:=temp;
p:=p^.next;
if (temp = nil) or (p = nil) then
begin
procMessage(2);
end
else
begin
p:=temp;
p:=p^.next;
while (i < k + n - 1) and (temp <> nil) do
begin
new(elem2);
elem2^.info := Elem[i - n + 1];
elem2^.next := nil;
temp^.next := elem2;
temp := elem2;
inc(i);
end;
temp^.next:=p;
temp:=p;
while (temp <> nil) do
begin
temp := temp^.next;
inc(i);
end;
end;
end;
end;
end;
end;
procedure Print;
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;
end.
Сама программа:
uses crt,lab3_uni;
var
t1:tin;
t2:tout;
f1,f2:text;
sim:char;
max,g:byte;
Begin
clrscr;
assign(f1,'massiv.in'); reset(f1);
assign(f2,'massiv.out'); rewrite(f2);
readln(f1,max);
inputtext(f1,t1);
form(t1,t2,max);
out(f2,t2);
close(f1);
close(f2);
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 |