數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告三-1-

實(shí)驗(yàn)報(bào)告書

課程名稱：《數(shù)據(jù)結(jié)構(gòu)》

實(shí)驗(yàn)題目：實(shí)驗(yàn)三

棧

一、實(shí)驗(yàn)?zāi)康?/p>

（1）掌握棧與隊(duì)列的數(shù)據(jù)類型描述及特點(diǎn)；

（2）掌握棧的順序和鏈?zhǔn)酱鎯?chǔ)存表示與基本算法的實(shí)現(xiàn)；

（3）按照實(shí)驗(yàn)題目要求，獨(dú)立完成實(shí)際程序的編寫編寫、調(diào)試和運(yùn)行，并通過用例的運(yùn)行過程抓獲

相關(guān)屏面驗(yàn)證程序設(shè)計(jì)的正確性。

二'實(shí)驗(yàn)內(nèi)容

（1）實(shí)現(xiàn)順序棧的創(chuàng)建（初始化）、壓入（插入）、彈出（刪除）操作（數(shù)據(jù)元素類型自己選取，

如整型、字符型等，或者參照書上算法選取數(shù)據(jù)類型），并給出棧的每次操作變化狀態(tài)；

（2）實(shí)現(xiàn)鏈棧的創(chuàng)建（初始化）、壓入（插入）、彈出（刪除）操作（數(shù)據(jù)元素類型自己選取，如

整型、字符型等，或者參照書上算法選取數(shù)據(jù)類型），要求給出棧的操作變化過程。

三'實(shí)驗(yàn)步驟

#include<stdio.h>

#include<stdlib.h>

#defineTRUE1

#defineFALSE0

SdefineStackSize50

typedefintStackElcmcntType;〃棧的順序存儲(chǔ)結(jié)構(gòu)定義

typedefstruct

StackElementTypeelem[StackSize];〃用來存放棧中元素的一堆數(shù)組

inttop;〃用來存放棧頂元素的下標(biāo)

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告三_________________________-2」

JSqStack;

voidInitStack(SqStack*s);

intIsEmpty(SqStack*s);

intIsFull(SqStack*s);

intPush(SqStack*s,StackElementTypee);

intPop(SqStack*s,StackElementType*e);

intGetTop(SqStack*s,StackElementType*e);

intGetStack(SqStack*s);

intmain()

(

SqStacks;

StackElementTypee;

StackElementTypex;

intflag=l;

while(flag!=0)

(

printf(〃二二二二順序棧的操作=二=\n〃)；

printf(〃①初始化棧\n");

printf(〃②元素進(jìn)棧\n〃)；

printf(，z③元素出棧\n〃)；

printf(〃④顯示棧元素\n〃)；

printf(〃⑤結(jié)束程序\n〃)；

printf(〃請(qǐng)輸入需要進(jìn)行的操作：\n〃)；

scanf&flag);

switch(flag)

(

case1:InitStack(&s);break;

case2:printf("元素進(jìn)棧,請(qǐng)輸入1個(gè)數(shù)據(jù)：\n〃)；

scanf&e);

Push(&s,e);

printf(〃進(jìn)棧成功！\n〃);break;

case3:printf("開始出棧！\n〃)；

Pop(&s,&x);

printf("出棧成功！\n〃);break;

case4:GetStack(&s);break;

case5:return0;

default:printf("輸入步驟錯(cuò)誤！\n〃);

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告三-3-

)

return0;

)

voidInitStack(SqStack*s)

(

s->top=-l;

printf("棧創(chuàng)建成功\n");

)

intIsEmpty(SqStack*s)〃判棧s為空時(shí)返回值為真,反之為假

(

return(s->top==-1?TRUE:FALSE);

)

intIsFull(SqStack*s)〃判棧滿

(

return(s->top==StackSize-1?TRUE:FALSE);

)

intPush(SqStack*s,StackElementTypee)〃進(jìn)棧

(

if(s->top==StackSizeT)

(

return(FALSE);〃棧已滿

}

s->top++;

s->elem[s->top]=e;

return(TRUE);

)

intPop(SqStack*s,StackElementType*e)〃將棧s的棧頂元素彈出,放到e所指的存儲(chǔ)空間中

(

if(s->top==-1)

(

return(FALSE);

}

else

(

*e=s->elem[s->top];

s->top—;〃修改棧頂指針

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告三____________________-4」

return(TRUE);

}

)

intGetTop(SqStack*s,StackElementType*e)〃將棧s的棧頂元素彈出,放到e所指的存儲(chǔ)空間

中，但棧頂指針保持不變

(

if(s->top==T)〃棧為空

(

return(FALSE);

)

else

(

*e=s->elem[s->top];

return(TRUE);

}

)

intGetStack(SqStack*s)〃將當(dāng)前棧內(nèi)元素顯示出來

(

inti;

i=s->top;

printf(〃當(dāng)前棧內(nèi)元素：\n〃)；

for(;i>-l;i--)

(

printfs->elem[i]);

)

printf(〃\n〃);

return(TRUE);

)

鏈棧的操作和順序棧十分相似，首先給出鏈棧的結(jié)構(gòu)定義

ttinclude<stdio.h>

#include<stdlib.h>

?defineTRUE1

#defineFALSE0

typedefintStackElementType;//鏈棧的結(jié)構(gòu)定義

typedefstructnode

(

StackElementTypedata;

structnode*next;

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告三-5.

}LinkStackNode;

typedefLinkStackNode*LinkStack;

voidInitStackNode(LinkStacktop);

intIsEmpty(LinkStacktop);

intPush(LinkStacktop,StackElementTypex);

intPop(LinkStacktop,StackElementType*x);

intGetStack(LinkStackNode*p);

intmain()

(

LinkStacks;

intcount;

s=(LinkStack)malloc(sizeof(LinkStackNode));

intflag=l;

while(flag!=O)

(

printf(〃二二二二鏈棧的操作二二二=\n〃);

printfC①初始化棧\n〃)；

printf(，z②元素進(jìn)棧\n〃)；

printf(z，③元素出棧\n〃)；

printf(〃④顯示棧元素\n〃)；

printf(，z⑤結(jié)束程序\n〃)；

printf(〃請(qǐng)輸入需要進(jìn)行的操作：\n〃)；

scanf&flag);

switch(flag)

(

case1:printf(〃初始化鏈棧！\n");

InitStackNode(s);

printf("初始化成功！\n〃);break;

case2:

inti;

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

(

Push(s,i);

)

printf(〃進(jìn)棧成功！\n");break;

case3:printf(〃開始出棧！\n");

Pop(s,&count);

printf("出棧成功！\n");break;

case4:GetStack(s);break;

case5:return0;

default:printf(〃輸入步驟錯(cuò)誤！\n〃);

)

)

return0;

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告/-6.

voidInitStackNode(LinkStacktop)〃建立一個(gè)空鏈棧

(

top->next=NULL;

)

intIsEmpty(LinkStacktop)

(

if(top->next==NULL)

return(TRUE);

return(FALSE);

)

intPush(LinkStacktop,StackElementTypex)〃將數(shù)據(jù)元素x壓入棧top中

(

LinkStackNode*temp;

temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));

if(temp二二NULL)

(

return(FALSE)"/申請(qǐng)空間失敗

)

temp->data=x;

temp->next=top->next;

top->next=temp;〃修改當(dāng)前棧頂指針

return(TRUE);

)

intPop(LinkStacktop,StackElementType*x)〃將棧top的棧頂元素彈出，放到x所指的存儲(chǔ)空

間中

{

LinkStackNode*temp;

temp=top->next;

if(temp二二NULL)〃棧為空

(

r