1、南京信息工程大學(xué) 實(shí)驗(yàn)（實(shí)習(xí)）報(bào)告實(shí)驗(yàn)（實(shí)習(xí)）名稱 棧和隊(duì)列 日期 2017.11.8 得分 指導(dǎo)老師 崔萌萌 系 計(jì)算機(jī)系 專業(yè) 軟件工程 年級(jí) 2016 班次 (1) 姓名 學(xué)號(hào) 一、實(shí)驗(yàn)?zāi)康?、學(xué)習(xí)棧的順序存儲(chǔ)和實(shí)現(xiàn)，會(huì)進(jìn)行棧的基本操作2、掌握遞歸3、學(xué)習(xí)隊(duì)列的順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)，會(huì)進(jìn)行隊(duì)列的基本操作4、掌握循環(huán)隊(duì)列的表示和基本操作二、實(shí)驗(yàn)內(nèi)容1、用棧解決以下問題：（1）對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)，顯示輸出與其等值的八進(jìn)制數(shù)，寫出程序。（2）表達(dá)式求值，寫出程序。2、用遞歸寫出以下程序：（1）求n！。（2）漢諾塔程序，并截圖顯示3、4、5個(gè)盤子的移動(dòng)步驟,寫出移動(dòng)6個(gè)盤子的移動(dòng)次數(shù)。

2、3、編程實(shí)現(xiàn)：（1）創(chuàng)建隊(duì)列，將asdfghjkl依次入隊(duì)。（2）將隊(duì)列asdfghjkl依次出隊(duì)。4、編程實(shí)現(xiàn)創(chuàng)建一個(gè)最多6個(gè)元素的循環(huán)隊(duì)列、將ABCDEF依次入隊(duì)，判斷循環(huán)隊(duì)列是否隊(duì)滿。三、實(shí)驗(yàn)步驟 1.棧的使用 1.1 用棧實(shí)現(xiàn)進(jìn)制的轉(zhuǎn)換： 代碼如下： #include #include using namespace std;int main() stack s; /棧s; int n,radix; printf(請(qǐng)輸入要轉(zhuǎn)換的十進(jìn)制非負(fù)整數(shù)： ); scanf(%d,&n); printf(請(qǐng)輸入目標(biāo)進(jìn)制： ); scanf(%d,&radix); printf(轉(zhuǎn)換為%d進(jìn)制： ,

