数据结构

2024-07-10 22:03| 来源: 网络整理| 查看: 265

第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

【本文地址】

公司简介

联系我们