H a r b i n I n s t i t u t e o f T e c h n o l o g y课程设计报告课程名称：数据结构与算法课程设计设计题目：一个基于XML的网站生成器院系：计算机科学与技术学院班级：*******设计者：* *学号：* * * * * * * * * *指导教师：王春宇设计时间：2008年9月1日哈尔滨工业大学哈尔滨工业大学课程设计任务书一、题目分析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> | 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 section[LEN][LEN] = {'\0'}; // 存储section分类的临时数组,含重复项char section_true[LEN][LEN] = {'\0'}; // 存储section分类的数组,无含重复项四、算法设计五、物理实现及结果从上述流程图可以看出基本算法主要包括标签判定、文章分类，建立网站首页和建立链接页面四个流程。
下面我们依次进行分析：1. 主要数据结构的物理设计1.XML文件标签的判定这一部分用到了栈的抽象数据类型，也是整个程序设计的基础。
其基本思想就是如果读到的字符是'<'则压入堆栈，直到读到'>'时弹出堆栈中的全部内容，即是读入标签的倒置，可以判断并根据定义将标签序号返回主函数了。
这个模块的伪码实现如下：int Judgement (ifstream & fin)// 判断标签{建立栈;初始化栈;先将'<'压入栈；while（直至遇到'>'停止压栈）{从文件顺次读出字符;将读入字符压栈；}将标签弹出栈并存放到一个数组中；判断是那个标签并返回到主函数{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>标签则进行对每一个article 的单独处理。
具体实现过程的伪码如下所示：void Create (ifstream & fin, ofstream & fout1, int k)// 对各个article建立子页面建立title,headline,author,section,date等临时二维数组；从文件中读取字符，若遇到'<'则调用标签判断函数；若遇到标签<title>把这篇文章的题目放入临时数组titles；遇到标签author把这篇文章的作者放入临时数组author 中；遇到标签<section>把这篇文章的section 放入临时数组group 中；遇到标签<date>将文章日期放入data临时数组中；遇到标签<body>跳出循环,准备进行子页面的创建；保存建立超级连接的语句；建立并打开新.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 = '<';char temp[LEN] = {'\0'};Stack S = new S_Node;MakeNull (S);Push (ch, S);while (ch != '>') // 将标签压栈{fin.get (ch);Push (ch, S);}for (int k = 0; S -> next != NULL; k++) Pop (S, &temp[k]);// 将标签弹出栈for (int count = 0; count < 15; count++)if (strcmp (temp, Label[count]) == 0) return count;// 进行比较,返回其值,值为其在数组中的位置return 15;}(2).文章分类的具体函数实现int Sort (ofstream & fout, int n) // 对article文档进行分类{int k = 0;fout << "<H2>" << section[0] << "</H2>" << endl;for (int i = 0; section[k][i] != '\0'; i++) section_true[k][i] = section[k][i]; k++;for (int l = 0; l < n; l++)// 将含有重复section的数组简化为非重复的,并存入另一个数组中{int b;for ( b = 0; b < k; b++){if (strcmp (section[l], section_true[b]))continue;else break;}if (b == k){fout << "<H2>" << section[l] << "</H2>" << endl;for (int i = 0; section[l][i] != '\0'; i++)section_true[k][i] = section[l][i];k++;}}return k;}(3).建立链接页面的具体函数实现void Create (ifstream & fin, ofstream & fout1, int k) // 对各个article建立子页面{int n, m = 0;char ch;char title[LEN] = {'\0'};char headline[LEN] = {'\0'};char author[LEN] = {'\0'};char section[LEN] = {'\0'};char date[LEN] = {'\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++){title[m] = ch;headline[m] = ch;}}else if (n == 5) // 存入author临时数组{for (fin.get(ch); ch != '<'; fin.get (ch), m++)author[m] = ch;}else if (n == 7) // 存入section临时数组{for (fin.get(ch); ch != '<'; fin.get (ch), m++)section[m] = ch;}else if (n == 9) // 存入date临时数组{for (fin.get(ch); ch != '<'; fin.get (ch), m++)date[m] = ch;}else{if (n != 11) exit (1); // 表明遇上了body,将进行文件内容的copyelse break;}m = 0;}while (n != 11);ofstream fout;strcat (title, ".html"); // 用于建立子页面for (m = 0; m < k; m++)if (!(strcmp (section, section_true[m]))){mark[q] = m;break;}fout1 << endl << "@" << q << " <A HREF=\"" << title << "\">" << headline << "</A><BR>\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 << "<html>\n<head>\n<title>" << title << "</title>\n</head>\n";fout << "<body background = \"Olympic.jpg\";>";fout << "<center>\n<H2>\n" << headline << "</H2>\n<H3>"<< author << "</H3>\n";fout << "<H5>" << date << "</H5>\n" << "<main>";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 << "</main>\n</body>\n</html>\n";}else exit (1);}else exit (1);}(4).建立网站首页的具体函数实现void Web (ofstream & fout1, int k)// 建立主页面,并对各个子页面建立超级连接{char ch;fout1 << "<html>\n<head>\n<title>2008 Olympic Games</title>\n</head>\n"; fout1 << "<body background = \"Olympic.jpg\";>\n";fout1 << "<center>\n<H1>2008 Olympic Games</H1>\n";for (int i = 0; i < k; i++){fout1 << "<H2>" << section_true[i] << "</H2>\n";ifstream fin;fin.open ("link.html", ios_base::in); // 创造链接文件if (!fin.is_open ()){cerr << "Could not open file." << endl;exit (1);}do{fin.get (ch);if (ch == '@'){int n;fin >> n;if (mark[n] == i){do{fin.get(ch);if (ch !='\n')fout1 << ch;}while (ch != '\n');fout1 << '\n';}}}while (fin.good ()); // 判断是否读到EOF}fout1 << "<br>\n<br>\n<br>\n<br>\n<br>\n<br>\n<br>\n";fout1 << "<H5>2008 - 9 - 01</H5>\n";fout1 << "\n</body>\n</html>";}3. 实现结果程序执行后在同一根目录下自动生成了一个网站，打开文件名为web.html 的文件即为网站首页，点击其中的文章标题即可进入链接页面，点击后退则返回网站首页．网站首页中的文章都已根据XML 文件中的section 分好类了．其执行结果如下：网站首页其中的一个链接页面六、结果分析从生成的网站来看，本次课程设计完成了由一个XML 文件自动生成一个新闻网站的功能．从网页上可以清楚的根据分类查找到需要的文章，并可点击文章查看详细内容，由于XML文件本身的复杂性和多功能性,程序只能对指定标签的XML文件进行操作，不能实现对复杂功能的识别．七、结论在本次实验中对网页的知识包括XML 和HTML 有了初步的了解及简单的掌握．通过这次实验加强对栈数据类型的应用能里，能运用栈的知识来解决实际复杂的问题，加强了对文件和字符串操作的能力．提高了自学和动手编程能力，为今后学习网站相关内容打下了基础．八、附录开发语言及编程环境:开发语言: C++编译环境: MinGW集成开发环境: Codeblocks九、参考文献1．廖明宏, 郭福顺,张岩，李秀坤,《数据结构与算法》,高等教育出版社。