Консультация № 165780
24.04.2009, 21:54
0.00 руб.
0 18 1
Здравствуйте!

Возникли трудности в написании процедуры на динамические списки.
"Описать процедуру, которая удаляет все элементы, у которых одинаковые "соседи" (первый и последний тоже считать соседями)".
Прошу помочь в составлении данной процедуры.
Спасибо!

Приложение:
Шапка к заданиям:
ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ

Каждому студенту сделать свой вариант задания, предусмотрев процедуры:
• создания динамического линейного списка, выбирая числа из текстового файла;
• вывода динамического линейного списка.

Обсуждение

Неизвестный
25.04.2009, 09:09
общий
это ответ
Здравствуйте, Сапожников Константин Юрьевич!

Программа в приложении.

С уважением, Дмитрий

Приложение:
program dinamik_list;
uses crt;
type TPElement=^TElement; { Указатель на элемент списка }
TElement=record
i: integer; { Элемент списка }
pred: TPElement; { Предыдущий элемент }
sled: TPElement; { Следующий элемент }
del: boolean; { Пометка удаления }
end;
var PSpisok: TPElement; { Указатель на список }
fin: text; { Входной файл }

{ Процедура вывода списка на экран }
procedure PrintList(List: TPElement);
var TekElm: TPElement;
begin
TekElm:=List;
if TekElm=nil then
writeln('Список пуст')
else begin
repeat
write(TekElm^.i,' -> ');
TekElm:=TekElm^.sled;
until TekElm=List;
writeln('Начало списка');
end;
end;

{ Добавление элемента в список - возвращает ссылку на новый элемент }
function AddToList(var List: TPElement): TPElement;
var tmp: TPElement;
begin
new(tmp);
{ Если список пустой то создаем первый элемент со ссылками на самого себя }
if List=nil then begin
tmp^.sled:=tmp;
tmp^.pred:=tmp;
List:=tmp; { Запомним новое начало списка }
end else begin { Иначе добавляем }
new(tmp);
{ Для нового элемента следующим будет первый }
tmp^.sled:=List;
{ ... а предыдщим будет тот что был предыдушим для первого }
tmp^.pred:=List^.pred;
{ Для предыдущего следующим станет новый элемент }
List^.pred^.sled:=tmp;
{ Для первого предыдущим также станет новый элемент }
List^.pred:=tmp;
end;
tmp^.del:=false;
AddToList:=tmp;
end;

{ Удаление элемента из списка - возвращает ссылку на след.элемент или nil }
function DelFromList(Item: TPElement): TPElement;
begin
if Item^.sled=Item then begin { Остался один элемент }
DelFromList:=nil;
end else begin
{ Предыдущим элементом для следующего станет предыдущий для удаляемого }
Item^.sled^.pred:=Item^.pred;
{ а следующим элементом для предыдщего станет следующий для удаляемого }
Item^.pred^.sled:=Item^.sled;
DelFromList:=Item^.sled;
end;
dispose(Item);
end;

{ Обработка списка по заданию - удаление одинаковых соседей }
procedure Obrabotka(var List: TPElement);
var TekElm: TPElement;
begin
{ Сначала поставим пометки на удаление }
TekElm:=List;
repeat
if TekElm^.sled^.i=TekElm^.pred^.i then
TekElm^.del:=true; { При выполнении условия - пометим на удаление }
TekElm:=TekElm^.sled;
until TekElm=List;
{ А теперь удалим помеченные элементы }
TekElm:=List;
repeat
TekElm:=TekElm^.sled;
if TekElm^.del then
{ Если удаляем начало списка - то надо запомнить новое начало }
if TekElm=List then begin
TekElm:=DelFromList(TekElm);
List:=TekElm;
end else
TekElm:=DelFromList(TekElm);
until TekElm=List;
end;

