文档章节

C和指针---第十七章:经典抽象数据类型

fzyz_sb
 fzyz_sb
发布于 2013/09/25 09:58
字数 4126
阅读 114
收藏 0
点赞 0
评论 0

17.1 内存分配

所有的ADT都必须确定一件事情---如何获取内存来存储值.有三种可选的方案:静态数组,动态分配的数组和动态分配的链式结构.

17.2 堆栈

17.2.1 接口

/*
**一个堆栈模块的接口
*/

#define STACK_TYPE int /* 堆栈所存储的值的类型 */
 
/*
** 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 );
一: 数组堆栈

备注:所有不属于外部接口的内容都被声明为static,这可以防止用户使用预定义接口之外的任何方式访问堆栈中的值.

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

#include "stack.h"
#include <assert.h>

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

static STACK_TYPE	stack[ STACK_SIZE ];
static int			top_element = -1;

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

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

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

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

int is_full( void )
{
	return STACK_SIZE - 1 == top_element;
}
二:动态数组堆栈

我们先声明两个额外的函数:

/*
** create_stack
** 创建堆栈.参数指定堆栈可以保存多少个元素
*/
void create_stack( size_t size );

/*
** destroy_stack
** 销毁堆栈,它释放堆栈所使用的内存
*/
void destroy_stack( void );
接口实现:
/*
** 一个用动态分配数组实现的堆栈
** 堆栈的长度在创建堆栈的函数被调用时给出,该函数必须在任何其他操作堆栈的函数被调用之前调用
*/

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

static STACK_TYPE	*stack;
static size_t		stack_size;
static int			top_element = -1;

void create_stack( size_t size )
{
	assert( 0 == stack_size );
	stack_size = size;
	stack = malloc( stack_size * sizeof( STACK_TYPE ) );
	assert( NULL != stack );
}

void destroy_stack( void )
{
	assert( stack_size > 0 );
	stack_size = 0;
	free( stack );
	stack = NULL;
}

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

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

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

int is_empty( void )
{
	assert( stack_size > 0 );
	return -1 == top_element;
}

int is_full( void )
{
	assert( stack_size > 0 );
	return top_element == stack_size - 1;
}
三:链式堆栈

由于只有堆栈的顶部元素才可以被访问,所以使用单链表就可以很好的实现链式堆栈.把一个新元素压入到堆栈是通过在链表的起始位置添加一个元素实现的.从堆栈中弹出一个元素是通过从链表中移除第一个元素实现的.位于链表头部的元素总是很容易被访问.

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

#define FALSE 0

typedef struct STACK_NODE {
	STACK_TYPE			value;
	struct STACK_NODE	*next;
} StackNode;

static StackNode *stack;

void create_stack( size_t size )
{

}

void destroy_stack( void )
{
	while ( !is_empty() ){
		pop();
	}
}

void push( STACK_TYPE value )
{
	StackNode *new_node;

	new_node = malloc( sizeof( StackNode ) );
	assert( NULL != new_node );
	new_node->value = value;
	new_node->next = stack;		//这里是关键,将新建节点插入到头部
	stack = new_node;
}

void pop( void )
{
	StackNode *first_node;
	assert( !is_empty() );
	first_node = stack;
	stack = first_node->next;
	free( first_node );
}

STACK_TYPE top( void )
{
	assert( !is_empty() );
	return stack->value;
}

int is_empty( void )
{
	return NULL == stack;		//备注:这里静态创建stack,所以本身会被初始化为NULL.如果非静态,请手动初始化为NULL
}

int is_full( void )
{
	return FALSE;
}

17.3 队列

接口:

/*
** 一个队列模块的接口
*/

#include <stdlib.h>

#define QUEUE_TYPE int

/*
** create_queue
** 创建一个队列,参数指定队列可以存储的元素的最大数量
*/
void create_queue( size_t size );

/*
** 销毁一个队列.
*/
void destroy_queue( void );

