大数据结构实验七自组织线性表.docx
- 文档编号:17471092
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:18
- 大小:152.79KB
大数据结构实验七自组织线性表.docx
《大数据结构实验七自组织线性表.docx》由会员分享,可在线阅读,更多相关《大数据结构实验七自组织线性表.docx(18页珍藏版)》请在冰点文库上搜索。
大数据结构实验七自组织线性表
HUNANUNIVERSITY
课程实验报告
题目:
自组织线性表
学生姓名
学生学号
专业班级
指导老师李晓鸿
完成日期2015年12月31日
一.需求分析
1.程序功能
本程序可输入汉语句子和要查找的汉字,并用需查找的汉字与汉字句子中的汉字进行查找比较,把查找到的汉字在顺序表中用转置法排序,输出查找结果与比较次数。
2.输入形式
用户输入句子,可以输入空格,不对非法输入做处理,假定输入的数据都合法汉字。
用户输入要查找的字,用空格隔开。
3.输出形式
输出要查找的汉字和查找结果及比较次数,并将输出保存到文件中。
要查找的汉字为:
“汉字A”查找成功,比较次数为。
。
。
。
。
。
“汉字B”查找失败,比较次数为。
。
。
。
。
。
4.测试数据
①数据1:
请输入文字(文字间可输入空格):
我爱你中国
请输入查找的字们(中间用空格隔开):
你你你你中国
输出:
你查找成功!
查找次数为:
3
你查找失败!
查找次数为:
2
你查找成功!
查找次数为:
1
你查找成功!
查找次数为:
1
中查找成功!
查找次数为:
4
国查找成功!
查找次数为:
5
②数据2:
请输入文字(文字间可输入空格):
隔壁老王买了个瓜很甜
请输入查找的字们(中间用空格隔开):
瓜很甜老王
输出:
瓜查找成功!
查找次数为:
3
很查找失败!
查找次数为:
2
甜查找成功!
查找次数为:
1
老查找成功!
查找次数为:
4
王查找成功!
查找次数为:
5
③数据3:
请输入文字(文字间可输入空格):
一二三四五六七八
请输入查找的字们(中间用空格隔开):
六六二二
输出:
六查找成功!
查找次数为:
6
六查找成功!
查找次数为:
5
二查找成功!
查找次数为:
2
二查找成功!
查找次数为:
1
④数据4:
请输入文字(文字间可输入空格):
君不见黄河之水天上来奔流到海
请输入查找的字们(中间用空格隔开):
不见君
输出:
不查找成功!
查找次数为:
2
见查找失败!
查找次数为:
3
君查找成功!
查找次数为:
3
⑤输入:
请输入文字(文字间可输入空格):
小明我真不知道该输入什么了
请输入查找的字们(中间用空格隔开):
你是小鸿吗
输出:
你查找成功!
查找次数为:
2
是查找失败!
查找次数为:
3
小查找成功!
查找次数为:
3
鸿查找失败!
查找次数为:
3
吗查找成功!
查找次数为:
3
二.概要设计
1.抽象数据类型
将每一个元素储存在一个有序并且有限的序列中,每一个元素都有一个自己的位置,也都有一个数据类型,所以使用线性表来储存每一个文字。
2.线性表ADT{
数据对象:
定义线性表的最大储存元素maxsize;
当前储存元素数listsize;
数据关系:
若listsize=0,则线性表没有元素,为空;
基本操作:
alist(intn)//构造函数
~alist()//析构函数
boolappend(inta)//增加元素
boolgetValue(int&it)const//获得it位置线性表的值
boolinsert(inta)//插入元素}
3.算法基本思想
自组织线性表根据估算的访问频率排列记录,先放置请求频率最高的记录,接下来是请求频率次高的记录,依此类推。
自组织线性表根据实际的记录访问模式在线性表中修改记录顺序。
自组织线性表使用启发式规则决定如何重新排列线性表。
转置方法的基本原理是,在一次查找过程中,一旦找到一个记录,则将它与前一个位置的记录交换位置。
这样,随着时间的推移,经常访问的记录将移动到线性表的前端,而曾经频繁使用但以后不再访问的记录将逐渐退至线性表的后面
4.程序基本流程
该程序主要分为输入模块,转置查找模块和输出模块
(1)读入模块:
从文件中读入一组汉字集合,并保存在自组织线性表中,读入要查找的汉字。
(2)转置查找模块:
依次根据需查找的汉字对汉字线性表遍历一次进行查找,若查找到该汉字,调用转置函数,将该汉字与前一个位置的汉字转置,然后继续查找下一个汉字。
(3)输出模块:
若查找到汉字,则输出到屏幕和文件中查找成功并显示查找次数;若没有查找到该汉字,输出到屏幕和文件中查找不成功并显示查找的次数。
三.详细设计
1.物理数据类型
本题中需要元素的交换,由于每个中文占用两个字节的函数,使用数组交换只需要交换数组的两个元素,较为便利,所以使用顺序表来实现线性表。
顺序表的伪代码
classAList
{
private:
intlistsize;
intmaxsize;
intfence;
Elem*listArray;
public:
AList(intsize)
{
maxsize=size;
fence=listsize=0;
listArray=newElem[size];
}
~AList(){delete[]listArray;}
voidsetStart(){fence=0;}
voidsetEnd(){fence=listsize;}
voidprev(){if(fence!
=0)fence--;}
voidnext(){
if(fence<=listsize)
fence++;
}
boolgetValue(Elem&it)const{
it=listArray[fence];
returntrue;
}
boolinsert(Elemitem){
if(listsize==maxsize)returnfalse;
for(inti=listsize;i>fence;i--)
listArray[i]=listArray[i-1];
listArray[fence]=item;
listsize++;
returntrue;
}
boolappend(Elem&item)
{
if(listsize=maxsize)returnfalse;
listArray[listsize++]=item;
returntrue;
}}
2.算法的具体步骤
顺序表的构建——查找元素——转置
顺序表的构建:
先将文字输入到一个string类的字符串中,再将字符串中每一个元素逐个赋值给顺序表,值得注意的是中文每个字占两个字符串,在赋值时需要跳过空格,即线性表中值存储文字。
stringa;
getline(cin,a);//可输入空格
for(inti=0;i { if(a[i]=='') { continue; } listArray[listsize]=a[i]; listsize++; } maxsize=listsize; returntrue; } 查找元素: 输入一组汉字,在顺序表中比较查找,若为数组中的第一个即是要找的汉字,则不处理(在swap函数里进行判断),若不是第一个,则将该汉字与前一个汉字在数组中的位置进行交换,并输出查找成功和比较的次数;若没找到这个汉字,则输出查找不成功和查找的次数。 并且注意跳过空格。 voidfind() { cout<<"请输入查找的字们(每个字间输入空格): "< stringb; getline(cin,b); inti; intsize=0; for(intj=0;j { if(b[j]=='') { j--;continue; } intjudge=0; for(i=0;i<=listsize;i+=2) { if(listArray[i]==b[j]&&listArray[i+1]==b[j+1]) { judge=1; swap(i); break; } } if(judge) cout<<"“"< "< else cout<<"“"< "< } } 转置: 若果查找成功,则进行转置,因为中文占两个字符,所以需要将两个字符转置。 如果需要转置的中午是开头,就不需要转置直接返回true。 boolswap(intn) { if(n<=1) returntrue; Elemtemp; temp=listArray[n]; listArray[n]=listArray[n-2]; listArray[n-2]=temp; temp=listArray[n+1]; listArray[n+1]=listArray[n-1]; listArray[n-1]=temp; return0; } 3.算法时空分析 n个汉字,查找n次,时间复杂度为O(n)。 4.输入输出格式 ①.输入 请输入文字(文字间可输入空格): cout<<"请输入文字(文字间可输入空格): "< stringa; getline(cin,a);//可输入空格 请输入查找的字们(中间用空格隔开): cout<<"请输入查找的字们(每个字间输入空格): "< stringb; getline(cin,b); ②.输出 查找成功,显示查找次数: if(judge) cout<<"“"< "< 查找失败,显示查找次数: else cout<<"“"< "< 4.测试结果 ①.测试1 ②.测试2 ③.测试3 ④.测试4 ⑤.测试5 5.实验心得 书上顺序表定义完整,题目难度不大,较前几次试验,比较简单。 六.附录 #include #include #include"iostream" usingnamespacestd; #defineElemchar classAList { private: intlistsize; intmaxsize; intfence; Elem*listArray; public: AList(intsize) { maxsize=size; fence=listsize=0; listArray=newElem[size]; } ~AList(){delete[]listArray;} voidsetStart(){fence=0;} voidsetEnd(){fence=listsize;} voidprev(){if(fence! =0)fence--;} voidnext(){ if(fence<=listsize) fence++; } boolgetValue(Elem&it)const{ it=listArray[fence]; returntrue; } boolinsert(Elemitem){ if(listsize==maxsize)returnfalse; for(inti=listsize;i>fence;i--) listArray[i]=listArray[i-1]; listArray[fence]=item; listsize++; returntrue; } boolappend(Elem&item) { if(listsize=maxsize)returnfalse; listArray[listsize++]=item; returntrue; } boolstar() { cout<<"请输入文字(文字间可输入空格): "< stringa; getline(cin,a);//可输入空格 for(inti=0;i { if(a[i]=='') { continue; } listArray[listsize]=a[i]; listsize++; } maxsize=listsize; returntrue; } voidfind() { cout<<"请输入查找的字们(每个字间输入空格): "< stringb; getline(cin,b); inti; intsize=0; for(intj=0;j { if(b[j]=='') { j--;continue; } intjudge=0; for(i=0;i<=listsize;i+=2) { if(listArray[i]==b[j]&&listArray[i+1]==b[j+1]) { judge=1; swap(i); break; } } if(judge) cout<<"“"< "< else cout<<"“"< "< } } boolswap(intn) { if(n<=1) returntrue; Elemtemp; temp=listArray[n]; listArray[n]=listArray[n-2]; listArray[n-2]=temp; temp=listArray[n+1]; listArray[n+1]=listArray[n-1]; listArray[n-1]=temp; return0; } }; intmain() { ALista(100); a.star(); a.find(); system("pause"); return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 组织 线性