实验2：基于visio的系统HIPO图和程序流程图

实验2：基于VISIO的系统HIPO图和程序流程图

目的：

1）掌握HIPO画法

2）掌握数据流程图画法

内容：

1）本文附录图3-25、教材P66图4.3 2）本文附录图3-44、图3-45、图3-47

销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销销

图3-25 销售管理系统的HIPO图

例题1（1994年软件设计师试题）

阅读下列说明和流程图，如图3-44所示，回答问题1和问题2，把解答写在答案的对应栏里。 【说明】

流程图3-45用来将数组A中的n（n?2）个数经变换后存储到数组B中。变换规则如下： （1）若A中有连续t个相同的元素（t>1），则在B存入t和该元素的值。 （2）若A中有连续t个元素（t?1），其中每个元素都与相邻的元素不相同，则在B中存入t和这t个元素的值。

例如：

A={3，3，3，3，5，5，7，6，3，6，2，2，2，2，1，2} 则变换后

B={4，3，2，5，-4，7，6，3，6，4，2，-2，1，2}

流程图中，逻辑变量C用来区分正在进行连续相同元素的计数还是连续不等元素的计数，Ki用来记录数组B存放t或-t的元素的下标。 【问题1】

填充流程图中的①至⑤，使之成为完整的流程图。 【问题2】

如果删除流程图中的判断框t:1，那么，当数组A={5,5,4,4}时，经改变后的流程图的变换，数组B将会有什么样的元素值？

start=<>true销CA(1):A(2)1销K1A(1)销B(2)2销K销2销ii:n<=false销C>truet销B(K1)Cfalse销start=CA(i-1):A(i)falseT:1 >销销B(K1)K销K1K+1销K<>Cfalset+1销tK+1销KA(i)销B(K)truet+1销ttruet销B(K1)K+1销K1A(i)销B(K+2)K+2销K1销t销A(i-1)销B(K)销2销ti+1销i图3-44 例题1流程图

分析：首先应仔细地阅读说明部分，了解程序实现什么样的功能。程序实际上是完成一个数组的变换。 例如：

A={3，3，3，3，5，5，7，6，3，6，2，2，2，1，2} 则变换后;

B={4，3，2，5，-4，7，6，3，6，4，2，-2，1，2} 也就是说，A中有4个“3”，所以在B中写入“3”的个数t（即4），再写入该元素值 （即3），A中接下来是两个“5”，所以在B中添加数据“2，5”；再下来是4个相邻但不同的数“7，6，3，6”，所以在B中写入-t（即-4），再写入t个元素值(即7，6，3，6)，后面的依次类推。

通过上面的分析，我们已经了解了程序要实现的功能，现在开始分析程序流程。

从整体上看，此程序的分支比较多，用到的变量也比较多。这种情况下，最好是自己手动地把数据代到程序中去，手动地模拟程序运行。这样，能让你最快地了解到程序的算法结构。题目中其实已近为考生提供了相当便利的条件，有一个实例，可以就用提供的实例来手动运算。所以，A(1)=A(2)=3 C=’true’ K1=1 B(2)=A(1)，这一句是把A(1)赋值给B(2)，当A的前t个元素相等时，B(1)保存t的值，B(2)保存该元素，元素值为A(1)，当A中连续t(t?1)个元素都与其相邻的元素不相同时，则在B(1)中存入-t，B(2)保存这t个元素中的第1个元素即A(1)。所以不管什么情况，B(2)都应该等于A(1)。接着看下一步，2→K，暂时不管空①，继续往下看，2→i，因为i?n，所以，A(i-1)=A(i)(C值为’true’)，再接着执行t=t +1，i=i+1??

当i=5时，A(i-1)<>A(i)，又因为C值为’true’，所以t→B(K1)。因为K1=1，B(K1)是存储连续相同数字的个数的，按我们的实例，现在的t应等于4，再往前推算，可以知道t应有初值1，所以空①应填1→t。再往下走，K1= K+1，此时的K1=3，为下一次记录t或是-t做准备，A(i)→ B(K1+1)。与前面的B(2)=A(1)类似，为下一轮的解析做准备。K=K+2t=1，到此，空④其实不用去搞复杂的分析和推敲，细心一点儿就能一下写出来。因为这里必须填’true’→C，如果不填这句，程序的两大分支将永远不能执行。同理可得空③应填’false’→C。空②所在的分支是当有n个连续不等数后接有相同的两个数时才执行的分支。前面已经说过B(K1)是用来存储t或-t的，但这里应该注意一点，t是否符合题目的要求。当判断A(i-1)=A(i)成立时，t计数到了第i-1个元素，但按题目的要求，A(i-1)不能计入n个不同的数中，所以空②应填1-t。

