汕头网站建设工作,安阳市建设工程领域网站,中企动力企业邮箱app,网站免费制作平台数据结构《栈》 1、栈的概念及结构2、栈的实现3、练习: 1、栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO… 数据结构《栈》 1、栈的概念及结构2、栈的实现3、练习: 1、栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 2、栈的实现 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。 进栈、出栈展示 实现栈最好声明与定义分开成俩个文件来处理头文件,h介绍接口实现文件.c(实现接口功能) 1、头文件.h
#includestdio.h
#includeassert.h
#includestdbool.h
#includestdlib.htypedef int type;
#define N 10;
//静态栈不常用所以我们要实现的是动态栈
typedef struct Stack
{type arr[N];int top;//栈顶
}Stack;//动态栈
typedef struct Stack
{type* a;int top;int capacity;
}sl;// 初始化栈
void Slint(sl* p);
// 入栈
void pushpop(sl* p, type x);
// 出栈
void STpop(sl* p);
// 获取栈顶元素
type STTop(sl* p);
// 获取栈中有效元素个数
int STsize(sl* p);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool empty(sl* p);
// 销毁栈
void destroy(sl* p);
实现文件.c
void Slint(sl* p)
{assert(p);p-a NULL;p-capacity 0;p-top 0;
}void pushpop(sl* p, type x)
{assert(p);if (p-top p-capacity){int newcapacity p-capacity 0 ? sizeof(type) : 2 * p-capacity;type* new (type*)realloc(p-a, sizeof(type) * newcapacity);if (new NULL){perror(realloc fail);return;}p-a new;p-capacity newcapacity;}p-a[p-top] x;p-top;}void STpop(sl* p)
{assert(p);p-top--;
}type STTop(sl* p)
{assert(p);assert(p-top 0);return p-a[p-top - 1];
}bool empty(sl* p)
{assert(p);return p-top 0;
}void destroy(sl* p)
{free(p-a);p-a NULL;p-capacity 0;p-top 0;
}int STsize(sl* p)
{assert(p);return p-top;
}3、练习:
括号匹配问题
第一步-实现一个栈在用栈的后进先出特性来匹配括号。 情况1如果为‘(’、‘[’、‘{’。左括号入栈
情况2如果为‘’‘}’‘]’右括号与栈顶匹配
//实现一个栈
typedef char type;typedef struct Stack
{type* a;int top;int capacity;
}sl;void Slint(sl* p);void destroy(sl* p);void pushpop(sl* p, type x);void STpop(sl* p);type STTop(sl* p);bool empty(sl* p);int STsize(sl* p);void Slint(sl* p)
{assert(p);p-a NULL;p-capacity 0;p-top 0;
}void pushpop(sl* p, type x)
{assert(p);if (p-top p-capacity){int newcapacity p-capacity 0 ? sizeof(type) : 2 * p-capacity;type* new (type*)realloc(p-a, sizeof(type) * newcapacity);if (new NULL){perror(realloc fail);return;}p-a new;p-capacity newcapacity;}p-a[p-top] x;p-top;}void STpop(sl* p)
{assert(p);p-top--;
}type STTop(sl* p)
{assert(p);assert(p-top 0);return p-a[p-top - 1];
}bool empty(sl* p)
{assert(p);return p-top 0;
}void destroy(sl* p)
{free(p-a);p-a NULL;p-capacity 0;p-top 0;
}int STsize(sl* p)
{assert(p);return p-top;
}
//匹配括号
bool isValid(char* s) {sl s3;Slint(s3);while (*s){if (*s ( || *s { || *s [)//情况1{pushpop(s3, *s);}else//情况2{if(empty(s3)){return false;}char top STTop(s3);STpop(s3);if ((top ( *s ! )) || (top [ *s ! ]) || (top { *s ! })){return false;}}s;}bool retempty(s3);//判断栈有没有数据destroy(s3);return ret ;}
}
