学生实验报告

实验名称：软件开发实践

指导教师:   

姓    名:   

学    号：  

班    级：  

日    期：  

实验报告

姓名:          学号:

一、实验号题目:  寻找所有的路径

二、实验的目的和要求:

     读懂一段程序的代码,学会里面分析问题的思路,规范自己写代码. 在阅读大量源代码的时候，能够提高自己对大的软件的把握能力，快速了解脉络，熟悉细节，不仅仅是编程技巧，还能在程序的架构，设计方面提高自己的能力。

三、算法描述:

你将给的字符串存储在一个矩形格子中。在这个矩形格子寻找一个字符串。出发点可能在格子中任何地方。方向可能向上,下,左,右,或对角的一个字母到下一个字母, 每个格子只能占用一次。你要归还 int类型的数来表示所有可能的路径的数目。如果返回结果是超过 1,000,000,000,的用-1表示.;

eg:

四、源程序清单:

#include <string.h>

#include <vector.h>

#include <iostream.h>

using namespace std; //Required for TopCoder gcc compiler

class WordPath

{

    typedef struct POINTtag{

        int x;

        int y;

        int count;

    }POS;

    typedef vector<POS> VETPOS;

   

public:

   

    int countPaths(vector <string> grid, string find)

    {

        int findStrLen = find.length();

        int gridSize   = grid.size();

        int gridStrLen = grid[0].length();

       

        vector <VETPOS> vec(findStrLen);

       

        int i,j,k;

       

        // 遍历grid中的每一个字符

        for ( i = 0; i < gridSize; i ++)

        {

            for ( j= 0; j < gridStrLen; j++)

            {

                for ( k=0; k<findStrLen; k++)

                {

                    char ch =  find.at(k);

                    //如果与find中位置k的字符相等，则将相应的grid中的位置坐标保存到相应的向量中去

                    if ( ch == grid[i].at(j) )

                    {

                        POS ps;

                        ps.x =j;

                        ps.y = i;

                       

                        //位置向量0中所有坐标的初始值为1，而其他位置向量中坐标的这个字段总会被指零后才计算

                        ps.count = 1;

                        vec[k].push_back(ps);

                    }

                }

            }

        }

       

        // 如果有find中的字符在grid中不存在则返回0

        for ( k=0; k<findStrLen; k++)

        {

            if ( vec[k].size() == 0 )

                return 0;

        }

                 

        VETPOS midVes;//保存当前位置向量中符合条件点的临时向量

       

        // 遍历从位置1开始的位置向量

        for ( i = 1; i < findStrLen ; i ++)

        {

            midVes.clear();

           

            //遍历当前位置向量中的所有位置坐标

            for ( j=0; j < vec[i].size(); j++)

            {

                POS cur = vec[i][j];

               

                //如果当前点与前个向量vec[i-1]中的点可以移动到达，则保存这个点到临时变量midVes中去

                if (  pathCount(cur,vec[i-1]))

                {

                    midVes.push_back(cur);

                }

            }

            //清空原来的向量

            vec[i].clear();

           

            //如果midVes中有符合条件的点存在，则将它保存到原来的位置向量中去

            //否则返回0

            if ( midVes.size() >0 )

            {

                vec[i] = midVes;

            }

            else

            {

                return 0;

            }

        }

       

        // 统计保存在最后位置向量中的点的count值

        int count = 0;

        for ( j=0; j < vec[findStrLen-1].size(); j++)

        {

            POS cur = vec[findStrLen-1][j];

            count += cur.count;

            if (count > 1000000000 )

                return -1;

        }

        return count;

    }

   

    int pathCount(POS &ps, VETPOS& pre)

    {

        //初始为0

        ps.count = 0;

        int i;

       

        //遍历pre中的每个位置坐标

        for ( i=0; i < pre.size(); i++)

        {

            //计算cur与pre[i]的纵横坐标差的绝对值

            int xAbs = ps.x - pre[i].x;

            int yAbs = ps.y - pre[i].y;

            

            xAbs = xAbs<0?-xAbs:xAbs;

            yAbs = yAbs<0?-yAbs:yAbs;

          

            //判断是否可以移动到达

            if (( xAbs == 1 && yAbs < 2 ) ||

                ( yAbs == 1 && xAbs < 2 ) )

            {

                ps.count += pre[i].count;//统计通过ps点的可能路径数。

            }

        }

       

        return ps.count;

    }

};

