Sunday, December 23, 2007

数据结构:关于哈夫曼树的建立以及哈夫曼编码

请求一件事……如果你是北邮的学生……请别抄了…………都抄一样的我的作业怎么办?

//Huffman EnCoding....DATA STRUCTURE, by ss1271@SIE,BUPT

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

typedef struct
 {
   unsigned int weight;
   unsigned int parent,lchild,rchild;
 }HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
 
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

 int min(HuffmanTree t,int i)
 {
   int j,flag;
   unsigned int k=UINT_MAX; // 取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)// s1为最小的两个值中序号小的那个
 {
   int j;
   s1=min(t,i);
   s2=min(t,i);
   if(s1>s2)
   {
     j=s1;
     s1=s2;
     s2=j;
   }
 }


void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
 {
   int m,i,s1,s2,start;
   unsigned c,f;
   HuffmanTree p;
   char *cd;
   if(n<=1)
     return;
   m=2*n-1;
   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
   for(p=HT+1,i=1;i<=n;++i,++p,++w)
   {
     (*p).weight=*w;
     (*p).parent=0;
     (*p).lchild=0;
     (*p).rchild=0;
   }
   for(;i<=m;++i,++p)
     (*p).parent=0;
   for(i=n+1;i<=m;++i)
   {
     select(HT,i-1,s1,s2);
     HT[s1].parent=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]='0';
       else
  cd[--start]='1';
     HC[i]=(char*)malloc((n-start)*sizeof(char));
     strcpy(HC[i],&cd[start]);
   }
   free(cd);
 }
 void main()
 {
 printf("Huffman Tree Creating & Huffman Encoding, by ss1271.\n");
 HuffmanTree HT;
 HuffmanCode HC;
    int *w,n,i;
    printf("请输入权值的个数(需要大于1):");
    scanf("%d",&n);
    w=(int*)malloc(n*sizeof(int));
    printf("请依次输入%d个权值(整型,每输入完成一个请回车确认):\n",n);
    for(i=0;i<=n-1;i++)
      scanf("%d",w+i);
    HuffmanCoding(HT,HC,w,n);
    printf("哈夫曼编码结果为:\n");
    for(i=1;i<=n;i++)
      puts(HC[i]);
 }

特别提供数据结构中关于二叉树的代码

希望为广大被数据结构打蒙的同学提供一些帮助,这是我最近做数据结构时候自己写的,具体什么功能不用我说了吧,自己看吧……

//Creation & Traversion of a Binary Tree...DATA STRUCTURE. by ss1271@SIE,BUPT
#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef struct Node
{
 int data;
 struct Node *lchild, *rchild;
}BiTNode;
typedef BiTNode *BiTree;
int createBiTree(BiTree *T)
{
 char c;
 scanf("%c",&c);
 if (c==' ')
  *T=NULL;
 else
 {
  if(!(*T=(BiTNode*)malloc(sizeof(BiTNode))))
   return OVERFLOW;
  (*T)->data =c;
  createBiTree(&(*T)->lchild);
  createBiTree(&(*T)->rchild);
 }
 return OK;
}
//Traverse BinTree

void preordertraverse(BiTree T)
{
 if(T)
 {
  printf("%c",T->data);
  preordertraverse(T->lchild);
  preordertraverse(T->rchild);
 }
}
void inordertraverse(BiTree T)
{
 if(T)
 {
  inordertraverse(T->lchild );
  printf("%c",T->data );
  inordertraverse(T->rchild );
 }
}
void postordertraverse(BiTree T)
{
 if(T)
 {
  postordertraverse(T->lchild );
  postordertraverse(T->rchild );
  printf("%c",T->data );
 }
}
void destroyBiTree(BiTree T)
{
   if(T)
   {
     if(T->lchild)
       destroyBiTree(T->lchild);
     if(T->rchild)
       destroyBiTree(T->rchild);
     free(T);
     T=NULL;
   }
 }
void main()
{
 BiTree T=NULL;
 printf("Create Binary Tree(Use space to instead a null node).\n");
 createBiTree(&T);
 printf("This Binary Tree's Pre-Order Traversion is:\n");
 preordertraverse(T);
 printf("\nThis Binary Tree's In-Order Traversion is:\n");
 inordertraverse(T);
 printf("\nThis Binary Tree's Post-Order Traversion is:\n");
 postordertraverse(T);
 char m;
 printf("Destroy this Binary Tree?(Y/N):");
 if((m=getchar())=='Y')
  destroyBiTree(T);
 else
  exit(0);
}

Wednesday, December 19, 2007

豆腐当肉卖——北邮学生爆料食堂黑幕



相关报道请参见12月16日《新京报》
http://edu.sina.com.cn/video/shitangtv/index.html

Friday, December 07, 2007

久违的成就感居然从模拟电路作业上找回了…



这作业写的~行云流水~嘿嘿

Pearl Harbor



On Dec.7.1941, the United States was deliberately attacked by the Japanese Empire.

So I write this to memory the crimes made by the Japs.

