第310章 有毛病！（2/2）

方向不同的链，故称为双向链表。将头结点和尾结点链接起来也能构成循环链表，并称之为

双向循环链表。

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

图所示。

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

用链式结构。实现原理：

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。要求：

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

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

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

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

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

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

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

如图（d）所示，当|t1-t2|==1时，表示共享栈满。那么大家可能会问一个问题，反正

就是这么一块空间，那我们二一添作五，直接均分不就行了（你好，我好，大家好，一片和

谐，此处应该有掌声）。均分看似合理，其实会导致很大问题，大家请想一下，程序的执行

是不确定的，也是不均衡的（好像说的有点玄乎），有的程序需要的空间大，有的程序需要

的空间小，图（b）中表示的是栈1占用的空间的大一些；图（b）中表示的是栈2占用的

空间的大一些，如果均分，就会出现旱涝不均，图（b）中栈1就会旱死（空间不够，而报

错），图（c）中栈2就会旱死（空间不够，而报错）。

5.括号匹配问题

在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是

否相匹配?

匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左

括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个

右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。

算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹

出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。

6.栈与递归调用的实现

栈的另一个重要应用是在程序设计语言中实现递归调用。递归调用：一个函数(或过程)

直接或间接地调用自己本身，简称递归(Recursive)。为了使递归调用不至于无终止地进行下

去，实际上有效的递归调用函数(或过程)应包括两部分：递推规则(方法)，终止条件,初始。