【数据结构周周练】004顺序栈与链栈 -数制转换

清疚 2021-06-11 15:12 391阅读 0赞

这次只有一道题：数制转换，采用了顺序栈和链栈。这是栈的一个很经典的应用，不过结构定义和算法实现方法不唯一，如果大家有其他的算法实现，在下面评论哦！

**目录**

习题一：数制转换

1、题目

2、顺序栈实现

代码

执行结果

3、链栈实现

代码

执行结果

--------------------

# 习题一：数制转换 #

## 1、题目 ##

将一个十进制的数转化为八进制。

## 2、顺序栈实现 ##

### 代码 ###

#define MAXSTACKSIZE 20
    #define STACKCREMENT 5
    #include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct {
    	int *base;
    	int *top;
    	int stacksize;
    }SqStack;
    
    int InitStack(SqStack &S) {
    	S.base = (int*)malloc(MAXSTACKSIZE * sizeof(SqStack));
    	if (!S.base)
    	{
    		exit(OVERFLOW);
    	}
    	S.top = S.base;
    	S.stacksize = MAXSTACKSIZE;
    	return 1;
    }
    
    int Push(SqStack &S, int e) {
    	if (S.top - S.base == S.stacksize) {
    		S.base = (int *)realloc(S.base, (S.stacksize + STACKCREMENT) * sizeof(SqStack));
    		if (!S.base)
    		{
    			cout << "空间分配失败" << endl;
    			exit(OVERFLOW);
    		}
    		S.stacksize += STACKCREMENT;
    	}
    	*S.top++ = e;
    	return 1;
    }
    
    int Pop(SqStack &S, int &e) {
    	if (S.top == S.base)
    		return 0;
    	e = *--S.top;
    	return 1;
    }
    
    int DecimalismToOctal(SqStack &S, int decimalism, int &octal) {
    	int remainder;
    	int r;
    	octal = 0;
    	do{
    		remainder = decimalism % 8;
    		Push(S, remainder);
    		decimalism /= 8;
    	} while (decimalism);
    	
    	while (S.top != S.base)
    	{
    		octal *= 10;
    		Pop(S, r);
    		octal += r;
    		
    	}
    	return 1;
    }
    
    void main() {
    	SqStack S;
    	InitStack(S);
    	int decimalism_a = 160;
    	int octal_a;
    	DecimalismToOctal(S, decimalism_a, octal_a);
    
    	cout << "将十进制" << decimalism_a << "转化为八进制后的值为" << octal_a << endl;
    
    }

### 执行结果 ###

![70][]

## 3、链栈实现 ##

### 代码 ###

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct LNode {
    	int data;
    	struct LNode *next;
    }LNode,  *LinkStack;
    
    int InitStack(LinkStack &LS) {
    	LS = (LinkStack)malloc(sizeof(LNode));
    	if (!LS)
    	{
    		cout << "空间分配失败" << endl;
    		return OVERFLOW;	
    	}
    	LS->next = NULL;
    	return 1;
    }
    
    int Push(LinkStack &LS, int e) {
    	LS->data = e;
    	LinkStack p = (LinkStack)malloc(sizeof(LNode));
    	p->next = LS;
    	LS = p;
    	return 1;
    }
    
    int Pop(LinkStack &LS, int &e) {
    	if (LS->next)
    	{
    		LinkStack p = LS->next;
    		e = p->data;
    		LS->next = p->next;
    		free(p);
    		return 1;
    	}
    	return 0;
    }
    
    int DecimalismToOctal(LinkStack &LS, int decimalism, int &octal) {
    	int r;
    	octal = 0;
    	while (decimalism)
    	{
    		r = decimalism % 8;
    		decimalism /= 8;
    		Push(LS, r);
    	}
    	while (LS->next)
    	{
    		octal *= 10;
    		Pop(LS, r);
    		octal += r;
    		
    	}
    	return 1;
    }
    void main() {
    	LinkStack S;
    	InitStack(S);
    	int decimalism_a = 120;
    	int octal_a;
    	DecimalismToOctal(S, decimalism_a, octal_a);
    
    	cout << "将十进制" << decimalism_a << "转化为八进制后的值为" << octal_a << endl;
    }

### 执行结果 ###

![70 1][]

[70]: /images/20210516/0029794c2b944f3a875b0c0f5cd1f0a7.png
[70 1]: /images/20210516/a940e81bed4c42c0945f27d04804106a.png