文档介绍：数学与计算机学院
实验报告
( 2009 /2010 学年第 2 学期)
课程名称
数据结构
实验名称
实验1 栈和队列的用
实验时间
2010
年
4
月
26
日
指导单位
软件工程系
指导教师
周立章
学生姓名
郭春艳
班级学号
312008080611123
学院(系)
数学与计算机
专业
软件工程
实验名称
栈和队列的应用
指导教师
周立章
实验类型
验证
实验学时
3
实验时间
16:00-17:40
实验目的和要求
栈的顺序存储结构和链式存储结构;
掌握栈的先进后出的原则;
掌握栈的基本运算;加深理解顺序栈和链栈的意义,理解用栈的插入和删除操作算法。
掌握队列的顺序存储结构和链式存储结构;
掌握队列的先进先出的原则;
掌握队列的基本运算;加深理解顺序循环队列和链队列的意义,理解用顺序循环队列和链队列的入队和出队等基本操作算法。
实验要求:(1)理解栈初始化、判断栈是否空、入栈、出栈等算法;(2)理解队列入队、出队等算法。
二、实验环境(实验设备)
硬件: 微型计算机P4
软件: Windows XP+Microsoft Visual C++
三、实验原理及内容
实验题目:
:将任意一个十进制数转换成p进制的数。(p分别取2,8,16)
2. 假定一个单向循环链表来表示队列(即循环链队),该队列只设一个队尾指针rear,不设队首指针,试编写下列各种运算的算法:
向循环链队插入一个元素值为x的结点;
从循环链队中删除一个结点;
输出队列中所有元素;
实验前准备:
(1)请实现链栈的基本操作:初始化、进栈、出栈、输出。并要求上机验证通过。
(2)创建只有一个尾指针的单向循环队列的的结构体定义和初始化操作。
实验时完成1-2两题
实验后:考虑如果将2小题链队中的结点的数据类型改一个学生的通讯簿:姓名,手机号码、邮箱、QQ号。如何实现该题的相应算法,并要求上机验证通过。
实验解答:
1) 链栈中的结点是如何定义的?写出结构体描述。
typedef struct dnode
{
struct dnode *next;//指针域
int data; //数据域
}Dnode; //置于Sqstack前,因为后面的用到了Dnode
2)写出链栈的入栈算法
void push(Sqstack &S,Dnode *p,int e)
{
p=(Dnode *)malloc(sizeof(Dnode));//定义结点,分配空间
p->data=e;
///链栈不存在空间不足
//链栈是用指针取数据,->next
p->next=;
=p;//p始终指向最后结点
}
3)写出链栈的出栈算法?
void pop(Sqstack &S)
{
while(!=) //非空栈
{
if(->data>=10)//大于10进行字母转换
printf("%c",(char)(->data+55));
else
printf("%d",->data);
=->next;
}
printf("\n");
}
4)写出利用链栈进行通用数制转换算法?在该算法中你是如何考虑进位制中数码转换和保存的?
void DtoP(Sqstack &S)
{
==(Dnode *)malloc(sizeof(Dnode));
->next=0;
int n,i;
printf("请输入十进制数:");
scanf("%d",&n);
int x;
printf("请输入要转化成的进制:");
scanf("%d",&x);
while(n)
{ Dnode *p=0;
p=(Dnode*)malloc(sizeof(Dnode)); //指向结点的指针
push(S,p,n%x); //将余数进栈
n=n/x; //将商做为新的被除数
}
pop(S);
}
答:在算法中,考虑到十进制数转换成十六进制数,在模余数大于10时要将其转换成大写字母,又由大写字母与数字间的转换关系来进行判断输出。
在数据转换中,你使用的测试数据有哪些?测试了哪几种进位制?结果是什么?
答:测试数据有28,测试二进制:11100
测试数据有33,测试八进制:41
测试数据有9