第310章 有毛病！

式存储结构，目的是方便在不设指针类型的高级程序设计语言中使

用链式结构。实现原理：

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

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

小主，这个章节后面还有哦，请点击下一页继续阅读，后面更精彩！

的相对位置

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

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

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

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

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

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

C．双链表 D．仅有尾指针的单循环链表

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

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

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

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

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

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

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

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

data 域的值，并返回 1；否则，只 返回 0。要求：

⑴ 描述算法的基本设计思想；

⑵ 描述算法的详细实现步骤；

⑶ 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++语言实现），

关键之处请给出简要注释。

（1）算法的基本设计思想：

问题的关键是设计一个尽可能高效的算法， 通过链表的一趟遍历，找到倒数第 k 个结

点的位置。算法的基 本设计思想是：定义两个指针变量 p 和 q，初始时均指向头结点的下。

如图（d）所示，当|t1-t2| == 1 时，表示共享栈满。

本章未完，请点击下一页继续阅读！ 第3页 / 共4页