2022年《数据结构（本）》形考任务实践活动3

2022年国家开放大学数据结构(本)形考任务实践活动3

实验3栈、队列、递归设计

数据结构课程实验报告

学生姓名学号

班级指导老师

实验名称栈、队列、递归程序设计实验成绩

实!险报告

实验目的：

编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。

实

验实验要求：

概(1)正确理解栈的先进后出的操作特点，建立.初始栈，通过相关操作显示栈底元素。

述(2)程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作

规则打印结果栈中的元素。

实验基本原理；

(1)采用顺序栈，即用数组存储核元素。

(2)设定一个临时队列，用来存放从初始栈中出栈的元素。

(3)取出栈底元素后，将队列中的元素逐一出队并压入初始栈中。

实验设计思路、步骤和方法等：

(1)根据栈的先进后出特点，来进行实验

实(2)建立顺序栈、临时队列、依次取出压入栈

验实验过程(实验中涉及的记录、数据、分析)：

内4include<stdio.h>

容^include<stdlib.h>

4defineMaxSize100

typedefintElemType;

typedefstruct

(

ElemTypedata[MaxSize];

inttop;

}SeqStack;

typedefstruct

(

ElemTypedata[MaxSize];

intfront,rear;

)SeqQueue;

voidInitStack(SeqStack*s);

intStackEmpty(SeqStack*s);

intStackFul1(SeqStack*s);

voidPush(SeqStack*s,ElemTypex);

1

ElemTypePop(SeqStack*s);

ElemTypeGetTop(SeqStack*s)：

voidDispStack(SeqStack*s);

voidDispBottom(SeqStack*s);

voidInilQueue(SeqQueue*sq);

intQueueEmpty(SeqQueue*sq);

voidInQueue(SeqQueue*sq,ElemTypex);

ElemTypeOutQueue(SeqQueue*sq,ElemTypex);

ElemTypeGetQueue(SeqQueue*sq)

voidmain()

(

SeqStack*s;

SeqQueue*sq;

ElemTypex;

intn,i;

初始化栈s\n〃)；

s=(SeqStack*)ma1loc(sizeof(SeqStack));

InitStack(s);

printf("(2)栈为%s\n”,(StackEmpty(s)?"空非空〃));

printf("(3)输入要进栈的数据个数：”)；

scanf(飞d”,&n)：

printf("依次输入进栈的%d个整数：〃,n);

for(i=0;i<n;i++)

(

scanf(飞d”,&x);

Push(s,x);

)

printf(*(4)栈为%s\n",(SiackEmply(s)?"空":"非空"));

printf("(5)从栈顶到栈底的元素依次为:"):DispStack(s):

printf("(6)栈底元素为：");DispBottom(s);

printf(*(7)初始化队列sq\n");

sq=(SeqQueue*)ma1loc(sizeof(SeqQueue));

InitQucue(sq);

printf(*(8)队列为%s\n”,(QueueEmpty(sq)?"空":"非空"));

prinlf("(9)出栈/入队的元素依次为:“)；

while(!StackEmpty(s))

(

x=Pop(s);

printf(*%d",x);

InQueue(sq,x);

)

2

printfC\n*);

printf(*(10)栈为%s,”,(StackEmpty(s)?"空"："非空"))；

printf("队列为%s\n",(QueueEmpty(sq)?"空"："非空"));

printfCdl)出队/进栈的元素依次为:");

while(!QueueEmpty(sq))

(

x=OutQueue(sq,x);

printf(*%d",x);

Push(s,x);

)

prinlf('\n");

printf("(12)栈为%s,〃，(StackEmpty(s)?"空"<非空"));

printf("队列为%s\n”,(QueueEmpty(sq)?"空":"非空"));

printf("(13)从栈顶到栈底的元素依次为:“)；DispStack(s);

printf("(14)栈底元素为;DispBottom(s);

free(s);

free(sq):

)

voidInitStack(SeqStack*s)

(

s->top=-l;

)

intStackEmpty(SeqStack*s)

(

if(s->top==-l)

return1;

else

return0;/*否则返回0*/

)

intStackFull(SeqStack*s)

(

if(s->top==MaxSize-1)

return1;

else

return0;

)

3

voidPush(SeqStack*s,ElemTypex)

(

if(StackEul1(s))

(

prinlf("栈满溢出错误!\n0；

exit(l);

)

s->top++;

s->data[s->top]=x;

)

ElemTypePop(SeqStack*s)

(

if(StackEmpty(s))

(

printfC栈下溢错误!\n")；

exit(1);

)

s->top—;

returns->dataLs->top+l];

)

ElemTypeGetTop(SeqStack*s)

(

if(StackEmpty(s))

(

printf-栈下溢错误!\n〃)：

exit(1);

)

returns->data[s->top];

)

voidDispStack(SeqStack*s)

(

inti;

for(i=s->top;i>=0;i—)

printf(*%ds->data[i]);

printfC\n*)；

)

4

voidDispBottom(SeqStack*s)

(

printf'C^d”,s~>data[0]);

printf('\n");

)

voidInitQueue(SeqQueue*sq)

(

sq->front=sq->rear=0;

)

intQueueEmpty(SeqQueue*sq)

(

if(sq->rear=sq->front)

return1;

else

return0;

)

voidInQueue(SeqQueue*sq,ElemTypex)

(

if((sq->rear+1)%MaxSize==sq->front)

(

printf("循环队列已满!\n");

exit(1);

}

sq->data[sq->rear]=x;

sq->rear=(sq->rear+l)%MaxSize;

)

ElemTypeOutQueue(SeqQueue*sq,ElemTypex)

(

if(QueueEmpty(sq))/*队空*/

(

prinlf(〃循环队列己空，不能进行出队操作！\<)：

exit(1);

}

else1

x=sq->data[sq->front];

sq->front=(sq->fronl+1)%MaxSize;

5

returnx;

)

)

ElemTypeGetQueue(SeqQueue*sq)

(

ir(QueueEmpty(sq))

(

printf("队列已空，不能进行出队操作！\n");

exit(l);

)

returnsq->data[sq->front]：

)

实验结果：

(1)初始化栈

(2)栈为空

(3)输入要进栈的数据个数为5,依次输入进栈的5个整数：12345

(4)栈为非空

(5)从栈顶到栈底的元素依次为：54321

(6)栈底元素为：1

(7)初始化队列为：1

(8)队列为空

(9)出栈/入队的元素依次为：54321

(10)栈为空，队列为空

(11)出队/进栈的元素依次为：54321

(12)栈为非空，队列为空