Динамические структуры данных Опции

[kess]

Составить программу . которая переносит в конец непустого списка L эго первый элемент

[Lapp]

Теперь у тебя есть несколько (много) орехов, зарытых в ямки с записками. И тут ты вспоминаешь: первый орех был грецкий, а все остальные - обычные лесные.. И ты решаешь: грецкий орех надо оставить на закуску, то есть съесть последним. Но как это сделать? ведь он лежит в самой первой ямке!

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

1. Берешь самую первую записку (из спец.укромного места) - она указывает на ямку с грецким орехом - и кладешь ее пока в карман.

2. Берешь записку из первой ямки (с грецким орехом) - она указывает на вторую ямку - и кладешь ее в спец.укромное место. Теперь список начинается со второй ямки, а в бывшей первой ямке (с грецким орехом) записки нет совсем.

3. Проходишь по всему списку, находишь последнюю ямку (в ней нет записки) и кладешь туда записку из кармана, которая указывает на ямку с грецким орехом. Она была первой - стала последней (на нее указывает бывшая последняя ямка, которая теперь стала предпоследней). Записки в ней нет (см. п.2), что согласуется с признаком последней ямки.

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

Вот программа, которая реализует приведенный алгоритм:

type
  pList=^tList;
  tList=record
    Next:pList;     {записка-указатель на след ямку}
    Q:string        {тут будет сам орех}
  end;

procedure AddToList(s:string; var L:pList);
var
  M:pList;
begin
  if L=Nil then begin  {если ямок еще не было}
    New(L);            {выкапываем самую первую ямку}
    M:=L
  end                  {если ямки уже были}
  else begin
    M:=L;
    while M^.Next<>Nil do M:=M^.Next;  {находим последнюю из них}
    New(M^.Next);      {выкапываем следующую и кладем записку, где она}
    M:=M^.Next
  end;
  M^.Q:=s;             {кладем орех в ямку}
  M^.Next:=Nil  {убираем записки, которые могли случайно оказаться в ямке}
end;

procedure PrintList(L:pList);
begin
  while L<>Nil do with L^ do begin
    WriteLn(Q);        {достаем орех}
    L:=Next            {переходим к следующей ямке}
  end
end;

procedure InitList(var L:pList);
begin
  L:=Nil               {кладем записку, что орехов нет}
end;

var
  Quatations,M,t:pList;
  s:string;

begin
  InitList(Quatations);
  WriteLn('Введите несколько цитат (для завершения введите пустую строку):');
  repeat
    ReadLn(s);                             {находим орех}
    if s<>'' then AddToList(s,Quatations)  {кладем его в следующую ямку}
  until s='';

  if Quatations=Nil then WriteLn('Список пуст!')
  else if Quatations^.Next<>Nil then begin
    WriteLn('Введенный список:');
    PrintList(Quatations);
    t:=Quatations;                      {это твой карман}
    Quatations:=Quatations^.Next;      {в начало кладем записку из первой ямки}
    M:=Quatations;
    while M^.Next<>Nil do M:=M^.Next;   {проходим по всем ямкам до последней..}
    M^.Next:=t;            {.. и кладем в нее записку из кармана}
    t^.Next:=Nilж
    WriteLn; WriteLn('Переставленный список:');
    PrintList(Quatations)
  end
end.

Теперь тебе понятно, что такое списки?..