数据结构(C语言)栈的创建、入栈、出栈并进行进制转换
十进制数转换为八进制:
| N |N div 8(商) | N mod 8(余数)
|1348| 168 | 4
| 168 | 21 | 0
| 21 | 2 | 5
| 2 | 0 | 2
上述计算过程中是从低位到高位产生八进制数的各个数位,而打印输出应从高位到低位进行,因此若将计算过程中得到的八进制数顺序进栈,则按出栈顺序打印输出的即为最终的八进制数。
top=base记为栈空的标记,每当插入新的元素,则将指针top+1,非空栈的栈顶元素始终在栈顶元素的下一个位置。
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREATE 10
#define SElemType int
typedef int Status;
typedef struct {
SElemType *base;
SElemType *top;//栈顶指针
int stacksize;//已分配的存储空间
}SqStack;
Status InitStack(SqStack &s);
Status ClearStack(SqStack &s);
int StackLength(SqStack s);
Status GetTop(SqStack s,SElemType &e);
Status Push(SqStack &s, SElemType e);
Status Pop(SqStack &s, SElemType &e);
Status InitStack(SqStack &s)//初始化栈
{
s.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));//分配地址,能够容纳100个元素
if (!s.base)exit(-2);
s.top = s.base;//使栈顶等于栈底
s.stacksize = STACK_INIT_SIZE;//存储空间
return 1;
}
Status GetTop(SqStack s,SElemType &e)//若栈不空,则用e返回s的栈顶元素,并返回OK
{
if (s.top == s.base)//栈为空
{
return 0;
}
e = *(s.top - 1);//取得栈顶元素
}
Status Push(SqStack &s, SElemType e)//插入元素e为新的栈顶元素
{
if (s.top - s.base >= STACK_INIT_SIZE)//若栈满则追加存储空间
{
s.base = (SElemType *)realloc(s.base, (s.stacksize + STACKINCREATE * sizeof(SElemType)));
if (!s.base)
{
exit(-2);
}
s.top = s.base + s.stacksize;//s.base基地址更改,所以top指针要随之更改
s.stacksize += STACKINCREATE;
}
*s.top++ = e;//先将e的值赋给栈顶指针,再加1
return 1;
}
Status Pop(SqStack &s,SElemType &e)//出栈
{
if (s.top == s.base) return 0;//空栈
e = *--s.top;//由于栈顶指针始终指向栈顶元素的下一个位置,所以要先将栈顶指针减1,再赋值给e
return 1;
}
int StackLength(SqStack s)
{
return s.top-s.base;
}
Status ClearStack(SqStack &s)//将栈制空
{
s.base = s.top;
return 1;
}
int main()
{
int N = 0;
SqStack s;
InitStack(s);//初始化栈
scanf_s("%d", &N);
while (N)
{
Push(s, N % 8);//将元素入栈
N = N / 8;
}
SElemType e;
while (StackLength(s))
{
Pop(s, e);//出栈
printf("%d", e);
}
system("pause");
}