第310章 有毛病！(第2页)

简称线性链表。

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后

继结点的地址(或位置)，称为指针(poter)或链(lk)，这两部分组成了链表中的结点结构，

链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结只

包含一个指针域的链表，称为单链表。

存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散

分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。

操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个。

2、双向链表

双向链表(doubleLkedList):指的是构成链表的每个结点中设立两个指针域：一个指向

其直接前趋的指针域prior，一个指向其直接后继的指针域。这样形成的链表中有两个
方向不同的链，故称为双向链表。将头结点和尾结点链接起来也能构成循环链表，并称之为

双向循环链表。

双向链表的结点的类型定义如下。其结点形式如图所示，带头结点的双向链表的形式如

图所示。

就是用数组来实现链式存储结构，目的是方便在不设指针类型的高级程序设计语言中使

用链式结构。实现原理：

1、使用结构体数组，结构体有指针域cur和数据域data

2、一个数组分量表示一个节点，用cur代替指针指示节点在数组中

的相对位置

静态链表，就是用数组来实现链式存储结构，目的是方便在不设指

针类型的高级程序设计语言中使用链式结构。

1、在双向链表指针p的结点前插入一个指针q的结点操作是（）

2．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采

用（）存储方式最节省运算时间。

A．单链表b．仅有头指针的单循环链表

c．双链表d．仅有尾指针的单循环链表

3、下列关于线性表的叙述中，错误的是（）。

A.顺序表是使用一维数组实现的线性表

b.顺序表必须占用一片连续的存储单元

c.顺序表的空间利用率高于链表

d.在链表中，每个结点只有一个链域

【2016年】已知表头元素为c的单链表在内存中的存储状态如下表所示

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算

法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的