数据结构实验报告共享栈.doc

数据结构实 验 报 告 成绩_学号1217417007姓名严梦授课教师黄欣专业12信计实验报告递交日期10/8实验题目两个栈共享向量（栈类型定义如下），它们的栈底分别设在向量的两端，编制程序完成共用栈操作。一 需求分析1程序实现的功能：完成共用栈操作。编制函数：1). 元素x进栈i函数； void push(seqstack *s,int i,datatype x);2). 栈i退栈，并返回原栈顶元素函数； datatype pop(seqstack *s,int i);3). 取栈i顶元素函数；datatype top(seqstack *s,int i);4).显示共用栈内容；void show(seqstack *s);5). 主函数完成功能：a). 开辟栈空间; b). 两个栈分别进栈若干个元素; c). 两个栈分别退栈或取栈顶若干个元素;d). 显示最后栈内容; 2数据输入的内容输入形式与范围 输入所创建的栈规模n1，n2；输入进栈数据，其类型是整型数；输入数据以回车符相隔。3数据输出的内容与形式 输出取栈或出栈数据，输出共用栈元素, 数据以回车符相隔。二. 主要算法的算法思想.1开辟栈空间：定义数组开辟静态空间存储共用栈2. 元素x进栈i函数：判断进栈i，判断栈i是否已满，不满则执行进栈操作，否则不执行。3. 栈i退栈，并返回原栈顶元素函数：判断退栈i，判断栈i是否已空，非空则执行退栈操作，否则不执行。4. 取栈i顶元素函数:判断取栈i，判断栈i是否为空，非空则执行取栈顶操作，否则不执行。5. 主函数:开辟栈空间；依次调用进栈函数、退栈函数；调用去栈顶函数、显示共用栈函数。三. 设计：1共用栈存储结构：顺序表。共用栈类型定义：typedef struct datatype vm; Int top0,top1; seqstack; /*单链表结点类型*/2参数表（列出所有的符号常量与全局变量）参数名数据传递方式数据内容传递所属函数m符号常量宏定义100所有函数3函数间的调用关系图4列出每个函数的函数声明、函数作用、函数值、形参内容与形式、主要算法步骤等1)元素x进栈i元素函数首部：void push(seqstack *s,int i,datatype x); 形参：seqstack *s,int i,datatype x 函数作用：将元素x压入栈i顶端 函数值：无 局部变量 无 进栈算法主要步骤：(a) 判别栈是否已满 if(s-top0top1);(b) 判别进栈i if(s-top0=i); (c) 栈顶位置移动 s-top0+;else s-top1-; (d) 元素x进栈 s-vs-top=x; 2）栈i退栈，并返回原栈顶元素函数 函数首部：datatype pop(seqstack *s,int i); 形参：seqstack *s,int i 函数作用：栈i退栈，并返回原栈顶元素 函数值：datatype data局部变量 datatype data 算法主要步骤： 判断是否为空栈： (a)若空，则输出“upflow error” if(s-top0top199) printf(upflow errorn); (b)若不为空，则退栈，取栈顶元素并栈顶标志移动 data=s-vs-top0;s-top0-; data=s-vs-top1;s-top1+; 3). 取栈i顶元素函数 函数首部：datatype top(seqstack *s,int i); 形参：seqstack *s,int i 函数作用：读取栈i的栈顶元素。 函数值：datatype data局部变量：datatype data data算法主要步骤：(a) 判断栈i是否为空；if(s-top0=i)if(s-top0vs-top0； (c) 将读取的元素返回；return (data); 四. 调试分析：1调试中出现的问题，解决的办法 1）Top0未定义，直接用s-top0,还减少变量。 2每个函数的时、空复杂性分析 1）void push(seqstack *s,int i,datatype x);x进入栈i；T(n)=O(1)， S(n)=O(n); 2）datatype pop(seqstack *s,int i); 退栈i； T(n)=O(1), S(n)=O(n); 3). datatype top(seqstack *s,int i); 取栈i栈顶函数 T(n)=O(1) , S(n)=O(1); 4). void show(seqstack *s);显示共用栈内容 T(n)=O(1) , S(n)=O(1); 5). main() 主函数 T(n)=O(1) ， S(n)=O(n).3改进设想，经验体会 多个栈共用一个数组，栈顶栈底位置都需要考虑。五. 使用说明：如何使用你编制的程序、操作步骤.编译程序成功后，按界面提示输入栈规模以及数据。六. 测试结果：输入输出数据内容：窗口显示如下：(下划线部分为输入部分，其余为输出部分)测试数据一：input the node n1:3input the data s1:15input the data s1:16input the data s1:17input the node n2:4input the data :21input the data :22input the data :23input the data :24pop s0 top:17pop s1 top:24top s0:16top s1:23no.0 node:15no.1node:16no.99 node:21no.98 node 22no.97 node:23测试数据二：input the node n1:1input the data s1:15input the node n2:4input the data :21input the data :22input the data :23input the data :24pop s0 top:15pop s1 top:24empty errortop s1:23no.99 node:21no.98 node 22no.97 node:23七源代码清单#include#include#define m 100typedef int datatype;typedef struct datatype vm;int top0,top1;seqstack;void main()void push(seqstack *s,int i,datatype x);datatype pop(seqstack *s,int i);datatype top(seqstack *s,int i);void show(seqstack *s);seqstack stack100;int j,n;datatype data;stack-top0=-1;stack-top1=100;printf(input the node n1:n);scanf(%d,&n);for(j=0;jtop0,data);printf(input the node n2:n);scanf(%d,&n);for(j=0;jtop1,data);data=pop(stack,stack-top0);printf(pop s0 top:%dn,data);data=pop(stack,stack-top1);printf(pop s1 top:%dn,data);data=top(stack,stack-top0); if(data0)printf(top s0 :%dn,data);data=top(stack,stack-top1);printf(top s1 :%dn,data);show(stack);void push(seqstack *s,int i,datatype x)if(s-top0top1)if(s-top0=i)s-top0+;s-vs-top0=x;elses-top1-;s-vs-top1=x;elseprintf(overflow errorn);datatype pop(seqstack *s,int i)datatype data;if(s-top0=i)if(s-top0vs-top0;s-top0-;elseif(s-top199)printf(upflow errorn);elsedata=s-vs-top1;s-top1+;return (data);datatype top(seqstack *s,int i)datatype data;if(s-top0=i)if(s-top0vs-top0;elseif(s-top199)printf(empty errorn);elsedata=s-vs-top1;return (d