清华大学中级微观经济学讲义(清华 李稻葵)2

目录一、设计思想……………………………………………………….02二、算法流程图…………………………………………………….03三、源代码………………………………………………………….03四、运行结果……………………………………………………….09五、遇到的问题及解决…………………………………………….11六、心得体会……………………………………………………….12哈夫曼编码与解码的实现-1-一、设计思想哈夫曼的编码与解码：读取txt文件，统计所得到的文件中每个字母的权值，创建哈夫曼树，哈夫曼编码。哈夫曼解码，解码后内容写入到指定的txt文件，让用户选择不同的操作。读取txt文件，里面的内容是由英文单词组成。读取文件的时候传入文件存放的路径、读取方式以及读出以后存放的数组，最终可以得到一个存放目标文件内容的数组。将得到的数组进行字母权值的统计，统计每个字母出现的次数，次数即为每个字母的权值，在这个函数里面统计26个字母在目标文件中出现的次数，并且统计“逗号”、“句号”和“空格”的出现次数。使用的方法：每次从数组中取出一个字符，将字母的ASCII值与字母“a”相减，得到一个小于26的数，将存放权值数组的对应位置进行++运算，特殊的三个符号另作统计，如此可以得到目标文件中每个字母出现的次数。然后将字母出现次数为零的字母去掉重新组成一个字符数组，在配上对应的权值数组，统计完成后将字符数组与权值数组作为结果返回。将得到的字符数组与权值数组作为创建哈夫曼树的依据，哈夫曼树根据每个字母权值的大小来创建，每个节点，包括权值、状态（是否已经在哈夫曼树上，0代表不再哈夫曼树上，1代表在哈夫曼树上）、父节点、左子、右子和字母本身。假设有n个字母，也即是叶子节点，哈夫曼树上的节点应该为2*n–1个。前面的n个节点都有相应的字母，后面生成的n-1个节点是没有相应的字母的，用空字符替代。对每个节点进行初始化。初始化完成以后，开始创建哈夫曼树，每次选取两个权值最小的叶子节点组成一个新的节点，新的节点的左子设置为上面两个权值小的那个节点，右子为上面权值大的那个节点，权值为上面两个节点的权值的和，将上述选取出来的叶子节点标位设置为1，父节点为新创建出来的节点。将新的节点存放到原有的节点数组上，将已用过的节点从节点数组上去除。重复执行上述操作直到只剩下最后一个节点，完成哈夫曼树的创建。根据哈夫曼树进行编码，每次都从叶子节点开始遍历，设置为当前节点，根据此节点的父节点的左子是此节点还是右子是此节点，记录相应的编码0还是1，然后将此父节点设置为当前节点，重复上面的操作，直到当前节点不再具有父节点时得到该叶子节点的哈夫曼编码。将叶子节点用上面的方式进行编码，再用这些编码替换字母，从目标文件的数组中依次取出字母，将字母用相应的哈夫曼编码替代，存放到新的数组，执行完毕后，形成目标文件的哈夫曼编码，将此编码返回。根据哈夫曼树，将哈夫曼编码得到的0和1的字符串译成原先内容。解码的时候每次都站在哈夫曼树的最上面一个节点上，然后从编码得到的数组中每次取出一个字符，在根据取出的字符是‘0’还是‘1’决定是往该节点的左子走还是右子走。重复执行上面的操作，直到遇到叶子节点为止。将对应的叶子节点存放的字母存入解码数组中，重新回到根节点上，再进行上述的操作直到编码数组结束为止。得到的数组即为解码数组，解码数组作为解码的结果返回。写入txt文件，将解码得到的数组、文件的完整路径以及文件的写方式作为参数传入，将数组写入到相应的文件中。给用户相应的选择，0代表退出程序，1代表编码操作，2代表解码操作，每次根据用户的不同输入要求执行相应的功能。用一个循环来完成，当遇到0的时候就不再进行下面的操作，否则就让用户重新输入想要执行的操作。哈夫曼编码与解码的实现-2-二、算法流程图从文件中读取要进行编码的内容，创建哈夫曼数，哈夫曼编码解码。将解码得到的内容写入到指定的文件中。图1哈夫曼编码译码三、源代码下面给出的是哈夫曼编码解码算法实现程序的源代码：#includestdio.h#includestdlib.h#includestring.h#defineMaxValue100#defineMinValue0typedefstruct{intflag;//节点的标志位，0代表未存在哈夫曼树上，1代表已存在intparent;//当前节点的父节点intleftChild;//当前节点的左子intrightChild;//当前节点的右子intweight;//当前节点的权值charch;//当前节点代表的字母哈夫曼编码与解码的实现-3-}HaffTree;typedefchar*HaffCode;//存放每个字母哈夫曼编码//从指定的文件中读取内容，并且存放到数组中voidReadFile(charpath[],charway[],chararray[]){FILE*fp;inti=0;//根据路径和打开方式打开指定的文件，判断操作是否成功if((fp=fopen(path,way))==NULL){printf(can'topenthefile);}fgets(array,100,fp);//将文件的内容读入到字符数组中printf(%s,array);printf(\n);fclose(fp);//完成读取以后将文件关闭}//获得每个字母对应的权值，并将存在的字母存为数组，且将对应的权值返回voidGetWeight(chararray[],intletterWeight[],charexistLetters[],intweight[]){inti,j=0,k=0,m,n=strlen(array);//n代表array数组的长度for(i=0;in;i++){m=array[i]-'a';//计算当前字母与字符a的ASCII差值switch(m){case-53:letterWeight[26]++;break;//如果差值为-53，则为逗号case-51:letterWeight[27]++;break;//如果差值为-51，则为句号case-65:letterWeight[28]++;break;//如果差值为-65，则为空格default:letterWeight[m]++;//根据不同的差值，对应的字母权值加1}}printf(\tletter\t\tweight\n);for(i=0;i29;i++)//取出文件中没有出现的字母{if(letterWeight[i]!=0){switch(i){case26:existLetters[j++]=',';//若存在逗号，则存入数组weight[k++]=letterWeight[i];printf(\t,\t\t%d\n,letterWeight[i]);break;case27:哈夫曼编码与解码的实现-4-existLetters[j++]='.';//若存在句号，则存入数组weight[k++]=letterWeight[i];printf(\t.\t\t%d\n,letterWeight[i]);break;case28:existLetters[j++]='';//若存在空格，则存入数组weight[k++]=letterWeight[i];printf(\t空格\t\t%d\n,letterWeight[i]);break;default:existLetters[j++]=i+'a';//一般情况还原字母存入weight[k++]=letterWeight[i];printf(\t%c\t\t%d\n,i+'a',letterWeight[i]);}}}}//根据每个字母的权值，创建哈夫曼树voidCreateHaffTree(intweight[],HaffTreehaffTree[],charch[]){inti,j,x1,x2,m1,m2,n,k;n=strlen(ch);//计算字母数组的长度for(i=0;in*2-1;i++)//为哈夫曼树的2*n-1个节点初始化{if(in)//为n个叶子节点初始化{haffTree[i].weight=weight[i];haffTree[i].flag=0;haffTree[i].parent=-1;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;haffTree[i].ch=ch[i];}else//为n-1个非叶子节点初始化{haffTree[i].weight=0;haffTree[i].flag=0;haffTree[i].parent=-1;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;haffTree[i].ch='';}}for(i=0;in-1;i++)//构造哈夫曼树{x1=x2=MaxValue;哈夫曼编码与解码的实现-5-m1=m2=MinValue;//选取两个权值最小的节点for(j=0;jn+i;j++){if(haffTree[j].weight=x1&&haffTree[j].flag==0){x2=x1;x1=haffTree[j].weight;//x1代表左子的权值m2=m1;m1=j;//m1代表左子的下标}elseif(haffTree[j].weightx2&&haffTree[j].flag==0){x2=haffTree[j].weight;//x2代表右子的权值m2=j;//m2代表右子的下标}}haffTree[m1].parent=n+i;//将左子的父节点设置为新构造的节点haffTree[m1].flag=1;//设置标志位1haffTree[m2].parent=n+i;//将右子的父节点设置为新构造的节点haffTree[m2].flag=1;//设置标志位1haffTree[n+i].leftChild=m1;//父节点的左子为m1haffTree[n+i].rightChild=m2;//父节点的右子为m2//父节点的权值为左子的权值与右子的权值的和haffTree[n+i].weight=haffTree[m1].weight+haffTree[m2].weight;}}//进行哈夫曼树的编码，将编码形成的结果作为数组返回voidEncodeHaffTree(HaffTreehaffTree[],intn,HaffCodehaffCode[],charchr[],chartarget[],charencode[]){intchild,parent,start,i,j=0;char*ch;ch=(char*)malloc(n*sizeof(char));//分配可以放得下n个字符的内存空间//分配可以放得下n+1个字符指针的内存空间haffCode=(HaffCode*)malloc((n+1)*sizeof(char*));ch[n-1]='\0';for(i=0;in;i++){start=n-1;//编码的开始位置child=i;//设置当前节点parent=haffTree[child].parent;//设置父节点为当前节点的父节点while(parent!=-1)//如果当前节点存在父节点，则继续匹配哈夫曼编码与解码的实现-6-{if(haffTree[parent].leftChild==child)//如果父节点的左子是当前节点{ch[--start]='0';//将字符0存入数组}else//如果父节点的右子是当前节点{ch[--start]='1';//将字符1存入数组}child=parent;//设置当前节点parent=haffTree[child].parent;//获取当前节点的父节点}haffCode[i]=(char*)malloc((n-start)*sizeof(char));strcpy(haffCode[i],&ch[sta