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

數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告word文檔可自由復(fù)制編輯數(shù)據(jù)結(jié)構(gòu)與算法第二次實(shí)驗(yàn)報告電子105班趙萌2010021526數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第1頁。實(shí)驗(yàn)二：棧和隊(duì)列的定義及基本操作一、實(shí)驗(yàn)?zāi)康模?熟練掌握棧和隊(duì)列的特點(diǎn).掌握棧的定義和基本操作，熟練掌握順序棧的操作及應(yīng)用.掌握對列的定義和基本操作，熟練掌握鏈?zhǔn)疥?duì)列的操作及應(yīng)用,掌握環(huán)形隊(duì)列的入隊(duì)和出隊(duì)等基本操作.加深對棧結(jié)構(gòu)和隊(duì)列結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力二、實(shí)驗(yàn)內(nèi)容:定義順序棧，完成棧的基本操作：空棧、入棧、出棧、取棧頂元素;實(shí)現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換;定義鏈?zhǔn)疥?duì)列，完成隊(duì)列的基本操作：入隊(duì)和出隊(duì);1．問題描述：（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)換是計算機(jī)實(shí)現(xiàn)計算的基本問題，其解決方案很多，其中最簡單方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8NNdiv8Nmod8134816841682102125202從中我們可以看出，最先產(chǎn)生的余數(shù)4是轉(zhuǎn)換結(jié)果的最低位，這正好符合棧的特性即后進(jìn)先出的特性。所以可以用順序棧來模擬這個過程。以此來實(shí)現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換;.編寫主程序，實(shí)現(xiàn)對各不同的算法調(diào)用。（2）利用隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu),設(shè)計一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠?qū)︽準(zhǔn)疥?duì)列進(jìn)行如下操作：.初始化一個空隊(duì)列，形成一個帶表頭結(jié)點(diǎn)的空隊(duì);.完成一個元素的入隊(duì)操作，修改隊(duì)尾指針;.完成一個元素的出隊(duì)操作，修改隊(duì)頭指針;數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第2頁。其他算法的描述省略，參見實(shí)現(xiàn)要求說明。2．實(shí)現(xiàn)要求：對順序棧的各項(xiàng)操作一定要編寫成為C（C++）語言函數(shù)，組合成模塊化的形式，每個算法的實(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的棧頂元素，并返回OK;否則返回ERROR;.“入棧算法”操作結(jié)果：插入元素e為新的棧頂元素.“出棧算法”操作結(jié)果：若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERROR;.“實(shí)現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換算法”操作結(jié)果：輸入任意一個非負(fù)的十進(jìn)制數(shù)，輸出對應(yīng)的八進(jìn)制數(shù);對鏈?zhǔn)疥?duì)列的各項(xiàng)操作一定要編寫成為C（C++）語言函數(shù)，組合成模塊化的形式，每個算法的實(shí)現(xiàn)要從時間復(fù)雜度和空間復(fù)雜度上進(jìn)行評價。.“初始化空隊(duì)算法”操作結(jié)果：構(gòu)造一個空隊(duì)列Q;.“銷毀隊(duì)列算法”操作結(jié)果：銷毀隊(duì)列Q(無論空否均可);.“空隊(duì)列算法”操作結(jié)果：將Q清為空隊(duì)列;.“判隊(duì)列是否為空算法”操作結(jié)果：若Q為空隊(duì)列,則返回TRUE,否則返回FALSE;.“求隊(duì)列的長度算法”操作結(jié)果：求隊(duì)列的長度，返回隊(duì)列中結(jié)點(diǎn)的個數(shù);.“取隊(duì)頭元素算法”操作結(jié)果：若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR;.“入隊(duì)算法”操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素;.“出隊(duì)算法”操作結(jié)果：若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR;三、參考程序（一）順序棧1．文件SqStackDef.h中實(shí)現(xiàn)了棧的順序存儲表示#defineSTACK_INIT_SIZE10/*存儲空間初始分配量*/#defineSTACKINCREMENT2/*存儲空間分配增量*/typedefstructSqStack{數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第3頁。SElemType*top;/*棧頂指針*/intstacksize;/*當(dāng)前已分配的存儲空間，以元素為單位*/}SqStack;/*順序棧*/2．文件SqStackAlgo.h中實(shí)現(xiàn)順序棧的基本操作（存儲結(jié)構(gòu)由SqStackDef.h定義）StatusInitStack(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=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack&S){/*銷毀棧S，S不再存在*/free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;returnOK;}StatusClearStack(SqStack&S){/*把S置為空棧*/S.top=S.base;returnOK;}StatusStackEmpty(SqStackS){/*若棧S為空棧，則返回TRUE，否則返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第4頁。}數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第4頁。intStackLength(SqStackS){/*返回S的元素個數(shù)，即棧的長度*/returnS.top-S.base;}StatusGetTop(SqStackS,SElemType&e){/*若棧不空，則用e返回S的棧頂元素，并返回OK;否則返回ERROR*/if(S.top>S.base){e=*(S.top-1);returnOK;}elsereturnERROR;}StatusPush(SqStack&S,SElemTypee){/*插入元素e為新的棧頂元素*/if(S.top-S.base>=S.stacksize)/*棧滿，追加存儲空間*/{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));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)數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第5頁。return數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第5頁。e=*--S.top;returnOK;}StatusStackTraverse(SqStackS,Status(*visit)(SElemType)){/*從棧底到棧頂依次對棧中每個元素調(diào)用函數(shù)visit()。*//*一旦visit()失敗，則操作失敗*/while(S.top>S.base)visit(*S.base++);printf("\n");returnOK;}voidconversion10_8()/*算法3.1*/{/*對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)*/SqStacks;unsignedn;/*非負(fù)整數(shù)*/SElemTypee;InitStack(s);/*初始化棧*/printf("Enterannumber(>=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=n/8;}while(!StackEmpty(s))/*當(dāng)棧不空*/{Pop(s,e);/*彈出棧頂元素且賦值給e*/printf("%d",e);/*輸出e*/}printf("\n");}3．在SqStackUse.cpp文件中，測試算法3.1的調(diào)用，其中間接調(diào)用了順序棧的其他基本算法。typedefintSElemType;/*定義棧元素類型為整型*/數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第6頁。#include"SqStackDef.h"/*采用順序棧的類型定義*/#include"SqStackAlgo.h"/*利用順序棧的基本操作*/voidmain(){conversion10_8();/*十進(jìn)制數(shù)到八進(jìn)制轉(zhuǎn)換的驗(yàn)證*/}（二）鏈?zhǔn)疥?duì)列1．文件LinkQueueDef.h中實(shí)現(xiàn)單鏈隊(duì)列－－隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)的表示。typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront,rear;/*隊(duì)頭、隊(duì)尾指針*/}LinkQueue;2．文件LinkQueueAlgo.h中實(shí)現(xiàn)的鏈隊(duì)列的基本算法，其存儲結(jié)構(gòu)由LinkQueueDef.h定義。StatusInitQueue(LinkQueue&Q){/*構(gòu)造一個空隊(duì)列Q*/Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}StatusDestroyQueue(LinkQueue&Q){/*銷毀隊(duì)列Q(無論空否均可)*/while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第7頁。StatusClearQueue(LinkQueue&Q){/*將Q清為空隊(duì)列*/QueuePtrp,q;Q.rear=Q.front;p=Q.front->next;Q.front->next=NULL;while(p){q=p;p=p->next;free(q);}returnOK;}StatusQueueEmpty(LinkQueueQ){/*若Q為空隊(duì)列,則返回TRUE,否則返回FALSE*/if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}intQueueLength(LinkQueueQ){/*求隊(duì)列的長度*/inti=0;QueuePtrp;p=Q.front;while(Q.rear!=p){i++;p=p->next;}returni;}數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第8頁。{/*若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR*/QueuePtrp;if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;returnOK;}StatusEnQueue(LinkQueue&Q,QElemTypee){/*插入元素e為Q的新的隊(duì)尾元素*/QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)/*存儲分配失敗*/exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}StatusDeQueue(LinkQueue&Q,QElemType&e){/*若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR*/QueuePtrp;if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第9頁。{/*從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素調(diào)用函數(shù)vi()。一旦vi失敗,則操作失敗*/QueuePtrp;p=Q.front->next;while(p){vi(p->data);p=p->next;}printf("\n");returnOK;}3．文件LinkQueueUse.cpp中包含檢驗(yàn)LinkQueueAlgo.h中關(guān)于鏈?zhǔn)疥?duì)列基本操作的聲明、測試數(shù)據(jù)和主函數(shù)。#include"pubuse.h"/*與實(shí)驗(yàn)一的意義相同*/typedefintQElemType;/*假設(shè)鏈?zhǔn)疥?duì)列中的結(jié)點(diǎn)是一組整數(shù)*/#include"LinkQueueDef.h"#include"LinkQueueAlgo.h"voidvisit(QElemTypei){printf("%d",i);}voidmain(){inti;QElemTyped;LinkQueueq;i=InitQueue(q);if(i)printf("成功地構(gòu)造了一個空隊(duì)列!\n");printf("是否空隊(duì)列？%d(1:空0:否)",QueueEmpty(q));printf("隊(duì)列的長度為%d\n",QueueLength(q));EnQueue(q,-5);EnQueue(q,5);EnQueue(q,10);printf("插入3個元素(-5,5,10)后,隊(duì)列的長度為%d\n",QueueLength(q));printf("是否空隊(duì)列？%d(1:空0:否)",QueueEmpty(q));printf("隊(duì)列的元素依次為：");數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第10頁。數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)驗(yàn)報告全文共13頁，當(dāng)前為第10頁。i=GetHead_Q(q,d);if(i==OK)printf("隊(duì)頭元素是：%d\n",d);DeQueue(q,d);printf("刪除了隊(duì)頭元素%d\n",d);i=GetHead_Q(q,d);if(i==OK)printf("新的隊(duì)頭元素是：%d\n",d);ClearQueue(q);printf("清空隊(duì)列后,q.front=%uq.rear=%uq.front->next=%u\n",q.front,q.rear,q.front->next);DestroyQueue(q);printf("銷毀隊(duì)列后,q.front=%uq.rear=%u\n",q.front,q.rear);}思考題1．利用一個堆棧，將一個線性表中的元素按逆序重新存放。例如原來的順序?yàn)?2，8，6，4，2，要求改為2，4，6，8，12。[實(shí)驗(yàn)說明]設(shè)原始數(shù)據(jù)已存入數(shù)組a中，堆棧為stack，已清空，棧指針為top，初始top=0。首先從線性表第1個元素開始，依次將其元素壓入棧中，然后將棧中元素依次彈出，重新放入數(shù)組