operationfamilytree.cpp

数据结构——家谱的实现 本人的课程设计 MFC

	case 10:
	case 12:
		if(date.day<1||date.day>31)
			return false;
		else 
			return true;
		break;
	case 4:
	case 6:
	case 9:
	case 11:
		if(date.day<1||date.day>30)
			return false;
		else 
			return true;
		break;
	case 2:
		if(IsLeapYear(date.year)){
			if(date.day<1||date.day>29)
				return false;
			else 
				return true;
		}
		else{
			if(date.day<1||date.day>28)
				return false;
			else 
				return true;
		}
		break;
	default:
		return false;
	}

}

int COperationFamilytree::CompareDate(Date date1, Date date2)
{
	//本函数比较两日期大小:
	//date1比date2早,返回-1;date1比date2晚,返回1;date1与date2相等,返回0
	if(date1.year>date2.year)
		return 1;
	else if(date1.year<date2.year)
		return -1;
	else if(date1.month>date2.month)
		return 1;
	else if(date1.month<date2.month)
		return -1;
	else if(date1.day>date2.day)
		return 1;
	else if(date1.day<date2.day)
		return -1;
	else 
		return 0;

}

bool COperationFamilytree::IsLeapYear(int year)
{
	//本函数判断year是否为闰年
	if(year%4!=0)
		return false;
	else if(year%400==0)
		return true;
	else if(year%100==0)
		return false;
	else
		return true;
}

void COperationFamilytree::InsertSibling(Person &firstSibling,Person insertSibling)
{
	//本函数把insertSibling结点插入到以firstSibling为第一个结点的兄弟结点中
	//使兄弟结点以年龄排序
	Person pCur,pPre;
	pCur=firstSibling;							//pCur为第一个孩子
	//pCur不是第一个孩子,则pPre为pCur的前一个兄弟,否则pPre为pCur的父亲
	pPre=firstSibling->parent;
	for(;pCur!=0;pCur=pCur->sibling){			//兄弟之间以年龄大小排序(年龄大的在最前)
		if(CompareDate(pCur->info.birthday,insertSibling->info.birthday)>=0)
			break;
		pPre=pCur;
	}
	if(pCur==firstSibling){						//如果insertSibling的年龄比第一个孩子大
		insertSibling->sibling=firstSibling;	//则insertSibling应为pPre的第一个孩子
		pPre->child=insertSibling;
	}
	else{										//插入到相应位置
		insertSibling->sibling=pCur;
		pPre->sibling=insertSibling;
	}
}

void COperationFamilytree::Add(Person parent, Person addNode)
{
	//本函数把addNode结点加入到其父结点parent下
	addNode->child=addNode->sibling=0;			//把欲加入的结点所有指针域置空
	addNode->parent=parent;						//因addNode欲加为parent的孩子，故addNode结点的父指针域应指向parent
	if(parent==0){								//若parent为0，则表示欲加addNode为根结点
		if(T==0){								//若本为空家谱
			T=addNode;							//把addNode当成根结点
			return;
		}
		addNode->child=T;						//使原来的根结点成为新根结点的孩子
		T->parent=addNode;						
		T=addNode;
		return;
	}
	if(parent->child==0)						//parent无孩子，把addNode加入其孩子
		parent->child=addNode;
	else
		InsertSibling(parent->child,addNode);	//把addNode加到parent孩子的兄弟域中
}

void COperationFamilytree::Delete(Person &rootNode)
{
	//本函数删除以rootNode为根结点的所有结点
	if(rootNode->parent)						//如果rootNode有父结点				
		if(rootNode->parent->child==rootNode)	//如果rootNode为其父结点的第一个孩子
			rootNode->parent->child=rootNode->sibling;	//因要删掉rootNode,故把其父结点的孩子指针指向rootNode的第一个兄弟
		else{									//如果rootNode不是父结点的第一个孩子
			Person p=rootNode->parent->child;	//找到rootNode应在兄弟中的位置
			for(;p->sibling!=rootNode;p=p->sibling)
				;
			p->sibling=rootNode->sibling;		//插入到兄弟中
		}
	PostOrderTraverse(rootNode->child,DestroyNode);//删除以rootNode->child为根结点的所有结点
	if(rootNode==T)									//删除rootNode结点。如果rootNode为根结点，则删除根结点T
		DestroyNode(T);
	else
		DestroyNode(rootNode);
}

