西安交通大学：《计算机软件基础》第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。栈及相关概念 堆找(Stac) 栈是允许在同一端进行插入和删除操作的 特殊线性表。 允许进行插入和删除操作的一端称为栈项 (top),另一端为栈底( bottom);栈底固定, 而栈顶浮动; 栈中元素个数为零时称为空栈。 栈结构也称为后进先出表(LIFO)。 上一页 「停止放映 栈、栈顶、栈底、空栈 下一页 后进先出表栈底固定,而栈顶浮动 6页

下一页 上一页 停止放映 第 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。写出可 能的出栈序列。 出栈序列 操作序列 323 X S X S X 13 21 sssss 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 =-1 第10页

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