《第2章之线性链表》由会员分享，可在线阅读，更多相关《第2章之线性链表（41页珍藏版）》请在金锄头文库上搜索。
1、下一页 上一页 停止放映 第 2章之 线性链表 西安交通大学计教中心 一页 上一页 停止放映 第 2页 /41 采用链式存储结构的线性表有单链表、双向链表、单循环链表以及双向循环链表等多种形式。 单链表用一组地址任意的存储单元存放线性表中的数据元素。由于逻辑上相邻的元素其物理位置不一定相邻，为了建立元素间的逻辑关系，需要在线性表的每个元素中附加其后继元素的地址信息。 这种地址信息称为指针。附加了其他元素指针的数据元素称为结点。 单链表的概念 下一页 上一页 停止放映 第 3页 /41 结点定义 结点结构可描述为 : 据域 指针域 其中 类型由具体问题而定 ， 本节也将其设定为 C+语言描述为：
2、 / 数据域 / 指针域 *下一页 上一页 停止放映 第 4页 /41 带头结点单链表的逻辑结构 为了能顺次访问每个结点，需要保存单链表第一个结点的存储地址。这个地址称为线性表的头指针，本节用 为了操作上的方便，可以在单链表的头部增加一个特殊的头结点。头结点的类型与其他结点一样，只是头结点的数据域为空。 增加头结点避免了在删除或添加第一个位置的元素时进行的特殊程序处理。 a1 a2 带头结点的单链表 下一页 上一页 停止放映 第 5页 /41 链表（ 由结点组成的表。 头指针（ 指向链表中第 1个结点的指针。 头结点 为方便操作，在头指针和头结点之间设置的结点。 首元结点 第一个结点（ 基本概
3、念 指针 头结点 首元结点 a i . 第 下一页 上一页 停止放映 第 6页 /41 表示形式的统一 空表和非空表表示形式在头结点上得到统一 空表的形式 : 头结点 结点 非空表的形式 : 一页 上一页 停止放映 第 7页 /41 表示形式不统一 若没有头结点 , 空表和非空表的表示形式不统一。 空表形式 : 非空表形式 : 一页 上一页 停止放映 第 8页 /41 带头结点单链表的存储结构 38 数据域 数据域 38 22 94 86 86 94 22 存储地址 单链表存储结构示意图 下一页 上一页 停止放映 第 9页 /41 结点的 c+描述 /数据域 ,* /指针域 *这个定义是自引用
4、类型的。每个结点都包含另一个同类型结点的地址。 下一页 上一页 停止放映 第 10页 /41 指针操作 假如 该结点的数据域用 p-结点的指针域用 p-们都是变量，可以被赋值，也可向其他变量赋值。 例如 : 假定 则 p-; p-将 结点变为 : 5 N U L L n e x t 下一页 上一页 停止放映 第 11页 /41 指针的基本操作列表 p= 申请一个结点空间 ,并将地址送入 p） 释放 p=q 指针 p=q-针 p=p-针 p-q 将指针 p-指针 下一页 上一页 停止放映 第 12页 /41 指针操作的举例 1 申请一个结点空间 ,并将地址送入 p 操作前状态 操作后状态 p p
5、= 一页 上一页 停止放映 第 13页 /41 指针操作的举例 2 p=p- 指针右移一个结点位置。 ai ai p p 操作前状态 操作后状态 p p 下一页 上一页 停止放映 第 14页 /41 指针操作的举例 3 p=q- ai ai q q p p 操作前状态 操作后状态 下一页 上一页 停止放映 第 15页 /41 常用算法 （ 1） 求单链表的长度 单链表长度计数算法操作步骤 : 初始化 ,指针 数器置 0 每循环一次 , 计数器加 1 循环结束 ,返回计数器值 。 下一页 上一页 停止放映 第 16页 /41 求单链表长度算法程序 p= /； p!= / 循环 p = p- /指
6、针右移 +； /返回长度 下一页 上一页 停止放映 第 17页 /41 （ 2） 从单链表中删除第 q p ai p=q-q-p-p; 找到 使指针 使指针 使 链 释放 p 示例 下一页 上一页 停止放映 第 18页 /41 i ) if(k+; if(p= p- /从链表中删除该结点 p; /释放结点 p 删除算法 C+源程序 下一页 上一页 停止放映 第 19页 /41 （ 3） 在第 x 在链表的第 进行如下操作： s- x; s-p-p-s; ai p x s 1 2 找到 使指针 申请并生成新结点 s 使 示例 下一页 上一页 停止放映 第 20页 /41 i, x) if(k+;
7、 if(p= x; s-p-s; /修改结点 插入算法 C+源程序 下一页 上一页 停止放映 第 21页 /41 （ 4） 在单链表中查找数据值为 返回指向第 单链表查找算法操作步骤 : 初始化 ,指针 每循环一次 , 循环结束 ,返回指向 ，或空指针 。 下一页 上一页 停止放映 第 22页 /41 x ) p= / p!=& p-x ) /寻找 p = p- /指针右移 p!=&(p-x ) p; /找到了，返回地址 /没找到返回空指针 查找算法 C+源程序 下一页 上一页 停止放映 第 23页 /41 其他形式的链表 链表检索只能从头指针开始 ,且只能顺链表方向移动。 在单链表中 ,从表
8、的任一结点 时间复杂度是 O（ n）。 如果让链表首尾相接，构成环形，这就是单循环链表 。 链表可以从两个方向检索，效果更佳；这就是 双向循环链表 。 下一页 上一页 停止放映 第 24页 /41 单循环链表 单循环链表表示形式： . a1 a2 循环链表为空的条件 : 示形式为 : 下一页 上一页 停止放映 第 25页 /41 单循环链表特点 从表中任一结点出发 ,均可以找到表中其它结点。 找其前趋结点的时间复杂度是 O（ n）。 下一页 上一页 停止放映 第 26页 /41 双向循环链表 在单向循环链表中，也存在检索前趋结点费时的问题（所需时间是 O（ n）。 双向循环链表，其存储结构： /数据域 * / 指针域 *下一页 上一页 停止放映 第 27页 /41 双向循环链
