2-1.cpp

常微分方程初值问题的数值解法常微分方程初值问题的数值解法

#include <stdio.h>
#include <string.h>
#define MaxString 50
#define n 50
#define M 2*n-1

struct         /*定义结构体数组*/
{
    char letter;
    int num,weight,parent,Lchild,Rchild;
}Node[M+1],*node1,*node2;    /* 定义一个结构体数组,及两个指向结构体类型的指针 */

struct
{
    char letter;
    char code[20];
}Code[n];                    /* 定义结构体数组用来存放每个字母的哈夫曼编码 */

char String[50];             /* 定义一个字符串数组存储输入的字符串,用来转换完整编码使用 */

void Init(void)   /*初始化结构体数组*/
{
    int i = 1;
    node1 = &Node[1];       /* 初始化结构体指针 */
    node2 = &Node[2];
    for ( ; i < M+1; i++)             /* 初始化结构体中元素 */
    {
        Node[i].num = i;
        Node[i].letter = '0';
        Node[i].weight = 1;
        Node[i].parent = 0;
        Node[i].Lchild = 0;
        Node[i].Rchild = 0;
    }
}
    
int collect()      /*统计字符串输入到结构体数组中*/
{
    char ch[MaxString];
    int i = 0,j,k = 0;
    printf("please Input The String:");
    gets(ch);                                 /* 读入字符串 */
    for (i = 0;i<strlen(ch);i++)              /* 将字符串保存至String中 */
     String[i] = ch[i];
    for (i = 0; i < strlen(ch) ; i++)
     {
         j = 0;
        while ( ch[i] != Node[j+1].letter && j != k)        /*将字母统计存入表中*/
               { j++;}
        if ( ch[i] == Node[j+1].letter )
            (Node[j+1].weight)++;
         else
            {
                 Node[j+1].letter = ch[i];                   /* 与前面的均不相等则在最后写入 */
                 k++;
             }
     }
     return k;
}


select(int k)                   /*在权值中选择最小的两个*/
{
    int i = 0,j = 0,length;
    length = k;
    while (node1->parent != 0)                              /* 初始化node1准备判断 */
         node1 = &Node[++i];
    while (node2->parent != 0)                              /* 初始化node2准备判断 */
      if (node1 != &Node[++j])
         node2 = &Node[j];
    
     for ( i = 1; i < length;i++)                                                           /* 通过两次找最小的,找出两个最小值 */
       if ( node1->weight > Node[i].weight && node2 != &Node[i] && Node[i].parent==0)
          node1 = &Node[i];
     for ( j =1; j < length; j++)
       if (node2->weight > Node[j].weight && node1 != &Node[j] && Node[j].parent==0)
          node2 = &Node[j];
}


CrateHuffmanTree(int k)           /*创建哈弗曼树*/
{
    int i = 1;
    int length = k;
    for (i = length+1; i<= 2*length -1;i++)
    {
        select(length);
        Node[i].weight = node1->weight + node2->weight;
        Node[i].parent = 0;
        node1->parent = node2->parent = i;
        Node[i].Lchild = node1->num;
        Node[i].Rchild = node2->num;
    }
}


/*创建哈弗曼编码*/
CraHufCode(int k)                            /*对单个字符进行编码*/
{
    int length = k,i = 1,j = 1,m;
    char code[20];                                /* 定义临时用来存储反编码的字符串数组 */
    for (i = 1;i <= length; i++ )                  /*只对叶子结点编码*/
     {
         j = 0;
         node1 = &Node[i];                         /*初始化指针*/
         while(node1->parent != 0)
         {
           if( Node[node1->parent].Lchild == node1->num)         /* 构建反编码 */
            code[j] = '0';
            else code[j] = '1';
            node1 = &Node[node1->parent];
            j++;
          }
          Code[i].letter = Node[i].letter;
            m = 0;
         while (j != 0)                                       /* 将编码存储到Code中 */
              {
                   Code[i].code[m] = code[j-1];
                 j--;                                         /* code从后往前移动 */
                 m++;                                         /* M从前往后 */

             }


      }
}
/*创建对应单词的哈弗曼编码*/
CrateCode(int k)
{
    int i=0,j=1,length = k;
    char FCode[100];
    for (i=0;i<50;i++)
      FCode[i]=0;
      if(length == 1)
          printf("0");
    else
{ for ( i = 0;i < strlen(String);i++)
        for (j = 1; j <= length; j++)
          if (String[i] == Node[j].letter)           /* 进行字母匹配 */
              strcat(FCode,Code[j].code);            /* 将编码追加写入Fcode */

    printf("The HuffmanCode of your String is :\n");

     puts(FCode);   }                               /* 输出完整的哈弗曼编码 */

    

}


DeCode(int k,char FCode[])        /*对输入的哈弗曼编码进行译码*/
{
    int length = k,i=0,j=0;
    if ( length == 1)
     for (j=0;j<Node[1].weight;j++)
        printf("%c",Node[1].letter);
else
{   while(i < strlen(FCode))
   {
      node1 = &Node[2*length-1];
      while(node1->Lchild != 0)
      {
        if(FCode[i] == '0')
         node1 = &Node[node1->Lchild];
         else
           node1 = &Node[node1->Rchild];
           i++;
      }
      putchar(Node[node1->num].letter);

}
}
}



    
int main(void)
{
    int length,i;
    char FCode[100];
    Init();
    length = collect();
    CrateHuffmanTree(length);
    CraHufCode(length);
    CrateCode(length);
    printf("please Input The Huffman Code:");
    gets(FCode);
    DeCode(length,FCode);
    getch();

}