Разработка программы, реализующей алгоритм бинарного дерева

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ТЕОРЕТИЧЕСКИЙ ВОПРОСOpusNavigatorManager.NETCommanderCommander- очень легкий и компактный файловый менеджер

Проводник Windows

Q-Dir

ПОСТАНОВКА ЗАДАЧИ

ОПИСАНИЕ ПРОГРАММЫ

РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

ТЕСТИРОВАНИЕ

ВЫВОДЫ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

Теоретический вопрос - Обзор файловых менеджеров для Windows.

Следует рассмотреть: что представляет собой файловый менеджер, какие бывают файловые менеджеры, и основные файловые менеджеры разработанные под ОС Windows.

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

Для выполнения задачи понадобится структура для бинарного дерева, а также функции для добавления, удаления, поиска и вывода на экран.

ТЕОРЕТИЧЕСКИЙ ВОПРОС

Файловый менеджер (англ. <#"552459.files/image001.gif">

Рисунок 1 - Directory Opus

Данный файловый менеджер сочетает в себе простую работу с файлами и гибкостью настроек. Он также обладает полностью настраиваемым интерфейсом, встроенным ftp-клиентом с поддержкой SSL и SSH/SFTP, встроенный SMTP-клиентом, внутренней поддержкой архивов, просмотром мультимедиа, конвертацией графических файлов, встроенным командным языком, расширенными функциями поиска и переименования файлов, настраиваемыми горячими клавишами для управления.

Directory Opus может встраиваться в систему, в том числе полностью заменять собой Проводник...

DOS Navigator

DOS Navigator - консольный файловый менеджер <#"552459.files/image002.gif">

Рисунок 2 - DOS Navigator

На сегодняшний день распространяется в открытых исходных кодах <#"552459.files/image003.gif">

Рисунок 3 - FAR Manager

FAR Manager как и многие другие менеджеры также наследует две панели, стандартную расцветку и систему команд <#"552459.files/image004.gif">

Рисунок 4 - Редактор FAR с плагином Colorer <#"552459.files/image005.gif">

Рисунок 5 - FreeCommander

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

Из дополнительных функций можно отметить поиск файлов внутри архивов, соединение и разделение больших файлов, синхронизацию и сравнение папок, просмотр и редактирование свойств файлов, подключение к удалённым серверам и работу с командной строкой.

Nomad

это мощный файловый менеджер написанный на языке Delphi. Впервые выпущен в 1998 году.

Рисунок 6 - Nomad

Программа имеет мощную систему фильтрации файлов, поддерживает поиск файла по множеству параметров, функцию Drag and Drop, копирование и вставку файлов из буфера обмена. Обладает полной настройкой клавиатурной раскладки и цветовой схемы, а также возможностью создавать свои панели инструментов. Nomad имеет мощный встроенный просмотрщик <javascript:void(0);> файлов и редактор текстовых файлов, который поддерживает различные кодовые таблицы (включая Unicode и UTF-8), и легко конфигурируемое меню утилит.

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

Nomad.NET

Работа над проектом началась 2008 году. Программа была полностью переписана (не включает в себя строк кода из предыдущего Nomad) и как следствие реализована совершенно по новому.

Рисунок 7 - Nomad.NET

Новый Nomad разработан изначально многопоточным, а значит почти все долгие операции выигрывают время при использовании многоядерного процессора.

Среди достоинств: полная поддержка Unicod, поддержка вкладок (которые в отличие от других менеджеров, не привязаны к панели), мощные системы закладок, поиска и фильтрации, многофункциональная панель управления, поддержка большого количества форматов архивов, FTP папок и плагинов Total Commander.

Total Commander

Первая версия программы стала доступна 25 сентября <#"552459.files/image008.gif">

Рисунок 8 - Total Commander

К возможностям программы относятся многоязычный двухпанельный вкладочный графический интерфейс, полностью настраиваемые сочетания клавиш <#"552459.files/image009.gif">

Рисунок 9 - Unreal Commander

Файловый менеджер <#"552459.files/image010.gif">

Рисунок 10 - ViewFD

Он содержит аудио- и видеопроигрыватели (DirectShow, MCI), которые работают со своими списками (M3U, PLS), быстрый просмотр и слайд-шоу для файлов графики, редактирование изображений (с использованием геометрических эффектов, цветовых эффектов и настройки освещенности), группы изображений. Создание AVI файлов и HTML альбомов, калькулятор формул (с возможность построения графиков), просмотр и редактирование таблиц баз данных, выбор окон и заголовков, нажатия клавиш и содержимого экрана. Управление автозагрузкой и контроль запуска процессов, резервное копирование просмотр реестра (с возможностью расширенного поиска). Очистка дисков, директорий и файлов, предотвращающая накопление мусора и обеспечивающая конфиденциальность данных. Кодирование файлов, без контрольной суммы и заголовка (что значительно затрудняет несанкционированное обнаружение и декодирование). Просмотр дисков с возможностью создания образов и копирования фрагментов.

Проводник Windows

Проводник Windows - это приложение, реализующее графический интерфейс <#"552459.files/image011.gif">

Рисунок 11 - Q-Dir

Первый Q-Dir был тесно интегрирован с Проводником. Например, в нём использовались стандартные варианты просмотра панелей. Миниатюры, таблицы, списки, - все было взято из Проводника Windows.

Главными особенностями являются четырехпанельный интерфейс (есть возможность выбора другого количества панелей), мощный файловый фильтр, цветной фильтр (позволяет выбрать различные цвета для разных типов файлов), поддержка технологии Drag-and-drop <#"552459.files/image012.gif">

Рисунок 1 - Алгоритм работы функции menu().

Функция menu() представляет собой бесконечный цикл, в котором пользователь производит вызов нужной ему функции. При вводе пользователем символа ‘A’ - будет вызвана функция а(), предназначенная для заполнения дерева; ‘F’ - функция f(), предназначенная для поиска; ‘L’ - функция l(), предназначенная для вывода; ‘D’ - функция d(), предназначенная для удаления; ‘K’ - функция k(), предназначенная для отображения количества введённых элементов; при нажатии ‘Q’ происходит выход из программы; при чего-либо иного на экран выведется сообщение об ошибке и цикл повторится.

При вводе пользователем в любом из пунктов меню некорректной строки учитывается только первый введённый символ (Например, если пользователь вместо символа ввёл слово начинающееся с символа ‘a’ будет вызвана функция a().).

Функции используемые в программе:

РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

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

ТЕСТИРОВАНИЕ

На рисунках 12 - 14 представлена обработка, при вводе ошибочных данных.

Рисунок 12

Рисунок 13

Рисунок 14

На рисунке 15 показан вывод дерева на экран “боком”. На рисунке 16 - ввод элементов из файла и удаление с сохранением в файл, а также отбражение количества элементов. На рисунке 17 - функция поиска и удаление элемента с выводом на экран.

Рисунок 15

Рисунок 16

Рисунок 17

ВЫВОДЫ

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

ЛИТЕРАТУРА

1. Уолтер Сэвитч. С++ в примерах. Москва: Эком, 1997.

. В.А. Скляров. Язык С++ и объектно-ориентированное программирование. -Мн.: Выш. шк.,1997.

. Язык программирования Си. Москва: Производственно-внедренческий кооператив "И Н Т Е Р Ф Е Й С", 1988.

. Б.В. Керниган,Д.М. Ричи. ЯЗЫК С.

. В.А. Скляров. Программирование на языках Си и Си++. Мн.: Выш. шк.,1997.

. Страуструп Бьерн. Язык программирования Си++. М.: Софт,1999. (10 шт.).

. Шилд Герберт. - Самоучитель C++ / Герберт Шилдт . - СПб : BHV - Санкт-Петербург, 1997. - 511 с.

. Как программировать на С++ . Дж. Дейтел. Пер. В. Кузьменко . - М. : ЗАО "Издательство БИНОМ", 1998. - 1021 с. : ил.

. Visual C++ 6 Новые возможности для программистов. Ю. Тихомиров.- СПб.:БХВ-Санкт-Петербург,1998.-496 с.

. Основы алгоритмизации и программирования. Язык СИ. Е.М.Демидович.Мн.: “Бестпринт” 2003 г.

.Использование Visual C++ 6. Специальное издание. Грегори К.: Пер. с англ.-М.;СПб.;К.: Издательский дом “Вильямс”, 2001.-864 с.

ПРИЛОЖЕНИЕ

#include<stdio.h>

#include<math.h>

#include<ctype.h>

#include<string.h>

#include<stdlib.h>

#include <windows.h>buf[256];*rus(char *s) {CharToOem(s,buf); return buf;} tree//структура : содержание полей

{

int info;//код факультета (ключ)

int kaf;//количество кафедр

int pre;// количество преподавателей

char name[10]; //название факультета

char fam[10];// фамилия декана*left;// указатель на левого потомка*right;// указатель на правого потомка

};

//глобальные переменныые:*rt=NULL; //указатель на корень дереваcount=0; //счётчик элементовss[100]; //строка имени файла вывода для функцийsss[10]; //строка для функции “mist” (проверки корректности ввода)

int zn; //переменная для функции “mist”

char nam[10],fa[10]; //переменные для передачи данных в функцию “add”ka,pr; //*add(tree *root,tree *r, int c) //функция "add" - добавление

//элемента

{if(!r)

{r=new tree;(!r){printf(rus("Нет памяти\n")); exit(100);}>left=NULL;>right=NULL;>info=c;(r->name,nam);(r->fam,fa);>kaf=ka;>pre=pr;(!root) return r;(c<root->info) root->left=r;root->right=r;r;

}(c<r->info) add(r,r->left,c);add(r,r->right,c);root;

}*find(tree *root,int key) //функция "find" - поиск элемента по ключу

{if(root==NULL) return root;(root->info!=key)

{if(key<root->info) root=root->left;root=root->right;(root==NULL) break;

}root;

}view(tree *r,bool b) //функция "view" - вывод на экран

//содержимого узла дерева

{if(b)

{printf(rus("номер факультета : %d\n"),r->info);

printf(rus("название факультета : %s\n"),r->name);

printf(rus("фамилия декана : %s\n"),r->fam);(rus("количество кафедр : %d\n"),r->kaf);(rus("количество преподавателей: %d\n"),r->pre);

}

}*del(tree *root,int key,bool b) //функция "del" - удаление узла дерева,

// может использовать функцию "view"

{tree *p,*p2;

if(!root) return root;(root->info==key)

{if(root->left==root->right)

{printf(rus("Этот элемент удалён\n"));

view(root,b);-;root;NULL;

}(root->left==NULL)

{p=root->right;(rus("Этот элемент удалён\n"));(root,b);-;root;p;

}(root->right==NULL)

{p=root->left;(rus("Этот элемент удалён\n"));(root,b);-;root;p;

}

//else

{p2=root->right;=p2;(p->left) p=p->left;>left=root->left;(rus("Этот элемент удалён\n"));(root,b);-;root;p2;

}

}(root->info<key) root->right=del(root->right,key,b);root->left=del(root->left,key,b);root;

} mist(bool b) //функция "mist" - проверка ввода на корректность

{zn=0;le=strlen(sss);k=0;(b)

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

{(!isdigit(sss[i])) k++;zn+=(sss[i]-48)*pow(10,le-i-1);

}k;

{(!isalpha(sss[i])) k++;

}

return k;

}a() //функция "a" - предназначена для заполнения дерева, может

// использовать функции "add", "find" и "mist"

{int inf;c;z;v=1;

{z=2;(rus("Ввод\n1 - с клавиатуры\n0 - из файла\n"));("%s",&sss);[1]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));z=zn;

}while((v)&&((z<0)||(z>1)));(z)

