Fast Morse Code Encode And Decode

一.写在前面

现在UV段业余无线电已经玩够了，需要转战SW段了，要想在7050kHz上与HAM交流的话，就要学会普通话和常用标准缩略语；如果想在7030kHz上与HAM通讯的话就要熟练掌握通用的摩尔斯电码。

二.原理简介

首先通过两个数组分别保存字符摩尔斯编码和数字摩尔斯编码如下：

char* ctable[] = {
    "._",   //A
    "_...", //B
    "_._.", //C
    "_..",  //D
    ".",    //E
    ".._.", //F
    "__.",  //G
    "....", //H
    "..",   //I
    ".___", //J
    "_._",  //K
    "._..", //L
    "__",   //M
    "_.",   //N
    "___",  //O
    ".__.", //P
    "__._", //Q
    "._.",  //R
    "...",  //S
    "_",    //T
    ".._",  //U
    "..._", //V
    ".__",  //W
    "_.._", //X
    "_.__", //Y
    "__.."  //Z

};
char* ntable[] = {
    "_____",//0
    ".____",//1
    "..___",//2
    "...__",//3
    "...._",//4
    ".....",//5
    "_....",//6
    "__...",//7
    "___..",//8
    "____." //9
};

先说编码，编码比较简单，直接从输入字符串中顺序读每一个字符然后判断这个字符是数字还是英文字母直接就可以拿到这个字符对应的摩尔斯电码

编码函数如下：

const char* encodeMorseCode(const char* src)
{
    char* dst = (char*)malloc(sizeof(char)*4096);
    size_t index = 0;
    for(size_t i = 0; i < strlen(src); i++){
        if(src[i] >= '0' && src[i] <= '9'){
            for(size_t j = 0; j < strlen(ntable[src[i] - '0']); j++){
                dst[index++] = ntable[src[i] - '0'][j];
            }
        }
        else if(src[i] >= 'A' && src[i] <= 'Z'){
            for(size_t j = 0; j < strlen(ctable[src[i] - 'A']); j++){
                dst[index++] = ctable[src[i] - 'A'][j];
            }
        }
        else if(src[i] == ' '){
            dst[index++] = '/';
        }
        dst[index++] = ' ';
    }
    dst[index] = '\0';
    return dst;
}

这里需要说明的是在编码过程中原文中的空格被编码成’/’.

编码比较简单，这里就不在多说了。接下来看解码部分：

刚开始也是准备直接用循环来挨个匹配；但后来感觉这样效率实在是低！突然想到上次看到的一篇文章《一分钟学会摩尔斯电码》其中有这样一张图：

这是个树啊啊啊！！！？？？NICE

那么直接构建这棵树用来查询岂不美哉？

void makeMorseTree(Node* root)
{
    //put char node
    for(int i = 0; i < 26; i++){
        putCharNode(root,i,0);
    }

    //put num node
    for(int i = 0; i < 10; i++){
        putNumNode(root,i,0);
    }
}

此部分是造树函数，传入一个根节点，由此根节点出发遍地开花，造出一个二叉树。戏说不是胡说，这个函数可以分为两个部分第一个for循环主要是遍历存放英文字母编码表ctable将编码表中的英文字母挂到树上；第二个for循环只要是遍历数字编码表ntable将编码表中的数字挂到树上。接下来我就挑选putCharNode()函数展开说一下。

void putCharNode(Node* root,int row,int col)
{
    if(ctable[row][col] == '_' && root->left == NULL){
        Node* temp = (Node*)malloc(sizeof(Node));
        root->left = temp;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = '#';//invalid node value stored '#'
        putCharNode(temp,row, ++col);
    }else if(ctable[row][col] == '_' && root->left != NULL){
        putCharNode(root->left,row, ++col);
    }else if(ctable[row][col] == '.' && root->right == NULL){
        Node* temp = (Node*)malloc(sizeof(Node));
        root->right = temp;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = '#';//invalid node value stored '#'
        putCharNode(temp,row, ++col);
    }else if(ctable[row][col] == '.' && root->right != NULL){
        putCharNode(root->right,row, ++col);
    }else if(ctable[row][col] == '\0'){
        root->data = 'A' + row;
    }
}

三个参数 root 树根；row表示是ctable中的第几个编码；col表是row对应的编码的第几位。

分为五种情况：

1.读到_ 并且此节点左子树非空则递归 call putCharNode(root->left,row, ++col)

2.读到_ 并且此节点左子树空则先malloc新空间 然后 递归 call putCharNode(root->left,row, ++col)

