|
#include <vcl.h>
#pragma hdrstop
#include <iostream.h>
#include <math.h>
#include <fstream.h>
#include <windows.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
struct Direction;
//Основная запись
struct Direction {
Direction * left;
Direction * right;
char DWords;
int DCount;
};
typedef Direction * TypeLinkD;//ссылка на запись
typedef char Str[30];
//Обнуление массива(либо инициализация)
void IintMassive(TypeLinkD * Dmassive){
for (int i=0;i<100;i++)
Dmassive[i]=NULL;
};
//Пр вставки информации о букве в массив
void PutMassive (char DWords , TypeLinkD * Dmassive){
int i=0;
bool detect=false; //флаг для проверки того, что буква была занесена в массив и если не найдем, то добавим ее в конец массива
while (Dmassive[i]!=NULL){ //пока не достигнут конец массива проверяем, существует ли такая буква.
if (Dmassive[i]->DWords==DWords){
Dmassive[i]->DCount++; //если нашли, то увеличиваем поле с количеством этой буквы в тексте
detect=true;
}
i++;
}
if (detect!=true)
{ Dmassive[i]=new Direction;
Dmassive[i]->DWords=DWords;
Dmassive[i]->DCount=1;
Dmassive[i]->left=NULL;
Dmassive[i]->right=NULL;
}
}
//Процедура сортировки массива по убыванию, для того, чтобы объеденить два последнидних наименьших элемента
void SortMassive(TypeLinkD * Dmassive){
int i=0;
TypeLinkD z;
for (int o=0;o<100;o++){
while (Dmassive[i]!=NULL){
if ((Dmassive[i+1]!=NULL)&&(Dmassive[i]->DCount<Dmassive[i+1]->DCount)){
z=Dmassive[i];
Dmassive[i]=Dmassive[i+1];
Dmassive[i+1]=z;
}
i++;
}
i=0;}
}
//Формирование Самого дерева
TypeLinkD CreateTreeHaffman(TypeLinkD * Dmassive) {
int i=0;
Direction * z = NULL;
SortMassive(Dmassive); //сортировка массива по убыванию
while (Dmassive[1]!=NULL){ //пока не останется только 1 элемент в массиве и эелемнт не пустой
while (Dmassive[i]!=NULL){ //Подсчет количества букв для определния распложения двух наименьших элементов
i++;
}
z=new Direction; //объединяем (добавляем слева и справа) 2 последних элемента в один элемент (корень маленького дерева )
z->left=Dmassive[i-2];
z->right=Dmassive[i-1];
z->DCount=Dmassive[i-2]->DCount+Dmassive[i-1]->DCount;
Dmassive[i-1]=NULL; //стираем последний элемент массива
Dmassive[i-2]=z; // Перезаписываем последний элемент массива новым сформированным
i=i-2;
while ((i>=1)&&(Dmassive[i]->DCount>Dmassive[i-1]->DCount)){
z=Dmassive[i-1];
Dmassive[i-1]=Dmassive[i];
Dmassive[i]=z;
i--;
}
i=0;
}
return Dmassive[0]; //возвратили корень дерева или null если элемент пуст, нет ни одного символа
}
//Вывод символа и его кода
void WriteHaffman(TypeLinkD root, char * Str){
char left [30],right [30]; // в экземпляры функции будем каждый раз передавать новый путь в зависимости от выбранного направления похода - если вправо, то прибавляем к коду , который передается с самого верха 0 , если влево , то 1.
if (root->left==root->right){ //поиск листа дерева, если нашли выводим символ и код, если нет то копируем в массив новый путь и добавляем код в зависимости от его расположения справа или слева
cout<<root->DWords<<' '<<" "<<Str<<"\n";}
else {
int i=0;
while (Str[i]!=NULL){
left[i]=Str[i];
right[i]=Str[i];
i++;
}
left[i]='1'; //кодировка левой вестви
right[i]='0'; //кодировка правой ветви
left[i+1]=NULL;
right[i+1]=NULL;
WriteHaffman(root->left,left);
WriteHaffman(root->right,right);
}
return;
}
void main(){
int i=0;
char DWords;
char file [30];
int MAinkey;
do{
cout<<"\n 1: haffman 2: about author 3:exit ";
cin>>MAinkey;
if(MAinkey==1){
cout<<"\n insert filename: ";
cin>>file;
TypeLinkD root=NULL;
TypeLinkD Dmassive [100] ;
IintMassive(Dmassive);
ifstream GETFILE;
GETFILE.open(file);
if(!GETFILE){cout<<"\n file "<<file<<" not found "; system("pause");exit(1);}
while (!GETFILE.eof())
{
GETFILE>>DWords;
if (GETFILE.good())
PutMassive(DWords,Dmassive);
}
root=CreateTreeHaffman(Dmassive);
cout<<"\n symbol | code "<<"\n";
WriteHaffman(root,"");
cout<<"\n "<<system("pause");
}
if(MAinkey==2){
cout<<"\n LOL ";
}
}while(MAinkey!=3);
}
|
Линейный вид
