1. РЕКУРСИВНАЯ ОБРАБОТКА КАТАЛОГОВ

1.1. Функции для управление файлами и каталогами

Каталог – это файл, в котором хранится информация о содержимом данного каталога: файлы и другие каталоги, называемые подкаталогами. На каждом диске имеется один корневой (главный) каталог. В каждый момент времени какой-либо каталог является текущим. Текущим будет последний каталог в полном пути к файлу или каталогу. К элементам текущего каталога можно обращаться по имени без указания полного пути к элементу.

Любой каталог, кроме корневого, содержит элементы “.” и “..”, которые определяют сам текущий каталог и родительский каталог текущего каталога (каталог, в который вложен текущий каталог).

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

Прототипы всех функций для работы с каталогами и файлами, описания структур данных нужных для работы этих функций, а также определения необходимых констант находятся в файлах и . Ниже приводится список основных функций для работы с файлами и каталогами.

int findfirst(char *name, struct ffblk *ffblk, int attrib);

int findnext(struct ffblk *ffblk);

Первый аргумент name функции findfirst() определяет маску, которой должно удовлетворять имя искомого файла. Маска может содержать шаблоны. При формировании маски выбора файлов могут использоваться следующие символы:

• 
  * означает, что на месте этого символа может стоять сколько угодно (в том числе ноль) разрешенных символов имени или расширения файла;
  
• 
  ? означает, что на месте этого символа может стоять один из разрешенных символов.
  

• 
  “*.*” – выбирает все файлы из каталога (файлы с любым именем и любым расширением, в том числе и файлы без расширения);
  
• 
  “lab*.*” – выбирает все файлы с именами, начинающимися на «lab» и любым расширением: lab1.pas, lab123.exe, lab3 и т.д.;
  
• 
  “test?.txt” – выбирает файлы с расширением txt и именем, начинающемся с test плюс еще один символ: test1.txt, testа.txt и т. д.
  

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

struct ffblk {

char ff_reserved[21]; // зарезервировано для MS DOS

char ff_attrib; // байт атрибутов найденного файла

int ff_ftime; // время создания/модификации файла

int ff_fdate; // дата создания/модификации файла

long ff_fsize; // размер файла

char ff_name[13]; // имя найденного файла

};

Параметр attrib – это используемый в MS DOS байт атрибута файла, который употребляется при выборе подходящих для поиска файлов. Параметр attrib может быть комбинацией одной из следующих определенных в файле констант:

#define FA_RDONLY 0x01 // атрибут "только чтение"

#define FA_HIDDEN 0x02 // скрытый файл

#define FA_SYSTEM 0x04 // системный файл

#define FA_LABEL 0x08 // метка тома

#define FA_DIREC 0x10 // каталог

#define FA_ARCH 0x20 // архивный файл

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

Обе функции возвращают нулевое значение, если поиск файла закончился успешно.

Задача. В корне диска D: создать каталог (папку) TMP с пятью пустыми файлами TMPx.000, после чего вернуться в прежний каталог.

#include

#include

#include

// возврат в прежний каталог

void myDir(int d, char *p) {

setdisk(d);

chdir(p);

bioskey(0);

}

