当前位置：文档之家 › 数据结构课件ppt第三章-1

数据结构课件ppt第三章-1

  • 格式：ppt
  • 大小：307.50 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

数据结构课件-第三章

数据结构课件-第三章

{k=n%r ；push(S，k)；n/=r；}
while(!StackEmpty(S))
{pop(S，k)；printf(“%d ”，k)；}
}
例3.3 表达式中括号匹配问题。假设一个算术表达 式中包含圆括号、方括号和花括号三种类型的括号 ，编写一个判别表达式中括号是否正确配对的算法
。
算法思想：算术表达式中三种括号出现的次序 正好符合后到的括号要最先被匹配的“后进先 出”的栈的操作特点，因此可以利用一个栈来 存储三种左括号。当右括号出现时，看当前栈 顶括号是否与之匹配，若匹配则退栈，若不匹 配说明算术表达式中括号配对不正确。若算术 表达式中所有括号都能正确的别消解，则改算 术表达式中括号配对正确，否则该算术表达式 中括号配对不正确。用顺序栈实现如下 ：
if（（Sq->rear+1）%MAXSIZE==Sq->front） return 0; /*若循环队 列已满*/ Sq->elem［Sq->rear］=x; /*若循环队列未满，则先插入元素， 后将尾指针后移*/ Sq->rear=（Sq->rear+1）%MAXSIZE; return 1; }
数据结构
主编 许绘香 段明义 中国水利水电出版社
第三章 栈和队列
栈和队列是两种特殊的线性结构。从数据的结 构角度看，它们是线性表，从操作的角度看， 它们是操作受限的线性表。在日常生活中经常 会遇到栈或队列的实例。例如，停车场车辆的 调度要用到栈，排队购物要用到队列。
3.1工作场景导入
【工作场景】 某公司有一个地下停车场如图3-1-1，此停车场是一个可停 放n辆汽车的狭长通道,且只有一个大门可供汽车进出.汽车在停车 场内按照车辆到达时间的先后顺序, 依次从停车场最里向大门口 处停放(最先到达的第一辆车放在停车场的最里面)。 若车场内已 停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开 走,则排在便道上的第一辆车即可开入;当停车场内的某辆车要开 走时,在它之后进入的车辆必须退出车场为它让路,待该辆车开出 大门外,其他车辆再按照原次序进入车场,每辆车停放在车场的车 在它离开停车场时必须按照它停留的时间长短交纳费用. 如果停 留在便道上的车未进停车场就要离去，允许其离去，不收停车费， 并且仍然保持在便道上等待的车辆次序。编制程序模拟该停车场

精品课件-数据结构(刘肖)-第3章

精品课件-数据结构(刘肖)-第3章

第3章 栈与队列 图3-2 顺序栈的状态及进栈、出栈操作
第3章 栈与队列
可见栈空和栈满是进行栈操作的两个限制条件。 栈空条件：s->top = 0，此时不能进行出栈操作。 栈满条件：s->top = Maxsize -1，此时不能进行进栈操作。 2．栈的基本运算的实现 算法3-1 初始化。 栈的初始化即创建一个空栈。可通过指针变量获取该空栈。 算法描述如下：
第3章 栈与队列
该类型包含两部分内容：一个是存放栈中数据元素的data 数组，另一个是标记栈顶位置的top。在C语言的描述中，我们 可约定data数组中的data[0]单元不用，并用top=0表示栈空， 这也是初始化栈的状态。在实际应用时，只需声明一个属于上 述类型的栈变量，即可对此变量进行栈的有关操作。
(2) 在日常生活中，为了维持正常的社会秩序而出现的 常见现象是排队，计算机系统中也要解决各种任务的有序等待 问题，因此，设计一种队列结构来描述和解决此类问题将是必 要的和有效的。
本章我们就来学习栈与队列这两种结构及其在实际中的应 用。
第3章 栈与队列 知识要点
(1) 栈与队列的逻辑结构； (2) 栈与队列的顺序存储结构及链式存储结构； (3) 栈与队列的基本运算。 能力要求 应用栈与队列的基本运算解决计算机应用中的一些实际问 题。
第3章 栈与队列
3.1 栈
3.1.1 栈的定义及基本运算
第3章 栈与队列 生活中，我们都有洗盘子和取用盘子的经验，通常是将洗
好的盘子叠放在一起，放的时候是最先洗好的盘子放在最下面， 之后每洗完一个盘子，就将其累放在这叠盘子的最上面。取用 的时候是先取用最上面的盘子(即最后放置的盘子)，之后依次 取用放在顶部的盘子，而第一个放置的盘子最后一个被取用。 这个过程的特点就是最后放置的盘子最先取用，而最先放置的 盘子最后取用。那么，描述和解决类似这样放入次序和使用次 序相反的问题应采用什么样的数据结构呢？答案是“栈”结构。

