списки, списки Опции

[Krjuger]

А вам не кажется,klik1602,что ваша задача совсем другая по сравнению с топик стартером и имело бы смысл создать свою тему,да и поиск по сортировкам вам выдаст уйму результатов.У человека в данной теме проблема с самим списком,а ваша задача решается вообще без списков ,т.к

количество элементов в списке нам должно быть известно заранее

,что вам мешает тогда завести обычный массив,для которого в интернете тонна методов сортировки и приведенного кода.

Так что ,во-первых,уточните каким методом вам нужно отсортировать и как именно отсортировать.
Как имея,заведите 3 переменных,которые будут обозачать минимальный элемент,максимальный и количество,пройдитесь по вашему файлу и найдите минимальный максмальный элементы и количество,теперь у вас есть вся информация чтобы сделать массив удовлетворяющий сразу всем вашим условиям...

[klik1602]

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

Сообщение отредактировано: klik1602 - 2.03.2011 16:30

[volvo]

мне не понятно как перестроить массив?

Не надо массив перестраивать. Перестроить нужно список. Ничего, кроме как сделать нагло, но действенно, в голову пока не приходит:

const
   n = 5; { Это размер списка и массива }

   { Для теста - пусть будет константой }
   arr : array[1 .. n] of integer = (4, 2, 1, 5, 3);

{ В процедуру передаем указатель на голову списка,
   на выходе будем иметь по тому же указателю перестроенный список }
procedure rearrange (var start : plist);
var
   Links : array[1 .. n] of plist; { <--- Вот это - та самая наглость }

   function get_item (n : integer) : plist;
   var
      p : plist;
      i : integer;
   begin
      p := start;
      for i := 1 to n - 1 do p := p^.next;
      get_item := p;
   end;

var
  i : integer;
  new_start : plist;
begin
   { Сначала запоминаем все позиции элементов списка в нужном порядке }
   for i := 1 to n do
      Links[i] := get_item (arr[i]);

   { , а потом переназначаем указатели Next. Последний Next должен указывать в пустоту }
   start := Links[1];
   for i := 2 to n do
      Links[i - 1]^.next := Links[i];
   Links[n]^.next := nil;
end;

{ Вызывать - так, например: }
var
   i : integer;
   s, f : plist;
begin
   s := nil; f := nil;
   { Для примера, заполняем список значениями 1 .. 5, и смотрим, что получится: }
   for i := 1 to n do
      append (i, s, f); { <--- Эту процедуру я выкладывал неоднократно, поиском пользуемся }
   print(s);

   { перестраиваем список }
   rearrange(s);
   print(s);

   { Не забываем удалять список ... }
end.

На выходе:

   1   2   3   4   5
   4   2   1   5   3

, то есть, список переформирован.

[klik1602]

{ <--- Эту процедуру я выкладывал неоднократно,-поиском пользуемся } =мм( я не нашла, можете ещё раз скинуть, если не сложно)

[volvo]

Плохо искала. Вот тут она лежит, например:
Задача с использованием списка

[klik1602]

function get_item (n : integer) : plist - это функция получения указателя на голову списка?? и зачем new_start : plist? я не нашла где он используется?
мм, что-то у меня программа абру-кадабру а не переставленный список выдала))
вот мои наработки..

