数据结构实验七自组织线性表.docxVIP

HUNAN UNIVERSITY 课程实验报告 题 目： 自组织线性表 学生姓名 学生学号 专业班级 指导老师 李 晓 鸿 完 成 日期 2 0 1 5年 12 月 31日 一．需求分析 程序功能 本程序可输入汉语句子和要查找的汉字，并用需查找的汉字与汉字句子中的汉字进行查找比较，把查找到的汉字在顺序表中用转置法排序，输出查找结果与比较次数。 2.输入形式 用户输入句子，可以输入空格，不对非法输入做处理，假定输入的数据都合法汉字。 用户输入要查找的字，用空格隔开。 3.输出形式 输出要查找的汉字和查找结果及比较次数，并将输出保存到文件中。 要查找的汉字为： “汉字A”查找成功，比较次数为。。。。。。 “汉字 B”查找失败，比较次数为。。。。。。 4.测试数据  = 1 \* GB3 ①数据1： 请输入文字（文字间可输入空格）： 我爱你 中国 请输入查找的字们（中间用空格隔开）： 你 你 你 你 中 国 输出： 你 查找成功！查找次数为：3 你 查找失败！查找次数为：2 你 查找成功！查找次数为：1 你 查找成功！查找次数为：1 中 查找成功！查找次数为：4 国 查找成功！查找次数为：5 ②数据2： 请输入文字（文字间可输入空格）： 隔壁老王买了个瓜 很甜 请输入查找的字们（中间用空格隔开）： 瓜 很 甜 老 王 输出： 瓜 查找成功！查找次数为：3 很 查找失败！查找次数为：2 甜 查找成功！查找次数为：1 老 查找成功！查找次数为：4 王 查找成功！查找次数为：5  = 3 \* GB3 ③数据3： 请输入文字（文字间可输入空格）： 一二三四五六七八 请输入查找的字们（中间用空格隔开）： 六六二二 输出： 六 查找成功！查找次数为：6 六 查找成功！查找次数为：5 二 查找成功！查找次数为：2 二 查找成功！查找次数为：1 ④数据4： 请输入文字（文字间可输入空格）： 君不见黄河之水天上来 奔流到海 请输入查找的字们（中间用空格隔开）： 不 见 君 输出： 不 查找成功！查找次数为：2 见 查找失败！查找次数为：3 君 查找成功！查找次数为：3  = 5 \* GB3 ⑤输入： 请输入文字（文字间可输入空格）： 小明 我真不知道该输入什么了 请输入查找的字们（中间用空格隔开）： 你 是 小 鸿 吗 输出： 你 查找成功！查找次数为：2 是 查找失败！查找次数为：3 小 查找成功！查找次数为：3 鸿 查找失败！查找次数为：3 吗 查找成功！查找次数为：3 二．概要设计 1.抽象数据类型 将每一个元素储存在一个有序并且有限的序列中，每一个元素都有一个自己的位置，也都有一个数据类型，所以使用线性表来储存每一个文字。 2.线性表ADT{ 数据对象：定义线性表的最大储存元素maxsize; 当前储存元素数listsize; 数据关系：若listsize=0,则线性表没有元素，为空; 基本操作：alist(int n)//构造函数 ~alist()//析构函数 bool append(int a)//增加元素 bool getValue(int it) const //获得it位置线性表的值 bool insert(int a)//插入元素} 3.算法基本思想 自组织线性表根据估算的访问频率排列记录，先放置请求频率最高的记录，接下来是请求频率次高的记录，依此类推。自组织线性表根据实际的记录访问模式在线性表中修改记录顺序。自组织线性表使用启发式规则决定如何重新排列线性表。 转置方法的基本原理是，在一次查找过程中，一旦找到一个记录，则将它与前一个位置的记录交换位置。这样，随着时间的推移，经常访问的记录将移动到线性表的前端，而曾经频繁使用但以后不再访问的记录将逐渐退至线性表的后面 4.程序基本流程 该程序主要分为输入模块，转置查找模块和输出模块 读入模块：从文件中读入一组汉字集合，并保存在自组织线性表中，读入要查找的汉字。 转置查找模块：依次根据需查找的汉字对汉字线性表遍历一次进行查找，若查找到该汉字，调