利用栈实现把十进制数转换为二进制至十六进制之间的任一进制数并输出的功能。(第二版)

程序员文章站 2024-03-11 22:07:25

...

【实验题目内容】

保持计算机默认的十进制不变（要求不用C++流操纵符转换基数为八进制形式oct，不用C++流操纵符转换基数为十六进制形式hex，也不用setbase(base)函数将基数设置为base）。利用栈实现把十进制数转换为二进制至十六进制之间的任一进制数并输出的功能，要求设计C++算法。以下函数是要求实现的函数：

//将非负整数Integer转换为新基数为Radix的新整数newInteger
//完成转换返回true，否则，返回false
bool convert(long Integer, long Radix, long& newInteger);
//将十六整数Integer转换为字符串
string toString(long Integer);

【实验环境】（使用的软件）：VS - 2010

【项目设计源代码】

//stdafx.h头文件
#pragma once

#include "targetver.h"
#include <stdio.h>
#include <tchar.h>

// TODO: 在此处引用程序需要的其他头文件
#include<iostream>
#include<string>

using namespace std;

//linkNode.h
#pragma once
// 单链表的结点
// T为单链表中元素的模板类型
template <class T>
class linkNode
{
public:
	// 构造结点
	linkNode(void);
	// 析构结点
	~linkNode(void);
	// 元素
	T data;
	// 后继指针
	linkNode<T>* next;
};

// 构造结点
template <class T>
linkNode<T>::linkNode(void)
{
}

// 析构结点
template <class T>
linkNode<T>::~linkNode(void)
{
}

// LinkStack.h
#pragma once
#include "linkNode.h"
// 链栈类模板
// T为链栈中元素的模板类型
template <class T>
class LinkStack
{
public:
	// 默认构造函数
	LinkStack(void);
	// 析构函数
	~LinkStack(void);
protected:
	// 栈顶指针
	linkNode<T>* top;
public:
	// 遍历输出链栈
	void Print(void);
	// 判断栈是否为空
	bool IsEmpty(void) const;
	// 新元素newData进栈顶，进栈成功，
	// 则返回ture，否则，返回false
	bool Push(T newData);
	// 取栈顶元素topData，取栈顶元素成功，
	// 则返回true，否则，返回false
	bool GetTop(T& topData);
	// 栈顶元素topData出栈，栈顶元素出栈成功，
	// 则返回true，否则，返回false
	bool Pop(T& topData);
};

// 默认构造函数
template <class T>
LinkStack<T>::LinkStack(void)
{
	// 空链栈的栈顶为空
	top = NULL;
}

// 析构造函数
template <class T>
LinkStack<T>::~LinkStack(void)
{
	linkNode<T>* deleteNode,*current=top;
	while(current)
	{
		deleteNode=current;
		current=current->next;
		delete deleteNode;
	}
	top=NULL;
}

// 遍历输出链栈
template <class T>
void LinkStack<T>::Print(void)
{
	cout<<"top→";
	linkNode<T>* current=top;
	while(current!=NULL)
	{
		cout<<"["<<current->data<<"]";
		current=current->next;
		if(current!=NULL)
		{
			cout<<"[-]→";
		}
	}
	cout<<"[^]"<<endl;
}

// 判断栈是否为空
template <class T>
bool LinkStack<T>::IsEmpty(void) const
{
	return top==NULL;
}

// 新元素newData进栈顶，进栈成功，
// 则返回ture，否则，返回false
template <class T>
bool LinkStack<T>::Push(T newData)
{
	// 动态分配新元素
	linkNode<T>* newNode = new linkNode<T>;
	if(newNode==NULL)
	{
		// 内存分配失败
		cerr<<"内存分配失败。"<<endl;
		return false;
	}
	// 新元素的数据域更新为newData
	newNode->data = newData;
	// 原栈顶元素作为新元素的后继
	newNode->next = top;
	// 新元素成为新栈顶元素
	top=newNode;
	// 新元素进栈成功，返回true
	return true;
}

// 取栈顶元素topData，取栈顶元素成功，
// 则返回true，否则，返回false
template <class T>
bool LinkStack<T>::GetTop(T& topData)
{
	if(IsEmpty())
	{
		// 栈空，无任何元素
		return false;
	}
	// 栈顶元素通过引用形参topData返回
	topData = top->data;
	// 取栈顶元素成功，返回true
	return true;
}

