********
大学********学院
《数据结构与C语言综合训练》实习报告
题 目：“随机漫步”(Rand Walk)模拟演示系统
学 号 姓 名 专业班级 指导教师 实践日期
******** ******** ******** ******** ********
目 录
一、综合训练目的与要求 ..................................................................................................................... 1 二、综合训练任务描述 ......................................................................................................................... 1
(1)、任务描述 ........................................................................................................................................ 1 (2)、设计目的 ........................................................................................................................................ 1 (3)、基本要求 ........................................................................................................................................ 1
三、算法设计 ......................................................................................................................................... 2
(1)、文字描述 ........................................................................................................................................ 2 (2)、框图 ................................................................................................................................................ 2 (3)、伪代码 ............................................................................................................................................ 3 (4)、复杂度分析（选作） .................................................................................................................... 4
四、详细设计及说明 ............................................................................................................................. 4
(1)、主要结构体 .................................................................................................................................... 4 (2)、主要函数 ........................................................................................................................................ 4
五、调试与测试 ..................................................................................................................................... 5
(1)调试分析 ............................................................................................................................................ 5 (2)测试结果截屏及说明 ........................................................................................................................ 5
六、实习日志 ......................................................................................................................................... 7 七、实习总结 ......................................................................................................................................... 9 八、附录：核心代码清单 ..................................................................................................................... 9
(1)MAIN.cpp........................................................................................................................................... 9 (2)RandWalk.h ........................................................................................................................................ 9 (3)Operation.h ....................................................................................................................................... 10 (4)Simulate.h ....................................................................................................................................... 11
dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《C语言程序设计(C99版)》和《数据结构》课程后进行的综合练习。 本课综合训练的目的和任务： 1. 巩固和加深学生对C语言程序设计和数据结构课程基本知识的理解和掌握； 2. 培养利用数据结构知识解决实际问题的能力； 3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； 4. 掌握书写算法设计说明文档的能力； 5. 提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 (1)、任务描述 有一类问题总称为“随机漫步”(Random Walk)问题，这类问题长久以来吸引着数学界的兴趣。所有这些问题即使是最简单的解决起来也是极其困难的。而且它们在很大程度上还远没有得到解决。一个这样的问题可以描述为： 在矩形的房间里，铺有n×m块瓷砖，现将一只（醉酒的）蟑螂放在地板中间一个指定方格里。蟑螂随机地从一块瓷砖“漫步”到另一块瓷砖（可能是在找一片阿司匹林）。假设它可能从其所在的瓷砖移动到其周围八块瓷砖中的任何一个（除非碰到墙壁），那么它把每一块瓷砖都至少接触一次将花费多长时间？ 虽然这个问题可能很难用纯粹的概率技术来解决，但是使用计算机的话却十分容易。使用计算机解决此问题的技术称为“模拟”。这种技术广泛应用于工业中，用来预测运输流量，存货控制等等。 现在，利用所学的C语言程序设计和数据结构基础知识，建立一个“随机漫步”(Random Walk)模拟演示系统，并将得到的模拟结果(模拟产生的数据)保存，以供研究使用。 (2)、设计目的 利用二维数组解决复杂的实际问题；了解实际问题到计算机问题的转化；了解算法设计中边界条件的重要性。 (3)、基本要求 程序必须满足： ①能够处理所有的n和m值, n和m满足：2 0 && e.position.y + jmove[iTemp] > 0 && 3 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 e.position.x + imove[iTemp] <= e.tile.width && e.position.y + jmove[iTemp] <= e.tile.length) { //先判断要移动的位置是否合法，如果合法；改变位置，即蟑螂运动了 e.position.x += imove[iTemp]; e.position.y += jmove[iTemp]; e.iteration++; //记录蟑螂移动到方格的总次数 if(!e.tile.array[e.position.y - 1][e.position.x - 1]) e.passed++; //记录蟑螂已到过瓷砖方格的次数 e.tile.array[e.position.y - 1][e.position.x - 1]++;//统计该瓷砖方格被蟑螂走过的次数 }//if if(e.passed == e.tile.width*e.tile.length || e.iteration == ITERATIVE_MAX) break;//如果所有的瓷砖均已走过或是达到迭代极限条件，退出模拟系统 }//while }// manage (4)、复杂度分析（选作） 由于本系统是通过随机数的产生进行的模拟演示，时间复杂度与随机数的产生相关；至于空间复杂度，仅与用户输入的房间大小等信息相关。 四、详细设计及说明 (1)、主要结构体 struct coordinate { //功能；确定对象的坐标位置 int x,y; }; struct layout {//功能：表示矩形的房间,并将模拟得到的数据保存于二维数组中 int length,width; int **array;//二维数组计数器 }; struct situation { //功能：表示当前时刻模拟系统所处的局面情形 struct layout tile; //漫游布局 struct coordinate position; //对象所处位置 int passed; //已走过的瓷砖数目 int iteration; // 迭代 }; (2)、主要函数 void InitSituation(struct situation &e); //初始化房间的瓷砖方格的布局情况以及蟑螂初始位置 void manage(struct situation &e); 4 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 //主要的演示模拟过程，得到演示数据 void dispalyFormateLayout(struct layout e); //将得到的二维数组中的数据格式化输出 五、调试与测试 (1)调试分析 程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。 在对“随机漫步”(Random Walk)模拟演示系统进行设计的过程中，主要遇到的是在动态申请内存时总是忽略及时将其释放掉；随着所写程序不断深入变得复杂时，造成的困难就愈明显，在查找Bug时费神费力。 在另一方面，由于我写了多个程序，我想把多个程序集合到一个程序中去，这其中遇到了许多的困难。还有，在读取文件和保留文件时也出现了在平时编程写代码过程中没有遇到的错误现象。但在不断地耐心逐行调试中将问题解决。 (2)测试结果截屏及说明 ①在Code::Blocks10.05环境下：工程RandomWalk （图1：开始界面：演示说明） 5 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 如图1所示，在RandomWalk工程中，运行后将出现一个菜单，以供用户选择模拟演示操作。菜单包含“演示说明”、“模拟演示”、“动态演示”三大部分，根据用户的兴趣与需求进行相应的选择。 其中，两个动态模拟演示过程演示1、演示2直接调用工程RandomWalk_ULTIMATE和Multi_RandomWalk生成的内容。 模拟演示过后，系统会将演示得到的结果数据存到RandomWalk_Data.dat文件中，以供研究人使用该数据。 (图2：模拟结束后，将得到的演示数据显示出来) ②在Visual Studio 2005环境下：工程RandomWalk_ULTIMATE和Multi_RandomWalk 为了更加形象生动地体现模拟效果，使用动态效果将是一个很好的选择。工程RandomWalk_ULTIMATE所编写的程序就是将Code::Blocks10.05环境下编写的程序窗口化，并依托Visual Studio 2005中的一些关于时间控制的类从而实现了动态演示。效果很明显，不与以往只有数据的单调。 当然，在之前所编写代码中，我们只考虑了一只蟑螂“随机漫步”的情况。如图3所示，我编写了一个有五只蟑螂的情况。与只有一只蟑螂相比，虽然难度并没有增加多少，但增加了许多趣味性。 6 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 (图3：动态模拟演示的界面) 六、实习日志 2011年7月8日 星期五 根据自己的兴趣和编程能力，选取了“随机漫步”(Random Walk)模拟演示系统作为本次的实习课题。“随机漫步”(Random Walk)模拟演示系统课题并不困难，在白天的实习中已经实现了算法的核心部分，晚上完善了所有的功能函数。 2011年7月9日 星期六 在指导教师蔡骋老师的指导下，开始研究如何在Visual Studio 2005环境下，并利用C++编程尝试实现“随机漫步”(Random Walk)的动态演示。由于基础知识匮乏，不了解C++面向对象的概念，在尝试的过程中困难重重。整天的努力都没有取得实质性的进展。 2011年7月10日 星期日 上午在网络上收集了大量的关于图像处理与Windows编程的相关资料，并专心阅读 7 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 理解。下午又开始尝试编程实现“随机漫步”(Random Walk)的动态演示，取得了一些小进展，已经能够将蟑螂所在房间瓷砖格子显示出来。 期间，我还和同学们共同讨论了编程实现n元多项式的构造、加乘问题；并对n元多项式的构造提出了自己的见解。 2011年7月11日 星期一 今天很开心，终于实现了“随机漫步”(Random Walk)的动态演示。不过所编写的代码有待优化，界面设计几乎没有。但模拟的蟑螂终于在屏幕上动起来了，感觉挺炫的。 还有一点，我开始考虑如何利用读取文件的方式保存模拟演示中所产生的数据。我也收集了大量关于“Random Walk”的文献，想对“随机漫步”(Random Walk)模型做进一步的探索。但所得文献均为英文，阅读起来特别困难，但收获还是很大的，至少有多认识了许多英语单词。 2011年7月12日 星期二 经过一天的努力，终于编程实现“随机漫步”(Random Walk)的动态演示。但是感觉系统的演示功能太少了，演示给同学们看后，听取了他们的意见，开始尽自己的所能，向系统中添加功能。可是，“书到用时方恨少，事非经过不知难”，脑海中有着许多的构思，编程实现感觉很无助，理不清头绪。这迫使我不断的收集资料，阅读。 在分析自己编写的代码中，还发现了自己一个很不好的编程习惯，我老是忘记将申请的内存及时的释放；结果，代码运行的过程中死机了好几次，还找不出缘由。这浪费了很多的时间。 2011年7月14日 星期四 在实习中发现了一个更好的实现“随机漫步”(Random Walk)的动态演示的方法，并实现之。前几天编写的代码都只考虑房间的瓷砖方格中只有一只蟑螂的情况，现在，我增加了四只蟑螂在我的模拟系统中。感觉编写的代码与只有一只蟑螂的情况没有什么大的区别，不过这样可以很快的完成演示过程。一只蟑螂走完全部方格花费的时间还是很长的。 2011年7月15日 星期五 由于大部分的代码已经完成，我开始从数学的角度开始研究分析“随机漫步”问题。我试图利用模拟产生的数据来构思一个算法来绘制出相应的数据分布图。可是，现在的我缺乏线性代数、概率论和Matlab编程等基础知识，忙活了一天也没有什么收获。看别人写的论文也只是一知半解，阅读英文文献倍感吃力。 2011年7月16日 星期六 开始写和补充实习报告和“随机漫步”(Rand Walk)模拟演示系统的课程论文。整理资料和自己所写的代码。并对此次实习做出了总结。 2011年7月17日 星期日 为还没有完成实习课题的同学提供了帮助，给他们提意见。同时，自己也完善了自己的“随机漫步”(Rand Walk)模拟演示系统的课程论文，制作了要答辩的PPT和资料。 在实习中，我还将自己设计的模拟演示系统向指导教师和同学们进行了演示，并接受了他们所给的意见，对系统做了一点修改。 8 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 七、实习总结 八、附录：核心代码清单 批注：这里仅提供在Code::Blocks 10.05 IDE环境下编写的代码；至于在Visual Studio 2005环境下编写的动态演示代码的核心部分与下文提供的代码大同小异，如要查看请直接查看附件所提供的“源代码”部分。 (1)MAIN.cpp #include using namespace std; #include \"RandWalk.h\" int main(void) { RandWalk(); system(\"PAUSE\"); return 0; } (2)RandWalk.h #ifndef RANDWALK_H_INCLUDED #define RANDWALK_H_INCLUDED #include #include #include #include //头文件区 #include \"Operation.h\" #include \"Simulate.h\" void RandWalk(void) { //功能：进入Rand Walk模拟演示系统,选择操作 system(\"color 0E\"); bool quit = false; while(!quit) 9 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 { system(\"cls\"); menu(); int choose; scanf(\"%d\",&choose); switch(choose) { case 1: displayExplanation(); break; case 2: quit = simulate(); break; case 3: quit = true; break; default: printf(\"\您的输入不合法！\\n\ \"); system(\"PAUSE\"); break; } } } #endif // RANDWALK_H_INCLUDED (3)Operation.h #ifndef OPERATION_H_INCLUDED #define OPERATION_H_INCLUDED #define PREINSTALL_SIZE 10000 void menu(void) { //功能：打印菜单 puts(\" 欢迎进入\\\"Random Walk\\\"模拟演示系统：\"); puts(\"\\===================================================\"); puts(\"\\_1.查看演示说明.\"); puts(\"\\_2.进行模拟演示.\"); puts(\"\\_3.对此演示不感兴趣,退出程序.\"); puts(\"\\====================================================\"); printf(\" 输入序号，进行选择：\"); } 10 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 void displayExplanation(void) { //操作：读取文件displayExplanation.txt //功能：对Random Walk模拟演示系统进行解释说明 FILE* fp = fopen(\"displayExplanation.txt\",\"rw\"); if(!fp) { fprintf(stderr,\"EEOR：打开文件出错！\\n\"); exit(EXIT_FAILURE); } char Exp[PREINSTALL_SIZE],ch; int index = 0; while(ch = fgetc(fp),ch != EOF) Exp[index++] = ch; MessageBox(NULL,TEXT(Exp),TEXT(\"演示说明:\"),0); fclose(fp); } void inputPrompt(void) { puts(\"\地板上铺有n×m块瓷砖，请您确定m、n的值：\"); printf(\"\注：n和m满足： l.width || p.y > l.length) return false; else return true; } 12 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 void InitSituation(struct situation &e) { //操作：提示并输入蟑螂所在坐标位置(x,y) //功能：初始化当前时刻模拟系统所处的局面情形 inputPrompt(); scanf(\"%d%d\",&e.tile.length,&e.tile.width); InitLayout(e.tile); printf(\"\请输入蟑螂所在坐标位置(x,y): \"); scanf(\"%d%d\",&e.position.x,&e.position.y); while(!judgePosition(e.position,e.tile)) { printf(\"\您输入的值不合法！\\n\请重新输入坐标位置(x,y):\"); scanf(\"%d%d\",&e.position.x,&e.position.y); } e.iteration = 0; e.passed = 0; } void DestorySituation(struct situation &e) { //功能：销毁结构体e,释放初始化过程中申请的内存 DestoryLayout(e.tile); e.iteration = 0; e.passed = 0; e.position.x = e.position.y = 0; } void manage(struct situation &e) { //功能：模拟的基本操作过程，并得到相应的结果 int imove[8] = {-1,0,1,1,1,0,-1,-1},jmove[8] = {1,1,1,0,-1,-1,-1,0}; while(1) { int iTemp = rand()%8; if(e.position.x + imove[iTemp] > 0 && e.position.y + jmove[iTemp] > 0 && e.position.x + imove[iTemp] <= e.tile.width && e.position.y + jmove[iTemp] <= e.tile.length)//判断移动的方向是否合法 { e.position.x += imove[iTemp]; e.position.y += jmove[iTemp]; e.iteration++; if(!e.tile.array[e.position.y - 1][ e.position.x - 1]) e.passed++; 13 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 e.tile.array[e.position.y - 1][ e.position.x - 1]++; } if(e.passed == e.tile.width*e.tile.length || e.iteration == ITERATIVE_MAX) break; } } void displayLayout(struct layout e) { //功能：输出模拟过程中得到的数据 for(int i = 0; i < e.length; ++i) { for(int j = 0; j < e.width; ++j) printf(\"%d \",e.array[i][j]); puts(\"\"); } } void dispalyFormate(int m) { //功能：格式化输出int型数据 char s[5]; s[4] = '\\0'; int i = 0; while(m) { s[i++] = (char)(m%10 + '0'); m = m/10; } int j = i - 1,k = 0; while(j > k) { char cTemp = s[k]; s[k] = s[j]; s[j] = cTemp; j--,k++; } while(i != 3) s[i++] = ' '; printf(\"%s\",s); } void dispalyFormateLayout(struct layout e) { 14 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 //功能：格式化输出模拟过程中得到的数据， //并将数据存入到RandomWalk_Data.txt记事本文件中 FILE* fp; //fp = fopen(\"RandomWalk_Data.txt\ //fp = fopen(\"RandomWalk_Data.xls\ fp = fopen(\"RandomWalk_Data.dat\",\"w\"); if(!fp) printf(\"ERROR!\\n\"); for(int i = 0; i < e.length; ++i) { for(int j = 0; j < e.width; ++j) { dispalyFormate(e.array[i][j]); //将数据读入文件中 fprintf(fp,\"%d \",e.array[i][j]); } puts(\"\"); fprintf(fp,\"\\n\"); } fclose(fp); } bool conclusion(void) { MessageBox(NULL, TEXT(\"模拟已结束，模拟数据已存入相应的记事本中.\\n\如果想观看，请输入\\\"1\\\".\" \"\\n\输入\\\"2\\\重新进入演示系统.\\n\输入其他字符将退去本系统.\"), TEXT(\"提示信息:\"),0); int iTemp; printf(\"继续：\"); scanf(\"%d\",&iTemp); switch(iTemp) { case 2: return false; case 1: //system(\"start RandomWalk_Data.txt\"); //system(\"start RandomWalk_Data.xls\"); system(\"start RandomWalk_Data.dat\"); default: return true; } } bool simulate(void) 15 dabbysunshine@qq.com 源代码下载地址：http://download.csdn.net/detail/sunshinedabby/3992381 { struct situation EXAMPLE; InitSituation(EXAMPLE); displayLayout(EXAMPLE.tile); manage(EXAMPLE); dispalyFormateLayout(EXAMPLE.tile); printf(\"Iteration:%d\\n\",EXAMPLE.iteration); printf(\"Passed:%d\\n\",EXAMPLE.passed); DestorySituation(EXAMPLE); return conclusion(); } #endif // SIMULATE_H_INCLUDED 16
