数据结构笔记2 堆栈（堆栈的顺序存储、链式存储、表达式求值）

您所在的位置：网站首页 › 表达式求值总结的方法有哪些 › 数据结构笔记2 堆栈（堆栈的顺序存储、链式存储、表达式求值）

数据结构笔记2 堆栈（堆栈的顺序存储、链式存储、表达式求值）

2024-07-18 00:16:52| 来源: 网络整理| 查看: 265

文章目录堆栈的抽象数据类型描述堆栈的顺序存储实现堆栈的链式存储实现堆栈应用：中缀表达式转后缀表达式源代码汇总

堆栈的抽象数据类型描述

中缀表达式：运算符号位于两个运算数之间。如，a+b*c-d / e 后缀表达式：运算符号位于两个运算数之后。如， abc *+de / -

后缀表达式求值，需要有种存储方法，能顺序存储运算数，并在需要时“倒序”输出。这就引入了堆栈。

堆栈（Stack）：具有一定操作约束的线性表只在一端（栈顶，Top）做插入、删除插入数据：入栈（Push）删除数据：出栈（Pop）后入先出：Last In First Out（LIFO）

类型名称: 堆栈（Stack）数据对象集：一个有0个或多个元素的有穷线性表。 1、Stack CreateStack( int MaxSize )：生成空堆栈，其最大长度为MaxSize； 2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满； 3、void Push( Stack S, ElementType item )：将元素item压入堆栈； 4、int IsEmpty ( Stack S )：判断堆栈S是否为空； 5、ElementType Pop( Stack S )：删除并返回栈顶元素；

堆栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

#define MaxSize typedef struct SNode *Stack; struct SNode{ ElementType Data[MaxSize]; int Top; };

1、入栈

void Push( Stack PtrS, ElementType item ) {if ( PtrS->Top == MaxSize-1 ) { printf(“堆栈满”); return; } else { PtrS->Data[++(PtrS->Top)] = item; return; } }

PtrS->Data[++(PtrS->Top)] = item这个语句做了两件事情：

(PtrS->Top)++; PtrS->Data[PtrS->Top] = item;

2、出栈

ElementType Pop( Stack PtrS ) { if ( PtrS->Top == -1 ) { printf(“堆栈空”); return ERROR; /* ERROR是ElementType的特殊值，标志错误*/ } else return ( PtrS->Data[(PtrS->Top)--] ); }

例：请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。分析：一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。

#define MaxSize struct DStack { ElementType Data[MaxSize]; int Top1; /* 堆栈１的栈顶指针 */ int Top2; /* 堆栈２的栈顶指针 */ } S; S.Top1 = -1; S.Top2 = MaxSize; void Push( struct DStack *PtrS, ElementType item, int Tag ) { /* Tag作为区分两个堆栈的标志，取值为1和2 */ if ( PtrS->Top2 – PtrS->Top1 == 1) { /*堆栈满*/ printf(“堆栈满”); return ; } if ( Tag == 1 ) /* 对第一个堆栈操作 */ PtrS->Data[++(PtrS->Top1)] = item; else /* 对第二个堆栈操作 */ PtrS->Data[--(PtrS->Top2)] = item; } ElementType Pop( struct DStack *PtrS, int Tag ) { /* Tag作为区分两个堆栈的标志，取值为1和2 */ if ( Tag == 1 ) { /* 对第一个堆栈操作 */ if ( PtrS->Top1 == -1 ) { /*堆栈1空 */ printf(“堆栈1空”); return NULL; } else return PtrS->Data[(PtrS->Top1)--]; } else { /* 对第二个堆栈操作 */ if ( PtrS->Top2 == MaxSize ) { /*堆栈2空 */ printf(“堆栈2空”); return NULL; } else return PtrS->Data[(PtrS->Top2)++]; } } 堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。栈顶指针Top应该在链表的哪一头？若用单向链表实现一个堆栈，链表的头可以作为top，链尾不行（删除时找不到前一个结点）。

typedef struct SNode *Stack; struct SNode{ ElementType Data; struct SNode *Next; } ;