/*
** insert
** 向队列添加一个新元素,参数就是需要添加的元素
*/
void insert( QUEUE_TYPE value );

/*
** delete
** 从队列中移除一个元素并将其丢弃
*/
void delete( void );

/*
** first
** 返回队列中第一个元素的值,但不修改队列本身
*/
QUEUE_TYPE first( void );

/*
** is_empty
** 如果队列为空,返回TRUE,否则返回FALSE
*/
int is_empty( void );

/*
** is_full
** 如果队列已满,返回TRUE,否则返回FALSE
*/
int is_full( void );
实现:
/*
** 一个用静态数组实现的队列.数组的长度只能通过修改#define定义并重新编译模块来调整
*/

#include "queue.h"
#include <stdio.h>
#include <assert.h>

#define QUEUE_SIZE	100
#define ARRAY_SIZE	( QUEUE_SIZE + 1 )

static QUEUE_TYPE	queue[ ARRAY_SIZE ];
static size_t		front = 1;	//第一个元素空出来,用于判断队列满还是空
static size_t		rear = 0;

void insert( QUEUE_TYPE value )
{
	assert( !is_full() );
	rear = ( rear + 1 ) % ARRAY_SIZE;
	queue[ rear ] = value;
}

void delete( void )
{
	assert( !is_empty() );
	front = ( front + 1 ) % ARRAY_SIZE;
}

QUEUE_TYPE first( void )
{
	assert( !is_empty() );
	return queue[ front ];
}

int is_empty( void )
{
	return ( rear + 1 ) % ARRAY_SIZE == front;
}

int is_full( void )
{
	return ( rear + 2 ) % ARRAY_SIZE == front;
}

17.4 数---二叉搜索树

17.4.5 二叉搜索树的接口

#define TREE_TYPE int

/*
** insert
** 向树添加一个新值.参数是需要被添加的值,它必须原先并不存在于树中
*/
void insert( TREE_TYPE value );

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

/*
** pre_order_traverse
** 执行树的前序遍历.它的参数是一个回调函数指针,它所指向的函数将在树中处理每个
** 节点被调用,节点的值作为参数传递给这个函数
*/
void pre_order_traverse( void ( *callback )( TREE_TYPE value ) );
实现:
/*
** 一个使用静态数组实现的二叉搜索树.数组的长度只能通过修改#define定义
** 并对模块进行重新编译来实现
*/
#include "tree.h"
#include <assert.h>
#include <stdio.h>

#define TREE_SIZE	100
#define ARRAY_SIZE	( TREE_SIZE + 1 )

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

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

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

void insert( TREE_TYPE value )
{
	int current;
	/*
	** 确保值为非零,因为零用于提示一个未使用的节点
	*/
	assert( 0 != value );

	/*
	** 从根节点开始
	*/
	current = 1;

	/*
	** 从适合的子树开始,知道到达一个叶节点
	*/
	while ( 0 != tree[ current ] ){
		if ( value < tree[ current ] ){
			current = left_child( current );
		}
		else{
			assert( value != tree[ current ] );		//直接终止程序非常不好,可以用return来代替
			current = right_child( current );
		}
		assert( current < ARRAY_SIZE );
	}
	tree[ current ] = value;
}

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;
	}
	
	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[ currentr ] );
		do_pre_order_traverse( left_child( current ), callback );
		do_pre_order_traverse( right_child( current ), callback );
	}
}

void pre_order_traverse( void ( *callback )( TREE_TYPE value ) )
{
	do_pre_order_traverse( 1, callback );
}
二叉树的链式实现:
/*
** 一个使用动态分配的链式结构实现的二叉搜索树.
*/
#include "tree.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

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


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

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 = malloc( sizeof( TreeNode ) );
	assert( NULL != current );
	current->value = value;
	current->left = NULL;
	current->right = NULL;
	*link = current;
}

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 ( NULL != current ){
		 return &current->value;
	 }

	 return NULL;
}

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

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

