数据结构课程实习,实习班级：111081-4班 指导教师：张剑波 方芳,Company name,2,内容提要,实习时间安排 考核标准 需要提交的文档 实习题目及讲解,Company name,3,一、实习时间安排,实习时间（2周，3学分，48学时） 1月12号到1月20号，9天时间 下午2:00-6:00, 5学时 实习地点：信息楼202 课程实习中随时可以检查完成情况！,Company name,4,二、考核标准,上机考勤： 10% 课程设计报告：30% 软件设计作品：60% 注意：本次实习布置3道题可供选择，实习成绩与完成的题数和质量相关 1、优秀：完成3题，且代码质量高； 2、良好：完成2题，且代码质量高； 3、中等：完成2题，且代码质量一般； 4、及格：完成1题； 5、不及格：完成小于1题,Company name,5,三、需要提交的文档,课程设计报告：严格按照格式要求撰写，并使用A4纸打印 （课程设计报告不需要打印所有源代码） 源程序汇总：各班学习委员将所有同学的源代码以及设计报告汇总，按班级学号姓名的形式分目录存储，刻成光盘 上交时间：下学期开学第一周的周一 上交地点：信工楼213软件工程系,Company name,6,四、实习题目,实习一：软件压缩/解压缩软件 Szip（Huffman算法及应用） 要求：首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解码，也就是解压，复原原有文件。 例如：控制台程序命令为： 压缩命令 ：SZip A 1.doc Test.Haf 解压缩命令：SZip X Test.Haf 2.doc 或 SZip X Test.Haf,Company name,7,实习一,基本要求： 压缩准备：读取指定被压缩文件，对文件进行分析，建立哈夫曼树。 压缩：利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。 解压：打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。,Company name,8,实习一（续1）,提高要求： 基于Windows对话框界面，可选择输入/输出文件名，有压缩进度条显示。 解压不必指定文件后缀，自动生成原始文件。 同类型的文件测试不同的数据集，比较其压缩比，采用最有效的压缩方式。 支持多种类型文件的压缩。 试构建程序框架，使其能添加新的压缩/解压缩算法（例如书上LZW压缩算法）,Company name,9,实习一（续2）,测试数据： 约40000字符左右。 示例数据.txt， 80K，采用WinRar压缩后为43K；本算法压缩后约为61K； 示例数据.doc，144K，采用WinRar压缩后为52K。,Company name,10,实习一提示,针对ASCII字符集0,255的频率统计 数据类型采用BYTE或unsigned char 文件一般读取两次：统计与编码 分块读取文件，建议为1K的整数倍 为了获得较好的压缩效率，频率的确定要以大量的统计数字为依据，或者压缩时再动态地统计各字符出现的频率 静态Huffman压缩 动态Huffman压缩,Company name,11,实习一提示（续1）,压缩存储的实现 从字符序列中逐个取出字符，转换为Huffman编码，以位为单位依次存储。 例如：a:0, b:10, c:110; d:1110; e:1111 0100011000111000011110010 需要四个字节的空间， 使用unsigned short存储: 0xFFFF，16位 使用unsigned int存储: 0xFFFFFFFF，32位 使用位操作、移位操作,Company name,12,位操作示例,Int Insertbit (int bit) hufcoded=1； if (bit) hufcoded |=1; if (+bitcounter=8) bitcounter=0; fputc(hufcoded, file); ,一位操作，效率低下,参见JPEG的Huffman代码,Company name,13,实习一提示（续2）,Huffman树的保存: 顺序存储方法,511个结点足够 由于Huffman树是完全二叉树，每个非叶结点都有两个孩子，没有左孩子的结点一定是叶结点。所以，我们实际上只需要rlink字段就能描述我们的Huffman树 可以使用带右链的先根次序储Huffman树： 每个结点需要三个字段 Info是结点的数据，rlink是指右子树的指针，tag标记该结点是否有左子女 当rlink =512时表示它是指向右子树的指针，否则表示一个代码为rlink512的字符的叶结点。这样，约需要511的附加空间用于存储Huffman树。,Company name,14,实习一提示（续3）,解压过程： 把数据从Huffman编码还原到原来的字符编码，也要以位为单位，一位一位地进行。最先从根开始，根据面临的数据位是还是决定走左子树或右子树，走到叶结点就得到一个对应于该叶结点的字符；接着回到根结点，重复以上过程，叶到还原出所有的字符。,0100011000111000011110010 ,Company name,15,实习一提示（续4）,因为最后一字节的有效位可能只占一部分，所以，解码的终止条件应该是”得到所有的字符”而不是把所有的位走完；否则，到达最后一字节的最后一位时，可能走不到叶结点，也可能已经产生了多余的字符。,测试执行时间的函数： #include #include DWORD BegTime=timeGetTime(); . EndTime=timeGetTime()-BegTime;,Company name,16,实习二：动态规划算法的应用,题目：灰度图像压缩/解压缩类的实现 灰度图像的像素值范围在0，255之间，如果采用一个像素一个字节的存储方式，势必会造成空间的浪费。如果采用一定的无损压缩算法，可以大大提高减小文件大小，减少存储空间。 要求：针对提供的256色（8位）位图数据，采用教材上第15章动态规划中图像压缩算法（图像分段合并的思想），设计一个类，实现灰度位图数据的压缩和解压过程。,Company name,17,实习二（续1）,基本要求：完整的灰度图像类应具有以下功能： 1）对8位位图数据的读功能，提供ReadBitmap方法。 ReadBitmap方法有一个参数为输入位图文件名(*.bmp)，它能解析8位位图文件格式，获取位图BITMAPINFOHEADER信息和每个像素的数据信息，放入内存中。 2）对8位位图数据的写功能，提供WriteBitmap方法。 WriteBitmap方法有一个参数为输出位图文件名(*.bmp)，它能将内存中的位图文件信息，按照位图格式，写到位图文件中保存。,Company name,18,实习二（续2）,3）灰度图像压缩功能，提供Compress方法。 Compress方法有一个参数为输出压缩文件名(*.img) 它能将已经装入到内存中的8位位图信息，进行压缩，形成段标题和以变长格式存储的像素的二进制串，写入到文件中（注意：Img文件格式自行定义） 4）灰度图像解压功能，提供UnCompress方法。 UnCompress方法有一个参数为输入压缩文件名(*.img)，它能解析Img文件格式，将其在内存中解压缩为8位位图信息，以便输出为位图文件。,Company name,19,实习二（续3）,测试数据 数字化.bmp，636*455*8 纹理.bmp， 512*512*8 测试示例 类的测试用例如下： CCompressImage Test; Test. ReadBitmap(“数字化.bmp”); 读原始位图 Test. Compress(“Out.img”); 压缩 Test. UnCompress(“Out.img”); 解压 Test. WriteBitmap(“Out.bmp”); 还原位图信息 可使用ACDSee比较其属性信息及文件大小,Company name,20,实习二提示,压缩的步骤 读位图数据，统计分段信息 使用动态规划分段算法，获取空间最优分段 设计合适的文件格式 根据分段合并信息，对位图数据进行不等长的分段二进制位压缩 写入压缩文件 解缩的步骤 形成BITMAPINFOHEADER信息 分段解压像素信息，写入位图,Company name,21,实习二提示（1）,位图文件的格式 BITMAPFILEHEADER BITMAPINFOHEADER 像素信息 注意是沿Y轴镜像！ 灰度位图：BYTE字节流 16位位图：B5G6R5，Blue，Green，Red 24位位图：BGR,BGR, 32位位图：BGRA,BGRA,Company name,22,实习三：动态查找表算法的应用,题目：手机电话簿软件的实现 背景知识： 在很多实际应用中，动态索引结构在文件创建或初始装入记录时生成，在系统运行过程中插入或删除记录时，为了保持较好的检索性能，索引结构本身将随之发生改变。教材上已经介绍的动态查找数据结构包括：二叉搜索树（BST）、平衡二叉树（AVL）、红黑树（RBT）、B-树。 要求：选取一种已经学过的动态搜索树结构（例如使用BST或者AVL），设计并实现一个手机电话薄软件。,Company name,23,实习三（续1）,一个完整的电话簿软件应具有以下功能： （1）支持复式电话簿数据的存储，数据条目不少于500条。 每个人名下可保存的信息包括：姓名、手机号码、住宅电话号码、办公电话号码、电子邮件地址、所属群组、备忘录等。 （2）支持电话簿记录的添加、删除、编辑等操作。 （3）将不同类型的人群按照同事、朋友、家人、商务伙伴等分组，支持群组记录的添加、删除、编辑等操作。,Company name,24,实习三（续2）,（4）支持所有电话簿记录的导入、导出操作，外部数据采用TXT格式。 （5）支持电话簿记录的各种查询操作，具体包括： 逐条翻看 能显示所有的电话簿记录，支持分屏查看。 电话号码查找 输入一个电话号码（手机、住宅、办公），能将包含该号码的电话簿记录显示出来。 人名查找 输入一个人名（全名或者部分名），能将包含该姓名的电话簿记录显示出来。 群组查找 选择一种群组类型，能将属于该群组的所有电话簿记录显示出来。,Company name,25,实习三（续3）,提高要求： （1）系统支持铃声库和图片库的数据存储，提供添加、删除、修改、播放等操作。铃声库和图片库可直接使用文件目录进行管理；铃声格式可使用WAV、MP3或者WMA格式；图片格式可使用BMP、JPG等格式。 （2）电话簿记录信息支持：来电铃声、来电图片等信息，用户可通过界面编辑或者浏览某条电话簿记录的来电铃声、来电图片。 （3）人名查询支持：输入姓名的首字母查找。 （4）使用红黑树或者B-树的数据结构，来实现动态索引结构。,Company name,26,实习三（续4）,测试数据 自动随机生成500-1000条电话簿数据记录。 实习提示 设计合适的电话簿数据文件格式 设计合适的索引文件格式 字符串子串查找函数： CString:FindOneOf char *strstr( const char *string, const char *strCharSet ); 注意大小写！,