《数据结构答案第2章线性表学习指导》由会员分享，可在线阅读，更多相关《数据结构答案第2章线性表学习指导（9页珍藏版）》请在金锄头文库上搜索。
1、第2章线性表2.1 知识点分析1线性表的定义线性表是具有相同数据类型的n（n=0）个数据元素的有限序列，通常记为：(a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。在线性表中相邻元素之间存在着顺序关系。对于元素ai 而言，ai-1 称为 ai 的直接前驱，ai+1 称为 ai 的直接后继。也就是说：（1）有且仅有一个开始结点（a1），它没有直接前驱；（2）有且仅有一个终端结点（an），它没有直接后继；（3） 除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。 2顺序表顺序表是线性表的顺序存储，是指在内存中分配一组连续的存储单元依次存储
2、线性表的数据元素，元素之间的结构（关系）无需存放，顺序表的逻辑顺序和物理顺序是一致的。常用的顺序表的操作（运算）有建立顺序表、插入、删除、查找、访问、更新等。3线性链表线性链表（单链表）是线性表的链接式存储，在内存中分配存储单元可以是连续的，也可以是不连续的地址，存储单元中存放数据元素信息（数据域）和存放其后继结点地址（指针域）。常用的线性链表操作（运算）有建立链表、插入、删除、查找、访问、更新、求表长等。4顺序表和线性链表的比较（1） 顺序表优点：空间利用率高；可以随机存取表中任意一个元素，存储位置可以用公式：B+(i-1)*d 计算。缺点：对顺序表作插入、删除时需要通过移动大量的数据元素，
3、时间性能差；线性表预先分配空间时，必须按最大空间分配，存储空间得不到充分的利用；表的容量难以扩充（对有些高级语言而言）。（2） 单链表优点：对表作插入、删除时无需移动数据元素，时间性能好；因为动态分配存储空间，不会发生溢出现象；查找元素必须从首元素开始查找，比较费时。缺点：存储密度小，空间利用率低。2.2 典型习题分析【例1】带头结点单链表L为空的判断条件是（ ）。AL= =NULL BL-next= = NULL CL-next=L DL！=NULL分析：带头结点的单链表为空表如图2-1所示。L L图2-1带头结点的单链表 图2-2带头结点的循环单链表所以其判断条件可以表示为Lnext=NU
4、LL(注意用双=号)，如果单链表不带头结点，则其空判断条件是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=inext=p-next;p-next=s;时间复
5、杂度是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。图2-3 在*p之后插入*s s图2-4 删除*P的后继结点 x qppan图2-5 带头结点的单链表a1a2H【例4】在n个结点的单链表中要删除已知结点*P，需要找到 （1） ，其时间复杂度为 （2） 。而在双链表中要删除已知结点*P，其时间复杂度为 （3
6、） 。分析：（1）在单链表中删除一个结点，必须找到其前趋结点，应该应填写其前趋结点。（2）在单链表中找一个结点必须从首结点开始查找，所以单链表查找结点时间复杂度为O（n）。（3）双链表删除一个已知结点，如图2-6所示只要修改两个指针：p-front-rear=p-rear;p-rear-front=p-front;所以时间复杂度为O（1）。p2-6 双链表删除【例5】对于一个具有n个结点单链表，在p所指结点后插入一个新结点的时间复杂度为 （1） ，在给定值为x的结点后插入一个新结点的时间复杂度为 （2） 。分析：（1）单链表在指定结点之后插入结点，无需查找结点位置，其时间复杂度为O（1）。（2
7、）而给定一个值x之后插入结点，需要查找结点x位置，故其时间复杂度为O（n）。【例6】下列程序将一个顺序表（a1,a2,a3,a4,an）就地逆置的程序，请在处填上正确的语句。#include#define MAXLEN 10struct SeqList int dataMAXLEN; int last; SeqList a;void main() int i,temp,n;a.last=-1;coutn;for(i=0;ia.datai; a.last+;for(i=0; (1) ;i+) temp=a.datai; a.datai= (2) ; (3) =temp; for(i=0;in;i
8、+) couta.datait; coutnext; (1) ; while( (2) ) r=p-next; p-next=H1-next; H1-next=p; (3) ; H=H1; 分析：如图所示2-8带头结点循环单链表，将其逆置于,上述程序思路是，依次从单链表H取出结点，插入到单链表H1的头结点之后，如图2-9所示。p图2-8 带头结点的单循环链表aiHan图2-9 带头结点的单循环链表ai-1H1a1aiai （1）H1是循环单链表，填写H1-next=H1，表示是一个空循环单链表开始插入。（2）表示循环条件，对于循环单链结束条件是结点地址为头结点，所以填写p!=H。（3）为插入下
9、一个结点做准备，应该取下一个结点地址，所以填写p=r。【例8】假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知S为指向链表中某一结点的指针，试设计算法，在链表中删除指针s所指结点的前趋结点。分析：本题链表是一个循环单链表，解题思路是从结点s开始向后查找其前趋结点p，和s前趋的前趋结点q，修改指针结点的next值为s地址，即q-next=s，删除结点p。算法如下：void dele(linnode *s) linnode *p, *q; p=s-next ; q=s; while(p-next!=s) q=s; p=p-next; q-next=s; delete p;【例9】设
10、计一个算法，删除顺序表中值相同的结点。 分析：本题算法是从第一个结点开始到最后一个结点（注意如果有结点值相同，结点被删除后，顺序表长度随时变化）的元素值取出，和下面结点值依次比较，如果有相同值，从相同值下一个元素开始到最后一个元素，顺序往前移动一位。算法如下：SeqList del_SeqList(SeqList L) int i=0,j,k; while(i=L.last) j=i+1; while(j=L.last) if (L.datai=L.dataj) for(k=j+1;kprior=q。struct cdlist / 双链表数据类型datatype data; / 结点数据域struct cdlis
