哈尔滨工业大学课程设计报告.doc

Harbin Institute of Technology课程设计报告课程名称： 数据结构与算法课程设计设计题目： 一个基于XML的网站生成器 院 系： 计算机科学与技术学院 班 级： * 设 计 者： * * 学 号： * * * * * * * * * * 指导教师： 王 春 宇 设计时间： 2008年9月1日 哈尔滨工业大学哈尔滨工业大学课程设计任务书 姓 名： * 院 （系）： 计算机科学与技术 专 业： 计算机科学与技术 班 号： * 任务起至日期： 2008年8月25日2008年9月7日 课程设计题目： 一个基于XML 的网站生成器 课程设计要求：1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力,并且增加学习新知识的能力,并将其运用具体软件开发当中；2初步掌握基于XML 的网站生成器开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3提高综合运用所学的理论知识和方法独立分析和解决问题的能力和应用能力；4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风,提高动手思考能力。设计任务总述：分析一个XML 文件，并根据分析结果自动生成一个完整的新闻网站。理解栈结构，并能栈结构解决复杂的实际问题。XML 文件形如：Naked Students Seen on Rice CampusDonna B. CeriusMetro23 Sep 1999结果网站中每个article 对应一个网页。结果网站中的主页中有通向各个article 页面的链接。主页中的链接需依据XML 中article 的section 进行分类。网站页面的样式自行设计。工作计划及安排：第1、2 天问题分析和任务定义。根据设计题目的要求，设计一个基于XML 的网站生成器, 了解有关XML 和HTML 的知识和题目背景操作对象和生成结果,深刻理解题目内涵,明确任务方向.充分地分析和理解问题，并查阅相关资料填写任务书.第3、4 天逻辑设计。对基于XML 的网站生成器描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。第5、6 天物理设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。第7、8 天程序编码。把详细设计的结果进一步求精为C 程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚,简单易懂。第9、10 天程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它,最后形成一个HTML 文件,即输出一个与XML 相符的网站。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。第11、12 天结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。分析算法的时间、空间复杂性。并分析系统不足尽量优化系统,进一步完善.第13、14 天制作ppt 和填写课程设计报告,总结设计过程。指导教师签字_ 年 月 日 数据结构与算法课程设计中期检查结果学号：*姓名：* *指导老师：王春宇课程设计题目：一个基于XML 的网站生成器系统总任务描述：设计内容：分析一个XML 文件，并根据分析结果自动生成一个完整的新闻网站。理解栈结构，并能栈结构解决复杂的实际问题。XML 文件形如：Naked Students Seen on Rice CampusDonna B. CeriusMetro23 Sep 1999结果网站中每个article 对应一个网页。结果网站中的主页中有通向各个article 页面的链接。主页中的链接需依据XML 中article 的section 进行分类。网站页面的样式自行设计。需参阅关于XML 和HTML 的基本介绍。已完成工作描述：学习了有关XML 和HTML 的有关知识,了解了制作网页的基本过程,并且完成了程序逻辑设计和物理设计，对程序涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法。定义相应的存储结构并写出各函数的伪码算法，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。具体定义设计如下：1、抽象数据类型的定义typedef struct S_Node / 定义链表节点元素 char ch; struct S_Node * next;S_Node, * Stack; / 定义链表2、函数定义void MakeNull (Stack S) / 清空栈 S - next = NULL;void Push (char c, Stack S) / 压栈 Stack temp = new S_Node; temp - ch = c; temp - next = S - next; S - next = temp;void Pop (Stack S, char * c) / 出栈并付给*c栈顶数字 Stack temp; if (S - next != NULL) * c = S - next - ch; temp = S - next; S - next = temp - next; delete temp; int Judgement (ifstream & fin) / 判断标签 char ch = ) / 将标签压栈 fin.get (ch); Push (ch, S); for (int k = 0; S - next != NULL; k+) Pop (S, &tempk); / 将标签弹出栈 for (int count = 0; count 15; count+) if (strcmp (temp, Labelcount) = 0) return count; / 进行比较,返回其值,值为其在数组中的位置 return 15;int Sort (ofstream & fout, int n) / 对article文档进行分类 int k = 0; fout section0 endl; for (int i = 0; sectionki != 0; i+) section_trueki = sectionki; k+;for (int l = 0; l n; l+) / 将含有重复section的数组简化为非重复的,并存入另一个数组中 int b; for ( b = 0; b k; b+) if (strcmp (sectionl, section_trueb) continue; else break; if (b = k) fout sectionl endl; for (int i = 0; sectionli != 0; i+) section_trueki = sectionli; k+; return k;void Create (ifstream & fin, ofstream & fout1, int k) / 对各个article建立子页面 int n, m = 0; char ch; char titleLEN = 0; char headlineLEN = 0; char authorLEN = 0; char sectionLEN = 0; char dateLEN = 0; for (fin.get (ch); ch != ; fin.get (ch) continue; n =Judgement (fin); if (n = 2) do / 对读入标签进行比较 for (fin.get (ch); ch != ; fin.get (ch) continue; n = Judgement (fin); if (n = 3) / 存入title临时数组和headline临时数组,由于title临时数组要加后缀html,故需要两个临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) titlem = ch; headlinem = ch; else if (n = 5) / 存入author临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) authorm = ch; else if (n = 7) / 存入section临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) sectionm = ch; else if (n = 9) / 存入date临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) datem = ch; else if (n != 11) exit (1); / 表明遇上了body,将进行文件内容的copy else break; m = 0; while (n != 11); ofstream fout; strcat (title, .html); / 用于建立子页面 for (m = 0; m k; m+) if (!(strcmp (section, section_truem) markq = m; break; fout1 endl q A HREF= title headline n endl; / 保存建立超级连接的语句 q+; fout.open (title, ios_base:out | ios_base:trunc); / 判断是否打开成功 if (!fout.is_open () cerr Could not create the file. endl; exit (1); fout nn title nn; fout ; fout nn headline n author n; fout date n ; for (fin.get (ch); ch != ; fin.get (ch) continue; n = Judgement (fin); if (n = 12) for (fin.get (ch); ch != ; fin.get (ch) fout ch; fout nnn; else exit (1); else exit (1);void Web (ofstream & fout1, int k) / 建立主页面,并对各个子页面建立超级连接 char ch; fout1 nn2008 Olympic Gamesnn; fout1 n; fout1 n2008 Olympic Gamesn; for (int i = 0; i k; i+) fout1 section_truei n; ifstream fin; fin.open (link.html, ios_base:in); / 创造链接文件 if (!fin.is_open () cerr Could not open file. n; if (markn = i) do fin.get(ch); if (ch !=n) fout1 ch; while (ch != n); fout1 n; while (fin.good (); / 判断是否读到EOF fout1 nnnnnnn;fout1 2008 - 9 - 01n; fout1 nn;3、各函数之间的调用关系主函数判断标签模块建立分页面模块建立主页面模块建立可执行文件下一步工作计划及安排：1、编制代码，进行详细设计。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。并对程序进行调试,逐步完善，改进算法，降低时间和空间复杂度，达到程序的最优效果。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。2、优化网站结构，使之达到美观成熟实用的效果，尽量向专业网站的水平靠拢。3、写实验报告和制作ppt，准备终期答辩。填表时间：2008年8月31日指导教师签字：一、 题目分析XML代表Extensible Markup Language（eXtensible Markup Language的缩写，意为可扩展的标记语言）。XML是一套定义语义标记的规则，这些标记将文档分成许多部件并对这些部件加以标识。它也是元标记语言，即定义了用于定义其他与特定领域有关的、语义的、结构化的标记语言的句法语言。基于XML的网站生成器是将一个形如题目中XML文件生成一个网站。HTML英文名字是HyperText MarkupLanguage的缩写，中文名为超文本标记语言。所谓超文本标记语言，就是该类文档中提供的超级链接能够让浏览者在不同的页面之间进行跳转。标记语言是基于源代码解释的访问方式，它的原文件由一个纯文本文件组成，代码中由许多元素组成，而前台浏览器通过解释这些元素显示各种样式的文档。浏览器通读HTML文档，处理遇到的文本标签，将相关的内容显示在网页上。综上了解，题目要求根据一个已知XML文件自动生成一个新闻网站，即要建立新的HTML文件，并且根据XML文件中的各种标记来满足题目要求，在自动生成的新闻网站中，每个article在主页中都要有链接，并且根据article所属的section都文章进行分类。二、 总体设计基于上述分析，网站生成器程序是通过分析一个XML 文件建立多个HTML 文件，即网页。因此程序设计主要是对文件进行的操作。要完成这个设计必须实现文件、字符串的操作和栈的应用。应用栈解决实际复杂的特殊问题。栈是一种特殊的线性表，所有的插入删除操作都只在栈的一端进行。因此利用栈的这种特殊性质实现本试验的部分操作。这个设计最关键的部分即运用栈进行括号匹配的检验实现判断XML 文件中的各种标签。判断出相应标签即可进行相应的操作。因此标签读取及识别是整个设计的基础。因此这个设计主要有以下几个模块组成：主程序模块、判断标签模块、建立链接并制作链接网页模块、制作网站首页并将文章分类模块。三、 数据结构设计根据这一网站生成器的原理，需要的管理数据主要有：存放标签的链表，临时存放文章名、作者、日期以及所属分类的多个一维和二维数组， 下面就给出每种数据的详细分析。（一）在括号匹配的算法中设置一个栈，每读入一个括号，若是左括号或除右括号外的其他字符则直接存入堆栈，若是右括号则弹出堆栈中所有元素。抽象数据类型栈的形式定义：ADT Stack数据对象：D=Ai | Ai 属于ElenmSet, i=1,2,.,n数据关系：Rl= | Ai-1,Ai 属于D, i=2,.,n约定An 为堆栈顶，An 为堆栈底ADT typedef struct S_Node / 定义链表节点元素 char ch; /堆栈节点类型为字符型 struct S_Node * next; /下一个节点的指针S_Node, * Stack; / 定义链表（二）在存储文件的某些信息时需要用到多个一维数组和二维数组。抽象数据类型数组可形式的定义如下：ADT Array数据对象：Ji=0,.,Bi-1, i=0,1,2,.,n数据关系：R=R1,R2,.,Rn;ADT Array抽象数据类型数组的具体定义如下：char sectionLENLEN = 0; / 存储section分类的临时数组,含重复项char section_trueLENLEN = 0; / 存储section分类的数组,无含重复项四、 算法设计编译并创建出可执行文件调运Judgement函数判断标签生成主页面,并创建对各个子页面的链接查找所有的section,并将其分类,剔除重复项调用article函数,进行子页面的创建再次调用Judgement函数,找出article标签五、 物理实现及结果从上述流程图可以看出基本算法主要包括标签判定、文章分类，建立网站首页和建立链接页面四个流程。下面我们依次进行分析：1. 主要数据结构的物理设计1.XML文件标签的判定这一部分用到了栈的抽象数据类型，也是整个程序设计的基础。其基本思想就是如果读到的字符是时弹出堆栈中的全部内容，即是读入标签的倒置，可以判断并根据定义将标签序号返回主函数了。这个模块的伪码实现如下：int Judgement (ifstream & fin) / 判断标签建立栈;初始化栈;先将停止压栈）从文件顺次读出字符;将读入字符压栈；将标签弹出栈并存放到一个数组中；判断是那个标签并返回到主函数If (调用Strcmp（）比较函数，数组中内容依次与各个标签进行比较是否相同)则待判断标签即为此时比较的标签；将相应标签值返回主函数；2.文章分类的实现这一部分也许要用到Strcmp（）比较函数。现将所有的分类列出，再根据每篇文章的类别将所有的文章分类，其具体实现函数的伪码如下：void Sort(ofstream & fout, int n)/ 对article文档进行分类从XML 文件开始处一次找出每个article 的section；将第一篇article 的section 存入二维数组section_true；调用Strcmp（）比较函数，依次读取临时section中的字符串；判断其是否与section_true中元素相同；相同则跳过比较下一个article 的section；不同则将其写入section_true数组；将所有section 标题写入文件中；3.建立链接页面的实现在这部分的实现中，将重新从XML 文件的起始处读起，遇到标签则进行对每一个article 的单独处理。具体实现过程的伪码如下所示：void Create (ifstream & fin, ofstream & fout1, int k) / 对各个article建立子页面建立title,headline,author,section,date等临时二维数组；从文件中读取字符，若遇到则调用标签判断函数；若遇到标签把这篇文章的题目放入临时数组titles；遇到标签author把这篇文章的作者放入临时数组author 中；遇到标签把这篇文章的section 放入临时数组group 中；遇到标签将文章日期放入data临时数组中；遇到标签跳出循环,准备进行子页面的创建；保存建立超级连接的语句；建立并打开新.html 文件即链接网页;按照html 格式写入头信息网页标题;写入文章标题，即将titles 数组中内容写入；写入作者及日期；写入正文；关闭文件；4.建立网站首页的实现此过程序调用web 的函数，根据已写好的一个为将文章分类的文件对文章进行分类并产生网站首页，其具体伪码实现过程如下：void Web(ofstream & fout1, int k)向新建的web.html 文件写入html 头信息；写入第一个section；在已有文件根据文章标记判断所属的section 判断是否属于第一个section；若是，则复制标题的连接至web.html 中；不是则跳过此article 查找判断下一个；循环此过程一次判断并打印所有的section 及article；2. 核心算法的物理实现(1).XML文件标签判定的具体函数实现int Judgement (ifstream & fin) / 判断标签 char ch = ) / 将标签压栈 fin.get (ch); Push (ch, S); for (int k = 0; S - next != NULL; k+) Pop (S, &tempk); / 将标签弹出栈 for (int count = 0; count 15; count+) if (strcmp (temp, Labelcount) = 0) return count; / 进行比较,返回其值,值为其在数组中的位置 return 15;(2).文章分类的具体函数实现int Sort (ofstream & fout, int n) / 对article文档进行分类 int k = 0; fout section0 endl; for (int i = 0; sectionki != 0; i+) section_trueki = sectionki; k+;for (int l = 0; l n; l+) / 将含有重复section的数组简化为非重复的,并存入另一个数组中 int b; for ( b = 0; b k; b+) if (strcmp (sectionl, section_trueb) continue; else break; if (b = k) fout sectionl endl; for (int i = 0; sectionli != 0; i+) section_trueki = sectionli; k+; return k;(3).建立链接页面的具体函数实现void Create (ifstream & fin, ofstream & fout1, int k) / 对各个article建立子页面 int n, m = 0; char ch; char titleLEN = 0; char headlineLEN = 0; char authorLEN = 0; char sectionLEN = 0; char dateLEN = 0; for (fin.get (ch); ch != ; fin.get (ch) continue; n =Judgement (fin); if (n = 2) do / 对读入标签进行比较 for (fin.get (ch); ch != ; fin.get (ch) continue; n = Judgement (fin); if (n = 3) / 存入title临时数组和headline临时数组,由于title临时数组要加后缀html,故需要两个临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) titlem = ch; headlinem = ch; else if (n = 5) / 存入author临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) authorm = ch; else if (n = 7) / 存入section临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) sectionm = ch; else if (n = 9) / 存入date临时数组 for (fin.get(ch); ch != ; fin.get (ch), m+) datem = ch; else if (n != 11) exit (1); / 表明遇上了body,将进行文件内容的copy else break; m = 0; while (n != 11); ofstream fout; strcat (title, .html); / 用于建立子页面 for (m = 0; m k; m+) if (!(strcmp (section, section_truem) markq = m; break; fout1 endl q A HREF= title headline n endl; / 保存建立超级连接的语句 q+; fout.open (title, ios_base:out | ios_base:trunc); / 判断是否打开成功 if (!fout.is_open () cerr Could not create the file. endl; exit (1); fout nn title nn; fout ; fout nn headline n author n; fout date n ; for (fin.get (ch); ch != ; fin.get (ch) continue; n = Judgement (fin); if (n = 12) for (fin.get