四叉树问题.docx

《四叉树问题.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，以下虚拟的像素默认为白色，直接比拟，异或运算，相同为0不同为Iif(mAn)S-value=2;elseS-value=l;break;以下步骤也不必进行j=0；while(jwid-l)同y,判断横坐标是否超出实际宽度，是那么比拟n=l;if(m