实验二--栈、队列的实现及应用.doc

上传人:sk****8 文档编号:2214369 上传时间:2019-05-02 格式:DOC 页数:16 大小:194KB
下载 相关 举报
实验二--栈、队列的实现及应用.doc_第1页
第1页 / 共16页
实验二--栈、队列的实现及应用.doc_第2页
第2页 / 共16页
实验二--栈、队列的实现及应用.doc_第3页
第3页 / 共16页
实验二--栈、队列的实现及应用.doc_第4页
第4页 / 共16页
实验二--栈、队列的实现及应用.doc_第5页
第5页 / 共16页
点击查看更多>>
资源描述

1、实验二 栈、队列的实现及应用实验课程名:数据结构与算法专业班级: 学号: 姓名: 实验时间: 实验地点: 指导教师: 冯珊 一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用。2、掌握栈和队列的特点,即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验内容一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用。2、掌握栈和队列的特点,即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时2学时三、实验任务任务一:(1)实现栈的顺序存储(2)实现栈的链式存储。任务二:实现顺序存储的循环队列

2、,完成键盘缓冲区的功能。四、实验重点、难点1. 进栈、出栈栈顶指针都要改变。2. 队空、队满的条件及入队、出队时指针的变更。五、操作内容与要求1.任务一(1):完成下列程序,该程序实现栈的顺序存储结构,构建顺序栈(栈中的元素依次为R,S,Y,F,C,T),依次进行进栈和出栈操作,判断栈空和栈满操作,返回栈顶元素操作。要求生成顺序栈时,从键盘上读取数据元素。(1)源代码:#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define OK 1# define ERROR 0typedef char SEle

3、mType;/* 顺序栈的存储类型 */typedef struct /define structure SqStack()SElemType *base;SElemType *top;int stacksize;SqStack;/*构造空顺序栈*/int InitStack(SqStack *S) /InitStack() sub-functionS-base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if (!S-base)printf(“分配空间失败!n“);return (ERROR);S-top = S-base;

4、S-stacksize = STACK_INIT_SIZE;printf(“栈初始化成功!n“);return (OK); /InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack *S, SElemType *e) /GetTop() sub-functionif (S-top = S-base)printf(“栈为空!n“); /if empty SqStackreturn (ERROR);*e = *(S-top - 1);return (OK); /GetTop() end/*将元素压入顺序栈*/int Push(SqStack *S) /Push()

5、 sub-functionSElemType e;if (S-top - S-baseS-stacksize)S-base = (SElemType *)realloc(S-base, (S-stacksize +STACKINCREMENT*sizeof(SElemType);if (!S-base)printf(“存储空间分配失败!n“);return (ERROR);S-top = S-base + S-stacksize;S-stacksize += STACKINCREMENT;fflush(stdin);/清除输入缓冲区,否则原来的输入会默认送给变量 xprintf(“请输入要入栈

6、的元素的值:“);e = getchar();*S-top+ = e;return (OK); /Push() end/* 将元素弹出顺序栈*/int Pop(SqStack *S, SElemType *e) /Pop() sub-functionif (S-top = S-base)printf(“栈为空!n“);return (ERROR);*e = *-S-top;return (OK); /Pop() endvoid display(SqStack *s)if (s-top = s-base)printf(“栈为空!n“);elsewhile (s-top != s-base)s-t

7、op = s-top - 1;printf(“%c-“, *(s-top);printf(“n“);int main()int choice;SElemType e;SqStack s;doprintf(“=n“);printf(“ 0:退出n“);printf(“ 1:初始化栈n“);printf(“ 2:入栈n“);printf(“ 3:出栈n“);printf(“ 4:读取栈顶元素n“);printf(“ 5:显示栈中元素n“);printf(“=n“);printf(“输入操作选择代码(0-5):“);scanf(“%d“, while (choice5) printf(“输入有误,请

8、重新输入(0-5):“); scanf(“%d“, switch (choice)case 0:exit(1);case 1:InitStack( break;case 2:printf(“2n“); Push( break;case 3:Pop( printf(“出栈元素的值是:%cn“, e); break;case 4:GetTop( printf(“栈顶元素的值是:%cn“, e); break;case 5: printf(“栈中元素的值是为:n“); display( break; while (choice);return 0;(2)运行结果(3)结果分析顺序表通过设置栈顶运用线

9、性结构实现先进先出功能。2.任务一(2):完成下列程序,该程序实现栈的链式存储结构,构建链栈(栈中的元素依次为China,Japan,France,India,Australia),依次进行进栈和出栈操作,判断栈空和栈满操作,返回栈顶元素操作。要求生成链栈时,从键盘上读取数据元素。(1)源代码:#include#include#include# define OK 1# define ERROR 0typedef char DataType;/* 链式栈的存储类型 */typedef struct SNode /define structure LinkStack DataType data2

10、0;struct SNode *next;SNode,*LinkStack;void InitStack_L (LinkStack *top)top = (LinkStack)malloc(sizeof(SNode) ; top-next = NULL;printf(“nn栈初始化成功!nn“);/*取链式栈顶元素*/int GetTop_L(LinkStack *top,DataType e) /GetTop_L() sub-function if(!top-next) printf(“链栈为空!n“);return (ERROR);else strcpy(e,top-next-data);

11、return (OK); /GetTop_L() end/* 将元素压入链式栈*/int Push_L(LinkStack *top) /Push_L() sub-function SNode *q;DataType e20;q=(LinkStack)malloc(sizeof(SNode);if(!q) printf(“存储空间分配失败! n“);return (ERROR);fflush(stdin);/清除输入缓冲区,否则原来的输入会默认送给变量eprintf(“n请输入要入栈的元素的值:“);gets(e);strcpy(q-data,e);q-next=top-next;top-ne

12、xt=q;return (OK); /Push_L() end/*将元素弹出链式栈*/int Pop_L(LinkStack *top,DataType e) /Pop_L() sub-function SNode *q;if(!top-next) printf(“链栈为空! n “);return (ERROR);strcpy(e,top-next-data);q=top-next;top-next=q-next;free(q);return (OK); /Pop_L() endvoid display(LinkStack *top)LinkStack p=top-next;if(!p)pr

13、intf(“栈为空!n“);elsewhile(p) printf(“%s-“,p-data);p=p-next;printf(“n“); int main()char choice;DataType e20=“;LinkStack s=NULL;doprintf(“=n“);printf(“ 0:退出n“);printf(“ 1:初始化栈n“);printf(“ 2:入栈n“);printf(“ 3:出栈n“);printf(“ 4:读取栈顶元素n“);printf(“ 5:显示栈中元素n“);printf(“=n“);printf(“输入操作选择代码(0-5):“);fflush(stdin);scanf(“%c“,while(choice5) printf(“输入有误,请重新输入(0-5):“);fflush(stdin);scanf(“%c“,switch(choice)case 0:exit(1);case 1: InitStack_L(break;case 2: Push_L(break;case 3:Pop_L(break;case 4:GetTop_L(printf(“栈顶元素的值是:%sn“,e);break;case 5: printf(“栈中元素的值是: “);display(while(choice);return 0;(2)运行结果

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课程笔记

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。