软件技术基础栈和队列上机报告

1、12姓名：阚姗蕾学号： 2010012030037上机实验三ex3_1：一、程序流程说明链栈1）链栈结点类型定义为： typedef struct nodeint data;struct node *next;node_type;2）编写进栈函数 push3）编写出栈函数 pop4）编写 main 函数，首先建立一空链栈；调用进栈函数， 将从键盘输入的数据元素逐个进栈， 输入 0 结束；显示进栈 后的数据元素；调用两次出栈函数，显示出栈后的数据元素。二、程序代码#include#include/ 定义链栈typedef struct node_typeint data;struct node_

2、type *next; node_type;typedef struct stack_typenode_type *top;int length; stack_type;/ 进栈函数void push(stack_type *s,int newnode)node_type *p;p=(node_type *)malloc(sizeof(node_type); p-data=newnode;p-next=s-top;s-top=p;s-length +;/ 出栈函数int pop(stack_type *s)node_type *p;int x;if(s-top=NULL)printf(The

3、stack is NULL!n); return(0);else x=s-top-data; p=s-top;s-top=s-top-next; free(p);s-length-; return(x);/ 遍历并输出void showstack(stack_type *s)int i=0;int le;stack_type *s1;node_type *p; if(s-lengthlength=0;le=s-length;while(itop-data); i+;while(i-)/返回原栈push(s,pop(s1);int main()int num;stack_type stack;p

4、rintf(ninsert:number :n);stack.length=0;while(scanf(%d,&num)&num!=0) push(&stack,num); printf(The length of the stack is:n%d,stack.length); printf(nstack after push:n);showstack(&stack);thestackprintf(nThe length of is:n%dn,stack.length);printf(The first number to popn); printf(%dn,pop(&stack);print

5、f(The second number to popn);printf(%dn,pop(&stack);printf(nstack after pop:n);return 0;三、输入与输出insert:number :1 2 3 4 5 0The length of the stack is:5stack after push:5 4 3 2 1The length of the stack is:5The first number to pop5The second number to pop4 stack after pop:Process returned 0 （0x0） execut

6、ion time : 4.415 sPress any key to continue.四、上机遇到的问题1）问题：在主函数中调用 pop 函数时总是报错原因： pop函数头时这样写的： node_type *pop（stack_type *s） 解决办法：把 pop 改成返回 int2）问题：程序停止工作或显示 the stack is NULL!原因：在 showstack 函数中重复进行了 length 解决办法：在 showstack 函数中直接调用 push 函数进行栈的转移ex3_2：一、程序流程说明循环队列1）顺序循环队列类型定义为： #define N 20 typedef s

7、truct int dataN; int front, rear;queue_type;2）编写循环队列出队函数 dequeue3）编写循环队列入队函数 enqueue4）编写函数： void aa（queue_type *q） ； 调用出对函数把队列 q 中的元素一一出对列，如果是负数直接抛弃；如果 是正数，则调用入队函数，插入到 q 的队尾。5）编写 main函数，首先建立一个队列，其中的数据元素为： 2 3 -4 6 -5 8 -97 -10 20 ；然后调用 aa 函数，并将 aa 函数调用前后队列的数据元素分别输出 到屏幕上。二、程序代码#include#include#includ

8、e #define N 20/ 定义循环队列typedef struct int dataN; int front, rear;queue_type;/ 出队函数int dequeue(queue_type *q)int out;if(q-rear=q-front) printf(the queue is NULL!); elseout=q-dataq-front; q-front=(q-front+1)%N;return(out);/ 入队函数void enqueue(queue_type *q,int newnum)queue isif(q-rear+1)%N=q-front) print

9、f(the FULL!);else q-dataq-rear=newnum; q-rear=(q-rear+1)%N;/ 输出void showqueue(queue_type *q)int i;for(i=q-front;i!=q-rear;i=(i+1)%N)printf(%d ,q-datai);printf(n);/ 把队列 q 中的元素一一出对列，如果是负数直接抛弃；如果是正数，则调用入队函数，插入到 q 的队尾void aa(queue_type *q)int x;int t;t=q-rear-q-front+1;if(q-rear)front)t+=N;while(t-)x=de

10、queue(q);if(x0) enqueue(q,x);int main()queue_type que;int x;que.front=0;que.rear=0;while(scanf(%d,&x)!=EOF)que.dataque.rear=x; que.rear+;showqueue(&que);aa(&que);showqueue(&que);三、输入与输出2 3 -4 6 -5 8 -9 7 -10 20Z2 3 -4 6 -5 8 -9 7 -10 203 6 8 7 20 2请按任意键继续 . . .四、上机遇到的问题1)问题：程序停止工作原 因 ： 在 showqueue 函

11、 数 头 中 出 现 了 总 是 满 足 的 条 件 (i=q-front;(q-rear+1)%N!=q-front;(q-front+1)%N)解决办法：更改为 (i=q-front;i!=(q-rear+1);i=(i+1)%N) 2)问题：程序停止工作原因：没有定义 que-front 和 que-rear 的值 解决办法：把主函数中相应片段改为：que.front=0;que.rear=0;while(scanf(%d,&x)!=EOF)que.dataque.rear=x;que.rear+;3) 问题：输出时只有第一个元素按照 aa 函数的要求进行了处理 原因： aa 函数中没有

12、循环解决办法：再定义一个变量 t ，使算法循环ex3_3：一、程序流程说明书上第 12 题：1、创建两个栈公用一个以为数组空间 Sm, 他们的栈底分别设在一维数组的两 端。2、编写函数，取栈顶元素 get (i )，其中 i 为0或 1，表示堆栈号。二、程序代码#include #include #define m 100 / 创建两个栈公用一个以为数组空间 Sm, 他们的栈底分别设在一维数组的两端。typedef struct stack_typeint stackm;int top1;int top2; stacktype;/ 出栈int get(int i,stacktype *s)in

13、t out; if(i=0) out=s-stacks-top1; s-top1-; return out;else out=s-stacks-top2; s-top2+; return out;int main() stack_type s; int data; s.top1=0; s.top2=m-1; printf(Please enter the fitst stack:n);输入元素，以 0 为结束输入元素，以 0 为结束while(scanf(%d,&data)&data!=0)/ s.stacks.top1=data; s.top1+;s.top1-;printf(Please

14、enter the second stack:n);while(scanf(%d,&data)&data!=0)/s.stacks.top2=data;s.top2-;s.top2+;printf(The top of stack1 is:%dn,get(0,&s);printf(The top of stack2 is:%dn,get(1,&s);return 0; 三、输入与输出Please enter the fitst stack:1 2 3 0Please enter the second stack:-4 -3 -2 -1 0The top of stack1 is:3The to

15、p of stack2 is:-1请按任意键继续 . . .四、上机遇到的问题1)问题： Error大二学习 软基上机 未命名 3.cpp:33: error: base operand of - has non-pointer type stack_type 原因：主函数中不能用 - 代替.解决办法：将该行更改为 s.stackcount=data;2)问题：输出 The top of stack1 is:5177344The top of stack2 is:-346788601原因： top 在输入完成以后指向了栈顶元素的下一个解决办法：利用 top1- ；和 top2+ ；来调整其指向

16、ex3_4：一、程序流程说明书上第 13 题：1、创建一维数组 Sqm, 存储循环队列的元素2、设立标志 tag ，区分头尾指针相同时队列是空是满2、编写此队列相对应的入队列和出队列函数二、程序代码#include#include #include #define N 20int tag = 0;/ 定义循环队列typedef structint dataN;int front, rear; queue_type;/ 出队函数int dequeue(queue_type *q)int out;if(q-rear =q -front&tag=0) NULL!);elseout = q-dataq

17、-front;q-front=(q-front+1)%N;return(out);printf(thequeue is/ 入队函数void enqueue(queue_type *q,int newnum)if(q-rear%N=q-front&tag=1)FULL!);elseq-dataq-rear=newnum; q-rear=(q-rear+1)%N; if(q-rearfront)tag=0;printf(thequeue is/ 输出void showqueue(queue_type *q)int i;for(i=q-front; i!=q-rear; i=(i+1)%N)prin

18、tf(%d ,q-datai);printf(n);int main()queue_type q;int tag=0,data;q.front=0;q.rear=0;printf(enter the elements of the queue:n); while(scanf(%d,&data)&(data!=0) enqueue(&q,data);printf(the queue is:n);showqueue(&q);printf(the queue is:n);showqueue(&q);printf(deque:n%dn,dequeue(&q);return 0;三、输入与输出enter the elements of the queue:1 2 3 4 5 0the queue is:1 2 3 4 5the queue is:1 2 3 4 5deque:1请按任意键继续 . . .四、上机遇到的问题1)问题： Error大二学习 软基上机 未命名 3.cpp:27: error: too few argumen