当前位置：文档之家 › 数据结构(严蔚敏)课件第3章

数据结构(严蔚敏)课件第3章

  • 格式：pptx
  • 大小：1.03 MB
  • 文档页数：110

下载文档原格式

  / 110

合集下载

数据结构(严蔚敏)精第3章PPT课件

数据结构(严蔚敏)精第3章PPT课件

ppt精选版
10
二、栈的主要操作 1.初始化栈：InitStack(&S)
将栈S置为一个空栈(不含任何元素)。
2.进栈：PUSH(&S,X)
将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压 入”。
3.出栈： POP(&S，&e)
删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。
或简单定义如下：
#define M 100 int s[M]; int top;
ppt精选版
16
图3.2 顺序栈中的进栈和出栈
Top指向栈顶元素 初态：top=-1; 空栈，栈中无元素， 进栈：top=top+1; s[top]=x; 退栈：取s[top]; top=top-1; 栈满：top=M-1;栈溢出（上溢），不能再进栈（错误状 态） top=-1时不能退栈，下溢（ppt精正选版常状态，常作控制条件17）
ppt精选版
两种存储结构中的实现都不难，但应该对它
们了如指掌，特别要注意它们的基本操作实
现时的一些特殊情况，如栈满和栈空、队满
和队空的条件以及它们的描述方法。本章要
求必须完成的算法设计题为：3.15，3.17，
3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32。
其中前4个主要是练习栈的应用，后4个主要
插入：最先放入栈中元素在栈底，最后放入的元素在栈顶； 删除：最后放入的元素最先删除，最先放入的元素最后删除。 栈是一种后进先出(Last In First Out)的线性表，简称为LIFO 表。
ppt精选版
8
出栈 栈顶
an
进栈
出栈
进栈
…

教学课件 数据结构--严蔚敏

教学课件 数据结构--严蔚敏
1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度
1.1 数据结构讨论的范畴
Niklaus Wirth：
Algorithm + Data Structures = Programs
程序设计:
算法: 数据结构:
为计算机处理问题编制 一组指令集
处理问题的策略
问题的数学模型
例如: 数值计算的程序设计问题
结构静力分析计算 ─━ 线性代数方程组
全球天气预报 ─━ 环流模式方程 (球面坐标系)
非数值计算的程序设计问题
例一: 求一组(n个)整数中的最大值 算法: ? 基本操作是“比较两个数的大小” 模型：？ 取决于整数值的范围
例二：计算机对弈
算法：? 对弈的规则和策略 模型：? 棋盘及棋盘的格局
例三：足协的数据库管理
S 是 D上关系的有限集。
数据的存储结构
—— 逻辑结构在存储器中的映象
“数据元素”的映象 ？
“关系”的映象 ？
数据元素的映象方法：
用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2
关系的映象方法：（表示x, y的方法）
抽象数据类型的表示和实现
抽象数据类型需要通过固有数据 类型(高级编程语言中已实现的数据 类型)来实现。
例如，对以上定义的复数。
// -----存储结构的定义
typedef struct { float realpart； float imagpart；
}complex；
// -----基本操作的函数原型说明
顺序映象
以相对的存储位置表示后继关系 例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C

数据结构-清华大学严蔚敏

数据结构-清华大学严蔚敏
④ 除最后一个元素外，每个元素均有唯一一个直接 后继。
精选ppt课件
4
2.2 线性表的顺序存储
顺序存储 ：把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。
顺序存储的线性表的特点：
◆ 线性表中所有元素所占的存储空间是连续的; ◆ 数据元素在存储空间中是按逻辑顺序依次存放。 设有非空的线性表：(a1，a2，…an) 。顺序存储如图 2-1所示。
8
图2-2 链表结点结构
单链表是由表头唯一确定，因此单
链表可以用头指针的名字来命名。
1100
例1、线性表L=(bat，cat，eat，fat，
hat)
1300
其带头结点的单链表的逻辑状态和物理
存储方式如图2-3所示。
1305
head
3695
head
bat
cat
eat
fat
hat ⋀ 3700
图2-3 带头结点的单链表的逻辑精选状ppt课态件、物理存储方式
图2-6是带头结点的单循环链表的示意图。
head
head a1
a2
……
an
空表
非空表
图2-6 单循环链表精选示ppt意课件图
10
2.4 双向链表
双向链表(Double Linked List) :指的是构
成链表的每个结点中设立两个指针域：一个指向其直接 前趋的指针域prior，一个指向其直接后继的指针域 next。这样形成的链表中有两个方向不同的链，故称 为双向链表。
LOC(ai+1)=LOC(ai)+l
精选ppt课件
6
2.3 线性表的链式存储
2.3.1 线性表的链式存储结构

