西安交通大学：《计算机软件基础》第3单元 线性数据结构（二）

第3单元 线性数据结构 计算机软件基础 The software bas ic of computer 主讲:赵英良 西安交通大学 计算机教学实验中心

下一页 计算机软件基础 The software basic of computer 主讲：赵英良 西安交通大学 计算机教学实验中心 第3单元 线性数据结构 （二）

第2单元内容概要(一) 、数据结构 1。基本概念:数据、数据元素、数据项、数据结构、 数据结构的形式化描述方法 2。数据的逻辑结构: 逻辑结构的类别(集合、线性、树、图) 3。数据的物理结构及类别(顺序、链式、索引、散 列) 4。算法的描述及评价 (1)算法的概念: (2)算法的特性:有限、确定、可行、输入、输出 上一页 (3)设计算法的要求:正确、可读、健壮、效率 停止放映(4)算法的评价:时间复杂性、空间复杂性 下一页 第2页

下一页 上一页 停止放映 第 2 页 第2单元内容概要（一） 一、数据结构 1。基本概念：数据、数据元素、数据项、数据结构、 数据结构的形式化描述方法。 2。数据的逻辑结构： 逻辑结构的类别（集合、线性、树、图） 3。数据的物理结构及类别（顺序、链式、索引、散 列） 4。算法的描述及评价 （1）算法的概念： （2）算法的特性：有限、确定、可行、输入、输出 （3）设计算法的要求：正确、可读、健壮、效率 （4）算法的评价：时间复杂性、空间复杂性

第2单元内容概要(二) 、顺序表 1。线性表及相关概念和特征 线性表、长度、空表、前驱、后继 均匀性、有序性、形式化定义 2。顺序表 概念、特征、描述(数组、last) 3。顺序表的操作 (1)判空、判满、判合法(2)插入(3)删除 ●4。顺序表的优缺点及适用场合 数据连续存放、随机存取 上一页 逻辑上相邻,物理上也相邻 「停止放映 存储结构简单、易实现 插入、删除操作不便 下一页 存储密度大,空间利用率高 第3页

下一页 上一页 停止放映 第 3 页 第2单元内容概要（二） ⚫ 二、顺序表 1。线性表及相关概念和特征 线性表、长度、空表、前驱、后继、 均匀性、有序性、形式化定义 2。顺序表 概念、特征、描述（数组、last） 3。顺序表的操作 （1）判空、判满、判合法 （2）插入（3）删除 ⚫ 4。顺序表的优缺点及适用场合 – 数据连续存放、随机存取 – 逻辑上相邻，物理上也相邻 – 存储结构简单、易实现 – 插入、删除操作不便 – 存储密度大，空间利用率高

第2单元内容概要(三) 链表 1。单链表 结点、指针域、数据域、头指针、头结点。 2。单链表的描述 3。单链表的操作 (1)指针操作 指针说明、分配存储空间、判空、判满、释放 空间 (2)查找操作(3)插入(4)删除 上一页 4。单链表的特点及适用场合 5。单循环链表、双向链表、双向循环链表 「停止放映 描述、建立、判空、查找、插入、删除 下一页 第4页

下一页 上一页 停止放映 第 4 页 第2单元内容概要（三） ⚫ 三、链表 ⚫ 1。单链表 ⚫ 结点、指针域、数据域、头指针、头结点。 ⚫ 2。单链表的描述 ⚫ 3。单链表的操作 ⚫ （1）指针操作、 ⚫ 指针说明、分配存储空间、判空、判满、释放 空间 ⚫ （2）查找操作 （3）插入 （4）删除 ⚫ 4。单链表的特点及适用场合 ⚫ 5。单循环链表、双向链表、双向循环链表 描述、建立、判空、查找、插入、删除

本单元内容 栈、队列、数组、串的 有关概念 逻辑结构及特点 存储结构 有关操作 涉及章节:第1章的 1.3栈和队列(P32~P46) 上一页 1.4串和数组(P47P55) 「停止放映 下一页 第5页

