Разбор лабораторных по программированию: Продолжение...

Изменено: . Разместил: FadeDemon | Меню
Количество просмотров4`226 / FD1715-6-0

Ну вот. Прошло две недели, а все лабораторные уже защищены. Думаю, пришло самое время продолжить недавно начатый нами разбор оных. В прошлый раз мы остановились на 7-й лабе, поэтому сегодня будем рассматривать лабы с 7-й по 12-ю включительно. Полные исходники ко всем заданиям, как и в прошлый раз, доступны в конце статьи. Итак, начнём.


Лабораторная №7. Массивы как параметры функций


Мда… Учитывая что это уже 7-я по счёту лаба, могли бы придумать и чего-нибудь поинтереснее. Идейной сложности здесь абсолютный ноль. Важно усвоить только одну вещь: массив в Си, это всегда указатель на область памяти, в которой размещены сами элементы, и ничего более. Память для элементов может быть как выделена в стеке (при описании в программе переменной-массива фиксированной длины), так и любым другим динамическим образом, к примеру через malloc(). Из этого утверждения надо усвоить ещё один факт: функция, принимающая массив в качестве параметра не имеет понятия о его длине, и поэтому, длину массива надо передавать в функцию, к примеру, вторым параметром.


Это было вроде-как вступление, теперь смотрим задание:

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


Отбросим рассуждения, просто берём и делаем… Заметим только, что как бы вы массив не объявляли, он всегда будет подразумевать собой указатель, например:


Код: C++
void print(char *);
void print(char []);
void print(char [10]);

Все эти записи равнозначны, и какой из них пользоваться абсолютно не важно, это вопрос скорее религии, чем программирования на Си… Я, например, всегда пользуюсь первым вариантом — мне так удобнее… В общем, что такое сортировка пузырьком мы все знаем, поэтому просто возьмём и сделаем то что от нас хотят:


Код: C++
//обыкновенная заезженная перестановка
void inline swap(long *a, long *b){
    long c = *a;
    *a = *b;
    *b = c;
}

//обыкновенная заезженная сортировка
void array_sort(long *a, long s){
    long i, j;
    for(j = 0; j < s; j++){
        for(i = j + 1; i < s; i++){
            if(a[i] > a[j]){
                swap(a + i, a + j);
            }
        }
    }
}

Это функция, которая будет сортировать. Чтобы она начала сортировать, её надо вызвать:


Код: C++
void task_1(){
    long a1[20];
    long a2[10];
    long i;
    
    //заделываем массив первый
    cout << "\nOriginal array #1:\n";
    for(i = 0; i < 20; i++){
        a1[i] = rand() % 101;
        cout << a1[i] << ", ";
    }
    cout << "\n\n";

    //заделываем массив первый    
    cout << "Original array #2:\n";
    for(i = 0; i < 10; i++){
        a2[i] = rand() % 101;
        cout << a2[i] << ", ";
    }
    cout << "\n\n";
    
    //сротируем (вызываем функцию)
    array_sort(a1, 20);
    array_sort(a2, 10);
    // ...
}

Кстати, чтобы никто не испугался, надо напомнить, что ключевое словечко inline в объявлении функции значит только то, что компилятор имеет право код функции запихивать прямо в места её вызова, в целях оптимизации, для экономии времени на call и ret командах, и на логику работы программы это влияет чуть менее, чем никак. Посему, применение этого слова в коде функций чуть повыше, есть ни что иное, как в чистом виде пафос. Ну а в коде вызова всё понятно: запиливаем массивы, мусорим в них, и … (обратить внимание надо только на размеры массивов).


2. Написать функцию, которая вычисляет для двумерного массива с переменной длинной строк сумму элементов  каждой строки. Длинна каждой строки хранится в 0 элементе соответствующей строки. Массив сформировать с помощью случайных чисел, и вывести на экран в главной программе.

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


Код: C++
//для статических
void print(long matrix[][10]);

//для динамических
void print(long **matrix);

Ну, очевидно, что первый способ применяется к блочным статическим массивам, а второй — для динамических массивов, представляющих собой те самые указатели на указатели на указатели данные. В первом, кстати, случае, необходимо указывать в обязательном порядке размеры всех измерений кроме самого верхнего, ибо они определяют размер элемента самого первого по вложенности массива, который, как нам известно, изменяться с точки зрения Си не может.


Мы воспользуемся, как не трудно догадаться, вторым вариантом, ибо наш массив — вполне себе динамический. И снова напишем то, что от нас просят:


Код: C++
//длину будем сохранять в первом элементе, сумму во втором
//массив тут проще сделать динамическим (переменная длинна строки, какбэ)
void array_2x_calc(long **a, long h){
    long i, j;
    for(j = 0; j < h; j++){
        a[j][1] = 0;
        //смотрим на длину в нулевом элементе
        for(i = 0; i < a[j][0]; i++){
            a[j][1] += a[j][i + 2];
        }
    }
}

Рассматривая этот код, просто помним, что в нулевом элементе храниться длина строки, а в первом — её сумма, которая должна быть посчитана. Переменная h задаёт количество строк. Всё остальное здесь весьма тривиальное, и может быть найдено вами в исходниках в конце статьи. Покажем лучше, как оно работает, да пойдем дальше:


Иллюстрация 2-го задания (лаба 7)
Рис. №873. Иллюстрация 2-го задания (лаба 7)

Лабораторная №8. Структуры


Ну вот, пошли более интересные вещи. Что такое структура, я думаю осознать не сложно, грубо говоря это такая переменная тип данных, у которого может быть много разных полей. Поле структуры может быть тоже структурой, то-есть, структуры могут быть вложенными. При объявлении структур, всегда советую объявлять их как отдельные типы, в typedef. Ну, тот факт, что размер структуры есть сумма размеров всех её полей, я думаю, отметит за меня Капитан Очевидность, но его, кстати, не лишним будет поправить, и сделать оговорку, что верно это только если не брать в расчёт выравнивание. Выравнивание, это такая прихоть компилятора, предназначенная исключительно for optimisation purposes, заключающаяся в том, что длину поля структуры он делает не меньше какого-то числа (напр 4, 8 или 16) байтов, дополняя его в случае необходимости пустыми, неиспользуемыми байтами с правой стороны. То-есть, если выравнивание равно 8 байтам, а тип поля long, то под поле таки выделится 8 байт, но использоваться из них будут только 4 первых. На фига это нужно? Казалось бы, это мало того что всё усложняет, так ещё и жрёт лишние байты, но на самом деле, если вникнуть…


Всё дело в том, что у наших процессоров есть такая полу-призрачная особенность, которая позволяет им работать с адресами чуть-чуть быстрее, если они кратны некоторым числам (как раз таки 4, 8 или 16), то-есть, их некоторые младшие биты все обнулены. Поэтому, если поля структуры будут иметь некоторое выравнивание, и память под них будет выделяться так-же по выровненным адресам, а погода на планете Марс будет достаточно благоприятной, есть некоторая вероятность, что программа ваша и вправду будет работать чуточку быстрее. Незначительно. На несколько микро- или даже наносекунд, но будет. Невольно задумываешься, вот до чего дело заходит в оптимизации… Но! Уверяю вас, всё это только лирика. Люто, бешено нуждаться в выравнивании на 16 мы начинаем в тот момент, когда речь заходит про SSE, даже самым краем уха. Суть в том, что подавляющее большинство SSE команд благоразумно рассчитаны на работу исключительно с адресами кратными 16, и любые другие адреса они воспринимают как неполноценные, брезгливо реагируя на них ошибкой общей защиты (13-ым прерыванием), а сделано это потому, что по выровненным адресам значительно (почти в 2 раза) быстрее добывать 16-ти байтные блоки из DRAM-памяти, из-за особенностей её устройства, кратные адреса какбэ совпадают с адресами ячеек, из которых можно всё считать одним махом. То-есть, грубо говоря, по выровненному адресу 16 байт из памяти можно слизать за 1 такт, а по невыровненному — только за 2, и на производительность в критичных местах программы, использующих SSE, сей факт оказывает ну очень значительное влияние. С записью в память, конечно-же то-же самое, и из-за всех этих сложностей, SSE без выравнивания — уже не SSE, а если ещё и погода на Марсе ухудшиться, то он может оказаться в такой ситуации вполне себе медленнее, чем даже FPU. Такие вот дела.


Так-с… Что-то от темы мы куда-то отклонились. Перейдём сразу к заданиям и примерам. Задание первое:


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

Брр… Сколько тут всего интересного… Давайте по-порядку. Сначала сочиним нашу структуру, и сразу-же её и запишем:


Код: C++
typedef struct TSchool {
    long number;
    long leavers;
    long abiturients;
};

Вроде всё понятно. 3 поля, у всех тип long. Массив из них сделать так-же просто, вспомнив что тип нашей структуры — TSchool, получиться что-то вроде TSchool m[N], где m — сам объявляемый массив, а N — количество, собственно говоря, элементов, то-есть структур. Это в простейшем случае статического массива. Ну, чтобы объявить указатель на нашу структуру, как обычно справа надо дорисовать звёздочку (*). Короче, всё как обычно. А вот что такое индексная сортировка?…


На самом деле всё элементарно. При обычной сортировке мы меняем местами сами элементы, а при индексной — только их индексы во вспомогательном массиве. Алгоритм сортировки может быть любой, в нашем случае это сортировка пузырьком. Если всё это осмыслить, то делается это так:

1. Создаём массив из целых чисел, по размеру равный тому массиву, который надо отсортировать.
2. Заполняем его числами от нуля до N − 1, где N — количество элементов.
3. Сортируем наш массив индексов, сравнивая нужные элементы структур, которые лежат по индексам нашего массива в исходном массиве. А исходный массив не трогаем :)
4. Применяем изменения, сделанные в индексном массиве к исходному массиву, то-есть переносим все элементы на их новые индексы, лежащие в индексном массиве. Для этого, кстати, придется создать копию массива — по другому процедура весьма мозгоёбиста.

Чтобы голословным не быть, сразу и приведём нашу желаемую функцию, реализующую индексную сортировочку по полю нашей структуры abiturients, и берущую при этом все манипуляции с индексным массивом и применении изменений на себя:


Код: C++
//индексная сориторвка школ
void index_sort(TSchool *ss, long co){
    //по традицуии - пузырьковая
    long j, i;    
    long *im = new long[co];
    
    //делаем массив индексов
    for(i = 0; i < co; i++){
        im[i] = i;
    }
    
    //собственно сортируем
    for(j = 0; j < co; j++){
        for(i = 0; i < co; i++){
            //следить за пальцами
            if(ss[im[i]].abiturients < ss[im[j]].abiturients){
                swap(im[i], im[j]);
            }
        }
    }
    //коммитим изменения на наш структуромассив
    //без второго такого же тут трудно обойтись
    TSchool *s2 = (TSchool *) malloc(co * sizeof(TSchool));
    
    for(i = 0; i < co; i++){
        memcpy(&s2[i], &ss[im[i]], sizeof(TSchool));
    }
    
    //кладем все что получилось на место первого
    memcpy(ss, s2, sizeof(TSchool)* co);
    
    free(s2);
    
    //индексы больше не нужны
    delete im;
}

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


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

На языке SQL это бы выглядело примерно так (MySQL вариант):


Код: SQL
SELECT
	COUNT(rooms) AS `rooms_count`, /* кол-во комнат */
	SUM(rooms.students) AS `students`, /* кол-во студентов */
	AVG(rooms.area / rooms.students) AS `avg_area` /* средняя площадь на студента */
FROM rooms WHERE 1
GROUP BY rooms.faculty;

Но к огромному сожалению, базы данных мы тут не трогаем, и вообще изучаем Си. А жаль… Придётся нам изобретать что-то похожее на свою мини-базу данных. Основная идея тут в том, что поле факультета надо использовать как уникальный ключ, то-есть, для каждого факультета создать структуру, в которую, собственно, накапливать данные из массива с комнатами. Имена факультетов в отдельный массив вынести не только можно, но и нужно, причем вынести надо только уникальные, чтобы потом по ним ориентироваться в статистике по факультетам. Для этого нам, конечно-же, понадобиться функция поиска в массиве. Вот кстати и она:


Код: C++
//ищем строку в массиве
long array_search(char **a, char *s, long l){
    long i;
    for(i = 0; i < l; i++){
        if(0 == strcmp(a[i], s)){
            return i;
        }
    }
    //не судьба
    return -1;
}

//засовываем массив в факультет
//полагаем, что памяти под указатель хватит всегда
long array_push(char **a, char *s, long *c){
    a[*c] = (char *) malloc(strlen(s) + 1);
    strcpy(a[*c], s);
    //размер массива растет
    return (*c)++;
}

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


Код: C++
//читаем файл построчно, и...
    while(!feof(f) && i < co){
        //если считалось чтото верное, идем дельше
        if(4 == fscanf(f, "%d %f %s %d", &ss[i].number, &ss[i].area, buf, &ss[i].humanoids)){
            
            //паралельно рисуем кое-что
            printf("|%8d|%8.2f|%8s|%8d|\n", ss[i].number, ss[i].area, buf, ss[i].humanoids);
            display_hline(8, 4);
            
            //ищем нужный факультет
            tf = array_search(fa, buf, fco);
            //если не нашли - засовываем
            if(-1 == tf){
                tf = array_push(fa, buf, &fco);
            }
            
            //проставляем ид факультета
            ss[i].id_fac = tf;
            //идем дальше
            i++;
        }
    }

Суть такова: читаем файл с таблицей комнат по строчкам, добавляем комнату (структуру THostelRoom), и ищем в нашем списке считанный факультет. Если не нашли — добавляем. Далее, у свежедобавленной комнаты проставляем идентификатор факультета, коим является индекс в массиве факультетов. После этой экзекуции, остальные проблемы берет на себя вот такой код:


Код: C++
//и теперь займемся счетоводством
    //создаем таблицу данных по факультетам
    TFaculty *ta = (TFaculty *) malloc(fco * sizeof(TFaculty));
    //чистим её
    memset(ta, 0, fco * sizeof(TFaculty));
    //берем в зубы калькулятор
    for(i = 0; i < co; i++){
        //ну и считаем
        ta[ss[i].id_fac].rooms ++;
        ta[ss[i].id_fac].humanoids += ss[i].humanoids;
        ta[ss[i].id_fac].area  += ss[i].area;
    }
    
    //в конце высчитываем среднюю площадь на человектора
    for(i = 0; i < fco; i++){
        //ну и считаем
        ta[i].area_per_humanoid = ta[i].area / (float) ta[i].humanoids;

    }

Ах да! Для полноты картины, покажем, какие структуры мы тут используем:


Код: C++
typedef struct THostelRoom {
    long number;
    long id_fac;
    float area;
    long humanoids;
};

//данные по факультету, без его имени
typedef struct TFaculty {
    long rooms;
    long humanoids;
    float area;
    float area_per_humanoid;
};

Ну, что тут происходит, по моему, очевидно. Создаем массив со структурами TFaculty, по длине совпадающий с количеством уникальных факультетов, ну а дальше наполняем его данными из массива с комнатами. Всё, осталось только вывести. Уфф… Ну, взглянем на результат нашего труда. В качестве входных данных, используется файл lab8_data2.txt, который вы можете найти в исходниках. После его обработки, программа выдаёт примерно это:


Лаба 8, часть 2
Рис. №874. Лаба 8, часть 2

Вот и всё. Сделали мы восьмую лабу. Работу с файлами, кстати, рассматривать подробнее будем в 11 и 12 лабах. А сейчас мы берем, и переходим к девятой…


Лабораторная №8. Односвязные динамические списки.


Вот динамические списки, это по настоящему весело! Это моя любимая штука, постоянно используемая в проектировании игровых движков… Что такое динамический список? Это когда у нас в памяти много-много структур с какими-то данными, в которых есть указатель, указывающий на следующую за ним структуру, то-есть, все эти разбросанные по памяти структуры формируют устойчивую цепочку с последовательным доступом. То-есть, чтобы найти в этой цепочки некоторый элемент, надо сначала просмотреть все элементы, стоящие в цепочке до него, потому что другого способа получить прямой указатель на искомую структуру — нет. Списки удобны своей гибкостью, в них легко добавить элемент в любое место, или удалить его, и их размер может сколь угодно увеличиваться по мере работы программы. “Односвязный” список именуется так, кстати, потому, что в нём есть указатель только на следующий элемент. Если бы он был двусвязный, указателей было бы два: на предыдущую структуру, и следующую, хотя плюсов у такого списка не намного больше. Ну да нам это уже не интересно: взглянем лучше на задание.


1. Сформировать односвязный список, состоящий из структур, содержащих информацию: фамилия студента и 4 оценки. При формировании списка предусмотреть, чтобы он был упорядочен по возрастанию (по фамилии). Вывести полученный список.

Итак. Структура наша, поскольку предназначена для динамического списка, обладает на первый взгляд, некоторой своеобразной рекурсивностью: содержит указатель на саму себя. Рекурсивно в структурах, кстати, можно объявлять только указатели, рекурсивных структур подобным образом создавать нельзя, нетрудно, кстати, догадаться, почему :). Смотрится это безобразие примерно так:


Код: C++
typedef struct TStudent {
    char surname[32];
    long marks[4];
    TStudent *next;
};

Чтобы попытаться ещё немного прояснить устройство динамических списков, приведём мы ещё небольшую иллюстрацию в художественном стиле (стоит напомнить, что указатель последнего элемента в списке установлен в NULL):


Примерно так выглядит динамический список...
Рис. №875. Примерно так выглядит динамический список...

Тут мы сразу видим и ещё один непременный атрибут списков — переменную, указывающую на первый элемент списка. У нас эта переменная будет глобальной, и примет вот такой вид:


Код: C++
//указатель на вершину списка
TStudent *sm = NULL;

Далее, нам надо разобрать смысл двух очень операций с динамическим списком. Вернее, трёх операций. В них входят добавление элемента в произвольное место, удаление произвольного элемента, и самое простое — обход всех элементов списка. Давайте сразу решим с обходом, ибо это самое простое. Чтобы эту операцию сделать более универсальной, что-ли, я решил вынести её в функцию, берущую всю грязную работу по обходу списка на себя, и для каждого элемента вызывающую callback, то-есть функцию обратного вызова. Дополнительная фишка, если колбэк возвращает false, обход последующих элементов прекращается (а-ля какой-нибудь EnumWindows из Windows, например). Правда фишка оная нам не пригодилась, но зато смотрится красиво. Вот, кстати, как именно это смотрится, на примере реализации функции отображения содержимого списка:


Код: C++
//тип каллбека
typedef bool TWalkCallback(TStudent *);

//обход списка с помощью каллбека
void student_walk(TWalkCallback *f){
    TStudent *t = sm, *d;
    
    while(t != NULL){
        //защита, на случай, если список кому-то захочится испортить
        d = t;
        t = t->next;
        //зовем функцию обхода
        if(!f(d)){
            //если функция вернула не тру, то прекращаем шоу
            return;
        }
    }
}

//собстно, функция обхода, которая занимается пичатоньем
bool student_print_row(TStudent *s){
    printf("|%-20s|%2d|%2d|%2d|%2d|\n", s->surname, s->marks[0], s->marks[1], s->marks[2], s->marks[3]);
    cout <<"+--------------------+--+--+--+--+\n";
    //это важно
    return true;
}

//функция, которая все запускает
void student_print(){
    cout << "+--------------------+--+--+--+--+\n";
    cout << "| Surname            |M1|M2|M3|M4|\n";
    cout << "+--------------------+--+--+--+--+\n";
    student_walk(&student_print_row);
}

Выглядит мудрёно, но на самом деле… Понятно, что колбэк, это функция, принимающая один параметр типа TStudent *, и возвращающая что-то похожее на bool. Сам алгоритм обхода упрощённо выглядит примерно так:

1. Берём временный указатель.
2. Приравниваем его к головному.
3. Вызываем для него колбэк.
4. Если его поле next не равно NULL, временный указатель приравниваем его next, и переходим к пункту 3.
5. Если же next == NULL, то обход закончен.

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


Добавляем элемент
Рис. №876. Добавляем элемент

Здесь ещё сто́ит сделать оговорку на случаи, когда добавляем мы элемент не между двумя другими, а в начало, или, скажем, в конец списка: в первом случае мы должны головной указатель заставить показывать на элемент добавляемый, а указатель next добавляемого элемента заставить показывать на бывший головной указатель, а во втором случае, действовать как обычно, только не забыть next у добавляемого установить в NULL. Прежде чем вынести в студию код, вспомним, что по условию нашей задачи, добавлять элементы надо так, чтобы список был сортированным по фамилии. А как это сделать? А снова просто. Нужно всего-лишь найти такие два элемента a, b, стоящих друг за другом (a < b), что будет выполняться условие a ≤ x < b, где x — собственно, добавляемый элемент. Такие элементы, естественно, могут не найтись, и в этом случае, добавлять новый элемент нужно с начала, или с конца списка, с начала в том случае, если элемент меньше, чем все элементы в списке, и с конца, в случае, если он больше чем все элементы в списке (это говорим мы про упорядочивание по возрастанию). Наш код, в общем-то, руководствуется более простой логикой, но смысл, в целом, тот-же:


Код: C++
//эта интересная штука добавляет студента так, чтобы он был сортированным
//то-есть, добавляет его как-бы не в начало списка
void student_insert(char *surname, long *marks){
    TStudent *t = sm, *n = NULL, *p = NULL;
    //делаем новичка
    n = new TStudent;
    memcpy(n->marks, marks, sizeof(long) * 4);
    memcpy(n->surname, surname, 32);
    n->next = NULL;
    
    //идем по списку, и ищем больший элемент
    while(t != NULL){
        
        //если мы нашли фамилию, которая больше нашей
        if(-1 == strcmpi(surname, t->surname)){
            //лепим новичка сюда
            n->next = t;
            //если предыдущий указатель нулл, то надо менять головной илимент
            if(NULL == p){
                sm = n;
            }else{
                p->next = n;
            }
            return;
        }

        //предыдущий
        p = t;
        //следующий
        t = t->next;
    }
    //в противном случае все печально. новый элемент надо совать в самый конец
    //а на конец у нас уже показывает p
    if(NULL != p){
        p->next = n;
    }else{
        //совсем печальная ситуация, когда нет не одного элмента
        sm = n;
    }
}

Прежде чем пойти дальше, посмотрим на второе задание:


2. Найти и удалить из списка студентов, имеющих хотя бы одну неудовлетворительную оценку. Вывести откорректированный список.

Ну, думаю, что определить, удовлетворительная оценка, или нет, трудностей у нас составить не должно, а вот удаление надо-бы разобрать. Хотя, я думаю, если общая картина ясна, то и смоделировать порядок действий при удалении труда составить не должно. Хотя моделировать то там особенно и нечего… Чтобы элемент произвольный из списка удалить, нужно просто указатель next предыдущего элемента направить на следующий за удаляемым элемент, а память, занимаемую удаляемым элементом — удалить. При удалении последнего элемента алгоритм не меняется. В случае головы, изменять придётся головной указатель, я думаю все смогут догадаться, как именно. Лучше проиллюстрируем процiдурку:


Удаляем элемент
Рис. №877. Удаляем элемент

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


Код: C++
//убиваем студента, и закапываем труп
bool student_delete(TStudent *su){
    TStudent *t = sm;
    
    //такое тоже бывает
    if(NULL == su){
        return false;
    }
    
    //если елемент главный
    if(sm == su){
        //отрываем голову, и удаляем ее
        sm = sm->next;
        delete su;
        return true;
    }
    
    //если не главный
    while(t != NULL){
        //если нашли наш илимент
        if(t->next == su){
            //корректируем указатели так,
            //чтобы они на приговоренного больше не показывали
            t->next = t->next->next;
            //производим экзекуцию
            delete su;
            return true;
        }
        
        //следующий проходите
        t = t->next;
    }
    
    //студент был в бронежилете
    return false;
}

В общем, как всегда, ничего сложного. Прежде чем объявить, что лабу мы сделали, глянем на её 3-е задание, имеющее некоторую аналогию с предыдущим.


3. Освободить память, занятую списком.

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


Код: C++
//убийца студентов
void student_killer(){
    TStudent *t = sm, *d;
    
    //убиваем всех студентов, по одному
    while(t != NULL){
        d = t;
        t = t->next;
        delete d;
    }
}

Вот и всё. С динамическими списками мы разобрались, как, собственно, и с половиной лаб. Идём по такому случаю дальше…


Лабораторная №10. Деревья. Получение навыков работы с древовидными структурами


Деревья, может и чуть реже используются, чем динамические списки, но не менее важны для нас, чем оные. А может даже и более. Самый канонiчный пример дерева — это наша файловая система. Оно, правда, не двоичное, то-есть, у каждого его узла может быть сколько угодно потомков (в любой папке может быть сколько угодно много других папок и файлов). Мы же будем сейчас экспериментировать с двоичными деревьями, которые очень удобны, чтобы в них что-нибудь искать. Не так удобны (из-за возможности вырождения), как бинарные кучи, например, но тем не менее. Прежде чем начать, давайте глянем на задание.


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

Теперь, когда у нас поставлена конкретная задача, объявим небольшую рекурсивную структуру, которая будет отвечать за один элемент (узел) дерева. Тут можно проследить лёгкую аналогию с динамическим списком:


Код: C++
typedef struct THuman {
    char surname[32];
    char sportname[32];
    long score;
    //указатели на ветки
    THuman *l;
    THuman *r;
};

Поскольку дерево у нас двоичное, соответственно, детей у него может быть только двое, именно поэтому, указателей в каждой структуре тоже две штуки. Для удобство называют их правым и левым. Теперь пару слов о построении: чтобы в дереве что-то можно было быстро найти, его сначала нужно для этого правильно построить. Для этого, все узлы дерева должны удовлетворять одному из правил: значение правого потомка должно быть больше или равно значению узла, а значение левого — строго меньше. Или же — всё наоборот. Какое из этих правил использовать — не принципиально, главное чтобы для всех узлов оно было одинаковым. Мы, например, будем использовать правило первое.


Для наглядности, сразу приведём здесь пример дерева, построенного из чисел 65, 120, 70, 40, 10, 45, 155, собственно тот, что предлагает нам методичка к лабе. Надеюсь, это ситуацию прояснит:


Иллюстрация двоичного дерева
Рис. №878. Иллюстрация двоичного дерева

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

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

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


Код: C++
//указатель на вершину дерева
THuman *sm = NULL;

//добавляем человекув
void tree_add_human(THuman **dest, char *surname, char *sportname, long score){
    if(NULL == *dest){
        //случай первый и крайний
        *dest = new THuman;
        memset(*dest, 0, sizeof(THuman));
        //впаиваем данные
        strcpy((*dest)->surname, surname);
        strcpy((*dest)->sportname, sportname);
        (*dest)->score = score;
    }else{
        //так просче и быстрее чем тонна ифов
        tree_add_human(strcmpi(surname, (*dest)->surname) < 0 ? &(*dest)->l : &(*dest)->r, surname, sportname, score);
    }
}

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

2. Написать функцию обхода дерева.

Теперь, разберёмся, как нужно производить обход дерева. По аналогии со списком, делать это будем callback-ом, и нам снова понадобиться рекурсия. Без лишних рассуждений:


Код: C++
typedef bool TTreeWalkCallback(THuman *);

//обходим все дерево каллбеком
bool tree_walk_callback(THuman *tree, TTreeWalkCallback *f){
    if(NULL != tree){
        //предусматриваем досрочный выход
        if(!tree_walk_callback(tree->l, f)){
            return false;
        }
        if(!f(tree)){
            return false;
        }
        if(!tree_walk_callback(tree->r, f)){
            return false;
        }
    };
    //идем даальше
    return true;
}

Здесь предусмотрена та-же фишка с досрочным выходом: как только кто-то возвращает false, обход мгновенно прекращается. Основной принцип же обхода заключается в том, что рекурсивная функция должна сначала обойти левое поддерево узла, затем вызвать колбэк для текущего узла, и затем обойти правое поддерево (конечно, если поддеревья эти не равны NULL). Таким образом, мы обойдем всё дерево так, что во первых, посетим каждый элемент только один раз, и во вторых, элементы которые мы обойдем окажутся упорядочены, в нашем случае, по возрастанию. Если расшифровать, то значение каждого следующего элемента будет больше, предыдущего. Запустив программу, в этом не трудно убедиться…


3. Написать функцию поиска по заданной фамилии спортсмена.

Ну и наконец, самое важное, ради чего дерево и создавалось, в общем-то. Алгоритм почти такой-же как и при добавлении, только вместо добавления ищем элементы, совпадающие с искомым значением. Если нашли — возвращаем указатель на найденный элемент, и возвращаем NULL если не нашли. Сразу это и продемонстрируем:


Код: C++
//обыкновенный поиск по дереву
THuman *tree_search(THuman *hu, char *surname, long *iters){
    //колво используемых итераций
    (*iters)++;
    if(NULL == hu){
        return NULL;
    }
    
    //сравниваем
    long cmp = strcmpi(surname, hu->surname);
    
    //похоже что нашли
    if(0 == cmp){
        return hu;
    }else{
        //рекурсируем, ищем в своих ветках
        return tree_search(cmp < 0 ? hu->l : hu->r, surname, iters);
    }
}

Кстати заметьте, этот пример ещё и подсчитывает количество узлов, которые нам пришлось пройти, прежде чем нужное значение было найдено (или не найдено). В остальном всё очень просто, и как ещё раз можно заметить, имеет сходство с добавлением. Ещё одна интересная тема — как удалить произвольный узел, но поскольку от нас этого искусства не требуют, рассматривать мы это и не будем. Лаба №10 к сдаче готова.


Лабораторная №11. Программные средства для работы с файлами. Текстовые файлы.

Как положить жирафа в холодильник?
1. Открыть холодильник                    
2. Положить туда жирафа                  
3. Закрыть холодильник                      

Суть

От холодильника и жирафа, работа с файлами мало чем отличается. Файл, вообще говоря, это последовательность байтов, хранящаяся в большинстве своём на диске, или другом запоминающем устройстве, с произвольным случайным доступом. Чтобы с файлом что-то сделать, к примеру, считать из него байты, нужно ни много ни мало открыть файл, прочитать байты, закрыть файл. Всё. С записью то-же самое. У файла есть ещё указатель (file pointer), с его помощью можно настроить начальный байт, с которого нужно читать/писать. В Си за работу с файлами отвечает туева хуча функций, нам из них потребуются fopen(), fclose(), fscanf(), fgets(), fputs(), fread(), fwrite(), ну и пожалуй ещё access(), fileno(), ftruncate() и fflush(), но чуть позже. Функция открытия файла fopen() принимает 2 параметра, имя файла, который надо открыть, и режим открытия, в виде текстовой, блеать, строчки. Последнее обстоятельство вызывает у меня исключительную ненависть, из-за своей неочевидности, может я чего-то не понимаю, но с теми-же флагами для Шindowsкой CreateFileEx() работать на порядок приятнее. В общем, режима нам потребуется два три: "r", "w" и "r+", третий понадобиться чуть позже. Первый открывает файл только для чтения (писать не получиться), второй для записи (и чтения) с уничтожением существующего файла (флаг CREATE_ALWAYS для CreateFileEx()), и третий — открывает на чтение/запись, но если файла не существует, функция вернет ошибку. Возвращает fopen() указатель на некую структуру типа FILE, которая для Си является аналогом хэндла (handle), которые использует ОС для идентификации открытых в данный момент файлов. Собственно говоря, почти все функции для работы с файлами в Си, для идентификации файла такой указатель и принимают. В том числе и fclose(), которая файл закрывает, заодно уничтожая структуру, адресуемую указателем.


Теперь осветим немного чтение и запись, в текстовом режиме. После того, как файл мы открыли, из него можно что-нибудь прочитать, или записать. Это можно сделать функциями fgets() и fputs() соответственно. Первая принимает указатель на строку, максимальный её размер, и указатель на файл, вторая — только строку и указатель на файл. Функция fgets() читает из файла до тех пор, пока не найдёт там перевод строки (символ 0x0A или \n), и результат чтения своего помещает в память, на которую показывает первый её параметр, то-есть указатель на строку. Из этого не трудно догадаться, что память, в которую мы собираемся читать нужно для начала выделить. На случай, если вдруг строка окажется длиннее, чем наша выделенная память, предназначен второй параметр — максимальная длинна, по достижении этой длинны, fgets() перевод строки искать перестает, и возвращает то что уже успела начитать. Ну, fputs() работает несколько проще — просто берет, и записывает указанную строку в файл. Возвращает что-нибудь положительное (ноль, например) если все нормально, или -1 (константу EOF) если произошла какая-то жопа. fgets() возвращает указатель на считанную строку, если все прошло нормально, и NULL, если случилась жопа. Вот так всё не логично в этом мире, друзья.


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


1. Создать текстовый файл из N строк. Все слова, начинающиеся с гласных, переписать в один новый файл, а с согласных – в другой новый файл.

Где брать сами строки, нам не сказали, поэтому я решил, что их можно генерировать рандомно, причем так, что одно слово — одна строка. Ну, сказано — сделано:


Код: C++
//генерируем слово в комплекте с переводом строки
void rand_word(char *ss){
    long ml = rand() % 10 + 5;
    ss[ml] = '\n';
    ss[ml + 1] = 0;
    long i;
    ss[0] = 'A' + rand() % (('Z' - 'A') + 1);
    for(i = 1; i < ml; i++){
        ss[i] = 'a' + rand() % (('z' - 'a') + 1);
    }
}

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


Код: C++
//создаем файл первый
FILE *f = fopen("words_both.txt", "w");
if(NULL == f){
	cout << "Failed to create file 'words_both.txt' :(\n";
	return EXIT_FAILURE;
}

char buf[4096];

for(i = 0; i < n; i++){
	//делаем случайное слово
	rand_word(buf);
	//и дописываем его в файль
	fputs(buf, f);
}

fclose(f);

//далее, делаем два других фала и распихиваем туда слова
FILE *fa = fopen("words_a.txt", "w");
if(NULL == fa){
	cout << "Failed to create file 'words_a.txt' :(\n";
	return EXIT_FAILURE;
}

FILE *fb = fopen("words_b.txt", "w");
if(NULL == fb){
	cout << "Failed to create file 'words_b.txt' :(\n";
	return EXIT_FAILURE;
}

f = fopen("words_both.txt", "r");
if(NULL == f){
	cout << "Failed to open file 'words_both.txt' for reading :(\n";
	return EXIT_FAILURE;
}

while(!feof(f)){
	//если строка не пустая
	if(fgets(buf, 4096, f) > 0 && 0 != strcmp(buf, "")){
		//если первая буква гласная, то в первый, иначе во второй
		//сравнение производим по китайски, по другому мне лень
		if(buf[0] == 'A' || buf[0] == 'E' || buf[0] == 'I' || buf[0] == 'O' || buf[0] == 'U' || buf[0] == 'Y'){
			fputs(buf, fa);
		}else{
			fputs(buf, fb);
		}
		
	}
}

cout << "\n";

//все холодильники закрываем
fclose(f);
fclose(fb);
fclose(fa);

На этом примере, кстати, сразу учимся простейшим способом обрабатывать ошибки. Ведь мы знаем, что если fopen() вдруг вернула NULL, то значит что-то пошло не так, и об этом наверное надо-бы сообщить пользователю программы… Что тут, собственно, и делается. Далее, от нас ещё требуется вывести файл, ну, я решил это сделать более правильным красивым способом. Хотя тут если рассуждать, красивый-некрасивый… Впрочем мне пришлось использовать здесь некоторое количество магии Вуду Windows API, чтобы получить вот такую функцию:


Код: C++
//печатаем файл напрямую в консоль
bool file_display(char *fname){
    FILE *f = fopen(fname, "r");
    if(NULL == f){
        printf("Failed to open file '%s' for reading :(\n", fname);
        return false;
    }
    
    HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);

    //перепечатываем файл полностью, без разделения на строки
    char buf[0x1001];
    DWORD rs = 0, rds;
    while(!feof(f)){
        rs = fread(buf, 1, 0x1000, f);
        //складываем данные в консоль
        WriteFile(hcon, buf, rs, &rds, NULL);
    }
    
    cout << "\n";
    
    fclose(f);
    return true;
}

Вся прелесть здесь в максимальной производительности: файл читается блоками по 64 килобайта, и этими-же блоками отправляется в поток консоли. В итоге, файл перепечатывается полностью, без каких-либо изменений. По поводу, к примеру, WriteFile(), советую посмотреть в MSDN, нам тут её описывать долго. А вот про fread() и fwrite() сто́ит рассказать. Обе функции принимают 4 параметра: указатель на память, два размера, и указатель на файл, и возвращают количество элементов, с которыми была произведена операция (сколько было их прочитано/записано), только первая функция, как нетрудно догадаться, выполняет чтение из файла, а вторая — записывает данные в файл, причём, для определения количества байтов, которые надо прочитать или записать, используется произведение размеров (2 и 3-й параметры перемножаются), то-есть, чтобы указать конкретным числом, сколько байтов считать/записать, в один из этих размеров (лучше первый) нужно поставить единицу, а во второй — собственно само число байтов. Сделано так видимо затем, чтобы можно было задавать размер одного элемента отдельно, и количество элементов — тоже отдельно, тогда элементом могла служить, например, структура (а ещё количество записанных/считанных байтов делиться на размер элемента, и уже эта цифра функцией возвращается, да). Но это, извините, большое излишество, на мой скромный, по крайней мере, взгляд. Впрочем вопросы религии нас снова не интересуют.


Кстати, никогда (слышите, никогда!!!), ни при каких обстоятельствах, даже под дулом револьвера, приставленного к виску, не используйте для копирования файла в консоль (или ещё куда-нибудь) функции fgetc()/fputc(). Как мы знаем, эти функции предназначены для записи/чтения одного байта из файла, и как следствие, приводят к вызову WriteFile() для каждого, отдельно взятого байтика. Вот если бы вы захотели принести в комнату виноград из холодильника, вы бы, наверное бы, принесли сразу всю гроздь, не стали бы таскать по одной виноградинке, правда? Так вот здесь смысл тот же самый. Если можно читать блоками, всегда, обязательно нужно читать (писать) блоками, а если этого не делать, это приведёт к катастрофическому падению производительности. Это равносильно попыткам отрисовывать кадры в какой-нибудь игре через SetPixel(), и удивляться, ну почему блять так тормозит. За такие вещи анально карают раскалённой кочергой, помните это, и не делайте так. Впрочем, с лирикой покончим.


Завершим мы первое задание вот таким вот кодом:


Код: C++
//рисуем результат, открывая холодильники по новой
    cout << "\nSource file:\n";
    file_display("words_both.txt");
    
    cout << "\nFile A:\n";
    file_display("words_a.txt");
    
    cout << "\nFile B:\n";
    file_display("words_b.txt");

Что этот код сделает — думаю, все уже поняли. Смотрим второе задание.


2. В новый файл переписать каждую строку наоборот.

Так и хочется сказать — извращенцы! Ну да ладно. Нам здесь понадобиться функция strrev(), чтобы часом не стать изобретателями ещё одного велосипеда. Функция эта принимает один параметр — строку, и все символы в ней записывает в обратном порядке, что нам, собственно, и требуется. Ещё нюанс: поскольку fgets() вычитывает строки вместе с их окончанием — переводом строки, а strrev() таких тонких различий между символами не делает, от перевода этого нам нужно избавиться, чтобы он не оказался в строке на первом месте после её разворота. Больше здесь размышлять неочем. Берём, и пишем:


Код: C++
//ну и наконец реально последний этап
f = fopen("words_both.txt", "r");
if(NULL == f){
	cout << "Failed to open file 'words_both.txt' for reading :(\n";
	return EXIT_FAILURE;
}

FILE *fr = fopen("words_rev.txt", "w");
if(NULL == fr){
	cout << "Failed create file 'words_rev.txt' :(\n";
	return EXIT_FAILURE;
}

while(!feof(f)){
	//если строка не пустая
	if(fgets(buf, 4096, f) > 0 && 0 != strcmp(buf, "")){
		//реверсим строку и записываем в другой файл
		//перевод строки реверсить не надо
		buf[strlen(buf) - 1] = 0;
		strrev(buf);
		buf[strlen(buf)] = 0x0a;
		fputs(buf, fr);
	}
}

fclose(fr);
fclose(f);

cout << "\nReversed strings file:\n";
file_display("words_rev.txt");

Что, зачем, куда, и почему, мы уже, кажется, разъяснили. Интересное в этой лабе подошло к концу. А это значит, что мы, собрав последнюю волю в кулак, выпив последнюю чашку кофе, и предвкушая скорый конец этому кошмарному сну, переходим к 12-й лабе.


Лабораторная №12. Обработка бинарных файлов.


Ну, о файлах мы уже знаем довольно много, а что ещё не знаем, очень скоро узнаем. Сразу смотрим, что из нас хотят извлечь:

Запись имеет вид: ФИО пассажира, количество занимаемых багажом мест, общий вес вещей. Используя функции и режим меню:
а) создать файл из N записей;
б) просмотреть файл;
в) добавить в конец файла новую запись;
г) найти и удалить из файла записи о пассажирах, общий вес вещей которых меньше, чем 10 кг.


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


Итак, наш файл будет представлять себя самый обыкновенный массив из структур. Структура будет выглядеть примерно так:


Код: C++
//структуру принудительно объявляем без выравнивания
typedef struct TRecord {
    char psname[64];
    long places;
    long weight;
} __attribute__((aligned(1)));

Тут нужно вспомнить, что такое выравнивание, о котором мы говорили в лабораторной №8. Поскольку структура сия будет храниться в файле, и выигрыш от выравнивания, как следствие, будет бесконечно малым, нам лучше сделать приоритет на экономии байтиков, и выравнивание убрать, то-есть сделать его равным единичке. Хотя в данном случае от этого никому шибко жарко-холодно не станет — все поля и так кратны выравниванию по-умолчанию на 4. Но мы принципиальны и непреклонны. Кстати, важное замечание: поле char psname[64]; наглядно демонстрирует нам, как не надо хранить строки в файлах в более реальных программах. Почему? Ну очевидно: если строка будет из 2-х символов, 61 байт пропадёт зря. А если из 67 — то это будет EPIC FAIL. В нормальных программах отдельно храниться длинна строки (числом long, например), и сама строка, и чтение производиться потоковым методом, то-есть, сначала читается 4 байта, содержащие длину строки, и только потом читается указанное там количество байтов — это и будет нашей строкой. Мы сказали образно и упрощённо, но оно на самом деле примерно так.


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


Код: C++
//файлег, в котором все у нас будет храниццо
const char DB_FILE [] = "lab12_database.bin";

//работать мы бдуем с только одним файлом
FILE *p_file = NULL;

//готовим программу к работе
bool file_db_open(){
    if(access(DB_FILE, 0) == -1){
        //файла пока еще нету
        p_file = fopen(DB_FILE, "w+");
    }else{
        //файл уже есть
        p_file = fopen(DB_FILE, "r+");
    }
    return NULL != p_file;
}


//закрываем наш любимый файлик
bool file_db_close(){
    
    if(NULL == p_file){
        return false;
    }
    
    //сбрасываем буфера, на всякий
    fflush(p_file);
    fclose(p_file);
    p_file = NULL;
    return true;
}

Что такое fflush(), узнаем чуть позже. Сейчас мы лучше сконцентрируемся на первом задании (то-есть, для нас, пункте в). Оно заключается в том, что нужно получить от юзера некоторые данные, и в файл их записать, в конец. То-есть, добавить структуру в наш файл-массив. Для этого, нам, с помощью fseek(), надо файловый указатель сместить в самый конец, и только потом вызвать fwrite() со всеми нужными параметрами. Короче, будет так:


Код: C++
//дописываем в конец файла структурку
bool file_db_append(TRecord *r){
    if(NULL == p_file){
        return false;
    }
    //ставим цуказатель в конец
    fseek(p_file, 0, SEEK_END);
    long n_wrt = fwrite(r, sizeof(TRecord), 1, p_file);
    //если чтото-там записалось
    if(1 == n_wrt){
        //проделав все манипуляции, сбросим буфера на диск
        fflush(p_file);
        return true;
    }else{
        //чтото пошло наперекосякос
        return false;
    }
}

Константа SEEK_END говорит нам, что положение файлового указателя надо указывать от конца файла. Есть ещё SEEK_SET (от начала файла) и SEEK_CURRENT (от текущего положения), обычно используется SEEK_SET. Второй параметр fseek() отвечает за, собственно, новое положение указателя. В нашем случае — ноль от конца — приводит к установке указателя, собственно, в конец файла. Ну а дальше записываем, и за счёт этого, размер файлика вырастает на размер одной структурки. Ах да, ещё сто́ит отметить, что при вызове любых функций чтения/записи, они сдвигают файловый указатель вперёд на считанное/записанное количество байтов, и поэтому при чтении всего файла от начала до конца указатель сдвигать нам не надо.


А вот теперь поговорим про fflush(). Надо сказать сразу, что функция эта здесь совершенно не обязательная, и используется тут исключительно из правил хорошего тона. Всё дело в том, что когда мы записываем некоторые данные в файл функциями fwrite(), fputs(), fputc() и пр., где-то в недрах рантайма Си, это рано или поздно приводит к вызову WriteFile() и WriteFileEx(), которые в свою очередь отправляют записываемые данные ядру операционной системы, чтобы оно их, собственно, уже на уровне железа, записало в наш файлик, то-есть, на жёсткий диск, к примеру. Но ядро нынешних ОС весьма хитрое, мало того что оно поддерживает асинхронную запись (и чтение), так в нём ещё существует такая штука, как кэширование записи. Другими словами, вызов WriteFileEx() с какими-то данными, совершенно не гарантирует, что данные эти немедленно в нужный файл попадут, и запишутся на диск. На самом деле, данные наши попадут в некоторое недосягаемое нам измерение пространство, которое находится где-то между чистилищем и преисподней в недрах ядерной памяти ОС, и полностью контролируются ядром, ну, и ещё драйверами файловой системы, и известное нам как кэш-буфера файловой системы (в MSDN возможно зовут их по другому). Вернее, контроль мы над этими буферами на себя конечно некоторый взять можем, например, при открытии файла через CreateFileEx() можно указать флаг FILE_FLAG_NO_BUFFERING, правда это повлечет дополнительные проблемы с выравниванием. Но есть ещё одна штука, которая позволяет нам гарантировать то, что данные, которые мы очень хотим записать, 100% попадут на жесткий диск, и покинут пределы буферов файловой системы, и называется эта штука FlushFileBuffers(), а в Си для этой API существует обёртка, которая как раз и известна нам в виде функции fflush(). Именно поэтому, после записи очередного кусочка данных в наш файлик, функцию эту мы и вызываем — мы просто заботимся о том, чтобы когда наш маленький юзер введёт парочку десятков записей, и тут вдруг ВНЕЗАПНО какие-то злые дядьки вырубят в доме электричество, данные, которые наш маленький юзер так усердно вбивал — сохранились бы, а без предусмотрительного вызова fflush() они, вероятно бы, так и остались бы в кэш-буферах, ввиду их (данных) мизерного размера, и после выключения электричества, навсегда бы покинули этот бренный мир… Ну я думаю понятна та вещь, что кэш-буфера располагаются в энергозависимой оперативной памяти. Эта поучительная история, в общем демонстрирует нам, почему именно, иногда (а лучше всегда), мы должны использовать fflush(), или его аналоги. В качестве доказательства этого факта, вы можете этот интересный эксперимент, с отключением света, и влиянием на последствия вызова fflush(), провести дома на своём компьютере. Будет поучительно.


Но мы что-то как-то куда-то совсем опять отвлеклись. Возвращаемся к реальной жизни. Я думаю как у юзера выпросить данные все знают. Поэтому мы перейдём к заданию следующему. А в нём нас просят удалять записи. Я думаю, что как удалить элемент из обыкновенного массива (передвинуть все элементы на один элемент, чтобы они заняли место удалённого), мы тоже все знаем, поэтому в теории, тут не должно возникнуть затруднений, поскольку наш файл этот тот же самый массив. Но есть тут одно НО, перемещать все элементы в файле, идущие за удаляемым — задача весьма ресурсоёмкая, особенно если элементов там много. Да и вообще, перемещение всех элементов, не самый лучший вариант закрытия дырки, образованной удалённым элементом. Мне в голову пришёл другой способ: на место удалённого элемента класть самый последний элемент. Нарушается, правда порядок, но в данном случае, нас это совершенно не смущает. Как именно это делать, смотрим сразу на примере:


Код: C++
//выясняем рамер нашего файла
long file_db_size(){
    if(NULL == p_file){
        return 0;
    }
    
    return filelength(fileno(p_file));
}

//очистка файла от ненужных данных
bool file_db_reduce(long minw, long *n_deleted){
    if(NULL == p_file){
        return false;
    }
    
    //счетчик удаленных
    *n_deleted = 0;
    
    //здесь мы применим хитрость, и будем на место удаленного класть последнюю запись..
    long cn = file_db_size() / sizeof(TRecord);
    long i;
    
    TRecord buf;
    
    //топаем снизу вверх
    for(i = cn - 1; i >= 0; i--){
        fseek(p_file, i * sizeof(TRecord), SEEK_SET);
        fread(&buf, sizeof(TRecord), 1, p_file);
        
        //если условие выполняется
        if(buf.weight < minw){
            //мысленно укорачиваем файл
            cn --;
            //счетчик удаленных уывеличиваем
            (*n_deleted)++;
            
            if(i < cn){
                //ежели есть последущие елементы, то последний кладем на это место
                fseek(p_file, cn * sizeof(TRecord), SEEK_SET);
                fread(&buf, sizeof(TRecord), 1, p_file);
                fseek(p_file, i * sizeof(TRecord), SEEK_SET);
                fwrite(&buf, sizeof(TRecord), 1, p_file);
            }
            
            //слегка обрезаем файлик
            ftruncate(fileno(p_file), cn * sizeof(TRecord));
        }
        //и так - много-много раз
    }
    
    //проделав все манипуляции, сбросим буфера на диск
    fflush(p_file);
    
    return true;
}

Главная особенность здесь — искать нужно снизу вверх, чтобы элемент, который мы берём с конца с целью заткнуть образовавшуюся дыру, всегда был уже корректным, а иначе может получиться белиберда. Кстати, если вам скажут, что более быстрый способ, чем этот — переписать все данный сначала в новый файл, а старый потом удалить, не верьте. Это ложь, пиздёж, и провокация. Такая манипуляция ОДНОЗНАЧНО будет дольше, хотя-бы потому, что драйверу файловой системы (в случае NTFS) надо будет минимум два раза слазить в MFT, чтобы там произвести удаление и создание записи файлика. Ну просто без вариантов. Даже способ с перемещением всего остаточного хвоста будет работать значительно быстрее.


Здесь мы ещё видим функцию ftruncate(). Она призвана делать одну операцию: устанавливать размер файла. Обычно, с целью его обрезать (как в нашем случае), хотя могут быть и исключения. Является, кстати, обёрткой для SetEndOfFile(). У ftruncate() есть одна особенность — она принимает не указатель на Сишную структуру-файл, а номер файла, который можно узнать с помощью функции fileno(). Доподлинно неизвестно, но теоретически это может быть именно хэндл файла в ОС. Этот же номер, кстати, принимает и другая функция filelength(), призванная узнавать размер открытого файла.


На этой мажорной ноте мы можем подметить, что 12-я лабораторная сдалась в плен, и мы её сделали. А это значит, что мы сделали все 12 лабораторных работ из семестра… Пришло самое время вздохнуть с облегчением и похвалить себя.


Исходники


Следуя традициям и обещанию, приобщаю к народному достоянию рабочие исходники всех 6-ти рассмотренных лабораторных, скачать их можно отсюда. В комплекте с ними идут файлы данных, используемые в некоторых лабах, будьте внимательны. Как обычно, всё сделано для компиляции в Dev-C++. Заголовки, гарантирующие работоспособность всех примеров, таковы:


Код: C++
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <conio.h>
#include <io.h>
#include <windows.h>
#include <string.h>
#include <unistd.h>

using namespace std;

Вот мы и полностью завершили наш обзор. В моих наушниках как раз доигрывает 8-ми часовой, 350-й эпизод A State of Trance, и последний трэк его очень подходит, чтобы описать, что я ощущаю (а возможно и ощущают читатели), завершив, наконец, эту статью…


Продолжительность 08:52    Битрейт 184 кбит/с   

На этом всё. До скорых встреч, друзья!
Ключевые слова Программизм, Лабораторная, Массивы, индексная сортировка, файл, динамические списки, Структура, Деревья, fflush, Dev-C++
QR-код
Интересное
HV relay driver, или продолжение темы зарядовых насосов Задача сего устройства — зарядить конденсатор до 36 вольт, разрядить его на обмотки электромагнитов, и подать на них небольшое постоянное напряжение, для поддержки их включенными.

Читать »»
Случайные фото