数据结构严蔚敏PPT完整版2024新版

数据结构严蔚敏PPT完整版2024新版

选择排序的基本思想
在未排序序列中找到最小（或最大）元素，存放到排序 序列的起始位置，然后，再从剩余未排序元素中继续寻 找最小（或最大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。
交换排序和归并排序
交换排序的基本思想
通过不断地交换相邻的两个元素（如果它们的顺序错 误）来把最小的元素“浮”到数列的一端。具体实现 时，从第一个元素开始，比较相邻的两个元素，如果 前一个比后一个大，则交换它们的位置；每一对相邻 元素做同样的工作，从开始第一对到结尾的最后一对 ；这步做完后，最后的元素会是最大的数；针对所有 的元素重复以上的步骤，除了最后一个；持续每次对 越来越少的元素重复上面的步骤，直到没有任何一对 数字需要比较。
归并排序的基本思想
将两个或两个以上的有序表合并成一个新的有序表。具 体实现时，把长度为n的输入序列分成两个长度为n/2 的子序列；对这两个子序列分别采用归并排序；将两个 排序好的子序列合并成一个最终的排序序列。
查找的基本概念和方法
查找的定义
根据给定的某个值，在查找表中确定 一个其关键字等于给定值的数据元素 的过程或操作。
数组的定义和基本操作
数组的定义
数组（Array）是由相同类型的元素（ element）的集合所组成的数据结构 ，分配一块连续的内存来存储。利用 元素的索引（index）可以计算出该 元素对应的存储位置。
数组的基本操作
数组的基本操作包括数组的创建、数 组的初始化、数组的访问、数组的遍 历、数组的排序和数组的查找等。
顺序表的基本操作实现
包括插入、删除、查找等操作，时间复杂度为 O(n)。
顺序表的特点
支持随机访问，存储密度高，但插入和删除操作需要移动大量元素。

《数据结构(C语言版 第2版)》(严蔚敏 著)第三章练习题答案

《数据结构(C语言版 第2版)》(严蔚敏 著)第三章练习题答案

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

严蔚敏数据结构课件chap3(2)

严蔚敏数据结构课件chap3(2)

Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队 尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; }
1 2 3 返址 n
5 7 5 8
a z
一、 抽象数据类型队列的定义 链队列---队列的链式表示 二、 链队列 队列的链式表示 和实现 循环队列---队列的顺序表 三、 循环队列 队列的顺序表 示和实现
队列的类型定义
ADT Queue { 数据对象： 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： 数据关系： R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头 an 端为队列尾 队列头， 队列头 队列尾 基本操作： 基本操作： } ADT Queue
队列的基本操作： 队列的基本操作：
InitQueue(&Q) QueueEmpty(Q) GetHead(Q, &e) EnQueue(&Q, e) DestroyQueue(&Q) QueueLength(Q) ClearQueue(&Q) DeQueue(&Q, &e)
QueueTravers(Q, visit())
…
}// a
递归函数执行的过程可视为同一函数 同一函数 进行嵌套调用，例如：
递归工作栈： 递归工作栈：递归过程执行过程中占用的

数据结构严蔚敏C语言版第三章