//以下为测试代码

void Load(vector <string> &grid, string &find)

{

    string array[]={"ABC",

        "FED",

        "GHI"};

   

    for (int i=0; i < sizeof(array)/sizeof(string); i++)

    {

        grid.push_back(array[i]);

        cout<<array[i]<<endl;

    }

    find = "ABCDEFGHI";

    cout <<find<<endl;

}

void Load1(vector <string> &grid, string &find)

{

    string array[]={"ABC",

 "FED",

 "GAI"};

   

    for (int i=0; i < sizeof(array)/sizeof(string); i++)

    {

        grid.push_back(array[i]);

        cout<<array[i]<<endl;

    }

    find = "ABCDEA";

    cout <<find<<endl;

}

void Load2(vector <string> &grid, string &find)

{

    string array[]={"ABABA",

 "BABAB",

 "ABABA",

 "BABAB",

 "ABABA"};

   

    for (int i=0; i < sizeof(array)/sizeof(string); i++)

    {

        grid.push_back(array[i]);

        cout<<array[i]<<endl;

    }

    find = "ABABABBA";

    cout <<find<<endl;

}

void Load3(vector <string> &grid, string &find)

{

    string array[]={"AA",

 "AA"};

   

    for (int i=0; i < sizeof(array)/sizeof(string); i++)

    {

        grid.push_back(array[i]);

        cout<<array[i]<<endl;

    }

    find = "AAAA";

    cout <<find<<endl;

}

void Load4(vector <string> &grid, string &find)

{

    string array[]={"AAAAA",

 "AAAAA",

 "AAAAA",

 "AAAAA",

 "AAAAA"};

   

    for (int i=0; i < sizeof(array)/sizeof(string); i++)

    {

        grid.push_back(array[i]);

        cout<<array[i]<<endl;

    }

    find ="AAAAAAAAAAA";

    cout <<find<<endl;

}

int main(int argc, char* argv[])

{

    WordPath word;

    vector <string> grid;

    string find;

    void(*LoadFn[])(vector <string> &grid, string &find)={

    Load,Load1,Load2,Load3,Load4};

   

    for ( int i = 0; i < sizeof(LoadFn)/sizeof(LoadFn[0]); i ++)

    {

        grid.clear();

        LoadFn[i](grid,  find);

        cout<<word.countPaths(grid,  find)<<endl;

    }

       return 0;

}

五、运行结果:

六.实验收获.

阅读代码是程序员的基本技能，同时也是软件开发、维护、演进、审查和重用过程中不可或缺的组成部分。如果我们掌握非常好的读代码的能力,能够很大提高我们程序的可读性.读源代码，至少有3个好处。第一个好处是可以学习到很多编程的方法，看好的源代码，对于提高自己的编程水平，比自己写源代码的帮助更大。当然不是说不用自己写，而是

说，自己写代码的同时，可以从别人写的好的源代码中间学习到更多的编程方法和技巧。第二个好处是，可以提高自己把握大规模源代码的能力。一个比较大型的程序，往往都是经过了很多个版本很长的时间，有很多人参与开发，修正错误，添加功能而发展起来的。所以往往源代码的规模都比较大，少则10-100多k, 多的有好几十个MB. 在阅读大量源代码的时候，能够提高自己对大的软件的把握能力，快速了解脉络，熟悉细节，不仅仅是编程技巧，还能在程序的架构，设计方面提高自己的能力。

这是我们组综合网络上一些看法总结下来的：

分析一个源代码，一个有效的方法是：

　　1、阅读源代码的说明文档，比如本例中的README, 作者写的非常的详细，仔细读过之后，在阅读程序的时候往往能够从README文件中找到相应的说明，从而简化了源程序的阅读工作。

　　2、如果源代码有文档目录，一般为doc或者docs， 最好也在阅读源程序之前仔细阅读，因为这些文档同样起了很好的说明注释作用。

　　3、从makefile文件入手，分析源代码的层次结构，找出哪个是主程序，哪些是函数包。这对于快速把握程序结构有很大帮助。

　　4、从main函数入手，一步一步往下阅读，遇到可以猜测出意思来的简单的函数，可以跳过。但是一定要注意程序中使用的全局变量（如果是C程序），可以把关键的数据结构说明拷贝到一个文本编辑器中以便随时查找。

