自组织线性表

1、背景自组织线性表根据估算的访问频率排列记录，先放置请求频率最高的记录，接下来是请 求频率次高的记录，依此类推。自组织线性表根据实际的记录访问模式在线性表中修改记录 顺序。自组织线性表使用启发式规则决定如何重新排列线性表。转置方法的基本原理是，在 一次查找过程中，一旦找到一个记录，则将它与前一个位置的记录交换位置。这样，随着时 间的推移，经常访问的记录将移动到线性表的前端，而曾经频繁使用但以后不再访问的记录 将逐渐退至线性表的后面。尽管一般情况下自组织线性表的效率可能没有查找数和已排序的线性表那么好，但它也 有自身的优势。它可以不必对线性表进行排序，新记录的插入代价很小；同时也比查找树更 容易实

2、现，且无需额外的存储空间。问题描述用转置法实现一个自组织线性表，保存一组汉字用于查询。基本要求（1）从文件中读入一组汉字集合，用自组织线性表保存。（2）在查询时，采用转置法调整自组织线性表的内容。（3）从文件中依次读入需查询的汉字，把查询结果保存在文件中（如找到，返回比 较的次数，如果没有找到，返回比较的次数）需求分析（1）输入的形式：输入汉字的个数n,n为大于0的正整数，并输入一组汉字；（2） 输出的形式：输出是否找到（查询成功查找不成功）和比较的次数；（3）程序所达到的功能：本程序可以通过用户从键盘中输入汉字个数n和n个汉字进行 保存，然后用户通过输入汉字对储存的汉字进行访问，对n个汉字根

3、据估算的访问 频率进行排序，并输出查询的汉字是否查找成功和查询的次数的信息；但是该程序 不处理有相同字的一组汉字：（4）测试数据：输入：5汉字的个数请输入一组汉字：我是中国人请输入查找的汉字：中国输出：中查询成功3/比较的次数输出：国查询成功4/比较的次数概要设计：抽象数据类型的定义：因为数据对象和数据关系符合线性表的数据结构，可以 采用线性表数据结构。线性表的ADT：数据对象：D= ai I ai EElemSet, i=1,2,.,n, n30 （ 称n为线性表的表长；称n=0时的线性表为空表。数据关系：R1 = |ai-1 ,aiED, i=2,.,n 基本操作：void Creat(l

4、ink *l)创建新的线性表void swap(link *l,int i,int j)/交换两个元素bool find(link *l,char *s)/查找基本算法思想：自组织线性表根据估算的访问频率排列记录，先放置请求频率最 高的记录，接下来是请求频率次高的记录，依此类推。自组织线性表根据实际的 记录访问模式在线性表中修改记录顺序。自组织线性表使用启发式规则决定如何 重新排列线性表。转置方法的基本原理是，在一次查找过程中，一旦找到一个记录，则将它与前一 个位置的记录交换位置。这样，随着时间的推移，经常访问的记录将移动到线性 表的前端，而曾经频繁使用但以后不再访问的记录将逐渐退至线性表的后

5、面程序的流程：程序由三个模块组成：输入模块：汉字个数的输入及需保存的汉字序列的输入排序模块：输入查询的汉字，查询时进行自组织线性表排序输出模块：输出查询是否成功和查询的次数详细设计：(1)物理数据类型：由于自组织线性表中元素的位置与元素的访问频率有关，可 以采用专制的方法来实现自组织线性表，也就是把找到的记录与它在线性表 中的前一条记录交换位置，随着时间的推移把最常用的记录移动到线性表的 前面。定义数组：typedef struct Node/保 存汉字char data3;Node;typedef struct link/线性表Node *node;int length;link;void

6、Creat(link *l)创建新的线性表的伪代码：void Creat(link *l)coutl-length;l-node=(Node *)malloc(l-length*sizeof(Node);coutlength”汉字”； getchar();for(int i=0;ilength;i+)gets(l-nodei.data);void swap(link *l,int i,int j)/交换两个元素的伪代码：void swap(link *l,int i,int j)char s3;strcpy(s,l-nodei.data);strcpy(l-nodei.data,l-nodej

7、.data);strcpy(l-nodej.data,s);bool find(link *l,char *s)/查找的伪代码：bool find(link *l,char *s)for(int i=0;ilength;i+)if(!strcmp(s,l-nodei.data)if(i!=0)swap(l,i,i-1);cout”查找成功”；couti+1endl;比较的次数return true;return false;cout ”查找不成功”；couti+1endl;/ 比较的次数算法的具体步骤：第一步 获取汉字个数n及n个汉字，建立n为长度的汉字数组第二步输入一个汉字，在数组中比较查找，若为数组中的第一个即是要 找的汉字，则不处理，若不是第一个，则将该汉字与前一个汉字在数组中 的位置进行交换，并输出查找成功和比较的次数；若没找到这个汉字，则 输出查找不成功和查找的次数；第三步重复执行第二步操作或者结束查找算法的时间分析