软基上机实验报告

《软基上机实验报告》由会员分享，可在线阅读，更多相关《软基上机实验报告（8页珍藏版）》请在金锄头文库上搜索。

1、一、程序流ex3_3：教材第一章习题12题一一扩展题二、1)两个栈共用一个数组空间，它们的栈底分别在数组两端，栈顶相向而行。编写入栈 和出栈函数，实现两个栈元素分别的(但共用)入栈和出栈。三、 2)main 中函数完成以下测试：四、a、能否在共用空间上实现两个独立的栈：即能否向两个栈分别输入元素；能否分别从两个栈取出元素，每个栈取出的元素的顺序符合各自栈的特点五、b、能否在共用空间用满时，及时制止新的入栈行为。六、例如：七、假设数组大小为6, main函数实现以下动作，向栈1接连入栈4个元素后， 向栈2入栈2个元素致栈满，再向栈2输入一个元素，将报错。接着从栈1出栈1个元素， 再向栈2入栈，就

2、会成功。最后，两个栈分别出空，观察输出顺序是否满足栈的特点。八、程说明九、ex3_4：教材第一章习题13题一一扩展题十、 1)实现一种扩展的循环队列，使得全部的数组空间都能使用，基本思路是当传统循环队列放满时：即十一、(rear+1)%MAXNUM =front 为真十二、时，可以再入队一个元素，接着rear = (rear+1)%MAXNUM后就会与front相等，此 时将另外一个变量flag设置为1,表示此时的rear=front不是为空，而是满。否则flag为0 时，如果出现rear=front,则表示队列为空。十三、2) main()函数实现以下测试：十四、a、能否实现全部“装满”，即

3、装入元素个数为MAXNUM十五、b、能否按照循环队列那样绕着存放空间循环存放。十六、c、能否在装满后，拒绝再装。十七、d、能否在装满后，不会变成“空”的一一即可以还可正常出队。十八、e、能否在全部出空后，不会变成“满”的一一即可还可正常入队。十九、例如：二十、假设循环队列最大空间为5, main()函数实现以下动作，接连成功入队5个元素，入队第6个元素时，报错。接着出队3个元素，入队3个元素，均成功。再入队1 个，报错。继续连续成功出队6个元素，出队第7个时报错。最后，再成功入队2个元素。拓展题 3-3：1. 首先建立一个共有一个数组空间的栈(栈一以数组空间的头为栈尾，栈二以数组空间的 尾为栈

4、尾)2. 进栈：首先进行两步判断，先对栈顶的合理性进行判断，如果栈一的栈顶小于一或栈二 的栈顶大于数组空间长度，返回错误，然后再对栈是否已满进行判断，如果已满，返回 错误。接着进行入栈，如果入栈一，将元素赋予栈一的栈顶，将栈一的顶加一，如果入 栈二，将元素赋予栈二的栈顶，将栈二的顶减一。3. 出栈：根据所入的栈进行判断，如果该栈已空，返回错误。然后进行出栈，如果是栈一， 将栈顶减一，如果是栈二，将栈顶减一即可。拓展题 3-4：由于队头不储存元素，所以传统的方法无法完全利用分配的存储空间1. 进队列函数：首先对队列是否已满进行判断，如果头尾节点相等且flag置1,那么队列已满，返回错误。然后进行

5、入队(基本题的入队方法，这里不再赘述)2. 出队列函数：首先对队列是否已空进行判断，如果头尾节点相等且flag为0那么队列 已空，返回错误。然后进行出队(基本题的出队方法，这里不再赘述)3. 主函数：设置一个flagmain位，初始为0,每一个元素进栈加一，每一个元素出栈减一, 如果为5将flag为置一，小于5时均将flag为置0.程序代码：拓展题 3-3：#include#include#define N 6typedef structint dataN;int top1;int top2;node;/进栈函数int push(node *t,int i,int x)node *p;p=t;

