快速排序和散列表数据结构实验报告.docx
- 文档编号:17149802
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:19
- 大小:141.31KB
快速排序和散列表数据结构实验报告.docx
《快速排序和散列表数据结构实验报告.docx》由会员分享,可在线阅读,更多相关《快速排序和散列表数据结构实验报告.docx(19页珍藏版)》请在冰点文库上搜索。
快速排序和散列表数据结构实验报告
HUNANUNIVERSITY
数据结构
实验报告
题目:
散列表和快速排序
学生姓名
学生学号
专业班级
指导老师夏艳
日期2016.05.24
实验7快速排序
背景
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
假设含n个记录的序列为{R1,R2,…,Rn}
其相应的关键字序列为{K1,K2,…,Kn}
这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系:
Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn}的操作称作排序。
排序算法是计算机科学中最重要的研究问题之一。
对于排序的研究既有理论上的重要意义,又有实际应用价值。
它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。
常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。
例1:
有时候应用程序本身就需要对信息进行排序。
为了准备客户账目,银行需要根据支票的号码对支票排序;
例2:
在一个绘制互相重叠的图形对象的程序中,可能需要根据一个“在上方”关系将各对象排序,以便自下而上地绘出对象。
例3:
在一个由n个数构成的集合上,求集合中第i小/大的数。
例4:
对一个含有n个元数的集合,求解中位数、k分位数。
问题描述
在操作系统中,我们总是希望以最短的时间处理完所有的任务。
但事情总是要一件件地做,任务也要操作系统一件件地处理。
当操作系统处理一件任务时,其他待处理的任务就需要等待。
虽然所有任务的处理时间不能降低,但我们可以安排它们的处理顺序,将耗时少的任务先处理,耗时多的任务后处理,这样就可以使所有任务等待的时间和最小。
只需要将n件任务按用时去从小到大排序,就可以得到任务依次的处理顺序。
当有n件任务同时来临时,每件任务需要用时ni,求让所有任务等待的时间和最小的任务处理顺序。
基本要求
(1)数据的输入输出格式:
输入:
第一行是一个整数n,代表任务的件数。
接下来一行,有n个正整数,代表每件任务所用的时间。
输出:
输出有n行,每行一个正整数,从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。
按此顺序进行,则使得所有任务等待时间最小。
(2)使用快速排序,轴值采用随机数确定。
测试数据
输入
9
534261573
输出
1
2
3
3
4
5
5
6
7
实验提示
(1)将n个正整数排序后依次输出即可。
(2)需调用srand(),才能让每次的随机数不一样。
选做内容
若采用并行操作系统,一次可同时处理两件任务,求让所有任务等待的时间和最小的任务处理顺序。
课后题目
给出一个能列出某一集合的k分位数的O(nlogk)的算法。
一、需求分析
本程序需要利用数组来存放操作数,需要一个比较关键码大小的函数和一个交换顺序的函数,和进行快排操作的快排函数。
测试用例
输入
9
534261573
输出
1
2
3
3
4
5
5
6
7
二、概要设计
抽象数据类型
抽象数据类型
算法的实质是对一个数组存储数据的关键码进行一个排序操作,任何一种排序算法都可以达到同样的效果,只不过是时间代价不一样,我们需要用时间开销相对较少的快速排序函数堆元素关键码进行排序;
算法的基本思想
1.利用随机数产生轴值。
为保证轴值在相应的范围内可采用:
rand()%(j-i+1)+i进行处理,那么返回的结果就在i到j之间。
2.将轴值的位置的数与末尾的数进行互换。
3.进行数据的调整,l从左边开始,找到第一个比轴值处数大的元素,然后让r从右边开始找到第一个比轴值处数小的元素,将l和r对应的这两个数进行互换。
如此进行,直到l>=r。
最后返回l的值,作为将轴值正确归位的下标索引。
4.按照上述函数返回的索引交换l和末尾的数(轴值归位),则l左边的数比轴值小,右边的数比轴值大。
5.l将整个数组分为左右两部分,两边再进行同样的快排操作。
三、程序的流程:
程序由三个模块组成:
输入模块:
读入任务数n,和每件任务所花的时间,存放在数组里面。
处理模块:
进行快排操作。
输出模块:
将排好序的数据输出。
四、详细设计:
物理数据类型
boolcomp(inta,intb)//比较函数,如果排序的关键码a> b则返回true,否则返回false。
voidswap(int*a,inti,intj)//交换函数
intfindpivot(inti,intj)//在排序关键码范围内随机选取轴值
intpartition(intArray[],intleft,intright,intpivot)//将记录移动到合适的分组
voidqsort(intArray[],inti,intj)//快排函数
算法的时空分析
快速排序算法在最差情况下算法时间开销并不比冒泡排序小,最佳情况则为,log(n)平均时间代价为θ(nlog(n))。
四、调试分析
本算法很好理解,就是通过递归将数据按照和轴值比较的结果分为大于轴值和小于轴值的两部分,在对这两部分按同样的方法递归到数组有序;
五、测试结果
实验8散列表
背景
散列表(Hashtable,也叫哈希表),是根据关键码值(Keyvalue)而直接进行访问的数据结构。
也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
这个映射函数叫做散列函数,存放记录的数组叫做散列表。
在理想情况下,查找、插入、删除操作的时间均为O
(1),是一种高效的动态集合结构。
例1:
计算机程序设计语言的编译程序需要维护一个符号表,其中元素的关键值为任意字符串,与语言中的标识符对应。
该符号表常采用散列表。
例2:
为了节约空间,常常需要把文本文件采用压缩编码方式存储。
LZW是对文本文件进行压缩和解压缩的方法之一,该方法采用了散列。
问题描述
我们希望在浩瀚的图书中,去发现一本书是否存在。
我们不知道书的编号,只知道它的书名。
(其实这已经不错了...)。
通过书名,来查询它是否存在。
为了简化问题,我们假设每本书的书名都是一组小写字母组成,长度不超过100字符。
基本要求
(1)根据输入建立图书名称表,采用散列表实现该表,散列函数选用BKDE字符串哈希。
(2)数据的输入输出格式:
输入分为两部分
第一部分,第一行是行数n,n<=5000。
余下n行,每行一个字符串。
表示已存在的图书记录。
第二部分,第一行是行数m,m<=1000。
余下m行,每行一个字符串。
表示要查询的图书记录。
输出:
输出为m行,如果被查的记录存在,则输出"YES",如果不存在则输出"NO"。
测试数据
输入:
4
a
ans
and
hellocpp
9
a
b
an
as
ans
and
ande
hellocbb
hellocpp
输出:
YES
NO
NO
NO
YES
YES
NO
NO
YES
实验提示
(1)冲突处理方法为:
顺次循环后移到下一个位置,寻找空位插入。
(2)BKDE字符串哈希
unsignedinthash_BKDE(char*str)
{
/*初始种子seed可取31131131313131131313etc..*/
unsignedintseed=131;
unsignedinthash=0;
while(*str)
{
hash=hash*seed+(*str++);
}
return(hash&0x7FFFFFFF);
}
将字符串哈希到小于2^31的整数t,再将t用随机数哈希法映射到2^15以内的数。
选做内容
每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,采用折叠法构造一个四位数的哈希函数。
课后题目
实现文本LZW压缩和解压缩。
一、需求分析
1.本程序要求利用散列表存储和查找图书,查找成功则输出YES,否则输出NO。
2.本程序使用给定的一个散列函数BKDE首先将字符串哈希到小于2^31的整数t散列地址,然后通过随机散列函数hash_rand将上述地址t再次哈希到2^15范围,我使用了取余法映射到了32768(2^15),虽然有点大,但是好像题目是这样要求的,不会是我理解错了吧~-~;
3.遇到冲突处理方法为:
从发生冲突的地址顺次循环后移到下一个位置,寻找空位插入;
4.搜索也是使用上述两个哈希映射找到对应地址,查看地址处的图书关键码是否是需要查找的图书关键码,如果不是则从那个地址往下搜索到一个匹配的关键码即可。
测试用例
输入:
4
a
ans
and
hellocpp
9
a
b
an
as
ans
and
ande
hellocbb
hellocpp
输出:
YES
NO
NO
NO
YES
YES
NO
NO
YES
二、概要设计
抽象数据类型
1、抽象数据类型
为实现数据的快速查找功能,需要用散列表存储数据,并且将映射函数以及冲突处理方法作为查找的函数和方法;
散列表的映射使用了给定的BKDE函数和用取余法映射的随机映射函数;
主函数通过HashingLisst类的insert函数插入一个新元素,通过find函数查找需要查找的元素,没有找到返回NO,找到则返回YES.
算法的基本思想
通过编写两个映射函数来确定存储数据的地址,函数BKDE为实验要求给出,随机映射函数为自己选择合适的映射方法写出,散列表使用数组来实现吗,冲突解决机制为往后搜索一个空位置直接插入。
三、程序的流程:
程序由三个模块组成:
(1)输入模块:
通过键盘输入图书名存储图书,通过键盘输入图书名来查找图书;
(2)功能模块:
存储图书调用insert函数,检索调用find函数;
(3)输出模块:
查找到相应图书则输出YES,否则输出NO。
四、详细设计:
物理数据类型
unsignedinthash_BKDE(char*str)//散列函数
unsignedinthash_rand(unsignedintvalue)//随机散列函数
classHashingList//散列表类
voidHashingList:
:
insert(char*str)//散列表类的插入数据成员函数
boolHashingList:
:
find(char*str)//散列表类的检索数据成员函数
算法的时空分析
如果不发生冲突,散列表的插入和查找是通过映射直接找得到,如果发生冲突,也能快速从冲突位置向下检索得到,除非散列表里没有该元素则会检索到散列表尾部,时间代价跟散列表的均匀冲突程度有关,所以算法时间代价为θ
(1)。
四、调试分析
本算法并没有什么特别难理解的地方,是很简单的一个算法,主要是理解散列表的检索机制。
五、测试结果
七、附录
程序源代码(c++)
1.快速排序
/*快速排序*/
#include
#include
usingnamespacestd;
boolcomp(inta,intb)//比较函数
{
returna>b;
}
voidswap(int*a,inti,intj)//交换函数
{
inttemp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
intfindpivot(inti,intj)//随机产生轴值
{
srand(time(NULL));
returnrand()%(j-i+1)+i;
}
intpartition(intArray[],intleft,intright,intpivot)//将记录移动到合适的分组
{
do
{
while(comp(pivot,Array[++left]));//不断向后移动直到找到第一个大于pivot
while((left swap(Array,left,right); } while(left returnleft;//返回右分组的第一个位置 } voidqsort(intArray[],inti,intj)//快排函数 { if(j<=i)return; intpivotindex=findpivot(i,j);//找到轴值 swap(Array,pivotindex,j);//将轴值移到数组最后 intk=partition(Array,i-1,j,Array[j]);//返回分组后的右边第一个位置 swap(Array,k,j);//将轴值放到数组分组右边的第一个位置 qsort(Array,i,k-1);//对左半部分继续快排 qsort(Array,k+1,j);//对右半部分继续快排 } intmain() { inti,n; cin>>n; int*Array=newint[n]; for(i=0;i cin>>Array[i]; qsort(Array,0,n-1); for(i=0;i cout< return0; } 2.散列表 /*散列表*/ #include #include usingnamespacestd; constintMAX=32768;//散列表最大长度 constintNAMESIZE=100;//书名长度 unsignedinthash_BKDE(char*str)//散列函数 { unsignedintseed=131; unsignedinthash=0; while(*str) { hash=hash*seed+(*str++); } return(hash&0x7FFFFFFF); } unsignedinthash_rand(unsignedintvalue)//随机散列函数 { unsignedintaddress=value%MAX;//取余法将地址映射到MAX(2^15)内 returnaddress; } unsignedintHash(char*str)//生成通过BKDE散列函数和hash_rand随机散列函数的映射地址; { returnhash_rand(hash_BKDE(str)); } classHashingList//散列表类 { private: char**Array;//散列表数组 intArraySize;//散列表长度 public: HashingList(); ~HashingList(); voidinsert(char*); boolfind(char*); }; HashingList: : HashingList()//构造函数里初始化散列表 { ArraySize=MAX; Array=newchar*[ArraySize]; for(inti=0;i { Array[i]=newchar[NAMESIZE]; Array[i]=NULL; } } HashingList: : ~HashingList(){} voidHashingList: : insert(char*str)//插入一个数据 { unsignedintpos=Hash(str); while(Array[pos]! =NULL)//往后寻找空位置插入 pos++; Array[pos]=str; } boolHashingList: : find(char*str)//搜索函数,找到关键码 { unsignedintpos=Hash(str); while(Array[pos]! =NULL) { if(Array[pos]==str)returntrue; pos++; } returnfalse; } intmain() { boolArray[20];//定义一个20本图书容量的数组 char*str=newchar[NAMESIZE];//开辟一个存储图书名字的数组 HashingListHashing;//定义一个散列表类的变量Hashing cout<<"输入图书本数n: "; intn; cin>>n; getchar(); cout<<"输入n个书名: "< for(inti=0;i { cin>>str; getchar(); Hashing.insert(str); } cout<<"输入待查的图书本数m: "; intm; cin>>m; getchar(); cout<<"输入图书名: "< for(intj=0;j { cin>>str; getchar(); Array[j]=Hashing.find(str); } cout<<"输出: "< for(intk=0;k if(Array[k]) cout<<"YES"< else cout<<"No"< return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 排序 列表 数据结构 实验 报告