第03章 设计与实现234986.pptVIP

第3章 设计与实现 概述 1、算法--- 以Markov算法为例 2、选择数据结构 3、程序结构 4、小结 概 述 数据结构是程序设计的中心环节 eg1 单向链表 问题、数据结构、程序语言的关系 问题=处理流程=算法 数据结构=数据保存=处理的状态 语言是对数据结构的描述手段 Markov(马尔可夫)随机数据生成 算法 用途 输入的文章视为一系列互相重叠的短语，算法将根据所有短语生成一个随机性的文章 短语 = 前缀[=2个词] + 后缀[1个词] 算法原理 根据原文本的统计性质，随机选择任意前缀的某个后缀输出并调整前缀，进行迭代 输入所有词后才能开始输出 算法(续一) 算法描述---例如前缀长度为2 设置W1和W2为文本的前两个词 输出W1和W2 循环： 随机地选出W3，它是文本中W1W2的后缀之一 打印W3， 把W1和W2分别换成W2和W3 重复循环 算法(续二) 算法例子 原文 Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious. (end) 部分前缀-后缀对 Show your flowcharts tables your flowcharts and will flowcharts and conceal will be mystified. obvious. 输出的例子 Show your tables and I will be obvious. 选择数据结构 中等规模的数据量---输入词数设定 输入的保存方法 == 影响生成算法 完整的输入串+词的指针数组 =产生新词，调整前缀，检索所有词，输出匹配的某个后缀 词的位置倒排链表 =词的散列表指向词在串中的位置=扫描所有词[无关联] 前缀+后缀集合[=状态集] 输入时形成所有可能前缀并记录每个前缀的所有可能后缀 输出时对任意前缀，随机选取某个后缀输出即可 任意状态+任意后缀=链表/动态数组 前缀的关联性=散列表 选择数据结构(续一) 附加问题 短语出现多次[相同的前缀+后缀] =后缀保存多次 vs. 后缀+计数器 词本身的表示 =存储为独立字符串 vs. 词的散列表[节约存储+指针比较] 总体结构描述 程序基于一个状态表执行 每个状态由一个前缀+后缀链表组成 前缀作为关键词，保存在散列表中 每个前缀是固定大小的词集合 选择数据结构(续二) 图例 选择数据结构(续三) 总体结构C表示 常数=边界假设 enum { NPREF = 2, /* number of prefix words */ NHASH = 4093, /* size of state hash table array */ MAXGEN = 10000 /* maximum words generated */ }; 状态表 typedef struct State State; typedef struct Suffix Suffix; 选择数据结构(续四) struct State { char *pref[NPREF]; /* prefix words */ Suffix *suf; /* list of suffixes */ State *next; /* next in hash table */ }; struct Suffix { char *word; /* suffix */ Suffix *next; /* next in list of suffixes */ }; State *statetab[NHASH]; /* hash table of states */ 程序结构 顶级结构[0-1级] 程序结构(续一) 0级程序 /* markov main: markov-chain random text generation */ int main(void) { int i, nwords = MAXGEN; char *prefix[NPREF]; /* current input prefix */ long seed; seed = time(NULL); srand(seed); for (i = 0; i NPREF; i++) /* set up initial prefix */ prefix[i] = NONWORD; build(prefix, stdin); add(prefix, NONWORD); generate(nwords); retu