现在的位置: 首页 > 综合 > 正文

栈:装水的杯子(一)入门测试题

2013年02月11日 ⁄ 综合 ⁄ 共 5091字 ⁄ 字号 评论关闭
 


子渊学算法

——栈:装水的杯子

 

(一)入门测试题

 

首先来介绍我们的主人公:梁子渊,男,12岁,小学六年级学生。

子渊参加了计算机程序设计兴趣小组,学了一个学期的PASCAL语言和简单的组合数学知识,想要向更高级的技术——数据结构和算法发起挑战了。正巧爸爸也是一个算法迷,于是两父子展开了以下的对话:

       “爸爸,我想学习数据结构和算法,老师说掌握它们就可以在计算机的天地里畅通无阻了。爸爸你快教教我吧!”

       “是吗?那你基础打得怎么样了?让我先来考考你,看看你有没有学习算法的潜质。”

“好啊!尽管放马过来吧——只是题目不要太难。”

“你放心,绝对基础题!”

题目:输入一个正整数n,试分离并输出其各位数字。例如,输入n=1234,则输出1234。(保证n不超出integer的范围)

子渊一看题目心里就乐了,这么简单啊!我刚学习PASCAL语言的时候就做过这种题目了,不就是考查整除和取余运算吗?

不到三分钟,子渊就把代码交到了爸爸手里:

{代码1}

{输入一个正整数n,试分离并输出其各位数字}

PROGRAM
Separate(INPUT, OUTPUT);

VAR

    v, n : integer;

 

BEGIN {MAIN}

    writeln('Input n:');

    readln(n);

 

    while n <> 0 do

    begin

        v := n mod 10; {分离出n的个位数字}

        write(v:2);

        n := n div 10; {去除n的个位数字}

    end; {while}

END.

爸爸看了代码以后,点了点头,说:“不错不错,代码风格不错!结构整齐,注释完整,基本功还可以。可惜啊!没按题目要求来做。”

子渊一听就急了,“怎么没按题目要求做?我不是从低位到高位把n的各位数字都分离并输出来了吗?”

“你把n的各位数字从低位到高位都分离了是不错,可是你的输出顺序也是从低位到高位,这不符合题目要求,也与我们的书写习惯不同啊。”

“对喔!我刚好弄反了。”子渊这才不会意思的挠了挠脑袋,“这该怎么办呢?”

“再好好想想!如果给定的正整数n是个3位数呢?”爸爸提示道。

3位数?那很好办啊!只要从高位开始分离数字就好了。”子渊兴奋得跳了起来,“也就是说,我只要先判断出n是个几位数,从高位开始分离数字就好了,因为保证n不超出integer的范围(HIGH(integer) = 32767),所以它至多是个5位整数,这样我至多判断5次就可以知道n是个几位数了。”

不一会儿,新的代码又交到了爸爸的手里:

{代码2}

{先判断出n是个几位数,再从高位开始分离数字并输出}

PROGRAM
Separate(INPUT, OUTPUT);

VAR

    v, n, h : integer;

 

FUNCTION
Highest(n : integer) : integer; {
判断n是个几位数,最大为32767}

begin

    if n > 10000 then

        Highest := 10000

    else if n > 1000 then

        Highest := 1000

    else if n > 100 then

        Highest := 100

    else if n > 10 then

        Highest := 10

    else

        Highest := 1;

end; {Highest}

 

BEGIN {MAIN}

    writeln('Input n:');

    readln(n);

 

    h := Highest(n); {判断n是个几位数}

    while h <> 0 do {分离数字并将其入栈}

    begin

        v := n div h; {分离出n的最高位数字}

        write(v:2);

        n := n mod h; {去除n的最高位数字}

        h := h div 10;{n位数降1}

    end; {while}

END.

“不错,确实能实现我所要求的功能,反应挺快!可是你不觉的这次的代码很“丑陋”吗?你看,姿态臃肿,一点也不简洁。特别是那个Highest()函数,只能用来判断integer类型数据,通用性很差。我们编写代码也是要讲究美感的啊!”爸爸稍微点了点头就马上叹起气来。

