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

《高考理综试题及答案(全国卷2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3线性表的链式表示和实现2.3.1线性链表链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。存储链表中数据元素的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中数据元素的逻辑顺序和物理顺序不一定相同。为了表示数据元素ai和ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点（node）。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次

2、序链接在一起的。每一个结点只包含一个指针域的链表，称为单链表或线性链表。为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。datanext图2-2链表结点结构data：数据域，存放数据元素信息。next：指针域，存放结点的直接后继的地址，指针域中存储的信息称为指针或链。2.3.1线性链表结点包括两个域：数据域和指针域。n个结点连接成一个链表，即为线性表的链式存储结构。2.3.1线性链表单链表的存取必须从头指针开始，头指针指示链表中第一个结点。例1、线性表L=(

3、ZHAO，QIAN，SUN，LI，zhou,wu,zheng,wang)存储地址数据域指针域头指针H3117131925313743LIQIANSUNWANGWUZHAOZHENGZHOU43131NULL3771925HZHAOQIANSUNLIZHOUWUZHENGWANGC语言中用结构指针来描述(线性表的单链表存储结构)typedefstructLNode{ElemTypedata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/}LNode，*LinkList;/*结点的类型*/2.3.1线性链表a1La2…an

4、带头结点的单链表非空表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操作前y

5、px……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个元素存在时

6、，其值赋给e,并返回OK，否则返回ERROR{p=L->next;j=1;//使p指向第一个结点while(p&&jnext;++j;}if(!p

7、

8、j>i)returnerror;e=p->data;//p为NULL表示i太大;j>i表示i为0}算法2.8移动指针p的频度：i<1时：0次;i∈[1,n]：i-1次；i>n：n次。∴时间复杂度:O(n)。2.3.2单链表的基本操作单链表的插入插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域

9、为e的新结点q，q结点作为p的直接后继结点。算法描述（算法2.9）statusListInsert_L(LinkList&L，inti，ElemTypee)//在带头结点的单链表L的第i个位置插入值为e的结点{p=L;j=0;while(p&&jnext;++j;}if(!p

10、

11、j>i-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->next=p->next;p->next=s;returnok;}}链表的长度为n，合法的插入位置是1≦i≦n。算法的时间

12、主要耗费移动指针p上，故时间复杂度亦为O(n)2.3.2单链表的基本操作单链表的删除删除单链表中的第i个结点。为了删除第i