Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Циклический сдвиг

Автор: Гость 22.02.2007 3:04

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

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

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

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


 ! 
Как оказалось позднее, ты сделал это ДВА раза!
Второе ПРЕДУПРЕЖДЕНИЕ!
Твоя подсеть может вся пострадать за тебя..
Lapp


Автор: Lapp 22.02.2007 8:55

Показываю на примере простого массива. Не знаю, что ты имел в виду под использованием динамической организации - уточни.

Сначала запоминаем последний элемент в буфер.
Затем делаем цикл сверху вниз от 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 23.02.2007 3:41

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

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


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

Автор: Lapp 23.02.2007 9:58

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

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

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

Автор: xds 23.02.2007 10:15

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

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

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 24.02.2007 3:03

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

Автор: -Sasha- 10.06.2007 5:29

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