空⑤是直接从i：n的判断分支出去的一部分，如果i>n则执行那一部分分支。其实可以不看底下的大段程序，只要n=1（当然，这个题出题时考虑不够周全，没有考虑到n=1时会产生数组溢出，正确的做法应是把这种情况归到A(1)<>A(2)这个分支，但我们做题时可以这么考虑），又因为当C为’true’时B(K1)=t，所以C为’false’时应填：B(K1)=-t。

问题2，前面已经把所有的空都填好了，所以此题只需把数组，代入到删除了的程序中手动运行即可得到答案：B={2，5，0，2，4}。 参考答案 【问题1】

①1->t ②1-t ③'true'->c ④'false'->c ⑤-t->B(K1) 【问题2】

B={2，5，0，2，4}

例题2（1993年软件设计师试题）

阅读下列说明和流程图，如图3-45所示，回答问题1至问题3，把解答写在答卷的对应栏内。

startSN(1)销LN2销II销JI:NW<=销stopLN1:80<=80-LN销N[N/(I-J-1)]销LNWMOD(N,I-J-1)销LNBabcd销L销销销销1销kJ:I销销>>t销B(K1)销S(SL(J):SL(J)-1)销L(K:K+SN(J)-1)efg<=hi销->k销销 LNB:0>K+1销kLNB-1销LNBJ+1销J

图3-45 例题2流程图

销I+1销I【说明】

本流程图的功能是对预处理后的正文文件进行排版输出。

假定预处理后的正文文件存放在字符串S中，S由连续的单词组成，单词由连续的英文字母组成。在预处理过程已产生以下信息：变量NW存放正文中单词的个数，数组元素SL(I)存

放正文中第I个单词在S中的字符位置，SL(1)存放正文中第1个单词的长度。规定S中的字符位置从1开始计数，每个字符占一个位置。字符串S中的某个单词可用如下的子串形式来存取：

S（单词起始位置：单词终止位置）

并规定在对字符串（或子串）赋值时，赋值号两端的字符串（或子串）长度必须相等。 排版输出的要求如下： (1) 每行输出80个字符；

(2) 一个单词不能输出在两行中；

(3) 除最后一行外，所有输出行既要左对齐又要右对齐。即每行的第一个字符必须是某个单词的第一个字母，最后一个字符必须是某个单词的最后一个字母； (4) 单词之间必须有一个或一个以上的空格；

(5) 最后一行只须左对齐，且单词之间均只有一个空格；

(6) 使空格尽可能地均匀分布在单词之间，即同一行中相邻的单词的空格数量最多相差1。 假定正文中至少有两个以上的单词，每个单词的长度均小于40。此外，流程图中省略了数据的输入部分。图中[W]表示不超过W的最大整数。 【问题1】

填充流程图中的①至⑥，使之成为完整的流程图。 【问题2】

图3-45中的“输出末行”框未经细化，如果将如图3-45所示的虚线部分复制到“打出末行”框上，那么复制部分应做怎样的修改？可用图中所示的 a,b,...,j来回答，例如a改成1→i，删除b。 【问题3】

如将图3-45中开始部分的 SN(1)→LN,改成2→i改成1→i，则修改后的流程图是否正确。 分析：其实做过一些流程图试题的读者已经能在解题过程中总结出一些经验了，其中的一条就是找程序中没有赋初值的变量，这些变量一定是要在你要填的空里赋初值的。这样能够缩小目标，加快解题速度。而且想像程序流程图题，一旦前一两空填出来了，你对程序结构的了解就能很快的更进一步，后面就势如破竹了。

此题正好可以运用这一点，在 第二个判断框中有LN1:80，但在 前面没有对LN1赋初值，所以我们可以马上就可以知道空①已经给LN1赋初值。那么具体应该赋什么值呢？

我们可以看到，当LN1小于等于80时，程序执行到②→i=i+1再到比较条件i：NW->①。结合题目中的“每行舒服80个字符”、“SN(1)存放正文中第1个单词的长度”，我们很容易能分析出LN1应是当前行的长度，能分析出出LN1应是当前行的长度，这个长度应该包括单词的长度和中间的空格，又因为前面又SN(1)→LN，所以空①应填LN+SN(1)→LN1,1是空格的长度，LN原来行的长度，S(I)是当前单词的长度。接下来的空②很明显搜LN1->LN,这是为下一轮的运算做准备。