3.读到.并且此节点左子树非空则递归 call putCharNode(root->right,row, ++col)

4.读到.并且此节点左子树空则先malloc新空间 然后 递归 call putCharNode(root->right,row, ++col)

5.读到\0则表示此字符对应的编码读取结束，要进行字符挂树操作，此时直接 root->data = 'A' + row即可。

数字挂树同理，接下来就是读入摩尔斯电码查树即可得到译码结果：

const char* decodeMorseCode(Node* root,const char* src)
{
    char* dst = (char*)malloc(sizeof(char)*4096);
    char temp[6] = {'\0'};
    size_t index = 0;
    size_t offset = 0;
    for(size_t i = 0; i < strlen(src); i++){
        while(src[i] != ' ' && src[i] != '\0'){
            temp[offset++] = src[i++];
        }
        temp[offset] = '\0';
        dst[index++] = findCode(root, temp,0);
        offset = 0;
    }
    dst[index] = '\0';
    return dst;
}

译码函数传入树根root和摩尔斯电码src；以空格键为分割将其放入temp数组中然后call findCode(root, temp,0)函数进行递归爬树找到temp中摩尔斯电码对应的字符。

char findCode(Node* root, char* temp,int index)
{
    if(root == NULL)
        return 35;//invalid code!
    else if(temp[index]=='/')
        return ' ';
    else if(temp[index] == '_')
        findCode(root->left,temp,++index);
    else if(temp[index] == '.')
        findCode(root->right,temp,++index);
    else if(temp[index] == '\0'){
        if(root->data == '#')
            return 35;//invalid code!
        else
            return root->data;
    }
}

至此；此快速摩尔斯电码编码&&译码关键代码已经全部介绍完。

接下来看调用例子demo.c

/*
this file used for the morse code encode test.
*/
#include "morsecode.h"

int main()
{
    //init the root node
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = '?';//the root data part stored value '?'
    root->left = NULL;
    root->right = NULL;

    //make tree
    makeMorseTree(root);

    //encode and decode
    const char* morse = encodeMorseCode("BH6AOL");
    const char* plain = decodeMorseCode(root,"_._. __._ / _._. __._");

    //print the result
    printf("BH6AOL --> %s\n", morse);
    printf("_._. __._ / _._. __._ --> %s\n", plain);

    return 0;
}

编译运行结果如下（Windows GCC）：

Microsoft Windows [版本 10.0.18362.10005]
(c) 2019 Microsoft Corporation。保留所有权利。

C:\Users\Michael Jiang\Desktop\MorseCode>gcc demo.c morsecode.c -std=c11

C:\Users\Michael Jiang\Desktop\MorseCode>a.exe
BH6AOL --> _... .... _.... ._ ___ ._..
_._. __._ / _._. __._ --> CQ CQ

GitHub传送：https://github.com/MichaelJiang1997/MorseCode

三.全部源码

morsecode.h

/*
// Morse Code Header
// Last-Modified:2019-8-8 17:09:25
// Copyright (C)2019 Michael Jiang <sencom1997@outlook.com>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef MORSECODE_H
#define MORSECODE_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
    char  data;
    struct Node* left;
    struct Node* right;
}Node;
void putNumNode(Node* root,int row,int col);
void putCharNode(Node* root,int row,int col);
void makeMorseTree(Node* root);//this func call putNumNode() and putCharNode() to make a morse code tree
void preOrder(Node* root);//DLR Morse Tree for test
char findCode(Node* root, char* temp,int index);
const char* decodeMorseCode(Node* root,const char* src);
const char* encodeMorseCode(const char* src);

#endif

morsecode.c

/*
Fast Morse Code Encoder && Decoder
Michael Jiang <sencom1997@outlook.com>
2019-8-7 15:31(七夕版)
*/
#include "morsecode.h"

char* ctable[] = {
    "._",   //A
    "_...", //B
    "_._.", //C
    "_..",  //D
    ".",    //E
    ".._.", //F
    "__.",  //G
    "....", //H
    "..",   //I
    ".___", //J
    "_._",  //K
    "._..", //L
    "__",   //M
    "_.",   //N
    "___",  //O
    ".__.", //P
    "__._", //Q
    "._.",  //R
    "...",  //S
    "_",    //T
    ".._",  //U
    "..._", //V
    ".__",  //W
    "_.._", //X
    "_.__", //Y
    "__.."  //Z

};
char* ntable[] = {
    "_____",//0
    ".____",//1
    "..___",//2
    "...__",//3
    "...._",//4
    ".....",//5
    "_....",//6
    "__...",//7
    "___..",//8
    "____." //9
};

