数据结构--顺序栈的基本运算.doc

数据结构上机报告_年_月_日姓名_ 学号_ 同组成员 _1. 实验题目及要求实验一：顺序栈的各种基本运算编写一个程序，实现顺序栈的各种基本运算，并在基础上完成以下功能:1) 初始化顺序栈；2) 判断顺序栈是否为空；3) 依次进栈元素a,b,c,d,e；4) 判断顺序栈是否为空；5) 输出栈长度；6) 输出从栈顶到栈底的元素；7) 读出栈顶元素；8) 删除栈顶元素；9) 输出从栈顶到栈底的元素；10) 判断顺序栈是否为空；11) 释放栈。2. 需求分析首先初始化顺序栈（1） 判断顺序队列S是否为空输入参数的格式和合法取值范围：若顺序栈内无元素则输出顺序栈为空，反之输出顺序栈为非空。输出格式：判断顺序栈是否为空：测试数据：初始化顺序表后，显示顺序栈为空。（2） 依次进栈元素a,b,c，d，e 输入参数的格式和合法取值范围：依次进栈元素a,b,c,d,e并用逗号分隔。输出格式：依次进栈元素a,b,c,d,e。测试数据：依次进队列元素a,b,c,d,e后，顺序栈中包含a,b,c,d,e五个元素 。（3） 输出栈的长度 输入参数的格式和合法取值范围： 此时顺序栈中包含a,b,c,d,e五个元素，故长度为5。输出格式：输出栈长度：5。测试数据：此时顺序栈中的元素为a,b,c,d,e。所以屏幕显示输出栈长度：5。（4） 输出从栈顶到栈底的元素输入参数的格式和合法取值范围：进栈顺序依次为a,b,c,d,e，故栈底为a，栈顶为e，则栈顶到栈底元素依次为e,d,c,b,a。输出格式：输出从栈顶到栈底的元素：edcba测试数据：进栈顺序依次为a,b,c,d,e，故栈底为a，栈顶为e，则栈顶到栈底元素依次为e,d,c,b,a。（5） 读出栈顶元素输入参数的格式和合法取值范围：顺序栈中元素从栈顶到栈底依次为e,d,c,b,a。故栈顶为e。输出格式：读出栈顶元素：e。测试数据：顺序栈中元素从栈顶到栈底依次为e,d,c,b,a。故屏幕显示读出栈顶元素为e。（6） 删除栈顶元素输入参数的格式和合法取值范围：顺序栈中元素从栈顶到栈底依次为e,d,c,b,a。故栈顶为e，删除e。输出格式：删除栈顶元素e。测试数据：顺序栈中元素从栈顶到栈底依次为e,d,c,b,a。进行删除栈顶元素操作，即删除元素e。 （7） 输出从栈顶到栈底的元素输入参数的格式和合法取值范围：此时删除了栈顶元素e，栈顶元素变为d，故顺序栈中元素从栈顶到栈底依次为d,c,b,a，输出格式：输出从栈顶到栈底的元素：dcba测试数据：此时栈顶到栈底元素依次为d,c,b,a，故屏幕显示输出从栈顶到栈底的元素：dcba。 3. 概要设计（1） 给出所用抽象数据类型的逻辑定义。 ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,n,n0 结构关系：R=| ai-1,ai D,i=2,n 基本操作： InitStack (&S) 操作前提：S是一个未初始化的空栈。 操作结果：构造一个空栈S。 DestroyStack (&S) 操作前提：栈S已存在。操作结果：栈S清被摧毁。 StackEmpty (S) 操作前提：栈S已存在。操作结果：若栈S为空栈，则返回TURE，否则返回FALSE。 StackJudgement 操作前提：栈S已存在。 操作结果：若栈S为空栈，则输出是，没否则输出否。 StackLength (S) 操作前提：栈S已存在。操作结果：返回S的元素个数。 Push (&S,e)操作前提：栈S已存在。操作结果：插入元素e为新的栈顶元素。 GetTop (S,&e) 操作前提：栈S已存在且非空。操作结果：用e返回S的栈顶元素。 Pop（&S,&e）操作前提：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse(S,visit() 操作前提：栈S已存在且非空。操作前提：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。（2） 画出各模块之间的调用关系图。main DestroyStackInitStackStackEmpty StackJudgement StackLengthPush GetTop PopStackTraverse （3） 用伪码给出主程序的主要处理过程。 #include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2typedef int Status;typedef char SElemType;Status visit(SElemType e);#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;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;Status DestroyStack (SqStack &S) free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;Status StackEmpty (SqStack S) if(S.top=S.base)return TRUE;elsereturn FALSE;Status StackJudgement(SqStack S)if(S.top=S.base)printf(是n);elseprintf(否n);return OK;Status 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;int StackLength (SqStack S) return S.top-S.base;/ StackLengthStatus visit(SElemType e) printf(%c,e);return OK;Status GetTop (SqStack S, SElemType &e) if(S.top=S.base) return ERROR;e = *(S.top-1);return e;Status Pop (SqStack &S, SElemType &e) if(S.top=S.base) return ERROR;e= * -S.top;return e;Status StackTraverse (SqStack S, Status( *visit)(SElemType) while(S.top!=S.base) visit(*-S.top); return OK;void main() SElemType e;SqStack S;printf(1)初始化顺序栈。n);InitStack(S);printf(2)判断顺序栈是否为空:n);StackJudgement(S);StackEmpty(S);printf(3)依次进栈元素a,b,c,d,e:n);Push(S,a);Push(S,b);Push(S,c);Push(S,d);Push(S,e);printf(4)判断顺序栈是否为空:n);StackJudgement(S);StackEmpty(S);printf(5)输出栈长度:%dn,StackLength(S);printf(6)输出从栈顶到栈底的元素:n);StackTraverse(S,visit);printf(n);printf(7)读出栈顶元素:%cn,GetTop(S,e);printf(8)删除栈顶元素:%cn,Pop(S,e);printf(9)输出从栈顶到栈底的元素:n);StackTraverse(S,visit);printf(n);printf(10)判断顺序栈是否为空n);StackEmpty(S);StackJudgement(S);printf(11)释放栈。);DestroyStack(S);4. 详细设计（1） 类型定义 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;（2） 给出所用抽象数据类型中每个操作的伪码算法 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;Status DestroyStack (SqStack &S) free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;Status StackEmpty (SqStack S) if(S.top=S.base)return TRUE;elsereturn FALSE;Status StackJudgement(SqStack S)if(S.top=S.base)printf(是n);elseprintf(否n);return OK;Status 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;int StackLength (SqStack S) return S.top-S.base;/ StackLengthStatus visit(SElemType e) printf(%c,e);return OK;Status GetTop (SqStack S, SElemType &e) if(S.top=S.base) return ERROR;e = *(S.top-1);return e;Status Pop (SqStack &S, SElemType &e) if(S.top=S.base) return ERROR;e= * -S.top;return e;Status StackTraverse (SqStack S, Status( *visit)(SElemType) while(S.top!=S.base) visit(*-S.top); return OK;（3） 给出其他模块的伪码算法 void main() SElemType e;SqStack S;printf(1)初始化顺序栈。n);InitStack(S);printf(2)判断顺序栈是否为空:n);StackJudgement(S);StackEmpty(S);printf(3)依次进栈元素a,b,c,d,e:n);Push(S,a);Push(S,b);Push(S,c);Push(S,d);Push(S,e);printf(4)判断顺序栈是否为空:n);StackJudgement(S);StackEmpty(S);printf(5)输出栈长度:%dn,StackLength(S);printf(6)输出从栈顶到栈底的元素:n);StackTraverse(S,visit);printf(n);printf(7)读出栈顶元素:%cn,GetTop(S,e);printf(8)删除栈顶元素:%cn,Pop(S,e);printf(9)输出从栈顶到栈底的元素:n);StackTraverse(S,visit);printf(n);printf(10)判断顺序栈是否为空n);StackEmpty(S);StackJudgement(S);printf(11)释放栈。);DestroyStack(S);5. 调试分析（1） 调试过程中主要遇到哪些问题？是如何解决的？ 在调试过程中，输出从栈顶到栈底的元素时出现了问题，使得输出不是字母而是数字，后发现原因在输出的数据类型错误，从而输出数字，将输出数据类型改为%c字符型后结果正确。（2） 经验和体会通过这次试验，我深切的理解了顺序栈的知识要点和表示与实现。并通过C语言实现了顺序队列的初始化，判空，删除，插入，等。进一步熟练了C语言操作环境。6. 测试结果7. 附件#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2typedef int Status;typedef char SElemType;Status visit(SElemType e);#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;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;Status DestroyStack (SqStack &S) free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;Status StackEmpty (SqStack S) if(S.top=S.base)return TRUE;elsereturn FALSE;Status StackJudgement(SqStack S)if(S.top=S.base)printf(是n);elseprintf(否n);return OK;Status 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;int StackLength (SqStack S) return S.top-S.base;/ StackLengthStatus visit(SElemType e) printf(%c,e);return OK;Status GetTop (SqStack S, SElemType &e) if(S.top=S.base) return ERROR