2010年高考理综试题及答案(全国卷2)

2.3线性表的链式表示和实现2.3.1线性链表链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。存储链表中数据元素的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中数据元素的逻辑顺序和物理顺序不一定相同。为了表示数据元素ai和ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点（node）。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结点只包含一个指针域的链表，称为单链表或线性链表。为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。datanext图2-2链表结点结构data：数据域，存放数据元素信息。next：指针域，存放结点的直接后继的地址，指针域中存储的信息称为指针或链。2.3.1线性链表结点包括两个域：数据域和指针域。n个结点连接成一个链表，即为线性表的链式存储结构。2.3.1线性链表单链表的存取必须从头指针开始，头指针指示链表中第一个结点。例1、线性表L=(ZHAO，QIAN，SUN，LI，zhou,wu,zheng,wang)存储地址数据域指针域头指针H3117131925313743LIQIANSUNWANGWUZHAOZHENGZHOU43131NULL3771925HZHAOQIANSUNLIZHOUWUZHENGWANGC语言中用结构指针来描述(线性表的单链表存储结构)typedefstructLNode{ElemTypedata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/}LNode，*LinkList;/*结点的类型*/2.3.1线性链表a1La2…an带头结点的单链表非空表L带头结点的单链表空表在单链表中，每个元素的存储位置都包含在其直接前驱结点的信息之中。PP-next指向第2个元素，p-data=a1,p-next-data=a2单链表是非随机存取的存储结构常见的指针操作①q=p;pa……操作前pa……q操作后②q=p-next;bpa……操作前操作后qbpa……③p=p-next;bpa……操作前操作后pba……④q-next=p;c…pbqa……操作前操作后qb……ac…p(a)⑤q-next=p-next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)2.3.2单链表的基本操作取单链表中的第i个元素:对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表是非随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。2.3.2单链表的基本操作statusGetElem_L(LinkListL，inti,ElemType&e)//L为带头结点的单链表的头指针//当第i个元素存在时，其值赋给e,并返回OK，否则返回ERROR{p=L-next;j=1;//使p指向第一个结点while(p&&ji){p=p–next;++j;}if(!p||ji)returnerror;e=p-data;//p为NULL表示i太大;ji表示i为0}算法2.8移动指针p的频度：i1时：0次;i∈[1,n]：i-1次；in：n次。∴时间复杂度:O(n)。2.3.2单链表的基本操作单链表的插入插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。算法描述（算法2.9）statusListInsert_L(LinkList&L，inti，ElemTypee)//在带头结点的单链表L的第i个位置插入值为e的结点{p=L;j=0;while(p&&ji-1){p=p–next;++j;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s-data=e;s-next=p-next;p-next=s;returnok;}}链表的长度为n，合法的插入位置是1≦i≦n。算法的时间主要耗费移动指针p上，故时间复杂度亦为O(n)2.3.2单链表的基本操作单链表的删除删除单链表中的第i个结点。为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p–next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。设单链表长度为n，则删去第i个结点仅当1≦i≦n时是合法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是p–next!=NULL。显然此算法的时间复杂度也是O(n)。算法描述(算法2.10)statusLinkListDelete_L(LinkList&L，inti,ElemType&e)//在带头结点的单链表L中删除第i个元素，并由e返回其值{p=L;j=0;while(p-next&&ji-1){p=p–next;++j;}if(!(p-next)||ji-1)returnerror;q=p–next;p–next=q–next;free(q);returnok;}单链表是一种动态结构，建立线性表的链式存储结构的过程是一个动态生成链表的过程2.3.2单链表的基本操作逆向建立单链表（算法2.11）ViodCreateList_L(LinkList&L,intn)//逆位序输入n个元素的值，建立带表头结点的单链线性表L。{L=(LinkList)malloc(sizeof(LNode));L-next=NULL;for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));scanf(&p-data);p-next=L-nxet;L-next=p;}}时间复杂度为O（n）单链表的合并设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以Lc为头指针的有序链表。合并前的示意图如图2-4所示。15⋀图2-4两个有序的单链表La，Lb的初始状态-249……Lbpb-7312……23⋀LaLcpapcpa，pb分别是待考察的两个链表的当前结点，pc指向Lc表中最后一个结点。合并了值为-7，-2的结点后示意图如图2-5所示。图2-5合并了值为-7，-2的结点后的状态-249……15⋀LbpcpbLc-7312……23⋀Lapa算法说明算法中pa，pb分别是待考察的两个链表的当前结点，pc指向Lc表中最后一个结点。算法描述（算法2.12）VoidMergeList_L(LinkList&La，LinkList&Lb,LinkList&Lc)//已知单链线性表La和Lb的元素按非递减排列//归并La和Lb得到新的单链线性表Lc也按值非递减排列{pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&&pb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;free(Lb);//释放Lb头结点}2.3.3循环链表循环链表(CircularLinkedList)：是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。图2-6是带头结点的单循环链表的示意图。空表图2-6单循环链表示意图非空表a1a2……anHH有时，若在循环链表中设立尾指针而不设头指针，可使某些操作简化。循环链表的操作对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：⑴判断是否是空链表：head-next==head;⑵判断是否是表尾结点：p-next==head;ABB,A2.3.4双向链表双向链表(DoubleLinkedList):指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。双向链表是为了克服单链表的单向性的缺陷而引入的。1双向链表的结点及其类型定义双向链表的结点的类型定义如下。其结点形式如图2-7所示，带头结点的双向链表的形式如图2-8所示。typedefstructDulnode{ElemTypedata;structDulnode*prior,*next;}DulNode，*DulinkList;elementnextprior图2-7双向链表结点形式……非空双向链表head⋀a2a1an⋀空双向链表head⋀⋀图2-8带头结点的双向链表形式2.3.4双向链表……非空双向循环链表链表heada2a1an空双向循环链表head图2-8带头结点的双向循环链表形式双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：p-prior-next=p=p-next-prior;结点p的存储位置存放在其直接前趋结点p-prior的直接后继指针域中，同时也存放在其直接后继结点p-next的直接前趋指针域中。2双向链表的基本操作(1)双向链表的插入将值为e的结点插入双向链表中。插入前后链表的变化如图2-9所示。算法2.18statusListInsert_Dul(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))returnerror;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnerror;s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-pror=s;returnok;}Sep…………ai-1ai图2-9双向链表的插入1234(2)双向链表的结点删除设要删除的结点为p，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。StutasListDelete_Dul(DulLinkList&L,inti,ElemType&e){//删除带头结点的双链循环线性表L的第i个元素，1=i=表长if(!(p=GetElemP_Dul(L,i)))returnERROR;e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);returnOK;}注意：与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。abcp12ac2.3.5重新定义线性链表及其基本操作单链表存在以下缺点：1.求线性表的长度时不如顺序存储结构；2.在链表中，“位序”的概念淡化，被数据元素在线性表中的“位置”代替。typedefstructLNode{//节点类型ElemTypedata;structLNode*next;}*Link,*PositionStatusMakeNode(