栈和队列的定义及基本操作

闽 江 学 院 电 子 系 实 验 报 告

学生姓名：樊兴德 班级：15级电信一班 学 号：3151003165 一、 实验题目：栈和队列的定义及基本操作 二、 实验地点：大成楼A210 三、 实验目的： 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3.掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等 基本操作。 4.加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 四、 实验内容： 1.定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素； 2.实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换； 利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作： . 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底； . 完成一个元素的入栈操作，修改栈顶指针； . 完成一个元素的出栈操作，修改栈顶指针； . 读取栈顶指针所指向的元素的值； . 实现将十进制数N 和其它d 进制数的转换 ..编写主程序，实现对各不同的算法调用。 五、 实验环境（使用的软件）：Visual C++6.0 六、 实验步骤及操作： #include #include #define MAXSIZE 100 typedef struct { int data[MAXSIZE];

1

int top; }seqstack; seqstack *s; int setnull(seqstack *s)/* 把S 置为空栈*/ {s->top=-1; return 1;} destroystack(seqstack *S)/* 销毁栈S，S 不再存在*/ { free(s); return 1; } int empty(seqstack *s) /* 若栈S 为空栈，则返回TRUE，否则返回FALSE */ {if(s->top==-1) return 1; else return 0; } int push(seqstack *s,int e) /* 插入元素e 为新的栈顶元素*/ {if(s->top==MAXSIZE-1) return 0; else { s->data[++s->top]=e; return 1; } } int pop(seqstack *s)/* 若栈不空，则删除S 的栈顶元素，用e 返回其值，并返回OK；否则返回ERROR */ {if(s->top==-1) return NULL; else return s->data[s->top--]; } int gettop(seqstack *s) { if(s->top==-1) return NULL; else { return s->data[s->top]; 2

} }void convert(int a,int q) /*转换*/ {int n,i,j; while(a) { n=a%q; a=a/q; push(s,n); } printf(\"答案是\\n\"); j=s->top; while(s->top>-1) { i=pop(s); if(i==10) printf(\"A\"); else if(i==11) printf(\"B\"); else if(i==12) printf(\"C\"); else if(i==13) printf(\"D\"); else if(i==14) printf(\"E\"); else if(i==15) printf(\"F\"); else printf(\"%d\ } s->top=j; printf(\"\\n\"); } int Stacklen(seqstack *s)/* 返回S 的元素个数，即栈的长度*/ { int n; n=s->top+1; return n; } void main() /*主函数*/ { int i,x,n; s=(seqstack *)malloc(sizeof(seqstack)); s->top=-1; printf(\" **************************************************************\\n\"); printf(\" * 顺序栈操作程序 *\\n\"); printf(\" * 1:十进制间转换任意进制 2:判断是否空栈 *\\n\"); printf(\" * 3:求栈的长度 4:读出栈顶元素 *\\n\"); printf(\" * 5:置空栈 6:销毁栈 *\\n\"); printf(\" * 7:退出程序 *\\n\"); printf(\" **************************************************************\\n\"); 3

while(i) {printf(\"请输入您的选择1,2,3,4,5,6,7\\n\"); scanf(\"%d\ switch(i) { case 1:printf(\"请输入十进制数字\\n\"); scanf(\"%d\ for(n=0;n!=8&&n!=2&&n!=16;) {printf(\"需要转换为多少进制\\n\"); scanf(\"%d\ if(x==0) printf(\"0\\n\"); else convert(x,n);break; case 2:printf(\"%d\\n\ case 3:printf(\"%d\\n\ case 4:printf(\"%d\\n\ case 5:printf(\"%d\\n\ case 6:printf(\"%d\\n\ case 7:printf(\"感谢使用\\n\");i=0;break; default:printf(\"\\n 您的选择错误，请重新选择!\\n\"); } } } 保存，编译，连接，运行。 七、 实验结果: 1.将十进制数64转换为八进制数。 4

2.将十进制数128转化为十六进制数。 5

八、 实验总结及心得体会： 1.栈是操作受限的线性表，限定对元素的插入和删除运算只能在表的一端进行。 2.由栈的定义可知，每一次入栈的元素都在原栈顶元素之上成为新的栈顶元素，每一次出栈的元素总是当前栈顶元素使次栈顶元素成为新的栈顶元素，即最后进栈的元素总是最先出栈。所以栈也称为后进先出表。 6

九、 对本实验过程及方法、手段的改进建议： 对单个实现程序进行一一编译连接，能够更好更快的找出程序代码中的错误。 报告评分： 指导教师签字： 批阅日期： 注意：

 实验报告以纸质文档形式上交。实验报告将记入平时成绩；

 每次实验开始时，交上一次的实验报告，否则将扣除此次实验成绩。

7