　　5、分析函数包（针对C程序），要注意哪些是全局函数，哪些是内部使用的函数，注意extern关键字。对于变量，也需要同样注意。先分析清楚内部函数，再来分析外部函数，因为内部函数肯定是在外部函数中被调用的。

　　6、需要说明的是数据结构的重要性：对于一个C程序来说，所有的函数都是在操作同一些数据，而由于没有较好的封装性，这些数据可能出现在程序的任何地方，被任何函数修改，所以一定要注意这些数据的定义和意义，也要注意是哪些函数在对它们进行操作，做了哪些改变。

　　7、在阅读程序的同时，最好能够把程序存入到cvs之类的版本控制器中去，在需要的时候可以对源代码做一些修改试验，因为动手修改是比仅仅是阅读要好得多的读程序的方法。在你修改运行程序的时候，可以从cvs中把原来的代码调出来与你改动的部分进行比较(diff命令), 可以看出一些源代码的优缺点并且能够实际的练习自己的编程技术。

　　8、阅读程序的同时，要注意一些小工具的使用，能够提高速度，比如vi中的查找功能，模式匹配查找，做标记，还有grep，find这两个最强大最常用的文本搜索工具的使用

附：读代码秘诀115条

1.要养成一个习惯, 经常花时间阅读别人编写的高品质代码.

2.要有选择地阅读代码, 同时, 还要有自己的目标. 您是想学习新的模式|编码风格|还是满足某些需求的方法.

3.要注意并重视代码中特殊的非功能性需求, 这些需求也许会导致特殊的实现风格.

4.在现有的代码上工作时, 请与作者和维护人员进行必要的协调, 以避免重复劳动或产生厌恶情绪.

5.请将从开放源码软件中得到的益处看作是一项贷款, 尽可能地寻找各种方式来回报开放源码社团.

6.多数情况下, 如果您想要了解"别人会如何完成这个功能呢?", 除了阅读代码以外, 没有更好的方法.

7.在寻找bug时, 请从问题的表现形式到问题的根源来分析代码. 不要沿着不相关的路径(误入歧途).

8.我们要充分利用调试器|编译器给出的警告或输出的符号代码|系统调用跟踪器|数据库结构化查询语言的日志机制|包转储工具和Windows的消息侦查程序, 定出的bug的位置.

9.对于那些大型且组织良好的系统, 您只需要最低限度地了解它的全部功能, 就能够对它做出修改.

10.当向系统中增加新功能时, 首先的任务就是找到实现类似特性的代码, 将它作为待实现功能的模板.

11.从特性的功能描述到代码的实现, 可以按照字符串消息, 或使用关键词来搜索代码.

12.在移植代码或修改接口时, 您可以通过编译器直接定位出问题涉及的范围, 从而减少代码阅读的工作量.

13.进行重构时, 您从一个能够正常工作的系统开始做起, 希望确保结束时系统能够正常工作. 一套恰当的测试用例(test case)可以帮助您满足此项约束.

14.阅读代码寻找重构机会时, 先从系统的构架开始, 然后逐步细化, 能够获得最大的效益.

15.代码的可重用性是一个很诱人, 但难以理解与分离, 可以试着寻找粒度更大一些的包, 甚至其他代码.

16.在复查软件系统时, 要注意, 系统是由很多部分组成的, 不仅仅只是执行语句. 还要注意分析以下内容: 文件和目录结构|生成和配置过程|用户界面和系统的文档.

18.可以将软件复查作为一个学习|讲授|援之以手和接受帮助的机会.
第二章: 基本编程元素





19.第一次分析一个程序时, main是一个好的起始点.

20.层叠if-else if-...-else序列可以看作是由互斥选择项组成的选择结构.

21.有时, 要想了解程序在某一方面的功能, 运行它可能比阅读源代码更为恰当.

22.在分析重要的程序时, 最好首先识别出重要的组成部分.

23.了解局部的命名约定, 利用它们来猜测变量和函数的功能用途.

24.当基于猜测修改代码时, 您应该设计能够验证最初假设的过程. 这个过程可能包括用编译器进行检查|引入断言|或者执行适当的测试用例.

25.理解了代码的某一部分, 可能帮助你理解余下的代码.

26.解决困难的代码要从容易的部分入手.

27.要养成遇到库元素就去阅读相关文档的习惯; 这将会增强您阅读和编写代码的能力.

28.代码阅读有许多可选择的策略: 自底向上和自顶向下的分析|应用试探法和检查注释和外部文档, 应该依据问题的需要尝试所有这些方法.