void main(void) {

int d;

d = getdisk(); // сохраняем текущий диск

getcurdir(0, path); // сохраняем текущий каталог

if(setdisk(3) == -1) { // переход на диск D:

puts("Ошибка перехода на диск D: !!!\n");

bioskey(0);

return;

}

if(chdir("TMP")==0) { // переход в каталог TMP

chdir(".."); // возврат в корень диска D:

myDir(d,path); // возврат в прежний каталог

return;

if(mkdir("TMP")==-1) { // создание каталога

puts("Ошибка создания каталога TMP !!!\n");

myDir(d,path); // возврат в прежний каталог

return;

}

chdir("TMP"); // переход в созданный каталог TMP

fname[3] = x++;

if((ff = fopen(fname, "w")) == NULL)

puts("Ошибка создания файла %s !!!\n", fname);

else

fclose(ff);

chdir(".."); // возврат в корень диска D:

puts("Каталог TMP с пятью файлами создан успешно !!!\n");

myDir(d,path); // возврат в прежний каталог

}

Задача. Вывести на экран все cpp-файлы из текущего каталога.

#include

#include

void main(){

struct ffblk qq;

int a;

a = findfirst("*.cpp", &qq, 0); //поиск первого файла

while(!a) {

printf(" %s\n", qq.ff_name);

a = findnext(&qq); //поиск следующего файла

}

}

1.2. Определение времени и даты создания файла

ff_ftime ║15.....11║10........5║4.......0║

╠═╤═╤═╤═╤═╬═╤═╤═╤═╤═╤═╬═╤═╤═╤═╤═╣

╚═╧═╧═╧═╧═╩═╧═╧═╧═╧═╧═╩═╧═╧═╧═╧═╝

Часы Минуты Секунды/2

ff_fdate ║15..........9║8.....5║4.......0║

╠═╤═╤═╤═╤═╤═╤═╬═╤═╤═╤═╬═╤═╤═╤═╤═╣

╚═╧═╧═╧═╧═╧═╧═╩═╧═╧═╧═╩═╧═╧═╧═╧═╝

Год после 1980 Месяц День

Можно напрямую выделять поля времени и даты из этих переменных, а можно использовать для этих целей структуру ftime. Структура ftime, описанная в , используется для доступа к полям времени и даты, соответствующим этим форматам:

struct ftime {

unsigned ft_tsec : 5; // секунды/2

unsigned ft_min : 6; // минуты

unsigned ft_hour : 5; // часы

unsigned ft_day : 5; // день

unsigned ft_month : 4; // месяц

unsigned ft_year : 7; // год после 1980

};

ft_hour ft_min ft_tsec

╠═╤═╤═╤═╤═╬═╤═╤═╤═╤═╤═╬═╤═╤═╤═╤═╣

╚═╧═╧═╧═╧═╩═╧═╧═╧═╧═╧═╩═╧═╧═╧═╧═╝

Часы Минуты Секунды/2

ft_year ft_month ft_day

31.........25 24...21 20.....16

╠═╤═╤═╤═╤═╤═╤═╬═╤═╤═╤═╬═╤═╤═╤═╤═╣

╚═╧═╧═╧═╧═╧═╧═╩═╧═╧═╧═╩═╧═╧═╧═╧═╝

Год после 1980 Месяц День

В примере продемонстрированы оба способа определения даты и времени создания/модификации файла:

#include

#include

void main() {

struct ffblk ss;

findfirst("in",&ss,0);

// использование структуры ftime

int h1, m1, s1, d1, mo1, y1;

struct ftime *tt;

tt= (struct ftime *)&ss.ff_ftime;

s1 = tt->ft_tsec * 2;

m1 = tt->ft_min;

h1 = tt->ft_hour;

d1 = tt->ft_day;

mo1 = tt->ft_month;

y1 = tt->ft_year + 1980;

// прямой доступ

int h2, m2, s2, d2, mo2, y2;

s2 = (ss.ff_ftime & 0x001F) * 2;

m2 = (ss.ff_ftime>>5) & 0x003F;

h2 = (ss.ff_ftime>>11) & 0x001F;

d2 = ss.ff_fdate & 0x001F;

mo2 = (ss.ff_fdate>>5) & 0x000F;

y2 = ((ss.ff_fdate>>9) & 0x007F) + 1980;

}

1.3. Понятие рекурсивной функции

Простым примером рекурсивной функции является функция для вычисления факториала целого неотрицательного числа.

// рекурсивная функция

int fact_r(int n) {

int ans;

if(n==0) return 1;

ans = fact_r(n-1) * n; // рекурсивный вызов

return ans;

}

// нерекурсивная функция

int i, ans;

ans = 1;

for(i=1; i<=n; i++)

ans *= i;

return ans;

}

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

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