数据结构ppt3

数据结构ppt3

54
6
6
到一位8进制数则进栈
6
0
6
保存，转换完毕后依
所以：（3456）10 =（6613）8
次出栈则正好是转换 结果。
3.1 栈
3.1.4 栈的应用实例
例3.4
算法设计： 当N>0时，重复(1)，(2)：
（1）若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈 s的内容依次出栈，算法结束。
3.1 栈
3.1.1 栈的定义和运算
栈的定义：
栈是只能在一端进行插入和删除的线性表(运算受限)。 由此，栈具有后进先出（LIFO）的特性。
入栈(插入)
栈顶元素
an
…
a2 a1
出栈(删除) 栈顶：插入、删除的一端
栈底：栈顶的另一端
3.1 栈
3.1.1 栈的定义和运算
栈的基本运算：
(1) 初始化栈init_stack(S)： 设置栈S为空。
量top来标识栈顶位置。 类型定义如下：
#define maxsize 50 typedef struct
{ elementtype data[maxsize]; int top;
} seqstack; //定义了一个栈类型seqstack seqstack s1,*s; //定义了栈变量s1和指向栈类型的指针s
为此，可采用循环结构来解决，即将Q->data[0]做为Q>data[maxsize-1]的下一个存储位置——循环队列。
3.2 队列
3.2.2 顺序队列与循环队列
1、存储结构
Q->rear
1
Q->data: 0
maxsize-1
Q->front

数据结构全部课件

数据结构全部课件

p
top ai ai-1
链栈的删除算法
template <class T> T LinkStack::Pop( )
top
{
if (top==NULL) throw "下溢";
x=top->data; p=top; top=top->next; delete p; return x;
a1
∧
}
第3章 特殊线性表——栈
直接解决：为每个栈开辟一个数组空间。
分析会出现什么问题？如何解决？
解决方案② 利用顺序栈单向延伸的特性，使用一个数组来存储 两个栈。
分析会出现什么问题？如何解决？
第3章 特殊线性表——栈
使用一个数组来存储两个栈， 解决方案一:为每个栈开辟一个数组空间。 让一个栈的栈底为该数组的始 端，另一个栈的栈底为该数组 存储空间的浪费。 的末端，每个栈从各自的端点 解决方案二: 向中间延伸。
第3章 特殊线性表——栈
栈的示意图
入栈 出栈
1.举一些生活中的例子。 2.假定有三个元素按a、 b、c的次序依次进栈， 且每个元素只允许进一 次栈，则可能的出栈序 列有多少种？
栈顶
栈底
a3 a2 a1
注意：栈只是对表插入和 删除操作的位置进行了限 制，并没有限定插入和删 除操作进行的时间。
栈的特性：后进先出
第3章 特殊线性表——栈
顺序栈的基本运算的实现——入栈
template <class T> void seqStack::Push ( T x) { if (top==MAX_SIZE-1) throw “溢出”; top++; data[top]=x; } 时间复杂度？

《数据结构》课件

《数据结构》课件

