数据结构第二章串讲+复习要点

数据结构第二章串讲+复习要点  

　　本章的 重点 是掌握 顺序表 和 单链表 上实现的各种基本算法及相关的时间性能分析 难点 是使用本章所学的基本知识 设计有效算法 解决与线性表相关的应用问题

　　要求达到< 识记 >层次的内容有:线性表的逻辑结构特征;线性表上定义的基本运算 并利用基本运算构造出较复杂的运算

　　要求达到< 综合应用 >层次的内容有 顺序表的含义及特点 顺序表上的插入 删除操作及其平均时间性能分析 解决简单应用问题

　　链表如何表示线性表中元素之间的逻辑关系;单链表 双链表 循环链表链接方式上的区别; 单链表上实现的建表 查找 插入和删除等基本算法及其时间复杂度 循环链表上尾指针取代头指针的作用 以及单循环链表上的算法与单链表上相应算法的异同点 双链表的定义和相关算法 利用链表设计算法解决简单应用问题

　　要求达到< 领会 >层次的内容就是顺序表和链表的比较 以及如何选择其一作为其存储结构才能取得较优的时空性能

　　线性表 的 逻辑结构特征 是很容易理解的 如其名 它的逻辑结构特征就好象是一条线 上面打了一个个结 很形象的 如果这条线上面有结 那么它就是非空表 只能有一个 开始结点 有且只能有一个 终端结点 其它的结前后所相邻的也只能是一个结点( 直接前趋 和 直接后继 )

　　关于线性表上定义的基本运算 主要有构造空表 求表长 取结点 查找 插入 删除等

　　线性表 的 逻辑结构 和 存储结构 之间的关系 在计算机中 如何把线性表的结点存放到存储单元中 就有许多方法 最简单的方法就是 按顺序存储 就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中 在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的

　　在顺序表中实现的基本运算主要讨论了 插入 和 删除 两种运算 相关的算法我们通过练习掌握 对于顺序表的插入和删除运算 其平均时间复杂度均为 O(n)

　　线性表的 链式存储结构 它与顺序表不同 链表 是用一组 任意的存储单元 来存放线性表的结点 这组存储单元可以分布在内存中任何位置上 因此 链表中结点的逻辑次序和物理次序不一定相同 所以为了能正确表示结点间的逻辑关系 在存储每个结点值的同时 还存储了其后继结点的地址信息(即指针或链) 这 两部分信息组成链表中的结点结构

　　一个单链表由头指针的名字来命名

　　对于单链表 其操作运算主要有 建立单链表 (头插法 尾插法和 在链表开始结点前附加一个 头结点 的算法) 查找 (按序号和按值) 插入 运算 删除 运算等 以上各运算的平均时间复杂度均为 O(n) 其主要时间是耗费在查找操作上

　　循环链表 是一种首尾相接的链表 也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点) 形成一个环 采用循环链表在实用中多采用尾指针表示单循环链表 这样做的好处是查找头指针和尾指针的时间都是O( ) 不用遍历整个链表了

　　判别链表终止的条件也不同于单链表 它是以指针是否等于某一指定指针如头指针或尾指针来确定

　　双链表 就是双向链表 就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior 这样形成的链表就有 两条不同方向的链 使得从已知结点查找其 直接前趋 结点可以和查找其 直接后继 结点的时间一样缩短为 O( )

　　双链表 一般也由头指针head惟一确定 双链表也可以头尾相链接构成 双(向)循环链表

　　关于顺序表和链表的比较 请看下表

　　具体要求 顺序表 链表

　　基于空间 适于线性表长度变化不大 易于事先确定其大小时采用 适于当线性表长度变化大 难以估计其存储规模时采用

　　基于时间 由于顺序表是一种随机存储结构 当线性表的操作主要是查找时 宜采用 链表中对任何位置进行插入和删除都只需修改指针 所以这类操作为主的线性表宜采用链表做存储结构 若插入和删除主要发生在表的首尾两端 则宜采用尾指针表示的单循环链表

　　第二章 线性表 复习要点

　　本章复习要点是

　　线性表的逻辑结构特征 常见的线性表的六种基本运算 并可以根据这些基本运算组合得到更复杂的运算

　　顺序表的特征 顺序表中结点地址的计算

　　顺序表上实现的基本运算(算法) 主要是插入和删除的算法 顺序表的算法应该掌握 算法时间复杂度要记住

　　单链表的特征 图形表示法

　　单链表的各种算法实现 并能运用这些算法解决一些简单问题;

　　循环链表的特征 双链表的特征以及它们的主要算法实现

　　可能出的题型有 填空题 简答题 应用题和算法题

　　如

　　在双链表中插入运算的时间复杂度为 ( )

　　A O( ) B O(n) C O(lgn) D O(nlgn)

　　请问头指针 开始结点和头结点的区别与联系

　　关于单链表上进行排序的算法设计