[数据结构]栈的基本操作以及利用栈实现二进制计算器

admin管理员组

文章数量:1794759

[数据结构]栈的基本操作以及利用栈实现二进制计算器

目录

• 一. 栈的概述
• 二. 二进制计算器的实现
• • 1. 二进制数转换为其他进制的流程
  • 2. 如何利用顺序栈完成上述步骤
• 三. 代码实现
• • 1. 栈的基本操作
  • • 1). 栈的顺序存储结构
    • 2). 初始化栈
    • 3). 入栈(栈满，利用realloc函数增容)
    • 4). 出栈
  • 2. 进制转换器代码实现
  • • 1). 二进制转换为八进制
    • 2). 二进制转换为十六进制
    • 3). 二进制转换为十进制

一. 栈的概述

  栈是一种先进后出的数据结构，最后进去的元素最先出来。在栈中，仅允许在栈的一端进行操作，即从栈顶插入元素，栈顶取出元素。

二. 二进制计算器的实现 1. 二进制数转换为其他进制的流程

   1).在二进制数中，如何转换为其他进制数。    这里以二进制转化位八进制数为例，当我们需要将110101101转换为八进制数时，一般以三位二进制数对应一位八进制数进行划分。当高位不够三位二进制数时，以0补全。之后利用位权表示法进行计算。

2. 如何利用顺序栈完成上述步骤

   思想与上述转换方法类似，只是在存储计算出的八进制数时略有区别。(同样利用二进制转八进制为例)

   1). 将二进制数按照顺序进行入栈。    2). 取出三位二进制数，利用位权表示法进行计算对应八进制数。    3). 对计算结果进行存储，这里我们是从后向前对二进制数进行处理，如果直接输出会导致输出结果 逆序 ，所以我们再一次利用栈先进后出的特性对计算结果进行存储。开辟一个新栈 将计算结果顺序入栈，再通过出栈对数据进行输出就会正常显示计算结果。   4).在该程序中使用的结构为栈的顺序存储结构，在初始化栈时会固定栈的大小，如果栈空间不足，会利用动态扩容的方法增加栈的长度。具体实现请看下方代码。

三. 代码实现 1. 栈的基本操作 1). 栈的顺序存储结构

在这个程序中，我们使用栈的顺序存储结构。

struct sqStack { ElemeType* base; ElemeType* top; int stackSize; // 当前栈的最大容量 }; 2). 初始化栈 void CreateStack(sqStack*& sq) { sq->base = new ElemeType[STACK_INIT_SIZE]; if (!sq->base) { cout << "分配空间失败" << endl; return; } sq->top = sq->base; sq->stackSize = STACK_INIT_SIZE; } 3). 入栈(栈满，利用realloc函数增容)

realloc()函数使用时，会重新申请一块指定大小的内存空间，并将之前数据进行移入。

void StackPush(sqStack*& sq, ElemeType e) { if (sq->top - sq->base >= sq->stackSize) { sq->base = (ElemeType*)realloc(sq->base, (sq->stackSize + STACKINCREAMENT) * sizeof(ElemeType)); if (!sq->base) { cout << "增加分配空间失败" << endl; return; } sq->stackSize += STACKINCREAMENT; } *sq->top = e; sq->top++; } 4). 出栈 int StackPop(sqStack*& sq, ElemeType& e) { if (sq->top == sq->base) { cout << " 栈空" << endl; return 0; } e = *--(sq->top); return 1; } 2. 进制转换器代码实现 1). 二进制转换为八进制 void Bin2Oct(sqStack*& sq) { // 创建新栈 用来存储转换后的结果 sqStack* sqOct = new sqStack; CreateStack(sqOct); // 取出存放二进制栈的元素 计算转换为8进制的结果 for (int j = 0; j < sq->top - sq->base; j++) { ElemeType octNum = 0; for (int i = 0; i < 3; i++) { ElemeType e; if (!StackPop(sq, e)) { continue; } // 因为输入值为字符类型，所以利用48减去元素，得到ACSII表对应字符 int binNum = abs(48 - e); octNum += binNum * pow(2, i); } octNum += 48; // 将计算好的8进制数 入栈 StackPush(sqOct, octNum); } cout << "转换后结果为:"; PrintOct(sqOct); } 2). 二进制转换为十六进制 void Bin2Oct(sqStack*& sq) { // 创建新栈 用来存储转换后的结果 sqStack* sqOct = new sqStack; CreateStack(sqOct); // 取出存放二进制栈的元素 计算转换为8进制的结果 for (int j = 0; j < sq->top - sq->base; j++) { ElemeType octNum = 0; for (int i = 0; i < 4; i++) { ElemeType e; if (!StackPop(sq, e)) { continue; } int binNum = abs(48 - e); octNum += binNum * pow(2, i); } octNum += 48; // 如果超过10则转换为字母 if (octNum > 57) { octNum += 7; } // 将计算好的16进制数推入栈 StackPush(sqOct, octNum); } cout << "转换后结果为:"; PrintOct(sqOct); } 3). 二进制转换为十进制

二进制转十进制只需要使用位权表示法算出转化总和即可，不用利用栈去存储转换结果。

int Bin2Dec(sqStack*& sq) { int sum = 0; ElemeType e; int len = StackLen(*sq); for (int i = 0; i < len; i++) { PopStack(sq, e); int num = abs(48 - e); sum += num * pow(2, i); } return sum; }

本文标签： 数据结构计算器操作