03-stack设计与实现专题讲座


Stack设计实现专题讲座

Stack基概念
栈种特殊线性表
栈仅线性表端进行操作
栈顶(Top)：允许操作端
栈底(Bottom)：允许操作端

Stack常操作
创建栈
销毁栈
清空栈
进栈
出栈
获取栈顶元素
获取栈

C语言描述栈设计实现 生财富库积累
#ifndef _MY_STACK_H_
#define _MY_STACK_H_

typedef void Stack

Stack* Stack_Create()

void Stack_Destroy(Stack* stack)

void Stack_Clear(Stack* stack)

int Stack_Push(Stack* stack void* item)

void* Stack_Pop(Stack* stack)

void* Stack_Top(Stack* stack)

int Stack_Size(Stack* stack)

#endif _MY_STACK_H_

栈序存储设计实现
1基概念

2设计实现
头文件
#ifndef __MY_SEQLIST_H__
#define __MY_SEQLIST_H__

typedef void SeqList
typedef void SeqListNode

SeqList* SeqStack_Create(int capacity)

void SeqStack _Destroy(SeqStack * list)

void SeqStack _Clear(SeqStack * list)

int SeqStack _Length(SeqStack * list)

int SeqStack _Capacity(SeqStack * list)

int SeqStack _Insert(SeqStack * list SeqListNode* node int pos)

SeqListNode* SeqList_Get(SeqList* list int pos)

SeqListNode* SeqList_Delete(SeqList* list int pos)

#endif __MY_SEQLIST_H__


栈链式存储设计实现
1基概念



2设计实现
头文件
#ifndef _MY_LINKSTACK_H_
#define _MY_LINKSTACK_H_

typedef void LinkStack

LinkStack* LinkStack_Create()

void LinkStack_Destroy(LinkStack* stack)

void LinkStack_Clear(LinkStack* stack)

int LinkStack_Push(LinkStack* stack void* item)

void* LinkStack_Pop(LinkStack* stack)

void* LinkStack_Top(LinkStack* stack)

int LinkStack_Size(LinkStack* stack)

#endif _MY_LINKSTACK_H_

栈应
应1：匹配
编译器具检测括号否匹配力
实现编译器中符号成检测？
#include int main() { int a[4][4] int (*p)[4] p a[0] return 0

算法思路
第字符开始扫描
遇见普通字符时忽略遇见左符号时压入栈中
遇见右符号时栈中弹出栈顶符号进行匹配
匹配成功：继续读入字符
匹配失败：立停止报错
结束：
成功 字符扫描完毕栈空
失败：匹配失败字符扫描完毕栈非空
需检测成出现互相邻事物时
栈进先出特性
栈非常适合需匹配场合

计算机质工作做数学运算计算机读入字符串
9 + (3 1) * 5 + 8 2计算值？


应2：中缀 缀
计算机质工作做数学运算计算机读入字符串
9 + (3 1) * 5 + 8 2计算值？
缀表达式 ？符合计算机运算
波兰科学家20世纪50年代提出种运算符放数字面缀表达式应
惯数学表达式做中缀表达式符合类思考惯

实例：
5 + 4> 5 4 +
1 + 2 * 3 > 1 2 3 * +
8 + ( 3 – 1 ) * 5 > 8 3 1 – 5 * +
中缀表达式符合类阅读思维惯
缀表达式符合计算机运算惯
中缀表达式转换成缀表达式？
中缀转缀算法：
遍历中缀表达式中数字符号
数字：直接输出
符号：
左括号：进栈
运算符号：栈顶符号进行优先级较
栈顶符号优先级低：符合进栈 （默认栈顶左括号左括号优先级低）
栈顶符号优先级低：栈顶符号弹出输出进栈
右括号：栈顶符号弹出输出直匹配左括号
遍历结束：栈中符号弹出输出
中缀转缀

计算机基缀表达式计算？
8 3 1 – 5 * +
遍历缀表达式中数字符号
数字：进栈
符号：
栈中弹出右操作数
栈中弹出左操作数
根符号进行运算
运算结果压入栈中
遍历结束：栈中唯数字计算结果

栈神奇
中缀表达式惯表达方式
缀表达式计算机喜欢表达方式
通栈方便中缀形式变换缀形式
中缀表达式计算程类似程序编译运行程

扩展：字符串计算结果
1+2*(66(2*3)+7)
1
字符串解析
词法语法分析
优先级分析
数结构选型栈树？

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档