4)队列:与堆栈相似队列也是一种特殊的线性表与 堆栈不同的是队列是先进先出的表FFo队列中数据 元素以a1a2an的顺序进入,又以相同的顺序出去 进队 a 出队 特点:先进先出(FIFO),后进后出(LLO 存储:在计算机中用一组连续的单元依次存储队列操作的数据元素 队列指针:用队头指针 front和队尾指针rear来描述队列 后面讲到数字滤浪用到) 11
11 （4）队列：与堆栈相似,队列也是一种特殊的线性表,与 堆栈不同的是,队列是先进先出的表FIFO.队列中数据 元素以a1 ,a2 ,…,an的顺序进入,又以相同的顺序出去. 特点：先进先出（FIFO）,后进后出(LILO). 存储：在计算机中,用一组连续的单元依次存储队列操作的数据元素. 队列指针：用队头指针front和队尾指针rear来描述队列. （后面讲到数字滤波用到） 进队 a n ······ a2 a1 出队
线性表、数组、堆栈和队列的共同特点是: 数据元素要求存放在连续的存储单元中 缺点: 做插入或删除操作时,要移动大量的数据元素,并浪费时 、不易扩展有时为了留有余地将会浪费存储空间
12 线性表、数组、堆栈和队列的共同特点是： 数据元素要求存放在连续的存储单元中. 缺点： 一、做插入或删除操作时,要移动大量的数据元素,并浪费时 间; 二、不易扩展,有时为了留有余地,将会浪费存储空间
2.链形结构 链表由若干个结点组成每个结点有两个域: 个是数据域用来存放数据元素; 个是指针咸用来存放下一个结点的数据域首址 通过指针城把各结点按要求的顺序连接起来组成 个首尾相连的表由于其组成象一条链条故取名为链表 为了确定链表中第一个结点的数据首址设置了头指针 (head);为了标识链表中的最后一个结点将其指针域 设置为“空”(NUL) 13
13 2．链形结构 链表由若干个结点组成,每个结点有两个域： 一个是数据域,用来存放数据元素; 一个是指针域,用来存放下一个结点的数据域首址. 通过指针域把各结点按要求的顺序连接起来组成一 个首尾相连的表,由于其组成象一条链条,故取名为链表. 为了确定链表中第一个结点的数据首址,设置了头指针 （head）;为了标识链表中的最后一个结点,将其指针域 设置为“空”（NUL）
链形结构的最大特点是:在逻辑上是有序的用指针城 指明结点(或数据素)之间的关系西在物上四 的物理位 前图此在使用表时通常只考总它的辑顺而不 链表的三种形式:单链表、循环链表和双重链表 链表的三种运算:插入结点、删除结点和查找结点 head - a 插入结点 neac a 删除结点 14
14 head a1 · a2 · a3 · ······ 删除结点 head a1 · 插入结点 b · a2 · ······ 链形结构的最大特点是：在逻辑上是有序的,用指针域 指明各结点（或数据元素）之间的关系;而在物理上则 可能是无序的,各结点在存储器中的物理位置可以任意 配置.因此在使用链表时,通常只考虑它的逻辑顺序,而不 关心它的实际存储位置. 链表的三种形式：单链表、循环链表和双重链表 链表的三种运算：插入结点、删除结点和查找结点
3.树形结构计算机所管理的数据、信息和文件有 时具有层次关系或上下级关系每个记录有四个域: 记录名、数据、左指针和右指针如果把记录抽象为 一个结点其形状很像一棵倒叉树称为树形结构或 简称树(tree) 结点A 数据 左指针 右指针 15
15 3．树形结构 计算机所管理的数据、信息和文件有 时具有层次关系或上下级关系.每个记录有四个域： 记录名、数据、左指针和右指针.如果把记录抽象为 一个结点,其形状很像一棵倒叉树,称为树形结构,或 简称树（tree）. 左指针 右指针 数据 结点A