数据结构课设.doc

数据结构课程设计报告 课程题目：低频单词过滤系统和马鞍点统计 实现方法： C 语 言 班 级： 软 件 101 姓 名： 赖 敏 指导教师： 董 跃 华 成 绩：_________________________ 信息工程学院 2012年6月17日 目录 第一部分 第一章 需求分析 1.1 项目内容及要求 …………………………………………………1 第二章 概要设计 2.1 数据定义 …………………………………………………………2 2.2 函数模块 …………………………………………………………3 2.3 算法实现 …………………………………………………………4 第三章 详细设计 3.1 函数伪码算法 ……………………………………………………6 3.2 主程序伪码算法 …………………………………………………12 第四章 调试分析 4.1 问题及分析 ………………………………………………………15 4.2 经验总结 …………………………………………………………16 第五章 测试结果 5.1 程序测试结果 ……………………………………………………16 第二部分 需求分析 概要设计 源代码 调试分析 附录 参考文献  第一部分 需求分析 陈述说明程序设计的任务,强调的是程序要做什么，需要么结果、所能达到的功能。 1.1 项目内容及要求 内 容： 对于一篇给定的英文文章，分别利用线性表和二叉排序树来实现单词频率的统计，实现低频词的过滤，并比较两种方法的效率。 设计要求： 1. 读取英文文章文件（InFile.txt），识别其中的单词。 2. 分别利用线性表和二叉排序树构建单词的存储结构。当识别出一个单词后，若线性表或者二叉排序树中没有该单词，则在适当的位置上添加该单词；若该单词已经被识别，则增加其出现的频率。 3. 统计结束后，删除出现频率低于五次的单词，并显示该单词和其出现频率。 4．其余单词及其出现频率按照从高到低的次序输出到文件中（OutFile.txt），同时输出用两种方法完成该工作所用的时间。 5．计算查找表的ASL值，分析比较两种方法的效率。 6．系统运行后主菜单如下： 当选择1后进入以下界面： 其中选择2时显示利用线性表来实现所有功能所用的时间。 当在主菜单选择2二叉排序树后，进入的界面与上图类同。 注意：1、写入到文件的单词，是删除低频单词后的单词； 2、计算的时间是单词以不同存储方式写入OutFile.txt时间。 概要设计 数据对象定义以及一些基本操作。 2.1 数据定义 一、以线性链表存储的数据定义如下： typedef struct lnode{ //定义线性表节点 char word[20]; int count; struct lnode *next; }lnode,*linklist; void createlink(linklist h,char *word); //建立线性链表，链表中已存在该单词计数器加1；否则创建新节点，计//数器置1 linklist delword1(linklist h); //删除链表中频度小于5的节点，删除的节点生成新链表，返回新链表头//指针 void sortlink(linklist h); //对链表进行降序排序 void printlink(linklist h); //在屏幕上输出链表 void outfile1(linklist h); //将链表输出到文件OutFile.txt double runtime1(linklist h); //返回链表输入文件OutFile.txt的时间 Float asllink(linklist h); //返回链表的平均查找长度 void dislink(linklist h); //释放链表空间 二、二叉排序树的数据定义如下： typedef struct bstode{ //二叉排序树节点定义 char word[20]; int count; struct bstode *lchild,*rchild; }bstode,*bstree; bstree createnode(bstree t,linklist h);