17.5 实现的改进

改进的方案就是用到面向对象的思想.但是不推荐用C的宏来完成面向对象--如果可以,请用C++.

(学习C后,才慢慢了解了一点C++,希望学完C后能学习下Java,更懂得C++.然后,当一名合格的C/C++程序员)

问题:

1.

void resize_stack( size_t newSize )
{
	assert( 0 == stack_size );
	stack_size = newSize;
	stack = realloc( stack, stack_size );
}


这里有中粗暴的方法是:直接销毁原来的堆栈,然后新malloc一个堆栈.但是这样的话,原来的数据均销毁了.所以,用realloc分配新的一块内存.

2.

#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


static QUEUE_TYPE	*queue;
static size_t		front = 1;	//第一个元素空出来,用于判断队列满还是空
static size_t		rear = 0;
static size_t		queue_size;
static size_t		array_size;

void create_queue( size_t size )
{
	assert( 0 == queue_size );
	queue_size = size;
	array_size = queue_size + 1;
	queue = malloc( queue_size * sizeof( QUEUE_TYPE ) );
	assert( NULL != queue );
}

void insert( QUEUE_TYPE value )
{
	assert( !is_full() );
	rear = ( rear + 1 ) % array_size;
	queue[ rear ] = value;
}

void delete( void )
{
	assert( !is_empty() );
	front = ( front + 1 ) % array_size;
}

QUEUE_TYPE first( void )
{
	assert( !is_empty() );
	return queue[ front ];
}

int is_empty( void )
{
	return ( rear + 1 ) % array_size == front;
}

int is_full( void )
{
	return ( rear + 2 ) % array_size == front;
}

3.

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

#define QUEUE_TYPE		int
typedef struct QUEUE{
	QUEUE_TYPE		value;
	struct QUEUE	*preNode;
	struct QUEUE	*nextNode;
} QueueNode;

static QueueNode *queue;

void push( QUEUE_TYPE value )
{
	QueueNode *newnode;
	newnode = malloc( sizeof( QueueNode ) );
	newnode->nextNode = queue;
	newnode->value = value;

	if ( queue ){
		queue->preNode = newnode;
		while ( queue->nextNode ){
			queue = queue->nextNode;
		}
		newnode->preNode = queue;		//不为空的时候,头节点的prenode指向最后一个节点

	}
	else{
		newnode->preNode = newnode;		//为空的时候,头节点指向自身
	}
	queue = newnode;
}

void pop()
{
	QueueNode *newnode;
	if ( queue->preNode == queue ){		//当只有一个值的时候,特殊处理
		free( queue );
		queue = NULL;
		return;
	}
	if ( queue ){
		newnode = queue->preNode;

		queue->preNode = newnode->preNode;
		newnode->preNode->nextNode = NULL;
		free( newnode );
	}
}

void delete( void )
{
	while ( NULL != queue ){
		pop();
	}
}

QUEUE_TYPE top( void )
{
	if ( queue ){
		return queue->preNode->value;
	}
	return -1;
}

int main(void)
{
	push( 1 );
	push( 2 );
	push( 3 );
	push( 4 );
	push( 5 );
	printf("%d\n", top() );	//5-->4-->3-->2-->1-->NULL 输出1
	pop();					//5-->4-->3-->2-->NULL
	pop();					//5-->4-->3-->NULL
	push( 10 );				//10-->5-->4-->3-->NULL
	printf("%d\n", top() );	//输出3
	pop();					//10-->5-->4-->NULL
	push( 111 );			//111-->10-->5-->4-->NULL
	printf("%d\n", top() );	//输出4

	return 0;
}
程序输出:

备注:并为进行严格的检查,比如空队列进行top时候,只是显示-1一样.

4.用数组,实际上很难实现的,或者说实现起来很麻烦.可以用链表实现:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


typedef struct STACK_NODE {
	int		*stack;
	int		size;
	int		top_elements;
} StackNode;

static StackNode stackArray[10];

