北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第二章 线性表、栈和队列

几种主要链表比较 单链表frst ao a1|a2…,an1 空的单链表 first last last 循环链表 first-ao a1 a2 少an-1 空的循环链表 first last last 双向链表 a0+a¨∷,an-1 last 循环双向链表 first ao 十-a1"∷ back ast 北京大学信息学院张铭编写 ⊙版权所有,转载或翻印必 age 26

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 back next 几种主要链表比较 first a0 a1 a2 an-1 last 单链表 空的单链表 first last first a0 a1 a2 an-1 last 循环链表 空的循环链表 first last first last a0 a1 an-1 双向链表 循环双向链表 first last a0 a1 an-1

注意指针变量的有效性 记得使用new 使用新指针变量,或要生成一个新结 点前先执行new操作 不要引用NUL指针 使用指针前,先用ⅱ语句(或 while循 环条件中的语句)判断它非空 不用引用 Delete了的指针 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 27

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 back next 注意指针变量的有效性 „ 记得使用new „ 使用新指针变量，或要生成一个新结 点前先执行new操作 „ 不要引用NULL指针 „ 使用指针前，先用if语句（或while循 环条件中的语句）判断它非空 „ 不用引用Delete了的指针

注意链表的边界处理 ■几个特殊点的处理 头指针处理 非循环链表尾结点的指针域保持为NULL n循环链表尾结点的指针回指头结点 链表处理 空链表的特殊处理 插入或删除结点时指针勾链的顺序 ■指针移动的正确性 插入 back 查找或遍历 北京大学信息学院张铭编 版权所有,转载或翻印必究 age 28

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 back next 注意链表的边界处理 „ 几个特殊点的处理 „ 头指针处理 „ 非循环链表尾结点的指针域保持为NULL „ 循环链表尾结点的指针回指头结点 „ 链表处理 „ 空链表的特殊处理 „ 插入或删除结点时指针勾链的顺序 „ 指针移动的正确性 „ 插入 „ 查找或遍历

24线性表实现方法的比较 顺序表的主要优点 ■没用使用指针,不用花费附加开销 线性表元素的读访问非常简洁便利 链表的主要优点 无需事先了解线性表的长度 n允许线性表的长度有很大变化 能够适应经常插入删除内部元素的情况 back 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 29

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 back next 2.4 线性表实现方法的比较 „ 顺序表的主要优点 „ 没用使用指针，不用花费附加开销 „ 线性表元素的读访问非常简洁便利 „ 链表的主要优点 „ 无需事先了解线性表的长度 „ 允许线性表的长度有很大变化 „ 能够适应经常插入删除内部元素的情况

应用场合的选择 不要使用顺序表的场合 经常插入删除时,不宜使用顺序表 线性表的最大长度也是一个重要因素 不要使用链表的场合 当读操作比插入删除操作频率大时, 不应选择链表 当指针的存储开销,和整个结点内容 所占空间相比其比例较大时,应该慎 back 重选择 北京大学信息学院张铭编写 版权所有,转载或翻印必究 age 30

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 back next 应用场合的选择 „ 不要使用顺序表的场合 „ 经常插入删除时，不宜使用顺序表 „ 线性表的最大长度也是一个重要因素 „ 不要使用链表的场合 „ 当读操作比插入删除操作频率大时， 不应选择链表 „ 当指针的存储开销，和整个结点内容 所占空间相比其比例较大时，应该慎 重选择