/*
	实验3：输入一组整型元素序列，建立一个链栈，
	实现该链栈的入栈和出栈操作，并实现10进制到2进制的转化。
*/
#include<stdio.h> 
#include<stdlib.h>  


#define STACK_INIT_SIZE 100    //存储空间初始分配量
#define STACKINCREMENT 10      //存储空间分配增量

typedef int SElemType;
typedef int Status;

#define OVERFLOW 0 
#define OK 1 
#define ERROR 0  
 
typedef struct {  
	SElemType *base;   //在栈构造之前和销毁之后，base的值为NULL
	SElemType *top;    //栈顶指针
	int stacksize;     //当前已分配的存储空间，以元素为单位
}SqStack; 

//构造一个空栈
Status InitStack(SqStack &S) { 
	S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));  
	if(!S.base)   exit(OVERFLOW); //存储分配失败
	S.top = S.base;  
	S.stacksize = STACK_INIT_SIZE;  
	return OK; 
}

//获得栈顶元素
Status GetTop(SqStack S,SElemType &e) { 
	if(S.top==S.base)  //判断栈是否为空
		return ERROR;  
	e = *(S.top-1);    //用e返回S栈顶元素，并返回OK。 
	return OK; 
}

//进栈
Status Push(SqStack &S,SElemType e) {  //插入元素e为栈顶元素
	if(S.top-S.base >= S.stacksize)  {  //如果栈满,追加存储空间  
		S.base=(SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof (SElemType));   
		if(!S.base)    exit(OVERFLOW); //如果存储空间分配失败，退出
		S.top = S.base + S.stacksize;   
		S.stacksize += STACKINCREMENT;  
	}  
	*S.top++ = e;  
	return OK; 
 }

//出栈
Status Pop(SqStack &S,SElemType &e){ 
	if(S.top==S.base)  //判断栈是否为空，用e返回出栈的值
		return ERROR; 
	e = *--S.top;  
	return OK; 
}

//进制转换
void conversion(int N,int i) { 
	SqStack S;  
	int e;  
	InitStack(S);        //构造空栈
	while(N)  {  
		Push(S,N % i);    //入栈
		N = N / i;  
	}   
	while(S.top != S.base) {   //如果栈不为空 
		Pop(S,e);			   //出栈 		
		if(e<10){
			printf("%d",e);  
		}else{
			printf("%d",e+55);  
		}	
	} 
	printf("\n"); 
} 
void main() { 
	int menu,i;
	int N;
	do{
		printf("*********** Menu ******************\n"); 
		printf("\n");
		printf("\n");
		printf("	1.使用栈进行数制的转换;\n");
		printf("	2.退出;\n");
		printf("\n");
		printf("\n");
		printf("********** Author: ZMH ************\n");
		scanf("%d",&menu);
		switch(menu){
			case 1:
					do{
						printf("请选择你所要转换的进制\n");
						printf("\n");
						printf("1.十进制转换为二进制\t");
						printf("2.十进制转换为八进制\t");
						printf("3.退出");
						printf("\n");
						scanf("%d",&i);
						switch(i){
						case 1:printf("请任意输入一个非负十进制整数:");
							scanf("%d",&N);
							printf("\n");
							printf("十进制数%d转换为二进制为:",N); 
							conversion(N,2);
							printf("\n");
							break;
						case 2:
							printf("请任意输入一个非负十进制整数:");
							scanf("%d",&N);
							printf("\n");
							printf("十进制数%d转换为八进制为:",8);
							printf("\n");
							break;
						case 3:exit(0);
						}
					}while(i);
		}
	}while(menu);
} 

By Mr.Z