电子斜技大学 软件技术基础 3.2线性结构之线性表-2 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
1、什么是线性结构 定义：有且仅有一个起始元素（无直接前趋，仅有一个直接后 继)，一个终点元素（无直接后继，仅有一个直接前趋），其余内 部元素各有一个直接前趋和一个直接后继的有限有序序列。 B 3 E ·常见类型：线性表、堆栈、队列、数组、串等 电子科技大学刘民岷 线性表 2
电子科技大学 刘民岷 线性表 2 • 定义：有且仅有一个起始元素(无直接前趋，仅有一个直接后 继)，一个终点元素(无直接后继，仅有一个直接前趋)，其余内 部元素各有一个直接前趋和一个直接后继的有限有序序列。 • 常见类型：线性表、堆栈、队列、数组、串等 B 1 2 3 E
3、线性表-物理存储结构 顺序存储结构 逻辑上连续，物理上也连续 数据域 dl d2 dn ·链式存储结构 一物理上可以不连续，逻辑关系由指针表示 数据域 指针域 dl d2 dn 电子科技大学刘民岷 线性表 3
电子科技大学 刘民岷 线性表 3 • 顺序存储结构 – 逻辑上连续，物理上也连续 • 链式存储结构 – 物理上可以不连续，逻辑关系由指针表示 d1 d2 …… dn 数据域 d1 d2 ... dn ^ 数据域 指针域
3.2线性表物理存储结构之链式存储 线性表的顺序存储结构容易实现，可以随机存取表中的任意 元素。 顺序表缺点是： 一难于插入、删除操作； 需要预先分配空间，不管这些空间能否最大限度地利用。 链表存储结构在这两个方面的优点： 一插入、删除操作容易 不需要预分空间。 。链表的元素一节点： data next 数据域 指针域 电子科技大学刘民岷 线性表 4
电子科技大学 刘民岷 线性表 4 • 线性表的顺序存储结构容易实现，可以随机存取表中的任意 元素。 • 顺序表缺点是： – 难于插入、删除操作； – 需要预先分配空间，不管这些空间能否最大限度地利用。 • 链表存储结构在这两个方面的优点： – 插入、删除操作容易 – 不需要预分空间。 • 链表的元素—节点： data next 数据域 指针域
3.2.1单向链表 链表(Link):由结点组成的表。 头指针(head):指向链表中第1个结点的指针。 头结点：为方便操作，在头指针和头结点之间设置的结点。 首元结点：第一个结点(al)。 头指针 head 头结点 首元结点 第个结点 a a 为什么要增加头结点？ 电子科技大学刘民岷 线性表 5
电子科技大学 刘民岷 线性表 5 ▪ 链表(Link):由结点组成的表。 ▪ 头指针(head): 指向链表中第1个结点的指针。 ▪ 头结点: 为方便操作，在头指针和头结点之间设置的结点。 ▪ 首元结点: 第一个结点(a1)。 head a1 头指针 头结点 首元结点 a i ... 第i个结点 ... 为什么要增加头结点？