void putNumNode(Node* root,int row,int col)
{
    if(ntable[row][col] == '_' && root->left == NULL){
        Node* temp = (Node*)malloc(sizeof(Node));
        root->left = temp;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = '#';//invalid node value stored '#'
        putNumNode(temp,row, ++col);
    }else if(ntable[row][col] == '_' && root->left != NULL){
        putNumNode(root->left,row, ++col);
    }else if(ntable[row][col] == '.' && root->right == NULL){
        Node* temp = (Node*)malloc(sizeof(Node));
        root->right = temp;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = '#';
        putNumNode(temp,row, ++col);
    }else if(ntable[row][col] == '.' && root->right != NULL){
        putNumNode(root->right,row, ++col);
    }else if(ntable[row][col] == '\0'){
        root->data = '0' + row;
    }
}

void putCharNode(Node* root,int row,int col)
{
    if(ctable[row][col] == '_' && root->left == NULL){
        Node* temp = (Node*)malloc(sizeof(Node));
        root->left = temp;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = '#';//invalid node value stored '#'
        putCharNode(temp,row, ++col);
    }else if(ctable[row][col] == '_' && root->left != NULL){
        putCharNode(root->left,row, ++col);
    }else if(ctable[row][col] == '.' && root->right == NULL){
        Node* temp = (Node*)malloc(sizeof(Node));
        root->right = temp;
        temp->left = NULL;
        temp->right = NULL;
        temp->data = '#';//invalid node value stored '#'
        putCharNode(temp,row, ++col);
    }else if(ctable[row][col] == '.' && root->right != NULL){
        putCharNode(root->right,row, ++col);
    }else if(ctable[row][col] == '\0'){
        root->data = 'A' + row;
    }
}

void makeMorseTree(Node* root)
{
    //put char node
    for(int i = 0; i < 26; i++){
        putCharNode(root,i,0);
    }

    //put num node
    for(int i = 0; i < 10; i++){
        putNumNode(root,i,0);
    }
}

void preOrder(Node* root)
{
    printf("%c ",root->data);
    if(root->left != NULL)
        preOrder(root->left);
    if(root->right != NULL)
        preOrder(root->right);
}

char findCode(Node* root, char* temp,int index)
{
    if(root == NULL)
        return 35;//invalid code!
    else if(temp[index]=='/')
        return ' ';
    else if(temp[index] == '_')
        findCode(root->left,temp,++index);
    else if(temp[index] == '.')
        findCode(root->right,temp,++index);
    else if(temp[index] == '\0'){
        if(root->data == '#')
            return 35;//invalid code!
        else
            return root->data;
    }
}

const char* decodeMorseCode(Node* root,const char* src)
{
    char* dst = (char*)malloc(sizeof(char)*4096);
    char temp[6] = {'\0'};
    size_t index = 0;
    size_t offset = 0;
    for(size_t i = 0; i < strlen(src); i++){
        while(src[i] != ' ' && src[i] != '\0'){
            temp[offset++] = src[i++];
        }
        temp[offset] = '\0';
        dst[index++] = findCode(root, temp,0);
        offset = 0;
    }
    dst[index] = '\0';
    return dst;
}

const char* encodeMorseCode(const char* src)
{
    char* dst = (char*)malloc(sizeof(char)*4096);
    size_t index = 0;
    for(size_t i = 0; i < strlen(src); i++){
        if(src[i] >= '0' && src[i] <= '9'){
            for(size_t j = 0; j < strlen(ntable[src[i] - '0']); j++){
                dst[index++] = ntable[src[i] - '0'][j];
            }
        }
        else if(src[i] >= 'A' && src[i] <= 'Z'){
            for(size_t j = 0; j < strlen(ctable[src[i] - 'A']); j++){
                dst[index++] = ctable[src[i] - 'A'][j];
            }
        }
        else if(src[i] == ' '){
            dst[index++] = '/';
        }
        dst[index++] = ' ';
    }
    dst[index] = '\0';
    return dst;
}

demo.c

/*
this file used for the morse code encode test.
*/
#include "morsecode.h"

int main()
{
    //init the root node
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = '?';//the root data part stored value '?'
    root->left = NULL;
    root->right = NULL;

    //make tree
    makeMorseTree(root);

    //encode and decode
    const char* morse = encodeMorseCode("BH6AOL");
    const char* plain = decodeMorseCode(root,"_._. __._ / _._. __._");

    //print the result
    printf("BH6AOL --> %s\n", morse);
    printf("_._. __._ / _._. __._ --> %s\n", plain);

    return 0;
}