if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; }//end InitSatck
2、返回栈顶元素 Status GetTop(SqStack S，SElemTtype &e) { if (S.top==S.base) return ERROR; e=*(S.top-1); return OK; }//end GetTop
switch(ch){ case ‘#’ : Pop(S,ch); //书上为c case ‘@’ : ClearStack(S); default : Push(S,ch); }//end switch
ch=getchar( ); }//end while 将从栈底到栈顶内的字符传送到用户数据区； ClearStack(s); if(ch!=eof) ch=gethar( ); } //end while DestroyStack(s); }//end LineEdit
InitStack(&S) 操作结果: 建立一个空栈S
DestroyStack(&S) 初始条件：栈S已存在 操作结果: 栈S被销毁
ClearStack(&S) 初始条件：栈S已存在 操作结果: 将S栈清空
StackEmpty(S) 初始条件：栈S已存在 操作结果：若栈S为空栈，返回true,否则返回false
v链栈
栈顶
top data next
栈底
…...
^
其操作与线性链表类似
3.2 栈的应用举例
3.2.1 3.2.2 3.2.3 3.2.5
Байду номын сангаас
数制转换 括号匹配的检验 行编辑程序 表达式求值

数据结构严蔚敏ppt课件

数据结构严蔚敏ppt课件数据结构（严蔚敏）版●资料上传者：安徽大学研究生●资料使用范围：各大学考研及本科教学●欢迎报考安徽大学研究生●“星光考研书屋”祝您学习愉快[学习目标]掌握线性表的顺序存储结构和抽象数据类型中定义的每一种操作的含义，在顺序存储方式下每一种操作的具体实现和相应的时间复杂度；掌握链接存储的概念，线性表的单、双链接存储结构，对它们进行插入和删除结点的方法，循环单、双链表和带表头附加结点的单、双链表的结构和操作特点；掌握每一种线性表操作在由动态结点构成的单链表上具体实现的算法以及相应的时间复杂度。

2第2章线性表线性结构是最常用、最简单的一种数据结构。

而线性表是一种典型的线性结构。

其基本特点是线性表中的数据元素是有序且是有限的。

在这种结构中：① 存在一个唯一的被称为“第一个”的数据元素；② 存在一个唯一的被称为“最后一个”的数据元素；③ 除第一个元素外，每个元素均有唯一一个直接前驱；④ 除最后一个元素外，每个元素均有唯一一个直接后继。

32.1 线性表的逻辑结构线性表(Linear List ) ：是由n(n ≧0)个数据元素(结点)a 1，a 2，…a n 组成的有限序列。

该序列中的所有结点具有相同的数据类型。

其中数据元素的个数n 称为线性表的长度。

当n=0时，称为空表。

当n>0时，将非空的线性表记作： (a 1，a 2，…a n ) a 1称为线性表的第一个(首)结点，a n 称为线性表的最后一个(尾)结点。

2.1.1 线性表的定义4a1，a2，…a i-1都是a i(2≦i≦n)的前驱，其中a i-1是a i的直接前驱;a i+1，a i+2，…a n都是a i(1≦i ≦n-1)的后继，其中a i+1是a i 的直接后继。

2.1.2线性表的逻辑结构线性表中的数据元素a i所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。

◆线性表中的结点可以是单值元素(每个元素只有一个数据项) 。

数据结构严蔚敏(全部章节814张PPT)-(课件)

① 集合：结构中的数据元素除了“同属于一个集合” 外，没有其它关系。
② 线性结构：结构中的数据元素之间存在一对一的 关系。
③ 树型结构：结构中的数据元素之间存在一对多的 关系。
④ 图状结构或网状结构：结构中的数据元素之间存 在多对多的关系。
图1-3 四类基本结构图
1.1.3 数据结构的形式定义
数据结构的形式定义是一个二元组： Data-Structure=(D，S)
计算机求解问题的一般步骤
编写解决实际问题的程序的一般过程：
– 如何用数据形式描述问题?—即由问题抽象出一个 适当的数学模型; – 问题所涉及的数据量大小及数据之间的关系; – 如何在计算机中存储数据及体现数据之间的关系? – 处理问题时需要对数据作何种运算? – 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。
其中：D是数据元素的有限集，S是D上关系的有限集。 例2：设数据逻辑结构B=（K，R）
K={k1, k2, …, k9} R={ <k1, k3>，<k1, k8>，<k2, k3>，<k2, k4>，<k2, k5>，<k3, k9>， <k5, k6>，<k8, k9>，<k9, k7>，<k4, k7>，<k4, k6> } 画出这逻辑结构的图示，并确定那些是起点，那些是终点
<基本操作名>(<参数表>) 初始条件： <初始条件描述> 操作结果： <操作结果描述>
– 初始条件：描述操作执行之前数据结构和参数应 满足的条件;若不满足，则操作失败，返回相应的出 错信息。

