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表中最后一个结点。

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

合并了值为-7,-2的结点后示意图如图2-5所示。pa La Lc Lb -2 pc 4 pb 9 …… -7 3 12 ……

23

15

图2-5

合并了值为-7 ,-2的结点后的状态

算法说明算法中pa ,pb分别是待考察的两个链表的当前结 点，pc指向Lc表中最后一个结点。

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

算法描述(算法2.12)Void MergeList_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头结点

}

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

2.3.3 循环链表循环链表(Circular Linked List):是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结 点，整个链表的指针域链接成一个环。 从循环链表的任意一个结点出发都可以找到链表中 的其它结点，使得表处理更加方便灵活。 图2-6是带头结点的单循环链表的示意图。HH …… an

a1

a2

空表

非空表

图2-6 单循环链表示意图

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

循环链表的操作对于单循环链表，除链表的合并外，其它的操作和 单线性链表基本上一致，仅仅需要在单线性链表操作算 法基础上作以下简单修改： ⑴ 判断是否是空链表：head->next==head ; ⑵ 判断是否是表尾结点：p->next==head ; 有时，若在循环链表中设立尾指针而不设头指针， 可使某些操作简化。A

B

B,A

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

2.3.4 双向链表双向链表(Double Linked List) :指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的指 针域prior,一个指向其直接后继的指针域next。这样形 成的链表中有两个方向不同的链，故称为双向链表。 和单链表类似，双向链表一般增加头指针也能使双 链表上的某些运算变得方便。将头结点和尾结点链接起来也能构成循环链表，并 称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入

的。

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

1 双向链表的结点及其类型定义双向链表的结点的类型定义如下。其结点形式如 图2-7所示，带头结点的双向链表的形式如图2-8所示。

typedef struct Dulnode { ElemType data ; struct Dulnode *prior , *next ; }DulNode,*DulinkList ;prior element nexthead

图2-7 双向链表结点形式head a1 a2 …… an

空双向链表

非空双向链表 图2-8

带头结点的双向链表形式

本文来源：https://www.bwwdw.com/article/73hm.html