首页  思维导图  详情



 



数据结构chapter_04

2019-06-19 14:55:28   16  举报





数据结构java

第四章

数据结构

java

笔记

模板推荐

作者其他创作

大纲/内容

栈

定义

特殊的线性表,其插入与删除操作只允许在线性表的一端进行,通常称允许插入与删除的一端为栈顶,不允许的一端为栈底,无元素时为空栈

S=(A+B+C+D+E) 中 A为栈底元素,E为栈顶元素,后进先出表

运算规则

出栈或弹出(POP)  入栈或压入(PUSH)

顺序栈基于数组基本运算

InitStack(S)构造空栈S

StackEmpty判断是否空栈

StackFull(S)判断是否为满栈

Push(S , x)入栈,若栈不满,x压入栈顶

Pop(S)出栈

seqStack

链式栈基于单链表的实现

基本

栈溢出

"上溢" 栈满时进栈

"下溢"栈空时退栈

栈的表示与实现

中缀转后缀表达式

'(' > '*' > '/' > '+' = '-'

如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。

队列

定义

入队操作称为队列的插入

出队称为队列的删除

队列的数据元素与线性表的数据元素完全相同

接口

队列的存储分为链式存储与顺序存储

顺序循环队列

解决假溢出

操作`

假设数组空间是m , 只要在入 , 出队列时,将队首和队尾的指针对m作求模运算即可,取值范围 0 - m-1

入队时 rear = (rear + 1) % maxSize

出队时 front = (front + 1) % maxSize

队空:front == rear

队满: (rear + 1)%maxSize == front

求队长:(rear-front + maxSize)%maxSize

链式队列

定义队列的存储结构基本和线性表的定义相同

特殊的线性表,只考虑对线性表的两端操作的情况,并且只能一端插入,另一端删除

线性表除此之外（不限定一端插入、一端删除），还需要考虑中间的结点的插入、删除、查询等操作。

一个链队由头指针和尾指针唯一确定

基本运算

队列的使用

运算规则

 Collect

Get Started

数据结构图__1

 Collect

Get Started

数据结构和算法

 Collect

Get Started

数据结构

 Collect

Get Started

数据结构与算法





0 条评论

下一页