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;
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说公务员考试2010年高考理综试题及答案(全国卷2)在线全文阅读。
相关推荐：