我们通常所说的线性表是一种位置或元素内容没有限制的数据结构。在某些特定场景下，限制操作或元素是很有必要的，如下图所示：
具体到现实世界中的应用，不同类型的容器有不同的使用场景。普通的顺序表就像一个开架，你可以随意放置物品，也可以在任意位置插入或移除。而队列像排队，新的元素只能加入队列尾部，排在最前面的是最先离开的，不能插队。栈就像一个只有一个开口的容器，取出时只能取出最后放进去的元素。
栈（stack）是一种后进先出（LIFO）的线性表，栈规定只能在一端进行插入和删除操作。栈通常采用顺序存储，也可以使用链表存储。
编写一个程序，使用栈结构实现一个二进制到八进制的转换器，二进制和八进制数均可使用字符串表示。
进制转换常通过栈实现，这与数据流的输入方式密切相关。输入一串0\1字符，首先输入的字符处于二进制数的高位，后输入的字符处于低位。转换为八进制时，必须从低位开始每三位0\1字符转换成一个八进制数，使用栈可以方便地实现这一操作。具体步骤如下：
I 输入表示二进制的0\1字符串，将每次输入的0\1字符放入栈s1中保存。进栈顺序使得二进制数的最高位在栈底，最低位在栈顶；
II 从栈s1中每取出三位0\1字符串，将其转换成对应的八进制数，并用字符表示。先得到的是八进制数的低位，因此将该八进制数保存在新栈s2中，直到s1中的元素全部取出。这样八进制数的高位位于s2的栈顶，低位位于栈底；
III 将s2中的字符逐一取出并显示，就得到原二进制数对应的八进制表示。
代码：
运行效果：
运算过程图解如下：
上述要转换的二进制数1011101，首先将高位放入s1的栈底，低位依次放入。转换后低位放入s2的栈底，高位放入栈顶。取出输出时，s2的栈顶先取出高位，这正好与我们的习惯排列方式一致，即135。
附源码：
#include "stdio.h"
#include "math.h"
#include "malloc.h"
#define STACK_INIT_SIZE 30
#define STACKINCREMENT 10
typedef struct{
char *base;
char *top;
int stacksize;
}sqStack;
int initStack(sqStack *s)
{
/*内存中开辟一段连续空间作为栈空间，首地址赋值给s->base*/
s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!s->base) return 0;/*分配空间失败*/
s->top = s->base;/*最初时，栈顶即栈底*/
s->stacksize = STACK_INIT_SIZE;/*最大容量为STACK_INIT_SIZE */
return 1;
}
int Push(sqStack *s, char e){
if(s->top - s->base >= s->stacksize){/*栈满，追加空间*/
s->base = (char *)realloc(s->base, (s->stacksize +
STACKINCREMENT)*sizeof(char));
if(!s->base) return 0;/*存储分配失败*/
s->top = s->base + s->stacksize;
s->stacksize = s->stacksize + STACKINCREMENT;/*设置栈的最大容量*/
}
*(s->top) = e;/*放入数据*/
s->top++;
return 1;
}
int Pop(sqStack *s , char *e){
if(s->top == s->base) return 0;
*e = *--(s->top);
return 1;
}
void Bi2Oct()
{
sqStack s1;
sqStack s2;
char c;
int i,sum=0;
initStack(&s1);/*创建一个栈s1，用于存放二进制字符串*/
scanf("%c",&c);/*输入0/1字符表示的二进制数，以#结束*/
while(c!='#')
{
if(c=='0' || c=='1')
Push(&s1,c);
scanf("%c",&c);
}
initStack(&s2);/*创建一个栈s2，用于存放八进制字符串*/
while(s1.top!=s1.base)
{
for(i=0;i<3 && s1.top!=s1.base;i++)
{
Pop(&s1,&c);/*取出栈顶元素*/
sum = sum + (c-48) * pow(2,i);/*转换为八进制数*/
//数字0-9在ASCII中是48-57号字符
}
Push(&s2,sum+48) ;/*将八进制数以字符形式压入栈中*/
sum = 0;
}
while(s2.base != s2.top ){/*输出八进制栈的内容*/
Pop(&s2,&c);
printf("%c",c);
}
}
main()
{
printf("Please input a binary number to convert to octal number，ended by '#'\n");
Bi2Oct();
getchar();
getchar();
}
－End－
文章为用户上传，仅供非商业浏览。发布者：Lomu，转转请注明出处： https://www.daogebangong.com/articles/detail/shu-ju-jie-gou-zhan-yu-jin-zhi-zhuan-huan-qi.html
支付宝扫一扫 
评论列表（196条）
测试