数据结构报告——08.doc

数据结构程序设计院 系： 计算机科学学院 专 业： 网络工程 年 级： 2008 课程名称： 数据结构 学 号： * 姓 名： * 指导教师： * 2009年 月 日骑士周游世界一 、 需求分析本程序用来完成将马放在国际象棋的88棋盘方格中，马按走棋规则进行移动，每个方格只走一次，走遍棋盘上的全部64个方格，寻找出路线。输入的形式及数据范围（1） 以二维数组boardij，表示棋盘上的每一格，初始时将数组初设为零，之后在程序中若此位置进入路径中，则被设置为与路径相对应的数值若数组所有的元素都被设为某一个数值，说明有一条通路，就结束了寻找，就输出整个数组，得到一条通路。（2） 路径入口可以用户自己定义，程序的开始会提示用户输入行与列。（3） 若存在路径，程序会输出一个88的数据，数据是从1到64，从入口设定为第一步，之后会一直顺着数字到64结束；若不存在路径，程序会输出英文：wrong! 说明没有这一条通路。（4） 本程序只能输出一条通路，还需要进一步改进。二、 详细设计 int boardnn=0; stack horsesqn;/设置栈结构，其中sqn为64 int top=0;/栈顶 int a8=-2,-1,1,2,2,1,-1,-2; int b8=1,2,2,1,-1,-2,-2,-1;/a与对应的b组成了马走一步的八个路径 int i,j,u,v; horsetop.x=i; horsetop.y=j;/i与j为起始坐标 horsetop.k=0; top+; boardij=top; int m=0; int flag; while(top!=0&topsqn)/若栈不空且栈中数据没有到64 i=horsetop-1.x; j=horsetop-1.y; flag=0; while(m=0&u=0&vn&boarduv=0)/如果此位置在棋盘内且没有重复 flag=1; boarduv=top+1; else m+; if(flag=1)/找到了正确位置，入栈 horsetop.x=u; horsetop.y=v; horsetop.k=m; top+; m=0; Else/没有找到正确位置 top-; m=horsetop.k+1;/将位置设为上一个错误位置的下一个路 boardhorsetop.xhorsetop.y=0;/如果不能走，则退到前一步 三、 调试分析1、 程序不是很大，但是在调试时发现运行的时间较长，占用CPU比较大，若出现了死循环，则需要细心地去寻找，原因大概是在回退时没有掌握好下一步的位置，则不会有正确的结果。2、 保持良好的编程习惯，要在合适的时候分行，便于修改的时候查错。3、 可以用双斜杠将多个不同功能的函数分开，便于检查。4、 在多个语句嵌套时应该注意花括号的范围，不要把变量放错了位置。四、 测试结果输出截屏五、 课程设计总结1、 骑士周游世界，又叫作马踏棋盘，确实是个很有趣的程序，通过写这个程序，我们确实深入了解了栈的作用，以及入栈出栈的时机和效果。2、 循环中也有窍门，不可没有循环出口，否则会得不到正确的结果，给自己也会带来不好的感觉。3、 调试不成功，不能钻牛角，要及时向别人请教，不然一个很小的错误就能困扰好几天！哈夫曼树及编码哈夫曼树又称最优二叉树，是树的带权路径长度最短的二叉树。而哈夫曼编码就是给哈夫曼的每一个叶子节点赋予一个特定的1与0组成的密码，可以将叶子所代表的数据编成密码，反过来也可将一串1、0组成的密码翻译回数据串。一、需求分析根据用户提供的字符和其权值，建立一个哈夫曼树，并且将每个字符对应的哈夫曼编码求出来，还要对用户给出的密码进行翻译操作。哈夫曼树的储存结构为二叉树类型，编码则存在字符串数组中。二、概要设计 1、抽象数据类型:typedef struct /定义结构体储存哈夫曼树中的叶子字符 int wgt;/字符的权值 int pat,lc,rc;/字符的父亲节点，左孩子和右孩子htnode,*hufft;/定义中有一个指针类型用来动态分配空间char c20;/用来存放各个字符2、主程序void main() hufft tree;/哈弗曼树 char* code20;/用来存放与字符对应的哈夫曼编码 char ch100;/储存密码 int num,n20,i; coutnum; cout输入各个字符：; for(i=1;ici; cout输入各个字符对应的权值：; for(i=1;ini; huffmancoding(tree,code,n,num); /建立哈夫曼树和找出哈夫曼编码，输出哈夫曼树的终态和编码 coutch; translate(ch,tree,num,c);/根据输入的密码翻译为字符串并输出 coutendl; system(pause);三、详细设计1、 构造哈夫曼树和编码void huffmancoding(hufft &ht,char* hc20,int w20,int n) int m,i,s1,s2; m=2*n-1;/m为根结点 ht=new htnodem+1; hufft p; for(p=ht+1,i=1;iwgt=wi;p-pat=0;p-lc=0;p-rc=0;/构赋空值 for(;iwgt=0;p-pat=0;p-lc=0;p-rc=0; for(i=n+1;i=m;i+) select(ht,i-1,s1,s2);/在ht1.i-1中选择pat为0且wgt最小的两个结点 hts1.pat=i;hts2.pat=i; hti.lc=s1;hti.rc=s2; hti.wgt=hts1.wgt+hts2.wgt; for(i=1;i=m;i+) couthti.wgt hti.pat hti.lc hti.rcendl;/输出哈夫曼树 char* cd; cd=new charn; cdn-1=0; for(i=1;i=n;i+)/从叶子到根逆向求每个字符的哈夫曼编码 int start,c,f; start=n-1; for(c=i,f=hti.pat;f!=0;c=f,f=htf.pat) if(htf.lc=c)/若为左孩子 cd-start=0;/编为0 else/否则编为1 cd-start=1; hci=new charn-start; strcpy(hci,&cdstart);/将编码存入hc数组中 for(i=1;i=n;i+) coutci hciendl;/输出所有字符的编码 delete cd;2、 翻译密码void translate(char c100,hufft &ht,int n,char zimu20) int i,t=2*n-1;/t指向最后一个也就是根结点 for(i=0;ci!=0;i+) if(ci=0)/如果是0就往左走 t=htt.lc; else/否则为1往右走 t=htt.rc; if(htt.lc=0&htt.rc=0)/找到字符了就输出 coutc2，其中弧的权值为w int lo1,lo2; anode *p; lo1=locate(g,c1); lo2=locate(g,c2);/确定c1、c2在图g中的位置 adda(g.listlo1.first,lo2,w); adda(g.unlistlo2.first,lo1,w); /将该弧加在邻接表和逆邻接表的lo1、lo2的位置，w为权值2、找出各个顶点的最早和最晚发生时间，以最早为例void finde(vnode a,int head,int n);/找到第head顶点的最早开始时间，存在数组n中 anode *p; int b; if(ahead.first) for(p=ahead.first;p;p=p-next) b=nhead+p-wgt; if(np-adjadj=b; finde(a,p-adj,n);/指向下一个顶点（p-adj），递归 void earlytime(agraph a,int m)/找出图a中各个顶点的最早发生时间，储存在数组m中 int lo(vnode v,int n); int begin; begin=lo(a.unlist,a.vnum);/定出入度为0的顶点，从这里开始找最早开始时间 finde(a.list,begin,m);3、找出由关键点组成的关键路径并输出void showroad(vnode v,int a,char out,int outn,char c,int cn)/将储存关键顶点的c数组在顶点结构v中组成关键路径输出，并且储存在数/组out中 bool have(char c1,char c2,int c3); int i,jn=outn; char j20; for(i=0;ioutn;i+) ji=outi;/为了不破坏数组out的值，开始时用j数组代替out anode *p; if(!va.first)/递归出口，找到了出度为0的点，也就是最后的点 for(i=0;ioutn;i+) coutouti; coutnext) if(have(vp-adj.data,c,cn) /若顶点p-adj中的字符在关键点中，就要加入到路径中 jjn+=vp-adj.data; showroad(v,p-adj,j,jn-,c,cn); /递归输出路径，可以输出多条路径 四、调试分析1、 本次程序由于加入了指针，因此要注意指针是否为空的问题，若是指向空而改变指针所指的数据的值，程序会报错，在程序的调试阶段我也遇到了这样的问题，找出来费了好大的劲，还有由于结构比较复杂，有时在双层或多层结构时一不小心就会出现问题。2、 本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。3、 在函数内部有时需要多定义参数，注意参数的作用域，而且注意传引用调用和传值调用的区别，不能不正确的修改实参的值，否则会导