北航数据结构课件 (4)
- 格式：pdf
- 大小：809.91 KB
- 文档页数：65
文档推荐
-
北航数据结构页数:6
-
北航10秋学期《算法与数据结构》模拟题一页数:5
-
北航数据结构课件 (8)页数:99
-
数据结构北航软件技术基础课程ppt页数:50
下载文档原格式
合集下载
数据结构北航软件技术基础课程ppt
eMail:gaoliansheng@
2020/9/23
liansheng_gao@
软件技术基础
• 第零章 编程的一些问题 • 第五章 二叉树和树
• 第一章 绪 论
• 第六章 图和广义表
• 第二章 线 性 表
• 第七章 排 序
• 第三章 栈和队列
• 第八章 查 找
试，通过测试用例保证每条源代码至少执行一次
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 结i述 果re： ：m由 测e专 试n门 报t的 告A测n试a人ly员s对is软件进行测试
• 概要设计-Prim12ary测 测试 试D计e划sign
• 详细设计-Detaile条 wda件lDkt：her编osu译gihg、n链接成功，完成单元测试，
2020/9/23
第零章 程序设计的一些问题
• 软件和属性
– 计算机运行中不可缺少的 – 预先编好，能为他人使用 – 商品
• 盘和软件
– 盘是软件的载体
• 软件的分类
– 应用软件 – 系统软件
2020/9/23
第零章 程序设计的一些问题
• 程序设计的几个阶段(软件工程简介)
– 六、七十年代出现了软件危机
2020/9/23
数据元素
• 数据元素是数据的基本单位。 • 它也可以再由不可分割的数据项组成
2020/9/23
数据对象 性质相同的数据元素的集合 。
例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音…..
数据对象是性质相同的数据元素集合。
2020/9/23
数据结构
• 数据元素集合（也可称数据对象） • 各元素之间的关系，即结构。
北航数据结构课件 (10)
（ 1，4，6 ， 12 8，8 12 ， 6，11，… ）
例
49
temp
temp＞K[j] j=0 38 97 76 65 13 27 50
… (若干趟后)
K[j+1]=K[ j ]； j=j−1；
65
38
49
76 65
76 97
65 97
13
27
50
K[j+1]=temp;
38
49
65
76
97
核心思想
首先确定一个元素的间隔数gap。 将参加排序的元素按照gap分隔成若干个子序列 ( 即分别把那些位置相隔为gap的元素看作一个子序 列),然后对各个子序列采用 某一种排序方法 进行排 序；此后减小gap值，重复上述过程，直到gap<1。
一种减小gap的方法：
gap1 = n/2 gapi = gapi-1/2
1.时间性能 —— 排序过程中元素之间的比较次数与元素的
移动次数。 本章讨论各种排序方法的时间复杂度 时主要按照最差情况下所需要的比较次数 来进行。
2.空间性能 —— 除了存放参加排序的元素之外，排序过程
中所需要的其他辅助空间。
3.排序稳定性 —— 对于值相同的两个元素，排序前后的先后
次序不变，则称该方法为稳定性排序方法， 否则，称为非稳定性排序方法。
算 法
泡排序法的排序趟数与原始序列中数 据元素的排列有关，因此，排序的趟数为 一个范围，即[1..n-1]。
什么情况下至少排序一趟 什么情况下要排序n-1趟
O(n
2)
结论
泡排序方法比较适合于 参加排序的序列的原始状态 基本有序的情况
泡排序法是 稳定性排序方法。
北航数据结构-栈
实验报告：栈实现逻辑关键词求值17374347周京成一、问题描述逻辑关键词求值是程序设计语言中的一个基本问题，简单说就是让计算机理解并且接受高级语言描述的概念，这里的处理对象是“”，代表和；“v”代表并；，“~”代表非；“_”代表蕴含；“-”代表当且仅当；“（”，“）”左右括号；以及代表Ture 的数字1和代表False的0按照一定规则构成的合法式子，由于各种运算之间有优先级关系，所以用括号来隔开，所以使用栈来求逻辑表达式的值，这里我们最好输出的是True和False，为了方便，输入的数字只有1和0.二、数据结构：栈由于使用的是python语言，可以不用直接构造一个栈结构，直接使用列表，就可以实现栈的各类操作，比如进栈，出栈等等。
三、算法的设计和实现：1.首先建立两个列表，分别存储读入的数字和字符2.读入数字和字符，当读入右括号“）”，则要计算这个括号里面的运算结果，存储在数字列表中。
3.最后只剩下最多一个字符和两个数字，再进行讨论既可。
四、预期结果与问题预期结果和我们自己运算应该是一致的，例如（~（1_0））^((1v0)-1)=True一般可能的问题：1．在表达式最外面加括号，例如（1^0）,则需要判断字符列表是不是为空，来判断这种情况。
2.只数字列表只剩一个数字，这时候也要判断字符列表是不是空，最好再输出。
附：python代码：str1=input()list1=[]//字符列表list2=[]//数字列表for i in str1:if i.isdigit()==True:list2.append(int(i))//判断是不是数字else:if i!=")":list1.append(i)//不是右括号存储else:last=list1.pop()//右括号进行计算，各种栈操作while(last!="("):if last=="^":list2.append(list2.pop() and list2.pop())if last=="v":list2.append(list2.pop() or list2.pop())if last=="~":list2.append(not list2.pop())if last=="_":if (not list2.pop()) and (list2.pop())==True: list2.append(0)else:list2.append(1)if last=="-":if (list2.pop()+list2.pop()) in [0,2]:list2.append(1)else:list2.append(0)last=list1.pop()if list1==[]:print (bool (list2.pop()))//判断字符列表是否为空 else : //输出if list1[0]=="^":print (bool (list2.pop() and list2.pop())) if list1[0]=="v":print (bool (list2.pop() or list2.pop())) if list1[0]=="~":print (bool (not list2[0]))if list1[0]=="_":if (not list2.pop()) and list2.pop()==True : print (False )else :print (True )if list1[0]=="-":if (list2.pop()+list2.pop()) in [0,2]: print (True ) else :print (False )输出样例：中国剩余定理（简单写下）：我们只做对于有限多个质数的同余方程组。
北航--数据结构课件第1章
例
procedure MATRIX( A, B, C, n )
for i←1 to n do
------------------------- n+1
for j←1 to n do
------------------ n(n+1)
C[i, j]←0
--------------------------------- n2
课程名称：算法与数据结构
数据结构
教材名称：
《数据结构》
唐发根 编著 科学出版社
《数据结构习题与解析》
科学出版社 2002
为什么要开设 数据结构课程
目的
通过本课程的学习，运用本 课程讨论的知识更好地进行算法 设计与算法分析，掌握计算机进 行数据处理的基本原理、基本方 法和技巧，进一步提高程序设计 的水平和能力。
和最小值。 4. m MOD n 表示m对n取模。 5. 算术运算符有+、-、、/、↑(幂)。 6. 关系运算符有= 、≠、< 、> 、≤、≥ 。
7. 逻辑运算符有and、or、n因子。
用自然语言表达的算法
(1) M除以N，将余数送中间变量R； (2) 测试余数R是否等于零？
loop 语句串
forever
4. 分情况语句
5. 算法调用语句
case
：条件1： 语句串1
：条件2： 语句串2
...
...
...
...
：条件n： 语句串n
：else ： 语句串n+1
end
相当于Pascal语言 的case语句或C语言中 的switch语句
call 算法名(参数表) 变量名←算法名(参数表)
最新北航《嵌入式系统》课件_第三章幻灯片
北航《嵌入式系统》课件_第三 章
第3章 目录
1.简介
9.异常
2.ARM7TDMI
10.复位
3.ARM7TDMI的模块和 11.存储器及存储器映射
内部框图
I/O
4.体系结构直接支持的 数据类型
5.处理器状态
6.处理器模式
7.内部寄存器
8. 程序状态寄存器
3.1 ARM简介
▪改进了ARM/Thumb状态之间的切换效率； ▪E---增强型DSP指令集,包括全部算法操作和16 位乘法操作； ▪J----支持新的JAVA,提供字节代码执行的硬件 和优化软件加速功能。
3.1 ARM简介
ARM处理器核简介
ARM公司开发了很多系列的ARM处理器核， 目前最新的系列已经是ARM11了，而ARM6核以及 更早的系列已经很罕见了。目前应用比较广泛的系 列是：
3.1 ARM简介
项目
ARM7
ARM9
ARM10
流水线
30
150
260
功耗（mW/MHz） 0.06
性能 MIPS**/MHz
架构
0.97 冯诺伊曼
0.19（+cache） 1.1 哈佛
0.5 （+cache）
1.3
哈佛
ARM11
8
335
0.4 （+cache）
1.2
哈佛
3.1 ARM简介
各ARM体系结构版本——V1
该版本的ARM体系结构，只有26位的寻址空 间，没有商业化，其特点为：
▪基本的数据处理指令（不包括乘法）； ▪字节、字和半字加载/存储指令； ▪具有分支指令，包括在子程序调用中使用的分 支和链接指令； ▪在操作系统调用中使用的软件中断指令。
第3章 目录
1.简介
9.异常
2.ARM7TDMI
10.复位
3.ARM7TDMI的模块和 11.存储器及存储器映射
内部框图
I/O
4.体系结构直接支持的 数据类型
5.处理器状态
6.处理器模式
7.内部寄存器
8. 程序状态寄存器
3.1 ARM简介
▪改进了ARM/Thumb状态之间的切换效率； ▪E---增强型DSP指令集,包括全部算法操作和16 位乘法操作； ▪J----支持新的JAVA,提供字节代码执行的硬件 和优化软件加速功能。
3.1 ARM简介
ARM处理器核简介
ARM公司开发了很多系列的ARM处理器核， 目前最新的系列已经是ARM11了，而ARM6核以及 更早的系列已经很罕见了。目前应用比较广泛的系 列是：
3.1 ARM简介
项目
ARM7
ARM9
ARM10
流水线
30
150
260
功耗（mW/MHz） 0.06
性能 MIPS**/MHz
架构
0.97 冯诺伊曼
0.19（+cache） 1.1 哈佛
0.5 （+cache）
1.3
哈佛
ARM11
8
335
0.4 （+cache）
1.2
哈佛
3.1 ARM简介
各ARM体系结构版本——V1
该版本的ARM体系结构，只有26位的寻址空 间，没有商业化，其特点为：
▪基本的数据处理指令（不包括乘法）； ▪字节、字和半字加载/存储指令； ▪具有分支指令，包括在子程序调用中使用的分 支和链接指令； ▪在操作系统调用中使用的软件中断指令。
北航数据结构
四、结果
代码： def qsort(slist,l,r):
if l>r: return -1
t=slist[l] i=l j=r while i!=j:
while slist[j]>=t and i<j: j-=1
while slist[i]<=t and i<j: i+=1
if i<j: slist[i],slist[j]=slist[j],slist[i]
实验报告-快速排序与希尔排序
一、问题描述
快速排序实现中采用了发现逆序和交换记录位置的方法，算法最基本的思想还是划分， 即按某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一 个排序的序列。
希尔排序方法又称为缩小增量的插入排序。基本思想：先将整个待排记录序列分割成为 若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行 一次直接插入排序。
三算法的设计与实现
快速排序
1.设两个指针 low 和 high，初值分别为 low 和 high 2.设第一个元素关键字为 pivotkey 3.从 high 所指位置向前搜索找到第一个小于 pivotkey 的记录互相交换，然后从 low 所指位 置起向后搜索，找到第一个大于 pivotkey 的记录互相交换 4.重复 3，直至 low=high 为止。 希尔排序 （1）先取增量 d>1,把全部记录分成 d 个组 （2）对每组进行直接插入排序 （3）逐渐减少增量 d，直到为 1，所有记录在同一组，直接插入排序为止。
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法 因 D.L.Shell 于 1959 年提出而得名。
代码： def qsort(slist,l,r):
if l>r: return -1
t=slist[l] i=l j=r while i!=j:
while slist[j]>=t and i<j: j-=1
while slist[i]<=t and i<j: i+=1
if i<j: slist[i],slist[j]=slist[j],slist[i]
实验报告-快速排序与希尔排序
一、问题描述
快速排序实现中采用了发现逆序和交换记录位置的方法，算法最基本的思想还是划分， 即按某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一 个排序的序列。
希尔排序方法又称为缩小增量的插入排序。基本思想：先将整个待排记录序列分割成为 若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行 一次直接插入排序。
三算法的设计与实现
快速排序
1.设两个指针 low 和 high，初值分别为 low 和 high 2.设第一个元素关键字为 pivotkey 3.从 high 所指位置向前搜索找到第一个小于 pivotkey 的记录互相交换，然后从 low 所指位 置起向后搜索，找到第一个大于 pivotkey 的记录互相交换 4.重复 3，直至 low=high 为止。 希尔排序 （1）先取增量 d>1,把全部记录分成 d 个组 （2）对每组进行直接插入排序 （3）逐渐减少增量 d，直到为 1，所有记录在同一组，直接插入排序为止。
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法 因 D.L.Shell 于 1959 年提出而得名。
北航编译原理课件 04.语法分析
北京航空航天大学计算机学院
12
规则二 若有文法规则： ∷ 若有文法规则：U∷=x|y|……|z|Uv 其特点是：具有一个直接左递归的右部并位于最后， 其特点是：具有一个直接左递归的右部并位于最后， 这表明该语法类U是由 是由x或 这表明该语法类 是由 或y……或z其后随有零个 或 其后随有零个 或多个v组成 组成。 或多个 组成。 U⇒Uv ⇒ Uv v ⇒ Uv vv ⇒ …… ⇒ 可以改写为U∷ ∴ 可以改写为 ∷=(x|y|……|z){v} 通过以上两条规则，就能消除文法的直接左递归， 通过以上两条规则，就能消除文法的直接左递归， 并保持文法的等价性。 并保持文法的等价性。
北京航空航天大学计算机学院 21
效率低的原因 1) 语法分析要重做 2) 语义处理工作要推倒重来 设文法G（不具左递归性），U 设文法 （不具左递归性）， ∈Vn ）， U::= α 1 | α 2 | α 3
R∷=Sa|a ∷ Q∷=Sab|ab|b ∷
S∷=Sabc|abc|bc|c ∷ S∷=(abc|bc|c){abc} ∷
北京航空航天大学计算机学院
19
最后得到文法为: 最后得到文法为 S∷=(abc|bc|c){abc} ∷ Q∷=Sab|ab|b ∷ R∷=Sa|a ∷ 可以看出其中关于Q和R的规则是多余的规则 可以看出其中关于 和 的规则是多余的规则 ∴经过压缩后 S∷=(abc|bc|c){abc} ∷ 可以证明改写前后的文法是等价的
否则 S ∉ L(G[Z])
主要问题: 主要问题 左递归问题 回溯问题
主要方法: 主要方法 • 递归子程序法 • LL分析法 分析法
北京航空航天大学计自底向上分析算法的基本思想为：
+ 若Z ⇐ S
北航数据库课件
3
数据库设计概述
• 数据库设计的方法（2）
– 规范设计法：运用软件工程的思想和方法，把 整个设计过程划分为若干阶段，把复杂的大问 题分为若干相对简单的小问题，每个阶段只解 决整个设计中的部分问题。 – 规范设计法是迭代和逐步求精的过程，每一过 程完成时要进行设计分析，产生各种设计文 档，并组织评审和用户交流，如不满足要求则 进行修改。
• E-R图的组成：实体、联系、属性
– 实体：用长方形表示实体型，在框内写上实体名。 – 属性：用椭圆形表示实体的属性，并用无向边把实体 与其属性连接起来。 – 联系：用菱形表示实体间的联系，菱形框内写上联系 名。用无向边把菱形分别与有关实体相连，在无向边 旁标上联系的类型。若联系也具有属性，则属性和菱 形也用无向边连接上。
解决——同一实体的属性通常取分E-R图中属性的并，再适当调整次序。
– 实体之间的联系在不同分E-R图中呈现不同类型。
解决——根据语义加以综合或调整。
例：
A
A
A
n
l1 l2
n m
B
n p
C
l1
n
l2
p C
m
B
m
B
m
34
产品
m
组装
n
零件
编号
产品名
性能
零件数
零件号 零件名 材料号 耗用量
第四章 数据库设计
• • • • • 数据库设计概述 需求分析 概念结构设计 逻辑结构设计 物理结构设计
1
数据库设计概述
• 什么是数据库设计
– 是指对于一个给定的应用环境，设计优化的数据 库逻辑和物理结构，建立数据库及其应用系统， 使之能够有效地存储数据，满足用户的应用需求。
数据库设计概述
• 数据库设计的方法（2）
– 规范设计法：运用软件工程的思想和方法，把 整个设计过程划分为若干阶段，把复杂的大问 题分为若干相对简单的小问题，每个阶段只解 决整个设计中的部分问题。 – 规范设计法是迭代和逐步求精的过程，每一过 程完成时要进行设计分析，产生各种设计文 档，并组织评审和用户交流，如不满足要求则 进行修改。
• E-R图的组成：实体、联系、属性
– 实体：用长方形表示实体型，在框内写上实体名。 – 属性：用椭圆形表示实体的属性，并用无向边把实体 与其属性连接起来。 – 联系：用菱形表示实体间的联系，菱形框内写上联系 名。用无向边把菱形分别与有关实体相连，在无向边 旁标上联系的类型。若联系也具有属性，则属性和菱 形也用无向边连接上。
解决——同一实体的属性通常取分E-R图中属性的并，再适当调整次序。
– 实体之间的联系在不同分E-R图中呈现不同类型。
解决——根据语义加以综合或调整。
例：
A
A
A
n
l1 l2
n m
B
n p
C
l1
n
l2
p C
m
B
m
B
m
34
产品
m
组装
n
零件
编号
产品名
性能
零件数
零件号 零件名 材料号 耗用量
第四章 数据库设计
• • • • • 数据库设计概述 需求分析 概念结构设计 逻辑结构设计 物理结构设计
1
数据库设计概述
• 什么是数据库设计
– 是指对于一个给定的应用环境，设计优化的数据 库逻辑和物理结构，建立数据库及其应用系统， 使之能够有效地存储数据，满足用户的应用需求。
数据结构讲义
《数据结构》讲义(总158页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《数据结构》讲义第一章：绪论课程：数据结构课题：第一章—小节（共4个课时）什么是数据结构基本概念和术语抽象数据类型的表现与实现算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。
新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学内容及过程：……………………………第1-2课时……………………………计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。
计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。
进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系———产生背景。
什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。
其中建立数学模型的实质：找出操作对象之间的关系。
例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。
（地位）数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。
包括数值、字符、声音、图象等。
2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。
一个数据元素可由若干个数据项组成（Data Item）。
3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构4(清华大学)ppt
//取顶点 i 的值
virtual E getWeight (int v1, int v2); //取边上权值
virtual int getFirstNeighbor (int v);
//取顶点 v 的第一个邻接顶点
146-14
virtual int getNextNeighbor (int v, int w); //取邻接顶点 w 的下一邻接顶点
};
146-23
template <class T, class E> int Graphmtx<T, E>::getFirstNeighbor (int v) { //给出顶点位置为v的第一个邻接顶点的位置, //如果找不到, 则函数返回-1
virtual bool removeEdge (int v1, int v2); //在图中删去边(v1,v2)
};
146-15
邻接矩阵 (Adjacency Matrix)
• 在图的邻接矩阵表示中，有一个记录各个顶 点信息的顶点表，还有一个表示各个顶点之 间关系的邻接矩阵。
• 设图 A = (V, E) 是一个有 n 个顶点的图, 图的 邻接矩阵是一个二维数组 A.edge[n][n]，定义：
const int DefaultVertices = 30; //最大顶点数(=n)
template <class T, class E>
class Graph {
//图的类定义
protected:
int maxVertices;
//图中最大顶点数
int numEdges;
//当前边数
int numVertices;
146-17
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第四章
堆栈和队列
本章内容4.1堆栈的基本概念
4.2堆栈的顺序存储结构
4.3堆栈的链式存储结构
4.4堆栈的应用举例(习题课)
4.5队列的基本概念
4.6队列的顺序存储结构
4.7队列的链式存储结构
4.1堆栈的基本概念
进栈
退栈后进先出
堆栈的示意图
特殊性1. 其操作仅仅是一般线性表的
操作的一个子集。
2. 插入和删除操作的位置受到
限制。
二.堆栈的基本操作
1. 插入（进栈、入栈）
2. 删除（出栈、退栈）
3. 测试堆栈是否为空
4. 测试堆栈是否已满
5. 检索当前栈顶元素√√√
描述堆栈的顺序存储结构最简单的方法是利用一维数组STACK[ 0..M–1 ]来表示,同时定义一个整型变量(不妨取名为top)给出栈顶元素的位置。
a b c d e
top=4
上溢下溢—当堆栈已满时做插入操作。
—当堆栈为空时做删除操作。
溢出
数组:堆栈:静态结构动态结构
(top=M –1)(top=–
1)
0 1 2 3 M-1
…STACK[0..M -1]
top
0 1 2 3 M-1
……
top
1. 初始化堆栈
void INITIALS( int &top ){
top= –1;}
二. 堆栈的基本算法
0 1 2 3 M-1
……
top
3. 测试堆栈是否已满
0 1 2 3 M-1
…
STACK[0..M-1]
0 1 2 3 4
M -1
a d
c b
…
item
4. 插入(进栈)算法
5. 删除(出栈)算法
0 1 2 3 4 M-1
三. 多栈共享连续空间问题
（以两个堆栈共享一个数组为例）
当i=1时，将
item 插入第1个栈，
当i=2时，将item 插入第2个栈。
插入
top[0]++；
STACK[top[0]]=item ；
top[1]--；
STACK[top[1]]=item ；
i=2
top[0]=top[1]–1
0 1 2 …
M -1
0 1 2 …M -1
算法
算法
当i=1时，删除第1个栈的栈顶元素，当i=2时，删除第2个栈的栈顶元素。
top[0]––;
i=1
top[1]++;
i=2
0 1 2 …
M -1
可
用空间
第1栈栈空的条件删除
top[0]=-1 top[1]=M
第2栈栈空的条件
0 1 2 …
M -1
int POP( SElemType STACK[ ], int top[ ], int i, SElemType item )
{
if(i==1)
if(top[0]==–1)
return 0;
else{
item=STACK[top[0]––];
return 1;
}
else
if(top[1]==M)
return 0;
else{
item=STACK[top[1]++];
return 1;
}
}对第一个栈进行操作对第二个栈进行操作
链接堆栈就是用一个线性链表来实现一个堆栈结构, 同时设置一个指针变量( 这里不妨仍用top表示)指出当前栈顶元素所在链结点的位置。
栈为空时，有top=NULL。
栈顶元素
在一个初始为空的链接堆栈中依次插入元素
A, B, C, D
以后, 堆栈的状态为例
top
void INITIAL( STLink &top ){top=NULL;}
1.堆栈初始化
二.基本算法int EMPTYS( STLink top ){return top==NULL;}
2.测试堆栈是否为空
3.插入(进栈)算法
......
等效于在链表最前面插入一个新结点
4.删除(退栈)算法
......
仍然要判断栈空！
(2)
见习题课(2
)
4.5 队列的基本概念
先进先出一.队列的定义
进队出队
队头元素队尾元素
先进先出
队列的示意图
二. 队列的基本操作
1.队列的插入（进队、入队）
3. 测试队列是否为空
2. 队列的删除（出队、退队）
4. 检索当前队头元素
5. 创建一个空队√√√
特殊性1.其操作仅是一般线性表
的操作的一个子集。
2.插入和删除操作的位置
受到限制。
4.6 队列的顺序存储结构在实际程序设计过程中，通常借助一个一维数组QUEUE[0..M –
1]来描述队列的顺序存储结构，同时，设置
两个变量front 与rear 分别指出当前队头元素与队尾元素的位置。
QUEUE[0..M-1]
0 1 2 3 M -1b c d a e
一.构造原理
队头位置队尾位置
QUEUE[0..M –1]0 1 2 3 4 5 M-1
b c a d 初始时, 队列为空, 有
front= –1rear= –1测试队列为空的条件是
front=rear 约定
front 指出实际队头元素所在位置的前一个位置。
rear 指出实际队尾元素
所在的位置,
void INITIALQ( int &front, int &rear ) {front= –1;rear= –1;
}
1. 初始化队列
3. 插入(进队)算法front rear
item 0 1 M -1
a c d
b
01
2
34M -1M -2::
三.循环队列
把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为。
循环队列QUEUE[0..M -1]……0 1 2 3 4 ……M -2 M -1留课后学习
front与rear分别指向实际队头和队尾元素
空队对应的链表为空链表，空队的标志是
front = NULL
在一个初始为空的链接队列中依次插入
数据元素A, B, C, D
以后, 队列的状态为
例front rear
队尾元素队头元素
void INITIALQ(QLink &front, QLink &rear){front=NULL;rear=NULL ；
}
二.基本算法
1. 初始化队列
rear -
>link=p;
分两种情
况3. 插入(进队)front =rear =NULL 1
4. 删除(出队)
所谓销毁一个队列是指将队列所对应的链表中所有结点都删除，并且释放其存储空间，使队列成为一个空队(空链表)。
…
rear 归结为一个线性链表的删除
5. 销毁一个队列
一个线性链表的删除
…
…rear
本章内
容小结本章内容小结
堆栈、队列
堆栈、队列的顺序存储结构
堆栈、队列的链式存储结构
堆栈、队列的应用举例
堆栈、队列是特殊线性表(特殊性)
（循环队列）
堆栈、队列的定义
构造原理、特点
对应的插入、删除操作的算法设计
构造原理、特点
对应的插入、删除操作的算法设计
0 1 2 3 4 5 6 7
F G H A B C D E temp
0 1 2 3 4 5 6 7A B C D E F G H
0 1 2 3 4 5 6 7A A B C D E F G
循环右移1位0 1 2 3 4 5 6 7H A B C D E F G 请设计一算法，该算法将数组A[0..n-1]的所有元素循环右移k 个位置。
练习1H 保存
k=3 0 1 2 3 4 5 6 7A B C D E F G H 例。