数据结构之_栈的顺序存储和链式存储的代码实现
1.栈的基本概念
- 概念：
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
- 特性
它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
- 操作
- 栈的插入操作，叫做进栈，也成压栈。类似子弹入弹夹（如下图所示）
- 栈的删除操作，叫做出栈，也有的叫做弾栈，退栈。如同弹夹中的子弹出夹（如下图所示）
- 创建栈
- 销毁栈
- 清空栈
- 进栈
- 出栈
- 获取栈顶元素
- 获取栈的大小
栈的抽象数据类型
ADT 栈（stack）
Data
通线性表。元素具有相同的类型，相邻的元素具有前驱和后继关系。
Operation
// 初始化，建立一个空栈S
InitStack(*S);
// 若栈存在，则销毁它
DestroyStack(*S);
// 将栈清空
ClearStack(*S);
// 若栈为空则返回true，否则返回false
StackEmpty(S);
// 若栈存在且非空，用e返回S的栈顶元素
GetTop(S，*e);
// 若栈S存在，插入新元素e到栈S中并成为其栈顶元素
Push(*S，e);
// 删除栈S中的栈顶元素，并用e返回其值
Pop（*S, *e）;
// 返回栈S的元素个数
StackLength(S);
endADT
2.栈的顺序存储代码实现
- 基本概念
栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top只是栈顶元素在顺序表中的位置。
- 设计与实现
因为栈是一种特殊的线性表，所以栈的顺序存储可以通过顺序线性表来实现。
SeqStack.h
#ifndef SEQSTACK_H
#define SEQSTACK_H
#include
#include
//数组去模拟栈的顺序存储
#define MAX_SIZE 1024
#define SEQSTACK_TRUE 1
#define SEQSTACK_FALSE 0
typedef struct SEQSTACK {
void* data[MAX_SIZE];
int size;
}SeqStack;
//初始化栈
SeqStack* Init_SeqStack();
//入栈
void Push_SeqStack(SeqStack* stack, void* data);
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack);
//出栈
void Pop_SeqStack(SeqStack* stack);
//判断是否为空
int IsEmpty(SeqStack* stack);
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack);
//清空栈
void Clear_SeqStack(SeqStack* stack);
//销毁
void FreeSpace_SeqStack(SeqStack* stack);
#endif
SeqStack.c
#include"SeqStack.h"
//初始化栈
SeqStack* Init_SeqStack() {
SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
for (int i = 0; i
}
stack->size = 0;
return stack;
}
//入栈
void Push_SeqStack(SeqStack* stack, void* data) {
if (stack == NULL) {
return;
}
if (stack->size == MAX_SIZE) {
return;
}
if (data == NULL) {
return;
}
stack->data[stack->size] = data;
stack->size++;
}
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack) {
if (stack == NULL) {
return NULL;
}
if (stack->size == 0) {
return NULL;
}
return stack->data[stack->size - 1];
}
//出栈
void Pop_SeqStack(SeqStack* stack) {
if (stack == NULL) {
return;
}
if (stack->size == 0) {
return;
}
stack->data[stack->size - 1] = NULL;
stack->size--;
}
//判断是否为空
int IsEmpty(SeqStack* stack) {
if (stack == NULL) {
return -1;
}
if (stack->size == 0) {
return SEQSTACK_TRUE;
}
return SEQSTACK_FALSE;
}
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack) {
return stack->size;
}
//清空栈
void Clear_SeqStack(SeqStack* stack) {
if (stack == NULL) {
return;
}
for (int i = 0; i
stack->data[i] = NULL;
}
stack->size = 0;
}
//销毁
void FreeSpace_SeqStack(SeqStack* stack) {
if (stack == NULL) {
return;
}
free(stack);
}
栈的顺序存储.c
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include "SeqStack.h"
typedef struct PERSON {
char name[64];
int age;
}Person;
int main(void) {
//创建栈
SeqStack* stack = Init_SeqStack();
//创建数据
Person p1 = { "aaa", 10 };
Person p2 = { "bbb", 20 };
Person p3 = { "ccc", 30 };
Person p4 = { "ddd", 40 };
Person p5 = { "eee", 50 };
//入栈
Push_SeqStack(stack, &p1);
Push_SeqStack(stack, &p2);
Push_SeqStack(stack, &p3);
Push_SeqStack(stack, &p4);
Push_SeqStack(stack, &p5);
//输出
while (Size_SeqStack(stack) > 0) {
//访问栈顶元素
Person* person = (Person*)Top_SeqStack(stack);
printf("Name:%s Age:%dn", person->name, person->age);
//弹出栈顶元素
Pop_SeqStack(stack);
}
//释放内存
FreeSpace_SeqStack(stack);
system("pause");
return 0;
}
3.栈的链式存储
- 基本概念
栈的链式存储结构简称链栈。
思考如下问题：
栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？
答：由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让他俩合二为一呢，所以比较好的办法就是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。
- 设计与实现
链栈是一种特殊的线性表，链栈可以通过链式线性表来实现。
LinkStack.h
#ifndef LINKSTACK_H
#define LINKSTACK_H
#include
#include
//链式栈的结点
typedef struct LINKNODE {
struct LINKNODE* next;
}LinkNode;
//链式栈
typedef struct LINKSTACK {
LinkNode head;
int size;
}LinkStack;
//初始化函数
LinkStack* Init_LinkStack();
//入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data);
//出栈
void Pop_LinkStack(LinkStack* stack);
//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack);
//返回栈元素的个数
int Size_LinkStack(LinkStack* stack);
//清空栈
void Clear_LinkStack(LinkStack* stack);
//销毁栈
void FreeSpace_LinkStack(LinkStack* stack);
#endif
LinkStack.c
#include"LinkStack.h"
//初始化函数
LinkStack* Init_LinkStack() {
LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
stack->head.next = NULL;
stack->size = 0;
return stack;
}
//入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data) {
if (stack == NULL) {
return;
}
if (data == NULL) {
return;
}
data->next = stack->head.next;
stack->head.next = data;
stack->size++;
}
//出栈
void Pop_LinkStack(LinkStack* stack) {
if (stack == NULL) {
return;
}
if (stack->size == 0) {
return;
}
//第一个有效结点
LinkNode* pNext = stack->head.next;
stack->head.next = pNext->next;
stack->size--;
}
//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack) {
if (stack == NULL) {
return NULL;
}
if (stack->size == 0) {
return NULL;
}
return stack->head.next;
}
//返回栈元素的个数
int Size_LinkStack(LinkStack* stack) {
if (stack == NULL) {
return -1;
}
return stack->size;
}
//清空栈
void Clear_LinkStack(LinkStack* stack) {
if (stack == NULL) {
return;
}
stack->head.next = NULL;
stack->size = 0;
}
//销毁栈
void FreeSpace_LinkStack(LinkStack* stack) {
if (stack == NULL) {
return;
}
free(stack);
}
栈的链式存储.c
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include "LinkStack.h"
typedef struct PERSON {
LinkNode node;
char name[64];
int age;
}Person;
int main(void) {
//创建栈
LinkStack* stack = Init_LinkStack();
//创建数据
Person p1, p2, p3, p4, p5;
strcpy(p1.name, "aaa");
strcpy(p2.name, "bbb");
strcpy(p3.name, "ccc");
strcpy(p4.name, "ddd");
strcpy(p5.name, "eee");
p1.age = 10;
p2.age = 20;
p3.age = 30;
p4.age = 40;
p5.age = 50;
//入栈
Push_LinkStack(stack, (LinkNode*)& p1);
Push_LinkStack(stack, (LinkNode*)& p2);
Push_LinkStack(stack, (LinkNode*)& p3);
Push_LinkStack(stack, (LinkNode*)& p4);
Push_LinkStack(stack, (LinkNode*)& p5);
//输出
while (Size_LinkStack(stack) > 0) {
//取出栈顶元素
Person* p = (Person*)Top_LinkStack(stack);
printf("Name:%s Age:%dn", p->name, p->age);
//弹出栈顶元素
Pop_LinkStack(stack);
}
//销毁栈
FreeSpace_LinkStack(stack);
system("pause");
return 0;
}
4.栈的应用(案例)
4.1案例1: 就近匹配
几乎所有的编译器都具有检测括号是否匹配的能力，那么如何实现编译器中的符号成对检测？如下字符串:
#include
- 算法思路
- 从第一个字符开始扫描
- 当遇见普通字符时忽略，
- 当遇见左符号时压入栈中
- 当遇见右符号时从栈中弹出栈顶符号，并进行匹配
- 匹配成功：继续读入下一个字符
- 匹配失败：立即停止，并报错
- 结束：
- 成功: 所有字符扫描完毕，且栈为空
- 失败：匹配失败或所有字符扫描完毕但栈非空
- 总结
- 当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性
- 栈非常适合于需要“就近匹配”的场合
案例代码：
#include"LinkStack.h"
//案例一 就近匹配
void test02(){
char* str = "#include
//初始化栈
LinkStack* lstack = InitLinkStack();
//匹配括号
char* pCurrent = str;
while (*pCurrent != ' '){
if (*pCurrent == '('){
PushLinkStack(lstack, pCurrent);
}
else if (*pCurrent == ')'){
char* p = (char*)TopLinkStack(lstack);
if (*p == '('){
PopLinkStack(lstack);
}
}
pCurrent++;
}
if (GetLengthLinkStack(lstack) > 0){
printf("匹配失败!n");
}
//销毁栈
DestroyLinkStack(lstack);
}
int main(){
test02();
system("pause");
return EXIT_SUCCESS;
4.2案例2：中缀表达式和后缀表达式
- l 后缀表达式（由波兰科学家在20世纪50年代提出）
- 将运算符放在数字后面 ===》 符合计算机运算
- 我们习惯的数学表达式叫做中缀表达式===》符合人类思考习惯
- l 实例
- 5 + 4 => 5 4 +
- 1 + 2 * 3 => 1 2 3 * +
- 8 + ( 3 – 1 ) * 5 => 8 3 1 – 5 * +
- l 中缀转后缀算法：
遍历中缀表达式中的数字和符号：
- 对于数字：直接输出
- 对于符号：
- 左括号：进栈
- 运算符号：与栈顶符号进行优先级比较
- 若栈顶符号优先级低：此符号进栈 （默认栈顶若是左括号，左括号优先级最低）
- 若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
- l 右括号：将栈顶符号弹出并输出，直到匹配左括号
遍历结束：将栈中的所有符号弹出并输出
- l 中缀转后缀伪代码 priority
transform(exp)
{
创建栈S；
i= 0；
while(exp[i] != ‘ ’)
{
if(exp[i] 为数字)
{
Output（exp[i]）;
}
else if(exp[i] 为符号)
{
while(exp[i]优先级 <= 栈顶符号优先级)
{
output（栈顶符号）；
Pop（S）;
}
Push(S, exp[i]);
}
else if(exp[i] 为左括号)
{
Push(S, exp[i]);
}
else if(exp[i] 为右括号)
{
while(栈顶符号不为左括号)
{
output（栈顶符号）；
Pop（S）;
}
从S中弹出左括号；
}
else
{
报错，停止循环；
}
i++;
}
while(size(S) > 0 && exp[i] == ‘ ’)
{
output(栈顶符号)；
Pop（S）;
}
}
- l 动手练习
将我们喜欢的读的中缀表达式转换成计算机喜欢的后缀表达式
中缀表达式: 8 + ( 3 – 1 ) * 5
后缀表达式: 8 3 1 – 5 * +
4.3案例3：计算机如何基于后缀表达式计算
- l 思考
计算机是如何基于后缀表达式计算的？
例如：8 3 1 – 5 * +
- l 计算规则
遍历后缀表达式中的数字和符号
- 对于数字：进栈
- 对于符号：
- 从栈中弹出右操作数
- 从栈中弹出左操作数
- 根据符号进行运算
- 将运算结果压入栈中
遍历结束：栈中的唯一数字为计算结果
- l 代码实现（伪代码） express
compute(exp)
{
创建栈；
int i = 0;
while( exp[i] != ‘ ’)
{
if（exp[i]为数字）
{
Push（S, exp[i]）;
}
else if(exp[i]为符号)
{
1. 从栈顶弹出右操作数；
2. 从栈中弹出左操作数；
3. 根据符号进行运算；
4. Push（stack， 结果）；
}
else
{
报错，停止循环；
}
i++;
}
if( Size(s) == 1 && exp[i] == ‘ ’)
{
栈中唯一的数字为运算结果；
}
返回结果；
}
京公网安备 11010802041100号