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

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

第三章作业

1、写出下列程序段的输出结果。

viodmain()

{StackS;

charx,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);

}

stack

2、简述下列算法的功能（栈的元素类型SElemType为int）。

（1）Ststusalgo1(StackS)

{intI,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）Statusalgo2(StackS,inte)

{StackT;intd;

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）（2314）（3214）（3421）

（3241）（4321）

4、写出下列程序段的输出结果（队列中的元素类型QelemType

为char）。

viodmain()

{QueueQ;InitQueue(Q);

charx=’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）。

voidalgo3(QueueQ)

{StackS;intd;

InitStack(S);

while(!QueueEmpt(Q))

{DeQueue(Q,d);Push(S,d);

}

while(!StackEmpty(S))

{Pop(S,d);EnQueue(Q,d);

}

}

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

6、为了充分利用空间，将两个栈共同存储在长度为n的一维数组

中，共享数组

空间。设计两个栈共享一维数组的存储表示方式，画出示意图。

栈顶

栈底

栈底

实验二

1、简单计算器。

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