void create_stack( int index, int size )
{
	assert( 0 == stackArray[ index ].size );
	stackArray[ index ].size = size;
	stackArray[ index ].stack = malloc( size * sizeof( int ) );
	assert( NULL != stackArray[ index ].stack );
	stackArray[ index ].top_elements = -1;
}

void delete_stack( int index )
{
	assert( index >= 0 && index < 10 );
	assert( stackArray[ index ].size > 0 );
	stackArray[ index ].size = 0;
	free( stackArray[ index ].stack );
	stackArray[ index ].stack = NULL;
}

int is_full( int index )
{
	assert( index >= 0 && index < 10 );
	assert( stackArray[ index ].size > 0);
	return stackArray[ index ].top_elements == stackArray[ index ].size - 1;
}
int is_empty( int index )
{
	assert( index >= 0 && index < 10 );
	assert( stackArray[ index ].size > 0);
	return -1 == stackArray[ index ].top_elements;
}

void push( int index, int value )
{
	assert( index >= 0 && index < 10 );
	assert( !is_full( index ) );
	stackArray[ index ].top_elements++;
	stackArray[ index ].stack[ stackArray[ index ].top_elements ] = value;	
}

void pop( int index )
{
	assert( index >= 0 && index < 10 );
	assert( !is_empty( index ) );
	stackArray[ index ].top_elements--;
}

int top( int index )
{
	assert( index >= 0 && index < 10 );
	assert( !is_empty( index ) );
	return stackArray[ index ].stack[ stackArray[ index ].top_elements ];
}

void printStack( int index )
{
	while ( !is_empty( index ) ){
		printf("%d ", top( index ) );
		pop( index );
	}

	printf("\n");
}

int main(void)
{
	int i = 0;
	int j = 0;
	for ( i = 0; i < 10; i++ ){
		create_stack( i, 10 );
	}
	for ( i = 0; i < 10; i++ ){
		for ( j = 0; j < 10; j++ ){
			push( i, j );
		}
	}

	for ( i = 0; i < 10; i++ ){
		printStack( i );
	}

	return 0;
}
程序输出:

5.

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

typedef struct TREE{
	struct TREE		*leftChild;
	struct TREE		*rightChild;
	int				value;
} TreeNode;

void insertNode( TreeNode **tree, int value )
{
	TreeNode *current;

	while ( NULL != *tree ){
		if ( value < ( *tree )->value ){
			tree = &( *tree )->leftChild;		//这里注意:要用tree而不是*tree.否则无法进行修改
		}
		else if ( value == ( *tree )->value ){
			return;
		}
		else{
			tree = &( *tree )->rightChild;
		}
	}

	current = malloc( sizeof( TreeNode ) );
	current->leftChild = NULL;
	current->rightChild = NULL;
	current->value = value;
	*tree = current;
}

void deleteNode( TreeNode **tree, int value )
{
	while ( NULL != *tree ){
		if ( value == ( *tree )->value ){
			break;
		}
		else if ( value < ( *tree )->value ){
			tree = &( *tree )->leftChild;
		}
		else{
			tree = &( *tree )->rightChild;
		}
	}

	if ( NULL == *tree ){		//为空时删除完毕
		return;
	}
	if ( NULL == ( *tree )->leftChild && NULL == ( *tree )->rightChild ){	//为叶节点
		free( *tree );
		*tree = NULL;
	}
	else if ( NULL == ( *tree )->leftChild && NULL != ( *tree )->rightChild ){	//包含左节点
		TreeNode *tempNode;
		tempNode = ( *tree );
		*tree = (*tree)->rightChild;
		free( tempNode );
	}
	else if ( NULL != ( *tree )->leftChild && NULL == ( *tree )->rightChild ){	//包含右节点
		TreeNode *tempNode;
		tempNode = ( *tree );
		*tree = ( *tree )->leftChild;
		free( tempNode );
	}
	else{
		TreeNode *tempNode = ( *tree )->leftChild;
		TreeNode *preNode = NULL;
		if ( NULL == tempNode->rightChild ){			//当子节点无右节点的时候,特殊处理
			( *tree )->value = tempNode->value;
			( *tree )->leftChild = tempNode->leftChild;
			return;
		}
		while ( tempNode->rightChild ){					//否则,将子树中的最大值(即最最右节点copy到删除节点上面)
			preNode = tempNode;
			tempNode = tempNode->rightChild;
		}
		(*tree)->value = tempNode->value;
		free( tempNode );
		tempNode = NULL;
		preNode->rightChild = NULL;
	}
}