begin
clrscr;
{ Открываем файл }
assign(fin,'chisla.txt');
{$I-}
reset(fin);
if IOResult<>0 then begin
writeln('Не могу открыть входной файл');
halt;
end;
{$I+}
{ Читаем и создаем список }
PSpisok:=nil;
while not(eof(fin)) do
readln(fin,AddToList(PSpisok)^.i);
{ Выводим исходный список на экран }
write('Исходный список: ');
PrintList(PSpisok);
{ Обрабатываем список в соответствии с условиями }
Obrabotka(PSpisok);
{ Выводим получившийся список на экран }
writeln;
write('Результат обработки: ');
PrintList(PSpisok);
readln;
end.
Неизвестный
25.04.2009, 11:21
общий
Спасибо большое за помощь! Но процедура написана, к сожалению, не совсем доступно для меня.
Может быть можно как-нибудь доработать имеющуюся у меня процедуру:
(скопирую сюда всю программу, в которой так же есть процедура PEREVOROT, которая переворачивает список. Процедура - DEL_SOSED - процедура, удаляющая элементы с одинаковыми соселями - требует доработки, процедура создания списка с чтением из текстового файла lab11.txt и процедура вывода списка)

uses crt;
type uk=^stud;
stud=record
info:integer;
adr:uk;
end;
var p1,p2,p3,first:uk;
f:text;
p:boolean;
b:integer;

Procedure SOZD_SPIS;
begin
assign(f,'lab11.txt');
{$I-}reset(f){$I+};
if Ioresult<>0 then
begin writeln('file not found');
readkey;
exit;
end;
first:=nil;
while not seekeof(f) do
begin new(p1);
read(f,p1^.info);
if first=nil
then first:=p1
else p2^.adr:=p1;
p2:=p1;
end;
p2^.adr:=nil;
writeln;
writeln('Spisok sozdan');
readkey;
end;

Procedure VIVOD(t:string);
begin
writeln;writeln(t);
p1:=first;
writeln;
while p1<>nil do
begin
write(p1^.info:3);
p1:=p1^.adr
end;
writeln;
readkey
end;

Procedure PEREVOROT;
var i,j,k:integer;c:uk;
begin
p:=true;
repeat
p1:=first;
while p1^.adr<>nil do
begin
p2:=p1;
p1:=p1^.adr;
end;
p1^.adr:=p2;
p2^.adr:=nil;
if p then begin p:=false;c:=p1 end;
until p2=first;
first:=c;
end;

Procedure DEL_SOSED;
begin
p3:=first;
p:=false;
while p3^.adr<>nil do
p3:=p3^.adr;
if first^.adr^.info=p3^.info then
begin
p2:=first;
first:=first^.adr;
dispose(p2);
end;
p1:=first^.adr;
p2:=first;
while p1^.adr<>nil do
begin
if (p1^.adr^.info=p2^.info) and (not p) then
begin
b:=p1^.info;
p:=true;
p1:=p1^.adr;
p3:=p2^.adr;
dispose(p3);p2^.adr:=p1;
end;
if (p1^.adr^.info=b) and p then
begin
b:=p1^.info;
p3:=p1;
p1:=p1^.adr;
p2^.adr:=p1;
dispose(p3);
end
else
begin
p:=false;
p2:=p1;
p1:=p1^.adr;
end;
end;
if p1^.info=first^.info then
begin
p2^.adr:=nil;
dispose(p1);
end;
end;

BEGIN clrscr;
repeat
clrscr;
writeln(' 1 - SOZD_SPIS');
writeln(' 2 - VIVOD');
writeln(' 3 - PEREVOROT');
writeln(' 4 - DEL_SOSED');
writeln;
writeln(' 0 - EXIT');
case readkey of
'1':SOZD_SPIS;
'2':VIVOD('ishodniy spisog:');
'3':begin VIVOD('ishodniy spisok:');
PEREVOROT;
VIVOD('perevernutiy spisok:');
end;
'4':begin VIVOD('ishodniy spisok:');DEL_SOSED;VIVOD('obrabotanniy spisok') end;

'0':exit;
end;
until false;
END.

Неизвестный
25.04.2009, 11:54
общий
к примеру если текстовый файл содержит числа:

3 2 4 11 7 11 23 8 2 8 2 3 6 5 7 2

процедура удаляет первую 3, 7, находящуюся между 11 - 7 - 11, затем из 8 2 8 2 удаляет внутреннюю 2 и 8 - все эти действия выполняются правильно, но также процедура удаляет последнее число - 2. Как избавиться от этого?
Неизвестный
25.04.2009, 14:39
общий
Удаление у вас сделано в принципе неправильно - посмотрите мой код: вам нужно сделать два обхода списка - на первом только пометить элементы для удаления (нужно завести еще один флаг, как у меня) и ничего не удалять не в коем случае, а на втором уже удалить помеченые.

Вот так, например
В структуру добавлено еще одно поле: del: boolean;
Код:

type stud=record
info:integer;
adr:uk;
del: boolean;
end;

и процедура:
Код:

Procedure DEL_SOSED;
begin
{ Я не делал проверку на кол-во элементов в списке, так что если }
{ их менее 2-х, то поведение программы не предсказуемо }
{ Первый проход по списку - помечаем на удаление }
{ Первый элемент проверим отдельно }
first^.del:=false;
p1:=first;
repeat
p1:=p1^.adr;
p1^.del:=false;
until p1^.adr=nil; { Находим конец списка и заодно сбрасываем флаг удаления }
if first^.adr^.info=p1^.info then first^.del:=true;
{ Затем проверяем все остальные }
p1:=First; { Предыдущий }
p2:=First^.adr; { Тот который проверяем }
repeat
if p2^.adr=nil then begin { Это последний элемент }
if p1^.info=first^.info then p2^.del:=true;
end else
if p1^.info=p2^.adr^.info then p2^.del:=true;
p1:=p1^.adr;
p2:=p1^.adr;
until p2=nil;
{ Второй проход - удаляем помеченные элементы }
{ Начнем со второго }
p1:=First; { Предыдущий }
p2:=First^.adr; { Тот который удаляем }
repeat
if p2^.del then begin
p1^.adr:=p2^.adr;
dispose(p2);
end else
p1:=p1^.adr;
p2:=p1^.adr;
until p2=nil;
{ Первый удалим отдельно }
if First^.del then begin
p1:=First^.adr;
dispose(First);
First:=p1;
end;
{ Все }
end;


По условиям задачи лучше использовать кольцевой двунаправленный список, я так и сделал, но не посмотрел, что список должен быть линейным. Сорри.

