《四叉树问题.docx》由会员分享，可在线阅读，更多相关《四叉树问题.docx（12页珍藏版）》请在三一办公上搜索。
1、四叉树问题编写人：张天骥，景宇轩，张华添，刘凤麟，周弋涛，熊林学号：008120040081200500812008120230081202300812030编写时间：09-5-11一、问题描述使用四叉树来存储栅格图像耍求：（1）能够用四叉树存储给定的黑白图像并能显示图像；（2）图像的格式：bmp格式的黑白图像。（bmp格式见文件BMP文件格式说明.p7,那么清零并读取下一个byte）,用处理m的方法给n赋值（易知这里n指（X+i,y+j）处像素的值），与m异或运算，为0那么继续直到循环结束将m值赋给S.value,为I时即图像非全黑/全白）跳出这两层循环并让S.value=2,然后创立四个子
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）（刚好循环到这个在实际像素之外的坐标时），假设yllen,那么直接将m与1比
3、拟，相同那么整个子图像均为白色（由于循环外层y,内层X顺序的缘故，yllen,必然此后的像素均在实际图像外），不同那么无需进一步比拟，直接再分；假设xllen,那么也将m和1比拟，不同的是假设相同就跳到下-行的第一个像素继续比拟，而不是跳出循环再分子图像。输出图像时，本程序仅将具有实际像素的子图像输出（xwid,ytop=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!);voidp
4、op(PLSTPkt)出栈PSTp;if(pkttop=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=wh?w:h;for(k=l;m;m=l,k=l);returnk;PFBTtree(intwidjntheitintIenjinsignedlongintoffset,unsignedlongintsiz
5、e,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
6、(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(ISttop!=NULL)开始构建S=top(lst);pop(lst);xn=S-xxxn,yn表示结点左下角坐标简化程序之用，无其他意义yn=S-yy;if(xnwid/1卜*2.1讨.辿11片1;如果该结点坐标超出实际长宽(是用2M长宽补足的坐标)，默认该结点代表的这些地方都是白色CISC/在实际图像中k=len(int)pow(2Slayer);
7、计算该结点代表的子图像长宽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中，用于以后比拟子图像是否所有像素均为此值Svalue=m;以后跳出循环便利之用,不同还可以再改for(i=0;ihei-l)如果该列超出了实际高度n=l，以
8、下虚拟的像素默认为白色，直接比拟，异或运算，相同为0不同为Iif(mAn)S-value=2;elseS-value=l;break;以下步骤也不必进行j=0；while(jwid-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=
9、O;bytc=fgctc(fp);j+;继续比拟if(S-valuc=2)brcak7果该节点需再分，跳出子图像比拟循环if(S-value=2)for(j=0;jlayer=S-layer+1;层数更高t-xx=S-xx+directionj0*len(int)pow(2,t-layer)ffl子结点的左下角坐标t-yy=S-yydirectionjJ1*lcn(int)pow(2,t-laycr);S-nextj=W/与该结点连接并进栈PUSh(ISt,t);fclose(fp);returnth;voidgotoxy(intx,inty)把光标移到相应坐标COORDc;c.X=x;c.Y
10、=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-xxyylayer);if(Svalu-=1)白色fo(i=0;ixx,hci-liSyy)
11、;文件存储与控制台的纵坐标是颠倒的forg=0yxx+jyy+jvalue=O)黑色fo(i=0;ixx,hci-1-i-S-yy);fbrg=0jl+)PUtChar(*);free(三);else/还有for(i=0;inexti);free(三);Igotoxy(0,hei);intmain(intargc,char*argv)HANDLEhOut;/标准输出句柄CRDSiZeJ/控制台坐标结构hOut=GetStdHandle(STD_OUTPUT_HANDLE);读取控制介句柄CoNSoLE_SCREEN_BUFFER_INFOblnfo;控制台信息结构体GetCOnSOIeSCre
12、enBUfferlnfO(hOut*&bInfo)，获取控制台信息if(bInfo.dwSize.XDEFAULTWIDbnfo.dwSize.YDEFAULTHEI)U/控制台过小，调整至默认值Size-X=DEFAULTWID;Size-Y=DEFAULTHEI;SetConSoIeSCreenBUfferSiZe(hut,size);GetConSoIeSCreenBUfferlnfo(hut,fcblnfo);for(intj=Oyb!nfo.dwSize.Xj+)printf(*);Printfr四叉树存储输出黑白图像演示程序n全组共同设计n张天骥编写tree,out函数，控制台控制
13、代码n刘凤麟编写main函数，界面优化与时间输出的代码n熊林、景宇轩设计栈局部n周弋涛、张华添完成测试n创立日期：09-4-28n最后修改日期：09S21n数据结构存入StdafX.h,运用四叉树与琏栈结构n);for(j=0;jblnfo.dwSizc.XIlheibInf.dwSizc.Y)图像过大，调整控制台SiZC.X=wid+INSURE;sizc.Y=hei+INSURE;SetConsoleScrecnBuffcrSizc(hOut,sizc);tag=l;SyStem(”c1s)/清屏ICn=go(wid,hci);四叉树结构只能处理像素宽高均为为2n的图像，故计算比实际宽高长
14、的最小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保证
15、正常对话，保存图像输出结果)保证输出无误,wid,hei.sizeX,size.Y);Printfr恭喜！程序演示成功!)；PrintfC您想要显示运行时间吗？(1或2)nl是的,我想知道运行多长时间jn2这个不用jn”);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
16、=O;isizc.X;i+)printf(,*,);PrinIf(nCopyright:张天骥，刘凤，熊林，景宇轩，周弋涛，张华添OfPKUSESSAllRightsReserved2023-5-2lnn,r);for(i=O;isize.X;i+)printf(,*,);printf(,);CIoSCHandIC(ht)关闭句柄return0;四、效率分析1 .时间效率最外层栈的循环与图像大小相符，故算法时间仅与图像有关(与几层循环关系不大)。对于实际大小Wid*hci的图像，最好情况图像单-颜色，实际执行Wid*hei次，最坏情况下是当Wid与ICn相同且均为2大小(设为Ien)时，每一层
17、子图像的左下角结点都要重复执行一次，再加上每次进一步细分子节点的时间,即len2*(1141+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. 选取例子：
18、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也应在内层循环的
19、最末而不是最初。己校正。在a、b图像输出时不能完全正确输出，方形边缘锯齿状缺失，线条变粗，调试发现初始计算变量bit时，当公式中数值太大时由于没有括号，强制转换运算符使bit异常，己校正。目前尚未测试出更多异常情况。3. 演示说明详尽活泼的界面,出错有提示,健壮性较强人性化提示界面正确输入原图像AR正确输出创新功能:显示输出bmp图像的时间,实为程序-大亮点！又一亮点:输出控制-自动调节缓冲区大小，无需担忧图片大小过大，用户不必操心六、进一步探讨1. 对于本四叉树图像算法，应当存在更好的方法提高时间效率，在四叉树构建过程中，左下角的相同像素往往因为细分子图像被反复比拟，改良的算法应能解决这问题。2. 对本程序而言，使用九叉树既可以节省空间效率，也能节省时间效率。首先，Ien如果是3“n,而不是2M,将相同图像包括进去所必需的Ien就会更小（如包括25*25的图像，Ien假设为2、就必须是32,而等于3“n时就只需是27）,构建的四叉树中不但虚拟的节点更少，而且由于层数减小，节点也会减少（层数引起的指数级节点减少，比九叉树引起的单层节点增多的速度更快）。同理，节点少了，需要比拟的次数也会更少。从直观上来讲，九叉树更接近于“逐像素构建图像的过程，必然要省略重复比拟过程和多余像素，更加节省时间空间。七、附图：构建四叉树与输出四叉树的流程图结束
