计算机软件基础 The software basic puter 主讲:赵英良 西安交通大学 计算机教学实验中心 第3单元 线性数据结构 (二) 9/18/2017 1 第2单元内容概要(一) 一、数据结构 1。基本概念:数据、数据元素、数据项、数据结构、数据结构的形式化描述方法。 2。数据的逻辑结构: 逻辑结构的类别(集合、线性、树、图) 3。数据的物理结构及类别(顺序、链式、索引、散列) 4。算法的描述及评价 (1)算法的概念: (2)算法的特性:有限、确定、可行、输入、输出 (3)设计算法的要求:正确、可读、健壮、效率 (4)算法的评价:时间复杂性、空间复杂性 2 第2单元内容概要(二) 二、顺序表 1。线性表及相关概念和特征 线性表、长度、空表、前驱、后继、 均匀性、有序性、形式化定义 2。顺序表 概念、特征、描述(数组、last) 3。顺序表的操作 (1)判空、判满、判合法(2)插入(3)删除 4。顺序表的优缺点及适用场合 数据连续存放、随机存取 逻辑上相邻,物理上也相邻 存储结构简单、易实现 插入、删除操作不便 存储密度大,空间利用率高 3 第2单元内容概要(三) 三、链表 1。单链表 结点、指针域、数据域、头指针、头结点。 2。单链表的描述 3。单链表的操作 (1)指针操作、 指针说明、分配存储空间、判空、判满、释放空间 (2)查找操作(3)插入(4)删除 4。单链表的特点及适用场合 5。单循环链表、双向链表、双向循环链表 描述、建立、判空、查找、插入、删除 4 本单元内容 栈、队列、数组、串的: 有关概念 逻辑结构及特点 存储结构 有关操作 涉及章节:第1章的 栈和队列(P32~P46) 串和数组(P47~P55) 5 一、栈 1。栈及相关概念 堆栈(Stack) 栈是允许在同一端进行插入和删除操作的特殊线性表。 允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动; 栈中元素个数为零时称为空栈。 栈结构也称为后进先出表(LIFO)。 栈、栈顶、栈底、空栈 后进先出表栈底固定,而栈顶浮动 6 栈有关概念 栈顶指针 在栈操作过程中,有一个专门的栈指针(习惯上称它为TOP),指出栈顶元素所在的位置。 栈空的条件: top = -1 栈满的条件: top = MAXSIZE-1 栈上溢 栈空间是有限的,若栈已满,再进行入栈操作时,就要产生上溢。 栈下溢 若栈空,再要执行出栈操作,则会发生下溢。 7 2、栈的基本运算 Setnull(Stack) 置栈为空; Empty(Stack) 判定栈是否为空; Push(Stack,x)进栈操作,在栈顶插入元素; Pop(Stack) 出栈操作,删除栈顶元素; Gettop(Stack) 取栈顶元素 8 例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 9 3、栈的顺序存储结构 (1)栈的顺序存储结构:实际上是一维数组。 (2)顺序栈:栈的顺序存储结构称为顺序栈。 栈的操作只能在一端进行;即栈顶位置随进栈和出栈而变化。 (3)顺序栈的C语言描述(初始化、定义): #define MAXSIZE n int stack[MAXSIZE]; int top = -1; 10