int countNode( TreeNode *tree )
{
	static countNum = 0;
	if ( NULL != tree ){
		countNum++;
		countNode( tree->leftChild );
		countNode( tree->rightChild );
	}

	return countNum;
}

void pre_print( TreeNode *tree )
{
	if ( NULL != tree ){
		printf("%d ", tree->value );
		pre_print( tree->leftChild );
		pre_print( tree->rightChild );
	}
}

void mid_print( TreeNode *tree )
{
	if ( NULL != tree ){
		mid_print( tree->leftChild );
		printf("%d ", tree->value );
		mid_print( tree->rightChild );
	}
}

void last_print( TreeNode *tree )
{
	if ( NULL != tree ){
		last_print( tree->leftChild );
		last_print( tree->rightChild );
		printf("%d ", tree->value );
	}
}


int main( void )
{
	TreeNode *node = NULL;
	insertNode( &node, 5 );
	insertNode( &node, 3 );
	insertNode( &node, 8 );
	insertNode( &node, 2 );
	insertNode( &node, 4 );
	insertNode( &node, 1 );
	insertNode( &node, 6 );
	insertNode( &node, 9 );
	insertNode( &node, 7 );
	insertNode( &node, 10 );
	pre_print( node );
	printf("\n");
	mid_print( node );
	printf("\n");
	last_print( node );
	printf("\n");
	printf("%d\n", countNode( node ) );

	return 0;
}

程序输出:

6.

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

#define QUEUE_TYPE		TreeNode*

typedef struct TREE{
	struct TREE		*leftChild;
	struct TREE		*rightChild;
	int				value;
} TreeNode;

typedef struct QUEUE{
	QUEUE_TYPE		value;
	struct QUEUE	*preNode;
	struct QUEUE	*nextNode;
} QueueNode;

static QueueNode *queue;


void insertNode( TreeNode **tree, int value )
{
	TreeNode *current;

	while ( NULL != *tree ){
		if ( value < ( *tree )->value ){
			tree = &( *tree )->leftChild;		//这里注意:要用tree而不是*tree.否则无法进行修改
		}
		else if ( value == ( *tree )->value ){
			return;
		}
		else{
			tree = &( *tree )->rightChild;
		}
	}

	current = malloc( sizeof( TreeNode ) );
	current->leftChild = NULL;
	current->rightChild = NULL;
	current->value = value;
	*tree = current;
}

void deleteNode( TreeNode **tree, int value )
{
	while ( NULL != *tree ){
		if ( value == ( *tree )->value ){
			break;
		}
		else if ( value < ( *tree )->value ){
			tree = &( *tree )->leftChild;
		}
		else{
			tree = &( *tree )->rightChild;
		}
	}

	if ( NULL == *tree ){		//为空时删除完毕
		return;
	}
	if ( NULL == ( *tree )->leftChild && NULL == ( *tree )->rightChild ){	//为叶节点
		free( *tree );
		*tree = NULL;
	}
	else if ( NULL == ( *tree )->leftChild && NULL != ( *tree )->rightChild ){	//包含左节点
		TreeNode *tempNode;
		tempNode = ( *tree );
		*tree = (*tree)->rightChild;
		free( tempNode );
	}
	else if ( NULL != ( *tree )->leftChild && NULL == ( *tree )->rightChild ){	//包含右节点
		TreeNode *tempNode;
		tempNode = ( *tree );
		*tree = ( *tree )->leftChild;
		free( tempNode );
	}
	else{
		TreeNode *tempNode = ( *tree )->leftChild;
		TreeNode *preNode = NULL;
		if ( NULL == tempNode->rightChild ){			//当子节点无右节点的时候,特殊处理
			( *tree )->value = tempNode->value;
			( *tree )->leftChild = tempNode->leftChild;
			return;
		}
		while ( tempNode->rightChild ){					//否则,将子树中的最大值(即最最右节点copy到删除节点上面)
			preNode = tempNode;
			tempNode = tempNode->rightChild;
		}
		(*tree)->value = tempNode->value;
		free( tempNode );
		tempNode = NULL;
		preNode->rightChild = NULL;
	}
}