{while(1)

{v=1;

{c=2;(rus("Выбери\n1 - ввод\n0 - стоп\n"));("%s",&sss);[1]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));c=zn;

}while((v)&&((c<0)||(c>1)));(c)

{v;*r=NULL;

{do

{v=1;(rus("Введите \nномер

факультета \n"));("%s",&sss);[9]='\0';=mist(1);(v) printf(rus("Ошибка

ввода\n"));inf=zn;

}while(v);=find(rt,inf);(r) printf(rus("Такой элемент уже

есть\n"));break;

}while(1);

{v=1;(rus("название факультета \n"));

scanf(rus("%s"),&sss);[9]='\0';=mist(0);(v) printf(rus("Ошибка ввода\n"));strcpy(nam,sss);

}while(v);

{v=1;(rus("фамилия декана \n"));(rus("%s"),&sss);[9]='\0';=mist(0);(v) printf(rus("Ошибка ввода\n"));strcpy(fa,sss);

}while(v);

do

{v=1;(rus("количество кафедр \n"));

scanf("%s",&sss);[9]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));ka=zn;

}while(v);

do

{v=1;(rus("количество

преподавателей \n"));

scanf("%s",&sss);[9]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));pr=zn;

}while(v);=add(rt,rt,inf);(rt)count++; return;

}return;

}

}

