數(shù)據(jù)結(jié)構(gòu)棧和隊列

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

試驗二棧和隊列

一、試驗?zāi)康?/p>

1.把握棧的順序表示和實現(xiàn)2.把握隊列的鏈式表示和實現(xiàn)二、試驗內(nèi)容

1.編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運算。2.實現(xiàn)隊列的鏈式表示和實現(xiàn)。三、試驗步驟

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

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

ElemTypestack[MAXNUM];inttop;}SqStack;

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

{q=(SqStack*)malloc(sizeof(SqStack)/*申請空間*/)/*入棧函數(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個數(shù)據(jù)元素是：m\\n\/*置空順序棧函數(shù)*/voidsetEmpty(SqStack*p){p->top=-1;}2./*定義鏈隊列*/typedefstructQnode{ElemTypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;}Lqueue;

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

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

for(i=1;idata=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出鏈隊列函數(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);}/*釋放空間*//*遍歷鏈隊列函數(shù)*/voiddisplay(Lqueue*q)

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

五、思考與提高

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

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

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

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

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

#include#include#include

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

typedefintStatus;typedefintSElemType;

//棧的順序存儲表示#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);//存儲分派失效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;

//單鏈隊列--隊列的鏈式存儲結(jié)構(gòu)typedefstructQNode{//定義結(jié)點結(jié)構(gòu)

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

}QNode,*QueuePtr;

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

QueuePtrfront;//隊頭指針QueuePtrrear;//隊尾指針

}LinkQueue;

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

voidmain(){

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

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

printf(\請選擇:\\n\

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

}}

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

break;

case2:printf(\請輸入要人隊的元素(一個整數(shù)):\

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

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

if(temp==OK){}

elseprintf(\隊列為空!\\n\break;

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

case4:len=LinkQueueLength(LQ);

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

default:flag=0;}

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

StatusInitLinkQueue(LinkQueue//生成一個頭結(jié)點，并

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

}

Q.front->next=NULL;returnOK;

StatusDestroyLinkQueue(LinkQueue

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

Q.rear->next=p;//插入至隊列尾Q.rear=p;//修改隊尾指針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;//判斷隊列是否已空，已空返回

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

if(Q