кодировка Хаффмана

#include <iostream>
#include <vector>
#include <string>
#include <climits>
 
using namespace std;
struct node
{
    node * leftChild;
    node * rightChild;
    double frequency;
    string content;
    string code;
 
 
};
 
vector<node> nodeArray;// Use nodeArray to record all the nodes that may be created in the whole process
 
node  extractMin()
{
    double temp = (double) INT_MAX;
    vector<node>::iterator i1,pos;
    for(i1 = nodeArray.begin(); i1!=nodeArray.end(); i1++)
    {
 
        if(temp>(*i1).frequency)
        {
            pos = i1;
            temp = (*i1).frequency;
        }
    }
 
    node tempNode = (*pos);
    nodeArray.erase(pos);
 
    return tempNode;
}
node getHuffmanTree()
{
    while(!nodeArray.empty())
    {
 
 
        node * tempNode = new node;
        node * tempNode1 = new node;
        node * tempNode2 = new node;
        *tempNode1 = extractMin();
        *tempNode2 = extractMin();
 
 
        tempNode->leftChild = tempNode1;
        tempNode->rightChild = tempNode2;
        tempNode->frequency = tempNode1->frequency+tempNode2->frequency;
        nodeArray.push_back(*tempNode);
        if(nodeArray.size() == 1)//only the root node exsits
        {
            break;
        }
    }
    return nodeArray[0];
}
 
 
void BFS(node * temproot,string s)
{
    node * root1 = new node;
    root1 = temproot;
 
    root1->code = s;
    if(root1 == NULL)
    {
 
    }
    else if(root1->leftChild == NULL && root1->rightChild == NULL)
    {
 
        cout<<"the content is "<<root1->content<<endl;
        cout<<"and its corresponding code is "<<root1->code<<endl;
    }
    else
    {
 
        root1->leftChild->code = s.append("0");
        s.erase(s.end()-1);
        root1->rightChild->code = s.append("1");
        s.erase(s.end()-1);
 
 
        BFS(root1->leftChild,s.append("0"));
        s.erase(s.end()-1);
        BFS(root1->rightChild,s.append("1"));
        s.erase(s.end()-1);
    }
 
}
 
 
 
 
void getHuffmanCode()
{
    int size,i;
    double tempDouble;
    string tempString = "";
 
    cout<<"Пожалуйста, введите количество данных, которые вы хотите закодировать!"<<endl;
    cin>>size;
 
    for(i = 0; i<size; i++)
    {
        cout<<"Пожалуйста, введите то, что вы хотите кодировать и их частоты появления!"<<endl;
        node tempNode;
        cin>>tempString;
        cin>>tempDouble;
 
 
        tempNode.frequency = tempDouble;
        tempNode.content = tempString;
        tempNode.leftChild = NULL;
        tempNode.rightChild = NULL;
        nodeArray.push_back(tempNode);
    }
 
 
    node root = getHuffmanTree();
 
 
    BFS(&root,"");
 
}
 
 
int main()
{
 
    vector<int> test;
    test.push_back(1);
    test.push_back(2);
    test.push_back(3);
    test.push_back(4);
    vector<int>::iterator i1 = test.begin();
    test.erase(i1);
 
    setlocale(LC_ALL,"Russian");
    getHuffmanCode();
    return 0;
}

// ConsoleApplication3.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
using namespace std;
 
long double p[256];
long double p2[256];
int c[256][256]; // массив с кодами
int l[256]; // длина
long double Q[256];
 
int up(int n, double q)
{
    int i;
    for (i = n - 2; i >= 1; i--)
    {
        if (p[i-1] <= q)
        {
            p[i] = p[i-1];
        }
        else
        {
            break;
        }
    }
    p[i] = q;
    return i;
}
//-------------------------------
int down(int n, int j)
{
    int i, z, l1;
    int s[16];
 
    for (z = 0; z<16; z++)
    {
        s[z] = c[j][z];
    }
    l1 = l[j];
    for (i = j; i <= n - 2; i++)
    {
        for (z = 0; z<16; z++)
        {
            c[i][z] = c[i+1][z];
        }
        l[i] = l[i+1];
    }
    for (z = 0; z<16; z++)
    {
        c[n-1][z] = s[z];
        c[n][z] = s[z];
    }
    c[n-1][l1] = 0;
    c[n][l1] = 1;
    l[n-1] = l1 + 1;
    l[n] = l1 + 1;
 
    return 0;
}
//-------------------------------
int huffman(int n)
{
    double q;
    int j;
    if (n == 1)
    {
        c[0][0] = 0;
        l[0] = 1;
        c[1][0] = 1;
        l[1] = 1;
    }
    else
    {
        q = p[n-1] + p[n];
        j = up(n, q);
        huffman(n - 1);
        down(n, j);
    }
    return 0;
}
 
