实验二 堆栈和队列基本操作的编程实现实验二堆栈和队列基本操作的编程实现
【实验目的】
堆栈和队列基本操作的编程实现
要求:
堆栈和队列基本操作的编程实现(2学时,验证型),掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现,存储结构可以在顺序结构或链接结构中任选,也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。
【实验性质】
验证性实验(学时数:2H)
【实验内容】
内容:
把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。
利...
实验二堆栈和队列基本操作的编程实现
【实验目的】
堆栈和队列基本操作的编程实现
:
堆栈和队列基本操作的编程实现(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 0
54 6 6
6 0 6 高
所以:(3456)10 =(6600)8
我们看到所转换的8进制数按底位到高位的顺序产生的,而通常的输出是从高位到低位的,恰好与计算过程相反,因此转换过程中每得到一位8进制数则进栈保存,转换完毕后依次出栈则正好是转换结果。
算法思想如下:当N>0时重复1,2
①若N≠0,则将N % r 压入栈s中,执行2;若N=0,将栈s的内容依次出栈,算法结束。
②用N / r 代替N
2、转换子程序
#include
#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
#include
#define L_size 50
void postexp()
{
int st[L_size],top=-1; //定义一个顺序栈,top为栈顶指针
int d=0; //定义用来字符串转换整数的变量d
char ch;
printf("请输入的后缀表达式(操作数、运算符之间使用空格间隔开,eg:3 2 5 * +):\n"); //输入范例
while((ch=getchar())!='\n') //开始输入字符并赋给ch
{
if(ch==' ') //如果输入的是空格,不做处理
else
switch(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
#include
#include
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;
}
}
}
【实验小结】(总结本次实验的重难点及心得、体会、收获)
得分_____________
评阅日期_____________
教师签名__ __________
本文档为【实验二 堆栈和队列基本操作的编程实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。