C语言课件 第23 24章.ppt

第23章 火车车厢重排,问题描述 问题分析及实现 开发过程常见问题及解决,第23章 火车车厢重排,问题描述 问题分析及实现 开发过程常见问题及解决,第23章 火车车厢重排,问题描述 问题分析及实现 开发过程常见问题及解决,第23章 火车车厢重排,问题描述 问题分析及实现 开发过程常见问题及解决,火车车厢重排,一列乱序排列货车车厢的火车，在经过车站时，可以从中间丢下这节车厢吗？而这节车厢却是终点站的车厢。那么，怎么样才可以使得出发前就可以以最快的理想的方式排好车厢号呢？使之在每站只丢下最后一节车厢，停留不长时间呢？本章讲解这类问题如何求解。,23.1 问题描述,一列货运列车共有n节车厢，每节车厢将停放在不同的车站，假定n个车站的编号分别为1n，货运列车按照第n站至第1站的次序经过这些车站，车厢的编号与他们的目的地相同。为了便于从列车上卸下相应的车厢，必须重新排列车厢，使各车厢从前至后都按照编号1到n的次序排列，当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。,23.2 问题分析及实现,23.2.1 问题分析 23.2.2 问题实现 23.2.3 程序运行,23.2 问题分析及实现,由问题描述可知，我们要实现的是将车厢放入缓冲轨，在需要压栈时压栈，需要出栈时出栈，最后将排序结果输出,23.2.1 问题分析,在这个问题的求解中，我们引入几个缓冲铁轨，在一个缓冲铁轨中放入车厢c，如果没有可用的缓冲铁轨，则返回0，如果空间不足，则引发异常否则返回1，为车厢c寻找最优的缓冲铁轨。,23.2.2 问题实现,1. 采用结构体保存过程数据 通过定义一个结构体类型，此结构体实现对列车车厢序号进行栈的存储和管理。那么，根据这个思路，代码如下（代码23-1.txt）。,01 #define stacksize 100 /*栈大小100个元素*/ 02 #define maxlength 100 /* 最大字符串长度*/ 03 typedef int datatype; /*栈元素的数据类型定义为整数*/ 04 typedef struct 05 06 datatype datastacksize; 07 int top; 08 seqstack; 09 void initial(seqstack *s) /*置空栈*/ 10 11 s-top=-1; 12 13 int isempty(seqstack *s) /*判栈空*/ 14 15 return s-top=-1; 16 17 int isfull(seqstack *s) /*判栈满*/ 18 19 return s-top=stacksize-1; 20 ,23.2.2 问题实现,2. 输出结果 将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显。代码如下（代码23-2.txt）。,23.2.2 问题实现,01 void output(int* minh, int* mins, seqstack h , int k, int n) 02 03 int i; 04 int c=pop( 11 12 ,23.2.2 问题实现,3. 将某个车厢号送入某个缓冲铁轨 铁轨不空时，在此铁轨顶部的车厢编号最小，否则将一个车厢号通过缓冲铁轨压入栈。代码如下（代码23-3.txt）。,23.2.2 问题实现,4. 火车车厢重排主函数 将所有火车车厢按数组规定的顺序送入缓冲铁轨等待排序。代码如下（代码23-4.txt）,23.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【enter】键，即可输出如下结果。,23.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 程序输出结果一直是同样的结果，不代表程序有错误，而是因为程序目的就是要让无论列车车厢号如何乱序，最终排的序是顺序的。 此程序的难点之一如何模拟停在铁轨上的列车。采用数组来模拟，这是最普遍的一种方法。,第24章 哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第24章 哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第24章 哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第24章 哈夫曼编码的实现,问题描述 问题分析及实现 开发过程常见问题及解决,哈夫曼编码的实现,现实的信息生活中，需要存储的信息是越来越多。在通信行业中，为了提高通信的效率，各路济济的人才也是绞尽脑汁了。本章将讲解为了减小信息的编码及通信的编码，需要重新对信息进行编码的一种非常重要的编码算法。哈夫曼编码现已应用到了很多行业，那么如何实现哈夫曼编码呢？它又有什么优势呢？,24.1 问题描述,哈夫曼编码（huffman coding）是一种编码方式，是可变字长编码（vlc）的一种。 huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称为huffman编码。以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在本章，使用c语言实现一个huffman编码的程序，可对预先定制的字符串及权重重新编码，打印每个字符串对应的编码。在数据通讯中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制代码，称之为编码。如果在编码时考虑字符出现的频率，将重复出现次数较高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。因此，哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。,24.2 问题分析及实现,24.2.1 问题分析 24.2.2 问题实现 24.2.3 程序运行,24.2 问题分析及实现,由问题描述可知，我们要实现的是打印huffman编码。在输入，处理，输出的环节中，要求的输入指的预先设定好的字符串及相应的权重，处理，就是huffman树创建的过程，而输出，就是将最终处理后的结果打印出来。 huffman编码，其中心目的就是为了使编码后的数据量比编码前的原始数据量有一个数量级的下降。换言之，就是为了压缩。无论是它应用在通信行业，信息存储方面，都是为了这一目的。那么，怎么实现呢？在问题分析阶段，我们给出具体的更详细的讲解。,24.2.1 问题分析,huffman的本质是压缩，那么压缩如何实现呢？采用哈夫曼（huffman）树，也称最优二叉树建树，树建好后，就等于每个节点上的编码已经编好，只需要打印出来。那么还记得前几章讲到的如何建立一个最优二叉树吗？带权路径长度最小的二叉树就是huffman树。所以求树的带权路径长度，就成为了关键。,24.2.2 问题实现,带权路径长度最小，就成了我们需要实现的目标。就是说，权重越大，离树的根部越近，这点相当于，一个单位的人员，权利越大，他的位置就离这个单位最高领导的位置越近，相反，越无足轻重，则离领导岗位就越远。 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子ti为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。实现的代码如下。,24.2.2 问题实现,1. 采用结构体保存过程数据 通过定义两个结构体类型，分别记录二叉树的信息和编码的信息。代码如下（代码24-1.txt）,24.2.2 问题实现,01 #include 02 #include 03 #define node 100 /*叶子结点数*/ 04 #define m 2*node-1 /*树中结点总数*/ 05 typedef struct 06 07 int parent; /*父结点*/ 08 int lchild; /*左子结点*/ 09 int rchild; /*右子结点*/ 10 char data10; /*结点值*/ 11 int weight; /*权重*/ 12 treenode; /*树结构体*/ 13 typedef struct 14 15 char cdnode; /*存放哈夫曼码*/ 16 int start; 17 code; /*编码结构体*/,24.2.2 问题实现,2. 输出结果 将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf，将结果回显。代码如下（代码24-2.txt）。,24.2.2 问题实现,01 void dispcode(treenode ht,code hcd,int n) 02 03 int sum=0,m=0; 04 int i,j,k; 05 printf(“哈夫曼编码:n“); /*输出哈夫曼编码*/ 06 for (i=0;in;i+) 07 08 j=0; 09 printf(“ %s:t“,hti.data); 10 for (k=hcdi.start;k=n;k+) 11 12 printf(“%c“,hcdi.cdk); 13 j+; 14 15 m+=hti.weight; 16 sum+=hti.weight*j; 17 printf(“n“); 18 19 printf(“n平均长度=%gn“,1.0*sum/m); 20 ,24.2.2 问题实现,3. 求解huffman的编码 通过对已经建立好的树进行循环遍历，向左路径记录0，向右路径记录1，直到所有节点均访问到。代码如下（代码24-3.txt）。,24.2.2 问题实现,/*对树编码*/ void createcode(treenode ht,code hcd,int n) int i,f,c; code hc; for (i=0;in;i+) /*根据哈夫曼树求哈夫曼编码*/ hc.start=n;c=i; f=hti.parent; while (f!=-1) /*循序直到树根结点*/ if (htf.lchild=c) /*处理左孩子结点*/ hc.cdhc.start-=0; else /*处理右孩子结点*/ hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /*start指向哈夫曼编码最开始字符*/ hcdi=hc; ,24.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【enter】键，即可输出如下结果。,24.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 开发中，要如何理解编码概念呢？编码，就是将一种信息用另外一种信息表示出来，而一般采用的方法就是以二进制进行编码，如ascii(美国国家标准编码字符集)。