c++ - 哪种方法更适合霍夫曼编码我想用它们的频率读取字符

Question

两个循环从字符串中读取字符

void ReadCharWithFreq(string str){ 
    int n = str.size();  
    int count = 0;

    // loops to read all char from string and frequency
    for(int i = 0;i<n;i++){
        for(int x =0;x<n;x++ ){
            if(str[i]==str[x]){
                count++;
            }
        }       

        //enqueue char with frequency
        enqueue(str[i],count);
        count=0;
    }
} //end of function

相同的功能不同的方法使用堆数组 freq[] 和 memeset我不明白 memeset(array,int,int) 的功能

void ReadCharWithFreq(string str){ 

    int n = str.size(); 
    int SIZE = 40;
    int spf=0;

    memset(freq, 0, sizeof(freq));

    for (int i = 0; i < n; i++){
        freq[str[i] - 'a']++; 
    }

    for (int i = 0; i < n; i++) { 
        if (freq[str[i] - 'a'] != 0) { 
            cout << str[i] <<" "<< freq[str[i] - 'a'] << " - >"; 
            enqueue(str[i], freq[str[i] - 'a']);
            freq[str[i] - 'a'] = 0;
        } 
    } 
} //end of function

以上哪种算法更准确、更高效我想从字符串中读取所有字符并计算它们的出现/频率

Answer 1

我会使用一个 std::array，其空间足以容纳您可能遇到的所有字符数:

#include <array>
#include <limits>

constexpr size_t ArrSize = std::numeric_limits<unsigned char>::max()+1;

std::array<unsigned char, ArrSize> ReadCharWithFreq(const std::string& str){
    std::array<unsigned char, ArrSize> freq{};
    for(unsigned char ch : str)
        freq[ch]++;
    return freq;
}

示例用法:

#include <iostream>
#include <iomanip>
#include <vector>

int main(int argc, char* argv[]) {
    std::vector<std::string> args(argv+1, argv+argc);

    for(const auto& str : args) {
        auto result = ReadCharWithFreq(str);

        for(size_t i=0; i<ArrSize; ++i) {
            if(result[i]) {
                std::cout << std::setw(3) << i << " " << static_cast<char>(i) << " " << static_cast<int>(result[i]) << "\n";
                // enqueue here? 
            } 
        }
    }
}