Неверно что при структуре требуется сортировка записей файла

Обновлено: 05.07.2024

Внешние и внутренние команды
Цель работы: Знакомство с возможностями интерпретатора командной строки и командами MS Windows .

Ознакомиться с теоретическим материалом.
Выполнить задания.
Ответить на контрольные вопросы.

Запустить интерпретатор командной строки

Увеличить размер окна интерпретатора и задать цвет фона и цвет шрифта (рекомендуется синий фон и белый шрифт).
Создать список фамилий студентов группы. Отсортировать список в алфавитном порядке и сохранить его в новом файле.
Создать текстовый файл, содержащий справочные сведения по командам DIR, COPY и XCOPY.
Вывести содержимое указанного в таблице 1.1 каталога по указанному формату на экран и в файл.
Скопировать все имеющиеся в каталоге Windows растровые графические файлы в каталог WinGrafika на диске С:. Если диск С: недоступен, использовать любой другой доступный диск.
Скопировать все имеющиеся в каталоге Windows исполняемые файлы в каталог WinEx на диске С:. Если диск С: недоступен, использовать любой другой доступный диск.

Таблица 1.1

Имя каталога	Что выводить	Сортировать по	Атрибуты файлов и каталогов
%Windows%	Файлы и подкаталоги	По дате	Скрытый

После этого запуститься программа cmd, в окне консоли которой можно начать писать команды (Рисунок 1 .2).

Рисунок 1.1 – Запуск интерпретатора командной строки CMD

Рисунок 1.2 – Вид интерпретатора командной строки CMD

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

Увеличим размер окна, задав ширину 100 и высоту 50 (Рисунок 1 .3).

Для изменения используемых цветов в CMD необходимо перейти на вкладку «Цвета». Так как удобнее использовать стандартную цветовую схему (серый текст на черном фоне), то в данные параметры не будем вносить никаких изменений (Рисунок 1 .4).

Рисунок 1.3 – Свойства интерпретатора командной строки CMD

Создать список фамилий студентов группы. Отсортировать список в алфавитном порядке и сохранить его в новом файле.

Рисунок 1.5 – Запись списка фамилий в файл
Полученный файл my.txt, содержит список введенных фамилий (Рисунок 1 .6).

Для сортировки списка фамилий воспользуемся командой SORT, вывод которой направим в новый файл «mysort.txt» (Рисунок 1 .7):

Sort C:\Users\korshevia\desktop\opsys\my.txt> C:\Users\korshevia\desktop\opsys\sortmy.txt

Рисунок 1.6 – Полученный список фамилий

Рисунок 1.7 – Сортировка списка фамилий
Полученный файл mysort.txt содержит список введенных фамилий, отсортированный в алфавитном порядке (Рисунок 1 .8).

Рисунок 1.8 – Содержимое файла mysort.txt

Создать текстовый файл, содержащий справочные сведения по командам DIR, COPY и XCOPY.

(DIR /? % COPY /? % XCOPY /?) > help.txt

Рисунок 1.9 – Запись справочных сведений в файл
Полученный файл help.txt содержит справочные сведения по командам DIR, COPY, XCOPY (Рисунок 1 .10).

Рисунок 1.10, Лист 1 – Справочные сведения по командам DIR, COPY и XCOPY

Вывести содержимое указанного в таблице 1.1 каталога по указанному формату на экран и в файл.

Для вывода информации о содержимом каталога воспользуемся командой: DIR C:\WINDOWS/O:D/A:H

При этом первым параметром служит переменная среды «windir», которая содержит путь к каталогу в котором находится ОС Windows. В качестве второго параметра укажем /A:H (отображение файлов с атрибутом скрытый). В качестве третьего параметра укажем /O:D (сортировка полученного списка по дате). В результате выполнения командного файла на консоль и в файл будет выведена информация о системных файлах в каталоге, где установлена ОС (рисунок 1.11).

Рисунок 1.11 – Результат выполнение командного файла

Скопировать все имеющиеся в каталоге Windows растровые графические файлы в каталог WinGrafika на диске С:. Если диск С: недоступен, использовать любой другой доступный диск.

COPY C:\WINDOWS\*.jpg C:\WinGrafika

Скопировать все имеющиеся в каталоге Windows исполняемые файлы в каталог WinEx на диске С:. Если диск С: недоступен, использовать любой другой доступный диск.

XCOPY C:\Windows\*.exe C:\WinEx\ /H

Рисунок 1.14 – Выполнение копирования исполняемых файлов
После выполнения копирования каталог WinEx будет содержать все исполняемые файлы из каталога Windows (рисунок 1.15).

Рисунок 1.15 – Содержимое каталога WinEx

Получение информации о конкретной команде.

