数据结构作业

1、第三章3.5假设s和x用于表示堆栈进入和堆栈退出操作，初始状态和最终状态为空的堆栈进入和堆栈退出操作序列可以表示为仅由s和x组成的序列。可操作的序列称为合法序列(例如，SXXSX是合法序列，SXS是非法序列)。本文试图给出一个通用的标准来区分给定序列与合法序列或非法序列，并证明两个不同的合法(堆栈操作)序列(对于相同的输入序列)不可能得到相同的输出元素(注意：在这种情况下，它指的是元素实体，而不是值)序列。解决方案：一般规则：任何前n个序列中的s的数目必须大于或等于x的数目，并且整个序列中的s的数目必须等于x的数目。证据：让两个法律序列：T1=SXST2=SXX假设前n个操作是相同的，并且从第

2、n个操作开始，它是具有不同序列的开始操作点。由于前n个操作是相同的，此时两个堆栈(堆栈A和堆栈B)的存储条件完全相同，假设堆栈的顶部元素此时都是A。第n个1操作是不同的，所以T1的第n个1操作是s，T2的第n个1操作是x。假设B是堆叠的，T1的输出顺序必须是先B后A；T2将是一个堆栈，它的输出顺序必须是先a后B.由于T1的输出是ba而T2的输出序列是ab这表明两个不同的合法堆栈操作序列的输出元素序列一定是不同的。3.9尝试将下面的递归过程重写为递归过程。void ditui(int n)int I；i=n。而(i1)coutxif(x=0)sum=0；其他测试(总和)；sum=x；标准输出#包

3、括#定义STACK_INIT_SIZE 100#定义TURE 1#定义FALSE 0#定义ok 1#定义错误0#定义不可行-1typedef int selemtypetypedef int状态；typedef结构int * base2；selem type * top2；int stacksizesqstack。状态INITstack(sqstack * s)int * p；p=(selem type *)malloc(STACK _ INIT _ SIZE * sizeof(selem type)；(*s)。基数0=(*s)。top0=p；(*s)。基数1=(*s)。top1=p STAC

4、K _ INIT _ SIZE-1；如果(！(*s)。基本0)出口(-2)；如果(！(*s)。基地1)出口(-2)；返回ok；状态推送(sqstack * s，int i，selemtype e)if(i=0)if(*)顶部0=(*)基本0 (STACK_INIT_SIZE/2)-1)返回错误；else *(s)。top0=e；返回ok；if(i=1)if(*)顶部1=(*)base1-(STACK_INIT_SIZE/2) 1)返回错误；else *(s)。top1-=e；返回ok；返回错误；状态弹出(sqstack * s，int i，selemtype * e)if(i=0(*s)。前0

5、=(* s)。base0返回错误；if(i=1(*s)。顶部1=(*)。base1)返回错误；if(i=0) * e=*(-(*)s)。top0)；返回ok；if(i=1) * e=*(-(*)s)。top1)；返回ok；void main()sqstack sta。selem type e；selem type * p；int I；如果(INITstack(sta) printf(“已创建双堆栈 n”)；Printf(请输入推送结束(0/1)和推送元素： n )；scanf(“% d % d”，即e)；如果(推(sta，即e)打印(元素已堆叠)；Printf(请输入推送结束(0/1)和推送元

6、素： n )；scanf(“% d % d”，即e)；如果(推(sta，即e)打印(元素已堆叠)；Printf(请输入推送结束(0/1)和推送元素： n )；scanf(“% d % d”，即e)；如果(推(sta，即e)打印(元素已堆叠)；Printf(左堆栈元素：)；p=sta . base0；同时(sta.top0！=p)printf(“% d”，* p)；p；Printf(右堆栈元素：)；p=sta . base1；同时(sta.top1！=p)printf(“% d”，* p)；p-；printf( n请输入堆栈结尾(0/1): n )；scanf(“% d”，I)；如果(Pop(s

7、ta，即e) printf(n堆栈顶部元素%d从堆栈中出来n ，e)；Printf(左堆栈元素：)；p=sta . base0；同时(sta.top0！=p)printf(“% d”，* p)；p；Printf(右堆栈元素：)；p=sta . base1；同时(sta.top1！=p)printf(“% d”，* p)；p-；运行结果：3.21假设表达式由单字母变量和双目四个运算符组成。试着写一个算法，将正常书写和正确书写的表达式转换成相反的波兰表达式。解决方案：程序源代码：#包括#包括#定义尺寸100typedef char selemtypetypedef结构selemtype * bas

8、eselemtype * topint大小；堆栈；int优先(char c1，char c2)char ch5= #-*/；int i=0，j=0；如果(c1=()返回0；当(chi chi!=c1) i。如果(I=2)I-；/加和减可认为是同级别的运算符如果(I=4)I-；/乘和除可认为是同级别的运算符当chj chj！(C2)j；if(j=2)j-；if(j=4)j-；如果(ij)返回1；否则返回0；void main()堆栈无线电台临时使用许可证ch=0，CT；斯塔。base=(selem类型*)malloc(SIZE * SIZeof(selem类型)；如果(！sta.base)出口(

9、0)；斯塔。top=sta。基地；斯塔。大小=0；* sta。top=#；printf(请输入表达式： n )；同时(ch！=#*sta.base=#)ch=getchar()；如果(a=chch=z)printf(% c ，ch)；其他if(ch=#)CT=*(-sta。顶部)；同时(ct！=#)印刷字体( % c ，印刷字体)；CT=*(-sta。顶部)；-斯塔。顶部；其他if(ch=()* sta。top=ch其他if(ch=)CT=*(-sta。顶部)；同时(ct！=()印刷字体( % c ，印刷字体)；CT=*(-sta。顶部)；否则CT=*(sta。top-1)；如果(先验(ct，

10、ch)=0)* sta。top=ch否则CT=*(-sta。顶部)；同时（优先(ct，ch)印刷字体( % c ，印刷字体)；CT=*(-sta。顶部)；*(sta.top)=ch .sta.top运行结果：3.22如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。解：程序源代码：#包括#包括#定义最大大小堆栈100#定义增量10#定义ok 1#定义错误-100typedef int elemtype2typedef int状态；typedef结构elemtype2 * topelemtype2 * baseint大小； stack2状态initstack2(stack2 da)爸爸。base=(elem类型2 *)malloc(max _