好库网 好库网首页 | 我的好库
VC开发指南

C语言实现树的动态查找

发布者:vchelp
发布日期:2013/6/5 19:45:12   更新日期:2013/6/5 19:45:12
阅读次数:3484
评分:4.80
介绍:本例演示一种树数据结构存储记录集合时的动态查找方法。
正文:

 

本例演示一种树数据结构存储记录集合时的动态查找方法。首先程序通过construct()函数,利用已经存在的结构体数组数据建立一个二叉树,建立树的过程中,要保证每个节点的值都大于它的左子树上节点的值而小于它右子树所有节点的值,该函数返回建立树的根指针;然后通过函数Search(root,name)查找,如果找到相应的数据,将其打印出来,如果没有找到,则用户可以选择是否将该数据插入到树中。

 

具体代码如下:

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#define NUM 4

struct tree
{
	char name[20];
	char city[20];
	char sex[10];
	char age[10];
	char job[10];
	struct tree *left;
	struct tree *right;
};

struct tree Datas[NUM]=
{
	"Willing","Tianjing","Female","21","worker",NULL,NULL,
	"Tom","Beijing","Male","31","doctor",NULL,NULL,
	"Sun","Weifang","Male","24","student",NULL,NULL,
	"Marry","Shanghai","Female","19","techer",NULL,NULL
};

struct tree *construct(
	struct tree *root, 
	struct tree *r, 
	struct tree *Data)
{
	if(!r)
	{
		r = (struct tree *)malloc(sizeof(struct tree));
		if(!r)
		{
			printf("内存分配失败!");
			exit(0);
		}
		r->left = NULL;
		r->right = NULL;
		strcpy(r->name,Data->name);
		strcpy(r->city,Data->city);
		strcpy(r->sex,Data->sex);
		strcpy(r->age,Data->age);
		strcpy(r->job,Data->job);
		if(!root)
			return r;
		if(strcmp(Data->name,root->name)<0)
			root->left = r;
		else 
			root->right = r;
		return r;
	}
	if(strcmp(Data->name,r->name)<0)
		construct(r,r->left,Data);
	else
		construct(r,r->right,Data);

	return root;	
}

struct tree *Search(root,name)
struct tree *root;
char name[];
{
	struct tree *p;
	if(root == NULL)
		printf("该树为空\n");
	p = root;
	while(strcmp(p->name,name)!=0)
	{
		if(strcmp(p->name,name)>0)
			p = p->left;
		else
			p = p->right;
		if(p == NULL)
			break;
	}
	return(p);
}

void print(struct tree *r)
{
	if(!r)
		return;
	print(r->left);
	printf("%s\n",r->name);
	print(r->right);
}

void print_currentData(struct tree *point)
{
	if(point == NULL)
		return;
	printf("	姓名:%s\n",point->name);
	printf("	城市:%s\n",point->city);
	printf("	性别:%s\n",point->sex);
	printf("	年龄:%s\n",point->age);
	printf("	工作:%s\n",point->job);
}

int main(void)
{
	int i;
	char c[10];
	char swap[20];
	char name[20];
	struct tree *root,*p;
	struct tree *temp;
	p = NULL;
	temp = NULL;
	root = NULL;
	for(i = 0;i<NUM;i++)
		root =construct(root,root,&Datas[i]);
	printf("现有人员资料:\n");
	print(root);
	printf("请输入要查找的人的名字\n");
	scanf("%s",name);
	p = Search(root,name);
	if(p == NULL)
	{
		printf("没有该人资料\n");
		printf("是否要插入该人资料[y/n]\n");
		scanf("%s",c);
		if(strcmp(c,"y")==0)
		{
			temp = (struct tree *)malloc(sizeof(struct tree));
			if(!temp)
			{
				printf("内存分配失败!");
				exit(0);
			}
			printf("请输入该人姓名:\n");
			scanf("%s",swap);
			strcpy(temp->name,swap);
			printf("请输入该人所在城市:\n");
			scanf("%s",swap);
			strcpy(temp->city,swap);
			printf("请输入该人性别[Male/Female]:\n");
			scanf("%s",swap);
			strcpy(temp->sex,swap);
			printf("请输入该人年龄:\n");
			scanf("%s",swap);
			strcpy(temp->age,swap);
			printf("请输入该人工作:\n");
			scanf("%s",swap);
			strcpy(temp->job,swap);
			temp->left = NULL;
			temp->right = NULL;
			root =construct(root,root,temp);
			print_currentData(temp);
			printf("现有人员资料:\n");
			root = root;
			print(root);
		}
		else 
			return 0;
	}
	print_currentData(p);
	return 1;
}

 


评论 [发表评论]
账号 密码 还没帐号呢,现在注册一个?

免责声明:好库网所展示的信息由买卖双方自行提供,其真实性、准确性和合法性由信息发布人负责。好库网不提供任何保证,并不承担任何法律责任。