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

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

Форум «Всё о Паскале» _ Задачи _ Сортировка списка простыми вставками

Автор: DOG-Paul 20.09.2006 17:16

Посомтрите код пожалуйста! Что не так?

Код

program sort1;
uses crt;
type
    plist = ^tlist;
    tlist = record
        info: integer;
        link: plist;
    end;
var    first: plist;
procedure sort (p: plist);                    {Процедура сортировки простыми вставками}
var t: plist;
begin
    while p<>nil do
        begin
            t:=p^.link;
            if p^.info>t^.info then
                begin
                    t^.link:=p;
                    p^.link:=t;
                    sort (first);
                    break;
                end;
            p:= p^.link;
        end;
end;
procedure print(p: plist);                    {Процедура вывода списка}
begin
    while p <> nil do
        begin
            write(p^.info, ' ');
            p := p^.link;
        end;
    writeln;
end;
procedure vvod (var first: plist);                {Процедура ввода списка}
var    s: integer;
    p, last: plist;
begin
    last := first;
    repeat
        write('Введите следующий элемент: ');
        readln(s);
        if s <> 0 then
            begin
                new(p);
                p^.info := s;
                p^.link := nil;
                if first = nil
                    then
                        first := p
                    else     last^.link := p;
                last := p;
            end;
    until s = 0;
end;
begin
    clrscr;
    writeln('Введите список:');
    first:=nil;
    vvod (first);
    sort (first);
    print(first);
    readkey;
end.

Автор: volvo 20.09.2006 17:21

Я же приводил уже рекурсивную функцию:
http://forum.pascal.net.ru/index.php?s=&showtopic=7992&view=findpost&p=55658

Автор: DOG-Pail 20.09.2006 20:48

Я понимаю, что пример вы приводили!
Но вот что вот в таком тексте программы не верно! Она выводит только 2 последних отсортированных! Проблема в сохранении указателя на первый элемент спика first
ПОМОГИТЕ ПЛИЗ!!!

Код
program sort1;
uses crt;
type
    plist = ^tlist;
    tlist = record
        info: integer;
        link: plist;
    end;
var    first: plist;
procedure sort (p: plist);                    {Процедура сортировки простыми вставками}
var t, t2: plist;
begin
    t:=p^.link;
    if t<>nil then
        if p^.info > t^.info then
            begin
                if first = p then
                          first:=t;
                t2:= t^.link;
                t^.link := p;
                p^.link := t2;
                sort (first);
            end
        else sort (p^.link);
end;
procedure print(p: plist);                    {Процедура вывода списка}
begin
    while p <> nil do
        begin
            write(p^.info, ' ');
            p := p^.link;
        end;
    writeln;
end;
procedure vvod (var first: plist);                {Процедура ввода списка}
var    s: integer;
    p, last: plist;
begin
    last := first;
    repeat
        write('Введите следующий элемент: ');
        readln(s);
        if s <> 0 then
            begin
                new(p);
                p^.info := s;
                p^.link := nil;
                if first = nil
                    then
                        first := p
                    else     last^.link := p;
                last := p;
            end;
    until s = 0;
end;
begin
    clrscr;
    writeln('Введите список:');
    first:=nil;
    vvod (first);
    sort (first);
    print(first);
    readkey;
end.

Автор: volvo 20.09.2006 21:11

Смотри, что ты делаешь:

procedure sort (p: plist); {Процедура сортировки простыми вставками}
var t, t2: plist;
begin
t:=p^.link;
if t<>nil then
if p^.info > t^.info then begin
if first = p then first:=t;

t2:= t^.link; { <--- А если t^.link = nil ?}
t^.link := p;
p^.link := t2;
sort (first);
end
else sort (p^.link);
end;

... что будет в указанном мной случае? Ты просто "отсечешь" все последующие элементы... Один элемент ты потеряешь в любом случае...

Так что не надо здесь мудрить с указателями, работай с данными:
procedure sort (p: plist);
var
t: plist;
X: integer;
begin
t := p^.link;
if t <> nil then

if p^.info > t^.info then begin
X := t^.info;
t^.info := p^.info;
p^.info := X;

sort (first);
end
else sort (p^.link);
end;
yes2.gif

Автор: Гость 20.09.2006 21:28

Да всё работает!
Но это будет как думаешь считаться првильм вариантом!?
Ведь у нас сортировка динамического списка?