本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列

試驗(yàn)二棧和隊(duì)列

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

1.把握棧的順序表示和實(shí)現(xiàn)2.把握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)二、試驗(yàn)內(nèi)容

1.編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2.實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。三、試驗(yàn)步驟

1.初始化順序棧2.插入元素3.刪除棧頂元素4.取棧頂元素5.遍歷順序棧6.置空順序棧7.初始化并建立鏈隊(duì)列8.入鏈隊(duì)列9.出鏈隊(duì)列10.遍歷鏈隊(duì)列四、實(shí)現(xiàn)提醒

1./*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedefstruct{

ElemTypestack[MAXNUM];inttop;}SqStack;

/*初始化順序棧函數(shù)*/voidInitStack(SqStack*p)

{q=(SqStack*)malloc(sizeof(SqStack)/*申請(qǐng)空間*/)/*入棧函數(shù)*/

voidPush(SqStack*p,ElemTypex)

{if(p->toptop=p->top+1;/*棧頂+1*/p->stack[p->top]=x;}/*數(shù)據(jù)入棧*/}

/*出棧函數(shù)*/

ElemTypePop(SqStack*p)

{x=p->stack[p->top];/*將棧頂元素賦給x*/p->top=p->top-1;}/*棧頂-1*//*獲取棧頂元素函數(shù)*/ElemTypeGetTop(SqStack*p){x=p->stack[p->top];}/*遍歷順序棧函數(shù)*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)

printf(\第%d個(gè)數(shù)據(jù)元素是：m\\n\/*置空順序棧函數(shù)*/voidsetEmpty(SqStack*p){p->top=-1;}2./*定義鏈隊(duì)列*/typedefstructQnode{ElemTypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;}Lqueue;

/*初始化并建立鏈隊(duì)列函數(shù)*/voidcreat(Lqueue*q)

{h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請(qǐng)空間*/h->next=NULL;q->front=h;q->rear=h;

for(i=1;idata=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出鏈隊(duì)列函數(shù)*/

ElemTypeLdelete(Lqueue*q){p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;

free(p);}/*釋放空間*//*遍歷鏈隊(duì)列函數(shù)*/voiddisplay(Lqueue*q)

{while(p!=NULL)/*利用條件判斷是否到隊(duì)尾*/{printf(\p=p->next;}}

五、思考與提高

1.讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？

2.假使一個(gè)程序中要用到兩個(gè)棧，為了不發(fā)生上溢錯(cuò)誤，就必需給每個(gè)棧預(yù)先分派一個(gè)足夠大的存儲(chǔ)空間。若每個(gè)棧都預(yù)分派過大的存儲(chǔ)空間，勢必會(huì)造成系統(tǒng)空間緊張。如何解決這個(gè)問題？

（1）鏈棧只有一個(gè)top指針，對(duì)于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針？

（2）一個(gè)程序中假使要用到兩個(gè)棧時(shí)，可通過兩個(gè)棧共享一維數(shù)組來實(shí)現(xiàn)。即雙向棧共享鄰接空間。假使一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？

六、完整參考程序1.棧的順序表示和實(shí)現(xiàn)

#include#include#include

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2

typedefintStatus;typedefintSElemType;

//棧的順序存儲(chǔ)表示#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10

typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;

StatusInitStack(SqStackStatusDestroyStack(SqStackStatusStackDisplay(SqStackStatusGetTop(SqStackS,SElemTypeStatusPush(SqStackStatusPop(SqStackStatusStackEmpty(SqStackS);

StatusInitStack(SqStackif(!S.base)exit(OVERFLOW);//存儲(chǔ)分派失效S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;

}//InitStack

StatusDestroyStack(SqStackS.top=S.base=NULL;returnOK;

}//InitStack

StatusStackDisplay(SqStack

inti=0;

if(S.base==S.top){printf(\堆棧已空!\\n\returnOK;}

while(p#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2

//Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;

//ElemType是順序表數(shù)據(jù)元素類型,此程序定義為int型typedefintQElemType;

//單鏈隊(duì)列--隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedefstructQNode{//定義結(jié)點(diǎn)結(jié)構(gòu)

QElemTypedata;//數(shù)據(jù)域structQNode*next;//指針域

}QNode,*QueuePtr;

typedefstructlinkqueue{//定義隊(duì)列結(jié)構(gòu)

QueuePtrfront;//隊(duì)頭指針QueuePtrrear;//隊(duì)尾指針

}LinkQueue;

StatusInitLinkQueue(LinkQueue//初始化一個(gè)隊(duì)列StatusDestroyLinkQueue(LinkQueue//銷毀一個(gè)隊(duì)列intLinkQueueLength(LinkQueue//隊(duì)列的長度StatusEnLinkQueue(LinkQueue//將一個(gè)元素入隊(duì)列StatusDeLinkQueue(LinkQueue//將一個(gè)元素出隊(duì)列StatusDisplayLinkQueue(LinkQueue);//顯示隊(duì)列中所有元素

voidmain(){

LinkQueueLQ;QElemTypee;intflag=1,ch,len;Statustemp;

printf(\本程序?qū)崿F(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列的操作。\\n\printf(\可以進(jìn)行入隊(duì)列、出隊(duì)列等操作。\\n\InitLinkQueue(LQ);//初始化隊(duì)列while(flag){

printf(\請(qǐng)選擇:\\n\

printf(\顯示隊(duì)列所有元素\\n\printf(\入隊(duì)列\(zhòng)\n\printf(\出隊(duì)列\(zhòng)\n\printf(\求隊(duì)列的長度\\n\printf(\退出程序\\n\scanf(\switch(ch){

}}

case1:DisplayLinkQueue(LQ);//顯示隊(duì)列中所有元素

break;

case2:printf(\請(qǐng)輸入要人隊(duì)的元素(一個(gè)整數(shù)):\

scanf(\//輸入要入隊(duì)列的字符EnLinkQueue(LQ,e);//入隊(duì)列DisplayLinkQueue(LQ);break;

case3:temp=DeLinkQueue(LQ,e);//出隊(duì)列

if(temp==OK){}

elseprintf(\隊(duì)列為空!\\n\break;

printf(\出隊(duì)一個(gè)元素:%d\\n\DisplayLinkQueue(LQ);

case4:len=LinkQueueLength(LQ);

printf(\隊(duì)列的長度為:%d\\n\break;

default:flag=0;}

printf(\程序運(yùn)行終止，按任意鍵退出!\\n\getch();

StatusInitLinkQueue(LinkQueue//生成一個(gè)頭結(jié)點(diǎn)，并

把首尾指針指向頭結(jié)點(diǎn)

}

Q.front->next=NULL;returnOK;

StatusDestroyLinkQueue(LinkQueue

p=(QueuePtr)malloc(sizeof(QNode));//生成一個(gè)新結(jié)點(diǎn)p->data=e;//賦值p->next=NULL;

Q.rear->next=p;//插入至隊(duì)列尾Q.rear=p;//修改隊(duì)尾指針returnOK;inti=0;

QueuePtrp=Q.front;while(p!=Q.rear){}returni;

++i;p=p->next;QueuePtrp;QElemTypee;while(Q.front!=Q.rear)

DeLinkQueue(Q,e);

free(Q.front);Q.front=Q.rear=NULL;returnOK;

StatusDeLinkQueue(LinkQueue

if(Q.front==Q.rear)returnERROR;//判斷隊(duì)列是否已空，已空返回

p=Q.front->next;//p指向隊(duì)列中第一個(gè)元素e=p->data;//取得該元素值Q.front->next=p->next;//修改隊(duì)首指針

if(Q