C语言栈实现及十进制转八进制应用

本文将介绍如何使用C语言实现栈这种数据结构，并利用它来解决实际问题——将十进制数转换为八进制数。

1. 栈的定义和基本操作

栈是一种遵循**后进先出（LIFO）**原则的数据结构。我们可以把它想象成一个桶，只能从一端放入和取出元素，最后放进去的元素会最先被取出来。

下面是用C语言实现的顺序栈结构体SqStack以及其基本操作函数：c#include <stdio.h>#include <malloc.h>#include <stdlib.h>

#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2

typedef int SElemType;typedef int Status;

#define STACK_INIT_SIZE 100 #define STRCKINCREMENT 10

typedef struct { SElemType *base; // 栈底指针 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); return OK;}

// 入栈Status Push(SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (SElemType*)realloc(S.base, (S.stacksize + STRCKINCREMENT) * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STRCKINCREMENT; } *S.top++ = e; return OK;}

// 出栈Status Pop(SqStack &S, SElemType &e) { if (S.top == S.base) return ERROR; e = *--S.top; return OK; }

// 判断栈是否为空Status StackEmpty(SqStack S) { if (S.top == S.base) return TRUE; else return FALSE;}

代码解释：

SElemType 定义了栈中元素的数据类型，可以根据需要修改。- SqStack 结构体包含三个成员：base 指向栈底，top 指向栈顶，stacksize 记录栈的容量。- InitStack 函数初始化一个空栈，分配内存并设置初始容量。- GetTop 函数获取栈顶元素的值，但不改变栈结构。- Push 函数将元素 e 入栈，如果栈满则动态扩容。- Pop 函数将栈顶元素出栈，并用 e 返回其值。- StackEmpty 函数判断栈是否为空。

2. 十进制转八进制

利用栈可以方便地实现十进制到八进制的转换。算法思路如下：

输入一个十进制整数 N。2. 循环执行以下操作，直到 N 变为 0： * 计算 N 除以 8 的余数 r，将 r 入栈。 * 将 N 更新为 N 除以 8 的商。3. 循环执行以下操作，直到栈为空： * 将栈顶元素出栈，输出该元素。cvoid conversion() { SqStack S; int N; SElemType e; InitStack(S); scanf('%d', &N); while (N) { Push(S, N % 8); N = N / 8; } printf('转换成八进制后的数为:'); while (!StackEmpty(S)) { Pop(S, e); printf('%d', e); } printf(' ');}

代码解释：

函数 conversion 实现了十进制到八进制的转换。- 首先初始化一个空栈 S。- 然后读取用户输入的十进制整数 N。- 利用循环将 N 转换为八进制数，并将每一位依次入栈。- 最后再将栈中元素依次出栈并输出，即可得到转换后的八进制数。

3. 完整代码示例c#include <stdio.h>#include <malloc.h>#include <stdlib.h>

// ... (栈的定义和操作函数，与上面代码一致) ...

int main() { SqStack S; SElemType e, x; InitStack(S); Push(S, 5); Push(S, 4); Push(S, 3); Push(S, 2); Push(S, 1); GetTop(S, e); printf('栈顶元素为%d ', e); printf(' '); Pop(S, x); printf('删除的栈顶元素为%d ', x); printf(' '); printf('输入一个十进制数:'); conversion(); return 0;}

运行结果：

栈顶元素为1

删除的栈顶元素为1

输入一个十进制数:1234转换成八进制后的数为:2322

总结

本文介绍了C语言栈的实现以及如何利用栈实现十进制到八进制的转换。栈作为一种基础的数据结构，在计算机科学中有着广泛的应用。掌握栈的概念和操作方法对于学习数据结构和算法至关重要。