搜索
7第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．顺序表和线性链表的比较（1）顺序表优点：空间利用率高；可以随机存取表中任意一个元素，存储位置可以用公式：B+(i-1)*d计算。缺点：对顺序表作插入、删除时需要通过移动大量的数据元素，时间性能差；线性表预先分配空间时，必须按最大空间分配，存储空间得不到充分的利用；表的容量难以扩充（对有些高级语言而言）。（2）单链表优点：对表作插入、删除时无需移动数据元素，时间性能好；因为动态分配存储空间，不会发生溢出现象；查找元素必须从首元素开始查找，比较费时。缺点：存储密度小，空间利用率低。2.2典型习题分析【例1】带头结点单链表L为空的判断条件是（）。A．L==NULLB．L-next==NULLC．L-next==LD．L！=NULL分析：带头结点的单链表为空表如图2-1所示。LL图2-1带头结点的单链表图2-2带头结点的循环单链表所以其判断条件可以表示为L－＞next==NULL(注意用双==号)，如果单链表不带头结点，则其空判断条件是L==NULL，如果是循环单链表，其空判断条件是L-next==L,如图2-2所示，故答案为B。＾8【例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）在单链表中找一个结点必须从首结点开始查找，所以单链表查找结点时间复杂度为O（n）。（3）双链表删除一个已知结点，如图2-6所示只要修改两个指针：p-front-rear=p-rear;p-rear-front=p-front;所以时间复杂度为O（1）。图2-3在*p之后插入*ss×①②图2-4删除*P的后继结点xqp×an∧图2-5带头结点的单链表a1a2H…pp②①92-6双链表删除【例5】对于一个具有n个结点单链表，在p所指结点后插入一个新结点的时间复杂度为（1），在给定值为x的结点后插入一个新结点的时间复杂度为（2）。分析：（1）单链表在指定结点之后插入结点，无需查找结点位置，其时间复杂度为O（1）。（2）而给定一个值x之后插入结点，需要查找结点x位置，故其时间复杂度为O（n）。【例6】下列程序将一个顺序表（a1,a2,a3,a4,……,an）就地逆置的程序，请在处填上正确的语句。#includeiostream.h#defineMAXLEN10structSeqList{intdata[MAXLEN];intlast;};SeqLista;voidmain(){inti,temp,n;a.last=-1;cout输入元素个数;cinn;for(i=0;in;i++){cina.data[i];a.last++;}for(i=0;(1);i++){temp=a.data[i];a.data[i]=(2);(3)=temp;}for(i=0;in;i++)couta.data[i]'\t';coutendl;}分析：（1）根据题意将一个顺序表交换，就是将第一个元素和最后一个元素交换，第二个元素和倒数第二个元素交换……，如图2-7所示，交换次数是元素的一半，即(n-1)/2，所以填写(n-1)/2。（2）和（3）是将二数交换，第一个元素和最后一个元素（序号为n-1），第二元素和倒数第二个元素（序号为n—1-1），……第i元素和倒数第i元素（序号为n-i-1）交换，所以（2）和（3）填写a.data[n-i-1]。012…a.last-2a.last-1a.lasta1a2a3…an-2an-1an2-7将顺序表倒置示意图10【例7】下列算法是将一个带头结点单循环链表H(非空)，实现逆置。voidinver(linnode*H){linnode*p,*H1,*r;H1=H;p=H-next;(1);while((2)){r=p-next;p-next=H1-next;H1-next=p;(3);}H=H1;}分析：如图所示2-8带头结点循环单链表，将其逆置于,上述程序思路是，依次从单链表H取出结点，插入到单链表H1的头结点之后，如图2-9所示。（1）H1是循环单链表，填写H1-next=H1，表示是一个空循环单链表开始插入。（2）表示循环条件，对于循环单链结束条件是结点地址为头结点，所以填写p!=H。（3）为插入下一个结点做准备，应该取下一个结点地址，所以填写p=r。【例8】假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知S为指向链表中某一结点的指针，试设计算法，在链表中删除指针s所指结点的前趋结点。分析：本题链表是一个循环单链表，解题思路是从结点s开始向后查找其前趋结点p，和s前趋的前趋结点q，修改指针结点的next值为s地址，即q-next=s，删除结点p。算法如下：voiddele(linnode*s){linnode*p,*q;p=s-next;q=s;while(p-next!=s){q=s;p=p-next;}q-next=s;deletep;}××p图2-8带头结点的单循环链表aiHan…图2-9带头结点的单循环链表ai-1H1a1…aiai11【例9】设计一个算法，删除顺序表中值相同的结点。分析：本题算法是从第一个结点开始到最后一个结点（注意如果有结点值相同，结点被删除后，顺序表长度随时变化）的元素值取出，和下面结点值依次比较，如果有相同值，从相同值下一个元素开始到最后一个元素，顺序往前移动一位。算法如下：SeqListdel_SeqList(SeqListL){inti=0,j,k;while(i=L.last){j=i+1;while(j=L.last)if(L.data[i]=L.data[j]){for(k=j+1;k=L.last;k++)L.data[k-1]=L.data[k];L.last--;}elsej++;i++;}returnL;}【例10】设有一循环双链表，但初始时每个结点的前趋指针域prior是空的，编写算法，使每个结点的前趋指针域指向其直接前趋结点的地址。分析：对循环双链表，其后继指针已经连接，前趋指针是空的，编写算法的思路是，用两个指针变量p,q，让p,q从头到尾访问双链表，并且q始终是p的前趋，修改p的前趋指针域，算法如下：p-prior=q。structcdlist//双链表数据类型{datatypedata;//结点数据域structcdlist*prior;//指向先前结点的指针structcdlist*next;//指向后继结点的指针}voidinvert_cdlist(cdlist*head){cdlist*p,*q;p=head-next;q=head;while(p!=head){p-prior=q;q=p;p=p-next;}head-prior=q;}【例11】设计一个带头结点双链表按下列要求的Locate运算的算法。12双链表的每个结点有4个域，前驱指针域prior、后继指针域next、数据域data、访问频率域freq（初始为0）。当进行一次Locate(head,x)运算时值为x的freq域值加1。要求将链表中结点按freq域从大到小排列，使频繁访问的结点总量靠近表头，并返回找到的值x的位置。分析：对双链表查找值x的结点，可以参照循环单链表思路处理，找到结点后，使其频率域加1，其频率域值要是大于其前趋频率域值，则两个结点要交换位置，交换位置后值为x的结点，其频率域的值要是还大于其前趋频率域值，继续交换，直到其频率域的值不大于其前趋频率域值为止。对于双链表交换相邻结点操作：①p-prior=q-prior;②q-prior-next=p;③q-next=p-next;④p-next-prior=q;⑤p-next=q;⑥q-prior=p;⑤①④②⑥③算法如下：intLocate(cdlist*head,datatypex){cdlist*p,*q;inti=1;p=head-next;q=head;while(p!=NULL&&p-data!=x){p=p-next;i++;}if(p==NULL)i=0;else{p-freq++;q=p-frior;while(q!=head&&q-freqp-freq){i--;p-prior=q-prior;q-prior-next=p;q-next=p-next;p-next-frior=q;p-next=q;q-prior=p;qp2-10双链表相邻两个结点交换示意图13}}returni;}2.3单元练习2解答一．判断题答案题目12345678910答案××√×××√√××二．填空题答案（1）必须（2）一对一（3）节省存储（4）插入、删除（5）顺序（6）O(1)（7）小（8）O(1)（9）O(n)（10）头指针（11）开始（12）n-i（13）n-i+1（14）前趋（15）顺序（16）指针（17）前趋（18）链式（19）p-