设计与实现PPT课件

1 第3章设计与实现 概述1 算法 以Markov算法为例2 选择数据结构3 程序结构4 小结 2 概述 数据结构是程序设计的中心环节eg1单向链表问题 数据结构 程序语言的关系问题 处理流程 算法数据结构 数据保存 处理的状态语言是对数据结构的描述手段Markov 马尔可夫 随机数据生成 3 算法 用途输入的文章视为一系列互相重叠的短语 算法将根据所有短语生成一个随机性的文章短语 前缀 2个词 后缀 1个词 算法原理根据原文本的统计性质 随机选择任意前缀的某个后缀输出并调整前缀 进行迭代输入所有词后才能开始输出 4 算法 续一 算法描述 例如前缀长度为2设置W1和W2为文本的前两个词输出W1和W2循环 随机地选出W3 它是文本中W1W2的后缀之一打印W3 把W1和W2分别换成W2和W3重复循环 5 算法 续二 算法例子原文ShowyourflowchartsandconcealyourtablesandIwillbemystified Showyourtablesandyourflowchartswillbeobvious end 部分前缀 后缀对Showyourflowchartstablesyourflowchartsandwillflowchartsandconceal willbemystified obvious 输出的例子ShowyourtablesandIwillbeobvious 6 选择数据结构 前提 中等规模的数据量 输入词数设定输入的保存方法 影响生成算法完整的输入串 词的指针数组 产生新词 调整前缀 检索所有词 输出匹配的某个后缀词的位置倒排散列表指向词在串中链表 词的的位置 扫描所有词 无关联 前缀 后缀集合 状态集 输入时形成所有可能前缀并记录每个前缀的所有可能后缀输出时对任意前缀 随机选取某个后缀输出即可任意状态 任意后缀 链表 动态数组前缀的关联性 散列表 7 选择数据结构 续一 附加问题短语出现多次 相同的前缀 后缀 后缀保存多次vs 后缀 计数器词本身的表示 存储为独立字符串vs 词的散列表 节约存储 指针比较 总体结构描述程序基于一个状态表执行每个状态由一个前缀 后缀链表组成前缀作为关键词 保存在散列表中每个前缀是固定大小的词集合 8 选择数据结构 续二 图例 NULL NULL NULL statetab NHASH pref 0 suf pref 1 Show word you pref 0 suf pref 1 一个State next next next flowcharts word next tables 另一个State 9 选择数据结构 续三 总体结构C表示常数 边界假设enum NPREF 2 numberofprefixwords NHASH 4093 sizeofstatehashtablearray MAXGEN 10000 maximumwordsgenerated 状态表typedefstructStateState typedefstructSuffixSuffix 10 选择数据结构 续四 structState char pref NPREF prefixwords Suffix suf listofsuffixes State next nextinhashtable structSuffix char word suffix Suffix next nextinlistofsuffixes State statetab NHASH hashtableofstates 11 程序结构 顶级结构 0 1级 Markov造词 建立状态表build prefix stdin Level1 设定结束状态add prefix NONWORD 生成输出generate nwords 说明初始前缀设定 使用一个虚前缀 类似头结点 NONWORD数组NONWORD不会作为常规词 charNONWORD n Level0 12 程序结构 续一 0级程序 markovmain markov chainrandomtextgeneration intmain void inti nwords MAXGEN char prefix NPREF currentinputprefix longseed seed time NULL srand seed for i 0 i NPREF i setupinitialprefix prefix i NONWORD build prefix stdin add prefix NONWORD generate nwords return0 13 程序结构 续二 1级程序 build readinput buildprefixtable voidbuild char prefix NPREF FILE f charbuf 100 fmt 10 createaformatstring scouldoverflowbuf sprintf fmt ds sizeof buf 1 while fscanf f fmt buf EOF add prefix estrdup buf sprintf的用法 动态形成格式串 14 程序结构 续三 add addwordtosuffixlist updateprefix voidadd char prefix NPREF char suffix State sp sp lookup prefix 1 createifnotfound 参数1表示是否创建 addsuffix sp suffix movethewordsdowntheprefix memmove prefix prefix 1 NPREF 1 sizeof prefix 0 prefix NPREF 1 suffix 2级程序 lookup addsuffix memmove 调整新的前缀 为了下一步可以依次使用prefix数组操作输入的前缀 15 程序结构 续四 generate produceoutput onewordperline voidgenerate intnwords State sp Suffix suf char prefix NPREF w inti nmatch for i 0 i NPREF i resetinitialprefix prefix i NONWORD for i 0 i nwords i sp lookup prefix 0 16 程序结构 续五 if sp NULL eprintf internalerror lookupfailed exit 1 thennmatch 0 for suf sp suf suf NULL suf suf next if rand nmatch 0 prob 1 nmatch w suf word if nmatch 0 eprintf internalerror nosuffix d s i prefix 0 if strcmp w NONWORD 0 break printf s n w memmove prefix prefix 1 NPREF 1 sizeof prefix 0 prefix NPREF 1 w 17 程序结构 续六 2级程序 lookup searchforprefix createifrequested returnspointerifpresentorcreated NULLifnot creationdoesn tstrdupsostringsmustn tchangelater State lookup char prefix NPREF intcreate inti h State sp h hash prefix for sp statetab h sp NULL sp sp next for i 0 ipref i 0 break 18 程序结构 续七 if i NPREF foundit returnsp if create sp State emalloc sizeof State for i 0 ipref i prefix i sp suf NULL sp next statetab h statetab h sp returnsp 3级程序 hash emalloc 19 程序结构 续八 addsuffix addtostate suffixmustnotchangelater voidaddsuffix State sp char suffix Suffix suf suf Suffix emalloc sizeof Suffix suf word suffix suf next sp suf sp suf suf 20 程序结构 续九 3级程序constintMULTIPLIER 31 forhash hash computehashvalueforarrayofNPREFstrings unsignedinthash char s NPREF unsignedinth unsignedchar p inti h 0 for i 0 i NPREF i for p unsig