29.for (i=0; i<n; i++)形式的循环执行n次; 其他任何形式都要小心.

30.涉及两项不等测试(其中一项包括相等条件)的比较表达式可以看作是区间成员测试.

31.我们经常可以将表达式应用在样本数据上, 借以了解它的含义.

32.使用De Morgan法则简化复杂的逻辑表达式.

33.在阅读逻辑乘表达式时, 问题可以认为正在分析的表达式以左的表达式均为true; 在阅读逻辑和表达式时, 类似地, 可以认为正在分析的表达式以左的表达式均为false.

34.重新组织您控制的代码, 使之更为易读.

35.将使用条件运行符? :的表达式理解为if代码.

36.不需要为了效率, 牺牲代码的易读性.

37.高效的算法和特殊的优化确实有可能使得代码更为复杂, 从而更难理解, 但这并不意味着使代码更为紧凑和不易读会提高它的效率.

38.创造性的代码布局可以用来提高代码的易读性.

39.我们可以使用空格|临时变量和括号提高表达式的易读性.

40.在阅读您所控制的代码时, 要养成添加注释的习惯.

41.我们可以用好的缩进以及对变量名称的明智选择, 提高编写欠佳的程序的易读性.

42.用diff程序分析程序的修订历史时, 如果这段历史跨越了整体重新缩排, 常常可以通过指定-w选项, 让diff忽略空白差异, 避免由于更改了缩进层次而引入的噪音.

43.do循环的循环体至少执行一次.

44.执行算术运算时, 当b=2n-1时, 可以将a&b理解为a%(b+1).

45.将a<<n理解为a*k, k=2n.

46.将a>>n理解为a/k, k=2n.

47.每次只分析一个控制结构, 将它的内容看作是一个黑盒.

48.将每个控制结构的控制表达式看作是它所包含代码的断言.

49.return, goto, break和continue语句, 还有异常, 都会影响结构化的执行流程. 由于这些语句一般都会终止或重新开始正在进行的循环, 因此要单独推理它们的行为.

50.用复杂循环的变式和不变式, 对循环进行推理.

51.使用保持含义不变的变换重新安排代码, 简化代码的推理工作.

52.了解特定语言构造所服务的功能之后, 就能够更好地理解使用它们的代码.

53.识别并归类使用指针的理由.

54.在C程序中, 指针一般用来构造链式数据结构|动态分配的数据结构|实现引用调用|访问和迭代数据元素|传递数组参数|引用函数|作为其他值的别名|代表字符串|以及直接访问系统内存.

55.以引用传递的参数可以用来返回函数的结果, 或者避免参数复制带来的开销.

56.指向数组元素地址的指针, 可以访问位于特定索引位置的元素.

57.指向数组元素的指针和相应的数组索引, 作用在二者上的运算具有相同的语义.

58.使用全局或static局部变量的函数大多数情况都不可重入(reentrant).

59.字符指针不同于字符数组.

60.识别和归类应用结构或共用体的每种理由.

61.C语言中的结构将多个数据元素集合在一起, 使得它们可以作为一个整体来使用, 用来从函数中返回多个数据元素|构造链式数据结构|映射数据在硬件设备|网络链接和存储介质上的组织方式|实现抽象数据类型|以及以面向对象的方式编程.

62.共用体在C程序中主要用于优化存储空间的利用|实现多态|以及访问数据不同的内部表达方式.

63.一个指针, 在初始化为指向N个元素的存储空间之后, 就可以作为N个元素的数组来使用.

64.动态分配的内在块可以电焊工地释放, 或在程序结束时释放, 或由垃圾回收器来完成回收; 在栈上分配的内存块当分配它的函数退出后释放.

65.C程序使用typedef声明促进抽象, 并增强代码的易读性, 从而防范可移植性问题, 并模拟C++和Java的类声明行为.

66.可以将typedef声明理解成变量定义: 变量的名称就是类型的名称; 变量的类型就是与该名称对应的类型.

67.根据底层的抽象数据类型理解显式的数据结构操作.

68.C语言中, 一般使用内建的数组类型实现向量, 不再对底层实现进行抽象.

69.N个元素的数组可以被序列for (i=0; i<N; i++)完全处理; 所有其他变体都应该引起警惕.

70.表达式sizeof(x)总会得到用memset或memcpy处理数组x(不是指针)所需的正确字节数.