void shennon(int n)
{
    //p[0] = 0; 
    Q[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        Q[i] = Q[i - 1] + p[i-1];
        l[i] = (int)((-1) * (log10(p[i-1]) / log10(2)));
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= l[i]+1; j++) // <= или < проверить!!!
        {
            Q[i - 1] = Q[i - 1] * 2;
            c[i][j-1] = (int)Q[i - 1];
            if (Q[i - 1] > 1) Q[i - 1] = Q[i - 1] - 1;
        }
    }
}
 
int Med(int L, int R)
{
    float Sl = 0;
    for (int i = L; i < R; i++)
    {
        Sl += p[i];
    }
    float Sr = p[R];
    int m = R;
 
    while (fabs(Sr - Sl)>fabs(Sr + p[m - 1] - (Sl - p[m - 1])))
    {
        m--;
        Sl -= p[m];
        Sr += p[m];
    }
    return m - 1;
}
 
int Fano(int L, int R, int k)
{
    int m = 0;
    if (L<R)
    {
        k = k + 1;
        m = Med(L, R);
        for (int i = L; i <= R; i++)
        {
            if (i <= m) { c[i][k] = 0; l[i] += 1; }
            else { c[i][k] = 1; l[i] += 1; }
 
        }
        Fano(L, m, k);
        Fano(m + 1, R, k);
    }
 
    return 0;
}
 
int Gil(int n)
{
    float pr = 0;
    for (int i = 0; i < n; i++)
    {
        Q[i] = pr + p[i] / 2;
        pr += p[i];
        l[i] = ((-1 * (log(p[i]) / log(2.0f))) + 0.9999999f) + 1.0f;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < l[i]; j++)
        {
            Q[i] = Q[i] * 2;
            c[i][j] = Q[i];
            if (Q[i] > 1) Q[i] = Q[i] - 1;
        }
    }
    return 0;
}
 
char *ALF;
int ALFCount = 0;
 
void BigPrintf(bool sh)
{
    cout << "\n---------------------------------------------------------------------------|";
    cout << "\n     Символ    |     Вероятность     |   Кодовое слово   |      Длина      |";
    cout << "\n------------ --|---------------------|-------------------|-----------------|";
    cout << "\n               |                     |                   |                 |\n";
 
    for (int i = 0; i < ALFCount; i++)
    {
        printf("%10c", ALF[i]);
        cout << "     |          ";
        printf("%3.3f", p2[i]);
        cout << "      |      ";
 
        int k = 7;
        for (int j = 0; j < l[i + ((sh) ? 1 : 0)] + (sh) ? 1 : 0; j++)
        {
            cout << c[i + ((sh) ? 1 : 0)][j];
            k--;
        }
        while (k > 0)
        {
            cout << " "; k--;
        }
        cout << "      |   ";
 
        printf("%7d", l[i + ((sh) ? 1 : 0)] + ((sh) ? 1 : 0));
        cout << "       |";
 
        cout << "\n";
    }
    cout << "               |                     |                   |                 |\n";
    cout << "---------------------------------------------------------------------------|";
 
 
    cout << "\n";
}
 
