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

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

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

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

2.3.1

线性链表

结点包括两个域：数据域和指针域。n个结点连接成 一个链表，即为线性表的链式存储结构。data next

data :数据域，存放数据元素信息。next :指针域，存放 结点的直接后继的地址，指针域中存储的信息称为指针或链。

图2-2 链表结点结构

链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一 起的。 每一个结点只包含一个指针域的链表，称为单链表或线性链表。 为操作方便，总是在链表的第一个结点之前附设一个头结点(头指 针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度 等信息)。

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

2.3.1 线性链表单链表的存取必须从头指针开始，头指针指示链表中第一个结点。

例1、线性表L=(ZHAO,QIAN,SUN,LI,zhou,wu,zheng,wang)存储地址 头指针H 31 1 7 13 19 25 31 37 43 QIAN 数据域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU SUNZHENG

指针域 43 13 1 NULL 37 7 19 25 LIWANG

H

ZHAO

ZHOU

WU

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

2.3.1

线性链表

C语言中用结构指针来描述(线性表的单链表存储结构) typedef struct LNode { ElemType data; }LNode,*LinkList;L P a1

/*数据域，保存结点的值 */ /*指针域*/ /*结点的类型 */

struct Lnode *next;

在单链表中，每个元素的存储位置都包含在其直接前驱结点的信息之中。 P ->next指向第2个元素，p ->data=a1,p ->next ->data=a2 a2 带头结点的单链表 L 带头结点的单链表 空表 … 非空表 单链表是非随机存取的存储结构 an

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

常见的指针操作p q … … p a 操作后 p b … … a q b p … … a 操作后 q b c 操作前 … … b … …

① q=p ;

…

a 操作前 p

…

② q=p->next ;

…

a

操作前 p

操作后

③ p=p->next ;

…

a

b

操作前

④ q->next=p ;(a)… p

q a

…p

a c

b

…

…

操作后

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

q … a q … a b b … 操作前 …

p x p x y … y …

(b)

⑤ q->next=p->next ; (a)…

操作后q a x b y … … p … 操作前 b … 操作后 x p x y … y … q a x y 操作后 …

b…

…

p

p

q 操作前… a q … a b

(b)

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

2.3.2 单链表的基本操作取单链表中的第i个元素: 对于单链表，不能象顺序表中那

样直接按序号i访问 结点，而只能从链表的头结点出发，沿链域next逐个 结点往下搜索，直到搜索到第i个结点为止。因此，链 表是非随机存取结构。 设单链表的长度为n,要查找表中第i个结点，仅 当1≦i≦n时，i的值是合法的。

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

2.3.2 单链表的基本操作status GetElem_L(LinkList L , int i, ElemType &e) //L为带头结点的单链表的头指针 //当第i个元素存在时，其值赋给e,并返回OK,否则返回ERROR { p=L->next; j=1; // 使p指向第一个结点 while (p && j<i) { p=p–>next; ++j; } if (!p||j>i) return error; 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)。

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

2.3.2 单链表的基本操作单链表的插入 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入 到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p,然后生成一个数据域为 e的新结点q,q结点作为p的直接后继结点。 算法描述(算法2.9) status ListInsert_L(LinkList &L,int i,ElemType e) // 在带头结点的单链表L的第i个位置插入值为e的结点 { p=L; j=0; while ( p&& j<i-1) { p=p–>next; ++j; }

if (!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; return ok; } }链表的长度为n,合法的插入位置是1≦i≦n。算法的时间主要耗费 移动指针p上，故时间复杂度亦为O(n)

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

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)。

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

算法描述(算法2.10)status LinkListDelete_ L(LinkList &L, int i, ElemType &e)//在带头结点的单链表L中删除第i个元素，并由e返回其值

{ p=L; j=0; while ( p->next&& j<i-1) { p=p–>next; ++j; } if (!(p->next)||j>i-1) return error; q=p–>next; p–>next =q–>next; free(q); return ok;

}单链表是一种动态结构，建立线性表的链式存储结构的过程是一个动态生成 链表的过程

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

2.3.2 单链表的基本操作逆向建立单链表(算法2.11)Viod CreateList_L(LinkList &L , int n) //逆位序输入n个元素的值，建立带表头结点的单链线性表L。 { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for( i=n; i>0; --i) { p=(LinkList)malloc(sizeof(LNode)); scanf(&p->data); p->next=L->nxet; L->next=p; } } 时间复杂度为O(n)

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

单链表的合并设有两个有序的单链表，它们的头指针分别是La 、 Lb,将它们合并为以Lc为头指针的有序链表。合并前的 示意图如图2-4所示。pa Lc pc La -7 Lb -2 4 9 …… 15

3

12

……

23

pb

图2-4 两个有序的单链表La ,Lb的初始状态pa ,pb分别是待考察的两个链表的当前结点，pc指向Lc表中最后一个结点。

20 …… 此处隐藏：2496字，全部文档内容请下载后查看。喜欢就下载吧 ……