Перенести в начало списка все отрицательные элементы, вернуть количество переносов - Pascal
Формулировка задачи:
Дана, вот такая вот задачка: "«Перенести» в начало списка все отрицательные элементы, вернуть количество переносов."
Односвязный список и все такое. Проблема в том, что я ни как не могу придумать алгоритм решения данной задачи.
Решение задачи: «Перенести в начало списка все отрицательные элементы, вернуть количество переносов»
textual
Листинг программы
const
count = 25;
type
tList = ^rList;
rList = record
N : Integer;
X : tList;
end;
function Create : tList;
var
First, Cur : tList;
i : Integer;
begin
New(First);
First^.N := Random(21)-10;
Cur := First;
for i := 2 to count do
begin
New(Cur^.X);
Cur := Cur^.X;
Cur^.N := Random(21)-10;
end;
Cur^.X := nil;
Create := First;
end;
procedure See(List : tList);
begin
while List <> nil do
begin
Write(#32, List^.N);
List := List^.X;
end;
WriteLn;
end;
procedure MoveToBegin(var List : tList);
function isolate(E : tList) : tList;
var
Cur : tList;
begin
if E = List then
List := List^.X
else
begin
Cur := List;
while Cur^.X <> E do
Cur := Cur^.X;
Cur^.X := E^.X;
end;
isolate := E;
end;
procedure connect(var L, E : tList);
var
Cur : tList;
begin
if L = nil then
L := E
else
begin
Cur := L;
while Cur^.X <> nil do
Cur := Cur^.X;
Cur^.X := E;
end;
end;
var
Cur, Tmp, Negative, tmpNegative : tList;
begin
Negative := nil;
Cur := List;
while Cur^.X <> nil do
if Cur^.N < 0 then
begin
Tmp := Cur;
Cur := Cur^.X;
tmpNegative := isolate(Tmp);
tmpNegative^.X := nil;
connect(Negative, tmpNegative);
end
else
Cur := Cur^.X;
if Negative <> nil then
begin
Tmp := List;
List := Negative;
connect(List, Tmp);
end;
end;
var
List : tList;
begin
Randomize;
List := Create;
WriteLn('Список:'); See(List);
MoveToBegin(List);
WriteLn('Отрицательные в начале:'); See(List);
end.
Объяснение кода листинга программы
- Определение константы
countсо значением25 - Определение типа
tListкак указателя наrList - Определение структуры
rListс полямиNтипа Integer иXтипа указателя наtList - Определение функции
Createбез параметров, которая возвращает указатель наtList - Определение переменных
First,Cur,iтипа Integer - Выделение памяти для
First - Присвоение случайного значения от -10 до 10 полю
NструктурыFirst - Присвоение
CurзначенияFirst - Цикл от 2 до
countа. Выделение памяти дляCur^.X(следующего элемента списка) b. Переход к следующему элементу списка c. Присвоение случайного значения от -10 до 10 полюNструктурыCur^.X - Присвоение
Cur^.Xзначение nil (конец списка) - Возврат значения
Firstиз функцииCreate - Определение процедуры
Seeс параметромListтипа указателя наtList - Цикл, пока
Listне равно nil а. Вывод значения List^.N (элемента списка) b. Переход к следующему элементу списка - Вывод в консоль символа новой строки
- Определение процедуры
MoveToBeginс параметромListтипа указателя наtList - Определение функции
isolateс параметромEтипа указателя наtList, возвращающую указатель наtList - Определение процедуры
connectс параметрамиLиEтипа указателя наtList - Определение переменных
Cur,Tmp,Negative,tmpNegativeтипа указателя наtList - Присвоение
Negativeзначения nil - Присвоение
CurзначенияList - Цикл, пока
Cur^.Xне равно nil а. Если значение поляNу текущего элемента списка меньше 0- Присвоение
TmpзначенияCur - Переход к следующему элементу списка
- Присвоение
tmpNegativeзначенияisolate(Tmp) - Присвоение поля
XспискаtmpNegativeзначения nil - Вызов
connectс параметрамиNegativeиtmpNegativeb. Иначе - Переход к следующему элементу списка
- Присвоение
- Если
Negativeне равно nil а. ПрисвоениеTmpзначенияListb. ПрисвоениеListзначенияNegativec. Вызовconnectс параметрамиListиTmp - Определение переменной
Listтипа указателя наtList - Генерация случайных чисел
- Присвоение
Listзначения возвращаемого функциейCreate - Вывод текста
Список:в консоль - Вызов процедуры
Seeс параметромList - Вызов процедуры
MoveToBeginс параметромList - Вывод текста
Отрицательные в начале:в консоль - Вызов процедуры
Seeс параметромList - Конец программы