[C++知识库]C和指针 第17章 经典抽象数据类型 17.9 问题

1. 假定有一个程序，它读取一系列名字，但必须以反序将它们打印出来。哪种ADT更适合完成这个任务？
解析：
堆栈。堆栈的特性是先进后出，后进先出，所以适合完成这个任务。?

#include "stack.h"
#include <stdio.h>
#include <stdlib.h>

int main( void ){
?? ?int ch;
?? ?int counter;
?? ?
?? ?counter = 0;
?? ?printf( "input name you want:\n" );
?? ?while( (ch = getchar()) != EOF ){
?? ??? ?push( ch );
?? ??? ?++counter;
?? ?}
?? ?printf( "print name you input:\n" );
?? ?while( --counter >= 0 ){
?? ??? ?ch = top();
?? ??? ?putchar( ch );
?? ??? ?pop();
?? ?}

?? ?return EXIT_SUCCESS;
}

/* stack.h的内容如下：*/

/*
**一个堆栈模块的接口。?
*/?
#define STACK_TYPE char /*堆栈所存储的值的类型。*/

/*
**push
**把一个新值压入到堆栈中。它的参数是需要被压入的值。?
*/
void push( STACK_TYPE value );

/*
**pop
**从堆栈弹出一个值，并将它丢弃。
*/
void pop( void );

/*
**top
**返回堆栈顶部元素的值，但不对堆栈进行修改。
*/
STACK_TYPE top( void );

/*
**is_empty
**如果堆栈为空，返回TRUE，否则返回FALSE。
*/
int is_empty( void );

/*
**is_full
**如果堆栈已满，返回TRUE，否则返回FALSE。
*/
int is_full( void );

/* stack.cpp的内容如下：*/

/*
**用一个静态数组实现的堆栈。数组的长度只能通过修改#define定义
**并对模块重新进行编译来实现。?
*/
#include "stack.h"
#include <assert.h>

#define STACK_SIZE 100 /* 堆栈中值数量的最大限制。 */

/*
**存储堆栈中值的数组和一个指向堆栈顶部元素的指针。
*/
static STACK_TYPE stack[ STACK_SIZE ];
static int top_element = -1;

/*
**push
*/
void?
push( STACK_TYPE value ){
?? ?assert( !is_full() );
?? ?top_element += 1;
?? ?stack[ top_element ] = value;
}?

/*
**pop
*/
void?
pop( void ){
?? ?assert( !is_empty() );
?? ?top_element -= 1;
}

/*
**top
*/
STACK_TYPE
top( void ){
?? ?assert( !is_empty() );
?? ?return stack[ top_element ];
}

/*
**is_empty
*/
int?
is_empty( void ){
?? ?return top_element == -1;
}

/*
**is_full
*/
int?
is_full( void ){
?? ?return top_element == STACK_SIZE - 1;
}

