数据结构栈和队列实验报告(共17页).doc

《数据结构栈和队列实验报告(共17页).doc》由会员分享，可在线阅读，更多相关《数据结构栈和队列实验报告(共17页).doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上南京信息工程大学 实验（实习）报告实验（实习）名称 栈和队列 日期 2017.11.8 得分 指导老师 崔萌萌 系 计算机系 专业 软件工程 年级 2016 班次 (1) 姓名 学号 一、实验目的1、学习栈的顺序存储和实现，会进行栈的基本操作2、掌握递归3、学习队列的顺序存储、链式存储，会进行队列的基本操作4、掌握循环队列的表示和基本操作二、实验内容1、用栈解决以下问题：（1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。2、用递归写出以下程序：（1）求n！。（2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写

2、出移动6个盘子的移动次数。3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include #include using namespace std;int main() stack s; /栈s; int n,radix; printf(请输入要转换的十进制非负整数： ); scanf(%d,&n); printf(请输入目标进制： ); scanf(%d,&radix); prin

3、tf(转换为%d进制： ,radix); while(n) s.push(n%radix); n /= radix; while(!s.empty() /非空 printf(%d,s.top(); s.pop(); printf(n); return 0;运行结果如下： 2.2 求表达式的值 代码如下： #include #include #include #include #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior88 = /运算符优先级表 / + - *

4、 / ( ) # /*+*/ , /*(*/ ,=, , , /*#*/ , ,=, ; typedef struct StackChar /StackChar类型的结点SC char c; struct StackChar *next; SC;typedef struct StackFloat /StackFloat类型的结点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;

5、return p; SF* 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, floa

6、t b) /计算函数Operate 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

7、 = true; return Find; Status ReturnOpOrd(char op,char *TestOp) for(int i=0; ic != #) if (!In(*c, OPSET) Dr0 = *c; strcat(TempData,Dr); /字符串连接函数 c+; if (In(*c, OPSET) Data = atof(TempData); /字符串转换函数(double) OPND = Push(OPND, Data); strcpy(TempData,0); else /不是运算符则进栈 switch (precede(OPTR-c, *c) case :

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(请输入表达式: n); scanf(%s,s); printf(该表达式的值为: n); printf(%s = ,s); printf(%gn,EvaluateExpression(s); / %g r

9、eturn 0; 运行结果如下： 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;运行结果如下：2.2 哈诺塔：代码如下： #include int Hanoi(int n,char a,char b,char c) if(1 = n) printf(%c-%d-%c ,a,1,c); else Hano

10、i(n-1,a,c,b); 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(请输入汉诺塔的层数: ); scanf(%d,&n); Hanoi(n,a,b,c); printf(n); return 0;运行结果如下：n=3时n=4时n=5时n=6时由3,4,5可推知n层哈诺塔需要移动 次；n=6时,需要移动63次。3. 队列的出队和入队代码如下： #include #include #include #define OK 1#define ERROR

11、0#define OVERFLOW -1typedef char ElemType; /default ElemType = char typedef int Status; /Return Value /*队列节点的申明*/typedef struct node ElemType data; struct node *next; QNode,*QuePtr; /*链式队列*/typedef struct QuePtr front; /队头指针 QuePtr rear; /队尾指针，指向队尾元素的下一位 LinkQueue; Status InitQueue(LinkQueue *q) /初始

12、化队列 q-front = q-rear = (QuePtr)malloc(sizeof(QNode); q-front-next = NULL; return OK; Status EnQueue(LinkQueue *q,ElemType e) /将元素e入队列 QuePtr temp = (QuePtr)malloc(sizeof(QNode); /创建新结点 if(!temp) return OVERFLOW; temp-data = e; /初始化新结点的数据为e temp-next = NULL; /队列只能从队尾插入所以下一个结点初始化为NULL q-rear-next = te

13、mp; q-rear = temp; /将指向队尾的指针指向新结点 return OK; Status CreateQueue(LinkQueue *q /*,char a*/) /创建队列 InitQueue(q); int k; printf(请输入队列元素个数：); scanf(%d,&k); printf(请输入队列元素: 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-fr

14、ont-next; /初始化temp为要出队的结点的指针 if(q-front-next = q-rear) q-rear = q-front; *e = temp-data; /将出队的数据元素存入*e q-front-next = temp-next; /下一个结点成为队头 free(temp); /删除要出队的结点 return OK； bool IsEmpty(LinkQueue *q) /判断队列是否为空 if(q-front = q-rear) return true; return false; int GetQueueLength(LinkQueue *q) /返回队列的长度

15、QuePtr temp = q-front; int i = 0; while(temp != q-rear) +i; temp = temp-next; return i; Status Print(LinkQueue *q) /打印队列的元素 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 ma

16、in() /char a = a,s,d,f,g,h,j,k,1; LinkQueue q; CreateQueue(&q); char top; int len = GetQueueLength(&q); char k; printf(将队列中的所有元素出队:n); for(int i = 0;i len;+i) DeQueue(&q,&k); printf(%c ,k); printf(n); return 0; 运行结果如下： 4. 循环队列代码如下： #include #include #include #define MAXQSIZE 7#define OK 1#define ERR

17、OR 0typedef char QElemType;typedef int Status; /Return Value/ 实现循环队列typedef struct QElemType *base; int rear; / 队尾指针 int front; / 队头指针 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 En

18、Queue(Queue *PtrQ, QElemType item) if( (PtrQ-rear+1)%MAXQSIZE = PtrQ-front ) printf(队列满.n); return ERROR; PtrQ-rear = (PtrQ-rear+1) % MAXQSIZE; PtrQ-basePtrQ-rear = item; / 删除队头元素并把队头元素返回QElemType DeQueue( Queue *PtrQ) if( PtrQ-front = PtrQ-rear ) printf(队列空.n); return -1; PtrQ-front = (PtrQ-front+1

19、) % MAXQSIZE; return PtrQ-basePtrQ-front; / 打印队列元素Status print(Queue *PtrQ) int i = PtrQ-front; if( PtrQ-front = PtrQ-rear ) printf(队列空.); return ERROR; printf(队列存在的元素如下: ); while( i != PtrQ-rear) printf(%c , PtrQ-basei+1); i+; i = i % MAXQSIZE; printf(n); return OK;int main() char a=ABCDEF; Queue Q

20、; InitQueue(&Q); printf(入队列：n); for(int i=0;istrlen(a);+i) EnQueue(&Q, ai); print(&Q); printf(出队列：n); while(Q.front!=Q.rear) DeQueue(&Q); print(&Q); return 0;运行结果如下：四、实验小结1. 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。2. 队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。允许删除的一端称为队头，允许插入的一端称为队尾，当队列中没有元素时称为空队列，队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾，每次离开的成员总是队列头上的。专心-专注-专业