Сортировка и поиск записей в ОЗУ и в файлах

Сортировка и поиск записей в массивах не представляет каких-либо затруднений. Необходимо предусмотреть в массивах дополнительные ячейки для размещения записей, если записи будут добавляться в массив. Для сортировки и поиска в массивах можно предварительно прочитать все записи в массив и затем применить к массиву необходимые библиотечные функции. После сортировки массив может быть «сброшен» обратно в файл.

Пример

В программе выполняется сортировка и поиск элемента в массиве структурных переменных.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_BOOKS 1500

#define NAME 32

#define TITLE 64

typedef struct { char author [NAME];

char title [TITLE];

int year;

float price;

} BOOKS;

#include “myf.h”

void main(void)

{

int index, ret, func_number, i = 0;

BOOKS new; // переменная-ключ или новая запись

BOOKS *start, *ptr, *work; // память под массив, указатель текущей записи, рабочий

// указатель

int (*fcmp[5])() = // массив указателей на функции сравнения

{cmp_name, cmp_title, cmp_year, cmp_price, cmp_totally};

// Выделение памяти под массив и ввод записей из файла или в диалоге

start = (BOOKS *) calloc(MAX_BOOKS, sizeof(BOOKS));

if(start == NULL)

{

printf(“Память под массив не может быть выделена!\n”);

(void)getchar();

return;

};

…………………………………………………………………………………………………..

// начальный адрес массива записей хранится в start, в index – порядковый номер

// последнего введенного элемента, на последний элемент ссылается ptr,

// максимальный размер буфера для размещения записей не должен

// превышать MAX_BOOKS элементов

…………………………………………………………………………………………………

// сортировка по критерию, который запрашивается в диалоге и код критерия

// помещается в переменную func_number: 0 – по имени автора, 1 – по заголовку,

// 2 – по году издания, 3 – по цене

func_number = input_criteria();

qsort(start, index +1, sizeof(BOOKS), fcmp[func_number]);

…………………………………………………………………………………………………...

// добавление нового элемента в массив, элемент извне вводится в переменную new

// если элемента нет в массиве, то он добавляется, иначе – вывод сообщения

work = start;

input_book(&new); // ввод нового элемента

work = lfind(&new, work, &index, sizeof(BOOKS), fcmp[4]);

if(work == NULL) // нет совпадения по всем полям

{

index++;

if(index < MAX_BOOKS) // места достаточно

start[index – 1] = new;

else

{

puts(“База заполнена до предела!\n”);

index--;

break;

}

}

else

puts(“В базе уже есть этот элемент!\n”);

…………………………………………………………………………………………………

// Поиск в массиве элемента по заданному ключу, автору, названию и т.д.

// критерий поиска вводится в переменную func_number

func_number = search_criteria();

input_key(func_number, &new);

work = start;

for(; work != ptr;)

{

work = lfind(&new, work, &index, sizeof(BOOKS), fcmp[func_number]);

if(work != NULL)

{

puts(“Элемент найден:\n”);

output_book(work); // вывод результатов

break;

}

else

puts(“”);

}

…………………………………………………………………………………………………

}

Комментарий. #include “myf.h” указывает файл, где содержатся прототипы используемых функций. Если указано – “…”, то поиск файла выполняется в текущем каталоге, где расположен основной текст программы, затем поиск будет продолжен на основе пути, указанного в опции компилятора –l и только потом в стандартном INCLUDE. Если файл указан в форме <…>, то поиск выполняется сразу в стандартном каталоге. Прототипы в файле myf.h выглядят следующим образом:

int comp_name(const BOOKS *, const BOOKS *);

int comp_price(const BOOKS *, const BOOKS *);

int comp_title(const BOOKS *, const BOOKS *);

int comp_year(const BOOKS *, const BOOKS *);

int comp_totally(const BOOKS *, const BOOKS *);

int input_criteria(void);

int search_criteria(void);

void input_key(int, BOOKS *);

void input_book(BOOKS *);

Файл с определениями функций компилируется отдельно:

#include <string.h>

#define NAME 32

#define TITLE 64

typedef struct { char author[NAME];

char title[TITLE];

int year;

float price;

} BOOKS;

………………………………………………….

int comp_name(const BOOKS *one, const BOOKS *two)

{

return (strnicmp(one -> author, two -> author, strlen(one -> author)));

}

int comp_price(const BOOKS *one, const BOOKS *two)

{

return (one -> price – two -> price);

}

int comp_title(const BOOKS *one, const BOOKS *two)

{

return (strnicmp(one -> title, two -> title, strlen(one -> title)));

}

int comp_year(const BOOKS *one, const BOOKS *two)

{

return (one -> year – two -> year);

}

int comp_totally(const BOOKS *one, const BOOKS *two)

{

if(!strnicmp(one -> author, two -> author, strlen(one -> author)) &&

!strnicmp(one -> title, two -> title, strlen(one -> title)) &&

(one -> year == two -> year) &&

(one -> price == two -> price))

return 0;

else

return -1;

}

………………………………………………………………

// прочие функции

………………………………………………………………

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

int strnicmp(const char *s1, const char *s2, size_t maxlen),

которая преобразует все буквы в ASCIIZ-строках s1 и s2 в строчные и сравнивает их в лексикографическом порядке. Возвращает значения меньше 0 (s1 < s2), равное 0 (s1 == s2) или больше 0 (s1 < s2) в соответствующих случаях. Сравнение ограничивается maxlen числом символов.

Пример

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

#include <stdio.h>

#include <conio.h>

…………………………………………………………...

typedef struct BOOK TBOOK;

FILE *stream;

long length, k;

TBOOK *arr;

……………………………………………………………

stream = fopen(“…”, “r+b”);

if(stream == NULL)

{

printf(“Can’t open file!\n”);

return;

}

…………………………………………………………..

fseek(stream, 0L, SEEK_END);

length = ftell(stream);

k = length/sizeof(TBOOK);

arr = (TBOOK *)calloc(k, sizeof(TBOOK));

fseek(stream, 0L, SEEK_SET);

fread(arr, sizeof(TBOOK), k, stream);

// применение qsort

…………………………………………………………….

Вопросы для самоконтроля

• Чем отличаются аргументы функций malloc() и calloc()?
• Как выполняется «освобождение» heap-памяти?
• Как рассчитывается доступ к элементам не одномерных массивов через указатели?
• Опишите основные характеристики функций поиска и сортировки для структурных массивов!
• Как можно вычислить число записей в файле не считывая записи в основную память?

Вопросы для самостоятельного изучения

• Назначение и спецификации функций ftell() и fseek()?