网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
张林锴吧 关注：20贴子：1,035
  • 3回复贴，共1页
#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode, *HuffmanTree;
typedef char * *HuffmanCode;
int min(HuffmanTree t,int i)
{
int j,flag=0;
int k=99999; // 取k为不小于可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
//本实习题中右子树是最小值对应序号，左子树是次小值对应序号
void select(HuffmanTree t,int i,int &s1,int &s2)
{
s2=min(t,i);
s1=min(t,i);
}
void Huffmancoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,i,s1,s2,c,f,start;
char *cd;
if(n <= 1)
{
return;
}
m = 2*n-1;
HT = (HuffmanTree) malloc ((m+1)*sizeof(HTNode));
for(i = 1;i <= n;i++)
{
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
HT[i].weight = w[i-1];
}
for(;i <= m;i++)
{
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
HT[i].weight = 0;
}
for(i = n+1;i <= m;i++)
{
select(HT,i-1,s1,s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1;HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char *)malloc(n*sizeof(char));
cd[n-1] = '\0';
for(i = 1;i <= n;i++)
{
start = n-1;
for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent)
{
if(HT[f].lchild == c)
{
cd[--start] = '1';
}
else
{
cd[--start] = '0';
}
}
HC[i] = (char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
int main()
{
int i,n,t,j;
int w[26];
char a[100];
char s[26];
HuffmanTree HT;
HuffmanCode HC;
cin >> n;
for(i = 0;i < n;i++)
{cin >> s[i];}
for(i = 0;i < n;i++)
{cin >> w[i];}
cin.get();
Huffmancoding(HT,HC,w,n);
cin.getline(a,100);
int len = strlen(a);
for(j = 0;j < len;j++)
{
t = a[j]-'a'+1;
cout << HC[t];
}
cout << endl;
cout << a << endl;
return 0;
}
问题:
语言: C C++ GCC G++ Java
#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode, *HuffmanTree;
typedef char * *HuffmanCode;
int min(HuffmanTree t,int i)
{
int j,flag=0;
int k=99999; // 取k为不小于可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
//本实习题中右子树是最小值对应序号，左子树是次小值对应序号
void select(HuffmanTree t,int i,int &s1,int &s2)
{
s2=min(t,i);
s1=min(t,i);
}
void Huffmancoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,i,s1,s2,c,f,start;
char *cd;
if(n <= 1)
{
return;
}
m = 2*n-1;
HT = (HuffmanTree) malloc ((m+1)*sizeof(HTNode));
for(i = 1;i <= n;i++)
{
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
HT[i].weight = w[i-1];
}
for(;i <= m;i++)
{
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
HT[i].weight = 0;
}
for(i = n+1;i <= m;i++)
{
select(HT,i-1,s1,s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1;HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char *)malloc(n*sizeof(char));
cd[n-1] = '\0';
for(i = 1;i <= n;i++)
{
start = n-1;
for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent)
{
if(HT[f].lchild == c)
{
cd[--start] = '1';
}
else
{
cd[--start] = '0';
}
}
HC[i] = (char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
int main()
{
int i,n,t,j;
int w[26];
char a[100];
char s[26];
HuffmanTree HT;
HuffmanCode HC;
cin >> n;
for(i = 0;i < n;i++)
{cin >> s[i];}
for(i = 0;i < n;i++)
{cin >> w[i];}
cin.get();
Huffmancoding(HT,HC,w,n);
cin.getline(a,100);
int len = strlen(a);
for(j = 0;j < len;j++)
{
t = a[j]-'a'+1;
cout << HC[t];
}
cout << endl;
cout << a << endl;
return 0;
}
问题:
语言: C C++ GCC G++ Java
IP属地:北京来自Android客户端1楼2015-11-11 14:03回复
    3333333
    #include <stdlib.h>
    int root=0;
    typedef struct bitreenode
    {
    char data;
    int layer;
    struct bitreenode *lchild;
    struct bitreenode *rchild;
    }BiTreeNode,*BiTree;
    BiTree CreatBiTree(int start,int end,char *a,char *b)
    {
    char ch=a[root];
    root++;
    int i,n;
    for(i=start;i<=end;i++)
    {
    if(ch==b[i])
    {
    n=i;
    break;
    }
    }
    BiTree T;
    T=(BiTree)malloc(sizeof(BiTreeNode));
    T->data=ch;
    if(n-1>=start)
    T->lchild=CreatBiTree(start,n-1,a,b);
    else
    T->lchild=NULL;
    if(end>=n+1)
    T->rchild=CreatBiTree(n+1,end,a,b);
    else
    T->rchild=NULL;
    return T;
    }
    void Traverse(BiTree T)
    {
    if(T==NULL) return;
    if(T->lchild!=NULL)
    Traverse(T->lchild);
    if(T->rchild!=NULL)
    Traverse(T->rchild);
    if(T->data!=' ')
    printf("%c\n",T->data);
    }
    int main()
    {
    BiTree T;
    T=(BiTree)malloc(sizeof(BiTreeNode));
    int strat=0,end;
    char a[20],b[20];
    gets(a);
    gets(b);
    int i=0;
    while(a[i]!='\0')
    {
    i++;
    }
    end=i-1;
    T=CreatBiTree(strat,end,a,b);
    Traverse(T);
    return 0;
    }
    IP属地:北京2楼2015-11-11 15:16
    回复
      44444
      #include <stdio.h>
      #include<stdlib.h>
      typedef struct bitreenode
      {
      char data;
      struct bitreenode *lchild;
      struct bitreenode *rchild;
      }BiTreeNode,*BiTree;
      BiTree CreatBiTree()
      {
      BiTree T;
      char ch;
      ch=getchar();
      if(ch=='#')
      T=NULL;
      else
      {
      T=(BiTree)malloc(sizeof(BiTreeNode));
      T->data=ch;
      T->lchild=CreatBiTree();
      T->rchild=CreatBiTree();
      }
      return T;
      }
      void Traverse(BiTree T)
      {
      if(T==NULL)
      return;
      if(T->lchild!=NULL)
      Traverse(T->lchild);
      printf("%c",T->data);
      if(T->rchild!=NULL)
      Traverse(T->rchild);
      }
      int main()
      {
      BiTree T;
      T=(BiTree)malloc(sizeof(BiTreeNode));
      T=CreatBiTree();
      Traverse(T);
      printf("\n");
      return 0;
      }
      IP属地:北京3楼2015-11-11 15:16
      回复
        22222222
        #include <stdio.h>
        #include <stdlib.h>
        int max=0;
        typedef struct bitreenode
        {
        char data;
        int layer;
        struct bitreenode *lchild;
        struct bitreenode *rchild;
        }BiTreeNode,*BiTree;
        BiTree CreatBiTree(int layernum)
        {
        BiTree T;
        char ch;
        ch=getchar();
        while(ch==')')
        {
        ch=getchar();
        }
        if(ch==',')
        ch=getchar();
        if(ch>='A'&&ch<='Z')
        {
        if(max<layernum)
        max=layernum;
        T=(BiTree)malloc(sizeof(BiTreeNode));
        T->data=ch;
        T->layer=layernum;
        ch=getchar();
        if(ch=='(')
        {
        T->lchild=CreatBiTree(layernum+1);
        T->rchild=CreatBiTree(layernum+1);
        }
        else
        {
        T->lchild=NULL;
        T->rchild=NULL;
        }
        }
        else if(ch=='#')
        {
        T=NULL;
        }
        return T;
        }
        void Traverse(BiTree T,int n)
        {
        if(T==NULL) return;
        if(T->lchild!=NULL)
        Traverse(T->lchild,n);
        if(T->layer==n)
        printf("%c",T->data);
        if(T->rchild!=NULL)
        Traverse(T->rchild,n);
        }
        int main()
        {
        int flag=1;
        BiTree T;
        T=(BiTree)malloc(sizeof(BiTreeNode));
        T=CreatBiTree(flag);
        int i;
        for(i=1;i<=max;i++)
        {
        Traverse(T,i);
        }
        printf("\n");
        return 0;
        }
        IP属地:北京4楼2015-11-11 15:30
        回复

          扫二维码下载贴吧客户端

          下载贴吧APP
          看高清直播、视频！
          • 3回复贴，共1页
          发表回复
          发贴请遵守贴吧协议及“七条底线”贴吧投诉
          内  容:
            查看全部
          发 表
          保存至快速回贴

          发布成功
          去贴吧APP订阅抽奖结果通知
          扫码进入贴吧APP
          ···········
          开奖后第一时间站内信通知
          ···········
          中奖结果全员公示