北理工数据结构作业2.doc
《北理工数据结构作业2.doc》由会员分享,可在线阅读,更多相关《北理工数据结构作业2.doc(9页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、如有侵权,请联系网站删除,仅供学习与交流北理工数据结构作业2【精品文档】第 9 页第三章作业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);答:stack2、 简述下列算法的功能(栈的元素类型SElemTyp
2、e为int)。(1)Ststus algo1(Stack S) int I, n, A255; n=0; while ( ! StackEmpty(S) ) n+; Pop(S, An); for ( i=1; i=n; i+ ) Push(S, An);答:实现栈中元素的逆置(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);
3、 Push (S, d);答:通过栈T的辅助删除栈S中所有值为e的元素3、 设有4个元素1、2、3、4依次进栈,而出栈操作可随时进行(进出栈可任意交错进行,但要保证进栈次序不破坏1、2、3、4的相对次序),请写出所有可能的出栈次序。答:共14种情况,顺序如下:1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3421,3241,3214,4321。4、 写出下列程序段的输出结果(队列中的元素类型QelemType为char)。viod main ( ) Queue Q; InitQueue(Q);char x=e, y=c;EnQueue(Q,
4、 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);答:cha5、 简述下列算法的功能(栈和队列的元素类型均为int)。void algo3(Queue &Q) Stack S; int d; InitStack (S); while ( ! QueueEmpt(Q) ) DeQueue(Q, d); Push(S, d);while ( ! StackEmpty(
5、S) ) Pop(S, d); EnQueue(Q, d);答:利用栈S将队列Q中的元素进行逆置。6、 为了充分利用空间,将两个栈共同存储在长度为n的一维数组中,共享数组空间。设计两个栈共享一维数组的存储表示方式,画出示意图。答:设计两个栈Stack1和Stack2共享数组空间,Stack1的栈底放在数组的首端,Stack2的栈底放在数组的尾端,分别向两个栈中存储相应的元素,两个栈的栈顶分别向数组中间扩展。当总的存储空间不大于数组长度时,数组空间将得到最大利用。当两个栈占满整个数组空间时,这时两个栈共享一个长度为n的数组空间,再向栈中放元素时会发生上溢。0(Stack1底)12Stack1顶S
6、tack2顶n-3n-2n-1(Stack2底)实验二1、简单计算器。请按照四则运算加、减、乘、除、幂()和括号的优先关系和惯例,编写计算器程序。要求: 从键盘输入一个完整的表达式,以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如,输入:4+2*5=输出:14 输入:(4+2)*(2-10)=输出:-48程序如下:#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 100 /存储空间初始分配量#
7、define STACKINCREMENT 10 /存储空间分配增量typedef struct/定义运算符栈数据类型 char *base; char *top; int stacksize;SqStack1;typedef struct/定义操作数栈数据类型 int *base; int *top; int stacksize;SqStack2;int InitStack1(SqStack1 &S)/构造一个空的运算符栈 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S.base) exit(OVERFLOW); S.top
8、=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack1int InitStack2(SqStack2 &S)/构造一个空的操作数栈 S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack2char GetTop1(SqStack1 S)/若栈不空,则用char型元素e返回S的栈顶元素,并返回OK;否则返回E
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北理工 数据结构 作业
限制150内