清华大学：《C++数据结构》第三章 链表

第三章链表 单链表 多项式及相加 双向链表 稀疏矩阵

◼ 单链表 ◼ 循环链表 ◼ 多项式及其相加 ◼ 双向链表 ◼ 稀疏矩阵

单链表( Singly Linked List) 特点 ◆每个元素表项由结点(Noe)构成。 data link ◆线性结构 first→a0 结点可以连续,可以不连续存储 ◆结点的逻辑顺序与物理顺序可以不一致 表可扩充

单链表 (Singly Linked List) ◼ 特点 ◆ 每个元素(表项)由结点(Node)构成。 ◆ 线性结构 ◆ 结点可以连续，可以不连续存储 ◆ 结点的逻辑顺序与物理顺序可以不一致 ◆ 表可扩充 data link first a0 a1 a2 a3 a4 

单链表的存储映像 free (a)可利用存储空间 first fir ree (b)经过一段运行后的单链表结构

单链表的存储映像 free (a) 可利用存储空间 a0 a2 a1 a3  free first (b) 经过一段运行后的单链表结构

单链表的类定义 多个类表达一个概念单链表) ◆链表结点( Listnode)类 ◆链表(List)类 ◆链表游标( Iterator)类 定义方式 ◆复合方式 ◆嵌套方式 ◆继承方式

单链表的类定义 ◼ 多个类表达一个概念(单链表)。 ◆ 链表结点(ListNode)类 ◆ 链表(List)类 ◆ 链表游标(Iterator)类 ◼ 定义方式 ◆ 复合方式 ◆ 嵌套方式 ◆ 继承方式

class list. ∥1表类定义(复合方式) class ListNode i ∥链表结点类 friend class lists ∥链表类为其友元类 p rivate. int data; ∥/结点数据,整型 Listnode x link /结点指针 class list i ∥/链表类 privates Listnode*frst,*1ast;/表头指针

class List; //链表类定义（复合方式） class ListNode { //链表结点类 friend class List; //链表类为其友元类 private: int data; //结点数据, 整型 ListNode * link; //结点指针 }; class List { //链表类 private: ListNode *first , *last; //表头指针 };

class list 链表类定义(嵌套方式) private. class ListNode i ∥套链表结点类 public int data Listnode link. Listnode*frst,料last;/表头指针 public ∥链表操作

class List { //链表类定义(嵌套方式) private: class ListNode { //嵌套链表结点类 public: int data; ListNode *link; }; ListNode *first , *last; //表头指针 public: //链表操作……… };

链表类和链表结点类定义(继承方式) class listnode i ∥链表结点类 p rotected int data: Listnode class list: public class ListNode i ∥/链表类,继承链表结点类的数据和操作 privates Listnode*frst,*1ast;/表头指针

链表类和链表结点类定义(继承方式) class ListNode { //链表结点类 protected: int data; ListNode * link; }; class List : public class ListNode { //链表类, 继承链表结点类的数据和操作 private: ListNode *first , *last; //表头指针 };

单链表中的插入与删除 插入 ◆第一种情况:在第一个结点前插入 newnode->link= first i first= newnode; newnode newnode first first 十一_ (插入前) (插入后)

单链表中的插入与删除 ◼ 插入 ◆ 第一种情况：在第一个结点前插入 newnode->link = first ; first = newnode; （插入前） （插入后） first newnode newnode first

第二种情况:在链表中间插入 newnode->link=p->link p->ink= newnode newnode-L newnode p (插入前) (插入后)

(插入前) (插入后) ◆ 第二种情况：在链表中间插入 newnode->link = p->link; p->link = newnode； newnode p newnode p

。第三种情况:在链表末尾插入 newnode->link= p->link; p->link= newnode i newnode→ newnode-入 p (插入前) (插入后)

◆ 第三种情况：在链表末尾插入 newnode->link = p->link; p->link = newnode； (插入前) (插入后) newnode newnode p p  