DATA STRUCTURES 链表 存储地址「数据域指针域 头指针 21 13 43 31 13 7 入 31 43 构成顺序表:(4,21,9,8,5) Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 链表 4 1 5 ^ 9 7 8 31 21 13 数据域 指针域 43 头指针 存储地址 1 7 13 31 43 构成顺序表： （4，21，9，8，5）
DATA STRUCTURES 23单链表 特点 每个元素表项)由结点(Nd)构成。 data link 线性结构 ft→caaa{a囚 last 结点可以不连续存储 表可扩充 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 2.3 单链表 data link • 特点 – 每个元素(表项)由结点(Node)构成。 – 线性结构 – 结点可以不连续存储 – 表可扩充
DATA STRUCTURES 单链表的存储映像 free (a)可利用存储空间 first free (b)经过一段运行后的单链表结构 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 单链表的存储映像 free (a) 可利用存储空间 a0 a2 a1 a3 free first (b) 经过一段运行后的单链表结构
DATA STRUCTURES 单链表的类定义 使用面向对象方法,把数据与操作一起定义和 封装,用多个类表达一个单链表。 ◆链表结点( ListNode)类 链表L淡类 定义方式 ◆复合方式 嵌套方式 ◆继承方式 结构方式 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 单链表的类定义 ◼ 使用面向对象方法，把数据与操作一起定义和 封装，用多个类表达一个单链表。 ◆ 链表结点(ListNode)类 ◆ 链表(List)类 ◼ 定义方式 ◆ 复合方式 ◆ 嵌套方式 ◆ 继承方式 ◆ 结构方式
DATA STRUCTURES class lis 复合方式 class listnode i 链表结点类 friend class list 链表类为其友元类 private int data 结点数据,整型 Listnode x link /结点指针 class List i 链表类 private ListNode first;表头指针 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES class List; //复合方式 class ListNode { //链表结点类 friend class List; //链表类为其友元类 private: int data; //结点数据, 整型 ListNode * link; //结点指针 }; class List { //链表类 private: ListNode *first ; //表头指针 };