课程设计报告--连通问题.docx

《课程设计报告--连通问题.docx》由会员分享，可在线阅读，更多相关《课程设计报告--连通问题.docx（16页珍藏版）》请在优知文库上搜索。

1、第1章课题概述11.1 课题的目的11.2 课题的要求11.2. 1连通的定义11.2.2程序实现的功能要求1第2章概要设计22.1整个程序的运行思路及流程22.2BMP文件格式组成分析22.2.1单色位BMP格式文件头信息22.2.2单色位BMP格式文件位图数据52.3 图片的读入方式及分辨率的获取62.4 图片的“具象化”62.5 5判断连通的方式递归6第3章程序功能的实现83.1 读入图片并获取图片分辨率83.2 获取图片位图数据83.2.1判断图片在储存时的宽度和补位的数量83.2.2将每一个字节的信息正确输入字符串对象93.2.3对获取的字符串对象进行处理93.3 递归调用103.4

2、 将图片以二位数组形式输出（辅助功能）H第4章调试及发现问题的解决13第5章程序测试及分析14第6章总结15参考文献16第1章课题概述本次数据结构课程设计的题目是根据给定的黑白位图，分析出所有独立连通的群体。输出每个连通群体的面积。所谓面积，就是它含有的像素的个数。1.1 课题的目的BMP（全称BitmaP）是WindOWS操作系统中的标准图像文件格式，使用非常广泛。它采用位映射存储格式，图像深度可选lbit,4bit,8bit及24bito由于bmp文件格式是windows环境中交换与图有关的数据的一种标准，因此在WindoWS环境中运行的图形图像软件都支持BMP图像格式。因此在当下，熟练的

3、掌握Ibit的BMP图像文件的格式分析，并简单了解其他图像深度的BMP文件的格式组成，对今后的工作生活都能带来莫大的帮助。连通问题在日常生活中非常常见，例如互联网络，城市交通都属于联通相关的问题。本次课设中借用BMP格式图片求得像素点的连通问题，让我们初步掌握数据结构中图的知识，以高效率计算出图片中连通分量的数量和每一个连通分量的面积。1.2 课题的要求1.2.1 连通的定义in.bmp文件如下：tl.bmp文件如下：产我们可以定义：两个点距离如果小于2个像素，则认为这两个点连通。也就是说：以一个点为中心的九宫格中，围绕它的8个点与它都是连通的。如：tl.bmp所示，左下角的点组成一个连通的群

4、体；而右上角的点都是孤立的。1.2.2程序实现的功能要求根据给定的黑白位图，分析出所有独立连通的群体，输出每个连通群体的面积。所谓面积，就是它含有的像素的个数。第2章概要设计2.1整个程序的运行思路及流程根据课题要求，整个程序大体上可以分为三大步进行：1.读取目标图片获取分辨率；2.读取目标图片获得其位图数据，并以二维数组储存；3.判断连通并将结果输出。载入图片获取位图数据获取图片分辨率将图片“具象为”一个二维数组以二雄败姐形式：输出图形P分析独立连通群体，计算面积输出每个连通群体的面积图2-1整个程序的流程2.2BMP文件格式组成分析BMP文件存储结构的格式可以在Windows中的WINGD

5、Lh文件中找到定义。BMP文件总体上由4部分组成，分别是位图文件头、位图信息头、调色板和图像数据。我们将位图文件头、位图信息头、调色板作为文件的头信息整体分析。而图像数据另作具体分析。在分析文件结构时可以使用到UItraEdit软件，方便我们更加直观地观察和分析BMP文件的组成2.2.1单色位BMP格式文件头信息1 .位图文件头(bitmap-fileheader)位图文件头(bitmap-fileheader)包含了图像类型、图像大小、图像数据存放地址和两个保留未使用的字段。字段名大小(单位：字节)描述bfype2位图类别，根据不同的操作系统而不同，在WindoWS中，此字段的值总为BMbf

6、Size4BMP图像文件的大小bfReservedl2总为0bfReserved22总为0bfOffBits4BMP图像数据的地址(总计14字节)2 .位图信息头(bitmap-informationheader)位图信息头(bitmap-informationheader)包含了位图信息头的大小、图像的宽高、图像的色深、压缩说明图像数据的大小和其他一些参数。字段名大小(单位：字节)描述biSize4本结构的大小，根据不同的操作系统而不同，在WirldoWS中，此字段的值总为28h字节=40字节biWidth4BMP图像的宽度，单位像素biHeight4BMP图像的高度，单位像素biPlane

7、s2总为0biBitCount2BMP图像的色深，即一个像素用多少位表示，常见有1、4、8、16、24和32,分别对应单色、16色、256色、16位高彩色、24位真彩色和32位增强型真彩色biCompression4压缩方式，0表示不压缩，1表示RLE8压缩，2表示RLE4压缩，3表示每个像素值由指定的掩码决定biSizeimage4BMP图像数据大小，必须是4的倍数，图像数据大小不是4的倍数时用0填充补足biXPelsPerMeter4水平分辨率，单位像素/mbiYPelsPerMeter4垂直分辨率，单位像素/mbiClrUsed4BMP图像使用的颜色，0表示使用全部颜色，对于256色位图

