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

水深无声 2022-10-22 04:08 179阅读 0赞

### 目录 ###

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

# 一. 栈的概述 #

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

# 二. 二进制计算器的实现 #

## 1. 二进制数转换为其他进制的流程 ##

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

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

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

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

# 三. 代码实现 #

## 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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/f9c9848c674c49ad90a2f30cf95712ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/771f229f1f0444119e76ea7eb772ae1c.png