Функции двоичного ввода-вывода

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

FILE *in, *out;

in=fopen(“file1.dbl”, “rb”); //файл открыт для чтения в двоичном режиме

out=fopen(“file2.dbl”, “wb”); //файл открыт для записи в двоичном режиме

Функция fread производит ввод из потока в структурную переменную и имеет четыре аргумента:

• Адрес структуры, куда будет производиться чтение;

• Размер одной структуры в байтах;

• Количество читаемых структур;

• Имя потока.

В качестве результата функция возвращает количество реально введенных структур, а в случае обнаружения конца файла – 0.

Пример 6. Прочитать очередную структуру из потока in в переменную tel.

Fread(&tel, sizeof(tel), 1, in);

Пример 7. Пусть из потока in необходимо заполнить массив структур, при этом известно, что структур не более 100.

TEL tel[100];

int n;

n=fread(tel, sizeof(tel[0]), 100, in);

После ввода определяем реальный размер массива – n.

Количество структур в файле можно узнать и поделив размер файла на размер одной структуры.

Функция fwrite производит вывод из структурной переменной в поток и имеет четыре аргумента:

• Адрес записываемой структуры;

• Размер одной структуры в байтах;

• Количество записываемых структур;

• Имя потока.

В качестве результата функция возвращает количество реально записанных структур.

Пример 8. Записать структуру tel в поток out.

Fwrite(&tel, sizeof(tel), 1, out);

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

Проанализируем функцию:

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

В качестве результата возвратим сигнал (0 или 1) об успешности операции.

Вспомните режим открытия потока, при котором происходит накопление (дозапись) данных.

#include<stdio.h>

int AppendStructFile (char * NameFile)

{

FILE * out;

TEL tel;

out=fopen(NameFile, “ab”);

if (out==NULL)

return 0;

puts(“\nВведите структуру”);

InStruct(tel);

fwrite(&tel, sizeof(tel), 1, out);

return 1;

}

Динамические структуры данных

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

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

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

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

struct Info // структура для данных

{

…

};

struct Node

{

Info info;

Node *next;

};

Наиболее общей динамической структурой является линейный список.

Линейный список называется однонаправленным, если каждый элемент списка содержит адрес следующего элемента. У последнего элемента адрес 0.

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

Линейный список называется закольцованным, если последний элемент списка содержит адрес, указывающий на первый элемент списка.

Список определяется адресом начала списка.

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

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

• Начальное формирование списка;

• Добавление элемента в конец списка;

• Чтение элемента с заданным ключом;

• Вставка элемента в заданное место списка (до или после ключа);

• Удаление элемента с заданным ключом;

• Сортировка списка по ключу;

• Вывод списка на экран;

• Освобождение памяти, занимаемой списком.

Каждая операция реализуется в виде функции.

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

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

Проанализируем функции:

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

Функция add добавляет структуру в конец списка, для этого ей достаточно знать адрес начала списка, но для краткости действий передадим ей адрес последнего элемента в списке, а результатом функции будет новый адрес последнего элемента в списке.

Функция print выводит список на экран, зная адрес начала списка. Результат не возвращается.

В программе используются переменные: pbegin – для хранения адреса начала списка, pend – для хранения адреса последней структуры в списке.

#include<iostream> //подключение системных средств для

using namespace std; //возможности использовать потоки ввода-вывода

struct Info

{

int d;

};

struct Node

{

Info info;

Node *next;

};

Node * first(void);

Node * add(Node * pend);

void print(Node * pbegin);

void main(void)

{

Node *pbegin, *pend;

int i;

pend=pbegin=first(); //создали список

for(i=0;i<5;i++) //добавили еще 5 элементов в список

pend=add(pend);

print(pbegin); //вывели весь список на экран

return;

}

//Начальное формирование списка

Node*first(void)

{

//Выделяем память под элемент списка

Node*pv=newNode;

cout<<“\nВведите число”;

cin>>pv->info.d;

pv->next=0; //Адрес последней структуры в списке - 0

returnpv; //возврат адреса начала списка

}

//Добавление элемента в конец списка

Node*add(Node*pend)

{

//Выделяем память под очередной элемент списка

Node * pv=new Node;

cout<<“\nВведите число”;

cin>>pv->info.d;

pv->next=0; //Адрес последней структуры в списке - 0

pend->next=pv; //Сцепляем по адресу созданную структуру со списком

returnpv; //возврат нового адреса последней структуры в списке

}

//Вывод списка на экран

voidprint(Node*pbegin)

{

Node*pv=pbegin;

while(pv) //пока адрес текущей структуры списка не 0

{

cout<< pv->info.d<<endl;

pv=pv->next; //переход к следующей структуре в списке

}

return;

}

Задание 4. Добавьте к вышеприведенной программе еще какие-либо операции над списком.

Дадим краткие определения других динамических структур данных.

Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняется с одного конца списка, называемого вершиной стека. При выборке элемент исключается из списка. Другие операции со стеком не определены.

Очередь – это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец списка, а выборка - из другого конца списка. При выборке элемент исключается из списка. Другие операции не определены.

Бинарное дерево – это структура, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на другие бинарные деревья.