数据结构上机顺序栈建立.doc

1. 上机题目顺序栈的建立及基本操作实现，要求建立一个顺序栈，并且执行初始化、入栈、出栈、栈的清空、栈中元素计数等功能。2. 需求分析本次程序设计要求建立一个顺序栈，并且执行初始化、入栈、出栈、栈的清空、栈中元素计数等功能。（1） 输入形式为从键盘输入，用户根据界面的提示从键盘直接输入所对应的数即可。输入的值为正数或字符，用户输入其他的数据会产生错误。（2） 系统按照用户输入的数据类型，将会把相应的输出结果显示到界面上。（3） 测试：按照提示建立一个单链表，按照提示进行初始化、入栈、出栈、栈的清空、栈中元素计数等操作测试程序是否正确。3. 概要设计（1） 数据结构定义：#include stdio.h#include stdlib.h#define STACK_INIT_SIZE 10 / 存储空间初始分配量#define STACKINCREMENT 2 / 存储空间分配增量#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;typedef char SElemType; / 定义栈元素类型(2)画出各模块之间的调用关系图。Main()（） Int( )StatusListInsert()voidListEmpt()ySearchList( )GHhh()Listlength( )StatusListDelete()用伪码给出主程序的主要处理过程。4. 详细设计InitStack（&S)构造一个空栈。 Push(&S，e)插入元素为e的新栈顶。Pop（&s，&e）删除栈顶元素用e返回ClearStack(&s)清空栈StackEmpty(s)栈是否为空GetTop(s,&e)用e返回s的栈顶元素StackLength(&s)计算栈长度(2) 主要伪代码： 插入元素为e的新栈顶。Status Push(SqStack &S) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base, (S.stacksize+=STACKINCREMENT)*sizeof(SElemType); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; 删除栈顶元素用e返回Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; S.top-; e=*S.top ; return OK; /检验栈是否为空Status StackEmpty(SqStack &S) if(S.top=S.base) printf(栈为空); elseprintf(栈不为空); return OK; 用e返回s的栈顶元素Status GetTop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; p-; e=*p; return OK; 栈的长度Status StackLength(SqStack &S) if(S.base=NULL) return ERROR; else return OK; 清空栈Status ClearStack(SqStack &S) if(S.base=NULL) return ERROR; else S.top=S.base; return OK; 5. 调试分析在调试的时候初期的时候，我们解决了一些常见的错误，一些失误引起的语法错误，但是我也看到了我的程序的很多不足之处，例如：因为程序比较长，运行时如果没有表达清楚，很难进行操作，我在编程时没有明确提示，这样用起来我们自己都觉得别扭。在老师的指导下，我在程序中添加了printf(“输入、”);等语句，这样看的时候就一目了然，很方便。由于时第一次进行数据结构上机实验，把算法和C语言编程结合起来有点困难，总是把C语言编程的方法用在数据结构中，于是造成程序十分复杂，并且存在很多错误，在网上找了很多关于数据结构的算法编程才明白了一些，就是用C语言的方法把算法表示出来，只要熟记一些代码，多进行一些练习就显得比较简单了。6. 使用说明1 建立顺序栈:先输入顺序栈的元素个数，按ENTER键，输入第一个元素后，再按ENTER键换行输入第二个元素，同样操作进行下面。2 选项2是测试顺序栈是否为空。3 输入3选项是计算栈长度。4 选项4是读出栈顶元素。5 选项5元素出栈。6 选项6是销毁栈。7. 测试结果采用测试数据，列出实际的输入、输出结果。输入输出如截图：8. 附件/顺序栈#include stdio.h#include stdlib.h#define STACK_INIT_SIZE 10 / 存储空间初始分配量#define STACKINCREMENT 2 / 存储空间分配增量#define OVERFLOW -2#define OK 1#define ERROR 0typedef int Status;typedef char SElemType; / 定义栈元素类型/ 顺序栈 struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 ; Status InitStack(SqStack &S) S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStackStatus Push(SqStack &S,SElemType &e) if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK; Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; S.top-; e=*S.top ; return OK; /Pop Status StackEmpty(SqStack &S) if(S.top=S.base) printf(栈为空); elseprintf(栈不为空); return OK; /Empty Status GetTop(SqStack &S,SElemType &e) char *p=S.top ; if(S.top=S.base) printf(栈为空);return ERROR; p-; e=*p; printf(n栈顶元素为：%d,*p); return OK; /GetTop Status StackLength(SqStack &S) if(S.base=NULL) return ERROR; else printf(栈长为%d,S.top-S.base); return OK; /StackLength Status ClearStack(SqStack &S) if(S.base=NULL) return ERROR; else S.top=S.base; printf(栈已清空); return OK; /ClearStack int menu() int n;printf(n 主菜单);printf(n*);printf(n1.元素入栈2.测试栈是否为空);printf(n3.计算栈长 4.取出栈顶元素);printf(n5.元素出栈6.清空栈);printf(0.退出n);printf(n*n);printf(n请输入选项：);scanf(%d,&n);return n; /menu void main() int n; SElemType e; SqStack s; InitStack(s); n=menu(); while(n) switch(n) case 1:int i;printf(请输入要进栈的元素个数：n);scanf(%d,&n); InitStack(s);printf(请输入%d个数：n,n);for( i=1;i=n;i+) scanf(%d,&e); Push(s,e); Push(s,e); break; cas