下载文档原格式
数据结构 树的课程设计一、课程目标知识目标：1. 理解树的基本概念，掌握树的定义、基本术语及其应用；2. 学会运用二叉树的特点和性质，掌握二叉树的遍历方法；3. 掌握常见树结构（如二叉树、二叉搜索树、平衡树、堆等）的特点及操作。
技能目标：1. 能够运用所学知识，构建并操作树结构，解决实际问题；2. 能够编写程序实现二叉树的遍历算法，如前序、中序、后序遍历；3. 能够分析树的算法复杂度，评估不同树结构在实际应用中的性能。
情感态度价值观目标：1. 培养学生对数据结构的兴趣，激发学习热情，增强自主学习能力；2. 培养学生的团队合作意识，提高沟通能力，培养良好的编程习惯；3. 引导学生关注树结构在现实生活中的应用，认识到数据结构的价值。
本课程针对高中年级学生，结合《数据结构》教材，充分考虑学生的认知水平、学习兴趣和实际需求，制定明确的课程目标。
通过本课程的学习，使学生能够掌握树的基本概念和操作方法，培养解决实际问题的能力，提高编程技能，并形成积极的学习态度和价值观。
为实现课程目标，教学过程中将注重理论与实践相结合，鼓励学生动手实践，培养创新精神和团队合作能力。
后续教学设计和评估将依据本课程目标，分解为具体的学习成果，以确保教学效果。
二、教学内容1. 树的基本概念：树的定义、基本术语（根节点、叶子节点、子树、深度、高度等）；2. 二叉树：二叉树的定义、性质、存储结构（顺序存储、链式存储）、二叉树的遍历（前序、中序、后序遍历）；3. 二叉搜索树：二叉搜索树的定义、性质、插入、删除、查找操作；4. 平衡树：平衡二叉树的概念、AVL树的基本操作；5. 堆：堆的定义、性质、最大堆与最小堆的操作、堆排序；6. 树的应用：分析树在实际问题中的应用，如文件系统、组织结构、决策树等。
本章节教学内容依据课程目标，以《数据结构》教材为参考，系统性地安排了树的相关知识。
教学大纲明确指出，首先介绍树的基本概念和术语，接着深入学习二叉树及其遍历方法，然后扩展到二叉搜索树、平衡树和堆等特殊树结构，最后探讨树在实际应用中的价值。
优秀数据结构课程设计模板一、课程目标知识目标：1. 学生能理解数据结构的基本概念，掌握常用的数据结构类型及其特点。
2. 学生能描述线性表、栈、队列、树、图等数据结构的基本性质和应用场景。
3. 学生能运用所学知识分析实际问题的数据结构需求，并选择合适的数据结构进行解决。
技能目标：1. 学生具备使用编程语言实现各种数据结构的能力，并能熟练运用这些数据结构进行数据处理。
2. 学生能够运用算法分析技巧，评估不同数据结构在解决问题时的效率，优化程序性能。
3. 学生通过实际案例分析，培养解决复杂数据结构问题的能力，提高编程实践技能。
情感态度价值观目标：1. 学生能够认识到数据结构在计算机科学中的重要地位，增强对计算机科学的兴趣和热情。
2. 学生通过小组讨论和合作解决问题，培养团队协作能力和沟通能力。
3. 学生在学习过程中，养成积极思考、勇于探索的良好习惯，形成严谨、踏实的学术态度。
本课程针对高年级学生，课程性质为理论实践相结合。
在教学过程中，注重培养学生的动手能力、思维能力和创新能力。
课程目标旨在使学生在掌握基本数据结构知识的基础上，能够运用所学解决实际问题，提高编程技能，培养良好的团队协作和沟通能力，为后续学习打下坚实基础。
二、教学内容1. 数据结构基本概念：介绍数据结构的概念、作用和分类，引导学生理解数据结构在软件开发中的重要性。
教学内容：线性结构、非线性结构、逻辑结构与物理结构等。
2. 线性表：讲解线性表的定义、特点，以及线性表的顺序存储和链式存储实现。
教学内容：顺序表、链表、双向链表、循环链表等。
3. 栈与队列：介绍栈和队列的基本概念、操作及应用场景。
教学内容：栈的顺序存储和链式存储、队列的顺序存储和链式存储、栈与队列的应用等。
4. 树与二叉树：讲解树的基本概念、性质，重点介绍二叉树及其遍历算法。
教学内容：树的定义、二叉树的性质、二叉树的遍历、线索二叉树、二叉排序树等。
5. 图：介绍图的基本概念、存储结构，以及图的遍历算法。
西北工业大学智慧树知到“计算机科学与技术”《数据结构》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.树型结构最适合用来描述()。
A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据2.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作()型调整以使其平衡。
A.LLB.LRC.RLD.RR3.对于单链表形式的队列，队空的条件是()。
A.F=R=nullB.F=RC.F≠null且R=nullD.R-F=14.已知广义表a=((a,b,c),(d,e,f)),从a中取出原子e的运算是()。
A.tail(head(a))B.b.head(tail(a))C.head(tail(tail(head(a))))D.head(tail(tail(a)))5.二叉树在线索化后，仍不能有效求解的问题是()。
A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继6.对有序表18，20，25，34，48，62，74，85用二分查找法查找85，所需的比较次数为()。
A.1次B.2次C.3次D.4次7.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有()个结点。
A.15B.16C.17D.348.线性表的顺序存储结构是一种()存取结构。
A.随即存取B.顺序存取C.索引存取D.散列存取9.数据表A中有00个元素，如果仅要求求出其中最大的10个元素，则采用()排序。
A.堆排序B.希尔排序C.快速排序D.直接选择排序10.数据结构中，从逻辑上可以把数据结构分成()。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非先性结构D.内部结构和外部结构第1卷参考答案一.综合考核1.参考答案：C2.参考答案：B3.参考答案：A4.参考答案：D5.参考答案：D6.参考答案：D7.参考答案：D8.参考答案：A9.参考答案：A10.参考答案：C。
西北工业大学2022 年9 月《数据结构》作业考核试题及答案参考1. 对于哈希函数，冲突只能尽可能得少，不可能彻底避免。
( )A.正确B.错误参考答案： A2. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案： A3. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必挪移元素D.所需空间与线性表长度成正比参考答案： A4. 基数排序需要进行关键字的比较。
( )A.正确B.错误参考答案： B5. n 个结点的线索二叉树上含有的线索数为( )。
A.n-1B.n+1C.nD.2n参考答案： B6. B+树应用在( )文件系统中。
A.顺序B.散列C.VSAMD.ISAM参考答案： C7. 在头指针为 head 且表长大于 1 的单循环链表中，指针 p 指向表中某个结点，若p->next->next=head，则( )。
A、p 指向头结点B、p 指向尾结点C、*p 的直接后继是头结点D、*P 的直接后继是尾结点参考答案： D8. 设有 100 个数据元素，采用折半搜索时，最大比较次数为( )A.6B.7C.8D.10参考答案： B9. 已知二叉树的先序序列为 ABDECF，中序序列为 DBEAFC，则后序序列为( )。
A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案： B10. 哈希表不需要进行比较便可以直接取得所查记录。
( )A.正确B.错误参考答案： A11. 不含任何字符的串称为空串。
( )A、错误B、正确参考答案： B 12. 向一个有 127 个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要挪移( )个元素。
A.8B.63.5C.63D.7参考答案： B 13. 若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能浮现的出栈序列为( )。
《数据结构与算法》课程设计说明书题目：单词拼写检查器学院：计算机科学与工程专业：信息安全姓名：李培聪学号：1000360218指导教师：张瑞霞2012年0 9月08日目录引言 0“拼写检查器”——一个增强的记事本软件 (1)一、系统概述 (1)二、需求分析 (1)2.1系统分析 (1)“英文自动提示输入”功能也以对话框的形式进行实现，具有如下功能： (3)（1）输入单词的前缀部分，自动联想所有对应的后半部分，并显示在单词候选框里面。
3（2）双击候选框中单词自动将此单词插入到文本编辑界面的光标所在位置。
(3)2.2原理分析与数据需求 (3)因为计算机并不具备判断“哪些单词正确，哪些单词错误”的能力，所以无法直接通过某些语句或函数调用来实现“拼写检查”与“英文自动提示输入”功能。
假设计算机能够拥有地道的英国人的那种英文水平，那么我想也不需要有本程序的存在了。
(3)如何让计算机去判断一个单词的拼写正确性，这正是本程序要解决的核心问题所在。
以目前IT科技发展的现状来看，现在我们只能通过“把输入的单词与单词库每一个单词进行比较”这种方式来证明“这个单词是拼写正确的单词”。
正因此，为确保准确性，我们需要一个强大的英文单词库资源的支持。
为确保高效性，我们还需要一个合适的数据结构来存放单词库的数据以配合快速的检索算法。
(3)考虑到方便后期对字典进行维护，我选择了以TXT文本格式保存字典数据，并把这个TXT 文档作为项目的自定义资源封装到生成的EXE文件中。
这样，程序就等于自带了一个“字典库”。
这个“字典库”里存放了11万个英文单词，足以应对平时正常书写所包含的单词。
(3)当我们进行“把输入的单词与单词库每一个单词进行比较”这种操作。
将带来字符串的大量搜索操作。
于是需要我们从数据结构的选择和算法的设计上下功夫确保检索效率。
在这里我选用T RIE树来存储英文词典。
T RIE树俗称字典树、单词查找树，是应对单词检索操作的最优秀数据结构。
数据结构课程设计目录及正文一、课程设计目的数据结构是计算机科学中的一门重要基础课程，通过课程设计，旨在让学生更深入地理解和掌握数据结构的基本概念、原理和算法，并能够将其应用到实际问题的解决中。
培养学生的问题分析能力、算法设计能力、程序编写能力和调试能力，提高学生的综合素质和创新能力。
二、课程设计要求1、学生需独立完成课程设计任务，不得抄袭他人成果。
2、课程设计应具有清晰的结构和良好的可读性，代码规范，注释详细。
3、选择合适的数据结构和算法解决给定的问题，并对算法的时间复杂度和空间复杂度进行分析。
4、完成课程设计报告，包括问题描述、算法设计、程序实现、测试结果和总结等内容。
三、课程设计题目1、图书管理系统实现图书的添加、删除、查询、修改等功能。
按照图书的分类、作者、书名等进行排序和查找。
2、学生成绩管理系统录入学生的成绩信息，包括学号、姓名、课程名称、成绩等。
计算学生的平均成绩、总成绩，并按照成绩进行排序。
3、公交线路查询系统建立公交线路的网络模型。
实现站点之间的最短路径查询和换乘方案查询。
4、停车场管理系统模拟停车场的车辆进出管理。
计算停车费用，显示停车场的当前状态。
四、课程设计目录1、引言2、需求分析问题描述功能需求数据需求性能需求3、总体设计系统架构模块划分数据结构设计4、详细设计模块功能描述算法设计界面设计5、编码实现代码框架关键代码实现6、测试与调试测试用例测试结果调试过程7、总结课程设计的收获遇到的问题及解决方法对数据结构课程的进一步理解8、参考文献9、附录源程序代码五、正文内容（一）引言随着信息技术的不断发展，计算机在各个领域的应用越来越广泛。
数据结构作为计算机科学的重要基础，对于提高程序的效率和质量起着至关重要的作用。
本次课程设计旨在通过实际项目的开发，让学生将所学的数据结构知识运用到实践中，提高解决实际问题的能力。
（二）需求分析1、问题描述以图书管理系统为例，系统需要对图书馆中的图书进行有效的管理，包括图书的基本信息（书名、作者、出版社、出版日期、ISBN 号等）、图书的库存数量、借阅状态等。
《数据结构课程设计》教学大纲课程名称：数据结构课程设计适用专业：计算机科学与技术先修课程：数据结构学分：4总学时：60一、课程简介数据结构课程设计是为数据结构课程独立开设的一门实验课程。
数据结构课程设计是让学生综合运用数据结构课程中学到的几种典型数据结构，自行实现一个较为完整的应用系统的设计与开发。
其主要目的是使学生通过系统分析、系统设计、编程调试、写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用，进一步提高分析问题和解决问题的能力，提高程序设计水平。
二、课程目标目标1：掌握数据结构基本理论及相关算法，提出具体问题的正确数据结构表述和问题的合理解决方案和设计思想，培养学生对实际问题分析和设计能力。
目标2：能够针对特定问题进行探索，在编程环境中实现该问题的程序开发，培养学生实践动手能力。
目标3：针对特定问题的算法程序，进行实验数据验证和实验结果分析，并评价解决方案的性能，培养学生测试和分析能力。
三综合实践教学内容及要求（1）前期准备阶段1.教学内容：教师给学生讲解本课程设计的题目要求；学生完成选题及前期准备工作。
2.基本要求：（1）了解题目的基本要求，完成选题工作；（2）理解处理数据的逻辑结构、存储结构和解决问题的算法描述；（3）完成所选题目的概要设计，形成完整的设计方案。
3.重点及难点：重点：数据的逻辑结构、存储结构和相关算法的分析和设计。
难点：解决问题的算法分析和设计。
4.形成的成果及课外学习要求（1）要求学生完成题目的选取；（2）要求学生完成所选题目的概要设计；（3）要求学生想成所选题目的设计方案。
（2）设计实现阶段1.教学内容：学生在编程环境中完成程序的编辑、链接、运行和调试，形成功能正确的可执行文件，完成设计任务。
2.基本要求：（1）具备程序的编辑、链接、运行和调试能力；（2）具备系统开发设计能力；（3）能够在编程环境中实现课程设计题目的程序开发。
有时，我们会碰到对字符串的排序，若采用一些经典的排序算法，则时间复杂度一般为O(n*lgn)，但若采用Trie树，则时间复杂度仅为O(n)。
Trie树又名字典树，从字面意思即可理解，这种树的结构像英文字典一样，相邻的单词一般前缀相同，之所以时间复杂度低，是因为其采用了以空间换取时间的策略。
下图为一个针对字符串排序的Trie树(我们假设在这里字符串都是小写字母)，每个结点有26个分支，每个分支代表一个字母，结点存放的是从root节点到达此结点的路经上的字符组成的字符串。
将每个字符串插入到trie树中，到达特定的结尾节点时，在这个节点上进行标记，如插入"afb"，第一个字母为a，沿着a往下，然后第二个字母为f，沿着f往下，第三个为b，沿着b往下，由于字符串最后一个字符为'\0'，因而结束，不再往下了，然后在这个节点上标记afb.count++，即其个数增加1.之后，通过前序遍历此树，即可得到字符串从小到大的顺序。
（图取自网络）数据结构如下：[java]view plaincopy1.package com.trie;2.3.import java.util.ArrayList;4.import java.util.List;5./**6. * @author silence7. * @since 2013/7/28. * */9.public class Node {10. boolean isWord = false;11. Node[] child = new Node[26];//0-25：a:b12. List<String> pos = new ArrayList<String>();13.}实现代码：[java]view plaincopy1.package com.trie;2./**3. * @author silence4. * @since 2013/7/25. * */6.public class Trie {7. private Node root;8. Trie(){9. root = new Node();10. }11. public void addWord(String word,String pos){12. int len = word.length();13. Node s = root;14. for(int i =0;i<len;i++){15. int ch = word.charAt(i)-97;//c2 h716. if(s.child[ch] !=null){//有节点了17. s = s.child[ch];//后移18.19. }else{//没节点20. Node child = new Node();21. if(i==len-1){//最后一个字符22. child.isWord = true;23. child.pos.add(pos);24. }25. s.child[ch] = child;//挂上节点26. s = child;//后移27. }28. }29. }30. public void findWord(String word){31. int len = word.length();32. Node s = root;33. for(int i =0;i<len;i++){34. int ch = word.charAt(i)-97;35. if(s.child[ch]!=null){//节点存在36. s = s.child[ch];//后移37. if(i == len -1){38. for(String pos :s.pos){39. System.out.println(pos);40. }41. }42.43. }else{44. System.out.println("不存在这个单词");45. return ;46. }47.48. }49. }50.51. public static void main(String[] args) {52. Trie trie = new Trie();53. trie.addWord("silence", "1");54. trie.addWord("hello", "2");55. trie.addWord("word", "3");56.57. trie.findWord("silence");58.59. }60.61.}。
课程设计课程设计名称：数据结构课程设计专业班级：学生姓名：学号：指导教师：李磊课程设计时间：2015。
7.06—2015。
7。
10计算机类专业课程设计任务书目录目录 01需求分析 (2)1。
1系统介绍 (2)1.2程序的输入和输出 (2)1.3程序要达到的功能 (2)1。
4调试过程介绍 (2)2概要设计 (3)2。
1数据结构设计 (3)2.2系统模块设计 (3)3详细设计 (4)4系统演示 (19)4.1主界面 (19)4。
2数据录入 (20)4。
3翻译短文 (20)4。
4反译编码 (21)4。
5打印文件编码 (21)4。
6打印哈夫曼树 (22)5运行环境 (22)6课程心得总结 (23)参考文献； (23)1需求分析1.1系统介绍利用Huffman编码进行通信可以大大提高信道利用率．缩短信息传输时间，降低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道）,每端都需要一个完整的编／译码系统。
此程序就是为这样的信息收发站写一个Huffman码的编／译码系统。
1.2程序的输入和输出从终端读入字符集大小n,以及n个字符及各个字符的权值，建立赫夫曼树,并将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫夫曼树不在内存中,则从文件hfmTree中读取到内存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文件TextFile中；最后将已在内存中的哈夫曼树以直观的方式(树或凹入表形式）显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
1.3程序要达到的功能用户可以利用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文件的形式存到相应的文件里面。
1.4调试过程介绍（l)利用教材中的数据调试程序.(2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码选择2，输入THIS PROGRAM IS MY FAVORITE,屏幕上显示11010001011000111111000100010100110000100101010110010111011000111111 10010100011111110011101011000001001001001101101010同时文件codefile里面也出现相应的代码选择3，从codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE,并且文件textfile中也相应的存入了这段话.选择4，文件CodeFile以紧凑格式显示在终端上。
数据结构课程设计实验报告《课程设计》实验报告班级:学号:姓名:E-mail:日期:◎实验题目:字典树◎实验目的：设计合适的数据结构，建立字典树，解决文件中单词的搜索统计问题。
◎实验内容：现在有一个英文字典（每个单词都是由小写的'a'-'z'组成），单词量很大，达到100多万的单词，而且还有很多重复的单词。
此外，我们现在还有一些 Document，每个Document 包含一些英语单词。
针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。
1）基本型问题（1）选择合适的数据结构，将所有的英文单词生成一个字典Dictionary。
（2）给定一个单词，判断这个单词是否在字典 Dictionary中。
如果在单词库中，输出这个单词总共出现的次数。
否则输出NO。
2）扩展型问题（3）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。
例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。
（4）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。
（5）输出Dictionary中出现次数最高的10个单词。
3）高级型问题（6）现在我们有一些Document，每个Document 由一些单词组成，现在的问题就是给你一个word，检索出哪些 Document包含这个 word，输出这些Document 的DocumentID（就如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档）。
（7）在第（6）问中，我们只考虑了一个word 在哪些Document中的情况，我们进一步考虑2个相邻word的情况，检索出同时包含这两个相邻word的DocumentID。
4）挑战型问题（8）现在我们再对（7）的问题进行扩展，把（7）中的只检索相邻 2个word 推广到可以检索多个word（即连续的k个word，其中k>=2），检索出同时包含k 个连续word 的DocumentID。
我解决了前六个问题。
一、需求分析1．本程序演示中，程序自动读取目标文件，生成需要的文件。
2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据。
3．程序执行的主要命令包括：（1）构建栈；（2）构造字典树；（3）构建文件数；（4）树的查找；（5）结束。
二概要设计为实现上述算法，选择字典树为本程序的存储结构。
1、本程序包括三个模块：（1）主程序模块；（2）构建栈模块；（3）构造字典树模块；（4）构建文件数模块；（5）树的遍历模块；1、定义存储链表结构：（1）定义字典树与文件数结构：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#define NULL 0#define ERROR -1#define stack_in_size 100#define stackincrement 10struct TreeNode /*树结点*/{char ch;int number; /*以该字符为结束的单词出现的个数*/struct TreeNode* pt[26]; /*指向后继的字母的26个指针*/};struct TreeNode *root;typedef struct TreeNode *Link_TreeNode;struct MAX_TEN /*存放出现频率最高的十个单词数据结构*/{char STRING[35];int count; /*字符串出现的次数*/int xiabao; /*字符数组位置的下标*/};struct MAX_TEN MAX[10];struct MAX_TEN MIN;struct DocumentNode /*文件结点*/{char ch; /*存放某个单词的一个字符*/int number; /*以该字符为结束的单词出现的个数*/ struct DocumentNode* pt[26]; /*指向后继的字母的26个指针*/struct Locationn *next;/*连接以该字符为结束的单词所在的位置*/ };typedef struct DocumentNode *Link_DocumentNode;Link_DocumentNode ROOT[301]; /*300个根节点指针,零号单元不用*/ struct Locationn /*单词在文件中的位置*/{int num;struct Locationn *next;};struct WORD /*单词链表结构*/{char strr[35];struct WORD *next;};typedef struct{char *base;char *top;int stacksize;}SQSTACK;SQSTACK S,T;2、每个模块的分析：（1）主程序模块：void main(){printf("*****************基本型问题************************\n"); CREAT_DicTree();/*第一题，读入vocabulary文件，建立存放单词的字典树*/ printf("The First problem has been solved,a dictionary tree has been buildt\n");OPEN_SearchWordInVocabulary();/*第二题，生成SearchWordInVocabulary_Result.txt*/printf("The Second problem has been solved,SearchWordInVocabulary_Result.txt formed \n");printf("*****************扩展型问题************************\n"); OPEN_TotPrefixWord();/*第三题，生成TotPrefixWord_Result.txt*/printf("The Third problem has been solved,TotPrefixWord_Result.txt formed \n");OPEN_PrefixFrequence();/*第四题，生成PrefixFrequence_Result.txt*/ printf("The Forth problem has been solved,PrefixFrequence_Result.txt formed \n");OPEN_MostFrequenceWord();/*第五题，生成MostFrequenceWord.txt*/printf("The Fifth problem has been solved,MostFrequenceWord.txt formde\n");printf("*****************高级型问题************************\n"); CREAT_DocumentTree();/*第六题，读入Document文件，建立存放文件的树*/ printf("The Sixth problem has been solved,WordInDocument_Result.txt formed\n");}（2）构建栈模块：SQSTACK Creat() /*创建空栈*/{SQSTACK s;s.base=(char*)malloc(stack_in_size*sizeof(char));s.top=s.base;s.stacksize=stack_in_size;return s;} /*全局变量栈*/char pop(SQSTACK &s) /*出栈*/{char e;if(s.top==s.base)return ERROR;e=*(--s.top);return e;}void push(SQSTACK &s,char e) /*入栈*/{if(s.top-s.base>=s.stacksize){ s.base=(char*)realloc(s.base,(s.stacksize+stackincrement )*sizeof(char));s.top=s.base+s.stacksize;s.stacksize+=stackincrement;}*s.top=e;s.top=s.top+1;}int isempty(SQSTACK s) /*判断栈是否为空*/{if(s.base==s.top)return 1;elsereturn 0;}（3）构造字典树模块：Link_TreeNode creat() /*创建树结点，并返回指向该节点的指针*/ {int i;Link_TreeNode pt;pt=(Link_TreeNode)malloc(sizeof(TreeNode));pt->number=0;for(i=0;i<26;i++)pt->pt[i]=NULL;return pt;}void CREAT_DicTree() /*创建字典树*/{root=creat();Link_TreeNode q;FILE *fp;char *p;int ctmp;int jieshu;char str[35]; /*存放从文件中读入的单词*/if((fp=fopen("vocabulary.txt","r"))==NULL)printf("cannot open vocabulary.txt\n");while(1){jieshu=fscanf(fp,"%s",str);/*从文件中读入字符串*/q=root;if(jieshu==-1)break;else{p=str;while(*p!='\0'){ctmp=*p-97;if(q->pt[ctmp]!=NULL)q=q->pt[ctmp];else{q->pt[ctmp]=creat();q=q->pt[ctmp];q->ch=*p;}p++;if(*p=='\0'){q->number++;break;}}}}}（4）构建文件数模块：Link_DocumentNode CREAT()/*创建一个文件型的数据结构结点，并返回指向该节点的指针*/{int i;Link_DocumentNode p;p=(Link_DocumentNode)malloc(sizeof(struct DocumentNode));p->number=0;for(i=0;i<26;i++){p->pt[i]=NULL;}p->next=NULL; /*文件初始化*/return p;}void CREAT_DocumentTree() /*读入文件，创建文件树*/{Link_DocumentNode q;struct Locationn *LL;FILE *fp;char *p;int ctmp;int jieshu;int Location; /*定位单词在文章中的位置*/int k;char str[35]; /*存放从文件中读入的单词*/if((fp=fopen("Document.txt","r"))==NULL)printf("cannot open Document.txt\n");while(1){jieshu=fscanf(fp,"%s",str);if(jieshu==-1)break; /*文件中单词已读完*/if(!strcmp(str,"Document")){fscanf(fp,"%d",&k);ROOT[k]=CREAT();Location=1;fscanf(fp,"%s",str);}q=ROOT[k];p=str;while(*p!='\0') /*处理每个单词*/{ctmp=*p-97;if(q->pt[ctmp]!=NULL)q=q->pt[ctmp];else{q->pt[ctmp]=CREAT();q=q->pt[ctmp];q->ch=*p;}p++;if(*p=='\0'){q->number++;if(q->next==NULL){LL=(struct Locationn *)malloc(sizeof(struct Locationn));LL->num=Location;q->next=LL;LL->next=NULL;Location++;break;}else{LL=q->next;while(LL->next!=NULL)LL=LL->next;LL->next=(struct Locationn *)malloc(sizeof(struct Locationn));LL=LL->next;LL->next=NULL;LL->num=Location;Location++;break;}}}}}（5）程序使用的函数：SQSTACK Creat()char pop(SQSTACK &s)void push(SQSTACK &s,char e)int isempty(SQSTACK s)Link_TreeNode creat()void CREAT_DicTree()int Search(char str[],Link_TreeNode root)Link_TreeNode Get_Last_Link(char str[])bool OutPrint(Link_TreeNode p,FILE *fp)void RECHANGE_MIN(char tepp[],int cunt)bool GOT_MAX_TEN(Link_TreeNode p)Link_DocumentNode CREAT()void CREAT_DocumentTree()int Search_Doc(char str[],Link_DocumentNode root)void SORT_MAX_Ten()struct WORD *Creat_two_word_link(char str1[],char str2[])struct WORD *Creat_multi_word_link(int length,FILE *fp)void Search_Match_Word(struct WORD *head,int length,FILE *fp)void OPEN_SearchWordInVocabulary()void OPEN_TotPrefixWord()void OPEN_PrefixFrequence()void OPEN_MostFrequenceWord()void main()3、数据结构示意图：‘每个树结点有26个孩子四使用说明、测试分析及结果1、程序使用说明：（1）本程序的运行环境为VC6.0。