В BC стек вызовов можно просматривать при работе отладчика через пункт меню: Debug→Call Stack (комбинация клавиш Ctrl+F3).

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

Главным преимуществом рекурсивных функций является то, что с их помощью упрощается реализация алгоритмов, а программа становится понятнее.

1.4. Примеры рекурсивной обработки каталогов

#include

#include

#include

#include

#include

#include

// печать файлов

void PrintFile() {

struct ffblk f;

int p;

for(p=findfirst("*.*",&f,0xff); !p; p=findnext(&f))

printf(" %s\n",f.ff_name);

}

// печать каталогов

char pp[256]; //каталог

int p;

struct ffblk dir;

printf("%s\n",pp);

PrintFile();

int i = FA_DIREC;

for(p=findfirst("*.*",&dir,i); !p; p=findnext(&dir))

if(strcmp(dir.ff_name,".")!=0 &&

strcmp(dir.ff_name,"..")!=0 &&

dir.ff_attrib=='\x10') {

chdir(dir.ff_name); // заходим в каталог

PrintDir();

chdir(".."); // возвращаемся в родительский каталог

}

}

char path_beg[256]; // начальный каталог

char path_end[256]; // конечный каталог

clrscr();

getcurdir(0, path_beg);

PrintDir();

getcurdir(0, path_end);

if (strcmp(path_beg, path_end))

printf("Ошибка: не вернулись в начальный каталог!\n");

puts("Все каталоги и файлы напечатаны!");

bioskey(0);

}

Пример №2. Начиная с текущего каталога, удалить все файлы с расширением .bak.

#include

#include

#include

#include

#include

#include

// удаление файлов с расширением .bak

void UnlinkBak(void) {

struct ffblk ff;

int x;

if (!(ff.ff_attrib & FA_DIREC))

unlink(ff.ff_name);

}

// переход в другой каталог

struct ffblk ff;

int x;

UnlinkBak();

if(strcmp(ff.ff_name,".")!=0 &&

strcmp(ff.ff_name,"..")!=0 &&

ff.ff_attrib=='\x10') {

chdir(ff.ff_name); // заходим в каталог

NextDir();

chdir(".."); // возвращаемся в родительский каталог

}

}

char path_beg[256]; // начальный каталог

char path_end[256]; // конечный каталог

clrscr();

getcurdir(0, path_beg);

NextDir();

getcurdir(0, path_end);

if (strcmp(path_beg, path_end))

printf("Ошибка: не вернулись в начальный каталог!\n");

puts("Все файлы с расширением .bak удалены!");

bioskey(0);

}

2. РАБОТА С БИТАМИ

2.1. Основные понятия

просмотр в watch: c,x => 0x61 => 01100001

Десятичное число	Двоичное число	16-ричное число
010	02	016
110	12	116
210	102	216
310	112	316
410	1002	416
510	1012	516
610	1102	616
710	1112	716
810	10002	816
910	10012	916
1010	10102	A16
1110	10112	B16
1210	11002	C16
1310	11012	D16
1410	11102	E16
1510	11112	F16
1610	100002	1016

1. 
   Каждая цифра 16-ричной системы записывается четырехзначным двоичным числом;
   
2. 
   Нули, стоящие слева можно отбросить.
   

1. 
   Каждые четыре двоичные цифры, считая справа налево, записываются одной 16-ричной цифрой, которые выписываются также справа налево;
   
2. 
   Если для последней четверки не хватает цифр, слева от двоичного числа дописываются нули.
   

58₁₆ = 0101 1000₂ (1 байт)

B2₁₆ = 1001 0010₂

1101₂ = D₁₆

101010₂ = 2A₁₆

1111 1001₂ = F9₁₆ (1 байт)

