第章线性链表 线性结构特点:在数据元素的非空有限集中 ★存在唯一的一个被称作“第一个”的数据元素 ★存在唯一的一个被称作“最后一个”的数据元素 ★除第一个外,集合中的每个数据元素均只有一个 前驱 ★除最后一个外,集合中的每个数据元素均只有 个后继
第3章线性链表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个 前驱 除最后一个外，集合中的每个数据元素均只有一 个后继
★顺序存储结构的优缺点 今优点 逻辑相邻,物理相邻 可随机存取任一元素 存储空间使用紧凑 心缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配,利用不充分 ●表容量难以扩充
顺序存储结构的优缺点 ❖优点 ⚫逻辑相邻，物理相邻 ⚫可随机存取任一元素 ⚫存储空间使用紧凑 ❖缺点 ⚫插入、删除操作需要移动大量的元素 ⚫预先分配空间需按最大空间分配，利用不充分 ⚫表容量难以扩充
§线性表的链式存储结构 特点: 今用一组任意的存储单元存储线性表的数据元素 今利用指针实现了用不相邻的存储单元存放逻辑上相邻 的元素 今每个数据元素a,除存储本身信息外,还需存储其直 接后继的信息 今结点 结占 ●数据域:元素本身信息 ●指针域:指示直接后继的存储位置数据域指针域
§ 线性表的链式存储结构 特点： ❖用一组任意的存储单元存储线性表的数据元素 ❖利用指针实现了用不相邻的存储单元存放逻辑上相邻 的元素 ❖每个数据元素ai，除存储本身信息外，还需存储其直 接后继的信息 ❖结点 ⚫数据域：元素本身信息 ⚫指针域：指示直接后继的存储位置 数据域 指针域 结点
例线性表( ZHAO QIAN, SUNLLZHOU, WUZHENG,WANG) 存储地址数据域指针域 43 头指针 7 OⅠAN 13 H 13 SUN 31 19 WANG NULL 25 WU 37 31 ZHAO 37 ZHENG 43 ZHOU 25 ZHAO QIAN SUN ZHOU WU ZHENG WANG|∧
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 头指针
★线性链表 今定义:结点中只含一个指针域的链表叫~,也叫单链表 实现 typedef struct node{ datatype data struct node *link JJD JD h, p datalink(*p)表示p所指向的结点 (*p)data<→p>data表示p指向结点的数据域 结点(*p (*p)link→>p-列ik表示p指向结点的指针域 生成一个型新结点:p=(JD* malloc( sizeof(JD) 系统回收p结点: free(p)
❖实现 typedef struct node { datatype data; struct node *link; }JD; JD *h,*p; data link p 结点（*p） (*p)表示p所指向的结点 (*p).datap->data表示p指向结点的数据域 (*p).linkp->link表示p指向结点的指针域 生成一个JD型新结点：p=(JD *)malloc(sizeof(JD)); 系统回收p结点：free(p) 线性链表 ❖定义：结点中只含一个指针域的链表叫~，也叫单链表