F. Japs. And a stronger China will take place your places.

Long live the People's Republic of China!

Thursday, December 06, 2007

彻底被Live战略征服…



自从symbian(N70)转换到Wm.系统(多普达9000日版SoftBank x01ht)后,发现腾讯对windows mobile系统的自动连接支持不好,只能支持系统的“专用网络连接”,由于我不使用cmwap上网,导致我没法让他既自动连接彩信又挂qq。新浪现在不支持(06年还支持)来自移动设备的发布…可偏偏我发现wm系统捆绑了live套件,并且还可以用邮件代替live writer离线写作…所以,决定把spaces当作Primary Blog。

Wednesday, December 05, 2007

The Huge TFT Screen

 To welcome the so called professors, our school set a brand new huge TFT screen outside...

IMAGE_004

上午终于如愿看完了Feed Back circuit



昨天电子电路课换了一个老师,是一个山东口音的,说话的速度和之前的那个教授简直快了十倍……恨不得五分钟能说完之前一个小时的内容……考验中文听力的时刻到来了~好在虽然课上听得云里雾里,今天上午一个小时就全部搞定~留出时间准备下午的物理实验……

Tuesday, December 04, 2007

Terrible Day.......

I'm trying to use Spaces to blog something useful. But I failed. I've terrible mood today & I'll write something depressed here.
I've tried to finish my Physics Experiment Reports until I realized that I even hadn't fulfilled Mathematics yet, to make things worse, I've stucked by an unexpected problem 4 nearly 2 hrs..I don't know,why,everything, everybody, & every stuff I met was trying to stop me from...well,I even don't know what the hell exactly it is...

Friday, November 23, 2007

Show一下这两块CPU

左侧是T2300,1.66,右侧是T2600,2.16……目前手头只有这些图了……没办法,这周数据都丢了

image

Thursday, November 22, 2007

来看看我有多倒霉2

随之的第二天,尽管没课,但是却找不到一个可以看书的地方…于是在浪费了两个小时找不到自习室个后,我选择了在寝室恢复数据…渡过难熬的11个小时后,3GB数据最终只回来200MB不到,而且图片和很大一部分最重要的数据损坏了(庆幸一下老婆的照片存在手机里了~而且还是找回了游戏的存档,虽然是比当时的进度慢了一些,但是总比重新开始强…)我周末还要抽时间去验证这些数据…唉…有这么一糟事就是发生在所有科都第一也高兴不起来!

来看看我多倒霉

真是…估计我要是知道英语考了全班第一之后会造成如下后果的话也就不会那么卖命考了…:首先,电脑分区坏了…究其原因是我为了装上周日刚刚拿到的ubuntu710用acronis disk director 10从已有分区分出了ext3分区,结果发现不能格式化。我后来试图在进操作系统前用它把那个分区格式化,也失败了。结果我就想到重新做分区,当时急切想装,居然没有考虑到数据的问题,于是将近3GB的素材文档图片以及各种资料伴随着我的一个回车直接灰飞烟灭…而且,更要命的是,我还把这个重新分区的过程进行了三遍…其中做了2遍xp,三遍ubuntu(不知道为什么我给了他主分区他还是装不上,难道真的只能装在虚拟机里???),最后一遍是在50%电的情况下装完了vista Enterprise…(这也算是收获吧…至少证明了vista安装的比xp快n倍)

Wednesday, August 01, 2007

acer Aspire 5672拆机上T2600~

image

mPGA插座和T2300

image

T2300正面 

image

T2300背面

image

ATi Mobility X1400

image

散热系统

image

T2600的系统评分

image

Saturday, June 02, 2007

唉……被6班的放血打法赢了3分……Just 3 Points!

我知道输了的话……说什么也没有用了……但是,对于06606班这种放血的,遭人BS的打法来说,怎么都不为过!

裁判也很垃圾,明明我都已经把那个人规掉了,衣服快要被拽破了,依然不吹……防盗足球中也是要吹的啊……

……这个球赛还有一些值得让我们高兴的东西……至少,我们在小组赛最后一场血洗了对手……

嘿嘿,我的Jumper~

image

Wednesday, May 02, 2007

BUPT SIE 06601班篮球赛队服抢先预览~

以15号 VC.NET选手的队服为例……

这是正面

 3dfcf19c0da5ba9a3d261

反面是……

 

3dfcf19ce0e8773424825

Monday, April 30, 2007

终于找到Acer Bluetooth VOIP Phone的识别码了

我写在这里,希望对各位朋友有所帮助

我的本本是Acer Aspire 5672

兰芽电话的参数如下:

Model:VT25010

Rating:5V

IC NO :4441A-DBPC

如果您像我一样是WindowsVista的用户,那么您可能无法使用AcerVCM对兰芽电话进行连接。这没有关系,您的手机和本本照样可以通过手动连接或者配对的方式使用兰芽电话。

本人试了10分钟,包括1234,1111,0000等都用过了,无效。最后试到设备授权码是4444。

谢谢合作!!!!