北理工数据结构第三章实验报告

第三章作业

1、写出下列程序段的输出结果。 viod main ( ) { Stack S;

char x, y; InitStack (S); x=’c’; y=’k’;

Push(S, x); Push(S, ’a’); Push(S, y); Pop(S, x); Push(S, ’t’); Push(S, x); Pop(S, x); Push(S, ’s’); while ( ! StackEmpty(S) ) { Pop(S, y); printf (y); } printf(x);

}

stac k

2、简述下列算法的功能（栈的元素类型SElemType为int）。 （1）Ststus algo1(Stack S) { int I, n, A[255]; n=0;

while ( ! StackEmpty(S) ) { n++; Pop(S, A[n]); }

for ( i=1; i<=n; i++ ) Push(S, A[n]); }

将栈S中的元素以出栈的顺序排在数组中，且出栈的先后和数组的序号从小到大一致。栈S变成空栈。然后再从前到后输出数组中的数。 （2）Status algo2(Stack S, int e) { Stack T; int d; InitStack (T);

while ( ! StackEmpty(S) ) { Pop(S, d);

if ( d!=e ) Push(T, d);

}

while ( ! StackEmpty(T) ) { Pop (T, d); Push (S, d); } }

将和e一致的数排到栈底，其他元素前后顺序保持不变。

3、设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有可能的出栈次序。

可能次序：（1243）（1234）（1324）（1342）（1432）（2143）（2134）（2341）（2431） 4、写出下列程序段的输出结果（队列中的元素类型QelemType为char）。 viod main ( )

{ Queue Q; InitQueue(Q);

char x=’e’, y=’c’;

EnQueue(Q, ’h’); EnQueue(Q, ’r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q,’a’); while ( ! QueueEmpty(Q) ) { DeQueue(Q, y); printf(y); } }

答案：cha

5、简述下列算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q) { Stack S; int d; InitStack (S);

while ( ! QueueEmpt(Q) ) { DeQueue(Q, d); Push(S, d); }

while ( ! StackEmpty(S) ) { Pop(S, d); EnQueue(Q, d); } }

将队列Q中的元素的出列次序整个颠倒。

（2314）（3214）（3421）（3241）（4321）

6、为了充分利用空间，将两个栈共同存储在长度为n的一维数组中，共享数组空间。设计两个栈共享一维数组的存储表示方式，画出示意图。

栈顶

栈底 栈底

实验二

1、简单计算器。

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：

① 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ② 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。

例如，输入：4+2*5=

#include #include #define MaxSize 99

void translate(char str[],char exp[]) /*将算术表达式转换成后缀表达式*/ {

struct {

char data[MaxSize];

int top; /*top为栈顶*/

}op; /*定义一个含data和top的结构体*/

char ch; int i = 0,t = 0; op.top = -1;

输出：14 输出：-48

输入：(4+2)*(2-10)=

ch = str[i]; /*将str的每一个数转换成ch*/ i++;

while(ch != '\\0') /*ch对应不同的符号的时候对应的转换情况*/ {

switch(ch) {

case '(': /*当是（的时候，将此括号存入栈op*/ op.top++;op.data[op.top]=ch; break;

case ')':

while(op.data[op.top] != '(') /*括号内的转换优先级最高，故先提取表达式*/ {

exp[t]=op.data[op.top]; op.top--; t++; } op.top--; break; case '+': case '-':

while(op.top != -1&&op.data[op.top] != '(') {

exp[t] = op.data[op.top]; op.top--; t++; }

op.top++; /*恢复可插入位置*/ op.data[op.top] = ch; break; case '*': case '/':

while(op.top == '/'||op.top == '*') /*优先级*/ {

exp[t] = op.data[op.top]; op.top--;

t++; } op.top++;

op.data[op.top] = ch; break;

case ' ': /*忽略空格，排除误操作*/ break; default:

while(ch >= '0'&&ch <= '9') {

exp[t] = ch;t++; ch = str[i];i++; } i--;

exp[t] = '#'; /*分隔操作数，为了美观，也为了以后好分隔操作数，呵呵*/ t++; } ch = str[i]; i++; }

while(op.top != -1) /*得到剩下的部分*/ {

exp[t] = op.data[op.top]; t++; op.top--; }

exp[t] = '\\0'; /*表达式结束*/ }

float cal_value(char exp[]) {

struct {

float data[MaxSize]; int top;

}st; /*操作数栈*/ float d;

char ch; int t = 0; st.top = -1; ch = exp[t]; t++;

while(ch != '\\0') {

switch(ch) /*运算主体*/ { case '+':

st.data[st.top-1] = st.data[st.top-1]+st.data[st.top]; st.top--; break; case '-':

st.data[st.top-1] = st.data[st.top-1]-st.data[st.top]; st.top--; break; case '*':

st.data[st.top-1] = st.data[st.top-1]*st.data[st.top]; st.top--; break; case '/':

if(st.data[st.top] != 0)

st.data[st.top-1]=st.data[st.top-1]/st.data[st.top]; else {

printf(\除0是错误的\ } st.top--; break; default: d=0;

while(ch >= '0'&&ch <= '9') /*从后缀表达式中获取操作数，#作用在此体现*/ {

d = 10*d+ch-'0'; ch = exp[t];

t++; } st.top++; st.data[st.top] = d; }

ch = exp[t]; t++; }

return st.data[st.top]; }

int main() /*可以提到前面去*/ {

char str[MaxSize],exp[MaxSize]; /*str为算术表达式,exps为后缀表达式*/

printf(\表达式:\

gets(str); /*输入一个算术表达式*/ translate(str,exp); /*将算术表达式转换成后追表达式*/

printf(\计算结果:%g\\n\通过后缀表达式来求值*/ system(\ return 0; }

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