四叉树问题.docx

四叉树问题编写人：张天骥，景宇轩，张华添，刘凤麟，周弋涛，熊林学号：008120040081200500812008120230081202300812030编写时间：09-5-11一、问题描述使用四叉树来存储栅格图像耍求：（1）能够用四叉树存储给定的黑白图像并能显示图像；（2）图像的格式：bmp格式的黑白图像。（bmp格式见文件"BMP文件格式说明.p<r）；对于图像的显示可以分别用两个不同的字符来表示黑点和白点，比方上面的字母'A，可以这样显示：二、问题分析和数据结构算法的设计程序应有三个局部：读取文件头的必要信息，构建四叉树，在控制台输出。三个局部按顺序进行。为了使四叉树能够表示各个子图像的大小，位置，必须要有其左下角的坐标和各级节点的层数，其结构设计如下：typedefstructfour_branches_tree四叉树结构intxx,yy;/结点的坐标，是子图像左下角的坐标，最顶层根节点是（0,0）ShortintIayerM/四叉树层数,可用来计算子图像长宽，顶层为0,表示整个图像ShOrtintValUe;该值为1时表示该子图像的所有像素白色，0为黑色，2那么黑白都有，需要有子结点four_branches_tree*next;连接子结点，仅当value=2时才有，否那么值为NULL）FBT,*PFBT;要处理图像，首先要知道图像中数据的大小size,宽Wid,高hei,bmp文件中文件头的长度（黑白图像为十六进制的3E）每行像素的实际位数为W（W=（SiZe-3E）*8hei,3E是文件头的长度，和SiZe都以字节为单位，故乘以8表示位数），这样才能用坐标方式进行处理。而对于构建四叉树，其根本原理是：图像按四角均分成四块子图像（子图像wid,hei相等且均为2=的大小），每块从该子图像左下角（因为bmp图像数据是从左下角开始一行一行存起的）一行一行比拟像素；均为黑/白时赋值0/1,不均为黑白时，赋值2,并进一步再分为四块，直到子图像均为纯黑/纯白。这个过程中需要递归，但系统栈空间显然缺乏，所以程序用栈结构，其结构如下：typedefstructstacknode以下为链栈，用于构建四叉树和输出（PFBTs;structstacknode*next;ST,*PST;typedefstruct!stackPSTtop;*PLST.LST;先将每次处理时，从栈中取出新节点，假设需再分那么构建四个子结点并将之压入栈中。这是构建二叉树的主循环。由以上概述知，程序最关键的地方在于构建逻辑坐标和实际图像文件中该点像素位置处的映射。而在操作中有两处难点：一，黑白图像一个字节代表一像素，但最小读取单位是byte,所以不但要读该像素所在字节byte,还要读该像素所在字节的bit（0-7）；二，对于非整"n长宽的普通图像，应当将其逻辑上用"白像素"补足为2N长宽的图像，而那些虚拟的像素是不能与文件对应的，构建四叉树时必须考虑这种特殊情况。在理想的宽高都是"n的图像中，设取出栈后的子图像S节点坐标（x,y）（x,y均从0记起），该子图像的宽高为q=hei/QAS.layer）,该节点起始像素在文件中的字节的位置是：B=（x+y*w）8（取整），而在该字节中从左数的位数bit,那么是：bit=（x+y*w）mod8（0-7位），按照这个方法读取该像素位置后，为便于比拟，应将对该像素位操作使该字节其它的像素除去，该像素那么移到本字节最后一位上（让十六进制数m=80右移bit位和byte按位与操作，再将m右移7-bit位），得到m=0或1（黑伯）。然后进行两层循环（设循环变量分别为ij）,从零起均循环q次，每次外层循环重新定位图像该行第个像素B=（x+（y+i）*w）8（取整），bit=（x+（y+i）*w）mod8,内层那么每次都让bit+假设bit>7,那么清零并读取下一个byte）,用处理m的方法给n赋值（易知这里n指（X+i,y+j）处像素的值），与m异或运算，为0那么继续直到循环结束将m值赋给S.value,为I时即图像非全黑/全白）跳出这两层循环并让S.value=2,然后创立四个子结点坐标分别为（S->xx+directionjO*lencal（t->layer）,S->yy+directionj1*lencal（t->layer）（j是-个四次循环的变量，direction=0,0,l,0,0,l,1,1）,layer值是原结点Iayer+1,分别与原结点nextj指针连接。对于长宽度非2=的图像，计算一个"n的Ien作“虚拟长宽"，用同种方法比拟。不同的是，当整个子图像在实际图像之外时（x>=wid,y>=len）,将其当成白色处理（即赋S.value=l仅仅是局部"像素"在实际图像时，对于该像素（xl,yl）（刚好循环到这个在实际像素之外的坐标时），假设yl>len,那么直接将m与1比拟，相同那么整个子图像均为白色（由于循环外层y,内层X顺序的缘故，yl>len,必然此后的像素均在实际图像外），不同那么无需进一步比拟，直接再分；假设xl>len,那么也将m和1比拟，不同的是假设相同就跳到下-行的第一个像素继续比拟，而不是跳出循环再分子图像。输出图像时，本程序仅将具有实际像素的子图像输出（x<wid,y<len）。为遍历各个节点，需再次用到栈（具体略）。对于每个应输出的子图像，其各个像素（xl,yl）,Xl对应于控制台原坐标位置，yl那么输出在y2=hei-l-yl-i（i指该像素在图像第几行，这个变换是因为控制台的坐标以左上角为原点）。流程图见报告后三、程序设计/FCT.cpp:Definestheentrypointfortheconsoleapplication.四叉树存储输出黑白图像演示程序/组员：张天骥（组长）、张华添、周弋涛、熊林、刘凤麟、景宇轩程序全组共同设计，张天骥编写tree,out函数，控制台控制代码，刘凤麟编写main函数，界面优化与时间输出的代码，熊林、景宇轩设计栈局部，周弋涛、张华添完成测试。创立口期：09-4-28,最后修改日期:09-5-21数据结构在stdafx.h中，用到四叉树与链栈结构#includc"stdafx.h"#include"stdio.h"include"windows.h"includc"maJloc.h,'#include"stdlib.h"#include"time.h"#includc"math.h"#defineTRUE1#defineINSURE20用于调节控制台大小时加额外大小，确保图像输出结果保存#defineDEFAUErWlD80#defineDEFAULTHE1300控制台窗口默认大小80*300PLSTCreateSi()建栈PLSTplst=(PLST)malloc(sizeof(LST);if(st)puts(,NoSpace,);returnNULL;Ielseplst->top=NULL;returnplst;voidpush(PLSTplst,PFBTx)进栈PSTp;p=(PST)malloc(sizeof(ST);if(p!=NULL)p->s=x;p->next=plst->top:plst->top=p;)dseputs(,TULL!);voidpop(PLSTPkt)出栈PSTp;if(pkt>top=NULL)puts("Empty");elsep=plst->top:plst->top=plst->top->ncxt;frec(p);PFBTtop(PLSTkt)取栈顶元素if(1st->top=NULL)puts(mEmptyn,');return(lst->top->s);intgo(intw,inth)计算leu,Ien见说明intm,k;m=w>h?w:h;for(k=l;m;m»=l,k«=l);returnk;PFBTtree(intwidjntheitintIenjinsignedlongintoffset,unsignedlongintsize,charfilename)WOffSet是文件中图像数据到开头的长度，这是用来读取图像内容的intXn=O,yn=0,w,direction=O,O,l,O,O,l,1,1;同迷宫问题，构建图像的循环要用FILE*fp;BYTEm,n,byte;BYTEbit;/m是子图像左下角像素值m是子图像某像素的值,byte是某像素位与文件中的字节,bit是该像素在byte中左数第几位intij,k;循环longintB;/PFBTth.S,t;PLST1st;)st=createst()/创立栈if(lst=NULL)Printfe栈建立失败!")；returnNULL;th=(PFBT)malbc(sizeof(FBT);/初始化根节点th->xx=O;th->yy=O;th->layer=O;S=th;W=(SiZe.0x3E/8/hei;每行在文件中的实际宽度push(lst,th);fp=fbpcn(filename,',r");WhilC(ISt>top!=NULL)开始构建S=top(lst);pop(lst);xn=S->xxxn,yn表示结点左下角坐标简化程序之用，无其他意义yn=S->yy;if(xn>wid/1卜*2.1讨.>辿11片1;如果该结点坐标超出实际长宽(是用2M长宽补足的坐标)，默认该结点代表的这些地方都是白色CISC/在实际图像中k=len(int)pow(2S>layer);"计算该结点代表的子图像长宽B=(Iong)(Xn+yn*w)/8;"左下角像素对应文件中该字节的位置bit=(BYTE)(xn+yn*w)%8);"左下角像素对应该字节的第几位，从左往右0-7位的哪位？fscck(fp,B+offsct,SEEK_SET);校正位置，读取字节byte=fgetc(fp);m=0x80;/(l(X)OOOOO)binarym>>=bit;m=m&byte;m>>=7.bit;这几个位运算是只把左下角该像素值保存，移到m中，用于以后比拟子图像是否所有像素均为此值S>value=m;以后跳出循环便利之用,不同还可以再改for(i=0;i<=kl;i+H子图像列洌的循环B=(Iong)(Xn+(yn+i)*w)/8;与上类似，读取子图像该列第一个像素位置bit=(BYTE)(xn+(yn+i)*w)%8);fseek(fp,B÷offset,SEEK-SET);byte=fgetc(fp);if(yn+i>hei-l)如果该列超出了实际高度n=l，以下虚拟的"像素"默认为白色，直接比拟，异或运算，相同为0不同为Iif(mAn)S->value=2;elseS->value=l;break;以下步骤也不必进行j=0；while(j<k)(行的循环if(xn+j>wid-l)同y,判断横坐标是否超出实际宽度，是那么比拟n=l;if(mAn)S->value=2;elsej=0;break;不同的是这里仅跳出该行的循环n=0x80;n>>=bit;n=n&byte;n>>=7-bit11Jm,读取该像素值并移位使之仅可能为0,1if(mn)"与m不样！需要进步分子结点与子图像S->value=2;break;跳出elsebit+=1;/找下一位像素if(bit=8)/超出该字节，读下个字节bit=O;bytc=fgctc(fp);j+;"继续比拟if(S->valuc=2)brcak7果该节点需再分，跳出子图像比拟循环if(S->value=2)for(j=0;j<=3;j+)t=(PFBT)mallOC(SiZeOf(FBT);为value=2的结点创立子结点if(-NULL)Printfc栈建立失败!")；returnNULL;t->layer=S->layer+1;层数更高t->xx=S->xx+directionj0*len(int)pow(2,t->layer)ffl子结点的左下角坐标t->yy=S->yy÷directionjJ1*lcn(int)pow(2,t->laycr);S->nextj=W/与该结点连接并进栈PUSh(ISt,t);fclose(fp);returnth;voidgotoxy(intx,inty)把光标移到相应坐标COORDc;c.X=x;c.Y=y;SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLEXc);voidOut(PFBTheadJntIenJntWidjnthei)PLST1st;PFBTS;intiJ；lst=createst();if(lst=NULL)Printf(”对不起，数据溢出W请腾出局部内存并重新启动程序n“)；exit(O);push(lst,hcad);WhiIC(ISt->top!=NULL)同以上栈的方式S=Iop(Ist);pop(lst);if(S->xx<=wid-l&&S->yy<=hci-l)l=lcn(int)pow(2,S->layer);if(S>valu-=1)"白色fo(i=0;i<l;i+)gotoxy(S->xx,hci-liS>yy);文件存储与控制台的纵坐标是颠倒的forg=0y<I÷+)if(S->xx+j<=wid-l&&S->yy+j<=hci-)putchar('');fx(三);出栈后立即释放空间，节省时间elseif(S>value=O)黑色fo(i=0;i<l;i+)gotoxy(S->xx,hci-1-i-S->yy);fbrg=0j<l+)PUtChar('*');free(三);else/还有for(i=0;i<=3;i+)push(lst,S->nexti);free(三);Igotoxy(0,hei);intmain(intargc,char*argv)HANDLEhOut;/标准输出句柄CRDSiZeJ/控制台坐标结构hOut=GetStdHandle(STD_OUTPUT_HANDLE);读取控制介句柄CoNSoLE_SCREEN_BUFFER_INFOblnfo;控制台信息结构体GetCOnSOIeSCreenBUfferlnfO(hOut*&bInfo)，获取控制台信息if(bInfo.dwSize.X<DEFAULTWIDbnfo.dwSize.Y<DEFAULTHEI)U/控制台过小，调整至默认值Size-X=DEFAULTWID;Size-Y=DEFAULTHEI;SetConSoIeSCreenBUfferSiZe(hut,size);GetConSoIeSCreenBUfferlnfo(hut,<fcblnfo);for(intj=Oy<b!nfo.dwSize.Xj+)printf("*");Printfr四叉树存储输出黑白图像演示程序n全组共同设计n张天骥编写tree,out函数，控制台控制代码n刘凤麟编写main函数，界面优化与时间输出的代码n熊林、景宇轩设计栈局部n周弋涛、张华添完成测试n创立日期：09-4-28n最后修改日期：09S21n数据结构存入StdafX.h,运用四叉树与琏栈结构n");for(j=0;j<blnfo.dwSize.Xj+)pritf("*");FILE*fp;/文件指针charfilename100;intC;/供用户选择所用intwid,hci,lenwid,hci图像宽度高度，Ien大小足以包含图像的边长为2的方嘉正方形边长BITMAPFILEHEADERfile;/文件头结构BITMAPINFOEfo:"文件头信息类型PFBTheM;"四又树根节点Primfr四叉树存储输出单色bmp位图演示开始：n");Ioopl:标记1,用以用户选择时进入Printf("请输入完整文件路径:n");whilc(TRUE)scanf("%s",filename);fpfopen(filename,"r");if(!fp)(Printf("对不起您输入的文件不存在哦(，)rn");IOCP:/标记，用以用户选择时进入Printf("您可以选择：(1或2)nl我现在去创立吧！S2算j'n");/用户选择控制scanf(,%d'fC);if(C=l)Printfr您选择的是ln创立好/之后请输入路径：n,);if(C!=l)Printf(”您选择的是2n");break;continue;GetCOnsoleSCreenBUffeIinfo(hOut,&blnfo);获取缓冲区信息time_tstart,finish;/time_t变量用以存储开始和完成的时间点Start=CIoCk();/获取系统时间fread(&f1le,sizeof(BlTMAPFlLEHEADER),l,fp);读取图像文件头信息fread(&info,sizeof(BITMAPINFO),l,fp);fclose(fp);if(file.bfType!=0x4D42)标准黑白bmp格式Printfc文件并非标准黑白bmp格式!r);gotoloop;SCanfc%d”,&C);if(C!=l)break;continue;Iif(info.bmiHeaderbiBitCount!=l)假设非bmp黑白图像Printf("非黑白图像!n");gotoloop;scanf(,%d,C);if(C!=l)brcak;continue;Wid=info.bmiHcader.biWidth;实际图像宽度(X轴的像素数)hei=info.bmiHcader.biHeighi;/实际高度inttag;标记缓冲区在输出图像过程中是否被调整tag=O;if(wid>blnfo.dwSizc.XIlhei>bInf.dwSizc.Y)图像过大，调整控制台SiZC.X=wid+INSURE;sizc.Y=hei+INSURE;SetConsoleScrecnBuffcrSizc(hOut,sizc);tag=l;SyStem(”c1s")/清屏ICn=go(wid,hci);"四叉树结构只能处理像素宽高均为为2n的图像，故计算比实际宽高长的最小2n"像素数"以便生成四叉树head三=tree(wid,hciJen,file.bfOffBits,f11c.bfSize,fUename);/开始计算,返回的是树的根结点if(hcad=NULL)Printfe图像创立失败!5")；gotoloop1;OlH(headJen、Wid,hei);输出finish=clock();获取输出结束时间doubleduration=(doble)(finishstart)/CLoCKS_PER_SEC;输出所用总时间if(tag)Printf(”您的bmp文件为%d*%d像素n图像超出控制台大小，不用担忧，我们己将控制台调至%d*%d(长宽加20保证正常对话，保存图像输出结果)保证输出无误,wid,hei.sizeX,size.Y);Printfr恭喜！程序演示成功!")；PrintfC您想要显示运行时间吗？(1或2)nl是的,我想知道运行多长时间jn2这个不用j'n”);scaf("%d,tC);if(C=l)Printfe输出运行花了%f秒二duration);Printf(”n您还想要：(1或2)nl我还要继续输出图像112使用完毕U就到这吧。n");SCanf(”d&C);if(C=l)Printfe您选择的是15”)；gotoloop1;转至标记1if(C!=l)break;PrintfC感谢使用本程序，祝您愉快！W)；for(inti=O;i<sizc.X;i+)printf(,*,);PrinIf("nCopyright:张天骥，刘凤，熊林，景宇轩，周弋涛，张华添OfPKUSESSAllRightsReserved2023-5-2lnn,r);for(i=O;i<size.X;i+)printf(,*,);printf(,');CIoSCHandIC(ht)关闭句柄return0;四、效率分析1 .时间效率最外层栈的循环与图像大小相符，故算法时间仅与图像有关(与几层循环关系不大)。对于实际大小Wid*hci的图像，最好情况图像单-颜色，实际执行Wid*hei次，最坏情况下是当Wid与ICn相同且均为2"大小(设为Ien)时，每一层子图像的左下角结点都要重复执行一次，再加上每次进一步细分子节点的时间,即len2*(1÷141+l4n)+(4+42+4z5),所以时间效率应为O(len2)o输出局部亦应是O(len2)2 .空间效率涉及一个四叉树空间和栈空间。每个节点大小为m,最坏情况下对于Ien的最大层数Iayer(即2layer=len),每层都有子节点(除了最下层)，那么占用空间m*(l+4l+4*2+4*3+4layer),空间效率O(m*4(laycr+l),最好情况易知为O(m)。对于栈(节点大小n),由于只有最下层才有展开，故每层节点仅有三个，最坏情况0(3*n),最好情况0(n)o五、测试分析1. 选取例子：asd2（图像宽高能否正确反映）asd3（2n宽高的图像能否正确反映图像根本大小、位置）asd4（2人n宽高的复杂图像能否正确反映）asd（小图像能否正确反映）a、b（大图像能否正确反映）2. 测试经过：在asd3测试通过的图像，asd中显示混乱图像，经调试发现W的计算有误（原来的W在Wid整除8时为wid,不整除时为Wid用两个字节补足，后来发现bmp文件不完全是这么存储的），己校正，W计算方法见上。在asd2中最左端出现多余星号，发现图像输出函数的内部循环次数不对，己校正。在asd4中圆圈的局部边缘缺失，发现构建函数最内层循环的j应由O循环到k而非1到k,检验bit是否为8也应在内层循环的最末而不是最初。己校正。在a、b图像输出时不能完全正确输出，方形边缘锯齿状缺失，线条变粗，调试发现初始计算变量bit时，当公式中数值太大时由于没有括号，强制转换运算符使bit异常，己校正。目前尚未测试出更多异常情况。3. 演示说明详尽活泼的界面,出错有提示,健壮性较强人性化提示界面正确输入原图像A°R正确输出创新功能:显示输出bmp图像的时间,实为程序-大亮点！又一亮点:输出控制-自动调节缓冲区大小，无需担忧图片大小过大，用户不必操心六、进一步探讨1. 对于本四叉树图像算法，应当存在更好的方法提高时间效率，在四叉树构建过程中，左下角的相同像素往往因为细分子图像被反复比拟，改良的算法应能解决这问题。2. 对本程序而言，使用九叉树既可以节省空间效率，也能节省时间效率。首先，Ien如果是3“n,而不是2M,将相同图像包括进去所必需的Ien就会更小（如包括25*25的图像，Ien假设为2、就必须是32,而等于3“n时就只需是27）,构建的四叉树中不但虚拟的节点更少，而且由于层数减小，节点也会减少（层数引起的指数级节点减少，比九叉树引起的单层节点增多的速度更快）。同理，节点少了，需要比拟的次数也会更少。从直观上来讲，九叉树更接近于“逐像素构建"图像的过程，必然要省略重复比拟过程和多余像素，更加节省时间空间。七、附图：构建四叉树与输出四叉树的流程图结束