数据结构C++版课程设计报告数据结构C++版课程设计报告.doc

数据结构课程设计 报告 姓 名： 学 号： 专 业： 联系电话： E m a il:  目录 报告一 拼写检测器 3 1. 实验题目 3 2. 问题描述 3 3. 概要设计 3 4. 详细设计 4 5. 测试结果及分析 6 6. 源代码 8  报告一 拼写检测器 实验题目 拼写检测器（Speller checker） 问题描述 1. load the words in the dictionary file（加载字典文件） 2 .read the text file to be checked （读取被检测文件） 3. look up each word from the text file in the dictionary （逐个单词的检测其拼写） 4. print out the misspelled words in alphabetical order with their line numbers.（按字典顺序打印出错误的单词及其行号）例如某被检测文件内容如下： 显然第二行的laanguage和第六行的ammong拼写错误，输出应该： ammong 6 laanguage 2 概要设计 字典存储结构选择 由于所有的单词的长短不一，单词中字母重复的部分很多，如果用数组存储字典的话很浪费空间，所以考虑用树存储字典，相同部分只存储一次，每一棵树只存储相同字母开头的所有单词，从上往下，依次存储，孩子的脚标与字母对应（0-25号树的树根分别存放A-Z，26-51号树的树根分别存放a-z，其孩子也是一样）。 树的ADT 定义： ADT DTree{ 数据对象：D=｛ai | ai属于ElemSet，i=1，2，……，n n=0｝ 数据关系：若D为空集，则树为空；若紧含一个数据元素，则数据关系为空，否则： D中仅有一个称为跟（root）的数据元素，关系R没有前驱。 除根结点外，其余结点划分m个互不相交的子集，对任意的子集Di，root，xi属于R。 基本操作： InitTree( T); //建立空树 DestroyTree（ T）； //销毁树 Root(T) ; //求树跟 Insert（T，x）； //将元素x插入树中 Chile（T，x，i）； //求x结点的第i个孩子 ｝ADT DTree 排序存储结构选择 若选用数组，排序的时间复杂度很高，其单词长短不一，选用链表。 链表抽象数据定义 ADT LinkList{ 数据对象：D=｛ai| ai属于ElemSet，i=1，2，……，n n=0｝ 数据关系：R=｛ai-1,ai|ai-1,ai属于D，i=1，2，……，n n=0｝ 基本操作： Init（L）； //构造一个空链表 InsertInOrder（L，x）； //将元素插入有序表中使之仍然有序 DisPlay（）； //输出结点信息 ｝ADT LinkList； 其他函数 主函数main（）。 建字典函数CreateDTree（）。 检测拼写函数Checkspell（）。 详细设计 树存储字典，每个单词的字母是一个结点，而链表存放单词及行号，用WordsLine结构体单词及行号，定义结点类ListNode、链表类LinkList、树结点类DTreeNode、树类DTree。 Stuct struct WordsLine {//结点类，存放错误的单词及其行号 string word; int LineNumber; }; class ListNode //结点类定义 { friend class LinkList; //声明链表类LinkList为友元类 private: WordsLine data; //结点的数据域 ListNode* next; //结点的后继指针域，存放后继结点的地址 public: ListNode();//构造函数 ListNode(const WordsLine e):data(e),next(NULL){} //构造函数 WordsLine GetData(){return data;} //返回结点的数据值 ListNode* GetNext(){return next;} //返回结点的指针值 void SetData(WordsLine e){data=e;} //设置结点的数据值 void SetNext(