习题解答
tail = tail->Next ; free (tail) ; free (ptr);
C．tail = tail->Next->Next ; D．ptr = tail->Next->Next ;
Free (tail); tail->Next->Next = ptr->Next ; Free (ptr); free (ptr); 10．在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是 B 。 A．qtr->Next = ptr ; B．qtr->Next = ptr->Next ; ptr->Next = qtr ; ptr->Next = qtr ; C．qtr->Next = ptr->Next ; D．ptr->Next = qtr ; ptr = qtr ; qtr->Next = ptr ;
三、问答 1．试问，如下的线性表： L = (29，25，21，17，13，11，7，5，3，1) 是有序线性表还是无序线性表？
答：L是一个有序线性表。 2．线性表L第i个存储结点ai的起始地址LOC（ai）可以通过下面的公式计算得到： LOC（ai）= LOC（ai-1）+k
其中k表示存储结点的长度。这个公式对吗？为什么？ 答：这个公式是对的，因为第i个存储结点ai的起始地址LOC（ai），实际上就是等于第i-1个存储结点ai-1的起始地址LOC（ai-1）加上一个存储结点的长度k得到。
3．试说明创建顺序表算法Create_Sq ()中，Sq_max和Sq_num的不同之处。
答：Sq_max代表的是顺序表的最大长度，也就是它最多可以容纳下多少个数据元素，顺序表创建后，Sq_max是一个保持不变的常量；Sq_num代表的是顺序表内当前拥有的数据元素个数，在顺序表创建后，随着对数据元素进行的插入、删除操作，Sq_num将会不断地发生变化。 4．如何判断一个顺序表是否为空？ 答：只需判定Sq_num的当前值是多少，如果Sq_num为0，则表示顺序表Sq为空，否则表示该顺序表里有数据元素存在。
5．在算法2-3里，操作“Sq_num=Sq_num -1”的作用是什么？没有它行吗？ 答：该操作是非常重要的，因为顺序表里当前拥有的元素个数是通过Sq_num来记录的，删除了一个元素，Sq_num必须减1，这样才能正确反映出删除后表中元素的个数。所以，没有这个操作是不行的。
6．在算法2-9里，如果现在是把一个结点插入到单链表尾结点的后面。按照算法的描述，能够保证插入后最后一个结点的Next域为“Λ”吗？
答：能够。因为原来ptr->Next里是“Λ”，做了第1步操作： qtr->Next = ptr->Next ;
后，就是把插入结点的Next域置为“Λ”。 7．在一个单链表中，为了删除指针ptr所指的结点，有人编写了下面的操作序列。读懂并加以理解。试问，编写者能够达到目的吗？其思想是什么？
x = ptr->Data ; qtr = ptr->Next ;
ptr->Data = ptr->Next->Data ;
- 5 -
习题解答
ptr->Next = ptr->Next->Next ; free (qtr);
答：能够达到删除指针ptr所指结点的目的。编写者的思想是不去直接删除ptr所指的结点，而是在把ptr直接后继的Data域内容写入ptr所指结点的Data域之后，把它的直接后继删除。对于单链表来说，得到一个结点的直接后继容易，得到它的直接前驱难，所以这样的设计是有其可取之处的。 8．在一个单链表中，为了在指针ptr所指结点之前插入一个由指针qtr所指的结点，有人编写了下面的操作序列，其中temp是一个临时工作单元。读懂并加以理解。试问，编写者能够达到目的吗？其思想是什么？
qtr->Next = ptr->Next ; ptr->Next = qtr ; temp = ptr->Data ; p->Data = qtr->Data ; qtr->Data = temp ;
答：能够达到在指针ptr所指结点之前插入一个由指针qtr所指结点的目的。编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难，因此在这里先把qtr所指结点插入到ptr所指结点的后面，暂时成为它的直接后继。然后通过临时工作单元temp，将ptr及qtr所指结点的Data域内容进行交换，从而达到插入的目的。 9．打算形成一个有表头结点的循环双链表，初始时除了每个结点的Next域已经链接好外，它们的Prior域还都是空的。有人编写了下面的算法，试图完成Prior域的链接：
Com_Cd (Cd_h) {
ptr = Cd_h->Next ; qtr = Cd_h ; while (ptr != Cd_h) {
ptr ->Prior = qtr ; qtr = ptr ; ptr = ptr->Next ; }
Cd_h->Prior = qtr ; }
读懂并理解它，解释为什么能够完成各结点的Prior域的链接？ 答：算法中用两个指针ptr和qtr配合，从头到尾扫描这个循环双链表，以达到让每个结点的Prior域指向其直接前驱的目的。
四、应用
1．设计一个计算表头指针为Lk_h的单链表长度（即结点个数）的算法。 答：算法设计如下：
Length_Lk (Lk_h) { n = 0 ; ptr = Lk_h ;
/* ptr指向起始结点 */
while (ptr != NULL)
- 6 -
习题解答
{
ptr = ptr->Next ; n=n+1 ;
} return (n) ; }
/* n为结点计数单元 */
2．用总是在表的头部插入整数结点的方法建立一个单链表，当输入为0时，建表过程结束。 答：算法设计如下：
Clink() {
Lk_h = NULL; scanf (%d, &x); while (x != “0”) { }
return Lk_h; }
ptr = malloc (size); ptr->Data = x; ptr->Next = Lk_h; Lk_h = ptr; scanf (%d, &x);
3．一个不带表头结点的循环双链表Ck的表头指针为Ck_h，要在指针ptr指向处前插入一个rtr所指结点。模仿图2-21，对一般插入位置标示出下面4个操作步骤：
①rtr->Next = ptr ;
②rtr->Prior = ptr->Prior ; ③ptr->Prior->Next = rtr ; ④ptr->Prior = rtr ;
答：4个操作步骤的具体功能体现如下图所示。
4．试设计一个算法copy (Ck_h1, Ck_h2)，将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1的内容，复制到一个不带表头结点的、以Ck_h2为表头指针的单链表Ck2中。 答：算法具体如下。
Copy (Ck_h1, Ck_h2) {
ptr = Ck_h1->Next ;
- 7 -
习题解答
qtr = Ck_h2 ; while ( ptr != NULL) {
rtr = malloc (size); rtr->Data = ptr->Data ; }
qtr->Next = NULL ; }
qtr->Next = rtr ; qtr = rtr ; ptr = ptr->Next ;
5．已知一个带表头结点的递增单链表。试编写一个算法，功能是从表中去除值大于min、且值小于max的数据元素。（假定表中存在这样的元素） 答：所需算法编写如下。
Del_Sq(Lk_h, nim, max) {
ptr = Lk_h->Next ; {
qtr = ptr ; ptr = ptr->Next ; }
while ( (ptr != NULL) && (ptr->Data
/* qtr指出第1个大于max的结点位置，完成链接 */
/* 若结点值 /* ptr指向链表的起始结点 */ while ( (ptr != NULL) && (ptr->Data <= min) ) /* 跳过所有值<=min的结点 */ 6．已知一个带表头结点的无序单链表。试编写一个算法，功能是从表中去除所有值大于min、且值小于max的数据元素。 答：所需算法编写如下，其中指针ptr总是指向当前被检查的结点，qtr总是指向被检查结点的直接前驱。 Del_Lk (Lk_h, min, max) { ptr = Lk_h->Next ; while (ptr != NULL) { if ( (ptr->Data <= min) || (ptr->Data >= max) { qtr = ptr ; } else { qtr->Next = ptr->Next ; free (ptr); /* 删除ptr所指结点，往后移动ptr */ /* 往后移动qtr和ptr */ ptr = ptr->Next ; /* 不满足删除条件 */ /* ptr指向单链表的起始结点 */ /* 扫视直到链尾结点 */ - 8 -