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

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

团购合买资源类别：文库，文档格式：PPT，文档页数：71，文件大小：260KB

第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;

点击进入文档下载页（PPT格式）

共71页，可试读20页，点击继续阅读 ↓↓

点击下载（PPT格式）

浏览记录