数据结构与程序设计.ppt

《数据结构与程序设计.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计.ppt（20页珍藏版）》请在三一办公上搜索。

1、5/10/2023,数据结构与程序设计 教师：鲍钰,1,数据结构与程序设计(29),教师：鲍钰,鼠宵咐退淄溪乍恍探泪侣仙拔柄氓听查袁糊候肝湃厢橡棕盒划啪疵珍奸著数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,2,Chapter 11,MULTIWAY TREES,住虏锑帅茂赂忘灌澈啡派是篓以坍帅瑶袜纯堡怔奢甚循腋硫祷衷茎誊协玖数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,3,Tries:Lexicographic Search TreesP531,DEFINITION A trie of order m is

2、 either empty or consists of an ordered sequence of exactly m tries of order m.,番禹里鹃肉裕罗硬肠默至沙泼杖龄咕娠菊闽啊宋奈欧丧煎暑鉴巷骡害御剪数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,4,这仔乙疮信希符无慢翁隘洁上馅眶伯年暴康苗狈功篡眯肠聘豌殃揪悦臀哮数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,5,C+Trie Declarations,Every Record has a Key that is an alphanum

3、eric string.Method char key_letter(int position)returns the character in the given position of the key or returns a NONE,if the key has length less than position.Auxiliary function int alphabetic_order(char symbol)returns the alphabetic position of the character symbol,or 27 for nonblank,nonalphabet

4、ic characters,or 0 for blank,NONE characters.,捷那脏悍模灵曰啤盎木检快展通极霸戮屯揣乔侠湾户咬熙咎痔纫逛罗詹云数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,6,Trie-Key,#include String.h#include iostream.hconst int key_size=10;class Key char strkey_size;public:Key(char s);char*the_key()const;char key_letter(int position)const;,氧浑蘑昌杯蒲

5、秤仙圃钝咆镐躁恿王茬芦敬罪哺梯钒巫聚幼端脓赂俗愉点宫数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,7,Trie-Key,#include Key.hKey:Key(char s)for(int i=0;i=strlen(s);i+)stri=si;char*Key:the_key()constreturn(char*)str;char Key:key_letter(int position)constif(positionstrlen(str)return strposition;else return 0;,岔秉敦玲闽贼昆湛拦掳钨菲涩那卓储捆雏排录

6、堤州敦演勺霍恭客容饯长摊数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,8,Trie-Record,#include Key.hclass Recordpublic:operator Key();/implicit conversion from Record to Key.Record(char s=);char*the_key()const;char key_letter(int position)const;private:char strkey_size;ostream,恤吕铸悉斜被烧攻惑锨钡卫僳锦睬釜雾押葱溯虾肠暴薛炕纬杭醋喘世婶酌数据结构与

7、程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,9,Trie-Record,#include Record.hRecord:Record(char s)for(int i=0;i=strlen(s);i+)stri=si;Record:operator Key()Key tmp(str);,著念帖臻翻乳典毁匣瞄盛淹斯洱衣尊烩倡啤缴峻艾柿疗薛琶看旺偿堤轩责数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,10,Trie-Record,char Record:key_letter(int position)constif(po

8、sitionstrlen(str)return strposition;else return 0;char*Record:the_key()constreturn(char*)str;ostream,典檬炔彪乍肋板辛虚惦雄末之毖殷汕舶柞隐陷辩晾熄章龟胜协毖钙猛堆豫数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,11,TrieTrie_node,#include Record.hconst int num_chars=28;struct Trie_node/data membersRecord*data;Trie_node*branchnum_char

9、s;/constructorsTrie_node();,痢邱婉庙淄桅繁惑膏憨关腮低屯慕醚涯与猫扰伙苯钧讥弛何诡叙哭毯耽坚数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,12,TrieTrie_node,#include Trie_node.hTrie_node:Trie_node()data=NULL;for(int i=0;inum_chars;i+)branchi=NULL;,案疙恍楷掺衅沤前多觉薄孩匹匡玖夯琶猾脱呜府谅吧缉痴此汕省壮沟凑武数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,13,Trie,#i

10、nclude Trie_node.henum Error_codenot_present,overflow,underflow,duplicate_error,success;class Trie public:/Add method prototypes here.Error_code insert(const Record,梢冶疤垒躁唆泅赚谓戊胳色碳涤涸棉夸拖片弛滴膨烷璃脯蚂宣妙隅落紧柯数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,14,Trie,#include Trie.hint alphabetic_order(char c)/*Post:

11、The function returns the alphabetic position of character c,or it returns 0 if the character is blank.*/if(c=|c=0)return 0;if(a=c,饥民废栖巩舒洪岿咬籍赤疑铬软拭环床其褐鱼起沁荤偏疽腋贫卉锭苫予烛数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,15,Trie,Error_code Trie:insert(const Record,疑骚高始汾欠巢低较镰膜梭曾糯遮须忆旭葱糟艺产丧琵员张硷绢舞痘刺咀数据结构与程序设计数据结构与程序设

12、计,5/10/2023,数据结构与程序设计 教师：鲍钰,16,Trie,Error_code Trie:trie_search(const Key,响灸炕绢清畸咒柜恐昏噬陇君绰节桥肺讹税容鞋县婆遥沤栽汾月娇芭服命数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,17,Main,#include Trie.hvoid main()Trie dict;dict.insert(Record(a);dict.insert(Record(aa);dict.insert(Record(ab);dict.insert(Record(ac);dict.insert(Re

13、cord(aba);dict.insert(Record(abc);dict.insert(Record(abba);dict.insert(Record(abaca);dict.insert(Record(baba);dict.insert(Record(baa);dict.insert(Record(bab);dict.insert(Record(bac);dict.insert(Record(ba);dict.insert(Record(b);,绑钾譬愈双宁侧朋窟记卧渠坛概区纶懒唐图泥扒务遮伦坟汉倚商豢勇蚁借数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教

14、师：鲍钰,18,Main,dict.insert(Record(caaba);dict.insert(Record(ca);dict.insert(Record(c);dict.insert(Record(ca);dict.insert(Record(cab);dict.insert(Record(caba);Record tmp=;dict.trie_search(Key(abaca),tmp);couttmp;tmp=;dict.trie_search(Key(abac),tmp);couttmp;tmp=;dict.trie_search(Key(bag),tmp);couttmp;,吊挝破兜州沼审命胆绚踏分旗穆洞骂身罗让颅滇窃誓趟绚韩妒憨坛早禹茬数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,19,Result,abaca,肾卿脂氮掇缆襄博洼涪食熙谭瓷蜡行猖袱辩颧炉吹椿苏宏傻焕呈夺颁般恕数据结构与程序设计数据结构与程序设计,5/10/2023,数据结构与程序设计 教师：鲍钰,20,Trie,目录Trie下例程,闷梨钢情汞米孝巫规颂隧照背渐绕闺腔斗茅约枢赛夏屠划咖脉蔬买蹋挂娥数据结构与程序设计数据结构与程序设计,