栈和队列的基本操作.docx
《栈和队列的基本操作.docx》由会员分享，可在线阅读，更多相关《栈和队列的基本操作.docx（16页珍藏版）》请在冰点文库上搜索。
栈和队列的基本操作
《数据结构与算法》实验报告
专业
班级
学号
实验项目
实验二栈和队列的基本操作。
实验目的
1、掌握栈的基本操作：
初始化栈、判栈为空、出栈、入栈等运算。
2、掌握队列的基本操作：
初始化队列、判队列为空、出队列、入队列等运算。
实验容
题目1：
进制转换。
利用栈的基本操作实现将任意一个十进制整数转化为R进制整数
算法提示：
1、定义栈的顺序存取结构
2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）
3、定义一个函数用来实现上面问题：
十进制整数X和R作为形参
初始化栈
只要X不为0重复做下列动作
将X%R入栈X=X/R
只要栈不为空重复做下列动作
栈顶出栈输出栈顶元素
题目2：
利用队列的方式实现辉三角的输出。
算法设计分析
（一）数据结构的定义
1、栈的应用
实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。
因此，运用栈先进后出的性质，即可完成进制转换。
栈抽象数据结构描述
typedefstructSqStack/*定义顺序栈*/
{
int*base;/*栈底指针*/
int*top;/*栈顶指针*/
intstacksize;/*当前已分配存储空间*/
}SqStack;
2、队列的应用
由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。
即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。
队列抽象数据结构描述
typedefstructSeqQueue
{
intdata[MAXSIZE];
intfront;/*队头指针*/
intrear;/*队尾指针*/
}SeqQueue;
（二）总体设计
1、栈
（1）主函数：
统筹调用各个函数以实现相应功能
intmain（）
（2）空栈建立函数：
对栈进行初始化。
intStackInit（SqStack*s）
（3）判断栈空函数：
对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。
intstackempty（SqStack*s）
（4）入栈函数：
将元素逐个输入栈中。
intPush（SqStack*s,intx）
（5）出栈函数：
若栈不空，则删除栈顶元素，并用x返回其值。
intPop（SqStack*s,intx）
（6）进制转换函数：
将十进制数转换为R进制数
intconversion（SqStack*s）
2、队列
（1）主函数：
统筹调用各个函数以实现相应功能
voidmain（）
（2）空队列建立函数：
对队列进行初始化。
SeqQueue*InitQueue（）
（3）返回队头函数：
判断队是否为空，若不为空则返回队头元素。
intQueueEmpty（SeqQueue*q）
（4）入队函数：
将元素逐个输入队列中。
voidEnQueue（SeqQueue*q,intx）
（5）出队函数：
若队列不空，则删除队列元素，并用x返回其值。
intDeQueue（SeqQueue*q）
（6）计算队长函数：
计算队列的长度。
intQueueEmpty（SeqQueue*q）
（7）输出辉三角函数：
按一定格式输出辉三角。
voidYangHui（intn）
（三）各函数的详细设计：
1、栈
（1）intmain（）主函数
定义s为栈类型
调用函数建立空栈
调用进制转换函数
返回0值
（2）intStackInit（SqStack*s）空栈建立函数
动态分配存
判断分配成功并返回相应的值
若成功，初始化存储空间
（3）intstackempty（SqStack*s）判断栈空函数
若栈为空，返回0，否则返回1
（4）intPush（SqStack*s,intx）入栈函数
比较栈中元素所占空间与已分配存储空间
若栈满，追加存储空间
若存储失败则返回0
存储空间不够，添加增量
逐个输入数据元素
返回x的值
（5）intPop（SqStack*s,intx）出栈函数
如果栈为空，则返回0
若栈不空，则删除栈顶元素，用x返回其值
（6）：
intconversion（SqStack*s）进制转换函数
输入要转化的十进制数
输入要转化为几进制
运用求余运算改变进制数
运用选择结构控制十六进制的输出方式
2、队列
（1）voidmain（）主函数
输入辉三角的行数
调用辉三角输出函数
输出辉三角
（2）SeqQueue*InitQueue（）空队列建立函数
动态分配存
建立队列并返还该队列
（3）intQueueEmpty（SeqQueue*q）返回队头函数
判断队列为空，返回0
若不空返回队头元素
（4）voidEnQueue（SeqQueue*q,intx）入队函数
判断队满
若不满，逐个添加元素
（5）intDeQueue（SeqQueue*q）出队函数
若头指针等于尾指针，顺序队列是空的不能做删除操作
否则，删除队列
用x返回出队的值
（6）intQueueEmpty（SeqQueue*q）计算队长函数
头指针减尾指针，求队列长度
（7）voidYangHui（intn）输出辉三角函数
定义变量
循环输出元素1
插入1为队列队尾元素
使用空格控制输出格式
逐个输出队列元素，并构建下一行需输出的队列
运算结果插入队尾
实验测试结果及结果分析
（一）测试结果
（进制转换）
（辉三角）
（二）结果分析
调试程序时，出现了许多错误。
如：
有时候写的没有出现问题，但运行的结果是Pressanukeytocontinue。
程序肯定有错，但为什么会出现这种问题呢。
分号的忘记那还是很经常的，要加强注意。
在做表达式的计算的时候一定要注意何时入栈何时出栈，队列也是同样的。
如果如栈与出栈的情况判断不清楚就无法得出答案。
在写主函数时，如果是用voidmain的形式，那么可以不用有返回值，如果是intmain的话，要有返回值，既末尾要有return语句。
实验总结
1.进一步巩固了C语言的基础，尤其是指针那部分；
2.通过实验加深了对栈和队列的操作方面知识的认识。
更深层次了解了栈和队列的操作特点及不同之处；
3.通过实验达到了理论与实践结合的目的，提高了自己的编程能力；
4.程序可能不够完善需要在学习过程中不断去完善，这需要平时的努力。
附录实验程序代码
一、进制转换
#include
#include
#include
#defineSTACK_INIT_SIZE100/*存储空间初始分配量*/
#defineSTACKINCEREMENT10/*存储空间分配增量*/
typedefstructSqStack/*定义顺序栈*/
{int*base;/*栈底指针*/
int*top;/*栈顶指针*/
intstacksize;/*当前已分配存储空间*/
}SqStack;
/*建立空栈函数*/
intStackInit（SqStack*s）/*构造一个空栈*/
{s->base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;/*动态分配存*/
if（!
s->base）/*存储分配失败*/
return0;
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;/*初始化存储空间*/
return1;
}
/*判断栈空函数*/
intstackempty（SqStack*s）/*判断栈是否为空*/
{if（s->top==s->base）
{return1;}
else
{return0;}
}
/*入栈函数*/
intPush（SqStack*s,intx）/*入栈，插入x为新的栈顶元素*/
{if（s->top-s->base>=s->stacksize）/*比较栈中元素所占空间与已分配存储空间*/
{
s->base=（int*）realloc（s->base,（s->stacksize+STACKINCEREMENT）*sizeof（int））;
/*栈满，追加存储空间*/
if（!
s->base）/*若存储失败则返回0*/
return0;
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCEREMENT;/*存储空间不够，添加增量*/
}
*（s->top++）=x;/*逐个输入数据元素*/
returnx;
}
/*出栈函数*/
intPop（SqStack*s,intx）/*出栈操作*/
{if（s->top==s->base）/*如果栈为空，则返回0*/
return0;
x=*--s->top;/*若栈不空，则删除栈顶元素，用x返回其值*/
returnx;
}
/*进制转换函数*/
intconversion（SqStack*s）
{/*将所输入的任意一个非负的十进制数转换为R进制的数*/
intn,x=0,R=0;
printf（"输入要转化的十进制数：
\n"）;
scanf（"%d",&n）;
printf（"要转化为几进制：
\n输入2代表二进制\n输入8代表八进制\n输入16代表十六进制\n"）;
scanf（"%d",&R）;
printf（"将十进制数%d转化为%d进制是：
\n",n,R）;
while（n）
{Push（s,n%R）;/*运用求余运算改变进制数*/
n=n/R;
}
while（!
stackempty（s））
{x=Pop（s,x）;
switch（x）/*十六进制的输出方式*/
{case10:
printf（"A"）;
break;
case11:
printf（"B"）;
break;
case12:
printf（"C"）;
break;
case13:
printf（"D"）;
break;
case14:
printf（"E"）;
break;
case15:
printf（"F"）;
break;
default:
printf（"%d",x）;
}
}
printf（"\n"）;
return0;
}
/*主函数*/
intmain（）
{SqStacks;/*定义s为栈类型*/
StackInit（&s）;
conversion（&s）;
return0;
}
二、输出辉三角
#include
#include
#include
#defineMAXSIZE10
typedefstructSeqQueue/*定义队列*/
{
intdata[MAXSIZE];
intfront;/*队头指针*/
intrear;/*队尾指针*/
}SeqQueue;
/*建立空队列函数*/
SeqQueue*InitQueue（）/*构造一个空队列*/
{
SeqQueue*q;
q=（SeqQueue*）malloc（sizeof（SeqQueue））;/*动态分配存*/
q->front=q->rear=0;
returnq;
}
/*入队函数*/
voidEnQueue（SeqQueue*q,intx）/*插入元素x为队列的新的队尾元素*/
{
if（（q->rear+1）%MAXSIZE==q->front）/*判断队满*/
printf（"\n顺序循环队列是满的！
"）;
else
{
q->data[q->rear]=x;
q->rear=（q->rear+1）%MAXSIZE;
}
}
/*出队函数*/
intDeQueue（SeqQueue*q）/*若队列不空则删除队头元素，并返回其值*/
{
intx;
if（q->front==q->rear）
{
printf（"\n顺序队列是空的！
不能做删除操作！
"）;
return0;
}
x=q->data[q->front];/*用x返回出队的值*/
q->front=（q->front+1）%MAXSIZE;
returnx;
}
/*求队列长度函数*/
intQueueEmpty（SeqQueue*q）/*求队列的长度*/
{
return（q->front-q->rear）;
}
/*返回队头函数*/
intGetHead（SeqQueue*q）/*用e返回队头元素*/
{
inte;
if（q->front==q->rear）/*队列为空*/
e=0;
else
e=q->data[q->front];
returne;
}
/*输出辉三角函数*/
voidYangHui（intn）/*输出辉三角*/
{
SeqQueue*q;
inti,j,a,b;
for（i=1;iprintf（""）;
printf（"1\n"）;/*循环输出元素1*/
q=InitQueue（）;
EnQueue（q,0）;
EnQueue（q,1）;/*插入1为队列队尾元素*/
for（j=1;j{
for（i=1;iprintf（""）;
EnQueue（q,0）;
while（t!
=0）;/*逐个输出队列元素，并构建下一行需输出的队列*/
{
a=DeQueue（q）;
b=GetHead（q）;
if（t）printf（"%5d"b）;
elseprintf（"\n"）;
EnQueue（q,a+b）;
}
}
DeQueue（q）;
printf（"%5d",DeQueue（q））;
while（!
QueueEmpty（q））
{
b=DeQueue（q）;
printf（"%5d",b）;
}
}
/*主函数*/
voidmain（）
{
intn;
printf（"请输入辉三角的行数：
\n"）;
scanf（"%d",&n）;
YangHui（n）;
getchar（）;
printf（"\n"）;
}
序号
项目
得分
总分
1
实验报告排版（3分）
2
算法思想分析（6分）
3
源代码（6分）
4
实验结果及分析（5分）
升级会员 