查找操作
顺序查找
二分查找
链表查找
在顺序存储结构的线性表中，查找操 作需要从线性表的第一个节点开始， 逐个比较节点的数据域，直到找到目 标数据或遍历完整个线性表。时间复 杂度为O(n)。
在有序的顺序存储结构的线性表中， 查找操作可以采用二分查找算法。每 次比较目标数据与中间节点的数据域 ，如果目标数据大于中间节点，则在 右半部分继续查找；否则在左半部分 查找。时间复杂度为O(log n)。
数据结构是算法的基础。许多算法的实现需要依赖于特定的数据结构， 因此掌握常见的数据结构是编写高效算法的关键。
数据结构在解决实际问题中具有广泛应用。无论是操作系统、数据库系 统、网络通信还是人工智能等领域，数据结构都发挥着重要的作用。
数据结构的分类
根据数据的逻辑关系，数据结构可以分为线性结构和非线 性结构。线性结构如数组、链表、栈和队列等，非线性结 构如树形结构和图形结构等。
04
数据结构操作
插入操作
顺序插入
在顺序存储结构的线性表中，插入操作 需要找到插入位置的前驱节点，修改前 驱节点的指针，使其指向新节点，然后 让新节点指向后继节点。如果线性表的 第一个节点是空节点，则将新节点作为 第一个节点。
VS
链式插入
在链式存储结构的线性表中，插入操作需 要找到插入位置的前驱节点，修改前驱节 点的指针，使其指向新节点。如果线性表 的第一个节点是空节点，则将新节点作为 第一个节点。
图
01
02
03
04
图是一种非线性数据结构，由 节点和边组成，其中节点表示 数据元素，边表示节点之间的
关系。
图具有网络结构，节点之间的 关系可以是任意复杂的，包括
双向、单向、无向等。

数据结构3栈和队列PPT教学课件

数据结构3栈和队列PPT教学课件

~AStack() { delete [] elements; } // Destructor
void clear() { top = 0; }
注意：这里top在第I个位置
2020/12/12
8
一些重要的条件
栈满：top==maxSize-1； 栈空：top==-1
2020/12/12
9
链式栈
{
private:
int MaxSize;
// 栈中最大元素个数
int top;
// 栈中实际元素个数
T *elements; // 存储栈元素的数组
public:
AStack(int sz =DefaultListSize) // Constructor
{ size = sz; top = 0; elements = new T[sz]; }
virtual void MakeEmpty() = 0; virtual int isEmpty（） virtual int isFull（）=0
};
2020/12/12
5
顺序栈
由于栈是运算受限的线性表，因此 线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈， 它是运算受限的线性表。因此，可用 数组来实现顺序栈。因为栈底位置是 固定不变的，所以可以将栈底位置设 置在数组的两端的任何一个端点；栈 顶位置是随着进栈和退栈操作而变化 的，故需用一个整型变量top
时间上：顺序栈为O(1),链式栈为O(1) 空间上：顺序栈要一个固定的长度，当栈不够
满时，空间浪费；链式栈长度可变，但对于每 个元素需要一个链接域，产生结构性开销。 何时使用顺序栈？ 当要实现多个栈时，可用一个数组存储两个栈， 且最好是一个栈增长时另一个栈缩短。

《数据结构》课件第3章

《数据结构》课件第3章