/* 输出：

*/?
2. 在超级市场的货架上摆放牛奶时，使用哪种ADT更为合适？既需要考虑顾客购买牛奶，也需要考虑超级市场新到货一批牛奶的情况。
解析：
假如为了保证所有的牛奶不过期能尽量卖完，肯定是旧的牛奶摆放在前面，新的牛奶摆放在后面，这适合使用队列这种数据结构。?
3.在堆栈的传统接口中，pop函数返回它从堆栈中删除的那个元素的值。在一个模块中是否有可能提供两种接口？
解析：
传统接口和替代形式的借口很容易共存。top函数返回栈顶元素值，但并不实际移除它，pop函数移除栈顶元素并返回它。希望使用传递方式的用户可以用传统的方式使用pop函数。如果希望使用替代方案，用户可以用top函数获得栈顶元素的值，而且在使用pop函数时忽视它的返回值。?
4. 如果堆栈模块具有一个empty函数，用于删除堆栈中的所有值，模块的功能是不是变得更加明显更为强大？
解析：
模块的功能变得更为强大了，不过这可能提高它跟其他函数名发生冲突的几率和实现跟堆栈中其它函数相同的功能。?
5.在push函数中，top_element在存储之前先增值。但是pop函数中，它却在返回栈顶值后再减值。如果弄反这两个次序，会发生什么后果。
解析：在push函数中，如果top_element先存储值后增值可能会造成数组溢出。在pop函数中，如果top_element先减值再返回栈顶值则可能提前触发assert宏。?
6.如果在一个使用静态数组的堆栈模型中删除所有的断言，会产生什么后果？
解析：
会导致数组发生溢出，导致一些意料之外的结果。?
7.在堆栈的链式实现中，为什么destroy_stack函数从堆栈中逐个弹出元素？
解析：
由于它们中的每一个都是用malloc函数单独分配的，因此逐个将它们弹出可以保证每个元素均被释放。用于释放它们的代码在pop函数中已经存在，所以调用pop函数比复制那些代码更好。?
8.链式堆栈实现的pop函数声明了称为first_node的局部变量。这个变量可不可以省略？
解析：
first_node局部变量是用来表示当前需要删除的内存的地址，是不可以省略的。之前我们已经有过实验了，假如在stack = stack->next之前使用了free(stack)可能会导致stack->next的值发生改变。?
9.当一个循环数组已满时，front和rear值之间的关系和堆栈为空是是一样的。但是空和满是两种不同的状态。从概念上说，为什么会出现这种情况？
解析：
考虑一个具有5个元素的数组，它可以出现6种不同的状态：它可能为空，也可能分别包含1个、2个、3个、4个或5个元素。但front和rear始终必须指向数组中的5个元素之一。所以对于任何给定值的front，rear只可能出现5中不同的情况：它可能等于front、front+1、front+2、front+3、front+4（记住front+5实际上就是front，因为它已经环绕到这个位置）。我们不可能用只能表示5个不同状态的变量来表示6种不同的状态。?
10.有两种方法可用于检测一个已满的循环数组：始终保留一个数组元素不用；另外增加一个变量，记录数组中元素的个数。哪种方法更好一些？
解析：?
始终保留一个数组元素会浪费一个数组元素的空间。但不用增加额外的一个变量，假如数组元素占用的空间大于增加一个变量所占的空间， 而你的内存又比较小时，考虑使用增加一个变量的方法。假如数组元素占用的空间小于增加一个变量?所占的空间，而你的内存又比较小时，考虑使用始终保留一个数组元素不用。?
/* 根据你实际面临的问题做出最适合的选择就好。*/
12.队列既可以使用单链表也可以双链表实现。那个更合适？
解析：
假定拥有一个指向链表尾部的指针，单链表就完全可以达到目的。由于队列绝不会反向遍历，而双链表具有一个额外的链字段开销，因为它用于这个场合并无优势。?
13.画一棵树，它是根据下面的顺序把这些值一次插入到一棵二叉搜索树而形成的：20,15,18,32,5,91,-4,76,33,41,34
,21,90。?
解析：?

*/?
14.按照升序或降序把一些值插入到一棵二叉搜索树将导致树不平衡。在这样一棵树中查找一个值的效率如何？
解析：
效率较低，查找效率为N。N为数组元素中的元素个数。?
15.在使用前序遍历时，下面这棵树各节点的访问次序是怎么样的？中序遍历呢？后序遍历呢？层次遍历呢？

解析：?

前序遍历：54 36 22 16 25 41 40 51 72 61 80 73
中序遍历：16 22 25 36 40 41 51 54 61 72 73 80
后序遍历：16 25 22 40 51 41 36 61 73 80 72 54?
16.改写do_pre_order_traversal函数，用于执行树的中序遍历。?
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

int main( void ){
?? ?TREE_TYPE values[] = { 54, 36, 72, 22, 41, 61, 80, 16, 25, 40, 51, 73 };
?? ?int len;
?? ?int i;
?? ?
?? ?len = sizeof(values) / sizeof(*values);
?? ?for( i = 0; i < len; ++i ){
?? ??? ?insert( values[i] );
?? ?}
?? ?
?? ?printf( "the sequence of preorder traversal:\n" );
?? ?pre_order_traverse( print );
?? ?printf( "\n" );
?? ?
?? ?printf( "the sequence of inorder traversal:\n" );
?? ?in_order_traverse( print );
?? ?printf( "\n" );
?? ?
?? ?printf( "the sequence of postorder traversal:\n" );
?? ?post_order_traverse( print );
?? ?printf( "\n" );
?? ?
?? ?return EXIT_SUCCESS;
}
/* tree.h的内容如下：*/

/*
**二叉搜索树模块的接口。?
*/
#define TREE_TYPE int /*树的值类型。*/

/*
**print?
**打印数组中的某个值。?
*/
void print( TREE_TYPE value );
?
/*
**insert
**向树添加一个新值。参数是需要被添加的值，它必须原先不存在于树中。
*/
void insert( TREE_TYPE value );

/*
**find
**查找一个特定值，这个值作为第1个参数传递给函数。
*/
TREE_TYPE *find( TREE_TYPE value );

/*
**pre_order_traverse
**执行树的前序遍历。它的参数是一个回调函数指针，它所指向的函数将在树中处理每个节点时被调用，节点的值
**作为参数传递给这个函数。
*/?
void pre_order_traverse( void (*callback)( TREE_TYPE value ) );

/*
**in_order_traverse
**执行树的中序遍历。它的参数是一个回调函数指针，它所指向的函数将在树中处理每个节点时被调用，节点的值
**作为参数传递给这个函数。
*/?
void in_order_traverse( void (*callback)( TREE_TYPE value ) );

/*
**post_order_traverse
**执行树的后序遍历。它的参数是一个回调函数指针，它所指向的函数将在树中处理每个节点时被调用，节点的值
**作为参数传递给这个函数。
*/?
void post_order_traverse( void (*callback)( TREE_TYPE value ) );

/* tree.cpp的内容如下：*/

/*
**一个使用静态数组实现的二叉树搜索树。数组的长度只能通过修改#define定义
**并对模块进行重新编译来实现。?
*/?
#include "tree.h"
#include <stdio.h>
#include <assert.h>

#define TREE_SIZE 100 /*Max # of values in the trees*/
#define ARRAY_SIZE ( TREE_SIZE + 1 )

/*
**用于存储树的所有结点的数组。?
*/
static TREE_TYPE tree[ ARRAY_SIZE ];

/*
**left_child
**计算一个节点左孩子的下标。?
*/
static int?
left_child( int current ){
?? ?return current * 2;
}?

/*
**right_child
**计算一个节点右孩子的下标。?
*/
static int?
right_child( int current ){
?? ?return current * 2 + 1;
}?

/*
**print?
**打印数组中的某个值。?
*/
void print( TREE_TYPE value ){
?? ?printf( "%d ", value );?? ?
}?

/*
**insert
*/
void?
insert( TREE_TYPE value ){
?? ?int current;
?? ?
?? ?/*
?? ?**确保值为非零，因为零用于提示一个未使用的节点。
?? ?*/
?? ?assert( value != 0 );
?? ?
?? ?/*
?? ?**从根节点开始
?? ?*/
?? ?current = 1;
?? ?
?? ?/*
?? ?**从合适的子树开始，直到到达一个叶节点。
?? ?*/
?? ?while( tree[ current ] != 0 ){
?? ??? ?/*
?? ??? ?**根据情况，进入叶节点或右子树（确信未出现重复的值）
?? ??? ?*/
?? ??? ?if( value < tree[ current ] ){
?? ??? ??? ?current = left_child( current );
?? ??? ?}else{
?? ??? ??? ?assert( value != tree[ current ] );
?? ??? ??? ?current = right_child( current );
?? ??? ?}
?? ??? ?assert( current < ARRAY_SIZE );
?? ?}
?? ?
?? ?tree[ current ] = value;?
}?

/*
**find
*/
TREE_TYPE *
find( TREE_TYPE value ){
?? ?int current;
?? ?
?? ?/*
?? ?**从根节点开始。直到找到那个值，进入合适的子树。?
?? ?*/
?? ?current = 1;
?? ?while( current < ARRAY_SIZE && tree[ current ] != value ){
?? ??? ?/*
?? ??? ?**根据情况，进入左子树或右子树。?
?? ??? ?*/
?? ??? ?if( value < tree[ current ] ){
?? ??? ??? ?current = left_child( current );
?? ??? ?}else{
?? ??? ??? ?current = right_child( current );
?? ??? ?}
?? ?}?
?? ?if( current < ARRAY_SIZE ){
?? ??? ?return tree + current;?
?? ?}else{
?? ??? ?return 0;
?? ?}
}

/*
**do_pre_order_traverse
**执行一层前序遍历，这个帮助函数用于保存当前正在处理的节点的信息。
**它并不是用户接口的一部分。
*/
static void
do_pre_order_traverse( int current, void (*callback)( TREE_TYPE value ) ){
?? ?if( current < ARRAY_SIZE && tree[ current ] != 0 ){
?? ??? ?callback( tree[ current ] );
?? ??? ?do_pre_order_traverse( left_child( current ), callback );
?? ??? ?do_pre_order_traverse( right_child( current ), callback );?
?? ?}
}

/*
**pre_order_traverses
*/
void
pre_order_traverse( void (*callback)( TREE_TYPE value ) ){
?? ?do_pre_order_traverse( 1, callback );
}?

/*
**do_in_order_traverse
**执行一层中序遍历，这个帮助函数用于保存当前正在处理的节点的信息。
**它并不是用户接口的一部分。
*/
static void
do_in_order_traverse( int current, void (*callback)( TREE_TYPE value ) ){
?? ?if( current < ARRAY_SIZE && tree[ current ] != 0 ){
?? ??? ?do_in_order_traverse( left_child( current ), callback );
?? ??? ?callback( tree[ current ] );
?? ??? ?do_in_order_traverse( right_child( current ), callback );?
?? ?}
}

/*
**in_order_traverses
*/
void
in_order_traverse( void (*callback)( TREE_TYPE value ) ){
?? ?do_in_order_traverse( 1, callback );
}?

/*
**do_post_order_traverse
**执行一层后序遍历，这个帮助函数用于保存当前正在处理的节点的信息。
**它并不是用户接口的一部分。
*/
static void
do_post_order_traverse( int current, void (*callback)( TREE_TYPE value ) ){
?? ?if( current < ARRAY_SIZE && tree[ current ] != 0 ){
?? ??? ?do_post_order_traverse( left_child( current ), callback );
?? ??? ?do_post_order_traverse( right_child( current ), callback );?
?? ??? ?callback( tree[ current ] );
?? ?}
}

/*
**post_order_traverses
*/
void
post_order_traverse( void (*callback)( TREE_TYPE value ) ){
?? ?do_post_order_traverse( 1, callback );
}?

/* 输出：

?*/
17.改写do_pre_order_traversal函数，用于执行树的后序遍历。?
解析：
答案参考问题16。
18. 二叉搜索树的那种遍历方法可以以升序依次访问树中的所有节点？那种方法可以降序依次访问树中的所有节点？
解析：
中序遍历可以以升序访问一棵二叉搜索树的各个节点。没有一种预定义的遍历方法以降序访问二叉树的各个节点，但可以对中序遍历稍作修改，使它先遍历右子树然后再遍历左子树可以实现这个目的。?
19.destroy_tree函数是通过释放所有分配给树中节点的内存来删除这棵树，这意味着所有树节点必须以某个特定的次序进行处理。哪种类型的遍历最适合这个任务。
解析：
后序遍历最适合这个任务。因为后序遍历的顺序是先遍历左子树，然后再遍历右子树，最后遍历根节点。?
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"?

int main( void ){
?? ?TREE_TYPE values[] = { 54, 36, 72, 22, 41, 61, 80, 16, 25, 40, 51, 73 };
?? ?int len;
?? ?int i;
?? ?
?? ?len = sizeof(values) / sizeof(*values);
?? ?for( i = 0; i < len; ++i ){
?? ??? ?insert( values[i] );
?? ?}
?? ?
?? ?printf( "the sequence of preorder traversal:\n" );
?? ?pre_order_traverse( print );
?? ?printf( "\n" );
?? ?
?? ?printf( "the sequence of inorder traversal:\n" );
?? ?in_order_traverse( print );
?? ?printf( "\n" );
?? ?
?? ?printf( "the sequence of postorder traversal:\n" );
?? ?post_order_traverse( print );
?? ?printf( "\n" );
?? ?
?? ?post_order_traverse( destroy_tree );
?? ?
?? ?return EXIT_SUCCESS;?
}
/* tree.h的内容如下：*/

/*
**二叉搜索树模块的接口。?
*/
#define TREE_TYPE int /*树的值类型。*/

/*
**TreeNode结构包含了值和两个指向某个树节点的指针。
*/
typedef struct TREE_NODE{
?? ?TREE_TYPE value;
?? ?struct TREE_NODE *left;
?? ?struct TREE_NODE *right;
} TreeNode;

/*
**print?
**打印数组中的某个值。?
*/
void print( TREE_TYPE value );
?
/*
**insert
**向树添加一个新值。参数是需要被添加的值，它必须原先不存在于树中。
*/
void insert( TREE_TYPE value );

/*
**find
**查找一个特定值，这个值作为第1个参数传递给函数。
*/
TREE_TYPE *find( TREE_TYPE value );

/*
**find_2
**查找一个特定值，这个值作为第1个参数传递给函数。
*/
TreeNode *find_2( TREE_TYPE value );

/*
**destroy_tree
**删除树中单个的节点。?
*/
void destroy_tree( TREE_TYPE value );
?
/*
**pre_order_traverse
**执行树的前序遍历。它的参数是一个回调函数指针，它所指向的函数将在树中处理每个节点时被调用，节点的值
**作为参数传递给这个函数。
*/?
void pre_order_traverse( void (*callback)( TREE_TYPE value ) );

/*
**in_order_traverse
**执行树的中序遍历。它的参数是一个回调函数指针，它所指向的函数将在树中处理每个节点时被调用，节点的值
**作为参数传递给这个函数。
*/?
void in_order_traverse( void (*callback)( TREE_TYPE value ) );

/*
**post_order_traverse
**执行树的后序遍历。它的参数是一个回调函数指针，它所指向的函数将在树中处理每个节点时被调用，节点的值
**作为参数传递给这个函数。
*/?
void post_order_traverse( void (*callback)( TREE_TYPE value ) );

/* tree.cpp的内容如下：

/*
**一个使用动态分配的链式结构实现的二叉搜索树。
*/
#include "tree.h"
#include <assert.h>
#include <stdio.h>
#include <malloc.h>

/*
**指向树根节点的指针。?
*/?
static TreeNode *tree;

/*
**print?
**打印数组中的某个值。?
*/
void print( TREE_TYPE value ){
?? ?printf( "%d ", value );?? ?
}

/*
**insert
*/
void?
insert( TREE_TYPE value ){
?? ?TreeNode *current;
?? ?TreeNode **link;
?? ?
?? ?/*
?? ?**从根节点开始。?
?? ?*/?
?? ?link = &tree;
?? ?/*
?? ?**持续查找值，进入合适的子树。
?? ?*/
?? ?while( (current = *link) != NULL ){
?? ??? ?/*
?? ??? ?**根据情况，进入左子树或右子树（确认没有出现重复的值）
?? ??? ?*/
?? ??? ?if( value < current->value ){
?? ??? ??? ?link = &current->left;
?? ??? ?}else{
?? ??? ??? ?assert( value != current->value );
?? ??? ??? ?link = &current->right;
?? ??? ?}
?? ?}
?? ?
?? ?/*
?? ?**分配一个新节点，使适当节点的link字段指向它。
?? ?*/
?? ?current = (TreeNode *)malloc( sizeof( TreeNode ) );
?? ?assert( current != NULL );
?? ?current->value = value;
?? ?current->left = NULL;
?? ?current->right = NULL;
?? ?*link = current;?
}?

/*
**find
*/
TREE_TYPE *
find( TREE_TYPE value ){
?? ?TreeNode *current;
?? ?
?? ?/*
?? ?**从根节点开始，直到找到这个值，进入合适的子树。
?? ?*/
?? ?current = tree;
?? ?
?? ?while( current != NULL && current->value != value ){
?? ??? ?/*
?? ??? ?**根据情况，进入左子树或右子树。
?? ??? ?*/
?? ??? ?if( value < current->value ){
?? ??? ??? ?current = current->left;?
?? ??? ?}else{
?? ??? ??? ?current = current->right;
?? ??? ?}
?? ?}
?? ?if( current != NULL ){
?? ??? ?return &current->value;
?? ?}else{
?? ??? ?return NULL;
?? ?}
}

/*
**find_2
**查找一个特定值，这个值作为第1个参数传递给函数。
*/
TreeNode *find_2( TREE_TYPE value ){
?? ?TreeNode *current;
?? ?
?? ?/*
?? ?**从根节点开始，直到找到这个值，进入合适的子树。
?? ?*/
?? ?current = tree;
?? ?
?? ?while( current != NULL && current->value != value ){
?? ??? ?/*
?? ??? ?**根据情况，进入左子树或右子树。
?? ??? ?*/
?? ??? ?if( value < current->value ){
?? ??? ??? ?current = current->left;?
?? ??? ?}else{
?? ??? ??? ?current = current->right;
?? ??? ?}
?? ?}
?? ?return current;
}

/*
**destroy_tree
**删除树中单个的节点。?
*/
void destroy_tree( TREE_TYPE value ){
?? ?TreeNode *p = find_2( value );
?? ?if( p ){
?? ??? ?printf( "%d ", p->value );
?? ?}
?? ?free( p );
}

/*
**do_pre_order_traverse
**执行一层前序遍历。这个帮助函数用于保存当前正在处理的节点的信息。
**这个函数并不是用户接口的一部分。
*/
static void?
do_pre_order_traverse( TreeNode *current, void (*callback)( TREE_TYPE value ) ){
?? ?if( current != NULL ){
?? ??? ?callback( current->value );
?? ??? ?do_pre_order_traverse( current->left, callback );
?? ??? ?do_pre_order_traverse( current->right, callback );
?? ?}
}?

/*
**pre_order_traverse
*/
void
pre_order_traverse( void (*callback)( TREE_TYPE value ) ){
?? ?do_pre_order_traverse( tree, callback );
}?

/*
**do_pre_order_traverse
**执行一层前序遍历。这个帮助函数用于保存当前正在处理的节点的信息。
**这个函数并不是用户接口的一部分。
*/
static void?
do_in_order_traverse( TreeNode *current, void (*callback)( TREE_TYPE value ) ){
?? ?if( current != NULL ){
?? ??? ?do_in_order_traverse( current->left, callback );
?? ??? ?callback( current->value );
?? ??? ?do_in_order_traverse( current->right, callback );
?? ?}
}?

/*
**in_order_traverse
*/
void
in_order_traverse( void (*callback)( TREE_TYPE value ) ){
?? ?do_in_order_traverse( tree, callback );
}?

/*
**do_post_order_traverse
**执行一层前序遍历。这个帮助函数用于保存当前正在处理的节点的信息。
**这个函数并不是用户接口的一部分。
*/
static void?
do_post_order_traverse( TreeNode *current, void (*callback)( TREE_TYPE value ) ){
?? ?if( current != NULL ){
?? ??? ?do_post_order_traverse( current->left, callback );
?? ??? ?do_post_order_traverse( current->right, callback );
?? ??? ?callback( current->value );
?? ?}
}?

/*
**post_order_traverse
*/
void
post_order_traverse( void (*callback)( TREE_TYPE value ) ){
?? ?do_post_order_traverse( tree, callback );
}?

/* 输出：

*/?