6、if(p-top1top2=N)printf(the top of the stack is falsen);return 0;if(t-top2+1=t-top1)printf(this stack if fulln);return 0;if(i=1)p-datap-top1=x;p-top1+;elsep-datap-top2=x;p-top2-;return 0;/出栈函数int pop(node *t,int i)node *p;p=t;if(p-top1=0&i=0)printf(stack one if NULLn);return 0;if(p-top2=N-1&i=2) prin

7、tf(stack two if NULLn);return 0;if(i=1)p-top1-;elsep-top2+;return 0;/显示函数int show(node *t)node *p;int i;p=t;if(p-top1top2=N)printf(the top of the stack is flasen);return 0;elseprintf(stack one:n); for(i=p-top1-1;i=0;i-) printf(%d ,p-datai);printf(nstack two:n); for(i=p-top2+1;idatai);return 0;int ma

8、in()node p;int i,x;p.top1=0;p.top2=N-1;printf(input four numbers to stack one:n);for(i=0;i4;i+)scanf(%d,&x);push(&p,1,x);printf(input two numbers to stack two:n);for(i=0;i2;i+)scanf(%d,&x); push(&p,2,x);printf(if I input another number to stack twon);scanf(%d,&x);push(&p,2,x);printf(now I pop one nu

9、mber in stack one and push this number to stack twon); pop(&p,1);push(&p,2,x);show(&p);拓展题 3-4：#include #include#define N 5#define true 1#define false 0 typedef structint dataN;int front, rear;int flag;node;/入队列函数int enter(node *p,int x)if(p-rear=p-front&p-flag=1)printf(now this queuetype is fulln);

10、 return (false);elsep-datap-rear=x; p-rear=(p-rear+1)%N; return (true); /出队列函数 int out(node *p)int x;if(p-rear=p-front&p-flag=0)printf(this queuetype is nulln);return (false);elsex=p-datap-front;p-front=(p-front+1)%N;return x;int main()node p;int i,x=1,flagmain=0,n;p.front=p.rear=p.flag=0;while(1)pr

11、intf(what do you want to don1.entern2.outn); scanf(%d,&n);switch(n)case 1:if(flagmain=5)printf(refuse enter!nn);break;printf(please use 0 as the endn);while(x!=0)scanf(%d,&x);enter(&p,x);if(flagmain=5)p.flag=1;elsep.flag=0; flagmain+;break;case 2:printf(please input how many numbers you want to out:

12、n); scanf(%d,&x);for(i=0;ix;i+)out(&p); flagmain-;if(flagmain!=5) p.flag=0;break;二、测试数据拓展题 3-3：输入：input four numbers to stack one:1 2 3 4input two numbers to stack two:5 6if I input another number to stack two7this stack if fullnow I pop one number in stack one and push this number to stack two 输出：s

13、tack one:3 2 1stack two:7 6 5拓展题 3-4： 输入、输出： what do you want to do1. enter2.out1please use 0 as the end1 2 3 4 5 0what do you want to do1. enter2.out1refuse enter!what do you want to do1.enter2.out2please input how many numbers you want to out:3what do you want to do1.enter2.out1please use 0 as the

14、 end1 2 3 0what do you want to do1.enter2.out1refuse enter!四、上机时遇到的问题1.问题现象： 在拓展题3-3 中，莫名的程序终止 原因：首先没有对栈顶进行初始化，其次没有对栈顶的合法性进行判断 解决方法： 针对栈1 与栈 2 的特性进行初始化，同时加入对栈顶合法进行判断的语句2. 问题现象： 在拓展题3-3 中，进栈时，还有未用空间时，就报错，说空间已满 原因：由于栈顶不储存元素，故对栈是否已满的判断出错 解决办法： 将原先的 top1+1=top2 改为 top2+1=top13. 问题现象： 在拓展题 3-4 中，当队列已满时，再入一元素时，只是提