void ReadFile()
{
    setlocale(LC_ALL, "Russian");
    errno_t err;
    FILE *text;
    // Open for read (will fail if file "crt_fopen_s.c" does not exist)
    err = fopen_s(&text, "test.txt", "r");
 
    int count;
 
    //text = fopen("test.txt", "r");
    char *charArray;
    fseek(text, 0, SEEK_END);
    count = ftell(text);
    rewind(text);
 
 
    charArray = new char[count + 1];
    fread(charArray, 1, count, text);
    charArray[count] = 0;
 
 
    ALF = new char[count];
 
 
    int * ACount = new int[count];
    for (int i = 0; i < count; i++)
    {
        ACount[i] = 0;
    }
    for (int i = 0; i < count; i++)
    {
        bool newB = true;
        for (int j = 0; j < ALFCount; j++)
        {
            if (charArray[i] == ALF[j])
            {
                ACount[j]++;
                newB = false;
                break;
            }
        }
        if (newB)
        {
            ALF[ALFCount] = charArray[i];
            ACount[ALFCount]++;
            ALFCount++;
        }
    }
 
    for (int i = 0; i < 6; i++)
    {
        cout << ACount[i] << "  ";
        p[i] = (float)(ACount[i]) / count;
        cout << p[i] << "  ";
    }
 
    for (int i = 0; i < 256; i++)
    {
        p2[i] = p[i];
    }
 
    system("CLS");
}
 
void Clear()
{
    for (int i = 0; i < 256; i++)
    {
        l[i] = 0;
        p[i] = p2[i];
        for (int j = 0; j < 256; j++)
        {
            c[i][j] = 0;
        }
    }
}
 
float NormalLine(int n, long double *p, int *l)
{
    float sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += p[i] * (float)l[i];
    }
    return sum;
}
 
float NormalLineSh(int n, long double *p, int *l)
{
    float sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += p[i] * (float)(l[i+1]+1);
    }
    return sum;
}
 
float Entropia(long double *p, int n)
{
    float sum = 0;
    for (int i = 0; i < n; i++) sum -= p[i] * (log(p[i]) / log(2.0f));
    return sum;
}
 
int main()
{   
    ReadFile();
 
    huffman(ALFCount - 1);
    cout << "  Хаффман\n\n";
    BigPrintf(false);
    cout << "Средняя длина : " << NormalLine(ALFCount, p2, l) << "\n\n\n";
    Clear();
    
    shennon(ALFCount);
    cout << "  Шеннон\n\n";
    BigPrintf(true);
    cout << "Средняя длина : " << NormalLineSh(ALFCount, p2, l) << "\n\n\n";
    Clear();
 
    Fano(0, ALFCount - 1, -1);
    cout << "  Фано\n\n";
    BigPrintf(false);
    cout << "Средняя длина : " << NormalLine(ALFCount, p2, l) << "\n\n\n";
    Clear();
 
    Gil(ALFCount);
    cout << "  Гилберта Мура\n\n";
    BigPrintf(false);
    cout << "Средняя длина : " << NormalLine(ALFCount, p2, l) << "\n\n\n";
    Clear();
 
    cout << "Энтропия: " << Entropia(p2, ALFCount) << "\n\n\n";
    
    system("PAUSE");
    return 0;   
}

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <errno.h>
 
using namespace std;
 
 
long double p[256];
long double p2[256];
int c[256][256]; // массив с кодами
int l[256]; // длина
long double Q[256];
 
int up(int n, double q)
{
    int i;
    for (i = n - 2; i >= 1; i--)
    {
        if (p[i-1] <= q)
        {
            p[i] = p[i-1];
        }
        else
        {
            break;
        }
    }
    p[i] = q;
    return i;
}
//-------------------------------
int down(int n, int j)
{
    int i, z, l1;
    int s[16];
 
    for (z = 0; z<16; z++)
    {
        s[z] = c[j][z];
    }
    l1 = l[j];
    for (i = j; i <= n - 2; i++)
    {
        for (z = 0; z<16; z++)
        {
            c[i][z] = c[i+1][z];
        }
        l[i] = l[i+1];
    }
    for (z = 0; z<16; z++)
    {
        c[n-1][z] = s[z];
        c[n][z] = s[z];
    }
    c[n-1][l1] = 0;
    c[n][l1] = 1;
    l[n-1] = l1 + 1;
    l[n] = l1 + 1;
 
    return 0;
}
//-------------------------------
int huffman(int n)
{
    double q;
    int j;
    if (n == 1)
    {
        c[0][0] = 0;
        l[0] = 1;
        c[1][0] = 1;
        l[1] = 1;
    }
    else
    {
        q = p[n-1] + p[n];
        j = up(n, q);
        huffman(n - 1);
        down(n, j);
    }
    return 0;
}
 
