资源描述：
《数据结构实验报告共享栈.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数 据 结 构 实验报告成绩_____学号1217417007姓名严梦授课教师黄 欣专业12信计实验报告递交日期10/8实验题目两个栈共享向量（栈类型定义如下），它们的栈底分别设在向量的两端，编制程序完成共用栈操作。一．需求分析1．程序实现的功能：完成共用栈操作。编制函数：1).元素x进栈i函数；voidpush(seqstack*s,inti,datatypex);2).栈i退栈，并返回原栈顶元素函数；datatypepop(seqstack*s,inti);3).取栈i顶元素函数；datatype
2、top(seqstack*s,inti);4).显示共用栈内容；voidshow(seqstack*s);5).主函数完成功能：a).开辟栈空间;b).两个栈分别进栈若干个元素;c).两个栈分别退栈或取栈顶若干个元素;d).显示最后栈内容;2．数据输入的内容﹑输入形式与范围输入所创建的栈规模n1，n2；输入进栈数据，其类型是整型数；输入数据以回车符相隔。3．数据输出的内容与形式输出取栈或出栈数据，输出共用栈元素,数据以回车符相隔。二.主要算法的算法思想.1．开辟栈空间：定义数组开辟静态空间存储共用栈2
3、.元素x进栈i函数：判断进栈i，判断栈i是否已满，不满则执行进栈操作，否则不执行。3.栈i退栈，并返回原栈顶元素函数：判断退栈i，判断栈i是否已空，非空则执行退栈操作，否则不执行。4.取栈i顶元素函数:判断取栈i，判断栈i是否为空，非空则执行取栈顶操作，否则不执行。5.主函数:开辟栈空间；依次调用进栈函数、退栈函数；调用去栈顶函数、显示共用栈函数。三.设计：1．共用栈存储结构：顺序表。共用栈类型定义：typedefstruct{datatypev[m];Inttop0,top1;}seqstack;/
4、*单链表结点类型*/2．参数表（列出所有的符号常量与全局变量）参数名数据传递方式数据内容传递所属函数m符号常量宏定义100所有函数3．函数间的调用关系图4．列出每个函数的函数声明、函数作用、函数值、形参内容与形式、主要算法步骤等1)．元素x进栈i元素函数首部：voidpush(seqstack*s,inti,datatypex);形参：seqstack*s,inti,datatypex函数作用：将元素x压入栈i顶端函数值：无局部变量无进栈算法主要步骤：(a)判别栈是否已满if(s->top0t
5、op1);(b)判别进栈iif(s->top0==i);(c)栈顶位置移动s->top0++;elses->top1--;(d)元素x进栈s->v[s->top]=x;2）．栈i退栈，并返回原栈顶元素函数函数首部：datatypepop(seqstack*s,inti);形参：seqstack*s,inti函数作用：栈i退栈，并返回原栈顶元素函数值：datatypedata局部变量datatypedata算法主要步骤：判断是否为空栈：(a)若空，则输出“upflowerror”if(s->top0<0
6、)printf("upflowerror");if(s->top1>99)printf("upflowerror");(b)若不为空，则退栈，取栈顶元素并栈顶标志移动data=s->v[s->top0];s->top0--;data=s->v[s->top1];s->top1++;3).取栈i顶元素函数函数首部：datatypetop(seqstack*s,inti);形参：seqstack*s,inti函数作用：读取栈i的栈顶元素。函数值：datatypedata局部变量：datatyped
7、atadata算法主要步骤：(a)判断栈i是否为空；if(s->top0==i){if(s->top0<0)printf("emptyerror");}(b)读取栈i栈顶元素；data=s->v[s->top0]；(c)将读取的元素返回；return(data);四.调试分析：1．调试中出现的问题，解决的办法1）．Top0未定义，直接用s->top0,还减少变量。2．每个函数的时、空复杂性分析1）．voidpush(seqstack*s,inti,datatypex);x进入栈i；T(n)=O(1
8、)，S(n)=O(n);2）．datatypepop(seqstack*s,inti);退栈i；T(n)=O(1),S(n)=O(n);3).datatypetop(seqstack*s,inti);取栈i栈顶函数T(n)=O(1),S(n)=O(1);4).voidshow(seqstack*s);显示共用栈内容T(n)=O(1),S(n)=O(1);5).main()主函数T(n)=O(1)，S(n)=O(n).3．改进设想，经验体会多个栈共用一个数
