数据结构答案 第2章 线性表学习指导

《数据结构答案 第2章 线性表学习指导》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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．顺序表顺序表是线性表的顺序存储，是指在内存中分配

2、一组连续的存储单元依次存储线性表的数据元素，元素之间的结构（关系）无需存放，顺序表的逻辑顺序和物理顺序是一致的。常用的顺序表的操作（运算）有建立顺序表、插入、删除、查找、访问、更新等。3．线性链表线性链表（单链表）是线性表的链接式存储，在内存中分配存储单元可以是连续的，也可以是不连续的地址，存储单元中存放数据元素信息（数据域）和存放其后继结点地址（指针域）。常用的线性链表操作（运算）有建立链表、插入、删除、查找、访问、更新、求表长等。4．顺序表和线性链表的比较（1）顺序表优点：空间利用率高；可以随机存取表中任意一个元素，存储位置可以用公式：B+(i-1)*

3、d计算。缺点：对顺序表作插入、删除时需要通过移动大量的数据元素，时间性能差；线性表预先分配空间时，必须按最大空间分配，存储空间得不到充分的利用；表的容量难以扩充（对有些高级语言而言）。（2）单链表优点：对表作插入、删除时无需移动数据元素，时间性能好；因为动态分配存储空间，不会发生溢出现象；查找元素必须从首元素开始查找，比较费时。缺点：存储密度小，空间利用率低。2.2典型习题分析【例1】带头结点单链表L为空的判断条件是（）。A．L==NULLB．L->next==NULLC．L->next==LD．L！=NULL分析：带头结点的单链表为空表如图2-1所示。　

4、　　　　　　　＾　　　　　　　　L　　　　　　　　　　　　　　　　　　L　　　　　　　　　　　　　　　　　图2-1带头结点的单链表　　　　　图2-2　带头结点的循环单链表　所以其判断条件可以表示为L－＞next==NULL(注意用双==号)，如果单链表不带头结点，则其空判断条件是L==NULL，如果是循环单链表，其空判断条件是L->next==L,如图2-2所示，故答案为B。13【例2】在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。A．访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)B．在第i个结点之后插入一个新结

5、点(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

6、个结点的单链表中，实现（）的操作，其算法的时间复杂度是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就可以，时间复

7、杂度是O(1)，D不能选。求链表的第i个结点，必须从头结点开始，如图2-所示，其时间复杂度是O(n),故选A。图2-3在*p之后插入*ss×①②图2-4删除*P的后继结点xqp×pan∧图2-5带头结点的单链表a1a2H　…【例4】在n个结点的单链表中要删除已知结点*P，需要找到（1），其时间复杂度为（2）。而在双链表中要删除已知结点*P，其时间复杂度为（3）。分析：（1）在单链表中删除一个结点，必须找到其前趋结点，应该应填写其前趋结点。（2）在单链表中找一个结点必须从首结点开始查找，所以单链表查找结点时间复杂度为O（n）。（3）双链表删除一个已知结点，如

8、图2-6所示只要修改两个指针：p->front->rear=p->