void COperationFamilytree::Modify(Person &pNode, Person newValue)
{
	//本函数用结点newValue中的信息来修改结点pNode中的信息
	strcpy(pNode->info.name,newValue->info.name);
	strcpy(pNode->info.addr,newValue->info.addr);
	pNode->info.birthday=newValue->info.birthday;
	pNode->info.marry=newValue->info.marry;
	pNode->info.live=newValue->info.live;
	if(!pNode->info.live)					//如过世,还应有死亡日期
		pNode->info.deathday=newValue->info.deathday;
}


Person& COperationFamilytree::GetRoot()
{
	//本函数返回家谱的根结点
	return T;
}

int COperationFamilytree::ChildNums(Person pNode)
{
	//本程序返回pNode的孩子数
	Person p;
	p=pNode->child;
	int childnums=0;
	for(;p!=0;p=p->sibling)
		childnums++;
	return childnums;
}

int COperationFamilytree::InSiblingPos(Person pNode)
{
	//本函数返回pNode结点在其兄弟中的排行
	int pos=1;
	Person p=pNode->parent;
	if(p){
		p=p->child;
		for(;p!=pNode&&p!=0;p=p->sibling)
			pos++;
	}
	return pos;
}

int COperationFamilytree::InGenerationPos(Person pNode)
{
	//本函数返回pNode结点在第几代
	int pos=1;
	Person p;
	p=pNode->parent;
	for(;p!=0;p=p->parent)
		pos++;
	return pos;
}

void COperationFamilytree::SortByBirthday(QuickSortNode *order)
{
	//本函数对顺序表order以出生日期的大小排序
	int totalNums=0;
	QuickSortNode* startaddr=order;
	startaddr++;
	GetPersonNums(T,totalNums);
	CopyInfoFromBiTreeToArray(T,startaddr);
	QuickSort(order,1,totalNums);
}

int COperationFamilytree::Partition(QuickSortNode *order, int low, int high)
{
	//本函数供QuickSort函数调用
	//交换顺序表order中从low到high的记录，便枢轴记录到位，并返回其所在位置，此时
	//在它之前（后）的记录均不大（小）于它
	order[0]=order[low];				//用子表的第一个记录做枢轴记录				
	Date pivotkey=order[low].birthday;	//枢轴记录关键字
	while(low<high){					//从表的两端交替地向中间扫描
		while(low<high&&(CompareDate(order[high].birthday,pivotkey)==1
						||CompareDate(order[high].birthday,pivotkey)==0))
			--high;
		order[low]=order[high];			//将比枢轴记录小的记录移到低端
		order[low].birthday=order[high].birthday;				//枢轴记录到位
		order[low].oneself=order[high].oneself;
		while(low<high&&(CompareDate(order[low].birthday,pivotkey)==-1
						||CompareDate(order[low].birthday,pivotkey)==0))
			++low;
		order[high]=order[low];			//将比枢轴记录大的记录移到高端
	}
	order[low]=order[0];				//枢轴记录到位
	return low;							//返回枢轴位置
}

void COperationFamilytree::QuickSort(QuickSortNode *order, int low, int high)
{
	//本函数对顺序表order[low...high]作快速排序
	int pivotloc;
	if(low<high){									//长度大于1
		pivotloc=Partition(order,low,high);			//将order[low...high]一分为二
		QuickSort(order,low,pivotloc-1);			//对低子表递归排序，pivotloc是枢轴位置
		QuickSort(order,pivotloc+1,high);			//对高子表递归排序
	}
}

void COperationFamilytree::GetPersonNums(Person&T,int& personNums)
{
	//本函数返回以T为根结点的所有结点数，并把结果存入personNums中
	//初始值personNums必须为0
	if(T){
		personNums++;
		GetPersonNums(T->child,personNums);			//递归调用
		GetPersonNums(T->sibling,personNums);
	}
}

void COperationFamilytree::CopyInfoFromBiTreeToArray(Person &T, QuickSortNode *&order)
{
	//本函数先序遍历以T为根结点的所有结点，并把每一个结点的出生日期信息及其指针值
	//依次存入顺序表order中
	if(T){
		(*order).birthday=T->info.birthday;
		(*order).oneself=T;
		order++;
		CopyInfoFromBiTreeToArray(T->child,order);
		CopyInfoFromBiTreeToArray(T->sibling,order);
	}
}