《数据结构》实验二 栈和队列

《数据结构》实验指导及报告书

2014 / 2015 学年 第 1学期

姓 名： 学 号： 班 级： 指导教师：徐江

计算机科学与工程学院

2014

实验二 栈和队列

一、实验目的

1、掌握栈的结构特性及其入栈，出栈操作；

2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

二、实验内容和要求

1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。

#include #include #define ERROR 0 #define OK 1

#define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top;

int stacksize; /*当前已分配的存储空间*/ }SqStack;

int InitStack(SqStack *S); /*构造空栈*/ int push(SqStack *S,ElemType *e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/

void PrintStack(SqStack *S); /*出栈并输出栈中元素*/

int InitStack(SqStack *S){

S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR;

S->top=S->base;

S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/

int Push(SqStack *S,ElemType e){

}/*Push*/

int Pop(SqStack *S,ElemType *e){

}/*Pop*/

int CreateStack(SqStack *S){ int e;

if(InitStack(S))

printf(\ else{

printf(\ return ERROR; }

printf(\ while(scanf(\ Push(S,e); return OK; }/*CreateStack*/

void PrintStack(SqStack *S){ ElemType e;

while(Pop(S,&e)) printf(\}/*Pop_and_Print*/

int main(){ SqStack ss;

printf(\ CreateStack(&ss);

printf(\ PrintStack(&ss); return 0; }

算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？

#include

?

#include #define ERROR 0 #define OK 1

#define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top;

int stacksize; /*当前已分配的存储空间*/ }SqStack;

int InitStack(SqStack *S); /*构造空栈*/ int Push(SqStack *S,ElemType *e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/

void PrintStack(SqStack *S); /*出栈并输出栈中元素*/

int InitStack(SqStack *S){

S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base;

S->stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/

int Push(SqStack *S,ElemType e){ if(S->top-S->base>=S->stacksize) {

S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S->base) return ERROR; S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; }

*S->top++=e; return OK; }/*Push*/

int Pop(SqStack *S,ElemType *e){ if(S->top=S->base)return ERROR; e= --S->top; return OK;

}/*Pop*/

int CreateStack(SqStack *S){ int e;

if(InitStack(S))

printf(\ else{

printf(\ return ERROR; }

printf(\ while(scanf(\ Push(S,e); return OK; }/*CreateStack*/

void PrintStack(SqStack *S){ ElemType e;

while(Pop(S,&e)) printf(\}/*Pop_and_Print*/

int main(){ SqStack ss;

printf(\ CreateStack(&ss);

printf(\ Pop(&ss, &e); PrintStack(&ss); return 0; }

2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。 ? 实现代码

#include #include #define ERROR 0

本文来源：https://www.bwwdw.com/article/tig8.html