Int main()

{

root = add_node(NULL,"Root");

TREE* current = add_node(root,"File 1",LEFT);

current = add_node(current,"File 2",LEFT);

current = add_node(root,"Folder 1",RIGHT);

current = add_node(current,"File 11",LEFT);

current = add_node(current,"File 12",LEFT);

current = add_node(root->right,"Folder 2",RIGHT);

current = add_node(current,"File 21",LEFT);

show_tree();

del_tree();

root = NULL;

return 0;

}

Данная функция сначала инициализирует глобальный указатель root как

корень дерева и в качестве первого аргумента функции add_node() записывает

NULL, что означает, что предыдущего объекта не существует. Затем вводится

вспомогательный указатель current, с помощью которого выполняется создание

двоичного дерева, описывающее файловую структуру (рис. 6). После создания

дерева вызывается функция show_tree() для его отображения на экран, затем

оно удаляется и программа завершает свою работу.

Динамические типы данных – деки, стеки, очереди. Виды, структура, основные свойства.

Применение.

СТЕК

Цель работы: изучить теорию и научиться программировать стек.

Теоретические сведения

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

структуры для хранения данных. Наиболее простой из них является стек,

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

собой с помощью указателей. Особенность организации структуры стека

показана на рис. 3.

Из рис. 3 видно, что каждый объект стека связан с

последующим с помощью указателя next. Если

указатель next равен NULL, то достигнут конец стека.

Особенность работы со стеком заключается в том, что

новый объект всегда добавляется в начало списка.

Удаление также возможно только для первого

элемента. Таким образом, данная структура реализует

очередь по принципу «первым вошел, последним

вышел». Такой принцип характерен при вызове

функций в рекурсии, когда адрес каждой

последующей функции записывается в стеке для

корректной передачи управления при ее завершении.

Для описания объектов составляющих стек

можно воспользоваться структурами, например,

следующее определение задает шаблон для описания

объекта данных стека:

typedef struct tag_obj {

char name[100];

struct tag_obj* next;

} OBJ;

Здесь поле name – символическое имя объекта, а next – указатель на

следующий объект. Зададим указатель top как глобальную переменную со

значением равным NULL:

OBJ* top = NULL;

и введем функцию для добавления нового объекта в стек:

void push(char* name)

{

OBJ* ptr = (OBJ *)malloc(sizeof(OBJ));

структуры стека

strcpy(ptr->name,name);

ptr->next = top;

top = ptr;

}

Данная функция в качестве аргумента принимает указатель на строку

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

инициализируется указатель ptr на новый созданный объект. В поле name

записывается переданная строка, а указатель next инициализируется на первый

объект. Таким образом, добавленный объект ставится на вершину списка.

Для извлечения объекта из стека реализуется следующая функция:

void pop()

{

if(top != NULL)

{

OBJ* ptr = top->next;

printf("%s - deleted\n",top->name);

free(top);

top = ptr;

}

}

В данной функции сначала выполняется проверка указателя top. Если он не

равен значению NULL, то в стеке имеются объекты и самый верхний из них

следует удалить. Перед удалением инициализируется указатель ptr на

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

Затем вызывается функция printf(), которая выводит на экран сообщение об

имени удаленного объекта. Наконец, вызывается функция free() для удаления

самого верхнего объекта, а указатель top инициализируется на следующий

объект.

Для анализа работы данных функций введем еще одну вспомогательную

функцию, которая будет выводить имена объектов, находящихся в стеке.

void show_stack()

{

OBJ* ptr = top;

while(ptr != NULL)

{

printf("%s\n",ptr->name);

ptr = ptr->next;

}

}

Работа данной функции реализуется с помощью цикла while, который

работает до тех пор, пока указатель ptr не достигнет конца стека, т.е. пока не

будет равен значению NULL. Внутри цикла вызывается функция printf() для

вывода имени текущего объекта на экран и указатель ptr перемещается на

следующий объект.

Рассмотрим применение данных функций в функции main():

int main()

