实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求：堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】验证性实验（学时数：2H）【实验内容】内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。

可以实验一的结果自己实现数据输入、数据显示的函数。

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

【思考问题】1.栈的顺序存储和链表存储的差异？2.还会有数据移动吗？为什么？3.栈的主要特点是什么？队列呢？4.栈的主要功能是什么？队列呢？5.为什么会有环状队列？【参考代码】（一）利用顺序栈实现十进制整数转换转换成r进制1、算法思想将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下：N N / 8 （整除）N % 8（求余）3456 432 0 低432 54 054 6 66 0 6 高所以：（3456）10 =（6600）8我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。

算法思想如下：当N>0时重复1，2①若N≠0，则将N % r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。

②用N / r 代替N2、转换子程序#include<stdio.h>#define L_size 100 //根据需要自己定义L_size为顺序栈的最大存储容量void conversion(int N,int r){ //将十进制数N转换为r进制的数int s[L_size],top;//定义一个顺序栈，top为栈顶指针，注意此处没有使用结构体类型int x;top=-1; //初始化栈while (N!=0) //此循环为入栈操作{s[++top]= ; //余数入栈; //商作为被除数继续}while (top!=-1) //此循环为出栈操作{x=s[top--];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",x);}printf("\n");}3、编写主函数验证上述转换子函数是否正确。

void main() //自己设计主函数完成{int number,r; //number为待准备转换的十进制数，r为进制printf("请输入一个十进制整数：");scanf("%d",&number);printf("选择将该数转换为几进制数(2，8，16)：");scanf("%d",&r);printf("转换后的结果为：");conversion(number,r);}（二）用顺序栈实现算术后缀表达式求值1、算法思想。

后缀表达式求值步骤：a、循环读出后缀表达式中的每一个字符；b、若是数字，将对应的字符串转换成整数，入栈；c、若是运算符，从栈中弹出2个数，将运算结果再压入栈；d、若表达式输入完毕，栈顶即表达式值；2、后缀表达式求值子程序#include<stdio.h>#include<stdlib.h>#define L_size 50void postexp(){int st[L_size],top=-1; //定义一个顺序栈，top为栈顶指针int d=0; //定义用来字符串转换整数的变量dchar ch;printf("请输入规范的后缀表达式(操作数、运算符之间使用空格间隔开，eg:3 2 5 * +):\n"); //输入范例while((ch=getchar())!='\n') //开始输入字符并赋给ch{if(ch==' ') //如果输入的是空格，不做处理elseswitch(ch) //判断输入是否运算符，如果时就进行相应的操作{case '+':;;break;case '-':st[top-1]=st[top-1]-st[top];top--;break;case '*':st[top-1]=st[top-1]*st[top];top--;break;case '/':if(st[top]!=0)//分母不为零计算才有效{st[top-1]=st[top-1]/st[top];top--;}else{printf("除数为0!\n"); //分母为零计算无效，退出程序exit(1);}break;default:while(ch>='0'&&ch<='9'){;ch=getchar();}st[++top]=d;//将转换后的数值入栈d=0;}}printf("运算结果是:%d\n",st[top]);}3、编写主函数验证上述求值子函数是否正确。

void main() //自己设计主函数完成{postexp();}（三）链式队列基本操作1、队列结点定义根据实际处理数据的类型定义链队中结点的值域类型ElemType#include<stdio.h>#include<stdlib.h>#include<conio.h>typedef int Elemtype;typedef struct node //队列结点类型定义{ Elemtype data; //队列的数据元素类型struct node *link; //指向后继结点的指针}NODE;struct QueueLk{ //定义链队NODE *front,*rear;//定义链队队头和队尾指针};2、入队struct QueueLk *ldcr(struct QueueLk *QL,Elemtype x)//将元素x插入到链队列rear中，作为rear的新队尾{NODE *p;p=(NODE *)malloc(sizeof(NODE));p->data=x;p->link=NULL; //置新结点的指针为空if(QL->front==NULL) //队列为空QL->front=QL->rear=p;else{; //将链队列中最后一个结点的指针指向新结点; //将队尾指向新结点}return QL;}3、出队Elemtype ldsc(struct QueueLk *QL)//若链队列不为空，则删除队头元素，返回其元素值{ NODE *s;Elemtype x;if(QL->front==QL->rear) //队空，退出程序exit(1);s=QL->front->link; //取队头保存在s中; //删除队头结点if(s->link==NULL) //如果删除后队列为空，则处理队尾指针 QL->rear=QL->front;x=s->data; //将刚才出队的结点值给x; //释放出该结点的空间 return x;}4、队列的初始化void initqueue(QueueLk *QL){QL->front=(NODE *)malloc(sizeof(NODE));QL->front->link=NULL;QL->rear=QL->front;}5、队列的显示void dispqueue(QueueLk *QL){NODE *q;q=QL->front->link;if(q==NULL)printf("队列已空!\n");while(q!=NULL){printf("%5d",q->data);q=q->link;}printf("\n");}6、编写主函数验证上述子函数是否正确。

void main(){struct QueueLk *p;int choice,elemdata,x=0;p=(struct QueueLk *)malloc(sizeof(struct QueueLk));initqueue(p);while(1){printf("请输入你的操作选择：\n");printf("(1)元素入队请按数字1!\n");printf("(2)元素出队请按数字2!\n");printf("(3)显示队列请按数字3!\n");printf("(4)清屏幕请按数字4!\n");printf("(5)退出程序请按数字5!\n");scanf("%d",&choice);switch(choice){case 1:printf("请输入待进队元素的值：");scanf("%d",&elemdata);p=ldcr(p,elemdata);break;case 2:x=ldsc(p);printf("元素%d出队成功!\n",x);break;case 3:printf("队列中的元素分别为：\n");dispqueue(p);break;case 4:system("cls");break;case 5:return;}}}【实验小结】(总结本次实验的重难点及心得、体会、收获)得分_____________评阅日期_____________教师签名__ __________。