算法导论实验二.rar

算法导论实验二.rar

#include
#include
#include
#include
#include

#define NUMBER_SIZE 150		

char inputpath[]        =“../input/input_numbers.txt“;		//路径名 
char preorderpath[]     =“../output/size20/preorder.txt“;
char inorderpath[]      =“../output/size20/inorder.txt“;
char postorderpath[]    =“../output/size20/postorder.txt“;
char time1path[]        =“../output/size20/time1.txt“;
char deletedatapath[]   =“../output/size20/delete_data.txt“;
char time2path[]        =“../output/size20/time2.txt“;
char deleteinorderpath[]=“../output/size20/delete_inorder.txt“;

int num[150];		//全局数组 

enum ColorTypedef {
	RED
	BLACK
};

typedef struct RBTREENODE{			//定义树节点结构 
	int    data;
	int	   size; 
	enum   ColorTypedef color;
	struct RBTREENODE *left;
	struct RBTREENODE *right;
	struct RBTREENODE *p;
}rbTreeNode;

typedef struct RBTREE{		 
	rbTreeNode *root;
	rbTreeNode *nil;
}rbTree;	

/************************************随机生成数据********************************/ 

void dataRandProduce（ ）{
	
	int   ij; 
	FILE  *fp;
	if（ （ fp = fopen（ inputpath  “w“ ） ） == NULL ）{
		printf（ “file open failure !\n“ ）;
	}else{
		srand（ time（ NULL ） ）;
		num[0] = 1 + rand（ ） % NUMBER_SIZE;
		for（ i = 1; i < NUMBER_SIZE; i++ ）{			//每次生成一个数与之前生成过的所有数比较，若相同 
			num[i] = 1 + rand（ ） % NUMBER_SIZE;		//则重新生成 
			for（ j = 0; j < i; j++ ）{
				if（ num[i] == num[j] ）{
					i--;
					break;
				}
			}	
		}
		for（ i = 0; i < NUMBER_SIZE; i++ ）{
			fprintf（ fp  “%d\n“  num[i] ）;
		}
	}
	fclose（ fp ）;
}

/************************************红黑树初始化********************************/ 

rbTree * RBTreeInit（ ）{	
	
	rbTree *T = NULL;
	T = （ rbTree * ） malloc （ sizeof（ rbTree ） ）;
	if（ T == NULL ）{
		printf（ “T has no space !\n“ ）;
	}
	T->nil = （ rbTreeNode * ） malloc （ sizeof（ rbTreeNode ） ）;
	if（ T->nil == NULL ）{
		printf（ “T->nil has no space !\n“ ）;
	}
	T->root = T->nil;
	
	T->nil->data = NULL;
	T->nil->size = 0;
	T->nil->color = BLACK;
	T->nil->left = NULL;
	T->nil->right = NULL;
	T->nil->p = NULL;
	
	return T;	
} 

/************************************红黑树左旋和右旋********************************/ 

static void leftRotate（ rbTree *T  rbTreeNode * x ）{		//红黑树左旋 
	
	rbTreeNode *y = x->right;

	x->right = y->left;
	if（ y->left != T->nil ）
		y->left->p = x;
	y->p = x->p;
	if（ x->p == T->nil ）
		T->root = y;
	else if（ x == x->p->left ）
		x->p->left = y;
	else
		x->p->right = y;

	y->left = x;
	x->p = y;
	
	y->size = x->size;
	x->size = x->left->size + x->right->size +1;
}

static void rightRotate（ rbTree *T  rbTreeNode *x ）{		//红黑树右旋 
	
	rbTreeNode * y = x->left;

	x->left = y->right;
	if（ y->right != T->nil ）
		y->right->p = x;
	y->p = x->p;
	if（ x->p == T->nil ）
		T->root = y;
	else if（ x == x->p->left ）
		x->p->left = y;
	else
		x->p->right = y;

	y->right = x;
	x->p = y;
	
	x->size = y->size;
	y->size = y->left->size + y->right->size +

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        642  2016-11-09 19:18  PB14011022-project2\input\input_numbers.txt

     文件         46  2016-11-09 19:18  PB14011022-project2\output\size20\delete_data.txt

     文件         75  2016-11-09 19:18  PB14011022-project2\output\size20\delete_inorder.txt

     文件         83  2016-11-09 19:18  PB14011022-project2\output\size20\inorder.txt

     文件         83  2016-11-09 19:18  PB14011022-project2\output\size20\postorder.txt

     文件         83  2016-11-09 19:18  PB14011022-project2\output\size20\preorder.txt

     文件         96  2016-11-11 22:06  PB14011022-project2\output\size20\time1.txt

     文件         72  2016-11-11 22:07  PB14011022-project2\output\size20\time2.txt

     文件         46  2016-11-09 19:18  PB14011022-project2\output\size40\delete_data.txt

     文件        162  2016-11-09 19:18  PB14011022-project2\output\size40\delete_inorder.txt

     文件        170  2016-11-09 19:18  PB14011022-project2\output\size40\inorder.txt

     文件        170  2016-11-09 19:18  PB14011022-project2\output\size40\postorder.txt

     文件        170  2016-11-09 19:18  PB14011022-project2\output\size40\preorder.txt

     文件        192  2016-11-11 22:07  PB14011022-project2\output\size40\time1.txt

     文件         71  2016-11-11 22:07  PB14011022-project2\output\size40\time2.txt

     文件         46  2016-11-09 19:18  PB14011022-project2\output\size60\delete_data.txt

     文件        249  2016-11-09 19:18  PB14011022-project2\output\size60\delete_inorder.txt

     文件        257  2016-11-09 19:18  PB14011022-project2\output\size60\inorder.txt

     文件        257  2016-11-09 19:18  PB14011022-project2\output\size60\postorder.txt

     文件        257  2016-11-09 19:18  PB14011022-project2\output\size60\preorder.txt

     文件        288  2016-11-11 22:08  PB14011022-project2\output\size60\time1.txt

     文件         72  2016-11-11 22:08  PB14011022-project2\output\size60\time2.txt

     文件         46  2016-11-09 19:18  PB14011022-project2\output\size80\delete_data.txt

     文件        333  2016-11-09 19:18  PB14011022-project2\output\size80\delete_inorder.txt

     文件        341  2016-11-09 19:18  PB14011022-project2\output\size80\inorder.txt

     文件        341  2016-11-09 19:18  PB14011022-project2\output\size80\postorder.txt

     文件        341  2016-11-09 19:18  PB14011022-project2\output\size80\preorder.txt

     文件        383  2016-11-11 22:10  PB14011022-project2\output\size80\time1.txt

     文件         71  2016-11-11 22:11  PB14011022-project2\output\size80\time2.txt

     文件      17306  2016-11-08 20:25  PB14011022-project2\source\ex.cpp

............此处省略13个文件信息