滴水逆向联盟

标题: VC++2012编程演练数据结构《3》堆栈实现进制转换 [打印本页]

作者: 大灰狼 时间: 2014-9-24 08:32
标题: VC++2012编程演练数据结构《3》堆栈实现进制转换
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
　　栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。
　　栈可以用来在函数调用的时候存储断点，做递归时要用到栈！
　　以上定义是在经典计算机科学中的解释。
　　在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址增大，弹出的操作使得栈顶的地址减小。

　　栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。

打开IDE

我们创建一个VC++2012工程来实现堆栈类与应用

头文件

[cpp] view plaincopy

#if !defined(AFX_STACK_H__CC48020F_CB24_4299_8D43_0DCB84F1375E__INCLUDED_)
#define AFX_STACK_H__CC48020F_CB24_4299_8D43_0DCB84F1375E__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "stdafx.h"
//顺序栈的类定义stack.h
#define ERROR 0
#define EQUAL 1
#define OVERFLOW -1
#define STACKSIZE 100
#define STACKINCREMENT 10
class SqStack
{private:
SElemType *base;
SElemType *top;
int stacksize;
public:
//构造一个空栈S
Status InitStack(SqStack **S);
//栈存在则栈被销毁
Status DestroyStack();
//栈存在则清为空栈
Status ClearStack();
//栈存在则返回true,否则false
bool StackEmpty();
// 栈存在则返回栈的元素个数,即栈的长度
int StackLength();
//栈存在且非空则返回栈的栈顶元素
SElemType GetTop();
// 栈存在则插入元素e为新的栈顶元素
Status Push(SElemType e);
// 栈存在且非空则删除栈的栈顶元素并用e返回其值
SElemType Pop(SElemType *e);
// 栈的遍历
void StackTraverse(void (*visit)(SElemType *));
};
#endif // !defined(AFX_STACK_H__CC48020F_CB24_4299_8D43_0DCB84F1375E__INCLUDED_)

实现文件

[cpp] view plaincopy

//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "stack.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Status SqStack::InitStack(SqStack **S)
{
(*S)=(SqStack *) malloc(sizeof(SqStack));
(*S)->base=(SElemType *)malloc(STACKSIZE *sizeof(SElemType));
if(!(*S)->base) exit(OVERFLOW);
(*S)->top=(*S)->base;
(*S)->stacksize=0;
return 1;
}
Status SqStack::DestroyStack()
{
free(base);
return 1;
}
Status SqStack::ClearStack()
{
stacksize=0;
return 1;
}
bool SqStack::StackEmpty()
{
if(stacksize==0) return true;
else return false;
}
int SqStack::StackLength()
{
return stacksize;
}
SElemType SqStack::GetTop()
{
if(top==base)
{
cerr<<"空栈!\n";exit(1);}
return *(top-1);
}
Status SqStack::Push(SElemType e)
{
*(top++)=e;stacksize++;
return 1;
}
SElemType SqStack::Pop(SElemType *e)
{
if(top==base)
{
cerr<<"空栈!\n";
exit(1);
}
*e=*--top;
stacksize--;
return *e;
}
void SqStack::StackTraverse(void (*visit)(SElemType *))
{
while(top!=base)
{
stacksize--;visit(--top);
}}

我们来实现调用类演习一下

[cpp] view plaincopy

#include "stdafx.h"
#include "stack.h"
using namespace std;
void conversion()
{
SqStack *S;
SElemType e;
int n;
S->InitStack(&S);
printf("输入十进制数:");cin>>n;
if(n<0)
{ printf("\n数必须大于零!\n");
return;}
if(!n) S->Push(0);
while(n){
S->Push(n%8);n=n/8;}
printf("结果是:");
while(!S->StackEmpty()){
S->Pop(&e);
printf("%d",e);}
}
void main()
{
printf("运行结果:\n");
conversion();
getch();
}

欢迎光临滴水逆向联盟 (http://www.dtdebug.com/)