数据结构-栈的应用
数据结构
·
第1关：利用栈实现整数的十进制转八进制
本关必读
栈是基础的数据结构，元素操作遵循后进先出的原理。本关卡基于数组存储实现了栈的基本操作。
该方案将栈存储在一片连续空间里，并通过data、top和max三个属性元素。组织成为一个结构：
data: 给出栈存储空间的起始地址max: 指明栈存储空间最多可存储的数据元素个数top: 栈顶元素所处数组位置 为了讨论简化，我们假设每个数据元素是一个整数:typedef int T; // 数据元素的数据类型
struct Stack{T* data; // 数据元素存储空间的开始地址int top; // 栈顶元素所处数组位置int max; // 栈存储空间最多可存储的数据元素个数};
Stack指针对象，就可对栈表进行操作。
对数据元素进行操作处理是一个数据结构的重要组成部分。栈涉及的主要操作如下：
- 创建栈：创建一个最多可存储
max个数据元素的顺序存储的栈，初始状态设置为top=-1。该操作函数具体定义如下，其返回值为Stack指针：Stack* Stack_Create(int max) - 释放栈存储空间：释放
stk->data所指向的用于存储栈数据元素的存储空间。该操作函数具体定义如下：void Stack_Free(Stack* stk) - 置空栈：将当前栈变为一个空栈，实现方法是将
stk->top设置为-1。该操作函数具体定义如下：void Stack_MakeEmpty(Stack* stk) - 判断栈是否为空：若当前栈是空栈，则返回
true,否则返回false。该操作函数具体定义如下：bool Stack_IsEmpty(Stack* stk) - 判断栈空间是否为满：若栈顶达到最大长度，则返回
true,否则返回false。该操作函数具体定义如下：bool Stack_IsFull(Stack* stk) - 返回栈顶元素：返回栈顶元素
stk->data[stk->top]。该操作函数具体定义如下：T Stack_Top(Stack* stk) - 将元素进栈： 将元素
e压入栈顶。若栈满压入失败，返回异常，否则返回栈顶元素。该操作函数具体定义如下T Stack_Push(Stack* stk, T e) - 将元素出栈： 将栈顶元素出栈。若栈空出栈失败，返回异常，否则返回栈顶元素。该操作函数具体定义如下
T Stack_Pop(Stack* stk)
任务描述
本关任务：基于栈stack数据结构解决整数十进制转八进制的问题。
相关知识
为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作，3.进制转换。
创建栈
本例已基于数组存储结构实现了栈的创建，通过调用Stack* Stack_Create(int max)创建一个栈实例。
Stack *stk = Stack_Create(32);//创建一个栈实例
入栈和出栈操作
示例如下：
T e = 2018;Stack_Push(stk, e);//入栈e = Stack_Pop(stk);//出栈
进制转换
除K取余法，例如十进制数10转二进制：
上图可得：K=2，1010=10102 即：10=1×23+0×22+1×21+0×20
编程要求
本关的编程任务是补全右侧代码片段Decimal_Conversion_Octal中Begin至End中间的代码，具体要求如下：
- 在
Decimal_Conversion_Octal中，利用栈stack的基本操作实现整数的十进制转八进制，并输出八进制结果，末尾换行。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
样例一： 测试输入：71 预期输出：107
样例二： 测试输入：8 预期输出：10
开始你的任务吧，祝你成功！
//
// stack_.cpp
// Stack
//
// Created by ljpc on 2018/4/17.
// Copyright © 2018年 ljpc. All rights reserved.
//
#include "stack_.h"
// 栈操作实现文件
//
Stack* Stack_Create(int maxlen)
// 创建栈
{
Stack* stk = (Stack*)malloc(sizeof(Stack));
stk->data = (T*)malloc(sizeof(T)*maxlen);
stk->max = maxlen;
stk->top = -1;
return stk;
}
void Stack_Free(Stack* stk)
// 释放栈
{
free(stk->data);
free(stk);
}
void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
stk->top = -1;
}
bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
return -1 == stk->top;
}
bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
return stk->top == stk->max-1;
}
T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
return stk->data[stk->top];
}
T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
if(Stack_IsFull(stk)) {
printf("Stack_IsFull(): stack full error when push element to the stack!\n");
Stack_Free(stk);
exit(0);
}
else{
stk->top += 1;
stk->data[stk->top] = e;
return Stack_Top(stk);
}
}
T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
if(Stack_IsEmpty(stk)) {
printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
Stack_Free(stk);
exit(0);
}
else{
T topE = Stack_Top(stk);
stk->top -= 1;
return topE;
}
}
void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
if (Stack_IsEmpty(stk)) {
printf("The stack is empty.\n");
return;
}
//printf("The stack contains: ");
for (int i=stk->top; i>=0; i--) {
printf("%d", stk->data[i]);
}
printf("\n");
}
void Decimal_Conversion_Octal(T e)
// 利用stack栈实现整数的十进制转八进制
// 输入参数：十进制整数 e
// 打印e的八进制结果，末尾换行
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
Stack *stk = Stack_Create(100);
int x;
int i=0;
while(e>=8){
x=e%8;
i++;
Stack_Push(stk,x);
e=e/8;
}
Stack_Push(stk,e);
for(int j=0;j<=i;j++){
int a = Stack_Pop(stk);
printf("%d",a);
}
free(stk);
printf("\n");
/********** End **********/
}
第2关：利用栈判断字符串括号是否匹配
任务描述
本关任务：基于栈stack数据结构判断字符串中的括号是否匹配，字符串中仅包含如下字符：( ) [ ] { }。
相关知识
为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作。
- 创建栈、入栈和出栈操作请参考
第1关。
编程要求
本关的编程任务是补全右侧代码片段Bracket_Match中Begin至End中间的代码，具体要求如下：
- 在
Bracket_Match中，利用栈stack判断括号是否匹配， 若匹配输出YES，否则输出NO，末尾换行。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
样例一： 测试输入： 6 {[()]} 预期输出： YES
样例二： 测试输入： 4 [(]) 预期输出： NO
开始你的任务吧，祝你成功！
//
// stack_.cpp
// Bracket_Match
//
// Created by ljpc on 2018/4/18.
// Copyright © 2018年 ljpc. All rights reserved.
//
#include "stack_.h"
// 栈表操作实现文件
//
Stack* Stack_Create(int maxlen)
// 创建栈
{
Stack* stk = (Stack*)malloc(sizeof(Stack));
stk->data = (T*)malloc(sizeof(T)*maxlen);
stk->max = maxlen;
stk->top = -1;
return stk;
}
void Stack_Free(Stack* stk)
// 释放栈
{
free(stk->data);
free(stk);
}
void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
stk->top = -1;
}
bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
return -1 == stk->top;
}
bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
return stk->top == stk->max-1;
}
T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
return stk->data[stk->top];
}
T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
if(Stack_IsFull(stk)) {
printf("Stack_IsFull(): stack full error when push element to the stack!\n");
Stack_Free(stk);
exit(0);
}
else{
stk->top += 1;
stk->data[stk->top] = e;
return Stack_Top(stk);
}
}
T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
if(Stack_IsEmpty(stk)) {
printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
Stack_Free(stk);
exit(0);
}
else{
T topE = Stack_Top(stk);
stk->top -= 1;
return topE;
}
}
void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
if (Stack_IsEmpty(stk)) {
printf("The stack is empty.\n");
return;
}
//printf("The stack contains: ");
for (int i=stk->top; i>=0; i--) {
printf("%d", stk->data[i]);
}
printf("\n");
}
void Bracket_Match(T* str, int len)
// 利用stack栈判断括号是否匹配
// 输入参数：字符串序列，字符串长度
// 若匹配输出YES，否则输出NO，末尾换行
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
Stack *s = Stack_Create(200);
for (int i=0; i<len; i++) {
if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
Stack_Push(s, str[i]);
}
else{
if(Stack_Top(s)=='(' && str[i]==')'){
Stack_Pop(s);
}
else
if(Stack_Top(s)=='[' && str[i]==']')
{
Stack_Pop(s);
}
else
if(Stack_Top(s)=='{' && str[i]=='}')
{
Stack_Pop(s);
}
else{
printf("NO\n");
return;
}
}
}
if(Stack_IsEmpty(s)){
printf("YES\n");
}
else{
printf("NO\n");
}
/********** End **********/
}
第3关：利用栈判断字符串是否为回文串
任务描述
本关任务：基于栈stack数据结构判断字符串是否为“回文串”。
相关知识
为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作，3.“回文串”概念。
- 创建栈、入栈和出栈操作请参考
第1关
回文串
简单来说，“回文串”是一个正读和反读都一样的字符串： noon是回文串 moon不是回文串
编程要求
本关的编程任务是补全右侧代码片段Palindrome中Begin至End中间的代码，具体要求如下：
- 在
Palindrome中，利用栈stack判断字符串是否为回文串， 若是回文串输出YES，否则输出NO，末尾换行。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
样例一： 测试输入： 4 1221 预期输出： YES
样例二： 测试输入： 7 abababa 预期输出： YES
开始你的任务吧，祝你成功！
//
// stack_.cpp
// Palindrome
//
// Created by ljpc on 2018/4/18.
// Copyright © 2018年 ljpc. All rights reserved.
//
#include "stack_.h"
// 栈表操作实现文件
//
Stack* Stack_Create(int maxlen)
// 创建栈
{
Stack* stk = (Stack*)malloc(sizeof(Stack));
stk->data = (T*)malloc(sizeof(T)*maxlen);
stk->max = maxlen;
stk->top = -1;
return stk;
}
void Stack_Free(Stack* stk)
// 释放栈
{
free(stk->data);
free(stk);
}
void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
stk->top = -1;
}
bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
return -1 == stk->top;
}
bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
return stk->top == stk->max-1;
}
T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
return stk->data[stk->top];
}
T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
if(Stack_IsFull(stk)) {
printf("Stack_IsFull(): stack full error when push element to the stack!\n");
Stack_Free(stk);
exit(0);
}
else{
stk->top += 1;
stk->data[stk->top] = e;
return Stack_Top(stk);
}
}
T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
if(Stack_IsEmpty(stk)) {
printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
Stack_Free(stk);
exit(0);
}
else{
T topE = Stack_Top(stk);
stk->top -= 1;
return topE;
}
}
void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
if (Stack_IsEmpty(stk)) {
printf("The stack is empty.\n");
return;
}
//printf("The stack contains: ");
for (int i=stk->top; i>=0; i--) {
printf("%d", stk->data[i]);
}
printf("\n");
}
void Palindrome(T* str, int len)
// 利用stack栈判断字符串是否为回文串
// 输入参数：字符串序列，字符串长度
// 若是回文串输出YES，否则输出NO，末尾换行
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
Stack *st = Stack_Create(200);
for (int i=0; i<len/2; i++) {
Stack_Push(st, str[i]);
}
int j = (len&1)?(len/2+1):(len/2);
for (int i=j; i<len; i++) {
if(str[i]!=Stack_Top(st)){
printf("NO\n");
return;
}else{
Stack_Pop(st);
}
}
printf("YES\n");
/********** End **********/
}
第4关：栈之巩固练习
任务描述
根据栈的相关知识以及前面关卡的内容完成相关选择题。
开始你的任务吧，祝你成功！
-
1、
以下哪些项是栈元素操作的基本特点：（BC）
A、先进先出
B、先进后出
C、后进先出
D、后进后出 -
2、
利用栈实现十进制整数
1234转八进制，以下哪项栈表状态符合实际情况： (B) -
A、 A
D、 D - B、 B
C、 C -
3、
若已知一个栈的入栈顺序是A、B、C、D，其出栈序列为P1、P2、P3、P4，则P2、P4不可能是（C）
A、 B、D
B、 C、A
C、 D、C
D、 C、D
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
21
0- 0
已为社区贡献4条内容
所有评论(0)