顺序栈
数组在内存中占用一块连续的空间，也就是数组元素的内存地址是连续的。为了实现栈，一般是把数组头作为栈底，数组头部到数组尾部作为栈的增长方向，也就是用户只在数组尾部对数据进行插入和删除。
1、构建管理顺序栈信息的结构体类型，用于记录顺序栈的重要参数（栈底的地址、栈的容量、栈顶的有效下标）
2、创建一个空的顺序栈，并未记录顺序栈信息的结构体申请堆内存，并对栈底的地址、栈的容量、栈顶的有效下标进行初始化
3、根据栈的特性，新元素从栈顶入栈
4、根据栈的特性，把元素从栈顶出栈
5、对顺序栈中的元素进行遍历，由于栈的特性顺序栈需要从栈底开始向栈顶进行遍历
/********************************************************************************
*
* file name: SequenceStack
* author : [email protected]
* date : 2024/04/25
* function : 设计一个进制转换程序，使用顺序栈设计一个把十进制数转换为十六进制数
* 的接口，实现当通过键盘输入一个非负的十进制数，可以在终端输出对应的
* 十六进制数。
* note : None
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
* ****************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 指的是顺序栈中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造记录顺序栈SequenceStack各项参数(栈底地址+栈容量+栈顶元素的下标)的结构体
typedef struct SequenceStack
{
DataType_t *Bottom; // 记录栈底地址
unsigned int Size; // 记录栈容量
int Top; // 记录栈顶元素的下标
} SeqStack_t;
/*******************************************************************************
* name : SeqStack_Create
* function : 创建顺序表并对顺序栈进行初始化
* argument :
* @size :顺序栈的容量
*
* retval : 返回管理顺序栈的地址
* author : [email protected]
* date : 2024/04/25
* note : None
* ***************************************************************************/
SeqStack_t *SeqStack_Create(unsigned int size)
{
// 1.利用calloc为顺序栈的管理结构体申请一块堆内存
SeqStack_t *Manager = (SeqStack_t *)calloc(1, sizeof(SeqStack_t));
if (NULL == Manager)
{
perror("calloc memory for manager is failed");
exit(-1); // 程序异常终止
}
// 2.利用calloc为所有元素申请堆内存
Manager->Bottom = (DataType_t *)calloc(size, sizeof(DataType_t));
if (NULL == Manager->Bottom)
{
perror("calloc memory for Stack is failed");
free(Manager);
exit(-1); // 程序异常终止
}
// 3.对管理顺序栈的结构体进行初始化（元素容量 + 最后元素下标）
Manager->Size = size; // 对顺序栈中的容量进行初始化
Manager->Top = -1; // 由于顺序栈为空，则栈顶元素的下标初值为-1
return Manager;
}
/*******************************************************************************
* name : SeqStack_IsFull
* function : 判断顺序栈是否已满
* argument :
* @Maneger :
*
* retval : true and false
* author : [email protected]
* date : 2024/04/25
* note : None
* ***************************************************************************/
bool SeqStack_IsFull(SeqStack_t *Manager)
{
//判断顺序是否已满，如果已满则返回true；未满则返回false
return (Manager->Top + 1 == Manager->Size) ? true : false;
}
/*******************************************************************************
* name : SeqStack_Push
* function : 顺序栈的入栈
* argument :
* @Maneger :
* @Data :入栈的数据
* retval : true and false
* author : [email protected]
* date : 2024/04/25
* note : None
* ***************************************************************************/
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
// 1.判断顺序栈是否已满
if (SeqStack_IsFull(Manager))
{
printf("SeqStack Full is Full!\n");
return false;
}
// 2.如果顺序栈有空闲空间，则把新元素添加到顺序栈的栈顶
Manager->Bottom[++Manager->Top] = Data;
return true;
}
/*******************************************************************************
* name : SeqStack_IsEmpty
* function : 判断顺序栈是否为空
* argument :
* @Maneger :
*
* retval : true and false
* author : [email protected]
* date : 2024/04/25
* note : None
* ***************************************************************************/
// 判断顺序栈是否为空
bool SeqStack_IsEmpty(SeqStack_t *Manager)
{
//判断顺序是否为空，如果为空则返回true；不为空则返回false
return (-1 == Manager->Top) ? true : false;
}
/*******************************************************************************
* name : SeqStack_Pop
* function : 顺序栈的出栈
* argument :
* @Maneger :
*
* retval : 删除元素的值
* author : [email protected]
* date : 2024/04/25
* note : None
* ***************************************************************************/
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
DataType_t temp = 0; // 用于存储出栈元素的值
// 1.判断顺序栈是否为空
if (SeqStack_IsEmpty(Manager))
{
printf("SeqStack is Empty!\n");
return NULL;
}
// 2.由于删除了一个元素，则需要让顺序栈的栈顶元素下标-1
temp = Manager->Bottom[Manager->Top--];
return temp;
}
/***********************************************************************************
* name : SeqStack_base_conversion
* function : 设计一个进制转换程序，使用顺序栈设计一个把十进制数转换为十六进制数的接口，
* 实现当通过键盘输入一个非负的十进制数，可以在终端输出对应的十六进制数。
*
* argument :
* @Maneger :
* @Data :输入的值
* retval : None
* author : [email protected]
* date : 2024/04/25
* note : None
* *******************************************************************************/
void SeqStack_base_conversion(SeqStack_t *Manager, DataType_t num)
{
int cnt = 0; // 记录入栈的次数
int temp; // 记录出栈的元素
while (1)
{
// 判断顺序栈是否已满，如果未满则新的元素入栈，当栈满了则直接退出此循环语句
if (SeqStack_Push(Manager, num % 16))
cnt++;
else
return;
// 判断传入数据取模16是否等与本身如果等于本身则直接退出循环
if (num == num % 16)
break;
num /= 16;
}
printf("0x");
// 当循环条件不满足条件则不进入循环
while (cnt-- > 0)
{
// 把出栈的元素备份输出
temp = SeqStack_Pop(Manager);
// 当备份的数小于10则直接输出本身
if (temp < 10)
{
printf("%d", temp);
}
else // 当大于10则把自身加上55变换成大写字母
{
temp += 55;
printf("%c", temp);
}
}
printf("\n");
}
/***********************************************************************************
* name : SeqStackstr
* function : 通过键盘输入一个包括 '(' 和 ')' 的字符串string ，判断字符串是否有效。
* 要求设计算法实现检查字符串是否有效，有效的字符串需满足以下条件：
* argument :
* @Maneger :
* @str :字符串的第地址
* retval : None
* author : [email protected]
* date : 2024/04/25
* note : None
* *******************************************************************************/
void SeqStackstr(SeqStack_t *Manager, char *str)
{
// 备份栈顶元素的下标
int len = Manager->Top;
// 对字符串的元素进行辩遍历
for (int i = 0; i < sizeof(str); i++)
{
// 如果字符串的第一个元素为')'则函数直接结束
if (')' == str[0])
{
printf("Strings are invalid");
return;
}
// 如果传入的数组中有'('则进行入栈
else if ('(' == str[i])
{
SeqStack_Push(Manager, str[i]); // 入栈
}
// 如果为')'
else if (')' == str[i])
{
// 栈顶元素的下标大于一开始备份的栈顶元素的下标
if (Manager->Top > len)
{
SeqStack_Pop(Manager); // 出栈
Manager->Top--;
}
else // 如果栈顶元素下标不大于一开始备份的栈顶元素的下标则函数调用结束
{
printf("Strings are invalid");
return;
}
}
}
// 如果栈顶的元素下标与备份栈顶元素的小标相同则字符串输入正确
if (len == Manager->Top)
printf("Strings are valid");
else // 否则栈顶的元素下标与备份栈顶元素的小标相同则字符串输入不正确
printf("Strings are invalid");
}
/***********************************************************************************
* name : SeqStackstr
* function : 遍历顺序表所有元素，并输出所有元素的值
* argument :
* @Maneger :
* @str :字符串的第地址
* retval : None
* author : [email protected]
* date : 2024/04/25
* note : None
* *******************************************************************************/
void SeqStack_Print(SeqStack_t *Manager)
{
for (int i = 0; i <= Manager->Top; ++i)
{
printf(" Stack Element[%d] = %d\n", i, Manager->Bottom[i]);
}
}
int main(int argc, char const *argv[])
{
SeqStack_t *Manager = SeqStack_Create(100);
char str[100] = {0};
printf("Please input a strings :");
scanf("%s", str);
SeqStackstr(Manager, str);
SeqStack_base_conversion(Manager, 1000);
SeqStack_Print(Manager)
return 0;
}