《數(shù)據(jù)結構》實驗指導及報告書

2022/2022學年第_二學期

姓名:

學號：

班級：

指導教師：

計算機科學與工程學院

2022

實驗二棧和隊列

一、實驗目的

1、掌握棧的結構特性及其入棧，出棧操作；

2、掌握隊列的結構特性及其入隊、出隊的操作，掌握循環(huán)隊列的特點及其操作。

二、實驗內(nèi)容和要求

1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補充完整。要求輸入元素序列12345e,運

行結果如下所示。

#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

#defineSTACK.INT_SIZE10/*存儲空間初始分配量*/

#defineSTACKINCREMENT5/*存儲空間分配增量*/

typedefintElemType;/*定義兀素的類型*/

typedefstruct(

ElemType*base;

ElemType*top;

intstacksize;/*當前已分配的存儲空間*/

}SqStack;

intInitStack(SqStack*S);/*構造空棧*/

intpush(SqStack*S,ElemType*e);/*入蔻*/

intPop(SqStack*S,ElemType*e);/*出棧*/

intCreateStack(SqStack*S);/*創(chuàng)建棧*/

voidPrintStack(SqStack*S);/*出棧并軸出棧中兀素*/

intInitStack(SqStack*S){

S->base=(ElemType*)malloc(STACK.INT_SIZE*sizeof(ElemType));

if(!S->base)returnERROR;

S->top=S->base;

S->stacksize=STACK_INT_SIZE;

returnOK;

}/*InitStack*/

intPush(SqStack*S,ElemTypee){

}/*Push*/

intPop(SqStack*S,ElemType*e){

}/*Pop*/

intCreateStack(SqStack*S){

inte;

if(InitStack(S))

else{

returnERROR;

)

Push(S,e);

returnOK;

}/*CreateStack*/

voidPrintStack(SqStack*S){

ElemTypee;

while(Pop(S,&e))

}/*Pop_and_Print*/

intmain(){

SqStackss;

CreateStack(&ss);

PrintStack(&ss);

return0;

)

.算法分析：輸入元素序列12345,為什么輸出序列為54321?體現(xiàn)了棧的什么

特性？

#include<stdio.h>

#include<malloc.h>

#defineERROR0

ttdefineOK1

^defineSTACKJNT_SIZE10/*存儲空間初始分配量*/

^defineSTACKINCREMENT5/*存儲空間分配增量*/

typedefintElemType;/*定義元素的類型*/

typedefstruct(

ElemType*base;

ElemType*top;

intstacksize;/*當前已分配的存儲空間*/

}SqStack;

intInitStack(SqStack*S);/*構造空棧*/

intPush(SqStack*S,ElemType*e);/*入棧*/

intPop(SqStack*S,ElemType*e);/*出棧*/

intCreateStack(SqStack*S);/*創(chuàng)建棧*/

voidPrintStack(SqStack*S);/*出棧并輸出棧中元素*/

int1nitStack(SqStack*S){

S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));

if(!S->base)returnERROR;

S->top=S->base;

S->stacksize=STACK_INT_SIZE;

returnOK;

}/*InitStack*/

intPush(SqStack*S,ElemTypee){

if(S->top-S->base>=S->stacksize)

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

mType));

if(!S->base)returnERROR;

S->top=S->base+S->stacksize;

S->stacksize+二STACKINCREMENT;

}

*S->top++=e;

returnOK;

}/*Push*/

intPop(SqStack*S,ElemType*e){

if(S->top=S->base)returnERROR;

e=-S->top;

returnOK;

}/*Pop*/

intCreateStack(SqStack*S){

inte;

if(InitStack(S))

else{

returnERROR;

Push(S,e);

returnOK;

}/*CreateStack*/

voidPrintStack(SqStack*S){

ElemTypee;

while(Pop(S,&e))

}/*Pop_and_Print*/

intmain(){

SqStackss;

CreateStack(&ss);

Pop(&ss,&e);

PrintStack(&ss);

return0;

)

2、在第1題的程序中，編寫一個十進制轉換為二進制的數(shù)制轉換算法函數(shù)（要求利用棧來

實現(xiàn)），并驗證其正確性。

實現(xiàn)代碼

■

#include<stdio.h>

#include<malloc.h>

^defineERROR0

^defineOK1

^defineSTACKINITSIZE10/*存W?儲加0空？間？初？始°?分Q?配？量C?*/

^defineSTACKINCREMENT5/*存&?儲&i6空？間？分Q?配？增？量C?*/

typedefintSElcmType;/*定i§義°?元打素？的t?類Cf-CS型"a*/

typedefstruct

(

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;

intInitStack(SqStack&S);

intCreateStack(SqStack*S);

intGetTop(SqStackS,SElemType&e);

intPush(SqStack&S,SElemTypee);

intPop(SqStack&S,SElemType&e);

voidconversion();

voidmain()

(

inte;

SqStackS;

CreateStack(S);

GetTop(S,e);

Push(S,e);

conversion();

)

intInitStack(SqStack&S)

(

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

if(!S.base)returnERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

)

intCreateStack(SqStack&S)

(

inte;

if(InitStack(S))

printf();

else{

printf();

returnERROR;

)

printf(）；

while(scanf(,&e))

Push(S,e);

returnOK;

)

intGetTop(SqStackS,SElemType&e)

(

if(S.top==S.base)returnERROR;

e=*(S.top-1);

returnOK;

)

intPush(SqStack&S,SElemTypee)

(

if(S.top-S.base>=S.stacksize)

{

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)returnERROR;

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

S.stacksize+二STACKINCREMENT;

)

)

intPop(SqStack&S,SElemType&e)

(

if(S.top==S.base)returnERROR;

e=*-S.top;

returnOK;

)

voidconversion()

(

intn,e;

SqStackS;

printf();

scanf(,n);

while(n)

{

Push(S,n);

n=n/2;

)

Pop(S,e);

printf(,e);

3、閱讀并運行程序，并分析程序功能。

#include<stdio.h>

#include<malloc.h>

#include<string.h>

#defineM20

#defineelemtypechar

typedefstruct

{

elemtypestack[M];

inttop;

}

stacknode;

voidinit(stacknode*st);

voidpush(stacknode*st,elemtypex);

voidpop(stacknode*st);

voidinit(stacknode*st)

{

st->top=0;

)

voidpush(stacknode*st,elemtypex)

{

if(st->top==M)

else

(

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

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

}

}

voidpop(stacknode*st)

{

st->top=