8、来说，此值为IoOh=256biCIrlmportant4重要的颜色数，此值为0时所有颜色都重要，对于使用调色板的BMP图像来说，当显卡不能够显示所有颜色时，此值将辅助驱动程序显示颜色（总计40字节）值得注意的是，其中第19-22字节，记录了图片的宽度，而第23-26字节记录了图片的高度，由于我们的程序会有需求得到载入图片的分辨率，因此对这两个部分的读数尤为重要。in.bmpXW J . WWWWil .eeeeeeieh： 020h: 000003h: 0000e04eh: 0000050h: 0060h: 0e70h: e000080h: 0000090h: 000000a0h: 000e

9、0b0h: 00c0h: d0h: 00ee0h: 000f0h:4D 6E 01 00 00 00 00 0000 00 00 00 C3 0E 0000 02 00 00 00 00 00 003E e e ee 28 ee 01 00 ee ee e C3 0E 0 00 02 e FF FF FF FF FF FFFF 01 FF FF FF FFFF 7F 00 00 00 7FFF 7F FF FF FF 7FFF 7E 0F FF FF 7FFF 7E 0F FF FF 7FFF 00 00 00 00 7FFF FF F3 FF BF010eh: FF FF F7 FF BF

10、O110h: FF FF F6 FF BF l20h: FF FF F6 FF BF eeeeei3h: ff ff 07 ff ff eeei4eh: ee if ff ff ff eei50h: FF FF FF FF FFFF FF FF FF FF FF FD FF DD FF DD FFFF FFFFFFFF C3 FD FF FF DF FD FFFF C0 0F FF FF FF FF FF FF FF FF FF FF FF FF FF F3 FEFF F7 7F FF F7 07FF FF FF FFFF FF7F 7F 7F 7E 7F FF FF FF FF FF FF

11、FFFF FFFF FF FF FF FF FF FF FF FF 7F El FF FF FF FF 7F CD FF EF FF FF 7F DO FF FF FF FF 7F Cl FFFF FF FF FF FF FF FF FF FF FF FF FF F8 00 3F F7 FF BF F7 FF BF F6 FF BF F6 0 3FFF FF FD FF DF FD FF DF ElFF C0 7F FF FF FF FF FF FF FFFF F8 ff F7 ee FF F7 7 FF F7 FFFF F 00 00 7F FF FFeeeeeieeh： ff ff ff

12、ff ffFF FF FF FF FF FF FF FF图2-2用UltraEdit打开的in.bmp文件，深色部分前四位为宽度，后四位为高度3 .彩色表/调色板(colortable)之前的54个字节是每张BMP文件所共有的，常见到有这样一种说法：位图文件从文件头开始偏移54个字节就是位图数据了，这其实说的是24或32位图的情况。这也就解释了我们按照这种程序写出来的程序为什么对某些位图文件没用了。彩色表/调色板(colortable)是单色、16色和256色图像文件所特有的，相对应的调色板大小是2、16和256,调色板以4字节为单位，每4个字节存放一个颜色值，图像的数据是指向调色板的索引。可

13、以将调色板想象成一个数组，每个数组元素的大小为4字节。而针对我们这个课程设计所要求的单色图像，其中只有黑白两种颜色，因此调色板中有8个字节。因此对于所有单色图像整个文件头信息部分有62个字节。1.1 2.2单色位BMP格式文件位图数据除开文件头的部分，剩下的全部都是文件的位图数据。在单色位图中每个像素都只用一位保存，其中白色点像素为1,黑色点像素为0。由于位图信息头中的图像高度是正数，所以位图数据在文件中的排列顺序是从左下角到右上角，以行为主序排列的。最后谈谈数据的对齐规则。WindOWS默认的扫描的最小单位是4字节，如果数据对齐满足这个值的话对于数据的获取速度等都是有很大的增益的。因此,BM

14、P图像顺应了这个要求，要求每行的数据的长度必须是4的倍数，如果不够需要进行比特填充(以O填充)，这样可以达到按行的快速存取。这时，位图数据区的大小就未必是图片宽X每像素字节数X图片高能表示的了，因为每行可能还需要进行比特填充。1.3 图片的读入方式及分辨率的获取在这个问题上，我采用两种方法。第一种是采用RanelOmACCeSSRanCIOm类读入文件，然后调用类中的seek()方法，调整开始访问文件的位置。例如在获取图片的分辨率上，就可以seek(18)；直接来到记录图像宽度开始的位置，并一次读入四个字节，来获取图片的宽度。由于在文件内，记录图像宽度及高度的数字是按16进制倒叙存储，所以还需

15、要对读到的数值经过一定处理才能正常使用。第二种是调用Java中专门用于处理图像文件的IInage类，类中有现成的getHeight();和getWidth();方法，直接调用后，可以简单迅速地得到图像分辨率。本次课程设计，我主要以第一种方法展开。1.4 图片的“具象化”对于单色位图，每个像素的表达非0即1,而判断黑色的连通区域，实际上也就是在判断0的连通区域。因此我可以将图片的位图数据一次性读入为一个字符串对象，再根据实际情况对读入的字符串对象做一定的处理。最后将字符串转化为int类型，并且一个个的存入一个与图片等高等宽的二维数组中。由此来完成图片的“具象化二2. 5判断连通的方式一一递归假设在图片中有任意一个起点