// 栈顶元素topData出栈，栈顶元素出栈成功，
// 则返回true，否则，返回false
template <class T>
bool LinkStack<T>::Pop(T& topData)
{
	if(IsEmpty())
	{
		// 栈空，无栈何元素
		return false;
	}
	// 栈顶元素通过引用形参topData返回
	topData = top->data;
	// 保存原栈顶指针
	linkNode<T>* oldTop = top;
	// 栈顶指针后移1个元素
	top = top->next;
	// 释放原顶元素的空间
	delete oldTop;
	// 栈顶顶元素出栈成功，返回true
	return true;
}

// 主函数
#include "stdafx.h"
//包含链栈类模板头文件
#include "LinkStack.h"

//将非负整数Integer转换为新基数为Radix的新整数newInteger，
//完成转换，则返回true，否则，返回false
bool convert(long Integer, long Radix, long& newInteger)
{
	if(Integer < 0 || Radix <= 0 || Radix >= 100)
	{
		//整数Intege或新基数Radix的值不合法，无法转换，返回false
		return false;
	}
	LinkStack <unsigned long> stack;	//定义无符号长整型堆栈stack
	unsigned long Remainder;	//定义无符号长整型余数Remainder
	//将整数Integer对基数Radix求余数(从低位-->高位)，并依次压入堆栈stack
	while(Integer != 0)	//当被转换的整数Integer不为零时
	{
		Remainder = Integer % Radix;	//Integer对新基数Radix求余数存入Remainder
		stack.Push(Remainder);			//将余数Remainder压入栈顶
		Integer = Integer / Radix;		//Integer/Radix的商作为整数Integer的新值
	}
	newInteger = 0;	//转换结果newInteger清零
	//利用堆栈后进先出的特点，从堆栈中依次弹出基数为Radix的各位权值(从高位-->低位)
	while(!stack.IsEmpty())//当堆栈不空时
	{
		stack.Pop(Remainder);	//从栈顶弹出基数Radix的权值到Remainder
		if(Radix <= 10)
		{
			//基数Radix<=10，将newInteger*10+Remainder的值作为转换结果newInteger的新值
			newInteger = newInteger * 10 + Remainder;
		}
		else
		{
			//否则，将newInteger*100+Remainder的值作为转换结果newInteger的新值
			newInteger = newInteger * 100 + Remainder;
		}
	}
		return true;	//完成转换，返回true
}

//将十六整数Integer转换为字符串
string toString(long Integer)
{
	string Hexdecimal = "0123456789ABCDEF";
	string hexdecimalString="";
	while(Integer > 0)
	{
		hexdecimalString = Hexdecimal[Integer % 100] + hexdecimalString;
		Integer /= 100;
	}
	return hexdecimalString;
}

int _tmain(int argc, _TCHAR* argv[])
{
	//将运行结果窗口的属性设为黑字白底
	system("color F0");
	//定义变量Integer、Radix和newInteger
	long Integer, Radix, newInteger;
	//输出提示信息："输入1个非负的十进制数："
	cout << "输入1个非负的十进制数：";
	//从键盘输入1个非负的十进制数存入变量Integer中
	cin >> Integer;
	//输出提示信息："输入将要转换的新基数："
	cout << "输入将要转换的新基数：";
	//从键盘输入将要转换的新基数存入变量Radix中
	cin >> Radix;
	//调用函数convert，将非负整数Integer转换为基数为Radix的新整数newInteger
	if(convert(Integer, Radix, newInteger))
	{
		if(Radix <= 10)
		{
			//若转换成功，则输出非负整数整数Integer的值已经转换为基数为Radix的新整数newInteger的值
			cout << "非负整数" << Integer << "已经转换为" << Radix << "进制数：" << newInteger << endl;
		}
		else
		{
			//若转换成功，则输出非负整数整数Integer的值已经转换为基数为Radix的新整数newInteger的值
			cout << "非负整数" << Integer << "已经转换为" << Radix << "进制数：" << toString(newInteger) << endl;
		}
	}
	else
	{
		//转换失败，输出提示信息：整数Integer为负值，新基数Radix为负值或超过99，无法转换。
		cout << "整数" << Integer << "为负值，新基数" << Radix << "为负值或超过99，无法转换。" << endl;
	}
	return 0;
}