2022年《數(shù)據(jù)結(jié)構(gòu)（本）》形考任務(wù)實踐活動3

2022年國家開放大學數(shù)據(jù)結(jié)構(gòu)(本)形考任務(wù)實踐活動3

實驗3棧、隊列、遞歸設(shè)計

數(shù)據(jù)結(jié)構(gòu)課程實驗報告

學生姓名學號

班級指導(dǎo)老師

實驗名稱棧、隊列、遞歸程序設(shè)計實驗成績

實!險報告

實驗?zāi)康模?/p>

編寫一個算法，輸出指定棧中的棧底元素，并使得原棧中的元素倒置。

實

驗實驗要求：

概(1)正確理解棧的先進后出的操作特點，建立.初始棧，通過相關(guān)操作顯示棧底元素。

述(2)程序中要體現(xiàn)出建棧過程和取出棧底元素后恢復(fù)棧的入棧過程，按堆棧的操作

規(guī)則打印結(jié)果棧中的元素。

實驗基本原理；

(1)采用順序棧，即用數(shù)組存儲核元素。

(2)設(shè)定一個臨時隊列，用來存放從初始棧中出棧的元素。

(3)取出棧底元素后，將隊列中的元素逐一出隊并壓入初始棧中。

實驗設(shè)計思路、步驟和方法等：

(1)根據(jù)棧的先進后出特點，來進行實驗

實(2)建立順序棧、臨時隊列、依次取出壓入棧

驗實驗過程(實驗中涉及的記錄、數(shù)據(jù)、分析)：

內(nèi)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)輸入要進棧的數(shù)據(jù)個數(shù)：”)；

scanf(飛d”,&n)：

printf("依次輸入進棧的%d個整數(shù)：〃,n);

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

(

scanf(飛d”,&x);

Push(s,x);

)

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

printf("(5)從棧頂?shù)綏５椎脑匾来螢?"):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)從棧頂?shù)綏５椎脑匾来螢?“)；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("循環(huán)隊列已滿!\n");

exit(1);

}

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

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

)

ElemTypeOutQueue(SeqQueue*sq,ElemTypex)

(

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

(

prinlf(〃循環(huán)隊列己空，不能進行出隊操作！\<)：

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]：

)

實驗結(jié)果：

(1)初始化棧

(2)棧為空

(3)輸入要進棧的數(shù)據(jù)個數(shù)為5,依次輸入進棧的5個整數(shù)：12345

(4)棧為非空

(5)從棧頂?shù)綏５椎脑匾来螢椋?4321

(6)棧底元素為：1

(7)初始化隊列為：1

(8)隊列為空

(9)出棧/入隊的元素依次為：54321

(10)棧為空，隊列為空

(11)出隊/進棧的元素依次為：54321

(12)棧為非空，隊列為空