Групповые символы (шаблоны) и их использование.

Условная обработка команд в Windows осуществляется с помощью символов && и || следующим образом. Двойной амперсанд && запускает команду, стоящую за ним в командной строке, только в том случае, если команда, стоящая перед амперсандами была выполнена успешно.

Два символа || осуществляют в командной строке обратное действие, т.е. запускают команду, стоящую за этими символами, только в том случае, если команда, идущая перед ними, не была успешно выполнена.

Условная обработка действует только на ближайшую команду.

Перенаправление ввода/вывода и конвейеризация команд.

Если при этом заданный для вывода файл уже существовал, то он перезаписывается, если не существовал — создается. Можно также не создавать файл заново, а дописывать информацию, выводимую командой, в конец существующего файла. Для этого команда перенаправления вывода должна быть задана так: команда >> имя_файла.

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

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

Главными требованиями к алгоритмам сортировки являются экономное использование памяти и быстродействие выполнения. Быстродействие сортировки определяется количеством сравнений и количеством обменов (перестановок элементов), произведенных в процессе работы. Как правило, эффективность алгоритмов сортировки оценивается степенью роста количества операций сравнения.

Относительно небольшие объемы данных могут целиком помещаться в оперативной памяти. При этом имеется произвольный доступ к сортируемым элементам. В этом случае сортировка называется внутренней. Если объем данных велик и оперативной памяти нс хватает, то информацию размещают на внешних запоминающих устройствах. В этом случае доступ к элементам данных осуществляется последовательно (см. параграф 12.2), а сортировку называют внешней. Такую сортировку применяют и в тех случаях, когда данные изначально хранятся на внешних носителях, например, для файлов баз данных. Очевидно, что внутренняя сортировка для одинаковых данных будет выполняться быстрее, чем внешняя, так как в последнем случае основное время выполнения алгоритма будет затрачено на последовательный доступ к элементам.

Рассмотрим виды сортировок, применяемые к различным данным: числовым, строковым (текстовым), записям в файлах.

Сортировка числовых данных. Пусть даны числа а, «2. а_п (представленные, например, в виде массива). В зависимости от того, имеются ли среди них равные элементы, сортировка может быть выполнена:

Все приведенные ниже примеры выполняют сортировку строк в текстовом файле (длина строк в пределах от нуля до заданного максимального значения). Отсортированный файл записывается на место исходного. Файлы сложнее массивов и для работы с ними будет использован специальный класс CFile, в котором реализованы операции обмена с диском и необходимые операции сравнения. Важно отметить, что в алгоритмах распределения/слияния сравниваются только текущие записи из разных файлов и текущая запись файла с предыдущей записью этого же файла. Эти сравнения помещены в методы Comp и Skip:

struct CFile . void Init (char @name); // Инициализация void Open (); // Откpытие для чтения void Create(); // Откpытие для записи (создание) int EOF (); // Пpовеpка достижения конца файла (0-нет) int Comp (CFile @F); // Сpавнение с дpугим файлом void Write (CFile @F); // Запись стpоки int Skip (); // Чтение следующей стpоки (0-не конец сеpии) void Close (); // Закpытие end

После проверки EOF доступна одна строка файла. Она может сравниваться со строкой другого файла (с помощью Comp) и записываться в выходной файл (с помощью Write). Skip читает следующую строку и сравнивает ее с предыдущей. Если вновь прочитанная строка должна помещаться в выходной файл после ранее прочитанной (она "больше" предыдущей) - возвращается ноль, если нет (или если достигнут конец файла) - не ноль.

При рассмотрения алгоритммов сортировки детали реализации класса CFile не играют никакой роли, будут использованы лишь перечисленные восемь методов. Полная реализация класса приведена ниже. Поскольку используются классы, необходим компилятор версии 1.2. В принципе возможна реализация того же самого без использования классов. В этом случае CFile - обычная структура, все его методы - обычные функции, но с дополнительным параметром - ссылкой на файл:

struct CFile . end void Init(CFile @File; char @name) . end . Соответственно, вместо Data.Init(@name) нужно писать Init(@Data,@name). В данном конкретном случае оба способа примерно эквивалентны, но выбран вариант с использованием классов.

Во всех приведенных ниже примерах широко используются ссылки на экземпляры классов. Возможно, это не очень хорошо, но пока так.

"Очевидная" реализация функции распределения/слияния сходна с dSort:

После первого прохода в файле образуются упорядоченные цепочки длиной не менее двух, после второго - длиной не менее четырех и так далее, пока файл не будет состоять из одной упорядоченной цепочки. Таким образом, число проходов не превысит [Log2(N)+1], время одного прохода примерно пропорционально N, общее время

За счет увеличения числа временных файлов можно сократить число проходов:

Время одного прохода при этом увеличивается, т.к. требуется больше сравнений, но число проходов уменьшается. После первого прохода образуются упорядоченные цепочки длиной не менее nFile, после второго - nFile*nFile и так далее. Таким образом nFile - новое основание логарифма в формуле расчета числа проходов.

Наконец, можно объединить циклы распределения/слияния:

Существуют и еще лучшие алгоритмы, например алгоритм многофазной сортировки (R.L. Gilstad, 1960), основанный на несимметричном распределении записей исходного файла по лентам. Этот алгоритм не столь очевиден, как предыдущие, вот его упрощенная версия (используются два временных файла):

Здесь один раз выполняется распределение серий из исходного файла (в пропорции двух соседних чисел Фибоначчи), затем выполняется многократное слияние. Само название алгоритма "многофазная сортировка" можно понимать как много фаз слияния, хотя абсолютной уверенности в правильности этого нет.

Если число упрорядоченных серий в исходном файле не равно числу Фибоначчи, временные файлы дополняются пустыми сериями. Также учтено, что при распределении две несмежные серии могут слиться в одну (пример: 10,20;15,30;25,35;). Вот как выполняется сортировка файла, содержащего 22 серии:

22x1	v	v
v	7x0+14x1	5x0+8x1
5x0+2x1+6x2	8x1	v
5x2	v	5x1+2x2+1x3
v	5x3	2x2+1x3
2x5+1x6	2x3	v
1x6	v	2x8
v	1x14	1x8
1x22	-	-

Циклов выполняется на два больше, чем при слиянии на двух парах лент (xSort), но эти циклы более короткие.

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

добрый день.
есть бинарный файл, записываем в него массив структур (структура:поле1, поле2, поле3).

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

вот как можно это легче всего сделать.
спасибо

Иллюстрация того, что для внешней сортировки неэффективны методы внутренней?

Добавлено 25.06.11, 11:16
Длина структуры фиксирована?
Открывать файл для чтения/модификации в бинарном режиме.
Перед чтением структуры делать seek на ее начало. Можно читать несколько подряд.
Перед записью тоже делать seek на начало. Тоже можно писать несколько подряд.
Позиция структуры в файле скорее всего = (номер_структуры - 1)*длина_структуры.
Номер структуры считается с 1.

если я буду перед чтением 2 структур seek ставить на начало, то каждый раз будут считываться первые две структуры же? Перед чтением структуры делать seek на ее начало.

ой, сори.
спасибо, вроде по логике, всё должно работать, посмотрим.

А использовать mmap не судьба? Тогда вообще ничего читать/писать не надо =)

После seek данные считываются или пишутся последовательно - указатель сдвигается на соответствующее расстояние.
Обязательно надо делать seek после чтения перед записью или после записи перед чтением. Иначе не гарантируется правильность операций - часть данных может быть утеряна или записана не туда или прочитаны не те данные. Фактически, чтобы такого не происходило, приходится делать seek перед каждой серией чтений или записей.

Добавлено 25.06.11, 12:58
Это не только к C/C++ относится. Часто этого требуют системные вызовы.

если всё правильно понял, то для одного прохода так:

но оно пишет не в позицию (i-1)*sizeof(data2), а в конец файла, почему?

т.е. был файл, и там такая структура:
abc 21 cancer
abcd 17 leo
abcde 13 taurus
abcdef 25 capricorn
abcdefg 10 scorpio

после прохода:
abc 21 cancer
abcd 17 leo
abcde 13 taurus
abcdef 25 capricorn
abcdefg 10 scorpio
abcd 17 leo
abc 21 cancer
abcde 13 taurus
abcd 17 leo
abcdefg 10 scorpio
abcdef 25 capricorn

Что такое data?
Просто на всякий случай, чтобы проверить (к задаче не относится).

f2 и f3 что такое? Как они созданы, или как открыты?
Очень важно. Для некоторых вариантов позиционирование работает не совсем так, как хочется. Не говоря уже о том, что не все типы потоков подходят для задачи.
За что не люблю потоки C++ - слишком они абстрагированы от собственно файлов. По мне так куда полезнее было бы иметь еще и более низкоуровневое средство для работы с файлами.

Что ты надеешься прочитать при i=5?
Учитывая, что там до конца осталась только одна запись

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

С чего ты взял, что запись производится в конец потока?
Я там вижу, что местами там вообще ничего не писалось.

Что такое data?
Просто на всякий случай, чтобы проверить (к задаче не относится).

Что ты надеешься прочитать при i=5?
Учитывая, что там до конца осталась только одна запись

С чего ты взял, что запись производится в конец потока?
Я там вижу, что местами там вообще ничего не писалось.

Читайте также: