习题解答
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 - 习题解答 ptr = qtr->Next ; } } } 7．一个单链表Lk的表头指针为Lk_h，不同结点的Data域值有可能相同。编写一个算法，功能是计算出Data域值为x的结点的个数。 答：算法应该遍历链表的每一个结点，遇到一个结点的Data域值为x时，计数器n就加1。最后返回计数器n。 Count_Lk (Lk_h) { n = 0 ; ptr = Lk_h ; while (ptr != NULL) { if (ptr->Data == x) n = n+1 ; ptr = ptr->Next } return (n) ; } 第3章习题解答 一、填空 1．限定插入和删除操作只能在一端进行的线性表，被称为是 栈 。 2．如果在顺序栈满时仍打算进行进栈操作，就称为发生了“ 上溢 ”出错。 3．如果在顺序栈空时仍打算进行出栈操作，就称为发生了“ 下溢 ”出错。 4．在具有n个数据结点的循环队列中，队满时共有 n-1 个数据元素。 5．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。最终这个堆栈从栈顶到栈底的余留元素应该是 DA 。 6．中缀表达式(a+b)-(c/(d+e))对应的后缀表达式是 ab+cde+/- 。 7．函数的递归调用有两种形式：如果一个函数是直接调用自己，就称其为 直接 递归调用；如果一个函数是通过另一个函数来调用自己，就称其为 间接 递归调用。 8．设某栈的元素输入顺序是1、2、3、4、5，想得到4、3、5、2、1的输出顺序。那么push、pop的操作序列应该是 push、push、push、push、pop、pop、push、pop、pop、pop 。 9．设链栈的栈顶指针为Ls_top，那么它非空的条件应该是 Ls_top != NULL 。 10．队列中，允许进行删除的一端称为 队首 。 二、选择 1．一个栈的元素进栈序列是a、b、c、d、e，那么下面的 C 不能做为一个出栈序列。 A．e、d、c、b、a B．d、e、c、b、a C．d、c、e、a、b D．a、b、c、d、e - 9 - 习题解答 2．判定一个顺序队列Qs（最多有n个元素）为空的条件是 C 。 A．Qs_rear-Qs_front == n*size B．Qs_rear-Qs_front+1 == n*size C．Qs_front == Qs_rear D．Qs_front == Qs_rear+size 3．判定一个顺序队列Qs（最多有n个元素）真满的条件是 A 。 A．Qs_rear-Qs_front == n*size B．Qs_rear-Qs_front+1 == n*size C．Qs_front == Qs_rear D．Qs_front == Qs_rear+size 4．在一个链式队列Lq中，Lq_front和Lq_rear分别为队首、队尾指针。现在由指针ptr所指结点要进队，则插入操作应该是 B 。 A．Lq_front->Next = ptr; Lq_front = ptr; B．Lq_rear->Next = ptr; Lq_rear = ptr; C．ptr->Next = Lq_rear; Lq_rear = ptr; D．ptr->Next = Lq_front; Lq_front = ptr; 5．链栈与顺序栈相比，一个较为明显的优点是 D 。 A．通常不会出现栈空的情形 B．插入操作更加便利 C．删除操作更加便利 D．通常不会出现栈满的情形 6．向链栈插入一个结点时，操作顺序应该是 C 。 A．先修改栈顶指针，再插入结点 B．无须修改栈顶指针 C．先插入结点，再修改栈顶指针 D．谁先谁后没有关系 7．从链栈中删除一个结点时，操作顺序应该是 A 。 A．先保存被删结点的值，再修改栈顶指针 B．先修改栈顶指针，再保存被删结点的值 C．无须修改栈顶指针的值 D．谁先谁后没有关系 8．一个循环队列的最大容量为m+1，front为队首指针，rear为队尾指针。那么进队操作时求队位号应该使用公式 D 。 A．Cq_front = (Cq_front+1)%m B．Cq_front = (Cq_front+1)%(m+1) C．Cq_rear = (Cq_rear+1)%m D．Cq_rear = (Cq_rear+1)%(m+1) 9．在一个循环顺序队列里，队首指针Cq_front总是指向 B 。 A．队首元素 B．队首元素的前一个队位 C．任意位置 D．队首元素的后一个队位 10．若一个栈的进栈序列是1、2、3、4，那么要求出栈序列为3、2、1、4时，进、出栈操作的顺序应该是 A 。（注：所给顺序中，I表示进栈操作，O表示出栈操作） A．IIIOOOIO B．IOIOIOIO C．IIOOIOIO D．IOIIIOOO 三、问答 1．若元素进栈的序列是1、2、3、…、n，有一个出栈序列的第1个元素是n。那么，这个出栈序列的第i个元素是什么？ 答：由于栈具有“先进后出”的特性，因此只有将1、2、3、…、n依次都进栈后，出栈序列的第1个元素才能是n。所以，在这个出栈序列里，第个i元素应该是n-i+1。 2．设元素进栈的次序是a，b，c，d，e。试问，在下面所列的6种元素序列里，哪些可以是这个栈的出栈序列？ A．c，e，a，b，d B．c，b，a，d，e C．d，c，a，b，e D．a，c，b，e，d E．a，b，c，d，e F．e，a，b，c，d 答：对A进行分析。由于是c第1个出栈，因此b必须先于a出栈。但所给序列里，a - 10 -