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

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

    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("Init Success!\\n");

    else{

        printf("Init Fail!\\n");

        return ERROR;

    }

    printf("input data:(Terminated by inputing a character)\\n");

    while(scanf("%d",&e))

        Push(S,e);

    return OK;

}/*CreateStack*/

void PrintStack(SqStack *S){

    ElemType e;

    while(Pop(S,&e))

        printf("%3d",e);

}/*Pop_and_Print*/

int main(){

    SqStack ss;

    printf("\\n1-createStack\\n");

    CreateStack(&ss);

    printf("\\n2-Pop&Print\\n");

    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("Init Success!\\n");

    else{

        printf("Init Fail!\\n");

        return ERROR;

    }

    printf("input data:(Terminated by inputing a character)\\n");

    while(scanf("%d",&e))

        Push(S,e);

    return OK;

}/*CreateStack*/

void PrintStack(SqStack *S){

    ElemType e;

    while(Pop(S,&e))

        printf("%3d",e);

}/*Pop_and_Print*/

int main(){

    SqStack ss;

    printf("\\n1-createStack\\n");

    CreateStack(&ss);

    printf("\\n2-Pop&Print\\n");

    Pop(&ss, &e);

    PrintStack(&ss);

    return 0;

}

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

●实现代码

#include

#include

#define ERROR 0

#define OK 1

#define STACK_INIT_SIZE 10  /*存ä?储ä¡é空?间?初?始º?分¤?配?量¢?*/

#define STACKINCREMENT 5  /*存ä?储ä¡é空?间?分¤?配?增?量¢?*/

typedef  int SElemType; /*定¡§义°?元a素?的Ì?类¤¨¤型¨ª*/

typedef struct

{

    SElemType *base;

    SElemType *top;

    int stacksize;

}SqStack;

int InitStack(SqStack &S);

int CreateStack(SqStack *S);

int GetTop(SqStack S,SElemType &e);

int Push(SqStack &S,SElemType e);

int Pop(SqStack &S,SElemType &e);

void conversion();

void main()

{   

    int e;

    SqStack S;

    CreateStack(S);

    GetTop( S, e);

    Push( S, e);

    conversion();

}

int InitStack(SqStack &S)

{

    S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));

    if(!S.base)return ERROR;

    S.top=S.base;

    S.stacksize=STACK_INIT_SIZE;

}

int CreateStack(SqStack &S)

{

    int e;

    if(InitStack(S))

        printf("Init Success!\\n");

    else{

        printf("Init Fail!\\n");

        return ERROR;

    }

    printf("input data:(Terminated by inputing a character)\\n");

    while(scanf("%d",&e))

        Push(S,e);

    return OK;

}

int GetTop(SqStack S,SElemType &e)

{

    if(S.top==S.base) return ERROR;

    e=*(S.top-1);

    return OK;

}

int 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)return ERROR;

        S.top=S.base+S.stacksize;

        S.stacksize+=STACKINCREMENT;

    }

}

 int Pop(SqStack &S,SElemType &e)

{

   if(S.top==S.base)return ERROR;

   e= *--S.top;

   return OK;

 }

void conversion()

{

    int n,e;

    SqStack S;

    printf("input data:\\n");

    scanf("%d",n);

    while(n)

    {

        Push(S,n);

        n=n/2;

    }

        Pop(S,e);

        printf("%d",e);

}

3、阅读并运行程序，并分析程序功能。

#include

#include

#include

#define M 20

#define  elemtype  char

typedef struct

{

    elemtype stack[M];

    int top;

}

stacknode;

void init(stacknode *st);

void push(stacknode *st,elemtype x);

void pop(stacknode *st);

void init(stacknode *st)

{

st->top=0;

}

void push(stacknode *st,elemtype x)

{

if(st->top==M)

        printf("the stack is overflow!\\n");

    else

    {

st->top=st->top+1;

st->stack[st->top]=x;

    }

}

void pop(stacknode *st)

{

st->top=st->top-1;

}

int main()

{

    char s[M];

    int i;

    printf("create a empty stack!\\n");

    stacknode *sp;

    sp=malloc(sizeof(stacknode));

    init(sp);

    printf("input a expression:\\n");

    gets(s);

for(i=0;i    {

        if(s[i]=='(')

            push(sp,s[i]);

        if(s[i]==')')

            pop(sp);

    }

if(sp->top==0)

        printf("'('match')'!\\n");

    else

        printf("'('not match')'!\\n");

    return 0;

}

●输入：2+((c-d)*6-(f-7)*a)/6

●运行结果：

●输入：a-((c-d)*6-(s/3-x)/2

●运行结果：

●程序的基本功能：

以下为选做实验：

4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。

●实现代码

5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。

实现代码：

三、实验小结

四、教师评语