实验七自组织线性表.doc

HUNAN UNIVERSITY

课程预习报告

题 目： 自组织线性表
学生姓名
学生学号 2012080102
专业班级 计算机科学与技术班
完 成 日 期

－ 4 －
一、需求分析
自组织线性表根据估算的访问频率排列记录，先放置请求频率最高的记录，接下来是请求频率次高的记录，依此类推。自组织线性表根据实际的记录访问模式在线性表中修改记录顺序。自组织线性表使用启发式规则决定如何重新排列线性表。转置方法的基本原理是，在一次查找过程中，一旦找到一个记录，则将它与前一个位置的记录交换位置。这样，随着时间的推移，经常访问的记录将移动到线性表的前端，而曾经频繁使用但以后不再访问的记录将逐渐退至线性表的后面。
尽管一般情况下自组织线性表的效率可能没有查找数和已排序的线性表那么好，但它也有自身的优势。它可以不必对线性表进行排序，新记录的插入代价很小；同时也比查找树更容易实现，且无需额外的存储空间。
程序能达到的功能：
（1） 从文件中读入一组汉字集合，用自组织线性表保存。
（2） 在查询时，采用转置法调整自组织线性表的内容。
（3） 从文件中依次读入需查询的汉字，把查询结果保存在文件中（如找到，返回比较的次数，如果没有找到，返回比较的次数）
二、概要设计
抽象数据类型
由于每个汉字都有唯一的第一元素和最后元素，每个元素都有唯一的前驱和唯一的后继所以我们用线性表来存储汉字，且汉字是占两个字符位置，因此我们用二维数组来存储汉字。
ADT Array_2{
D={ai,j|ai,j∈汉字字符,0≤i≤b1-1, 0≤j≤b2-1}
R={R1,R2}
R1={<ai,j,ai+1,j>|ai,j,ai+1,j ∈D,0≤i≤b1-2,0≤j≤b2-1}
R2={<ai,j,ai,j+1>|ai,j,ai,j+1 ∈D,0≤i≤b1-1,0≤j≤b2-2}
基本操作P:
InitArray(&A,b1,b2); //初始化二维数组
DestroyArray (&A); //删除这个二维数组
ValueArray (A, &e,index1,index2);
AssignArray (&A, e, index1,index2);
} ADT Array_2
算法的基本思想
将文件中的汉字读入存储数组，将需要查找的汉字输入查找数组中，然后将查找数组中的汉字依次与存储数组中的汉字进行比较，若找到该汉字则进行转置操作，交换该汉字与前一个汉字的位置和比较次数，若没有找到则输出存储数组的长度，循环此操作一直到查找数组中的汉字全部查找完毕。
程序流程
程序主要由三个步骤组成： 
输入模块：读入两组汉字。
处理模块：计算两组汉字的个数，进行查找，互换操作。
输出模块：将查找结果输出。
三、详细设计
实现概要设计中的数据类型
倒置函数，查找到一次后，与前一个位置的数互换
bool flag;
void Inverse(char a[][2],int i,int j){
char temp=a[i][0];
a[i][0]=a[j][0];
a[j][0]=temp;
temp=a[i][1];
a[i][1]=a[j][1];
a[j][1]=temp;
}
查找汉字
int search(char a[][2],int size,char c[2]){
flag=0;
int i;
for( i=0;i<size;i++)
if(a[i][0]==c[0] && a[i][1]==c[1]){
//汉字所占的两位是否都相同
flag=1;
break;
}
if(flag){
if(i>0)
Inverse(a,i,i-1);
return i+1;
}
else
return size; //如果找不到则查找次数为以保存汉字的个数
}
主函数：
int main(){
int i,size1,size2,num;
static char a[100][2],b[100][2],c[2];
cin>>a[0];//每个汉字占两个字符的位置
for(i=0;;i++){
if(a[i][0]==0)
break;
}
size1=i; //计算该组汉字的长度
cin>>b[0];
for(i=0;;i++){
if(b[i][0]==0)
break;
}
size2=i;
for(i=0;i<size2;i++){
num=search(a,size1,b[i]);
c[0]=b[i][0];
c[1]=b[i][1];
if(flag)
cout<<"查找---"<<c<<"---成功！查找次数为："<<num<<endl;
else
cout<<"查找---"<<c<<"---失败！查找次数为："<<num<<endl;
}
system("pause");
return 0;
}
算法的时空分析
查找的最优情况是比较一次，即Θ(1)，最差情况比较n次，即Θ(n)。
int search(char a[][2],int size,char c[2]) 查找函数

函数的调用关系图

void Inverse(char a[][2],int i,int j) 转置函数
主函数

输入和输出的格式
输入          
请输入一串汉字

请输入你要查询的汉字(可以输多个汉字)
若成功则输出提示语句并且输出查找次数
若失败则输出提示语句并且输出查找次数
四、测试结果