现在我们开始分析主循环体内的语句：80-LN->N,算出一行结尾还有多少个空格，因为题目要求不能吧空格全放在行的结尾，要散布在单词中间。[N/(I-L-1)]→LNW这个操作是把多余空格除以本行的单词的间隔数再取整。MOD（N,I-J-1）→LNB，这个操作是把多余空格除以本行单词的间隔数在取余。也就是说，如果一行有5个单词第五个单词后还有7个空格，但无法放下第六个单词了，我们吧数据代入到式子里得：[7／（6-1-1）]→LNW,此时的 LNW=1,LNB=3,也就是说这7个空格应这样来分配，5个单词有4个间隔，首先每个空格加LNW个空格（即一个空格），再把前LNB个间隔处加1个空格。接下来1→K,J:I。

S(SL(J):SL(J)+SN(J)-I)→L(K:K+SN(J)-1)把单词插入到输出行的标准位置，⑤->K，通过上面的 分析再结合下面的 几条语句，我们可以发现LNW还未被使用，LNW应是加在每个间隔处的空格数，且K正好是确定输出行当前位置的变量（这一点可以从L(K:K+SN(J)-1)看

出），所以空⑤应填K+SN(J)+1+LNW.这个里面分为4个部分：K,SN(J),1,LNW.K：单词J写入到L的起始位置；SN(J)：单词J的长度；1:正常空格长度（题目要求“单词之间必须有一个或一个以上的空格”）；LNW：行尾多余空格平均分配到每个间隔的空格长度。

接下来我们来看空⑥，是在“打印L”处理后的，也就是当处理完一行并打印后，就要执行⑥，这样⑥应该是为新的一行处理做准备的，也就是说⑥应是对某个变量的赋值。我们现在可以逐一考查，循环里用到的哪些变量在新起一行时，要重新赋值。从“LN+SN(I+1)→LN1”可以看出，这个变量就是LN，因为LN存的是当前行的字符总数，当一行打印完后，LN的值应重新算，所以空⑥应填SN(I)→LN。 问题2：由于题目对末行输出的要求是：“最后一个行只须左对齐，且单词之间均只有一个空格”，所以我们不必考虑把尾部空格散布到单词间隔中，所以与LNB、LNW有关的语句得删除或修改。e中应该去掉LNW改为：K+SN(J)+1，f、g、h可以删除。

问题3：前面我们已经把所有空都填补完整，所以现在只需把改动的地方代入到程序里，手动模拟程序执行一段就能知道是否可行了。当执行到时LN+SN(I)+1→LN1，我们已经能够看出问题了，如果第一个单词加了一个空格位，那么此行一定会多出一个空格，所以这种改法是不行的。 参考答案 【问题1】

① LN+1+SN(1) →LN1 ② LN1→LN

③ ? ④ <

⑤ K+1+LNW+SN(j) ⑥ SN(1) →LN 【问题2】

删去f、g、h框，将e改成K+1+LNW+WN(J) →K。 【问题3】 不能。

例题3（2000年软件设计师试题）

阅读下列说明和数据流图，如图3-47所示，回答问题1至问题4，将解答写在答卷的对应栏内。

