数据结构C语言版 双链树.doc

《数据结构C语言版 双链树.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构C语言版双链树.txt你妈生你的时候是不是把人给扔了把胎盘养大？别把虾米不当海鲜。别把虾米不当海鲜。/*数据结构C语言版双链树P248编译环境：Dev-C++4.9.9.2日期：2011年2月15日*/#include#include//双链树的存储结构#defineMAXKEYLEN16//关键字的最大长度#defineN16//数据元素个数typedefstruct{intord;}Others;//记录的其它部分#defineNil''//定义结束符为空格(与教科书不同)typedefstru

2、ct{charch[MAXKEYLEN];//关键字intnum;//关键字长度}KeysType;//关键字类型typedefstruct{KeysTypekey;//关键字Othersothers;//其它部分(由主程定义)}Record;//记录类型typedefenum{LEAF,BRANCH}NodeKind;//结点种类:{叶子,分支}typedefstructDLTNode//双链树类型{charsymbol;structDLTNode*next;//指向兄弟结点的指针NodeKindkind;union{Record*infop

3、tr;//叶子结点的记录指针structDLTNode*first;//分支结点的孩子链指针}a;}DLTNode,*DLTree;//构造一个空的双链键树DTintInitDSTable(DLTree*DT){*DT=NULL;return1;}//销毁双链键树DTvoidDestroyDSTable(DLTree*DT){if(*DT)//非空树{if((*DT)->kind==BRANCH&&(*DT)->a.first)//*DT是分支结点且有孩子DestroyDSTable(&(*DT)->a.first);//销毁孩子子树if((*

4、DT)->next)//有兄弟DestroyDSTable(&(*DT)->next);//销毁兄弟子树free(*DT);//释放根结点*DT=NULL;//空指针赋0}}//算法9.15//在非空双链键树T中查找关键字等于K的记录，若存在，//则返回指向该记录的指针，否则返回空指针。Record*SearchDLTree(DLTreeT,KeysTypeK){DLTreep;inti;if(T){p=T;//初始化i=0;while(p&&isymbol!=K.ch[i])//查找关键字的第i位p=p

5、->next;if(p&&ia.first;++i;}//查找结束if(!p)//查找不成功returnNULL;else//查找成功returnp->a.infoptr;}elsereturnNULL;//树空}//若DT中不存在其关键字等于(*r).key.ch的数据元素,则按关键字顺序插r到DT中voidInsertDSTable(DLTree*DT,Record*r){DLTreep=NULL,q,ap;inti=0;KeysTypeK=r->key;if(!*DT&&K.num)//空树且关键

6、字符串非空{*DT=ap=(DLTree)malloc(sizeof(DLTNode));for(;ia.first=ap;ap->next=NULL;ap->symbol=K.ch[i];ap->kind=BRANCH;p=ap;ap=(DLTree)malloc(sizeof(DLTNode));}p->a.first=ap;//插入叶子结点ap->next=NULL;ap->symbol=Nil;ap->kind=LEAF;ap->a.infoptr=r;}else//非空树{p=*

7、DT;//指向根结点while(p&&isymbolnext;}if(p&&p->symbol==K.ch[i])//找到与K.ch[i]相符的结点{q=p;p=p->a.first;//p指向将与K.ch[i+1]比较的结点++i;}else//没找到,插入关键字{ap=(DLTree)malloc(sizeof(DLTNode));if(q->a.first==p)q->a.first=ap;//在长子的位置插入else//q->next==pq

8、->next=ap;//在兄弟的位置插入ap->next=p;ap->symbol=K.ch[i];ap->kind=BRANCH;p=ap;ap=(