Форум программистов, компьютерный форум CyberForum.ru

Создание строки символов из элементов дерева, проходя через него - C++

Восстановить пароль Регистрация
 
BlindDespair
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 18
19.12.2013, 01:49     Создание строки символов из элементов дерева, проходя через него #1
В общем осталось мне в методе кодирования Хаффмана для курсовой работы реализовать самую малость(битовые операции делать не нужно, главное построить сам алгоритм). Нужно мне из символов 0 и 1, которые я вижу проходя по дереву, создать строку, то есть символ, например, а кодируется 0, b - 10, c - 11, функция find выводит на экран 0 и 1 для каждого символа в перевернутом виде, то есть а - 0, b - 01, c - 11, мне нужно создать строку из этих 0 и 1 для каждого символа, чтобы я мог её записать, и перевернуть ещё, чтобы в правильном порядке было. Подскажите, пожалуйста, как это сделать?
Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <conio.h>
struct Haffman{
        unsigned char ch;
        float freq; 
        char code[255]; 
        Haffman *left;
        Haffman *right;
        int bincode;
}; 
Haffman *makeTree(Haffman *psym[],int k){
    Haffman *node;
    node = (Haffman*)malloc(sizeof(Haffman));
    node->freq = psym[k-1]->freq+psym[k-2]->freq;
    node->code[0]=0;
    node->left = psym[k-1];
    node->left->bincode = 1;
    node->right = psym[k-2];
    node->right->bincode = 0;
 
    if(k == 2){
        return node;
    }
    else{ 
        for(int i = 0;i < k;i++){
            if (node->freq>psym[i]->freq){   
                for(int j = k-1;j > i;j--){
                    psym[j] = psym[j-1];                                  
                }
                psym[i] = node;
                break;
            }
        }     
    }
    return makeTree(psym,k-1);
}
void view1(Haffman *node){
 if(node == NULL)return(void) printf("a\n") ;
 printf ("%d \n",(int)node->bincode);
 view1(node->left);
 view1(node->right);
} 
 
 
int find(Haffman *node, char c){
    if(node == NULL )return false;
    if( node->ch  == c ) {
        printf("%d \n",node->bincode);
        return 1;
    }
    if(find(node->left,c) || find(node->right,c)){
        if(node->bincode!=-1)
            printf("%d \n",node->bincode);
        return 1;
    }
    else{
        return 0;
    }
} 
 
int main (){
    FILE *fp,*fp2,*fp3; 
    fp=fopen("input.txt","r"); 
    fp2=fopen("output.bin","wb");
 
    int ReadingInfFile;  
    int k = 0; 
    int kk = 0;
    int AmountOfSimbol[256] = {0};
    Haffman simbols[256] = {0}; 
    Haffman *psym[256]; 
    float SumOfFreq = 0;
    char j=0;
    if(fp == NULL){
        puts("Г”Г*éë Г*ГҐ îòêðûò!");
        return 0;
    }
 
    Haffman *symbols = (Haffman*)malloc(k*sizeof(Haffman));
    Haffman **psum = (Haffman**)malloc(k*sizeof(Haffman*));
    while((ReadingInfFile = fgetc(fp))!=EOF){       
        for(int j = 0; j < 256; j++){
            if (ReadingInfFile == simbols[j].ch){
                AmountOfSimbol[j]++;
                kk++;               
                break;
            }
            if (simbols[j].ch == 0){
                simbols[j].ch = (unsigned char)ReadingInfFile;
                AmountOfSimbol[j]=1;
                k++; kk++;
                break;
            }           
        }       
    }
 
    for(int i = 0;i < k;i++){
        simbols[i].freq = (float)AmountOfSimbol[i]/kk;
    }
    
    for(int i = 0;i < k;i++){ 
        psym[i] = &simbols[i];
    }
    Haffman bufer;
    for(int i = 1;i<k;i++){
        for(int j = 0;j > k-1;j++){
            if(simbols[j].freq>simbols[j+1].freq){
                bufer = simbols[j];
                simbols[j] = simbols[j+1];
                simbols[j+1] = bufer;
            }
        }
    }
    for(int i = 0;i<k;i++){
            SumOfFreq+=simbols[i].freq;    
            printf("Íîìåð ñèìâîëГ* Гў ASCII:%d  Г—Г*ñòîòГ* âñòðå÷Г*åìîñòè:%.2f\tГ“Г*ГЁГЄГ*ëüГ*ûé ñèìâîë:%c\t\n",simbols[i].ch,simbols[i].freq,psym[i]->ch);
    }
    printf("\nÊîëè÷åñòâî ñèìâîëîâ Гў ГІГҐГЄГ±ГІГҐ:%d\tÑóììГ* Г·Г*ñòîò âñòðå÷Г*åìîñòè:%.2f\n",kk,SumOfFreq);
    Haffman *root = makeTree(psym,k);
    root->bincode = -1;
   view1(root);
    rewind(fp);
    printf("\n===============\n");
    while((ReadingInfFile = fgetc(fp)) != EOF){
                           find(root,ReadingInfFile);
                                for(int i = 0;i<k;i++){
                                        if(ReadingInfFile == simbols[i].ch){
                                        fprintf(fp2,"%d",simbols[i].bincode);
                                        }
                                }
    }
    fclose(fp2);
    fclose(fp);
    getch();
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2013, 01:49     Создание строки символов из элементов дерева, проходя через него
Посмотрите здесь:

Создание дерева C++
Если в строке есть элемент, равный среднему арифметическому элементов этой строки, то вставьте после него строку, состоящую из этих элементов C++
C++ Если в строке есть элемент, равный среднему арифметическому элементов этой строки, то вставьте после него строку, состоящую из этих элементов
создание дерева и подсчте элементов C++
C++ Удаление из строки повторяющихся элементов (через функцию)
C++ Получить из строк новую строку, содержащюю первые N1 символов строки S1 и последнии N2 символов строки S2
Считывание через ifstream строки состоящей из чисел и символов из файла C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru