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

姓名：阚姗蕾 学号：2010012030037上机实验三ex3_1：一、程序流程说明链栈 1）链栈结点类型定义为： typedef struct node int data; struct node *next; node_type;2）编写进栈函数push3）编写出栈函数pop4）编写main函数，首先建立一空链栈； 调用进栈函数，将从键盘输入的数据元素逐个进栈，输入0结束；显示进栈后的数据元素； 调用两次出栈函数，显示出栈后的数据元素。二、程序代码#include#include/定义链栈typedef struct node_type int data; struct node_type *next; node_type;typedef struct stack_type node_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 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; printf(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); printf(nThe length of the stack is:n%dn,stack.length); printf(The first number to popn); printf(%dn,pop(&stack); printf(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 pop4stack after pop:Process returned 0 (0x0) execution 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 20typedef struct 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 -9 7 -10 20；然后调用aa函数，并将aa函数调用前后队列的数据元素分别输出到屏幕上。 二、程序代码#include#include#include#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!); else out=q-dataq-front; q-front=(q-front+1)%N; return(out);/入队函数void enqueue(queue_type *q,int newnum) if(q-rear+1)%N=q-front) printf(the queue is 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=dequeue(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函数头中出现了总是满足的条件(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函数中没有循环解决办法：再定义一个变量t，使算法循环ex3_3：一、程序流程说明书上第12题：1、创建两个栈公用一个以为数组空间Sm,他们的栈底分别设在一维数组的两端。2、编写函数，取栈顶元素get（i），其中i为0或1，表示堆栈号。二、程序代码#include#include#define m 100/创建两个栈公用一个以为数组空间Sm,他们的栈底分别设在一维数组的两端。typedef struct stack_type int stackm; int top1; int top2; stacktype;/出栈int get(int i,stacktype *s) int 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); while(scanf(%d,&data)&data!=0)/输入元素，以0为结束 s.stacks.top1=data; s.top1+; s.top1-; printf(Please enter the second stack:n); while(scanf(%d,&data)&data!=0)/输入元素，以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 top of stack2 is:-1请按任意键继续. . .四、上机遇到的问题1）问题：Error C:UsersAdministratorDesktop大二学习软基上机未命名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+；来调整其指向 ex3_4：一、程序流程说明书上第13题：1、创建一维数组Sqm,存储循环队列的元素2、设立标志tag，区分头尾指针相同时队列是空是满2、编写此队列相对应的入队列和出队列函数二、程序代码#include#include#include#define N 20int tag = 0;/定义循环队列typedef struct int dataN; int front, rear; queue_type;/出队函数int dequeue(queue_type *q) int out; if(q-rear =q -front&tag=0) printf(the queue is NULL!); else out = q-dataq-front; q-front=(q-front+1)%N; return(out);/入队函数void enqueue(queue_type *q,int newnum) if(q-rear%N=q-front&tag=1) printf(the queue is FULL!); else q-dataq-rear=newnum; q-rear=(q-rear+1)%N; if(q-rearfront)tag=0; /输出void showqueue(queue_type *q) int i; for(i=q-front; i!=q-rear; i=(i+1)%N) printf(%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 C:UsersAdministratorDesktop大二学习软基上机未命名3.cpp:27: error: t