3、radix); while(n) s.push(n%radix); n /= radix; while(!s.empty() /非空 printf(%d,s.top(); s.pop(); printf(n); return 0;運(yùn)行結(jié)果如下： 2.2 求表達(dá)式的值 代碼如下： #include #include #include #include #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = /運(yùn)算符優(yōu)先級(jí)表 / + - * / ( ) # /*+*

4、/ , /*(*/ ,=, , , /*#*/ , ,=, ; typedef struct StackChar /StackChar類型的結(jié)點(diǎn)SC char c; struct StackChar *next; SC;typedef struct StackFloat /StackFloat類型的結(jié)點(diǎn)SF float f; struct StackFloat *next; SF; SC* Push(SC* s,char c) /SC類型的指針Push，返回p SC* p = (SC* )malloc(sizeof(SC); p-c = c; p-next = s; return p; SF*

5、 Push(SF* s,float f) /SF類型的指針Push，返回p SF* p = (SF* )malloc(sizeof(SF); p-f = f; p-next = s; return p; SC* Pop(SC* s) /SC類型的指針Pop SC* q = s; s = s-next; free(q); return s; SF* Pop(SF* s) /SF類型的指針Pop SF* q = s; s = s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /計(jì)算函數(shù)Ope

6、rate switch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; case : return pow(a,b); default : return 0; char OPSETOPSETSIZE = +,-,*,/,(,),#,; Status In(char Test,char *TestOp) int Find = false; for (int i=0; i OPSETSIZE; i+) if(Test = TestOpi) Find = true; retu

7、rn Find; Status ReturnOpOrd(char op,char *TestOp) for(int i=0; ic != #) if (!In(*c, OPSET) Dr0 = *c; strcat(TempData,Dr); /字符串連接函數(shù) c+; if (In(*c, OPSET) Data = atof(TempData); /字符串轉(zhuǎn)換函數(shù)(double) OPND = Push(OPND, Data); strcpy(TempData,0); else /不是運(yùn)算符則進(jìn)棧 switch (precede(OPTR-c, *c) case : /退棧并將運(yùn)算結(jié)果入棧

8、theta = OPTR-c; OPTR = Pop(OPTR); b = OPND-f; OPND = Pop(OPND); a = OPND-f; OPND = Pop(OPND); OPND = Push(OPND, Operate(a, theta, b); break; return OPND-f; int main() char s128; printf(請(qǐng)輸入表達(dá)式: n); scanf(%s,s); printf(該表達(dá)式的值為: n); printf(%s = ,s); printf(%gn,EvaluateExpression(s); / %g return 0; 運(yùn)行結(jié)果

9、如下： 2.遞歸的使用 2.1 求n！： 代碼如下： #include int Fact(int n) if(0 = n) return 1; else return n*Fact(n-1);int main() int n; scanf(%d,&n); printf(%d的階乘為：,n); printf(%d,Fact(n); return 0;運(yùn)行結(jié)果如下：2.2 哈諾塔：代碼如下： #include int Hanoi(int n,char a,char b,char c) if(1 = n) printf(%c-%d-%c ,a,1,c); else Hanoi(n-1,a,c,b);

10、 printf(%c-%d-%c ,a,n,c); Hanoi(n-1,b,a,c); return 0;int main() int n; char a=A,b=B,c=C; printf(請(qǐng)輸入漢諾塔的層數(shù): ); scanf(%d,&n); Hanoi(n,a,b,c); printf(n); return 0;運(yùn)行結(jié)果如下：n=3時(shí)n=4時(shí)n=5時(shí)n=6時(shí)由3,4,5可推知n層哈諾塔需要移動(dòng) 次；n=6時(shí),需要移動(dòng)63次。3. 隊(duì)列的出隊(duì)和入隊(duì)代碼如下： #include #include #include #define OK 1#define ERROR 0#define OVER

11、FLOW -1typedef char ElemType; /default ElemType = char typedef int Status; /Return Value /*隊(duì)列節(jié)點(diǎn)的申明*/typedef struct node ElemType data; struct node *next; QNode,*QuePtr; /*鏈?zhǔn)疥?duì)列*/typedef struct QuePtr front; /隊(duì)頭指針 QuePtr rear; /隊(duì)尾指針，指向隊(duì)尾元素的下一位 LinkQueue; Status InitQueue(LinkQueue *q) /初始化隊(duì)列 q-front =

12、 q-rear = (QuePtr)malloc(sizeof(QNode); q-front-next = NULL; return OK; Status EnQueue(LinkQueue *q,ElemType e) /將元素e入隊(duì)列 QuePtr temp = (QuePtr)malloc(sizeof(QNode); /創(chuàng)建新結(jié)點(diǎn) if(!temp) return OVERFLOW; temp-data = e; /初始化新結(jié)點(diǎn)的數(shù)據(jù)為e temp-next = NULL; /隊(duì)列只能從隊(duì)尾插入所以下一個(gè)結(jié)點(diǎn)初始化為NULL q-rear-next = temp; q-rear =

13、temp; /將指向隊(duì)尾的指針指向新結(jié)點(diǎn) return OK; Status CreateQueue(LinkQueue *q /*,char a*/) /創(chuàng)建隊(duì)列 InitQueue(q); int k; printf(請(qǐng)輸入隊(duì)列元素個(gè)數(shù)：); scanf(%d,&k); printf(請(qǐng)輸入隊(duì)列元素: n); for(int i=0;ik;+i) char a; getchar(); scanf(%c,&a); EnQueue(q,a); / for(int i=0;ifront = q-rear) return ERROR; QuePtr temp = q-front-next; /初始

14、化temp為要出隊(duì)的結(jié)點(diǎn)的指針 if(q-front-next = q-rear) q-rear = q-front; *e = temp-data; /將出隊(duì)的數(shù)據(jù)元素存入*e q-front-next = temp-next; /下一個(gè)結(jié)點(diǎn)成為隊(duì)頭 free(temp); /刪除要出隊(duì)的結(jié)點(diǎn) return OK； bool IsEmpty(LinkQueue *q) /判斷隊(duì)列是否為空 if(q-front = q-rear) return true; return false; int GetQueueLength(LinkQueue *q) /返回隊(duì)列的長(zhǎng)度 QuePtr temp =

15、 q-front; int i = 0; while(temp != q-rear) +i; temp = temp-next; return i; Status Print(LinkQueue *q) /打印隊(duì)列的元素 if(q-front = q-rear) return ERROR; QuePtr temp = q-front-next; while(temp != q-rear) printf(%c ,temp-data); temp = temp-next; printf(%c,temp-data); printf(n); return OK; int main() /char a

16、= a,s,d,f,g,h,j,k,1; LinkQueue q; CreateQueue(&q); char top; int len = GetQueueLength(&q); char k; printf(將隊(duì)列中的所有元素出隊(duì):n); for(int i = 0;i len;+i) DeQueue(&q,&k); printf(%c ,k); printf(n); return 0; 運(yùn)行結(jié)果如下： 4. 循環(huán)隊(duì)列代碼如下： #include #include #include #define MAXQSIZE 7#define OK 1#define ERROR 0typedef c

17、har QElemType;typedef int Status; /Return Value/ 實(shí)現(xiàn)循環(huán)隊(duì)列typedef struct QElemType *base; int rear; / 隊(duì)尾指針 int front; / 隊(duì)頭指針 Queue;Status InitQueue(Queue *Q) Q-base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType); if(Q-base = NULL) return ERROR; Q-front = Q-rear = 0; return OK;Status EnQueue(Queue *

18、PtrQ, QElemType item) if( (PtrQ-rear+1)%MAXQSIZE = PtrQ-front ) printf(隊(duì)列滿.n); return ERROR; PtrQ-rear = (PtrQ-rear+1) % MAXQSIZE; PtrQ-basePtrQ-rear = item; / 刪除隊(duì)頭元素并把隊(duì)頭元素返回QElemType DeQueue( Queue *PtrQ) if( PtrQ-front = PtrQ-rear ) printf(隊(duì)列空.n); return -1; PtrQ-front = (PtrQ-front+1) % MAXQSIZE; return PtrQ-basePtrQ-front; / 打印隊(duì)列元素Status print(Queue *PtrQ) int i = PtrQ-front; if( PtrQ-front = PtrQ-rear ) printf(隊(duì)列空.); re