ch02_2 线性表2-链式表示和实现.ppt

第2章 线性表 2.3 线性表的链式表示和实现 2.3 .1 链表的表示 特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 与链式存储有关的术语： 何谓头指针、头结点和首元结点？ 例： 结构类型的C语言表示法 介绍三个有用的库函数（都在stdlib.h 中）： sizeof(x)——计算变量x的长度； malloc(m) —开辟m字节长度的地址空间，并返回这段空间的首地址； free(p) ——释放指针p所指变量的存储空间，即彻底删除一个变量。 链表的实现 1. 单链表的插入 2. 单链表的删除 3. 链表的合并 1. 单链表的插入 2. 单链表的删除 3. 两个链表的归并（教材P31） 用链表可表示为： 算法分析： 其它链表形式 讨论2： 单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？ 链表的运算效率分析 1. 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 作业 用链表编写完整程序实现以下内容： 一条记录有学号和成绩两个数据项，建立两个有序表（按成绩由大到小），并合并成一个有序表。第一个表输入的数据如下（学号，成绩）：(1,70),(2,85),(3,75),(4,90)；第二个表输入的数据如下：(5,60),(6,80), (7,76),(8,50)。 * * 数据结构讲义 - 链式表示和实现 信息工程学院 王晟 Email:mssquall@263.net ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 43 13 1 NULL 37 7 19 25 数据域 指针域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存储地址 1 7 13 19 25 31 37 43 31 H 头指针 1、结点：数据元素的存储映像。由数据域和指针域两部分组成； 2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。 3、单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表； 有两个指针域的链表，称为双链表； 有多个指针域的链表，称为多链表； 首尾相接的链表称为循环链表。 a1 head a2 an …… head 循环链表示意图： 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 单链表可由一个头指针唯一确定。 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息; 首元结点是指链表中存储线性表第一个数据元素a1的结点。 头指针 头结点 首元结点 a1 一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？ 25 ZHOU 43 19 ZHENG 37 7 ZHAO 31 37 WU 25 NULL WANG 19 1 SUN 13 13 QIAN 7 43 LI 1 指针域 数据域 存储地址 答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。 7 ZHAO H 31 ∴头指针的值是31 上例链表的逻辑结构示意图有以下两种形式： ① ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H ② ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H 区别：① 无头结点 ② 有头结点 答： 讨论1. 在链表中设置头结点有什么好处？ 讨论2. 如何表示空表？ 头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。 答： 无头结点时，当头指针的值为空时表示空表； 有头结点时，当头结点的指针域为空时表示空表。 ^ 头指针 ^ 头指针 头结点 无头结点 有头结点 typedef struct Lnode { ElemType data; //数据域 struct Lnode *next; //指针域 }Lnode, *LinkList; // *LinkList为Lnode类型的指针 教材P28对