С уважением, Дмитрий
Неизвестный
25.04.2009, 15:48
общий
сделать флаг - пометить то есть?
Неизвестный
25.04.2009, 15:52
общий
почему паскаль не может распознать p1^.del:=false; ?
Неизвестный
25.04.2009, 21:28
общий
А вы добавили в определение структуры поле del:boolean;?
(Первый код в моем посте?)
Неизвестный
25.04.2009, 21:37
общий
дада... конечно добавил!
Неизвестный
25.04.2009, 21:39
общий
оп( сорри...не туда добавил...
Неизвестный
25.04.2009, 21:47
общий
теперь процедура работает, но проблема в том, что не учили нас использовать так булевую переменную.

есть еще один код, точнее изменена всего одна цифра в предыдущем моем коде:

Procedure DEL_SOSED;
begin
p3:=first;
p:=false;
while p3^.adr<>nil do
p3:=p3^.adr;
if first^.adr^.info=p3^.info then
begin
p2:=first;
first:=first^.adr;
dispose(p2);
end;
p1:=first^.adr;
p2:=first;
while p1^.adr<>nil do
begin
if (p1^.adr^.info=p2^.info) and (not p) then
begin
b:=p1^.info;
p:=true;
p1:=p1^.adr;
p3:=p2^.adr;
dispose(p3);p2^.adr:=p1;
end;
if (p1^.adr^.info=b) and p then
begin
b:=p1^.info;
p3:=p1;
p1:=p1^.adr;
p2^.adr:=p1;
dispose(p3);
end
else
begin
p:=false;
p2:=p1;
p1:=p1^.adr;
end;
end;
if p2^.info=first^.info then {раньше тут была строчка if p1^.info=first^.info then}
begin
p2^.adr:=nil;
dispose(p1);
end;
end;

процедура работает правильно и удаляет все как положено, учитывая все случаи. Есть ли в ней недостатки, и существенны ли они?
Неизвестный
25.04.2009, 22:12
общий
Вот вам случай который она не учитывает:
3 2 3 11 7 11 23 8 2 8 2 3 6 5 7 2
Должны удалиться первые 3 и 2, а удаляется только первая 3.

А что мешает вместо булевой переменной использовать например byte; и присваивать ему 0 вместо false и 1 вместо true?
Неизвестный
25.04.2009, 22:17
общий
и вправду двойку оставляет на месте.. но без данного признака процедуру не написать, как я понимаю...и без 0 и 1..
Неизвестный
25.04.2009, 22:43
общий
С признаком более простой вариант получается. Ну я тут прикидывал, что наверное можно и без него, только сложнее: там такие условия придется проверять, что черт ногу сломит. Хотя, если это принципиально, можно попробовать.
Неизвестный
25.04.2009, 22:47
общий
хмм....тогда лучше наверное оставить ваш код...
Неизвестный
25.04.2009, 22:57
общий
Вобще алгоритм получается такой
Проверяем условие
если решаем удалить текущий элемент, то надо опять проверить условие уже для след.элемента,
если удаляем и следующий, то проверяем условие и для 2-го следующего и так пока условие не выполниться и очередной элемент удалять
не надо будет - тогда удаляем всю цепочку и идем дальше.
Хм. Может быть не так уж и сложно получится. Счас попробую написать, а вы уж тогда смотрите сами, что лучше.
М.б. код и получится не большим, но для понимания мой первый вариант будет явно проще.
Неизвестный
25.04.2009, 22:59
общий
спасибо огромное за помощь!!! жду второй вариант!
Неизвестный
25.04.2009, 23:52
общий
Вы знаете, а ведь ваш код ведь был практически рабочим. Он ошибался только если под условия удаления подпадали первый или последний элементы. Я его немного упростил сведя условия под один if, убрал удаление первого элемента, заменив его на установку флага удаления, перенес удаление первого элемента в зависимости от этого флага в конец и исправил условие на удаление последнего элемента.
Вообщем смотрите, если что непонятно - разъясню. По-моему, все довольно лаконично вышло. Почему-то мне такой вариант сразу в голову не пришел.

Код:

Procedure DEL_SOSED;
var delfirst: boolean; { Добавил переменную для удаления первого элемента в конце процедуры }
begin
delfirst:=false; {По-умолчанию первый не удаляем}
p3:=first; {Если в этой части заменить p3 например на p1 - то необходимость в p3 вообще отпадает и ее можно удалить}
p:=false;
while p3^.adr<>nil do p3:=p3^.adr;
if first^.adr^.info=p3^.info then
delfirst:=true; {Здесь было удаление первого элемента}
p1:=first^.adr;
p2:=first;
while p1^.adr<>nil do
begin
if (p1^.adr^.info=p2^.info) and not p or (p1^.adr^.info=b) and p then {Свел ваших два if в один, потому как они делали одно и тоже}
begin
p:=true;
b:=p1^.info;
p1:=p1^.adr;
dispose(p2^.adr);
p2^.adr:=p1;
end
else
begin
p:=false;
p2:=p1;
p1:=p1^.adr;
end;
end;
{Исправил условие удаления последнего элемента по аналогии с условием в цикле}
if (p2^.info=first^.info) and not p or (b=first^.info) and p then
begin
p2^.adr:=nil;
dispose(p1);
end;
{Ну и наконец удаляем первый элемент}
if delfirst then begin
p1:=First^.adr;
dispose(First);
First:=p1;
end;
end;
Неизвестный
25.04.2009, 23:53
общий
спасибо большое!!!!!!!!!!!!!!!!я разберусь с процедурой и отпишу!
Форма ответа