第2章总结基本习题.doc

第二章:线性表---------------------------------------------------- 本章的重点是掌握顺序表和单链表上实现的各种基本算法; 难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。--------------------------------------------------------------------- 线性表的逻辑结构特征是很容易理解的,如其名,它的逻辑结构特征就好象是一条线,上面打了一个个结,很形象的,如果这条线上面有结,那么它就是非空表, 只能有一个开始结点,有且只能有一个终端结点,其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。关于线性表上定义的基本运算,主要有构造空表、求表长、取结点、查找、插入、删除等。--------------------------------------------------------------------- 线性表的链式存储结构。链表是用一组任意的存储单元来存放线性表的结点,这组存储单元可以分布在内存中任何位置上。因此,链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。对于单链表,其操作运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入运算、删除运算等。以上各运算的平均时间复杂度均为 O(n). 其主要时间是耗费在查找操作上。-------------------------------------------------------------------- 循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向 NULL 空而是指向开始结点(也可设置一个头结点),形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是 O(1) ,不用遍历整个链表了。判别链表终止的条件也不同于单链表,它是以指针是否等于某一指定指针如头指针或尾指针来确定。--------------------------------------------------------------------- 双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior, 这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋结点可以和查找其直接后继结点的时间一样缩短为 O(1) 。双链表一般也由头指针 head 惟一确定。双链表也可以头尾相链接构成双(向)循环链表。------------------------------------------------------------------ 关于顺序表和链表的比较基于空间:适于线性表长度变化不大,易于事先确定其大小时采用。适于当线性表长度变化大,难以估计其存储规模时采用。基于时间:由于顺序表是一种随机存储结构,当线性表的操作主要是查找时, 宜采用。链表中对任何位置进行插入和删除都只需修改指针,所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单