数据结构C语言版 双链树.doc
《数据结构C语言版 双链树.doc》由会员分享,可在线阅读,更多相关《数据结构C语言版 双链树.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构C语言版 双链树.txt你妈生你的时候是不是把人给扔了把胎盘养大?别把虾米不当海鲜。别把虾米不当海鲜。/*数据结构C语言版 双链树 P248编译环境:Dev-C+ 4.9.9.2日期:2011年2月15日 */#include #include / 双链树的存储结构 #define MAXKEYLEN 16 / 关键字的最大长度 #define N 16 / 数据元素个数 typedef structint ord;Others; / 记录的其它部分 #define Nil / 定义结束符为空格(与教科书不同) typedef structchar chMAXKEYLEN; / 关键字
2、 int num; / 关键字长度 KeysType; / 关键字类型 typedef structKeysType key; / 关键字 Others others; / 其它部分(由主程定义) Record; / 记录类型 typedef enumLEAF,BRANCHNodeKind; / 结点种类:叶子,分支 typedef struct DLTNode / 双链树类型 char symbol;struct DLTNode *next; / 指向兄弟结点的指针 NodeKind kind;unionRecord *infoptr; / 叶子结点的记录指针 struct DLTNode
3、*first; / 分支结点的孩子链指针 a;DLTNode,*DLTree;/ 构造一个空的双链键树DT int InitDSTable(DLTree *DT) *DT=NULL;return 1;/ 销毁双链键树DTvoid DestroyDSTable(DLTree *DT)if(*DT) / 非空树 if(*DT)-kind=BRANCH&(*DT)-a.first) / *DT是分支结点且有孩子 DestroyDSTable(&(*DT)-a.first); / 销毁孩子子树 if(*DT)-next) / 有兄弟 DestroyDSTable(&(*DT)-next); / 销毁兄
4、弟子树 free(*DT); / 释放根结点 *DT=NULL; / 空指针赋0 / 算法9.15/ 在非空双链键树T中查找关键字等于K的记录,若存在, / 则返回指向该记录的指针,否则返回空指针。Record *SearchDLTree(DLTree T,KeysType K)DLTree p;int i;if(T)p=T; / 初始化 i=0;while(p&isymbol!=K.chi) / 查找关键字的第i位 p=p-next;if(p&ia.first;+i; / 查找结束 if(!p) / 查找不成功 return NULL;else / 查找成功 return p-a.infop
5、tr;elsereturn NULL; / 树空 / 若DT中不存在其关键字等于(*r).key.ch的数据元素,则按关键字顺序插r到DT中 void InsertDSTable(DLTree *DT,Record *r)DLTree p=NULL,q,ap;int i=0;KeysType K=r-key;if(!*DT&K.num) / 空树且关键字符串非空 *DT=ap=(DLTree)malloc(sizeof(DLTNode);for(;ia.first=ap;ap-next=NULL;ap-symbol=K.chi;ap-kind=BRANCH;p=ap;ap=(DLTree)ma
6、lloc(sizeof(DLTNode);p-a.first=ap; / 插入叶子结点 ap-next=NULL;ap-symbol=Nil;ap-kind=LEAF;ap-a.infoptr=r;else / 非空树 p=*DT; / 指向根结点 while(p&isymbolnext;if(p&p-symbol=K.chi) / 找到与K.chi相符的结点 q=p;p=p-a.first; / p指向将与K.chi+1比较的结点 +i;else / 没找到,插入关键字 ap=(DLTree)malloc(sizeof(DLTNode);if(q-a.first=p)q-a.first=ap
7、; / 在长子的位置插入 else / q-next=p q-next=ap; / 在兄弟的位置插入 ap-next=p;ap-symbol=K.chi;ap-kind=BRANCH;p=ap;ap=(DLTree)malloc(sizeof(DLTNode);i+;for(;ia.first=ap;ap-next=NULL;ap-symbol=K.chi;ap-kind=BRANCH;p=ap;ap=(DLTree)malloc(sizeof(DLTNode);p-a.first=ap; / 插入叶子结点 ap-next=NULL;ap-symbol=Nil;ap-kind=LEAF;ap-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构C语言版 双链树 数据结构 语言版
限制150内