第章线性链表 线性结构特点:在数据元素的非空有限集中 ★存在唯一的一个被称作“第一个”的数据元素 ★存在唯一的一个被称作“最后一个”的数据元素 ★除第一个外,集合中的每个数据元素均只有一个 前驱 ★除最后一个外,集合中的每个数据元素均只有 个后继
第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)datadata表示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) 线性链表 ❖定义：结点中只含一个指针域的链表叫~，也叫单链表
头结点:在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空 头结点 al 空表
头结点：在单链表第一个结点前附设一个结点叫~ 头结点指针域为空表示线性表为空 h a1 a2 头结点 …... an ^ h ^ 空表
今单链表的基本运算 0查找:查找单链表中是否存在结点X。若有则返回指向X结点 的指针:否则返回NULL ◆算法描述 Ch2 3. txt ◆算法评价 若找到结点X,为结点X在表中的序号 Whil循环中语句频度为 7(n)=O(n) 否则,为n ●插入:在线性表两个数据元素a和b间插入X,已知p指向a p=a b p->link-s; s S->link=p->link ◆算法描述 Cha 4 txt ◆法评价T(n)=O(1)
❖单链表的基本运算 ⚫查找：查找单链表中是否存在结点X，若有则返回指向X结点 的指针；否则返回NULL ◆算法描述 While循环中语句频度为 若找到结点X，为结点X在表中的序号 否则，为n T(n) = O(n) p a b s x ◆算法评价 ⚫插入：在线性表两个数据元素a和b间插入x，已知p指向a p s->link=p->link; ->link=s; T(n) = O(1) ◆算法描述 ◆算法评价
●删除:单链表中删除b,设指向a p X bX p->link=-p->link->link ◆算法描述 ch2 5. bt ◆算法评价 T(n)=O()
◆算法描述 p a b c T(n) = O(1) ◆算法评价 ⚫删除：单链表中删除b，设p指向a p->link=p->link->link;
动态建立单链表算法:设线性表n个元素已存放在数组a中, 建立一个单链表,h为头指针 ◆算法描述 Ch2 6. txt 头结点 ◆算法评价 (n)=O( Ch2 3.c
T(n) = O(n) ⚫动态建立单链表算法：设线性表n个元素已存放在数组a中， 建立一个单链表，h为头指针 ◆算法描述 ◆算法评价 h 头结点 h 0 an ^ 头结点 h 0 an-a12 an…...^ 头结点 h 0 a1 a2 an-1 an ^ 头结点 0 …... an ^ Ch2_3.c h 头结点 0 ^
今单链表特点 ●它是一种动态结构,整个存储空间为多个链表共用 0不需预先分配空间 ●指针占用额外存储空间 ●不能随机存取。查找速度慢
❖单链表特点 ⚫它是一种动态结构，整个存储空间为多个链表共用 ⚫不需预先分配空间 ⚫指针占用额外存储空间 ⚫不能随机存取，查找速度慢