uses
 crt; {dlya ispol'zovaniya readkey i clrscr}
type
 Tinf=integer; {tip dannih elementa spiska}
 List=^TList; {ukazatel na element tipa TList}
 TList=record
  data:Tinf;
  index:Tinf;
  next:List;
 end;
 mass=array[1..10] of integer;
 stroka=string[30];
var
spis1,news1:List;
flag:boolean;
a:mass;
n:integer;


procedure vvodlist (var spis1:List);
var
 tmp:List;
 x:integer;
 f:text;
begin
 assign(f,'L14_spis.txt');
 reset(f);
 while not eof(f) do
 begin
  read(f,x);
  if spis1=nil then
  begin
   GetMem(spis1,sizeof(TList));
   tmp^.data:=x;
   tmp:=spis1;
 end
 else
 begin
  tmp:=spis1;
  while tmp^.next<>nil do
  tmp:=tmp^.next;
  GetMem(tmp^.next,sizeof(TList));
  tmp:=tmp^.next;
 end;
 tmp^.next:=nil;
 Tmp^.data:=x;
 end;
 close(f);
end;


procedure vivodlist(var spis1:List; flag:boolean;zag:stroka);
var
 fout:text;
begin
 assign(fout,'L14_itog.txt');
 if flag then
  rewrite(fout)
 else
  append(fout);
 writeln(fout,zag);
 while spis1<>nil do
 begin
  write(fout,spis1^.data,' ');
  spis1:=spis1^.next;
 end;
 writeln(fout);
 close(fout);
end;


procedure vvodmatr(var a:mass);
var
 i:integer;
 f:text;
begin
 assign(f,'L14_mass.txt');
 reset(f);
 for i:=1 to 10 do
 begin
  read(f,a[i]);
    end;
 close(f);
end;

procedure vivodmatr(a:mass);
var
 i:integer;
 fout:text;
begin
 assign(fout,'L14_itog.txt');
 append(fout);
 writeln(fout,'Massiv');
 for i:=1 to 10 do
 begin
   write(fout,a[i],' ');
 end;
  writeln(fout);
 close(fout);
end;

procedure sort(var spis1:List);
var
 Links : array[1 .. 10] of List;

function get_spis (n : integer) : list;
 var
  p:list;
  i : integer;
   begin
      p:=spis1;
      for i := 1 to n - 1 do p:= p^.next;
      get_spis:= p;
   end;

var
  i : integer;
  news1:list;
begin
   for i := 1 to n do
      Links[i] := get_spis(a[i]);
      spis1:= Links[1];
   for i := 2 to n do
      Links[i - 1]^.next := Links[i];
   Links[n]^.next := nil;
end;



begin
 n:=10;
 spis1:=nil;
 vvodlist(spis1);
 flag:=true;
 vivodlist(spis1,flag,'First Spisok');
 vvodmatr(a);
 vivodmatr(a);
 sort(spis1);
 flag:=false;
 vivodlist(spis1,flag,'Otsort Spisok');
end.

Сообщение отредактировано: klik1602 - 3.03.2011 14:54

[volvo]

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

[TarasBer]

> for i := 1 to n do
> Links[i] := get_item (arr[i]);

Мне это место почему-то не нравится.

[volvo]

Не знаю, почему. Опять преоптимизация? Предложи другое решение, посмотрим, понравится ли оно мне...

Добавлено через 6 мин.

мм, что-то у меня программа абру-кадабру а не переставленный список выдала))

То есть, ты действительно считаешь, что я должен проверить твой код на всех возможных значениях входного файла? Мне так не кажется. У тебя не работает - будь добра присоединить те данные, с которыми у тебя не работает.

Повторяю еще раз: само переформирование списка производится. Запусти пример в том виде, в котором я его привел, и убедись. А уж то, что ты либо некорректно читаешь список, либо его некорректно выводишь, либо неправильно заполняешь массив, согласно которому его надо перестроить - это как-то ко мне никакого отношения не имеет. Это сугубо твои проблемы, сделай правильно - будет работать.

Добавлено через 9 мин.
Ну вот, все встало на свои места. У тебя при входе в Sort указатель на голову списка уже нулевой. Исправляй свою процедуру вывода списка в файл, потом будешь предъявлять претензии

[klik1602]

=))) урррра)))) я поняла о чём вы))) всё исправила)) всё работает))) спасибо большое-прибольшое)))))))

[TarasBer]

> Не знаю, почему. Опять преоптимизация?

Лепить префикс "пре" на любую оптимизацию - это шаблон говнокода (когда придёт время оптимизировать _алгоритм_, будет поздно). Как и собственно сама преоптимизация (на уровне _кода_, который всегда можно отоптимизировать в последний момент), кстати, но тут её нет.

> Предложи другое решение, посмотрим, понравится ли оно мне...

for i := 1 to n do
Links[i] := get_item (arr[i]);

Эквивалентно

for i := 1 to n do
Links[revarr[i]] := get_item (i);

где revarr строится так:
for i := 1 to n do revarr[arr[i]] := i;

а вот уже "for i := 1 to n do что-то там с get_item(i)" можно заменить на проход списка.

А можно и не заменять, а сделать универсальнее get_item (добавить в неё немного искуственного интеллекта):

  function get_item (n : integer) : plist;

     var i : integer;
     const lastn: integer := 0; // запоминаем число последнего поиска
     const lastp: plist := nil; // запоминаем результат последнего поиска

   begin
      if lastn = n then // ничего не делаем
      else if lastn = n+1 then p := lastp^.next
      else begin 
        lastp := start;
        for i := 1 to n - 1 do lastp := lastp^.next;
      end;

      lastn := n;
      get_item := lastp;
   end;  

(кстати, форум таки жрёт пробелы вне тега кода)