“很丑陋?我怎么没感觉到啊!它不是很好地实现了我们的意图吗?”子渊很是不解。

“实现了所需要的功能不错,可是这种实现的方法不够简洁,美观,缺乏通用性。反正我看着就是不顺眼——就像你这乱七八糟的书桌一样。”话说着,爸爸就帮子渊整理起书桌来:他把摆放得杂乱无章的各种童话,围棋和自然科学书籍一一收起来,放到一旁的储物箱里。

“其实你最初从低位开始分离数字的思路是正确的,因为这样不用事先判断n是个几位数,所以很容易实现。但是你把数字一分离出来就马上输出是不对的,最先分离出的数字是不能最早输出的。”

“最先分离的数字不能最早输出?那我该怎么办呢?”子渊喃喃自语。

“——咦,我的那本《科幻大王》呢?就是放在桌子最上面那本,爸爸你把它弄哪里去了?我还没看完呢!”子渊突然发现自己书桌上的书都不见了,马上嚷嚷起来。

“你嚷嚷什么呀!那些书我都收起来了,全部放在储物箱里。那本《科幻大王》是我最先收起来的,应该在箱子的底部,你自己去拿吧。”

“爸爸你真爱作弄人啊,把它放在最下面了!那我不是要把其他的书都移开才能拿到吗?真麻烦!”

“是啊,最早放进去的书自然是最后拿出来了!”爸爸顺口回答,“其实生活中类似这样的情况还真不少呢,比如你妈妈换蜂窝煤的时候,最先放进去的煤块不也是最后被拿出来吗?”

“我知道我知道!还有杂技演员表演叠罗汉的时候,最后上去的人总是第一个下来。”子渊也不甘示弱地补充。

“是啊,还有我们喝水的时候,最先喝到的总是最上层的水,而它们是最后被倒进去的。”爸爸继续补充,“计算机科学家们还给这种操作特点取了一个优雅的名字——“后进先出”呢。”

“后进先出?”

“是啊,上面所有的例子,不都体现了“后进先出”的特点吗?”

“可是,计算机科学家们为什么要研究它们啊?还给它取一个这么奇怪的名字。”子渊还是不明白爸爸说这些话有什么意思。

““后进先出”(LAST IN FIRST OUT,简称LIFO)只是它的特点,其实这是计算机程序设计中一个常见的数据结构——栈(STACK),它是一种存储数据的容器,就像装水的杯子一样。”爸爸进一步解释,“水杯里的水按照“后进先出”的顺序被倒进倒出,存储在栈中数据也是是按照“后进先出”的方式被插入和删除的。”

“原来是这样啊!”子渊好像明白了些什么,但还是有很多的疑问,“可是这样的数据结构有什么作用呢?”

“要知道栈有什么用途,首先我们要搞清楚它本身的属性和能够实现的基本操作。子渊你想想看,这个像装水的杯子一样的数据容器——栈,它应该具备哪些属性和进行哪些操作呢?”

“存储数据的容器,像装水的杯子一样。。。。。嗯!那它应该可以插入和删除数据。对了,栈用什么来装这些数据啊?”子渊的问题就像水里的气泡一样不断地往外冒。

“栈可不是什么天外来客,它建立在各种程序设计语言的原有数据类型的基础上,比如PASCAL语言,我们可以用内置的数组或链表数据类型来实现栈结构。”爸爸解释道,“那你知道该如何用数组来实现栈的基本属性和操作吗?先考虑栈的属性,它具有哪些基本属性呢?”

“栈的属性?像装水的杯子一样的栈?首先应该要有一个容量属性吧,比如杯子的容量有200ML500ML等。”子渊回答。

“确实是这样!但不止这一个。实际上栈有三个基本属性:最大容量(最大高度),实际存储量(实际高度),栈空指示标志。计算机科学家用“栈顶”来指示栈的实际高度,用“栈底”来作为栈空指示标志。当栈顶和栈底指向同一位置时,表示栈内没有存储元素,即栈为空。”