71.区间一般用区间内的第一个元素和区间后的第一个元素来表示.

72.不对称区间中元素的数目等于高位边界与低位边界的差.

73.当不对称区间的高位边界等于低位边界时, 区间为空.

74.不对称区间中的低位边界代表区间的第一个元素; 高位边界代表区间外的第一个元素.

75.结构的数组常常表示由记录和字段组成的表.

76.指向结构的指针常常表示访问底层记录和字段的游标.

77.动态分配的矩阵一般存储为指向数组列的指针或指向元素指针的指针; 这两种类型都可以按照二维数组进行访问.

78.以数组形式存储的动态分配矩阵, 用自定义访问函数定位它们的元素.

79.抽象数据类型为底层实现元素的使用(或误用)方式提供一种信心的量度.

80.数组用从0开始的顺序整数为键, 组织查找表.

81.数组经常用来对控制结构进行高效编码, 简化程序的逻辑.

82.通过在数组中每个位置存储一个数据元素和一个函数指针(指向处理数据元素的函数), 可以将代码与数据关联起来.

83.数组可以通过存储供程序内的抽象机(abstract machine)或虚拟机(virtual machine)使用的数据或代码, 控制程序的运作.

84.可以将表达式sizeof(x) / sizeof(x[0])理解为数组x中元素的个数.

85.如果结构中含有指向结构自身|名为next的元素, 一般说来, 该结构定义的是单向链表的结点.

86.指向链表结点的持久性(如全局|静态或在堆上分配)指针常常表示链表的头部.

87.包含指向自身的next和prev指针的结构可能是双向链表的结点.

88.理解复杂数据结构的指针操作可以将数据元素画为方框|指针画为箭头.

89.递归数据结构经常用递归算法来处理.

90.重要的数据结构操作算法一般用函数参数或模板参数来参数化.

91.图的结点常常顺序地存储在数组中, 链接到链表中, 或通过图的边链接起来.

92.图中的边一般不是隐式地通过指针, 就是显式地作为独立的结构来表示.

93.图的边经常存储为动态分配的数组或链表, 在这两种情况下, 边都锚定在图的结点上.

94.在无向图中, 表达数据时应该将所有的结点看作是等同的, 类似地, 进行处理任务的代码也不应该基于它们的方向来区分边.

95.在非连通图中, 执行遍历代码应该能够接通孤立的子图.

96.处理包含回路的图时, 遍历代码应该避免在处理图的回路进入循环.

97.复杂的图结构中, 可能隐藏着其他类型的独立结构。

98.采用递归定义的算法和数据结构经常用递归的函数定义来实现.

99.推理递归函数时, 要从基准落伍测试开始, 并认证每次递归调用如何逐渐接近非递归基准范例代码.

100.简单的语言常常使用一系列遵循该语言语法结构的函数进行语法分析.

101.推理互递归函数时, 要基于底层概念的递归定义.

102.尾递归调用等同于一个回到函数开始处的循环.

103.将throws子句从方法的定义中移除, 然后运行Java编译器对类的源代码进行编译, 就可以容易地找到那些可能隐式地生成异常的方法.

104.在多处理器计算机上运行的代码常常围绕进程或线程进行组织.

105.工作群并行模型用于在多个处理器间分配工作, 或者创建一个任务池, 然后将大量需要处理标准化的工作进行分配.

106.基于线程的管理者/工人并行模型一般将耗时的或阻塞的操作分配给工人子任务, 从而维护中心任务的响应性.

107.基于进程的管理者/工人并行模型一般用来重用现有的程序, 或用定义良好的接口组织和分离粗粒度的系统模块.

108.基于流水线的并行处理中, 每个任务都接收到一些输入, 对它们进行一些处理, 并将生成的输出传递给下一个任务, 进行不同的处理.

109.竞争条件很难捉摸, 相关的代码常常会将竞争条件扩散到多个函数或模块; 因而, 很难隔离由于竞争条件导致的问题.

110.对于出现在信号处理器中的数据结构操作代码和库调用要保持高度警惕.

111.在阅读包含宏的代码时, 要注意, 宏既非函数, 也非语句.

112.do…while(0)块中的宏等同于控制块中的语句.

113.宏可以访问在它的使用点可见的所有局部变量.

114.宏调用可改变参数的值

115.基于宏的标记拼接能够创建新的标记符