数据结构答案线性表学习指导.docVIP

第2章　线性表 2.1 知识点分析　 1．线性表的定义 线性表是具有相同数据类型的n（n=0）个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 在线性表中相邻元素之间存在着顺序关系。对于元素ai 而言，ai-1 称为 ai 的直接前驱，ai+1 称为 ai 的直接后继。也就是说： （1）有且仅有一个开始结点（a1），它没有直接前驱； （2）有且仅有一个终端结点（an），它没有直接后继； （3） 除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。 2．顺序表 顺序表是线性表的顺序存储，是指在内存中分配一组连续的存储单元依次存储线性表的数据元素，元素之间的结构（关系）无需存放，顺序表的逻辑顺序和物理顺序是一致的。 常用的顺序表的操作（运算）有建立顺序表、插入、删除、查找、访问、更新等。 3．线性链表 线性链表（单链表）是线性表的链接式存储，在内存中分配存储单元可以是连续的，也可以是不连续的地址，存储单元中存放数据元素信息（数据域）和存放其后继结点地址（指针域）。 常用的线性链表操作（运算）有建立链表、插入、删除、查找、访问、更新、求表长等。 4．顺序表和线性链表的比较 顺序表 优点：空间利用率高；可以随机存取表中任意一个元素，存储位置可以用公式：B+(i-1)*d 计算。 缺点：对顺序表作插入、删除时需要通过移动大量的数据元素，时间性能差；线性表预先分配空间时，必须按最大空间分配，存储空间得不到充分的利用；表的容量难以扩充（对有些高级语言而言）。 单链表 优点：对表作插入、删除时无需移动数据元素，时间性能好；因为动态分配存储空间，不会发生溢出现象；查找元素必须从首元素开始查找，比较费时。 缺点：空间利用率2.2 典型习题分析 【例1】带头结点单链表L为空的判断条件是（ ）。 A．L= =NULL B．L-next= = NULL C．L-next==L D．L！=NULL 分析：带头结点的单链表为空表如图2-1所示。 　　　　　　　　 L 　　　　　　　　　　　　　　　　　　L　　 　　　　　　　　　　　 　　　　图2-1带头结点的单链表　　　　　 图2-2　带头结点的循环单链表 　所以其判断条件可以表示为L－＞next==NULL(注意用双==号)，如果单链表不带头结点，则其空判断条件是L==NULL，如果是循环单链表，其空判断条件是L-next==L,如图2-2所示，故答案为B。 【例2】在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。 A． 访问第i个结点(1=i=n)和求第i个结点的直接前驱(2=i=n) B． 在第i个结点之后插入一个新结点(1=i=n) C． 删除第i个结点(1=i=n) D． 将n个结点从小到大排序 分析：在顺序表中第i个结点之后插入一个新结点(1=i=n)，在其后结点都要顺序往后移动，所以时间复杂度为O（n），B不能选。顺序表删除第i个结点(1=i=n)，在其后结点都要顺序往前移动，所以时间复杂度为O（n），C不能选。在顺序表中，将n个结点从小到大排序，时间复杂度大于O（n）（在第9章讨论），D不能选。在顺序表中访问第i个结点,其地址可有公式直接计算出，因此时间复杂度为O（1），同样第i结点的直接前趋i-1结点，其时间复杂度也为O（1），故选A。 【例3】在具有n个结点的单链表中，实现（ ）的操作，其算法的时间复杂度是O( n )。 A．求链表的第i个结点 B．在地址为P的结点之后插入一个结点 C．删除开始结点 D．删除地址为P的结点的后继结点 分析：由单链表知在地址为P的结点之后插入一个结点，如图2-3所示，只需修改指针，即：①s-next=p-next;　②p-next=s;时间复杂度是O(1)，B不能选。删除开始结点只需要修改头结点，H-next=H-next-next;就可以了，时间复杂度是O(1)，C不能选。删除地址为P的结点的后继结点，如图2-4所示，p-next=p-next-next就可以，时间复杂度是O(1)，D不能选。求链表的第i个结点，必须从头结点开始，如图2-所示，其时间复杂度是O(n),故选A。 【例4】在n个结点的单链表中要删除已知结点*P，需要找到 （1） ，其时间复杂度为 （2） 。而在双链表中要删除已知结点*P，其时间复杂度为 （3） 。 分析：（1）在单链表中删除一个结点，必须找到其前趋结点，应该应填写其前趋结点。 （2）在单链表中找一个结点必须从首结点开始查找，所以单链表查找结点