char *ALF;
int ALFCount = 0;
 
void BigPrintf(bool sh)
{
    cout << "\n---------------------------------------------------------------------------|";
    cout << "\n     Символ    |     Вероятность     |   Кодовое слово   |      Длина      |";
    cout << "\n------------ --|---------------------|-------------------|-----------------|";
    cout << "\n               |                     |                   |                 |\n";
 
    for (int i = 0; i < ALFCount; i++)
    {
        printf("%10c", ALF[i]);
        cout << "     |          ";
        printf("%3.3f", p2[i]);
        cout << "      |      ";
 
        int k = 7;
        for (int j = 0; j < l[i + ((sh) ? 1 : 0)] + (sh) ? 1 : 0; j++)
        {
            cout << c[i + ((sh) ? 1 : 0)][j];
            k--;
        }
        while (k > 0)
        {
            cout << " "; k--;
        }
        cout << "      |   ";
 
        printf("%7d", l[i + ((sh) ? 1 : 0)] + ((sh) ? 1 : 0));
        cout << "       |";
 
        cout << "\n";
    }
    cout << "               |                     |                   |                 |\n";
    cout << "---------------------------------------------------------------------------|";
 
 
    cout << "\n";
}
 
void ReadFile()
{
    setlocale(LC_ALL, "Russian");
 
    errno_t err;
    FILE *text;
    // Open for read (will fail if file "crt_fopen_s.c" does not exist)
    err = fopen_s(&text, "test.txt", "r");
 
    int count;
 
    //text = fopen("test.txt", "r");
    char *charArray;
    fseek(text, 0, SEEK_END);
    count = ftell(text);
    rewind(text);
 
 
    charArray = new char[count + 1];
    fread(charArray, 1, count, text);
    charArray[count] = 0;
 
 
    ALF = new char[count];
 
 
    int * ACount = new int[count];
    for (int i = 0; i < count; i++)
    {
        ACount[i] = 0;
    }
    for (int i = 0; i < count; i++)
    {
        bool newB = true;
        for (int j = 0; j < ALFCount; j++)
        {
            if (charArray[i] == ALF[j])
            {
                ACount[j]++;
                newB = false;
                break;
            }
        }
        if (newB)
        {
            ALF[ALFCount] = charArray[i];
            ACount[ALFCount]++;
            ALFCount++;
        }
    }
 
    for (int i = 0; i < 6; i++)
    {
        cout << ACount[i] << "  ";
        p[i] = (float)(ACount[i]) / count;
        cout << p[i] << "  ";
    }
 
    for (int i = 0; i < 256; i++)
    {
        p2[i] = p[i];
    }
 
    system("CLS");
}
 
void Clear()
{
    for (int i = 0; i < 256; i++)
    {
        l[i] = 0;
        p[i] = p2[i];
        for (int j = 0; j < 256; j++)
        {
            c[i][j] = 0;
        }
    }
}
 
float NormalLine(int n, long double *p, int *l)
{
    float sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += p[i] * (float)l[i];
    }
    return sum;
}
 
float NormalLineSh(int n, long double *p, int *l)
{
    float sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += p[i] * (float)(l[i+1]+1);
    }
    return sum;
}
 
float Entropia(long double *p, int n)
{
    float sum = 0;
    for (int i = 0; i < n; i++) sum -= p[i] * (log(p[i]) / log(2.0f));
    return sum;
}
 
int main()
{
    ReadFile();
 
    huffman(ALFCount - 1);
    cout << "  Хаффман\n\n";
    BigPrintf(false);
    cout << "Средняя длина : " << NormalLine(ALFCount, p2, l) << "\n\n\n";
    Clear();
    cout << "Энтропия: " << Entropia(p2, ALFCount) << "\n\n\n";
 
    system("PAUSE");
    return 0;
}

    errno_t err;
    FILE *text;
    // Open for read (will fail if file "crt_fopen_s.c" does not exist)
    err = fopen_s(&text, "test.txt", "r");