int countNode( TreeNode *tree )
{
	static countNum = 0;
	if ( NULL != tree ){
		countNum++;
		countNode( tree->leftChild );
		countNode( tree->rightChild );
	}

	return countNum;
}

void pre_print( TreeNode *tree )
{
	if ( NULL != tree ){
		printf("%d ", tree->value );
		pre_print( tree->leftChild );
		pre_print( tree->rightChild );
	}
}

void mid_print( TreeNode *tree )
{
	if ( NULL != tree ){
		mid_print( tree->leftChild );
		printf("%d ", tree->value );
		mid_print( tree->rightChild );
	}
}

void last_print( TreeNode *tree )
{
	if ( NULL != tree ){
		last_print( tree->leftChild );
		last_print( tree->rightChild );
		printf("%d ", tree->value );
	}
}

void value_print( TreeNode *tree )
{
	if ( tree ){
		printf("%d ", tree->value );
	}
}
//----------------------------//

void push( QUEUE_TYPE value )
{
	QueueNode *newnode;
	newnode = malloc( sizeof( QueueNode ) );
	newnode->nextNode = queue;
	newnode->value = value;

	if ( queue ){
		queue->preNode = newnode;
		while ( queue->nextNode ){
			queue = queue->nextNode;
		}
		newnode->preNode = queue;		//不为空的时候,头节点的prenode指向最后一个节点

	}
	else{
		newnode->preNode = newnode;		//为空的时候,头节点指向自身
	}
	queue = newnode;
}

void pop()
{
	QueueNode *newnode;
	if ( queue->preNode == queue ){		//当只有一个值的时候,特殊处理
		free( queue );
		queue = NULL;
		return;
	}
	if ( queue ){
		newnode = queue->preNode;

		queue->preNode = newnode->preNode;
		newnode->preNode->nextNode = NULL;
		free( newnode );
	}
}

void delete( void )
{
	while ( NULL != queue ){
		pop();
	}
}

QUEUE_TYPE top( void )
{
	if ( queue ){
		return queue->preNode->value;
	}
	return NULL;
}

int main( void )
{
	TreeNode *node = NULL;
	TreeNode *tempNode;
	insertNode( &node, 5 );
	insertNode( &node, 3 );
	insertNode( &node, 8 );
	insertNode( &node, 2 );
	insertNode( &node, 4 );
	insertNode( &node, 1 );
	insertNode( &node, 6 );
	insertNode( &node, 9 );
	insertNode( &node, 7 );
	insertNode( &node, 10 );

	push( node );
	while ( queue ){
		while ( queue ){
			tempNode = top();
			printf("%d-->", tempNode->value );
			pop();
			if ( tempNode->leftChild){
				push( tempNode->leftChild );
			}
			if ( tempNode->rightChild ){
				push( tempNode->rightChild );
			}
		}
	}
	printf("NULL\n");
	return 0;
}

程序输出:

7. 只要看中序是否是升序就可以了.

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

typedef struct TREE{
	struct TREE		*leftChild;
	struct TREE		*rightChild;
	int				value;
} TreeNode;

