数据结构C语言版树的双亲表存储表示.doc

《数据结构C语言版树的双亲表存储表示.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构C语言版树的双亲表存储表示.txt如果不懂就说出来，如果懂了，就笑笑别说出来。贪婪是最真实的贫穷，满足是最真实的财富。幽默就是一个人想哭的时候还有笑的兴致。/*数据结构C语言版树的双亲表存储表示P135编译环境：Dev-C++4.9.9.2日期：2011年2月13日*/#includetypedefcharTElemType;//树的双亲表存储表示#defineMAX_TREE_SIZE100typedefstruct{TElemTypedata;//数据域intparent;//双亲位置域}PTNode;//结点结构typedefstruct

2、{PTNodenodes[MAX_TREE_SIZE];//存储结点的数组intn;//结点数}PTree;typedefstruct{intnum;TElemTypename;}QElemType;//定义队列元素类型typedefstructQNode{QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,//队头指针，指针域指向队头元素rear;//队尾指针，指向队尾元素}LinkQueue;TElemTypeNil='';//以空格符为空intI

3、nitTree(PTree*T){//操作结果:构造空树T(*T).n=0;return1;}voidDestroyTree(){//由于PTree是定长类型,无法销毁}//构造一个空队列QintInitQueue(LinkQueue*Q){(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));//动态分配一个空间if(!(*Q).front)exit(0);(*Q).front->next=NULL;//队头指针指向空，无数据域，这样构成了一个空队列return1;}//若Q为空队列,则返回1,否则返回0intQue

4、ueEmpty(LinkQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}//插入元素e为Q的新的队尾元素intEnQueue(LinkQueue*Q,QElemTypee){QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)//存储分配失败exit(0);//生成一个以为e为数据域的队列元素p->data=e;p->next=NULL;//将该新队列元素接在队尾的后面(*Q).rear->next=p;(*Q).rear=p;return1;}//若队列不空,删除Q的队头元素,

5、用e返回其值,并返回1,否则返回0intDeQueue(LinkQueue*Q,QElemType*e){QueuePtrp;if((*Q).front==(*Q).rear)return0;p=(*Q).front->next;//队头元素*e=p->data;(*Q).front->next=p->next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);return1;}//构造树TintCreateTree(PTree*T){LinkQueueq;QElemTypep,qq;inti=1,j,l;charc[MAX_TR

6、EE_SIZE];//临时存放孩子结点数组InitQueue(&q);//初始化队列printf("请输入根结点(字符型,空格为空):");scanf("%c%*c",&(*T).nodes[0].data);//根结点序号为0,%*c吃掉回车符if((*T).nodes[0].data!=Nil)//非空树{(*T).nodes[0].parent=-1;//根结点无双亲qq.name=(*T).nodes[0].data;qq.num=0;EnQueue(&q,qq);//入队此结点while(i

7、未满且队不空{DeQueue(&q,&qq);//出队一个结点printf("请按长幼顺序输入结点%c的所有孩子:",qq.name);gets(c);l=strlen(c);for(j=0;jMAX_TREE_SIZE){printf("结点数超过数组容量");exit(0);}(*T).n=i;}else(*T