实验二 堆栈和队列基本操作的编程实现

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY

数据结构 实 验 报 告

实验项目 学生姓名 完成日期 指导教师 实验成绩 评阅教师

实验类别 学生学号 基础篇 评阅日期

实验二 堆栈和队列基本操作的编程实现

【实验目的】

堆栈和队列基本操作的编程实现 要求：

堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

验证性实验（学时数：2H）

【实验内容】

内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【注意事项】

1.开发语言：使用C。

2.可以自己增加其他功能。

【实验分析、说明过程】

栈的顺序存储是利用 一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，每当插入新的栈顶元素时，指针top增一，删除栈顶元素时，指针top减一。

【思考问题】

1、栈的顺序存储和链表存储的差异？ 栈的顺序存储实现在于使用了数组，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用光而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用； 栈的链式存储使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间开始，另外当某个项不使用时也可将内存返还给系统。 2、还会有数据移动吗？为什么？ 3、栈的主要特点是什么？队列呢？ 栈的主要特点：先进后出，只能在表的一端进行插入和删除操作； 队列的主要特点：先进先出，只能在表的一端进行插入和在另一端进行删除操作。 4、栈的主要功能是什么？队列呢？ 栈和队列的作用是排队作用，可以应用在排队类型的数据处理上。 5、为什么会有环状队列？ 环形队列的特点是,不需要进行动态的内存释放和分配,使用固定大小的内存空间反复使用。非常的简单和高效。

【实验小结】 (总结本次实验的重难点及心得、体会、收获)

原来感觉这个实验挺难的，但是后来认真地看了书上的代码，完成实验后，才发现并没有想象中的难。有时候想的和实际做的结果是不一样的，以后还是要多写代码，多实际动手操作一下。 【附录-实验代码】

#include #include #include #define MAXSIZE 100 //根据需要自己定义MAXSIZE为顺序栈的最大存储容量 typedef struct stack { int data[MAXSIZE]; int top; }SEQSTACK; void initstack(SEQSTACK *s)//顺序栈初始化 { s->top=-1 ;//将栈顶指针指向初始的位置 } int empty(SEQSTACK *s) //判断栈空 { if(s->top==-1) return 1; else return 0; } void push(SEQSTACK *s,int x)//元素x进栈 { if(s->top==MAXSIZE-1) printf(\"存储空间已满，元素进栈失败！\\n\"); else { s->top ++; //栈顶指针加1 s->data[s->top]=x; //将元素x送到栈顶位置 } } int pop(SEQSTACK *s)//元素出栈，出栈元素用e返回 { int e; if(empty(s)==-1) { printf(\"栈中元素已空，出栈元素失败！\\n\"); return -99; } else { e=s->data[s->top]; //将栈顶元素赋值给变量e s->top --; //栈顶指针减1 return e; } } void conversion(SEQSTACK *s,int N,int r)

{ //将十进制数N转换为r进制的数 int x; initstack(s); while (N!=0) //此循环为入栈操作 { push(s,N%r); //将N除以r所得的余数压入栈 N=N/r; //N整除r所得的商赋值给N } while (!empty(s)) //此循环为出栈操作 { x=pop(s); if(x==10)printf(\"A\"); else if(x==11)printf(\"B\"); else if(x==12)printf(\"C\"); else if(x==13)printf(\"D\"); else if(x==14)printf(\"E\"); else if(x==15)printf(\"F\"); else printf(\"%d\ } printf(\"\\n\"); } void main() { int number,r; //number为待准备转换的十进制数，r为进制 SEQSTACK stack; char choice; while(1) { printf(\"请输入一个十进制整数：\"); scanf(\"%d\ printf(\"选择将该数转换为几进制数(2，8，16)：\"); scanf(\"%d\ fflush(stdin); printf(\"转换后的结果为：\"); conversion(&stack,number,r); printf(\"是否继续？按N结束，其他任意键继续…\"); scanf(\"%c\ system(\"cls\"); if(choice=='N'||choice=='n') break; } }