void insertNode( TreeNode **tree, int value )
{
	TreeNode *current;

	while ( NULL != *tree ){
		if ( value < ( *tree )->value ){
			tree = &( *tree )->leftChild;		//这里注意:要用tree而不是*tree.否则无法进行修改
		}
		else if ( value == ( *tree )->value ){
			return;
		}
		else{
			tree = &( *tree )->rightChild;
		}
	}

	current = malloc( sizeof( TreeNode ) );
	current->leftChild = NULL;
	current->rightChild = NULL;
	current->value = value;
	*tree = current;
}

void deleteNode( TreeNode **tree, int value )
{
	while ( NULL != *tree ){
		if ( value == ( *tree )->value ){
			break;
		}
		else if ( value < ( *tree )->value ){
			tree = &( *tree )->leftChild;
		}
		else{
			tree = &( *tree )->rightChild;
		}
	}

	if ( NULL == *tree ){		//为空时删除完毕
		return;
	}
	if ( NULL == ( *tree )->leftChild && NULL == ( *tree )->rightChild ){	//为叶节点
		free( *tree );
		*tree = NULL;
	}
	else if ( NULL == ( *tree )->leftChild && NULL != ( *tree )->rightChild ){	//包含左节点
		TreeNode *tempNode;
		tempNode = ( *tree );
		*tree = (*tree)->rightChild;
		free( tempNode );
	}
	else if ( NULL != ( *tree )->leftChild && NULL == ( *tree )->rightChild ){	//包含右节点
		TreeNode *tempNode;
		tempNode = ( *tree );
		*tree = ( *tree )->leftChild;
		free( tempNode );
	}
	else{
		TreeNode *tempNode = ( *tree )->leftChild;
		TreeNode *preNode = NULL;
		if ( NULL == tempNode->rightChild ){			//当子节点无右节点的时候,特殊处理
			( *tree )->value = tempNode->value;
			( *tree )->leftChild = tempNode->leftChild;
			return;
		}
		while ( tempNode->rightChild ){					//否则,将子树中的最大值(即最最右节点copy到删除节点上面)
			preNode = tempNode;
			tempNode = tempNode->rightChild;
		}
		(*tree)->value = tempNode->value;
		free( tempNode );
		tempNode = NULL;
		preNode->rightChild = NULL;
	}
}

int countNode( TreeNode *tree )
{
	static countNum = 0;
	if ( NULL != tree ){
		countNum++;
		countNode( tree->leftChild );
		countNode( tree->rightChild );
	}

	return countNum;
}

void pre_print( TreeNode *tree )
{
	if ( NULL != tree ){
		printf("%d ", tree->value );
		pre_print( tree->leftChild );
		pre_print( tree->rightChild );
	}
}

void mid_print( TreeNode *tree )
{
	if ( NULL != tree ){
		mid_print( tree->leftChild );
		printf("%d ", tree->value );
		mid_print( tree->rightChild );
	}
}

void last_print( TreeNode *tree )
{
	if ( NULL != tree ){
		last_print( tree->leftChild );
		last_print( tree->rightChild );
		printf("%d ", tree->value );
	}
}

void isTree( TreeNode *tree, int arr[] )
{
	static int i = 0;
	if ( NULL != tree ){
		isTree( tree->leftChild, arr );
		arr[ i++ ] = tree->value;
		isTree( tree->rightChild, arr );
	}
}


int main( void )
{
	TreeNode *node = NULL;
	int arr[10];
	int i = 0;
	insertNode( &node, 5 );
	insertNode( &node, 3 );
	insertNode( &node, 8 );
	insertNode( &node, 2 );
	insertNode( &node, 4 );
	insertNode( &node, 1 );
	insertNode( &node, 6 );
	insertNode( &node, 9 );
	insertNode( &node, 7 );
	insertNode( &node, 10 );

	for ( i = 0; i < 10; i++ ){
		arr[ i ] = 0;
	}

	isTree( node, arr );

	for ( i = 0; i < 9; i++ ){
		if ( arr[ i ] > arr[ i + 1 ]){
			break;
		}
	}
	if ( 9 == i ){
		printf("yes, it is right!\n");
	}


	return 0;
}
程序输出:

