福永网站设计,网站建设必须要在阿里云备案吗,WordPress自动推送到公众号,长沙有哪些网站建设公司好前言
这个专栏将会用纯C实现常用的数据结构和简单的算法#xff1b;有C基础即可跟着学习#xff0c;代码均可运行#xff1b;准备考研的也可跟着写#xff0c;个人感觉#xff0c;如果时间充裕#xff0c;手写一遍比看书、刷题管用很多#xff0c;这也是本人采用纯C语言…前言
这个专栏将会用纯C实现常用的数据结构和简单的算法有C基础即可跟着学习代码均可运行准备考研的也可跟着写个人感觉如果时间充裕手写一遍比看书、刷题管用很多这也是本人采用纯C语言实现的原因之一欢迎收藏 关注本人将会持续更新。 文章目录 什么是栈栈的代码实现数组栈链式栈 栈的应用求和存储数据的二进制表达式求值详解中缀表达式后缀表达式中缀转后缀 什么是栈
栈是一种运算受限的线性表它限定只能在表的一端进行插入和删除操作。
栈0的结构特性是后进先出LIFO ( Last In First Out)。栈又被称为后进先出表。
两个重要概念
栈顶:允许插入和删除的一端称作栈顶
栈底:不允许插入和删除的一端称作栈底。 数组栈结构如下 其中
栈底元素a1 栈顶元素an 入栈顺序a1, a2, …, an 依次入栈;出栈顺序an, an-1, …, a1先入的后出 只能在栈顶进行插入和删除。 链式栈结构 链式栈原理就是头插入、头删除。
栈的代码实现
ADT抽象操作
创建栈入栈出栈获取栈顶元素栈是否为空栈元素个数
数组栈
解释用数组模拟栈。 栈封装
封装元素
数据数组当前能存储的最大大小(容量)栈顶游标
typedef struct Stack {DataType* data;size_t maxSize; // int top;
}Stack;创建栈与栈初始化
这个步骤目标创建栈并且初始化栈变量
栈顶初始化-1入栈top出战top--
Stack* create_stack()
{Stack* stack (Stack*)calloc(1, sizeof(Stack));assert(stack);stack-top -1; // 栈顶初始值为 -1return stack;
}入栈
操作就是数组向后添加元素
注意就是扩容操作这里不够就**10**
void push(Stack* stack, DataType data)
{assert(stack);// 扩容if (stack-top stack-maxSize - 1) {DataType* temp (DataType*)realloc(stack-data, (stack-maxSize 10) * sizeof(DataType));assert(temp);stack-maxSize 10;stack-data temp;}stack-data[stack-top] data;
}获取栈顶元素和出栈
获取栈顶获取数组下标为top元素
出栈top减1
DataType top(Stack* stack)
{assert(stack);return stack-data[stack-top];
}void pop(Stack* stack)
{assert(stack);stack-top--;
}万金油函数
获取栈大小栈是否为空
这两个操作没什么难度看代码即可
bool empty(Stack* stack)
{assert(stack);return stack-top -1;
}size_t size(Stack* stack)
{assert(stack);return stack-top 1;
}⚗️ 总代码
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int DataType;typedef struct Stack {DataType* data;size_t maxSize;int top;
}Stack;Stack* create_stack()
{Stack* stack (Stack*)calloc(1, sizeof(Stack));assert(stack);stack-top -1; // 栈顶初始值为 -1return stack;
}void push(Stack* stack, DataType data)
{assert(stack);// 扩容if (stack-top stack-maxSize - 1) {DataType* temp (DataType*)realloc(stack-data, (stack-maxSize 10) * sizeof(DataType));assert(temp);stack-maxSize 10;stack-data temp;}stack-data[stack-top] data;
}DataType top(Stack* stack)
{assert(stack);return stack-data[stack-top];
}void pop(Stack* stack)
{assert(stack);stack-top--;
}bool empty(Stack* stack)
{assert(stack);return stack-top -1;
}size_t size(Stack* stack)
{assert(stack);return stack-top 1;
}int main()
{Stack* stack create_stack();for (int i 1; i 10; i) {push(stack, i);}printf(size: %llu\n, size(stack));while (!empty(stack)) {printf(%d , top(stack));pop(stack);}putchar(\n);printf(size: %llu\n, size(stack));return 0;
}链式栈 实现方式采用无头链表 模拟采用链表的头插和弹出头来模拟入栈和出栈操作。 栈封装
节点封装
存储元素、指针指向下一个节点
链表封装
采用在封装写法创建一个指针指向头节点同时定义size存储当前栈的大小是这个在封装写法的核心。 为什么说size是核心变量图示如下
typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;typedef struct Stack {Node* headNode;int size;
}Stack;封装创建节点和创建栈函数
Node* create_node(DataType data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;return node;
}Stack* create_stack()
{Stack* stack (Stack*)calloc(1, sizeof(Stack));assert(stack);return stack;
}元素入栈
在封装写法的核心是变量size当size0的时候说明这个时候是链表为空这个时候插入就是创建头节点其他情况就是正常头插这样引入变量也可以避免指针指向被修改的问题不需要采用二级指针。
图
// 头插
void push(Stack* stack, DataType data)
{assert(stack);Node* newNode create_node(data);if (stack-size 0) {stack-headNode newNode;}else {newNode-next stack-headNode;stack-headNode newNode;}stack-size;
}出栈和获取栈顶元素
获取栈顶就是获取头节点元素过程
出战删除头节点要注意的就是栈为空的情况。
图示
DataType top(Stack* stack)
{assert(stack);assert(stack-headNode);return stack-headNode-data;
}void pop(Stack* stack)
{assert(stack);if (stack-size 0) {return;}else {Node* temp stack-headNode;stack-headNode stack-headNode-next;free(temp);temp NULL;}stack-size--;}万金油函数
采用在封装写法对获取元素和判断是否为空有着天然的优势代码如下
bool empty(Stack* stack)
{assert(stack);return stack-size 0;
}int size(Stack* stack)
{assert(stack);return stack-size;
}总代码
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h// 采用无头链表实现typedef int DataType;typedef struct Node {DataType data;struct Node* next;
}Node;typedef struct Stack {Node* headNode;int size;
}Stack;Node* create_node(DataType data)
{Node* node (Node*)calloc(1, sizeof(Node));assert(node);node-data data;return node;
}Stack* create_stack()
{Stack* stack (Stack*)calloc(1, sizeof(Stack));assert(stack);return stack;
}// 头插
void push(Stack* stack, DataType data)
{assert(stack);Node* newNode create_node(data);if (stack-size 0) {stack-headNode newNode;}else {newNode-next stack-headNode;stack-headNode newNode;}stack-size;
}DataType top(Stack* stack)
{assert(stack);assert(stack-headNode);return stack-headNode-data;
}void pop(Stack* stack)
{assert(stack);if (stack-size 0) {return;}else {Node* temp stack-headNode;stack-headNode stack-headNode-next;free(temp);temp NULL;}stack-size--;}bool empty(Stack* stack)
{assert(stack);return stack-size 0;
}int size(Stack* stack)
{assert(stack);return stack-size;
}int main()
{Stack* stack create_stack();for (int i 1; i 10; i) {push(stack, i);}while (!empty(stack)) {printf(%d , top(stack));pop(stack);}return 0;
}栈的应用
其实在开发中用栈要不用封装好容器要么用数组模拟不会像上面那种方式手写。
求和存储数据的二进制
要求求一个数的二进制
// 一般栈开发中都有容器直接调用哪怕是C语言也是简单的模拟如下
void test_stack()
{// 用栈存储并打印 666 的二进制int stack[1024] { 0 }; // 数组模拟栈int top -1; // 定义栈顶int num 666;int t num;while (t) {stack[top] ((t 1) 1) ? 1 : 0; // 入栈t 1;}// 输出和弹出栈顶while (top ! -1) {printf(%d, stack[top--]); // 获取栈顶与出栈}
}表达式求值详解
中缀表达式
我们把平时所用的标准四则运算表达式即“9(3-1)×310÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间。
后缀表达式
后缀表达式也叫作逆波兰表达式对于“9(3-1)×310÷2”如果要用后缀表示法应该是什么样子“9 3 1-3*10 2/”这样的表达式称为后缀表达式叫后缀的原因在于所有的符号都是在要运算数字的后面出现。后缀表达式如何求解表达式的值
遍历后缀表达式如果遇到数字则直接入栈如果遇到操作符则弹出栈顶的两个元素进行计算后将结果入栈。最终栈内剩余的元素就是整个表达式的计算结果。 中缀转后缀
操作流程
如果栈顶元素的优先级大于等于当前操作符则先将栈顶元素弹出并输出到后缀表达式中再将当前操作符压入栈中。如果遇到了左括号则直接将其压入栈中如果遇到了右括号则弹出栈中的元素直到遇到了左括号为止并将这些元素输出到后缀表达式中。最后将栈中剩余的元素依次弹出并输出到后缀表达式中。 ⏰ 代码实现
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h/*
* 中缀a b * (c d) / e - f
* 后缀a b c d * e / f -
*/#define MAX_SIZE 2014
char stack[MAX_SIZE]; // 定义栈
int top -1;bool isdigits(char figure)
{return ((figure - 0 0) (figure - 0 9));
}bool is_operator(char op)
{return op || op - || op * || op /;
}int pri_operator(char key)
{switch (key){case :case -:return 1;case *:case /:return 2;}return 0;
}void midToLast(char* p, char* q)
{assert(p);assert(q);while (*p ! \0) {// 是数字 25543if (isdigits(*p)) { // 是数字while (isdigits(*p) || *p .) {*q *p;p;q;}// 加空格输出好看好一点*q ;q;}else if (is_operator(*p)) { // 运算符if (top -1) { // 栈空stack[top] *p;p;}else if (pri_operator(stack[top]) pri_operator(*p)) { // 栈顶符号 优先即大于等于 当先运算符while (top ! -1 is_operator(stack[top])) { // 弹出*q stack[top--]; q;// 加空格输出好看好一点*q ;q;}}else {stack[top] *p;p;}}else if (*p () {stack[top] *p;p;}else if (*p )) {while (top ! -1 stack[top] ! () {*q stack[top--];q;// 加空格输出好看好一点*q ;q;}if (top ! -1) { // 不是-1就是左括号top--;}p;}}// 剩余运算while (top ! -1) {*q stack[top--];q;// 加空格输出好看好一点*q ;q;}*q \0;
}int main()
{// 10 33 22 - 10 * 12 4 / 0.25 char midExpression[MAX_SIZE] { 10(33-32)*1012/40.25 };char lastExpression[MAX_SIZE * 2] ;midToLast(midExpression, lastExpression);printf(%s\n, lastExpression);return 0;
}/*输出
10 33 32 - 10 * 12 4 / 0.25 输出
*/