{*f;(true)

{char s[100];(rus("Введите имя файла\n"));("%s",&s);[99]=’\0’;=fopen(s,"r");(!f) {printf(rus("Ошибка чтения файла,

введите другое имя\n"));return;}

else break;

}

{fscanf(f,"%d",&inf);(f,rus("%s"),&nam);(f,rus("%s"),&fa);(f,"%d",&ka);(f,"%d",&pr);=add(rt,rt,inf);(rt)count++;

}while(!feof(f));

fclose(f);

}

}f() //функция "f" - предназначена для поиска узла дерева, может

// использовать функции "find", "view" и "mist"

{if(!rt){printf(rus("Пусто\n")); return;}*r;key;v=1;

do

{printf(rus("Введите число (номер факультета)\n"));

scanf("%s",&sss);[9]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));key=zn;

}while(v);=find(rt,key);(r)

{(r,1);

}printf(rus("Элемент не найден\n"));

}

void inorder(tree *root) //функция "inorder" - предназначена для вывода //дерева в симметричном порядке (на экран),

//использует функцию "view"

{if(!root)return;(root->left);(root->info)

{(root,1);(rus("\n"));

}(root->right);

} preorder(tree *root) //функция "preorder" - предназначена для вывода//дерева в прямом порядке (на экран),//использует функцию "view"

