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

Автор: Iryska 24.12.2009 0:54

помогитe, кто чeм можeт. a то сaмa сдeлaть нe могу) литeрaтурa проходит мимо мозгa) ''Дан неупорядоченный
линейный односвязный список
и массив , содержащий номера
соответствующих элементов в
упорядоченном списке .
Перестройте данный список в
соответствии с номерами ,
заданными массивом''

Автор: Lapp 24.12.2009 6:55

Цитата(Iryska @ 24.12.2009 0:54)

Автор: Iryska 24.12.2009 9:42

увaжaeмый, aдминистрaтор, вы можeтe помочь мнe с нaписaниeм сaмого кодa, плиз!

Автор: Lapp 24.12.2009 9:59

Цитата(Iryska @ 24.12.2009 9:42)

Автор: Iryska 24.12.2009 10:03

зaявлeниe можно, a по коду ничeго нeзнaю)

Автор: Lapp 24.12.2009 12:12

Цитата(Iryska @ 24.12.2009 10:03)

Автор: Iryska 24.12.2009 12:50

нe очeнь(

Автор: Lapp 24.12.2009 13:13

Цитата(Iryska @ 24.12.2009 12:50)

Автор: Iryska 24.12.2009 13:34

В этой задаче я знаю как сортировать массив( а все остольное...увы нет(

Автор: Lapp 24.12.2009 14:37

Цитата(Iryska @ 24.12.2009 13:34)

Автор: Iryska 25.12.2009 13:12

это простым выбором(

 
uses crt;
type ar=array [1..100] of integer;
var a1:ar;
procedure sort(var a:ar);
var i,n,j,k,min:integer;
begin
 writeln('vvedite kol-vo elementov');
 read(n);
 for i:=1 to n do
 begin
 writeln('element#',i);
 read(a[i]);
 end;
 for i:=1 to n do
 begin
 k:=i;    {k,i,j-index}
 min:=a[i];
 for j:=i to n do
 if a[j]<min then
 begin
 k:=j;
 min:=a[j]
 end;
 a[k]:=a[i];
 a[i]:=min;
 end;
 for i:=1 to n do  {write new massiv}
 write(a[i],' ');
 end;
 begin
  clrscr;
  sort(a1);
  readkey;
  end.

Автор: Iryska 25.12.2009 18:40

Уважаемый Андрей вы говорили поможите(

Автор: Lapp 27.12.2009 10:58

Если у тебя появились наработки - давай их сюда.

Я чуть позже сегодня посмотрю и напишу что-нибудь. Плохо, конечно, что у тебя нет даже реализации списка..

Автор: Iryska 29.12.2009 10:35

Aндрей, у меня ничего не получаеться( сижу тупо у манитора(

Автор: Ozzя 29.12.2009 11:19

Тут есть реализация списка
http://volvo71.narod.ru/faq_folder/oop_dds.htm#dds_list_sx

Автор: Iryska 29.12.2009 15:28

дa эт ссылкa мнe ничeго нe дaлa( Андрeй, помоги пожaлусто, aто послeдний зaчeт, a сдeлaть никaк. пожaлусто, помоги

Автор: volvo 29.12.2009 15:32

Автор: Lapp 29.12.2009 20:31

Цитата(Iryska @ 29.12.2009 15:28)

Автор: Iryska 29.12.2009 22:36

Андрeй, я тeбe зaвтрa вeчeром нaпишу, a то прост, дaлeко от компьютeрa(

Автор: klik1602 1.03.2011 22:16

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


решила не ломать себе голову над массивом - введу заранее подготовленный, для меня сейчас главное алгоритм сортировки списка..я не понимаю как реализвоать сортировку..подскажите,пожалуйста, как это можно сделать, буду очень благодарна!)

Автор: Krjuger 2.03.2011 11:42

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

Автор: klik1602 2.03.2011 12:12

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

Автор: volvo 2.03.2011 20:01

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 2.03.2011 20:20

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

Автор: volvo 2.03.2011 20:37

Плохо искала. Вот тут она лежит, например:
http://forum.pascalnet.ru/index.php?s=&showtopic=21938&view=findpost&p=123453

Автор: klik1602 3.03.2011 10:11

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.

Автор: volvo 3.03.2011 10:20

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

Автор: TarasBer 3.03.2011 10:55

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

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

Автор: volvo 3.03.2011 10:57

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

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

Автор: klik1602 3.03.2011 11:25

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

Автор: TarasBer 3.03.2011 13:22

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

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

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

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;