销销销销销销销销销销销销IN[]0销k,0销p,I销iIN[i]:销销销销销≠(IN[i]=?=销销) 销=K+1销kIN[i]销POLISH[k]P:0销销A =≠销销BS[p]:’(‘≠销≤销销B(p-1)销p销销A>i+1销iP:0?≠销销B=销销POLISH[]销销

图3-47 例题4流程图

【说明】

本流程图（如图3-47所示）是将中缀表示算术表达式转换成后缀表示，如中缀表达式 (A-(B*C+D)*E/(F+G))的后缀表示为ABC*D+E*-FG+/。

为了方便，假定变量名为单个英文字母，运算符只有“+”、“-”、“×”和“∕”（均为双目运算符，左结合），并假定所提供的算术表达式非空且语法是正确的。另外，中缀表示形式中无空格符，但整个算术表达式以空格符结束。流程图中使用的符号的意义如下：

? 数组IN[]存储中缀表达式。

? 数组POLISH[]存储其后缀表示。 ? 数组S[]是一个后进先出栈；

函数PRIOR(CHAR)返回符号CHAR的优先级，各符号的优先级见表3-6。

表3-6 各符号的优先级 CHAR PRIOR(CHAR) *、/ +、- （ ） 4 3 2 1 【问题1】

填充流程图中□的判断条件。 【问题2】

写出子程序A的功能，并顺序写出实现该功能的操作。 【问题3】

写出子程序B的功能，并顺序写出实现该功能的操作。 【问题4】

中缀表达式(A+B-C*D)*(E-F)/G经该流程图处理后的输出是什么？

分析：根据流程图中的符号得定义知道，数组IN[]与POLISH[]是对输入与输出的存储；而PRIOR是一个提取算术运算符号优先值的函数，语句没有多少可以发挥得地方；对数组S【】得定义是一个先进后出的栈。在数据结构中，对于栈的定义了3种厂用电操作如果采用数组来实现栈，需要定义一个栈顶指针p，其值为数组下标，其操作解释如下;

? 入栈：p+1→p;入栈元素→S[p]；

? 出栈： S[p] →栈元素变量; p-1→p； ? 栈是否为空：p=？0。

如果考生了解堆栈的常用操作，就可以分析流程图，并给出正确的答案。 根据流程图可以得到如下得提示： ? 3个变量：k,p,I.

? 根据第一个条件判断，可以知道：i是数组IN[]的小标。

从整个流程图得结构来看，该流程是一个循环处理，循环退出条件是IN[i]=空格，也就是中缀表达式输入完成，循环增量条件是i+i，循环体是从左到右依次输入处理中缀表达式。

对每次输入的中缀表达式的元素分4种情况分别进行处理。 (1) 如果是变量，则将变量保存到输入数组中。 (2) 如果是“（”，则进行A处理，A处理未知。

(3) 如果是“）”，则进行一个循环处理，循环退出条件是栈顶IN[p]=’(’，循环体是B，B处理未知。且B处理在整个流程图中出现3次。

但从循环退出条件可以分析出： A处理一定要将“（”进行入栈操作，因为“（”与“）”必须成对出现，而在处理“）”时，IN栈已经有“（”，所以A处理一定包含“（”元素的入栈操作。

因循环判断条件是IN[p]=’(’，所以可以分析该条件要随着循环的进行而变化，否则有可能进入死循环。而栈的常用操作是入栈、出栈操作，这里很明显应该是出栈操作，所以只可能是p值得改变，也就是B处理中需要栈顶的值的改变。另外，栈顶的值又怎样处理，这里需要结合流程中的其他任务进一步分析。

在退出循环后，直接丢掉栈顶的“）”值，再取下一输入值。 那么目前输入的“）”要进行这样的处理呢？这里根据考题给定的例题，可以知道，将一个中缀表达式转换成后缀表达式后，“（”、“）”均不出现在后缀表达式中，因此可以判断，输入的“）”在处理过程中是要找到匹配的“（”，对中缀表达式“（”、“）”之间的符号进行处理，而对“）”不进行任何处理。 (4) 如果输入的是运算符“*”、“∕”、“+”、“-”，则可能出现两个分支。

第一个分支：p是否为0，也就是栈是否为空，如果为空，则进行A处理，如不为空则进入第二个分支判断处理。

第二个分支：分支条件待确定，根据所给定的信息，可以确定是两个值比较大小，如果是大于则进行A处理，入股哦是小于等于则进行B处理，然后转入分支1的顶部，进入循环处理。

通过对循环体的分析可以得出如下的信息： A处理：含有入栈操作。

B处理：含有出栈操作，栈顶值是丢弃还是进行其他处理待定。

判断条件①：为两个值大小的判断，如果是小于等于，则进行出栈，如果大于等于则进行入栈。

再分析循环退出后的处理流程。

再次进入一个循环，循环条件为栈顶是否为空，如果不为空则进行B处理，也就是出栈操作，将栈中的元素按照后进先出的顺序进行退栈处理，从这里也很难确定B的其他信息。

流程分析完成后，再次分析题目给定的信息。在考题给定的信息中，还有一个优先表在流程中没有使用到，那么这个优先表只可能在流程图中的A、B处理或判断条件①中使用。优先表中的优先关系是运算符的优先关系，且用数值表示，而判断条件①已经分析出是两个值比较大小，因此可以假设判断条件①为判断两个运算符号的优先值。

情况一：中缀表达式的当前元素与后继元素的比较。这种情况的可能性比较小，在流程图中后续元素影响出栈是不合乎逻辑的。

情况二：后缀表达式的当前元素与后续元素的比较。这种情况的可能性比较小，因为当前元素影响写入的情况也不合乎逻辑。

情况三：中缀表达式的但钱元素与栈顶元素比较。这种情况的可能性比较大。 情况四：后缀表达式的当前元素与栈顶元素比较。这种情况的可能性也比较大。

情况五：栈顶元素与其下面在栈元素的比较。这种情况的可能性比较小，比栈内其他元素比较以决定是否出栈是不合乎逻辑的。

根据上面的分析，结合考题给出的例题再次分析，确定假设。 参考答案

【问题1】

PRIOR(IN[i]);PRIOR(S[p]) 【问题2】

功能：将当前符号IN[i]入栈 操作：p+1→p IN[i] →S[p] 【问题3】

功能：出栈（将栈顶元素送往数组POLISH[]） 操作：k+1→k S[p] →POLISH[k] p-1→p 【问题4】

AB+CD*-EF-*G/

本文来源：https://www.bwwdw.com/article/4qc3.html