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

《数据结构顺序栈的基本运算.pdf》由会员分享，可在线阅读，更多相关《数据结构顺序栈的基本运算.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.数据结构上机报告 _年_月_日 姓名_ 学号_ 同组成员 _ 1.实验题目及要求 实验一：顺序栈的各种基本运算 编写一个程序，实现顺序栈的各种基本运算，并在基础上完成以下功能:1)初始化顺序栈；2)判断顺序栈是否为空；3)依次进栈元素 a,b,c,d,e；4)判断顺序栈是否为空；5)输出栈长度；6)输出从栈顶到栈底的元素；7)读出栈顶元素；8)删除栈顶元素；9)输出从栈顶到栈底的元素；10)判断顺序栈是否为空；11)释放栈。2.需求分析 首先初始化顺序栈（1）判断顺序队列 S 是否为空 输入参数的格式和合法取值范围：若顺序栈内无元素则输出顺序栈为空，反之 输出顺序栈为非空。输出格式：判断顺序

2、栈是否为空：测试数据：初始化顺序表后，显示顺序栈为空。（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

3、,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

4、,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,

5、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)操作前提

6、：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。GetTop(S,&e)操作前提：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。Pop（&S,&e）操作前提：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。StackTraverse(S,visit()操作前提：栈 S 已存在且非空。操作前提：从栈底到栈顶依次对 S 的每个数据元素调用函数 visit()。一 旦 visit()失败，则操作失败。（2）画出各模块之间的调用关系图。main DestroyStack InitStack StackEmpty StackJudgement Stac

7、kLength Push GetTop Pop StackTraverse （3）用伪码给出主程序的主要处理过程。#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW-2 typedef int Status;typedef char SElemType;Status visit(SElemType e);.#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef

8、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.stacksiz

9、e=0;return OK;Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;else return FALSE;Status StackJudgement(SqStack S)if(S.top=S.base)printf(是n);else printf(否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)*s

10、izeof(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;/StackLength Status 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)

11、;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);St

12、ackEmpty(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);pri

13、ntf(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(S

14、TACK_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;else return FALSE;Status StackJudgement(SqS

15、tack S)if(S.top=S.base)printf(是n);else printf(否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 O

16、K;.int StackLength(SqStack S)return S.top-S.base;/StackLength Status 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(S

17、qStack 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(

18、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);StackJud

19、gement(S);printf(11)释放栈。);DestroyStack(S);5.调试分析（1）调试过程中主要遇到哪些问题？是如何解决的？在调试过程中，输出从栈顶到栈底的元素时出现了问题，使得输出不是字母而是数字，后发现原因在输出的数据类型错误，从而输出数字，将输出数据类型改为%c 字符型后结果正确。（2）经验和体会 通过这次试验，我深切的理解了顺序栈的知识要点和表示与实现。并通过 C 语言实现了顺序队列的初始化，判空，删除，插入，等。进一步熟练了 C 语言操作环境。.6.测试结果 7.附件#include#include#include#define TRUE 1#define FAL

20、SE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW-2 typedef 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*)m

21、alloc(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;else return FALSE;Status StackJudgem

22、ent(SqStack S)if(S.top=S.base)printf(是n);else printf(否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;.

23、return OK;int StackLength(SqStack S)return S.top-S.base;/StackLength Status 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 StackTra

24、verse(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)判断顺序栈是

25、否为空: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);