数据结构严蔚敏PPT(完整版)

排序算法的时间复杂度
时间复杂度是衡量算法效率的重要指标，常见的 排序算法的时间复杂度有O(n^2)、O(nlogn)、 O(n)等。
查找的基本概念和算法
查找的基本概念
查找是指在一个已经有序或部分 有序的数据集合中，找到一个特 定的元素或一组元素的过程。
常见查找算法
常见的查找算法包括顺序查找 、二分查找、哈希查找等。
先进先出（FIFO）的数据 处理。
并行计算中的任务调度。
打印机的打印任务管理。
二叉树的层序遍历（宽度 优先搜索，BFS）。
04
树和图
树的基本概念和性质
树的基本概念
树是一种非线性数据结构，由节 点和边组成，其中节点表示实体 ，边表示实体之间的关系。
树的性质
树具有层次结构，节点按照层次 进行排列，每个节点最多只能有 一个父节点，除了根节点外。
isEmpty：判断队列是否为空。
enqueue：向队尾添加一个元素。
front 或 peek：查看队首元素。
dequeue：删除队首的元素。
栈和队列的应用
栈的应用 后进先出（LIFO）的数据处理。
括号匹配问题。
栈和队列的应用
队列的应用
深度优先搜索（DFS）。 表达式求值。
01
03 02
栈和队列的应用
数据结构严蔚敏ppt( 完整版)
contents
目录
• 绪论 • 线性表 • 栈和队列 • 树和图 • 排序和查找 • 数据结构的应用案例分析
01
绪论
数据结构的基本概念
总结词
数据结构是计算机存储和组织数据的方式，是算法和数据操 作的基础。
详细描述
数据结构是计算机科学中研究数据的组织和存储方式的学科 ，它决定了数据在计算机中的表示和关系。数据结构不仅包 括数据的逻辑结构，还涉及到数据的物理存储方式以及数据 的操作方式。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
是"排队"。在计算机程序中，模拟排队的数据 结构是"队列"。
【学习目标】
1. 掌握栈和队列这两种抽象数据类型 的特点，并能在相应的应用问题中正确选 用它们。
2. 熟练掌握栈类型的两种实现方法。 3. 熟练掌握循环队列和链队列的基本 操作实现算法。 4. 理解递归算法执行过程中栈的状态 变化过程。
【重点和难点】
InitStack(&S) 操作前提： S为未初始化的栈。 操作结果： 将S初始化为空栈。 ClearStack(&S) 操作前提： 栈S已经存在。 操作结果： 将栈S置成空栈。 StackEmpty(S) 操作前提： 栈S已经存在。 操作结果： 若栈S为空，则返回TRUE,否则FALSE。
StackLength(S) 操作前提：栈S已经存在。 操作结果：返回S的元素个数即栈的长度。
Push(&S,e)
操作前提：栈S已经存在。
操作结果：在S的顶部插入(亦称压入)元素e；若S栈未满，将e 插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返 回TRUE。
Pop(&S,&e) 操作前提：栈S已经存在。
操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值； 若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。
二、栈的主要操作 1.初始化栈：InitStack(&S) 将栈S置为一个空栈(不含任何元素)。
2.进栈：PUSH(&S,X) 将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压 入”。
3.出栈： POP(&S，&e) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。
4.取栈顶元素： GETTOP(S，&e) 取栈S中栈顶元素。
栈和队列是在程序设计中被广泛使用的 两种线性数据结构，因此本章的学习重点在 于掌握这两种结构的特点，以便能在应用问 题中正确使用。
【知识点】
顺序栈、链栈、循环队列、链队列
【学习指南】
在这一章中，主要是学习如何在求解应 用问题中适当地应用栈和队列，栈和队列在 两种存储结构中的实现都不难，但应该对它 们了如指掌，特别要注意它们的基本操作实 现时的一些特殊情况，如栈满和栈空、队满 和队空的条件以及它们的描述方法。本章要 求必须完成的算法设计题为：3.15，3.17， 3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32。 其中前4个主要是练习栈的应用，后4个主要 是有关队列的实现方法的练习。
通常称，栈和队列是限定插入和删除 只能在表的“端点”进行的线性表。
线性表
Insert(L, i, x) 1≤i≤n+1 Delete(L, i) 1≤i≤n
栈
Insert(S, n+1, x)
Delete(S, n)
队列
Insert(Q, n+1, x)
Delete(Q, 1)
栈和队列是两种常用的数据类型
插入：最先放入栈中元素在栈底，最后放入的元素在栈顶； 删除：最后放入的元素最先删除，最先放入的元素最后删除。 栈是一种后进先出(Last In First Out)的线性表，简称为LIFO 表。
出栈 栈顶
an
进栈
出栈
进栈
…
a2
栈底
a1
(a) 栈 的 示 意 图
(b) 铁 路 调 序 栈 的 表 示
IsFull(S) 操作前提： 栈S已经存在。 操作结果： 判栈满函数，若S栈已满，则函数值为 TRUE， 否则为FALSE。
StackTraverse(S,visit()) 操作前提：栈S已经存在且非空。 操作结果：从栈底到栈顶依次对S底每个元素调用函 数visit()。一旦visit()失败，则操作失效。
5.判栈空： EMPTY(S) 判断栈S是否为空，若为空，返回值为1，否则返回值为0。
三、栈的抽象数据类型描述
ADT Stack{ 数据对象： D={ai| ai ∈ ElemSet，i=1,2,…,n,n≥ 0}
数据关系： R1={< ai-1 , ai > | ai-1 , ai ∈D, i=1,2,…,n} 基本操作：
图3.1 栈
例：设一个栈的输入序列为A,B,C,D,则借助一 个栈所得到的输出序列不可能是 。
(A) A,B,C,D (B) D,C,B,A
(C) A,C,D,B (D) D,A,B,C
答:可以简单地推算,得容易得出D,A,B,C是不可 能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈 顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是 D,C,B,A。所以本题答案为D。
目录
3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现
3.4 队列
一、栈的定义
3.1 栈
栈(stack)作为一种限定性线性表，是将线性表的插入和删除运 算限制为仅在表的一端进行。
通常将表中允许进行插入、删除操作的一端称为栈顶(Top)， 因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位 置指示器指示。同时表的另一端为固定的一端，被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地 称为进栈或入栈，删除操作称为出栈或退栈。
第三章 栈和队列
【课前思考】
1. 什么是线性结构？ 简单地说，线性结构是一个数据元素的序列。
2. 你见过餐馆中一叠一叠的盘子吗？如果它们是按 1,2,…,n 的次序往上叠的，那么使用时候的次序应 是什么样的？
必然是依从上往下的次序，即n,…,2,1。它们 遵循的是"后进先出"的规律，这正是本章要讨论的 "栈"的结构特点。 3. 在日常生活中，为了维持正常的社会秩序而出现 的常见现象是什么？
GetTop(S, &e)
操作前提： 栈S已经存在。 操作结果：取栈S的顶部元素。与Pop(&S, &e)不同之处在于 GetTop(S,&e)不改 栈的表示和实现
1. 顺序栈
顺序栈是用顺序存储结构实现的栈，即 利用一组地址连续的存储单元依次存放自栈 底到栈顶的数据元素，同时由于栈的操作的 特殊性， 还必须附设一个位置指针top（栈 顶指针）来动态地指示栈顶元素在顺序栈中 的位置。通常以top=0或 top=-1表示空栈。 顺序栈的存储结构可以用C语言中的一维数组 来表示。 栈的顺序存储结构定义如下：