Удаление элемента из списка
.doc
Министерство образования Российской Федерации
Санкт–Петербургский Государственный
Электротехнический Университет
Кафедра МО ЭВМ
Дисциплина: Программирование
Отчет по лабораторной работе №5
Выполнил:
студент группы 3341, Худяков Я.Д.
Проверил:
Преподаватель Самойленко В. П.
Санкт-Петербург
2004
1) Задание
Вставить заданное число элементов перед элементов с заданным номером.
2) Постановка задачи
Решение задачи реализовано при помощи Л1 списка с указателем на голову писка, текущий элемент и элемент, предшествующий текущему. Для удаления элемента с указанным номером первый элемент становится текущим, и список просматривается до нахождения нужного элемента. Если необходимо удалить первый элемент, то для этого указатель на голову смещается на один вперёд (как и указатель на текущий элемент) и то, на что указывал этот указатель удаляется. В противном случае, если найден нужный элемент (назовём его плохим, на него указывает указатель текущего элемента), то указатель текущего элемента переводится на следующий за плохим элемент (назовём его хорошим), указатель предшествующего плохому элементу начинает ссылаться на хороший элемент. После этого плохой элемент удаляется из памяти. Если элемент с заданным номером не существует, то выводится сообщение об ошибке, список при этом не меняется.
Проблемный тип принят за тип integer.
Спецификация функций и процедур:
|
Процедура |
Назначение |
|
InitList |
Инизиализация списка |
|
AddToList |
Добавление элемента в список |
|
ReleaseList |
Удаление списка |
|
DelElem |
Процедура удаления элемента |
|
|
Вывод списка на экран |
|
Null |
Проверка пуст ли список |
|
BOL |
Проверка в начале ли указатель |
|
EOL |
Проверка в конце ли указатель |
|
GoEOL |
Перемещение указателя в конец списка |
|
GoBOL |
Перемещение указателя в начало списка |
3) Текст программы
Units:
unit types;
interface
type tInfo = integer;
implementation
end.
Unit MyListt;
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 DelElem(List : MyList; K : integer);
procedure Print(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('Ок.');
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(3);
end;
procedure GoEOL(List : MyList);
begin
while (List^.Cur^.next <> nil) do
begin
List^.PredCur := List^.Cur;
List^.Cur := List^.Cur^.next;
procMessage(3);
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 DelElem(List : MyList; K : integer);
var i : integer;
temp : tLink;
begin
i:=1;
if (K < 1) then procMessage(2) else
begin {2}
if (not BOL(List)) then GoBOL(List);
if (K = 1) then
begin
temp := List^.pHead;
List^.pHead := List^.pHead^.next;
List^.Cur:=List^.pHead;
List^.PredCur := nil;
dispose(temp);
end else
begin {1}
while (i <> K) and (List^.Cur <> nil) do
begin
List^.PredCur := List^.Cur;
List^.Cur := List^.Cur^.next;
inc(i);
end;
{в Cur то что надо удалить}
{writeln(List^.Cur^.info);}
if (List^.Cur = nil) then
begin
procMessage(2);
GoBOL(List);
end else
begin {3}
temp := List^.Cur;
if (List^.Cur^.next <> nil) then
begin
List^.Cur:=List^.Cur^.next;
List^.PredCur^.next := List^.Cur;
end else
begin
List^.PredCur^.next := nil;
GoBOL(List);
end;
dispose(temp);
end; {3}
end; {1}
end;{2}
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;
end.
Сама программа:
{удаление элемента с заданным номером}
uses crt,types,MyListt;
var N, K, i ,choose,init,zap : integer;
l,elem : tinfo;
ch:char;
qw:boolean;
L1List:MyList;
label 1;
begin
init:=0;
zap:=0;
1:clrscr;
ch:='q';
choose:=0;
writeln('Меню программы:');
writeln('1 - Инициализация списка.');
writeln('2 - Заполнение списка.');
writeln('3 - Ввод номера элемента для удаления.');
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);
{K номер эл-та который удалим}
Writeln('Осуществляется удаление...');
DelElem(L1List, K);
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 |
1 3 4 5 |
|
5 1 2 3 4 5 1 |
2 3 4 5 |
|
5 1 2 3 4 5 6 |
Элемент, с заданным номером не существует. Список не изменился. 1 2 3 4 5 |
|
5 1 2 3 4 5 0 |
Элемент, с заданным номером не существует. Список не изменился. 1 2 3 4 5 |