202667.cpp

数据结构（清华版）

#include<iostream.h>
#include<fstream.h> 
//using namespace std;
//======================================================================================
typedef char TElemtype;//创建树结构体
typedef struct TNode
{
	TElemtype data;
	TNode *firstchild ,*nextsibling;
}*Tree;




//创建链队列结构体===================================================================
typedef Tree QElemtype;
typedef struct QNode
{
	QElemtype data;QNode *next;
} *LQueuePtr;
struct LQueue
{
	LQueuePtr front,rear;
};
//创建空队
void QueueInit(LQueue &Q)
{
	Q.front=new QNode;
	Q.front->next=NULL;
	Q.rear=Q.front;
}
//创建入列函数
void Enqueue(LQueue &Q,QElemtype e)
{
    LQueuePtr p;
	p=new QNode;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
//创建出队函数
bool Dequeue(LQueue &Q,QElemtype &e)
{
	LQueuePtr p;
	if (Q.front==Q.rear) return false;
	p=Q.front;
	Q.front=p->next;
	e=Q.front->data;
	delete p;
	return true;
}

//构建空树函数================================================================================
void CreateNode(Tree &T,TElemtype c)
{
	T=new TNode;T->data=c;
	T->firstchild=T->nextsibling=NULL;
}

//创建函数读入二元表序列构建孩子兄弟链表
void CreateTree(Tree &T,char fn[])
{
	LQueue q;Tree s,t,z;int i(0);
	ifstream f;TElemtype p,c;
	T=NULL;
	f.open(fn,ios::nocreate);
	if(!f) return;
	QueueInit(q);
	while (!f.eof())
	{
		f>>p>>c;
		if(c=='^') break;
		else if(p=='^')
		{
			CreateNode(T,c);Enqueue(q,T);
			s=T;
		}
		else
		{
			while(s->data!=p) {Dequeue(q,s);i=0;}
			CreateNode(t,c);
			if(i==0) {s->firstchild=t;i++;z=s->firstchild;}
			if(i==1) {z->nextsibling=t;z=z->nextsibling;}
			Enqueue(q,t);
		}
	}
	f.close();
}


//构建输出函数=====================================================================
void visit(TElemtype e)
{
	cout<<e;
}
//构建广义表输出函数
void Treelists(Tree T,void visit(TElemtype))
{
	Tree p;
	if(!T) return;visit(T->data);
	p=T->firstchild;
	if (p)
	{
		cout<<'(';
		while(p)
		{Treelists(p,visit);p=p->nextsibling;
		if(p)cout<<',';

		}
		cout<<')';
	}
}
//主函数============================================================================
void main()
{
	Tree T;
	CreateTree(T, "667.txt");
	cout<<"此树为   ";
	Treelists( T,visit);
	cout<<endl;
}