下一页 上一页 停止放映 第 5 页 本单元内容 ⚫ 栈、队列、数组、串的: –有关概念 –逻辑结构及特点 –存储结构 –有关操作 ⚫ 涉及章节：第1章的 1.3 栈和队列 (P32~P46) 1.4 串和数组 (P47~P55)

栈 1。栈及相关概念 堆找( Stack) 栈是允许在同一端进行插入和删除操作的 特殊线性表。 允许进行插入和删除操作的一端称为栈页 (top),另一端为栈底( bottom);栈底固定, 而栈顶浮动; 栈中元素个数为零时称为空栈。 栈结构也称为后进先出表(LIFO)。 上一页 「停止放映 栈、栈顶、栈底、空栈 下一页 后进先出表栈底固定,而栈顶浮动 0页

下一页 上一页 停止放映 第 6 页 一、栈 1。栈及相关概念 堆栈(Stack) –栈是允许在同一端进行插入和删除操作的 特殊线性表。 –允许进行插入和删除操作的一端称为栈顶 (top)，另一端为栈底(bottom)；栈底固定， 而栈顶浮动； –栈中元素个数为零时称为空栈。 –栈结构也称为后进先出表（LIFO）。 栈、栈顶、栈底、空栈 后进先出表 栈底固定，而栈顶浮动

栈有关概念 栈顶指针 在栈操作过程中,有一个专门的栈指针(习惯 上称它为ToP),指出栈顶元素所在的位置。 栈空的条件:top=-1 栈满的条件:top=MAXS|ZE-1 找上溢 栈空间是有限的,若栈已满,再进行入栈操作 时,就要产生上溢。 上一页 楼下溢 「停止放映 若栈空,再要执行出栈操作,则会发生下溢。 下一页 第7页

下一页 上一页 停止放映 第 7 页 栈有关概念 栈顶指针 在栈操作过程中，有一个专门的栈指针（习惯 上称它为TOP），指出栈顶元素所在的位置。 栈空的条件： top = -1 栈满的条件： top = MAXSIZE-1 栈上溢 栈空间是有限的，若栈已满，再进行入栈操作 时，就要产生上溢。 栈下溢 若栈空，再要执行出栈操作，则会发生下溢

2、栈的基本运算 ● Setnull( Stack)置栈为空; ● Empty( Stack)判定栈是否为空 Push( Stack,x)进栈操作,在栈顶插入元素; Pop( Stack)出栈操作,删除栈顶元素; 上一页 ● Gettop( Stack)取栈顶元素 「停止放映 下一页 第8页

下一页 上一页 停止放映 第 8 页 2、栈的基本运算 ⚫ Setnull（Stack） 置栈为空； ⚫ Empty（Stack） 判定栈是否为空； ⚫ Push（Stack，x）进栈操作，在栈顶插入元素； ⚫ Pop（Stack） 出栈操作，删除栈顶元素； ⚫ Gettop（Stack） 取栈顶元素

例1-10 有三个元素的进栈序列是1,2,3。写出可 能的出栈序列。 出栈序列 操作序列 S X S X S X 132 213 X S X 321 上一页 「停止放映 下一页 第9页

下一页 上一页 停止放映 第 9 页 例1-10 有三个元素的进栈序列是1，2，3。写出可 能的出栈序列。 出栈序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x

3、栈的顺序存储结构 (1)栈的顺序存储结构:实际上是一维 数组。 (2)顺序栈:栈的顺序存储结构称为顺 序栈。 ●栈的操作只能在一端进行;即栈顶位置随 进栈和出栈而变化。 ●(3)顺序栈的C语言描述(初始化、定义): 上一页 define maXsize n 「停止放映 int stack [ MAXSIZE] 下一页 int top 第10页

下一页 上一页 停止放映 第 10 页 3、栈的顺序存储结构 ⚫ （1）栈的顺序存储结构：实际上是一维 数组。 ⚫ （2）顺序栈：栈的顺序存储结构称为顺 序栈。 ⚫ 栈的操作只能在一端进行；即栈顶位置随 进栈和出栈而变化。 ⚫ （3）顺序栈的C语言描述(初始化、定义)： #define MAXSIZE n int stack[MAXSIZE]; int top = -1;