“这样啊!那栈的基本操作是不是删除和插入元素呢?”

“不错,这正是栈最基本的操作,就像杯子可以用来装水和倒水一样。需要注意的是,正如杯子的装水和倒水动作都是在最上层的水面进行,栈的插入和删除操作也只能在栈顶进行。我们称插入操作为入栈或进栈,而删除操作为出栈或退栈。”爸爸回答道,“那么,我们是不是只需要这两种基本操作就行了呢?”

“还有别的?那会是什么操作呢?”子渊陷入了沉思。

“子渊,你想想看,我们在往杯子里加水的时候是不是一直不停地加啊?”爸爸又给出了提示。

“啊?不是啊!杯子满了就不能再加了。对了,我们还要做一个判断栈满的操作。”

“还有呢?”

“往里加水的时候要判断栈满,那往外倒水的时候就应该判断栈空了——我们还要做一个判断栈空的操作。”

“不错,能够触类旁通,脑子转得挺快的啊!另外,我们并不是一拿到杯子就要喝水,有些时候我们只是想看看杯子里面的水干不干净,并不一定要往外倒水。这也可以看成是一个基本操作:获取栈顶元素的值。”

“栈顶元素?”

“是啊,我们把栈顶所指的元素称为栈顶元素。”

“原来是这样啊!那栈这种数据结构就是有三个基本属性和五个基本操作了咯?”

“正确。现在就请你写出实现它的PASCAL代码吧。”爸爸又交代了任务,“顺便说一句,那个分离数字的问题用栈可以很漂亮地解决。”

十分钟过去了。。。。。。

子渊在电脑里写出代码,并且编译通过,赶紧把爸爸拉过来请他检查。

下面是代码:

{代码3}

{利用栈解决分离数字问题:输入一个正整数n,试分离并输出其各位数字}

PROGRAM
Separate(INPUT, OUTPUT);

CONST

    MAXCAPACITY = 100; {栈的最大容量}

    BOTTOM = 0;        {栈底标志}

     

TYPE

    ElemType = integer;  {栈内元素数据类型}

    Stack   
= array [1..MAXCAPACITY] of ElemType; {
用数组表示的栈}

 

VAR

    s   
: Stack;       {
定义s为栈}

    top 
: integer;     {
栈顶标志}

    v, n : integer;

 

FUNCTION
StackEmpty(s : Stack; top : integer) : boolean; {
判断是否栈空}

begin

    StackEmpty := (top = BOTTOM);

end;
{StackEmpty}

   

FUNCTION
StackFull(s : Stack; top : integer) : boolean; {
判断是否栈满}

begin

    StackFull := (top = MAXCAPACITY);

end;
{StackFull}

   

FUNCTION
GetTop(s : Stack; top : integer)  :
ElemType; {
获取栈顶元素的值}

begin

    if StackEmpty(s, top) then

        writeln('underflow')

    else

        GetTop := s[top];

end; {GetTop}

 

PROCEDURE
Push(var s : Stack; var top : integer; data : ElemType); {
入栈}

begin

    if StackFull(s, top) then

        writeln('overflow')

    else

    begin

        inc(top);

        s[top] := data;

    end; {if}

end; {Push}

   

PROCEDURE
Pop(var s : Stack; var top : integer) ; {
出栈}

begin

    if StackEmpty(s, top) then

        writeln('underflow')

    else

        dec(top);

end; {Pop}

   

BEGIN {MAIN}

    top := 0; {栈顶初始化}

 

    writeln('Input n:');

    readln(n);

   

    while n <> 0 do {分离数字并将其入栈}

    begin

        v := n mod 10; {分离出n的个位数字}

        Push(s, top, v);      {个位数字入栈}

        n := n div 10; {去除n的个位数字}

    end; {while}

   

    while not StackEmpty(s, top) do {输出数字并出栈}

    begin

        write(GetTop(s, top) : 2);

        Pop(s, top);

    end; {while}

END.

 

爸爸终于笑了,子渊长长地舒出一口气——考试通过咯。

 

抱歉!评论已关闭.