переупорядочение файла, с помощью списка Опции

[Svetlana]

Всем доброго дня и ночи! Сегодня у меня был экзамен и надо было решить такую задачу:
Дан файл целых чисел.Переупорядочить его по неубыванию с помощью списка.Оформить в виде процедуры
Вот что я написала:

procedure Upor (var tsl;f);
var           x,min:integer;
begin       repeat begin reset(f); min:=0; while not eof(f) do begin
                                  read(f,x); if x<min then min:=x end;

                                  in-list(p,min,q);
                                     
                                  reset(f); 
                                  while not eof(f) do begin
                                  read(f,x); if x<min then min:=x end;
                                  {здесь оператор(станд. процедура или функция),который удаляет найденное число}

                                                           end
             until filesize(f)<>nil
Close(f)
end;

Теперь поясню то,что я хотела этим сказать:1.Ищем в файле мин.число,включаем его в список
2.Удаляем из файла минимум
3.Опять ищем в файле минимум,включаем его в список и удаляем из файла...Получается цикл,который заканчивается,когда файл станет пустым.

Моя ошибка,на которую указал преподаватель в том,что я минимуму присваиваю 0. Т.е. я не предуссматриваю случаи с отрицательными числами.И вообще она не эффективная...Укажите на ошибки,пожалуйста,если они здесь ещё есть.И как можно было решить эту задачу по-другому?Очень интересно...

Сообщение отредактировано: Svetlana - 29.06.2009 12:10

[volvo]

Укажите на ошибки,пожалуйста,если они здесь ещё есть

1)

здесь оператор(станд. процедура или функция),который удаляет найденное число

Нет такой стандартной процедуры, чтобы из файла удалить число.

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

P.S.

filesize(f)<>nil

Это что? Вообще-то FileSize возвращает размер (число), а не указатель...

[Svetlana]

Спасибо! Но я не могу понять,ведь со списком допустимы только три операции:просмотр списка,добавление элемента и удаление одного элемента. Так как происходит переупорядочение в списке?Мне этого не понять.

P.S. Если заменить FileSize<>0 будет правильно?Я так думаю...

[volvo]

ведь со списком допустимы только три операции:просмотр списка,добавление элемента и удаление одного элемента.

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

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

Если заменить FileSize<>0 будет правильно?

На уровне псевдокода - да, но реализация будет очень медленной. Представь, что у тебя файл из 50 элементов. Значит, тебе надо открыть файл и пройти по нему 49 раз (а это значит, сколько всего элементов ты прочитаешь из файла за эти 49 проходов?). А проход по файлу - это очень длительное занятие (относительно работы с памятью, конечно)... А если элементов будет 200, а не 50, что тогда?

[Krjuger]

допустимы только три операции:просмотр списка,добавление элемента и удаление одного элемента

Вот именно!!! различные комбинации этих действий и будут давать вам ваш результат.Вы знакомы с сортироваками в массиве?принцип такой же может быть.Например, вы смотрите на вашу информационную часть первого элемента списка,запоминаете ее,затем переходите ко второму элементу и сравниваете его информационную часть,если у второго меньше, то записываете на первое место,если нет,то переходите дальше к третьему и тд.Я правда подзабыл,как такая сортировка называется,вроде сортировка кучей.А вообще можно любую сортировку приспособить для списка.

Переупорядочить его по неубыванию

Тобиш надо упордочить по возрастанию?:0 Велик и богат наш русский язык.
А вообще ключевые слова в вашем задании:
......с помощью списка....
А ты посути просто береш список и туда уже в упорядоченном виде записываеш.А задание предполагает,что ты заполниш список,как есть в файле и уже в списке начнеш упорядочивать,ну или вариант Volvo"сразу добавлять элемент в список, сохраняя его упорядоченность по неубыванию".Иначе использование списка становится совсем бессмысленным.И еще желательно было указать какой список вы подразумеваете:однонаправленный или двунаправленный....
И еще у вас в коде указана процедура in-list,ну так почему вы ее не выложите?Ведь ее реализовать тоже можно по разному.

Сори,когда писал не видел сообщение Volvo(его тогда е было,когда начал писать).

Значит, тебе надо открыть файл и пройти по нему 49 раз (а это значит, сколько всего элементов ты прочитаешь из файла за эти 49 проходов?)

В худшем случае 49! да и еще не надо забывать,что помимо открытия ей еще надо перезаписывать файл удаляя элемент из него,а это еще замедляет процесс.49 раз как никак придется открыть, считать, удалить, закрыть

Сообщение отредактировано: Krjuger - 29.06.2009 13:06

[volvo]

Тобиш надо упордочить по возрастанию?

Неубывание <> возрастание...

1, 2, 3, 4, 5, 6, 7 - это возрастание (каждый следующий элемент СТРОГО больше предыдущего)
1, 1, 2, 3, 4, 5, 6, 6 - это неубывание (каждый следующий НЕ МЕНЬШЕ предыдущего)

Как упорядочить по возрастанию (чтоб каждый элемент был строго больше предыдущего) последовательность 3, 6, 9, 2, 8, 3, 5, 1, 9, 6?

[Krjuger]

Какие тонкости ))Мне действительно надо ответить на твой вопрос?

Неубывание <> возрастание...

Это как это извините???Уж яснее было бы если ты сказал,что возрастание это множество неубывания.

[Svetlana]

procedure in-list(var p:tsl;a:telement;q:tsl);
{p-указатель ссылки на начало списка,а-включаемая в список запись,q-сылка на звено,после которого нужно включить новую запись,еслиq=nil,то включение в начало списка}
var           r:tsl;
begin        new®; r^.element:=a;r^.next:=nil;
                if p=nil then {список пустой}p:=r  else 
                                    if q=nil then {включение в начало списка} begin r^.next:=p;p:=r end else 
                                                          begin r^.next:=q^.next;q^.next:=r end
end;

Добавлено через 3 мин.
Спасибо за ссылку!

З.Ы. Ту последовательность,что ты дал...её же нельзя упорядочить по возрастанию?Так получается. Вот по неубыванию можно...

[volvo]

Это как это извините

<> что означает, не знаешь? Читай доки в таком случае... возрастание и убывание - это РАЗНЫЕ вещи, специально для Krjuger-а, не разбирающегося в синтаксисе Паскаля...

Уж яснее было бы если ты сказал,что возрастание это множество неубывания.

Яснее кому? Тебе? Ну, можешь считать сам как тебе яснее. А как объяснять, я все-таки сам решу, без посторонней помощи...

Svetlana, твоя программа компиляцию не пройдет. Ничем. Минус нельзя использовать в идентификаторах, у него другая функциональность.

[Svetlana]

Ведь можно просто переименновать,это же не проблема...

[Krjuger]

<> для меня означает все,что угодно кроме.....И для меня неубывание никак не попадает под это определение.

Ту последовательность,что ты дал...её же нельзя упорядочить по возрастанию?Так получается. Вот по неубыванию можно...

ее можно упорядочить по возрастанию,просто при совпадении элементов один из них просто не попадет в упорядоченную последовательность,тобиш получится 1,2,3,5,6,8,9.

Ведь можно просто переименновать,это же не проблема...

Это не является проблемой при исправлении,но это является ошибкой.Твоего преподавателя не будет интересовать почему не работает твоя программа,из за непоставленного ';' или из за неправилного алгоритма,ему важен результат.

Сообщение отредактировано: Krjuger - 29.06.2009 13:55