{if(!root)return;(root->info)

{(root,1);(rus("\n"));

}(root->left);(root->right);

}postorder(tree *root) //функция "postorder" - предназначена для вывода //дерева в обратном порядке (на экран),

//использует функцию "view"

{if(!root)return;(root->left);(root->right);(root->info)

{(root,1);(rus("\n"));

}

//вывода дерева боком(на экран)

{(root->right!=NULL) print(root->right,level+1);(int i=0;i<level;i++) printf(rus(" "));(rus("%d\n"),root->info);(root->left!=NULL) print(root->left,level+1);

}finorder(tree *root) //функция "finorder" - предназначена для записи // в файл всего дерева либо его узла

{if(!root)return;*e;=fopen(ss,"a");(root->left);(root->info)

{fprintf(e,rus("%d\n"),root->info);(e,rus("%s\n"),root->name);(e,rus("%s\n"),root->fam);(e,rus("%d\n"),root->kaf);(e,rus("%d\n"),root->pre);

}(root->right);(e);

}l() //функция "l" - предназначена для вывода дерева, может использовать

// функции "print", "inorder", "preorder", "postorder" и "finorder"

{char s[2];(!rt){printf(rus("Пусто\n")); return;}(true)

{printf(rus("Введите \nВывод на экран\nB - боком,\nS - симметрично,\nW - сверху,\nH - снизу\nF - Вывод в файл\n"));(stdin,"%s",&s);[1]='\0';

*s=toupper(*s);(*s)

{case 'B':{printf(rus("\n")); print(rt,0);(rus("\n")); return;}'S':{inorder(rt); printf(rus("\n")); return;}'W':{preorder(rt); printf(rus("\n"));return;}'H':{postorder(rt);printf(rus("\n"));return;}'F':

{printf(rus("Введите имя файла\n"));("%s",&ss);[99]='\0';(rt);;

}: printf(rus("Ошибка ввода\n"));

}

}

}d() //функция "d" - предназначена для удаления, может

//использовать функции "find", "del", "finorder" и "mist"

{if(!rt){printf(rus("Пусто\n")); return;}*r=NULL;z;v=1;

{z=2;(rus("Вывод\n1 - на экран\n0 - в файл\n"));("%s",&sss);[1]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));z=zn;

}while((v)&&((z<0)||(z>1)));(z)

{int key;v=1;

do

{printf(rus("Введите число (номер факультета)\n"));

scanf("%s",&sss);[9]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));key=zn;

}while(v);=find(rt,key);(!r) {printf(rus("Элемент не найден\n"));return;}(rt->info==key) { rt=NULL; count=0;(rus("Все элементы удалены\n")); }

else rt=del(rt,key,1);

}

{*r=NULL;key;(rus("Введите имя файла\n"));("%s",&ss);[99]=’\0’; v=1;

{printf(rus("Введите число (номер факультета)\n"));

scanf("%s",&sss);[9]='\0';=mist(1);(v) printf(rus("Ошибка ввода\n"));key=zn;

}while(v);=find(rt,key);(!r) {printf(rus("Элемент не найден\n"));return;}(rt->info==key)

{(rt);=NULL; count=0;(rus("Все элементы удалены\n"));

}

{*e;=fopen(ss,"a");(e,rus("%d\n"),r->info);(e,rus("%s\n"),r->name);(e,rus("%s\n"),r->fam);(e,rus("%d\n"),r->kaf);(e,rus("%d\n"),r->pre);=del(rt,key,0);(e);

}

}

}k() //функция "k" - вывод колличества элементов дерева

{if(!count) printf(rus("Пусто\n"));printf(rus("Количество элементов = %d\n"),count);

}menu()//функция "menu"

{(true)

{s[2];(rus("Введите \nA - добавить,\nF - найти,\nD - удалить,\nL - вывод дерева,\nK - количество элементов, \nQ - выход\n"));(stdin,"%s",&s);[1]='\0';

*s=toupper(*s);(*s)

{case'A': a();break;'F': f();break;'L': l();break;'D': d();break;'K': k();break;'Q': exit(100);: printf(rus("Ошибка ввода\n"));break;

}

}

} main()//функция "main" : вызывает функцию "menu"

{menu();}