电子斜技大学 软件技术基础 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个结点 ... 为什么要增加头结点？
为什么要增加头结点？ 1)空表和非空表表示形式在头结点上得到统一 空表的形式：head->Next=NU儿L head 头结点 非空表的形式： head -Next Address head 头结点 电子科技大学刘民岷 线性表 6
电子科技大学 刘民岷 线性表 6 为什么要增加头结点？ 1） 空表和非空表表示形式在头结点上得到统一 – 空表的形式 : head -> Next = NULL – 非空表的形式: head -> Next = Address head ^ 头结点 head 头结点
为什么要增加头结点？ 2) 若没有头结点，空表和非空表的表示形式将不统一 空表形式： head NULL head -非空表形式：head->Next=Address head al 电子科技大学刘民岷 线性表 7
电子科技大学 刘民岷 线性表 7 为什么要增加头结点？ ２） 若没有头结点, 空表和非空表的表示形式将不统一 –空表形式: head = NULL –非空表形式: head -> Next = Address head head a1
3.2.1单向链表-示例 由食品组成的单链表 (biscuit,butter,cheese,eggs,grapes,jam) ·不带头结点。 头指针 head biscuit butter cheese eggs grapes lam 电子科技大学刘民岷 线性表 8
电子科技大学 刘民岷 线性表 8 • 由食品组成的单链表 （biscuit,butter,cheese,eggs,grapes,jam) • 不带头结点。 biscuit butter cheese eggs grapes jam ^ head 头指针
3.2.1单向链表-示例 •单链表在存储区的物理状态 存储地址 数据域(data) 指针域(next) 1 Grapes 60 11 biscuit 61 12 cheese 13 13 eggs 1 11 头指针 60 jam NULL head 61 butter 12 电子科技大学刘民岷 线性表 9
电子科技大学 刘民岷 线性表 9 •单链表在存储区的物理状态 存储地址 数据域（data） 指针域（next） Grapes 60 biscuit 61 cheese 13 eggs 1 jam NULL butter 12 1 11 12 13 60 61 11 头指针 head
3.2.1单向链表-基本运算 [算法41单链表的插入算法 线性表a1a2,…,a,用带头节点的单链表存储，要求在a 之前插入一个元素为x的节点。 单链表插入算法操作步骤： stepl 找到a1的位置，使指针p指向a.l step2申请并生成新结点s ● step3使s插入到a.和a之间 t->next=p->next p->next=t ai1 t->data=x 电子科技大学刘民岷 线性表 10
电子科技大学 刘民岷 线性表 10 [算法４] 单链表的插入算法 线性表a1 ,a2 ,…,an ,用带头节点的单链表存储，要求在ai 之前插入一个元素为ｘ的节点。 单链表插入算法操作步骤: • step1 找到ai-1的位置,使指针p指向ai-1 • step2 申请并生成新结点s • step3 使s插入到ai-1和ai之间 t->next=p->next p->next=t t->data=x s ai-1 ai p x ｔ