9.

void destroy_tree( TreeNode **tree )
{
	while ( *tree ){
		deleteNode( tree, ( *tree )->value );
	}
}

备注:进行添加和删除的时候,请把指针传递进去.

10.第七题已实现此功能,但不是终止程序,只是return了回去.

© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 404
博文 209
码字总数 447144
作品 0
武汉
程序员
[备忘]《C++入门经典》各章小节

《C++入门经典》(即英文版“Beginning C++ The Complete Language”的中译版) 各章小节 第1章 基本概念 ·C++中的程序至少包含一个main()函数。 ·函数的可执行部分由包含在一对花括号中的...

leeoo ⋅ 2011/12/24 ⋅ 0

第十七章 MariaDB

17.1 MariaDB简介 MariaDB数据库管理系统是MySQL的一个分支,主要由开源社区维护,采用GPL授权许可。MariaDB问世的目的是完全兼容MySQL,包括API和命令行,使之能轻松成为MySQL的代替品。在存...

忘情OK ⋅ 2017/06/30 ⋅ 0

C++快速入门

只学过Java的我最近笔试接触到各种C++的题目,于是稍微恶补了一下C++的基础部分,以下内容是基于《21天学通C++》的部分读书笔记,按照章节写的。 第二章 C++程序的组成部分 ①#include 预处理...

waffle930 ⋅ 2016/10/02 ⋅ 0

运维工作解释

运维工作解释 2017/3/9 PC小记:《运维之下》的文档作者对运维工作的解释清晰明了,有利于工作的划分和职业的规划,因而值得整理后分享。 https://github.com/opera443399/ops/tree/master/d...

pcnk ⋅ 2017/03/09 ⋅ 0

最基础的数据结构-左轻侯

作者:左轻侯 创建时间:2007-03-04 22:29:06 最后修改时间:2008-01-18 22:07:52 本文发表于《程序员》2007年第3期      最基础的数据结构   左轻侯   2007.2.3      引言   ...

一配 ⋅ 2015/10/16 ⋅ 0

第一章 数组与指针概念剖析

数组与指针生来就是双胞胎,多数人就是从数组的学习开始指针的旅程的。在学习的过程中,很自然就会经常听到或见到关于数组与指针的各种各样的看法,下面我节选一些在各种论坛和文章里经常见到...

北极心 ⋅ 2016/08/11 ⋅ 0

Linux内核编码规范

这是一个简短的文档,描述了linux内核的首选代码风格。代码风格是因人而异的,而且我不愿意把我的观点强加给任何人,不过这里所讲述的是我必须要维护的代码所遵守的风格,并且我也希望绝大多...

最新更新消息 ⋅ 2015/12/04 ⋅ 0

第七章 右左法则----复杂指针解析

首先看看如下一个声明: 这是一个会让初学者感到头晕目眩、感到恐惧的函数指针声明。在熟练掌握C/C++的声明语法之前,不学习一定的规则,想理解好这类复杂声明是比较困难的。 C/C++所有复杂的...

北极心 ⋅ 2016/08/11 ⋅ 0

void与void*详解

void关键字的使用规则: 1. 如果函数没有返回值,那么应声明为void类型; 2. 如果函数无参数,那么应声明其参数为void; 3. 如果函数的参数可以是任意类型指针,那么应声明其参数为void * ;...

ustbgaofan ⋅ 2015/01/07 ⋅ 0

c++ primer 第五版学习笔记

第二章 函数体外定义的内置类型变量会初始化为0,函数体外的是未初始化的 用constexpr声明变量表示它是一个常量表达式(编译器可以确定的值),且只能应用于字面值 c++11中可以用 来定义一个...

David栗子 ⋅ 2017/12/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 17分钟前 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部