Помогите плиз!
Нужно с помощью динамичесой организации данных, организовать сдвиг впрво. Пример вводим L1=(a, b, c) , а выводим L2=(c, a, b).
Кто поможет в двух-трёх словах как лучше организовать цикличкский сдвиг на одни элемент вправо?
сразу большое спасибо
М | Гость, не задавай вопросы в чужих темах! Предупреждение.. Тема разделена. Lapp |
! | Как оказалось позднее, ты сделал это ДВА раза! Второе ПРЕДУПРЕЖДЕНИЕ! Твоя подсеть может вся пострадать за тебя.. Lapp |
Показываю на примере простого массива. Не знаю, что ты имел в виду под использованием динамической организации - уточни.
Сначала запоминаем последний элемент в буфер.
Затем делаем цикл сверху вниз от n-1 до 1 по перекладыванию соседних ячкеек (из меньшего номера в больший).
Потом переносим содержимое буфера в первый элемент.
A:array[1..n]of tElement;
Buff:tElement;
.........
Buff:=A[n];
for i:=n-1 downto 1 do A[i+1]:=A[i];
A[1]:=Buff
Извините пож-та! Каюсь, больше не буду!
Я имел ввиду связанный список с динамическим выделенияем памяти (лаба про динамические структуры данных).
P.S. Вообщето задание на С, но спасибо если кто-чего подскажет и на Паскале, думаю пойму .
Если список - то ход решения может быть разным.
В принципе, можно сделать и аналогично, но только это будет нерационально, особенно в случае однонаправленного списка (в нем от одного элемента можно перейти вперед, к следующему, но нельзя перейти назад, к предыдущему). В двунаправленных списках, грубо говоря, работы будет столько же, сколько и с массивом. Но суть в том, что в списках (обоих типов) это можно сделать даже быстрее, чем в массиве. Вот примерный алгоритм (для однонаправленного списка)..
1. Содержимое самого начального указателя (указателя на список) перекладываешь в указатель последнего элемента (который до этого содержал NIL).
2. В начальный указатель списка кладешь содержимое указателя предпоследнего элемента.
3. В указатель предпоследнего элемента кладешь NIL.
Все это нужно делать именно в указанной последовательности, чтобы не затереть информацию в процессе.
Сказанное проиллюстрировано рисунком:
Сверху - начальное состояние списка, внизу - циклически сдвинутый список.
Как видишь, то, что с массивом делалось в цикле (зависящем от длины массива), в списке делается тремя присваиваниями.. Конечно, чтобы найти последний и предпоследний элемент, все равно нужен цикл (типа while или repeat).. Но если элементы крупные (большие записи), то это все равно будет эффективнее.
program ShiftList;
type
PList = ^TList;
TList = record
Prev, Next: PList;
n: Integer;
end;
procedure InitList(var List: TList);
begin
List.Prev := @List;
List.Next := @List;
end;
procedure AddItem(var List: TList; n: Integer);
var
p: PList;
begin
New(p);
p^.Next := @List;
p^.Prev := List.Prev;
List.Prev^.Next := p;
List.Prev := p;
p^.n := n;
end;
procedure FreeList(var List: TList);
var
p: PList;
begin
while List.Next <> @List do
begin
p := List.Next;
List.Next := p^.Next;
Dispose(p);
end;
List.Prev := @List;
end;
procedure ShrList(var List: TList);
var
p: PList;
begin
p := List.Prev;
List.Prev := p^.Prev;
List.Prev^.Next := @List;
p^.Next := List.Next;
p^.Next^.Prev := p;
p^.Prev := @List;
p^.Prev^.Next := p;
end;
procedure WriteList(const List: TList);
var
p: PList;
begin
p := List.Next;
while p <> @List do
begin
Write(p^.n, ' ');
p := p^.Next;
end;
Writeln;
end;
var
List: TList;
i: Integer;
begin
InitList(List);
for i := 1 to 10 do
AddItem(List, i);
WriteList(List);
ShrList(List);
WriteList(List);
ShrList(List);
WriteList(List);
ShrList(List);
WriteList(List);
FreeList(List);
Writeln;
end.
Big thanks.
Буду разбираться
Извините, но программа циклится. Подскажите в чем тут дело?