实验二 栈的操作及应用
实验学时：2
实验类型：（设计型）
一、实验目的
1. 理解并掌握栈的逻辑结构和链式存储方式；
2. 理解栈的相关基本算法；
3. 编程实现相关算法并进行验证；
4. 学会利用栈解决实际问题；
5. 掌握数制转换的实现算法。
二、实验条件
Visual C++。
三、实验原理及相关知识
1. 顺序栈的存储结构描述
2. 基本操作的算法描述
实验中涉及栈的构建、入栈、出栈、判断栈是否为空、获取栈顶元素、打印栈中所有元素等操作。
3. 数制转换运算的实现方法
假设要将十进制数N 转换为d 进制数，一个简单的转换算法是重复以下两步，直至N 为零：
（1）X = N mod d（mod 为求余运算）
（2）N = N div d （div 为整除运算）
四、实验步骤
1. 实现栈的构建、入栈、出栈、判断栈是否为空、获取栈顶元素、打印栈中所有元素等基本操作的函数。
2. 调用基本操作函数实现以下功能：
(1) 构建一个空栈；
(2) 将1,2,3,4入栈；
(3) 输出栈顶元素；
(4) 输出栈中所有元素；
(5) 按照1,2,3,4的顺序依次入栈；
(6) 输出三种不同的出栈序列；
(7) 将十进制数20转化为8进制数。
五、思考题及其它
1. 在将一个非负十进制数转换成十六进制数时，10-15是转换成字母A-F 输出的，如何解决这个问题？
【参考程序】
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define INIT_SIZE 100
#define INCREMENT 10
typedef int SElemType;
typedef struct {
SElemType *base ;
SElemType *top ;
int stacksize ; // 栈的可用最大容量
}SqStack;
int InitStack(SqStack *S){
// 创建一个空栈S
(*S).base=(SElemType *)malloc(INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
return ERROR;
;
(*S).stacksize=INIT_SIZE;
return OK;
}
int StackEmpty(SqStack *S)
{ //判断栈是否为空，为空则返回1，否则返回0
)
return 1;
else
return 0;
}
int GetTop(SqStack S, SElemType *e)
{ // 取出栈顶元素
if(S.top>S.base)
{
*e =*(S.top-1);
printf("栈顶元素是:%d",*e);
printf("\n");
return OK;
}
else
return ERROR;
}
int Push( SqStack *S, SElemType e )
{ //将数据元素e 入栈
if((*S).top-(*S).base>=(*S).stacksize) {
(*S).base=(SelemType *)
realloc((*S).base,((*S).stacksize+INCREMENT)*sizeof(SElemType));
if(!(*S).base)
return 0;
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize+=INCREMENT;
}
return OK;
}
int Pop(SqStack *S, SElemType *e)
{ //如栈不为空，将栈顶元素出栈
if((*S).top ==(*S).base)
return ERROR;
(*S).top--;
return OK;
}
void Print_SqStackTraverse( SqStack S ) //输出栈中元素 { //实现此函数
}
void conversion(int N ,int r) //把十进制数N 转换为r 进制 { //实现此函数
}
main()
{
SqStack S; InitStack(&S);
; ; ; ; ; ; ; ; ; ; }
//将1,2,3,4入栈 //输出栈顶元素 //输出栈中所有元素 //按照1,2,3,4的顺序依次入栈，输出三种不同的出栈序列//将十进制数20转化为8进制数
实验二 栈的操作及应用
实验学时：2
实验类型：（设计型）
一、实验目的
1. 理解并掌握栈的逻辑结构和链式存储方式；
2. 理解栈的相关基本算法；
3. 编程实现相关算法并进行验证；
4. 学会利用栈解决实际问题；
5. 掌握数制转换的实现算法。
二、实验条件
Visual C++。
三、实验原理及相关知识
1. 顺序栈的存储结构描述
2. 基本操作的算法描述
实验中涉及栈的构建、入栈、出栈、判断栈是否为空、获取栈顶元素、打印栈中所有元素等操作。
3. 数制转换运算的实现方法
假设要将十进制数N 转换为d 进制数，一个简单的转换算法是重复以下两步，直至N 为零：
（1）X = N mod d（mod 为求余运算）
（2）N = N div d （div 为整除运算）
四、实验步骤
1. 实现栈的构建、入栈、出栈、判断栈是否为空、获取栈顶元素、打印栈中所有元素等基本操作的函数。
2. 调用基本操作函数实现以下功能：
(1) 构建一个空栈；
(2) 将1,2,3,4入栈；
(3) 输出栈顶元素；
(4) 输出栈中所有元素；
(5) 按照1,2,3,4的顺序依次入栈；
(6) 输出三种不同的出栈序列；
(7) 将十进制数20转化为8进制数。
五、思考题及其它
1. 在将一个非负十进制数转换成十六进制数时，10-15是转换成字母A-F 输出的，如何解决这个问题？
【参考程序】
#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define INIT_SIZE 100
#define INCREMENT 10
typedef int SElemType;
typedef struct {
SElemType *base ;
SElemType *top ;
int stacksize ; // 栈的可用最大容量
}SqStack;
int InitStack(SqStack *S){
// 创建一个空栈S
(*S).base=(SElemType *)malloc(INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
return ERROR;
;
(*S).stacksize=INIT_SIZE;
return OK;
}
int StackEmpty(SqStack *S)
{ //判断栈是否为空，为空则返回1，否则返回0
)
return 1;
else
return 0;
}
int GetTop(SqStack S, SElemType *e)
{ // 取出栈顶元素
if(S.top>S.base)
{
*e =*(S.top-1);
printf("栈顶元素是:%d",*e);
printf("\n");
return OK;
}
else
return ERROR;
}
int Push( SqStack *S, SElemType e )
{ //将数据元素e 入栈
if((*S).top-(*S).base>=(*S).stacksize) {
(*S).base=(SelemType *)
realloc((*S).base,((*S).stacksize+INCREMENT)*sizeof(SElemType));
if(!(*S).base)
return 0;
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize+=INCREMENT;
}
return OK;
}
int Pop(SqStack *S, SElemType *e)
{ //如栈不为空，将栈顶元素出栈
if((*S).top ==(*S).base)
return ERROR;
(*S).top--;
return OK;
}
void Print_SqStackTraverse( SqStack S ) //输出栈中元素 { //实现此函数
}
void conversion(int N ,int r) //把十进制数N 转换为r 进制 { //实现此函数
}
main()
{
SqStack S; InitStack(&S);
; ; ; ; ; ; ; ; ; ; }
//将1,2,3,4入栈 //输出栈顶元素 //输出栈中所有元素 //按照1,2,3,4的顺序依次入栈，输出三种不同的出栈序列//将十进制数20转化为8进制数