Надо быстро уметь переводить из двоичной системы в десятичную:

1010₂ = 1*2³ + 0*2² + 1*2¹ + 0*2⁰ = 8 + 2 = 10₁₀

И наоборот (или остатки от деления числа на 2 выписывать справа налево):

25₁₀ = 16 + 8 + 1 = 1*2⁴ + 1*2³ + 0*2² + 0*2¹ + 1*2⁰ = 11001₂

Какое число можно закодировать в 1 байте => 2⁸ = 256 (беззнаковое).

Для отрицательного числа старший бит равен 1, в одном байте можно хранить число от -128 (0x80) до 127 (0x7F).

2.2. Основные операции для работы с битами

2.2.1. Поразрядные логические операции

При выполнении данных операций не имеет смысла смотреть на десятичное представление чисел.

int i=0x45FF, // i= 0100 0101 1111 1111

j=0x00FF; // j= 0000 0000 1111 1111

int k;

k=i^j; // k=0x4500 = 0100 0101 0000 0000

k=i&j // k=0x00FF = 0000 0000 1111 1111

k=~i; // k=0xBA00 = 1011 1010 0000 0000

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

int x = 11; // x & 1 ≡ x & 0x1 ≡ x & 0x0001

…0000 1011

& …0000 0001

----------

…0000 0001

Вывод: x&1, если =1, то число нечетное

int x = 12;

…0000 1100

& …0000 0001

----------

…0000 0000

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

Проверка на четность: последний бит равен 1 для нечетного числа, поэтому (с&1==1) (маска 00000001).

Проверка первого и последнего бита: с&0x81 (маска 10000001).

Пример: с=0xAF (10101111) => if (c&0x81==0x81) {нужные биты = 1 }

2.2.2. Операции сдвига: >> и <<

При сдвиге влево << правые освобождающиеся биты устанавливаются в нуль. При сдвиге вправо >> метод заполнения освобождающихся левых битов зависит от типа первого операнда. Если тип unsigned, то свободные левые биты устанавливаются в нуль. В противном случае они заполняются копией знакового бита (это так называемое размножение знака).

Число двоичных разрядов для сдвига может быть задано только константой или константным выражением, т.е. выражением, целиком состоящим из констант. Нельзя написать: int x, y=2; x = x>>y;

Результат операции сдвига не определен, если второй операнд отрицательный.

Операции сдвига – это наиболее быстрые способы умножения и деления на 2, 4, 8 и т. д. (т.е. на степень двойки).

Сдвиг влево << соответствует умножению первого операнда на степень числа 2, равную второму операнду, а сдвиг вправо >> соответствует делению первого операнда на 2 в степени, равной второму операнду.

unsigned char i=6, k; // i = 0000 0110

k = i<<1; // k = 0000 1100 = 12 = 6 * 2¹

k = i<<2; // k = 0001 1000 = 24 = 6 * 2²

k = i>>1; // k = 0000 0011 = 3 = 6 / 2¹

char j=-4, n; // j = 1111 1100

n = j<<1; // n = 1111 1000 = -8 = -4 * 2¹

n = j>>2; // n = 1111 1111 = -1 = -4 / 2²

unsigned char a=252; // a = 1111 1100

k = j>>2; // k = 0011 1111 = 63 = 252 / 2²

2.3. Примеры работы с битами

// Основные операции

unsigned char a, b, c;

int n;

с = a&b; // побитовое И, применяется к каждой паре бит

// a=01010111

// b=11001001

// c=01000001

с = a|b; // побитовое ИЛИ, применяется к каждой паре бит

// a=11000011

// b=01100111

// c=11100111

с = a^b; // побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ, применяется к каждой паре бит

// a=10101011

// b=11001100

// c=01100111

b = a>>n; // побитовый СДВИГ ВПРАВО на n разрядов, старшие разряды

// после сдвига устанавливаются в 0

// a=11001101

// n=3

// b=00011001