數(shù)據(jù)結(jié)構(gòu)與算法的實驗報告

數(shù)據(jù)結(jié)構(gòu)與算法第二次實驗報告電子105班趙萌2010021526實驗二：棧和隊列的定義及基本操作一、 實驗?zāi)康模?熟練掌握棧和隊列的特點.掌握棧的定義和基本操作，熟練掌握順序棧的操作及應(yīng)用.掌握對列的定義和基本操作，熟練掌握鏈?zhǔn)疥犃械牟僮骷皯?yīng)用，掌握環(huán)形隊列的入隊和出隊等基本操作.加深對棧結(jié)構(gòu)和隊列結(jié)構(gòu)的理解，逐步培養(yǎng)解決實際問題的編程能力二、 實驗內(nèi)容：定義順序棧，完成棧的基本操作：空棧、入棧、出棧、取棧頂元素；實現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換；定義鏈?zhǔn)疥犃?，完成隊列的基本操作：入隊和出隊；問題描述：（1） 利用棧的順序存儲結(jié)構(gòu)，設(shè)計一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠?qū)樞驐＿M(jìn)行如下操作：.初始化一個空棧，分配一段連續(xù)的存儲空間，且設(shè)定好棧頂和棧底；.完成一個元素的入棧操作，修改棧頂指針；.完成一個元素的出棧操作，修改棧頂指針；.讀取棧頂指針?biāo)赶虻脑氐闹担?將十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方案很多，其中最簡單方法基于下列原理：即除d取余法。例如：（1348）io=（2504）sNNdiv8Nmod8134816841682102125202從中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個過程。以此來實現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換；.編寫主程序，實現(xiàn)對各不同的算法調(diào)用。（2） 利用隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，設(shè)計一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠?qū)︽準(zhǔn)疥犃羞M(jìn)行如下操作：.初始化一個空隊列，形成一個帶表頭結(jié)點的空隊；.完成一個元素的入隊操作，修改隊尾指針；.完成一個元素的出隊操作，修改隊頭指針；.修改主程序，實現(xiàn)對各不同的算法調(diào)用。其他算法的描述省略，參見實現(xiàn)要求說明。實現(xiàn)要求：對順序棧的各項操作一定要編寫成為C(C++)語言函數(shù)，組合成模塊化的形式,每個算法的實現(xiàn)要從時間復(fù)雜度和空間復(fù)雜度上進(jìn)行評價。.“初始化棧算法”操作結(jié)果：構(gòu)造一個空棧S;.“銷毀棧算法”操作結(jié)果：銷毀棧s,S不再存在；.“置空棧算法”操作結(jié)果：把S置為空棧；.“判是否空棧算法”操作結(jié)果：若棧S為空棧，則返回TRUE，否則返回FALSE;.“求棧的長度算法”操作結(jié)果：返回S的元素個數(shù)，即棧的長度；.“取棧頂元素算法”操作結(jié)果：若棧不空，則用e返回S的棧頂元素，并返回0K;否則返回ERROR;.“入棧算法”操作結(jié)果：插入元素e為新的棧頂元素.“出棧算法”操作結(jié)果：若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERROR;.“實現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換算法”操作結(jié)果：輸入任意一個非負(fù)的十進(jìn)制數(shù)，輸出對應(yīng)的八進(jìn)制數(shù)；對鏈?zhǔn)疥犃械母黜棽僮饕欢ㄒ帉懗蔀镃(C++)語言函數(shù)，組合成模塊化的形式，每個算法的實現(xiàn)要從時間復(fù)雜度和空間復(fù)雜度上進(jìn)行評價。.“初始化空隊算法”操作結(jié)果：構(gòu)造一個空隊列Q；.“銷毀隊列算法”操作結(jié)果：銷毀隊列Q(無論空否均可)；.“空隊列算法”操作結(jié)果：將Q清為空隊列；.“判隊列是否為空算法”操作結(jié)果：若Q為空隊列，則返回TRUE,否則返回FALSE;.“求隊列的長度算法”操作結(jié)果：求隊列的長度，返回隊列中結(jié)點的個數(shù)；.“取隊頭元素算法”操作結(jié)果：若隊列不空，則用e返回Q的隊頭元素,并返回0K,否則返回ERROR;.“入隊算法”操作結(jié)果：插入元素e為Q的新的隊尾元素；.“出隊算法”操作結(jié)果：若隊列不空，刪除Q的隊頭元素，用e返回其值,并返回0K,否則返回ERROR;三、參考程序(一)順序棧文件SqStackDef.il中實現(xiàn)了棧的順序存儲表示#defineSTACK_INIT_SIZE10/*存儲空間初始分配量*/#defineSTACKINCREMENT2/*存儲空間分配增量*/typedefstmctSqStackSElemType*base;/*在棧構(gòu)造之前和銷毀之后，base的值為NULL*/SElemType*top;/*棧頂指針*/mtstacksize;/*當(dāng)前己分配的存儲空間，以元素為單位*/}SqStack;/*順序棧*/文件SqStackAlgo.h中實現(xiàn)順序棧的基本操作(存儲結(jié)構(gòu)由SqStackDef.h定義)StatusLutStack(SqStack&S)(/*構(gòu)造一個空棧S*/S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);/*存儲分配失敗*/S.top=S.base;S.stacksize=STACKINITSIZE;retuniOK;)StatusDestroyStack(SqStack&S){/*銷毀棧s,s不再存在*/fiee(S.base);S.base=NULL;S.top=NULL;S.stacksize=O;retuniOK;)StatusCleaiStack(SqStack&S){/*把s置為空棧*/S.top=S.base;retuniOK;)StatusStackEmpty(SqStackS){/*若棧S為空棧，則返回TRUE,否則返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;mtStackLength(SqStackS){/*返回s的元素個數(shù)，即棧的長度*/returnS.top-S.base;)StatusGetTop(SqStackS,SEleniType&e){/*若棧不空，則用e返回S的棧頂元素，并返回OK;否則返回ERROR*/if(S.top>S.base){e=*(S.top-l);returnOK;)elsereturnERROR;)StatusPush(SqStack&S,SElemTypee){/*插入元素e為新的棧頂元素*/if(S.top-S.base>=S.stacksize)/*棧滿，追加存儲空間*/{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEleniType));if(!S.base)exit(OVERFLOW);/*存儲分配失敗*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;)*(S.top)++=e;returnOK;)StatusPop(SqStack&S,SElemType&e){/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERROR*/if(S.top==S.base)returnERROR;e=*-S.top;retuniOK;}StatusStackTraverse(SqStackS,Status(*visit)(SElemType))(/*從棧底到棧頂依次對棧中每個元素調(diào)用函數(shù)VlSltOo*//*一旦visit。失敗，則操作失敗*/wlule(S.top>S.base)visit(*S.base++);prmtR”")；retuniOK;}voidconversion10_8()/*算法3.1*/(/*對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)*/SqStacks;unsignedn;/*非負(fù)整數(shù)*/SElemTypee;ImtStack(s);/*初始化棧*/pnntf("Entei-annumbei(>=0):");scanf("%u",&n);/*輸入非負(fù)十進(jìn)制整數(shù)n*/while(n)/*當(dāng)n不等于0*/{Push(s,n%8);/*入棧n除以8的余數(shù)(8進(jìn)制的低位)*/n=ii/8;}while(!StackEmpty(s))/*當(dāng)棧不空*/{Pop(s,e);/*彈出棧頂元素且賦值給e*/printf(”％d”,e);/*輸出e*/}pnntfC^i");}在SqStackUse.cpp文件中，測試算法3.1的調(diào)用，其中間接調(diào)用了順序棧的其他基本算法。typedefmtSElemType;/*定義棧元素類型為整型*/#include"pubuse.li"/*常量定義與系統(tǒng)函數(shù)原型聲明，與實驗一中的相同*/include“SqStackDef.h”/*采用順序棧的類型定義*/#include"SqStackAlgo.h"/*利用順序棧的基本操作*/voidmam()(conversionl0_8();/*十進(jìn)制數(shù)到八進(jìn)制轉(zhuǎn)換的驗證*/}(二)鏈?zhǔn)疥犃形募﨤iiikQueueDef.h中實現(xiàn)單鏈隊列 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)的表示。typedefstnictQNode{QElemTypedata;stnictQNode*next;)QNode,*QueuePti；typedefstnict{QueuePtrfront,real；/*隊頭、隊尾指針*/}LnikQueue;文件LnikQueueAlgo.il中實現(xiàn)的鏈隊列的基本算法，其存儲結(jié)構(gòu)由LiiikQueueDef.h定義。StatusLutQueue(LuikQueue&Q)(/*構(gòu)造一個空隊列Q*/Q.fiont=Q.iear=(QueuePti)malloc(sizeof(QNode));exit(OVERFLOW);Q.fiont->next=NULL;returnOK;)StatusDestroyQueue(LinkQueue&Q)(/*銷毀隊列Q(無論空否均可)*/wlule(Q.front){Q.ieai=Q.fiont->next;fiee(Q.fiont);Q.front=Q.rear;)returnOK;)StatusClearQueue(LnikQueue&Q){/*將Q清為空隊列*/QueuePtip,q;Q.ieai-Q.fiont;p=Q.fiont->next;Q.fiont->next=NULL;while(p)(q=p;p=p->next;free(q);)retuniOK;)StatusQueueEmpty(LuikQueueQ){/*若Q為空隊列，則返回TRUE,否則返回FALSE*/if(Q.fiont==Q.rear)returnTRUE;elsereturnFALSE;)mtQueueLength(LiiikQueueQ)(/*求隊列的長度*/mt1=0;QueuePtip;p=Q.fiont;wlule(Q.iear!=p){i+十；p=p->next;)retunii;)StatusGetHead_Q(LmkQueueQ.QElemType&e)(/*若隊列不空，則用e返回Q的隊頭元素，并返回OK,否則返回ERROR*/QueuePtip;if(Q.fiont==Q.rear)returnERROR;p=Q.fiont->next;e=p?>data;retuniOK;)StatusEnQueue(LnikQueue&Q,QElemTypee)(/*插入元素e為Q的新的隊尾元素*/QueuePtip=(QueuePtr)malloc(sizeof(QNode));if(!p)/*存儲分配失敗*/exit(OVERFLOW);p->data=e;p->next=NULL;Q.iear->next=p;Q.ieai-p;retuniOK;)StatusDeQueue(LnikQueue&Q,QElemType&e)(/*若隊列不空，刪除Q的隊頭元素，用e返回其值,并返回O虬否則返回ERROR*/QueuePtip;if(Q.fiont==Q.rear)returnERROR;p=Q.fiont->next;e=p?>data;Q.fiont->next=p->next;if(Q.ieai-=p)Q.ieai-Q.fiont;free(p);retuniOK;)StatusQueueTiaveise(LmkQueueQ,void(*vi)(QElemType))(/*從隊頭到隊尾依次對隊列Q中每個元素調(diào)用函數(shù)vi()o-旦vi失敗，則操作失敗*/QueuePtip;p=Q.fiont->next;while(p)(vi(p->data);p=p->next;)prmtR”\n”)；retuniOK;)文件LnikQueueUse.cpp中包含檢驗LnikQueueAlgo.h中關(guān)于鏈?zhǔn)疥犃谢静僮鞯穆暶鳌y試數(shù)據(jù)和主函數(shù)。#include"pubuse.li"/*與實驗一的意義相同*/typedefmtQElemType;/*假設(shè)鏈?zhǔn)疥犃兄械慕Y(jié)點是一組整數(shù)*/#include"LuikQueueDef.h"#include"LiiikQueueAlgo.h"voidvisit(QElemTypei)(pnntf(H%d”,i);}voidmam(){mti;QElemTyped;LnikQueueq;i=hiitQueue(q);】f(Dpnntf(”成功地構(gòu)造了一個空隊列!")；pnntfC'是否空隊列?%d(l:空0:否)M,QueueEmpty(q));pnntf("隊列的長度為%d\n",QueueLength(q));EnQueue(q,-5);EnQueue(q,5);EnQueue(qJO);pnntf(”插入3個元素(-5,5,10)后,隊列的長度為%d\iiM,QueueLengtli(q));printfC*是否空隊列?%d(l:空0:否)M,QueueEmpty(q));pnntf("隊列的元素依次為：，QueueTiaveise(q,visit);i=GetHead_Q(q,d);if(i==OK)pnntf(”隊頭元素是：％d",d);DeQueue(q,d);printfC*刪除了隊頭元素%d\n”,d)；i=GetHead_Q(q,d);if(i==OK)pnntf(”新的隊頭元素是：％d\n”,d);CleaiQueue(q);pnntf("清空隊列后,q.front=%uq.ieai=%uq.fiont->next=%u\ii",q.fiont,q.ieai-,q.fiont->next);DestioyQueue(q);pnntf("銷毀隊列后,q.front=%uq.iear=%u\ii",q.fiont,q.reai);)四、思考題利用一個堆棧，將一個線性表中的元素按逆序重新存放。例如原來