谁知道数据结构顺序栈的插入和删除运算源代码啊?-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

谁知道数据结构顺序栈的插入和删除运算源代码啊?

知与谁同 2018-07-15 13:12:49 1273
谁知道数据结构顺序栈的插入和删除运算源代码啊?
数据顺序 数据结构顺序栈 数据结构源代码 数据结构删除
分享到
取消 提交回答
全部回答(2)
  • 知与谁同
    2019-07-17 22:53:10
    关于二十四点游戏的编程思路与基本算法

    漫长的假期对于我来说总是枯燥无味的,闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。此游戏说来简单,就是利用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。但是其中却不乏一些有趣的题目,这不,我们刚玩了一会儿,便遇到了一个难题——3、6、6、10(其实后来想想,这也不算是个太难的题,只是当时我们的脑筋都没有转弯而已,呵呵)。

    问题既然出现了,我们当然要解决。冥思苦想之际,我的脑中掠过一丝念头——何不编个程序来解决这个问题呢。文曲星中不就有这样的程序吗。所以这个想法应该是可行。想到这里我立刻开始思索这个程序的算法,最先想到的自然是穷举法(后来发现我再也想不到更好的方法了,悲哀呀,呵呵),因为在这学期我曾经写过一个小程序——计算有括号的简单表达式。只要我能编程实现四个数加上运算符号所构成的表达式的穷举,不就可以利用这个计算程序来完成这个计算二十四点的程序吗。确定了这个思路之后,我开始想这个问题的细节。
    首先穷举的可行性问题。我把表达式如下分成三类——
    1、 无括号的简单表达式。
    2、 有一个括号的简单表达式。
    3、 有两个括号的较复4、 杂表达式。
    穷举的开始我对给出的四个数进行排列,其可能的种数为4*3*2*1=24。我利用一个嵌套函数实现四个数的排列,算法如下:
    /* ans[] 用来存放各种排列组合的数组 */
    /* c[] 存放四张牌的数组 */
    /* k[] c[]种四张牌的代号,其中k[I]=I+1。
    用它来代替c[]做处理,考虑到c[]中有可能出现相同数的情况 */
    /* kans[] 暂存生成的排列组合 */
    /* j 嵌套循环的次数 */
    int fans(c,k,ans,kans,j)
    int j,k[],c[];char ans[],kans[];
    { int i,p,q,r,h,flag,s[4],t[4][4];
    for(p=0,q=0;p<4;p++)
    { for(r=0,flag=0;r if(k[p]!=kans[r]) flag++;
    if(flag==j) t[j][q++]=k[p];
    }
    for(s[j]=0;s[j]<4-j;s[j]++)
    { kans[j]=t[j][s[j>;
    if(j==3) { for(h=0;h<4;h++)
    ans[2*h]=c[kans[h]-1]; /* 调整生成的排列组合在最终的表
    达式中的位置 */
    for(h=0;h<3;h++)
    symbol(ans,h); /* 在表达式中添加运算符号 */
    }
    else { j++;
    fans(c,k,ans,kans,j);
    j--;
    }
    }
    }

    正如上面函数中提到的,在完成四张牌的排列之后,在表达式中添加运算符号。由于只有四张牌,所以只要添加三个运算符号就可以了。由于每一个运算符号可重复,所以计算出其可能的种数为4*4*4=64种。仍然利用嵌套函数实现添加运算符号的穷举,算法如下:

    /* ans[],j同上。sy[]存放四个运算符号。h为表达式形式。*/
    int sans(ans,sy,j,h)
    char ans[],sy[];int j,h;
    { int i,p,k[3],m,n; char ktans[20];
    for(k[j]=0;k[j]<4;k[j]++)
    { ans[2*j+1]=sy[k[j>; /* 刚才的四个数分别存放在0、2、4、6位
    这里的三个运算符号分别存放在1、3、5位*/
    if(j==2)
    { ans[5]=sy[k[j>;
    /* 此处根据不同的表达式形式再进行相应的处理 */
    }
    else
    }
    }

    好了,接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类,是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种,无括号自然不用另行处理;而第二种情况由以下代码可以得出其可能性有六种,其中还有一种是多余的。
    for(m=0;m<=4;m+=2)
    for(n=m+4;n<=8;n+=2)
    这个for循环给出了添加一个括号的可能性的种数,其中m、n分别为添加在表达式中的左右括号的位置。我所说的多余的是指m=0,n=8,也就是放在表达式的两端。这真是多此一举,呵呵。最后一种情况是添加两个括号,我分析了一下,发现只可能是这种形式才不会是重复的——(a b)(c d)。为什么不会出现嵌套括号的情况呢。因为如果是嵌套括号,那么外面的括号肯定是包含三个数字的(四个没有必要),也就是说这个括号里面包含了两个运算符号,而这两个运算符号是被另外一个括号隔开的。那么如果这两个运算符号是同一优先级的,则肯定可以通过一些转换去掉括号(你不妨举一些例子来试试),也就是说这一个括号没有必要;如果这两个运算符号不是同一优先级,也必然是这种形式((a+-b)*/c)。而*和/在这几个运算符号中优先级最高,自然就没有必要在它的外面添加括号了。

    综上所述,所有可能的表达式的种数为24*64*(1+6+1)=12288种。哈哈,只有一万多种可能性(这其中还有重复),这对于电脑来说可是小case哟。所以,对于穷举的可行性分析和实现也就完成了。

    接下来的问题就是如何对有符号的简单表达式进行处理。这是栈的一个著名应用,那么什么是栈呢。栈的概念是从日常生活中货物在货栈种的存取过程抽象出来的,即最后存放入栈的货物(堆在靠出口处)先被提取出去,符合“先进后出,后进先出”的原则。这种结构犹如子弹夹。
    在栈中,元素的插入称为压入(push)或入栈,元素的删除称为弹出(pop)或退栈。

    栈的基本运算有三种,其中包括入栈运算、退栈运算以及读栈顶元素,这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。

    那么作为栈的著名应用,表达式的计算可以有两种方法。

    第一种方法——
    首先建立两个栈,操作数栈OVS和运算符栈OPS。其中,操作数栈用来记忆表达式中的操作数,其栈顶指针为topv,初始时为空,即topv=0;运算符栈用来记忆表达式中的运算符,其栈顶指针为topp,初始时,栈中只有一个表达式结束符,即topp=1,且OPS(1)=‘;’。此处的‘;’即表达式结束符。
    然后自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W做如下不同的处理:
    1、 若W为操作数
    2、 则将W压入操作数栈OVS
    3、 且继续扫描下一个字符
    4、 若W为运算符
    5、 则根据运算符的性质做相应的处理:
    (1)、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS,并继续扫描下一个字符。
    (2)、若运算符W为表达式结束符‘;’且运算符栈栈顶的运算符也为表达式结束符(即OPS(topp)=’;’),则处理过程结束,此时,操作数栈栈顶元素(即OVS(topv))即为表达式的值。
    (3)、若运算符W为右括号且运算符栈栈顶的运算符为左括号(即OPS(topp)=’(‘),则将左括号从运算符栈谈出,且继续扫描下一个符号。
    (4)、若运算符的右不大于运算符栈栈顶的运算符(即OPS(topp)),则从操作数栈OVS中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈OPS中弹出一个运算符,设为+,然后作运算a+b,并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。

    第二种方法——
    首先对表达式进行线性化,然后将线性表达式转换成机器指令序列以便进行求值。

    那么什么是表达式的线性化呢。人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式,有时必须借助括号才能将运算顺序表达清楚,而且处理也比较复杂。

    1929年,波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系,后来人们称之为波兰表示法(Polish notation)。波兰表达式的特点是运算符位于运算对象的后面,因此称为后缀表示。在对波兰表达式进行运算,严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。
    表达式 波兰表达式
    A-B AB-
    (A-B)*C+D AB-C*D+
    A*(B+C/D)-E*F ABCD/+*EF*-
    (B+C)/(A-D) BC+AD-/

    OK,所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式,利用栈可以把表达式变换成波兰表达式,也可以利用栈来计算波兰表达式的值。

    至于转换和计算的过程和第一种方法大同小异,这里就不再赘述了。

    下面给出转换和计算的具体实现程序——

    /* first函数给出各个运算符的优先级,其中=为表达式结束符 */
    int first(char c)
    { int p;
    switch(c)
    { case '*': p=2; break;
    case '/': p=2; break;
    case '+': p=1; break;
    case '-': p=1; break;
    case '(': p=0; break;
    case '=': p=-1; break;
    }
    return(p);
    }
    /* 此函数实现中缀到后缀的转换 */
    /* M的值宏定义为20 */
    /* sp[]为表达式数组 */
    int mid_last()
    { int i=0,j=0; char c,sm[M];
    c=s[0]; sm[0]='='; top=0;
    while(c!='\0')
    { if(islower(c)) sp[j++]=c;
    else switch(c)
    { case '+':
    case '-':
    case '*':
    case '/': while(first(c)<=first(sm[top]))
    sp[j++]=sm[top--];
    sm[++top]=c; break;
    case '(': sm[++top]=c; break;
    case ')': while(sm[top]!='(')
    sp[j++]=sm[top--];
    top--; break;
    default :return(1);
    }
    c=s[++i];
    }
    while(top>0) sp[j++]=sm[top--];
    sp[j]='\0'; return(0);
    }
    /* 由后缀表达式来计算表达式的值 */
    int calc()
    { int i=0,sm[M],tr; char c;
    c=sp[0]; top=-1;
    while(c!='\0')
    { if(islower(c)) sm[++top]=ver[c-'a'];/*在转换过程中用abcd等来代替数,
    这样才可以更方便的处理非一位数,
    ver数组中存放着这些字母所代替的数*/
    else switch(c)
    { case '+': tr=sm[top--]; sm[top]+=tr; break;
    case '-': tr=sm[top--]; sm[top]-=tr; break;
    case '*': tr=sm[top--]; sm[top]*=tr; break;
    case '/': tr=sm[top--];sm[top]/=tr;break;
    default : return(1);
    }
    c=sp[++i];
    }
    if(top>0) return(1);
    else
    }

    这样这个程序基本上就算解决了,回过头来拿这个程序来算一算文章开始的那个问题。哈哈,算出来了,原来如此简单——(6-3)*10-6=24。

    最后我总结了一下这其中容易出错的地方——

    1、 排列的时候由于一个数只能出现一次, 所以必然有一个判断语句。但是用什么来判断,用大小显然不行,因为有可能这四个数中有两个或者以上的数是相同的。我的方法是给每一个数设置一个代号,在排列结束时,通过这个代号找到这个数。

    2、在应用嵌套函数时,需仔细分析程序的执行过程,并对个别变量进行适当的调整(如j的值),程序才能正确的执行。

    3、在分析括号问题的时候要认真仔细,不要错过任何一个可能的机会,也要尽量使程序变得简单一些。不过我的分析可能也有问题,还请高手指点。

    4、在用函数对一个数组进行处理的时候,一定要注意如果这个数组还需要再应用,就必须将它先保存起来,否则会出错,而且是很严重的错误。

    5、在处理用户输入的表达式时,由于一个十位数或者更高位数是被分解成各位数存放在数组中,所以需对它们进行处理,将它们转化成实际的整型变量。另外,在转化过程中,用一个字母来代替这个数,并将这个数存在一个数组中,且它在数组中的位置和代替它的这个字母有一定的联系,这样才能取回这个数。

    6、由于在穷举过程难免会出现计算过程中有除以0的计算,所以我们必须对calc函数种对于除的运算加以处理,否则程序会因为出错而退出(Divide by 0)。

    7、最后一个问题,本程序尚未解决。对于一些比较著名的题目,本程序无法解答。比如说5、5、5、1或者8、8、3、3。这是由于这些题目在计算的过程用到了小数,而本程序并没有考虑到小数。
    0 0
  • 青衫无名
    2019-07-17 22:53:10
    你需要堆栈的插入和删除方法。
    插入方法是Push()返回值为空 定义为: public void Push()
    删除方法是Pop() 返回值为objcet 定义为: public object Pop()
    0 0
添加回答
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

最新问题