图3.1 栈结构示意图 (a) 非空栈；(b) 空栈
假设有一个栈S=(a1, a2 ,…, ai-1, ai, ai+1, …, an)，如果a1 先进栈，则an最后进栈。因为进栈和出栈元素都只能在栈 顶一端进行，所以每次出栈的元素总是当前栈中栈顶的元 素，它是最后进栈的元素，而最先进栈的元素要到最后才 能出栈。在日常生活中，有许多类似栈的例子。例如将洗 净的盘子放入消毒桶时，总是一个接一个地往上摞(相当于 进栈)；取出盘子时，则是从最上面一个接一个地往外拿 (相当于出栈)，最后取出的是最先放进去的那个盘子。因 此，栈又被称为后进先出(Last In First Out,LIFO)的线性表。
top是栈顶指针，它是指针类型变量，top唯一地确定一 个链栈。对于不带头结点的链栈，栈顶元素为top，当 top = NULL时，该链栈为空栈；带头结点的链栈的栈顶元 素为top->next，栈为空的条件是top->next = NULL，如图3.3 所示。
图3.3 带头结点的链栈示意
下面讨论在带头结点的链栈上实现进栈和出栈操作 的算法。
{ /* 将栈S的栈顶元素弹出，其值复制到x所指的存储空
间中 */
if(S->top==-1)
/*栈为空*/
return(0);
else
{
*x=S->data［S->top］;
S->top--;
/*修改栈顶指针*/
return(1);
}
}
(6) 取栈顶元素。
int gettop(SeqStack S, Elemtype *x) { /* 将栈S的栈顶元素值复制到x所指的存储空间中，但
1. 递归的定义 递归就是一个事件或对象部分地由自己组成，或 者由它自己定义。例如，求阶乘就是递归的一个典型 的例子：

03数据结构基本概念PPT课件

03数据结构基本概念PPT课件

数据结构研究的主要内容
①数据元素之间的逻辑关系 ②采用的存储结构 ③对这些数据元素采用何种方式进行操作
2020/11/23
9
例：数据结构——学生成绩表
✓数据元素（学号、姓名、科目、成绩） ✓数据元素之间的关系（逻辑结构） ✓数据元素的存储（物理结构） ✓对数据元素的操作（增、减、查找、修改等）
33
数据结构上的常见操作
遍历、插入、更新、 删除、 查找、 排序 注意：每个问题都有一种和多种算法
找到效率最高的 以最容易理解的方式设计 设计的算法不容易出错或出错情况较少
2020/11/23
34
算法
算法的评价
时间复杂度
代码的执行时间，一般是以代码实际执行的指令数量（条）
空间复杂度
2020/11/23
11
数据的逻辑结构
数据元素之间关系的描述 描述逻辑结构的方法：描述法和图示法 描述法：
二元组 B ＝ （ K， R ）
K：元素集合 R：元素间关系的集合
注意：元素间的关系一般抽象为前驱与后继关 系，即表明结构中，一个元素的前一个元素是 谁，它的后一个元素又是谁
2020/11/23
24
索引存储
方法
为放在内存 中的元素建 索引表
K1
立索引表
1
K3
元素可以离 2
散存放
3
K4
通过查索引 4 表找到需要 索引号
K2
的元素
2020/11/23
联想：图书馆的查书卡
0300 0301 0302 0303 0304 0305 0306 0307 0308 0309
25
散列存储
散列存储方法
2020/11/23

数据结构ppt课件完整版

数据结构ppt课件完整版
数据结构是计算机中存储、组织 数据的方式，它定义了数据元素 之间的逻辑关系以及如何在计算 机中表示这些关系。
数据结构分类
根据数据元素之间关系的不同， 数据结构可分为线性结构、树形 结构、图形结构等。
4
数据结构重要性
01
02
03
提高算法效率
合理的数据结构可以大大 提高算法的执行效率，减 少时间和空间复杂度。
33
案例三：最小生成树在通信网络优化中应用
Kruskal算法
基于并查集实现，按照边的权值从小到大依次添加边，直到生成 最小生成树。
Prim算法
从某一顶点开始，每次选择与当前生成树最近的顶点加入，直到 所有顶点都加入生成树。
通信网络优化
最小生成树算法可用于通信网络优化，通过选择最优的通信线路 和节点，降低网络建设和维护成本。
2024/1/28
简化程序设计
数据结构的设计和实现可 以简化程序设计过程，提 高代码的可读性和可维护 性。
解决实际问题
数据结构是解决实际问题 的基础，如排序、查找、 图论等问题都需要依赖于 特定的数据结构。
5
相关术语解析
数据元素
数据元素是数据的基本 单位，通常作为一个整
体进行考虑和处理。
2024/1/28
02
队列的基本操作包括入队（enqueue）、出队（ dequeue）、查看队首和队尾元素等。
03
队列的特点
2024/1/28
04
数据从队尾入队，从队首出队。
05
队列中元素的插入和删除操作分别在两端进行，因此也称 为双端操作。
06
队列中没有明显的头尾标记，通常通过计数器或循环数组 等方式实现。
15
栈和队列应用举例
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

栈顶指针
an
an-1
a1 ∧
顺 序栈
top F E top D C top base base B A base C B A
top:栈顶指针，始终指向栈顶元素的下一个位置。 栈顶指针，始终指向栈顶元素的下一个位置。 栈顶指针 base：栈底指针，始终指向栈底的位置，base＝NULL，栈不存在。 ：栈底指针，始终指向栈底的位置， ＝ ，栈不存在。 base==top，栈空。 ，栈空。
}
Status Push (SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) {//栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } s.top *S.top++ = e; s.top return OK; c }
InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &e) ClearStack(&S) Push(&S, e) Pop(&S, &e) StackTravers(S, visit())
InitStack(&S)
类似于线性表的顺序映象实现， 指向表尾的指针可以作为栈顶指针。 //----- 栈的顺序存储表示 ----#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { SElemType *base; //构造栈之前和销毁栈之后，base值为 构造栈之前和销毁栈之后， 值为NULL 值为 SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 } SqStack;
a2
栈底
a1 栈只能在栈顶进行插入删除等操 作，按照后进先出的原则。
队列：队尾进行插入操作， 队头进行删除操作。
栈、队列与线性表的插入、删除 操作对比
线性表 栈 队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n
b s.base a s.base b a
Status Pop (SqStack &S, SElemType &e) { // 若栈不空，则删除S的栈顶元素， // 用e返回其值，并返回OK； // 否则返回ERROR if (S.top == S.base) return ERROR; e = *--S.top; return OK; }
a1 a2 …… an e
Pop(&S, &e)
初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素， 并用 e 返回其值。 a1 a2 … … an-1 an
栈的存储方法
顺序栈：利用一组地址连续的 top 存储单元依次存放自栈底到栈 C 顶的数据元素，同时附设指针 B top指示栈顶元素在顺序栈中的 base A 位置。 链栈：头指针指向栈顶元素，每个结点的 指针域指向前一个结点。
链栈
top
栈顶 栈底
an
an-1
a1 ∧
注意: 注意 链栈中 指针的方向
链栈是动态分配元素存储空间， 链栈是动态分配元素存储空间， 元素的插入删除操作都是在表 的同一端进行， 的同一端进行，头指针就是栈 顶指针。 顶指针。
3.2 栈的表示和实现
栈的定义 栈的几个基本操作的实现
Status InitStack (SqStack &S) Status Push (SqStack &S, SElemType e) Status Pop (SqStack &S, SElemType &e)
GetTop(S, &e)
初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。
a1 a2
……
an
ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。
Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新 的栈顶元素。
s.base s.top C B A s.base s.top C B A
e
Status InitStack (SqStack &S) {// 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;
第三章 栈和队列
栈和队列是操作受限的线性表，它们 的基本操作是线性表操作的子集。 栈是限定仅在表尾进行插入或删除操 作的线性表。 表尾端成为栈顶，表头端成为栈底。 栈的修改是按后进先出的原则进行， 栈又称为后进先出的线性表。
栈和队列的示意图
出栈 栈顶 进栈
an
. . . 队 头 队 尾 出队列 a1 a2 a3 . . . an 入队列
操作结果：构造一个空栈 S。DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。
StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则 返回 TRUE，否则FALE。
StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数， 即栈的长度。
栈和队列是两种常用的数据类型
3.1 栈的类型定义 3.2 栈的表示与实现 3.3 栈的应用举例 3.4 队列的类型定义 3.5 队列类型的实现
3.1 栈的类型定义
ADT Stack { 数据对象： 数据对象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： 数据关系 R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： 基本操作： } ADT Stack