{

char str[100];

for(int i = 0;i < 5;i++) {

sprintf(str,"Object %d",i+1);

push(str);

}

show_stack();

while(top != NULL) pop();

return 0;

}

Здесь создается стек, состоящий из 5 объектов, с помощью оператора

цикла for. Внутри цикла инициализируется переменная str с именем объекта,

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

функции show_stack() на экране появляются следующие строки:

Object 5

Object 4

Object 3

Object 2

Object 1

Полученные результаты показывают, что последний 5-й добавленный

объект находится на вершине стека, а первый – в конце. При вызове функции

pop() в цикле while() осуществляется удаление элементов стека из памяти ЭВМ.

В результате на экране появляются строки:

Object 5 - deleted

Object 4 - deleted

Object 3 - deleted

Object 2 - deleted

Object 1 – deleted

Таким образом, функция pop() удаляет верхние объекты стека с 5-го по 1-й.__

Очередь на базе списка

Из механизма FIFO следует, что в очереди доступны два элемента v первый и последний простая очередь (см. рис. 5).

Структура данных, представляющая очередь, могла бы выглядеть следующим образом:

type

TypeOfElem= {};

Assoc= ^ElementOfQueue;

ElementOfQueue= record

Elem: TypeOfElem;

NextElem: Pointer

end;

Queue= Assoc;

3.2 Создание (очистка) очереди

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

procedure CreateQueue ( var FirstElem, LastElem: Queue);

begin

FirstElem:= nil;

LastElem:= nil

end;

3.3 Проверка очереди на пустоту

Условием пустоты очереди является значения указателей на первый и последний элементы, равные nil.

function QueueIsClear( var FirstElem, LastElem: Queue ): Boolean;

begin

QueueIsClear:= ( FirstElem= nil ) and ( LastElem= nil )

end;

3.4 Включение элемента в очередь

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

procedure IncludeInQueue( var FirstElem, LastElem: Queue; NewElem: TypeOfElem);

var

ServiceVar: Queue;

begin

{создание нового элемента}

new( ServiceVar );

ServiceVar^.Elem:= NewElem;

ServiceVar^.NextElem:= nil;

if ( FirstElem= nil ) and ( LastElem= nil ) then begin

{создать очередь из одного элемента}

FirstElem:= ServiceVar;

LastElem:= ServiceVar

end

else begin

{созданный элемент поместить в конец очереди}

LastElem^.NextElem:= ServiceVar;

LastElem:= ServiceVar

end

end;

3.5 Выбор элемента из очереди

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

procedure SelectFromQueue( var FirstElem, LastElem: Queue; var Result: TypeOfElem);

var

ServiceVar: Queue;

begin

if not ( ( FirstElem= nil ) and ( LastElem= nil ) ) then begin

Result:= FirstElem^.Elem;

ServiceVar:= FirstElem;

{убираем 1-ый элемент из очереди}

FirstElem:= FirstElem^.NextElem;

{был ли это последний элемент}

if FirstElem= nil then

LastElem:= nil;

dispose( ServiceVar )

end

end;

Работа с файлами: представления файлов, наборы функций для работы с файлами.

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

Открытие и закрытие файла

Для открытия файла служит функция fopen, продекларированная следующим образом:

FILE *fopen(char *name; char *mode);

Эта функция возвращает файловый указатель, либо NULL, если открыть файл не получилось, а принимает name – строку с именем файла или путём к нему и mode – строку с режимом открытия. Существуют следующие режимы открытия: Режим Назначение

"r" Только чтение, открытие несуществующего файла невозможно.

"r+" Чтение и запись, открытие несуществующего файла невозможно.

"w" Запись в пустой файл. Если файл не существует, то он создаётся, а если существует, то вся информация в нём стирается.

"w+" Чтение и запись со стиранием при открытии. Если файл не существует, то он создаётся.

"a" Запись в конец – запись всегда осуществляется только после последнего байта файла.

"a+" Запись в конец с возможностью чтения.

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

Побайтовый ввод

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

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