(1) 堆栈初始化（建立空栈） (2) 判断堆栈S是否为空在这里插入图片描述

Stack CreateStack() { /* 构建一个堆栈的头结点，返回指针 */ Stack S; S =(Stack)malloc(sizeof(struct SNode)); S->Next = NULL; return S; } int IsEmpty(Stack S) { /*判断堆栈S是否为空，若为空函数返回整数1，否则返回0 */ return ( S->Next == NULL ); } void Push( ElementType item, Stack S) { /* 将元素item压入堆栈S */ struct SNode *TmpCell; TmpCell=(struct SNode *)malloc(sizeof(struct SNode)); /* 申请结点 */ TmpCell->Element = item; TmpCell->Next = S->Next; S->Next = TmpCell; }

主要靠这俩个语句：

TmpCell->Next = S->Next; S->Next = TmpCell;

（数组需要判别满不满，链表不需要）

ElementType Pop(Stack S) { /* 删除并返回堆栈S的栈顶元素 */ struct SNode *FirstCell; ElementType TopElem; if( IsEmpty( S ) ) { printf(“堆栈空”); return NULL; } else { FirstCell = S->Next; S->Next = FirstCell->Next; TopElem = FirstCell ->Element; free(FirstCell); return TopElem; } }

（记得释放空间 free(FirstCell)）

堆栈应用：中缀表达式转后缀表达式

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。 ① 运算数：直接输出； ② 左括号：压入堆栈； ③ 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）； ④ 运算符： • 若优先级大于栈顶运算符时，则把它压栈； • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈； ⑤ 若各对象处理完毕，则把堆栈中存留的运算符一并输出。

中缀转换为后缀示例：（ 2*（9+6/3-5）+4）在这里插入图片描述

源代码汇总 typedef int Position; struct SNode { ElementType *Data; /* 存储元素的数组 */ Position Top; /* 栈顶指针 */ int MaxSize; /* 堆栈最大容量 */ }; typedef struct SNode *Stack; Stack CreateStack( int MaxSize ) { Stack S = (Stack)malloc(sizeof(struct SNode)); S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); S->Top = -1; S->MaxSize = MaxSize; return S; } bool IsFull( Stack S ) { return (S->Top == S->MaxSize-1); } bool Push( Stack S, ElementType X ) { if ( IsFull(S) ) { printf("堆栈满"); return false; } else { S->Data[++(S->Top)] = X; return true; } } bool IsEmpty( Stack S ) { return (S->Top == -1); } ElementType Pop( Stack S ) { if ( IsEmpty(S) ) { printf("堆栈空"); return ERROR; /* ERROR是ElementType的特殊值，标志错误 */ } else return ( S->Data[(S->Top)--] ); } typedef struct SNode *PtrToSNode; struct SNode { ElementType Data; PtrToSNode Next; }; typedef PtrToSNode Stack; Stack CreateStack( ) { /* 构建一个堆栈的头结点，返回该结点指针 */ Stack S; S = (Stack)malloc(sizeof(struct SNode)); S->Next = NULL; return S; } bool IsEmpty ( Stack S ) { /* 判断堆栈S是否为空，若是返回true；否则返回false */ return ( S->Next == NULL ); } bool Push( Stack S, ElementType X ) { /* 将元素X压入堆栈S */ PtrToSNode TmpCell; TmpCell = (PtrToSNode)malloc(sizeof(struct SNode)); TmpCell->Data = X; TmpCell->Next = S->Next; S->Next = TmpCell; return true; } ElementType Pop( Stack S ) { /* 删除并返回堆栈S的栈顶元素 */ PtrToSNode FirstCell; ElementType TopElem; if( IsEmpty(S) ) { printf("堆栈空"); return ERROR; } else { FirstCell = S->Next; TopElem = FirstCell->Data; S->Next = FirstCell->Next; free(FirstCell); return TopElem; } }

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

数据结构笔记2 堆栈（堆栈的顺序存储、链式存储、表达式求值）

数据结构笔记2 堆栈（堆栈的顺序存储、链式存储、表达式求值）

今日新闻

点击排行

推荐新闻

图片新闻

专题文章