自组织线性表.doc

题目:自组织线性表
背景
自组织线性表根据估算的访问频率排列记录,先放置请求频率最高的记录,接下来是请求频率次高的记录,依此类推。自组织线性表根据实际的记录访问模式在线性表中修改记录顺序。自组织线性表使用启发式规则决定如何重新排列线性表。转置方法的基本原理是,在一次查找过程中,一旦找到一个记录,则将它与前一个位置的记录交换位置。这样,随着时间的推移,经常访问的记录将移动到线性表的前端,而曾经频繁使用但以后不再访问的记录将逐渐退至线性表的后面。
尽管一般情况下自组织线性表的效率可能没有查找数和已排序的线性表那么好,但它也有自身的优势。它可以不必对线性表进行排序,新记录的插入代价很小;同时也比查找树更容易实现,且无需额外的存储空间。
问题描述
用转置法实现一个自组织线性表,保存一组汉字用于查询。
基本要求
(1) 从文件中读入一组汉字集合,用自组织线性表保存。
(2) 在查询时,采用转置法调整自组织线性表的内容。
(3) 从文件中依次读入需查询的汉字,把查询结果保存在文件中(如找到,返回比较的次数,如果没有找到,返回比较的次数)
实验分析:
题目要求用转置方法实现自组织线性表,也就是把找到的记录与它在线性表中的前一条记录交换位置,随着时间的推移把最常用的记录移动到线性表的前面。函数void transpose(char a[][2],int i,int j)实现字符串的交换位置。int search(char a[][2],int size,char c[2])函数用于查找是否有相应的字符,在自组织线性表中。
实验代码:
#include<iostream>
using namespace std;
bool flag;
void transpose(char a[][2],int i,int j); //转置函数的声明
int search(char a[][2],int size,char c[2]);//search函数的声明
int main(){
int i,m,n,num;
static char a[200][2],b[200][2],c[2];
cin>>a[0];
for(i=0;;i++){
if(a[i][0]==0)
break;}
m=i;
cin>>b[0];
for(i=0;;i++){
if(b[i][0]==0)
break;
}
n=i;
for(i=0;i<n;i++){
num=search(a,m,b[i]);
c[0]=b[i][0];
c[1]=b[i][1];
if(flag)
cout<<"查找"<<c<<"成功,查找次数为:"<<num<<endl;
else
c