Циклический сдвиг, на динамических данных Опции

[Гость]

Помогите плиз!
Нужно с помощью динамичесой организации данных, организовать сдвиг впрво. Пример вводим L1=(a, b, c) , а выводим L2=(c, a, b).

Кто поможет в двух-трёх словах как лучше организовать цикличкский сдвиг на одни элемент вправо?

сразу большое спасибо

М

Гость, не задавай вопросы в чужих темах! Предупреждение.. Тема разделена. Lapp

!

Как оказалось позднее, ты сделал это ДВА раза! Второе ПРЕДУПРЕЖДЕНИЕ! Твоя подсеть может вся пострадать за тебя.. 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

[Judgedim]

Извините пож-та! Каюсь, больше не буду!

Я имел ввиду связанный список с динамическим выделенияем памяти (лаба про динамические структуры данных).


P.S. Вообщето задание на С, но спасибо если кто-чего подскажет и на Паскале, думаю пойму .

Сообщение отредактировано: Judgedim - 22.02.2007 23:49

[Lapp]

Если список - то ход решения может быть разным.
В принципе, можно сделать и аналогично, но только это будет нерационально, особенно в случае однонаправленного списка (в нем от одного элемента можно перейти вперед, к следующему, но нельзя перейти назад, к предыдущему). В двунаправленных списках, грубо говоря, работы будет столько же, сколько и с массивом. Но суть в том, что в списках (обоих типов) это можно сделать даже быстрее, чем в массиве. Вот примерный алгоритм (для однонаправленного списка)..

1. Содержимое самого начального указателя (указателя на список) перекладываешь в указатель последнего элемента (который до этого содержал NIL).
2. В начальный указатель списка кладешь содержимое указателя предпоследнего элемента.
3. В указатель предпоследнего элемента кладешь NIL.

Все это нужно делать именно в указанной последовательности, чтобы не затереть информацию в процессе.
Сказанное проиллюстрировано рисунком:

Сверху - начальное состояние списка, внизу - циклически сдвинутый список.
Как видишь, то, что с массивом делалось в цикле (зависящем от длины массива), в списке делается тремя присваиваниями.. Конечно, чтобы найти последний и предпоследний элемент, все равно нужен цикл (типа while или repeat).. Но если элементы крупные (большие записи), то это все равно будет эффективнее.

[xds]

Вообщето задание на С

Здесь будет только на Паскале. Иначе - в разделе "Другие языки".

Вот возможная реализация. Используется двунаправленный список с фиктивным элементом. Такая организация списка позволяет без дополнительного просмотра списка: добавлять элементы в начало и конец списка, удалить любой элемент, вставить элемент в произвольное место списка, выводить список в любом порядке, сдвигать список с обоих направлениях. Использование фиктивного элемента избавляет нас от проверок на пустоту списка и его границы. Разберись - пригодится!

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.

[Judgedim]

Big thanks.
Буду разбираться

[-Sasha-]

Извините, но программа циклится. Подскажите в чем тут дело?